比赛链接:https://atcoder.jp/contests/abc284
做出了四个题。第五个题很简单可以直接暴力,但是怂了。
E题:大意是给出n个点,m条边,度最多为10。求从1开始的简单图。超过1e6输出1e6。
注意到度最多为10和1e6就可以直接暴力,简简单单。
code:
const int nn = 2e5+10; vector<int> ve[nn]; bool sign[nn]; int ans = 0; void dfs(int cur){ if(ans>=1e6) return; for(int i=0;i<ve[cur].size();i++){ if(!sign[ve[cur][i]]){ ans++; sign[ve[cur][i]] = true; dfs(ve[cur][i]); sign[ve[cur][i]] = false; } } } int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n'); ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0); int n,m; cin>>n>>m; int a,b; for(int i=1;i<=m;i++){ cin>>a>>b; ve[a].push_back(b); ve[b].push_back(a); } sign[1] = true; ans=1; dfs(1); cout<<min(ans,int(1e6))<<endl; }
F题:大意是给出一个字符串。该字符串假设为a + b+ c组成。那么b的逆串为a+b。求是否存在。以及b开始的位置的前一个下标。
字符串哈希。抽象字符串前后缀为数字,记录pow。
最后遍历一遍n/2,找一个位置。计算两种数值相减。细节很多。
code:
hashv operator + (hashv a,hashv b) { int c1=a.fi+b.fi,c2=a.se+b.se; if (c1>=mod1) c1-=mod1; if (c2>=mod2) c2-=mod2; return make_pair(c1,c2); } hashv operator - (hashv a,hashv b) { int c1=a.fi-b.fi,c2=a.se-b.se; if (c1<0) c1+=mod1; if (c2<0) c2+=mod2; return make_pair(c1,c2); } hashv operator * (hashv a,hashv b) { return make_pair(1ll*a.fi*b.fi%mod1,1ll*a.se*b.se%mod2); } const int nn = 2e6+10; hashv pw[nn],s[nn],t[nn]; char tt[nn]; int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n'); ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0); int n; cin>>n; n=n*2; cin>>tt+1; hashv base = make_pair(13331,23333);//定义某种进制数,做双哈希 pw[0] = make_pair(1,1);//定义0次方为1 for(int i=1;i<=n;i++){//正向将字符串哈希到s pw[i] = pw[i-1]*base;//进制数,用于相减 s[i] = s[i-1]*base + make_pair(tt[i],tt[i]); } for(int i=n;i>=1;i--){//反向将字符串哈希到t t[i] = t[i+1]*base + make_pair(tt[i],tt[i]); } for(int i=1;i<=n/2;i++){ hashv s1 = s[i]*pw[n/2-i] + (s[n]-s[n/2+i]*pw[n/2-i]);//零散的高阶+尾巴 hashv s2 = t[i+1]-t[i+n/2+1]*pw[n/2]; //一个高阶带尾巴 - 另一个尾巴的高阶 = 零散高阶带尾巴 if(s1==s2){ for(int j=i+n/2;j>i;j--) cout<<tt[j]; cout<<endl; cout<<i<<endl; return 0; } } cout<<-1<<endl; }