题目链接:https://codeforc.es/gym/444200/problem/F
大意是存在一个类字符串为 ababa ,修改为类似马拉车算法的,&|a|b|a|b|a|,给出每个位置以它为中心的回文半径的长度。
构造一个仅包含a和b的字符串,满足输入的2*n+2长度的序列。
根据序列构造字符串,设当前字符串长度为r,当r<a[i]+i-1时,将左边的移动到右边来。
code:
void solve() { int n; cin>>n; for(int i=1;i<=2*n+2;i++){ cin>>a[i]; } char ch = 'a'; for(int i=1,r=1;i<=2*n+2;i++){ while(i+a[i]-1>r) r++,c[r] = c[2*i-r]; if(i==1) c[i] = '&'; else if(i%2==0) c[i] = '|'; else if(c[i]==0) c[i] = ch, ch = (ch=='a'?'b':'a'); } for(int i=1;i<=2*n+2;i++){ if(c[i]!='&'&&c[i]!='|') cout<<c[i]; } }
题目链接:https://codeforc.es/gym/444200/problem/H
大意是给出一个无向图,对于i从1-n的任意一个点的边数 到 任意j从1-n的任意一个点的边数。f(i,j) = cnt[i]&cnt[j] + cnt[i]|cnt[j] + cnt[i]^cnt[j] 求cgm。
猜想:因为n和m大小差不多,也就是说m不是很大,那么一定存在许多边数一样的点。直接哈希一下边数相同的数量,然后暴力+公式跑一下。
code:
const int nn = 1e6+10; vector<int> ve[nn]; void solve() { int n,m; cin>>n>>m; int x,y; for(int i=1;i<=m;i++){ cin>>x>>y; ve[x].push_back(y); ve[y].push_back(x); } map<ll,ll>mp; for(int i=1;i<=n;i++){ mp[ve[i].size()]++; } vector<int> kk; for(auto c:mp){ kk.push_back(c.fi); } ll ans = 0; for(int i=0;i<kk.size();i++){ for(int j=i+1;j<kk.size();j++){ ans+=mp[kk[i]]*mp[kk[j]]*(kk[i]&kk[j])*(kk[i]|kk[j])*(kk[i]^kk[j]); ans%=mod9; } } cout<<ans<<endl; }
题目链接:https://codeforc.es/gym/444200/problem/J
这题当时读的有点不太明白。大意就是给出一个序列,每天可以占有土地并吸取前缀和。需要保证能量为非负数,不能保证输出-1.
做法:记录下前缀和,然后每到一个点更新一下当前最大前缀和,如果为负数,求去累加一下前面最大的前缀和。题不是很难,,,,
code:
int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n'); ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0); ll n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; s[i] = s[i-1]+a[i]; } if(s[n]<0){ cout<<-1<<endl; return 0; } ll maxt = 0; ll sum = 0; ll ans = 0; for(int i=1;i<=n;i++){ ans++; maxt = max(maxt,s[i]); if(sum+s[i]<0){ if(maxt<=0){ cout<<-1<<endl; return 0; } else{ ll sy = abs(sum+s[i]); ans+=upchu(sy,maxt); sum+=maxt*(upchu(sy,maxt)); } } sum+=s[i]; } cout<<ans<<endl; }
题目链接:https://codeforc.es/gym/444200/problem/K
大意是有n+1个人投骰子,第一个人只能投1-m中的一个数,每个骰子有m面。求1-m的失败概率。
做法:这个题是队友做的,当时我绕进去出不来了。这个题对于1-n次投掷,都是等概率的,跟之前的结果有关系,所以每次概率都是(m-i)^n/(m-1)^n
啊啊啊啊啊。这个题没想出来是我的锅,队友狠狠捞了一把。
code:
void solved() { int n,m; cin>>n>>m; for(int i=1;i<=m;i++) { int a=quick_power(m-i,n,mod); int b=quick_power(m-1,n,mod); cout<<a*quick_power(b,mod-2,mod)%mod<<" "; // cout<<((a%mod)*quick_power(b,mod-2,mod))%mod<<" "; } }
题目链接:https://ac.nowcoder.com/acm/contest/58871/D
大意是给出一个n*m的图,每个点存在一个数。你可以从任意点作为起点,四连通移动,如果数相等,不加能力,如果比当前小+1能力,否则不能移动(比当前数大)。求最大能量值。
做法:记忆化搜索。记忆化是想到了,但是没想到怎么具体实现它。这个题我们可以反向考虑,我们从小点往大点搜索,这样我们就可以覆盖掉大点的所有获得的最大能量。初始每个点能量为-1,如果点能量比走的步数多了就直接返回,否则,进行赋值并搜索。
code:
void dfs(int curx,int cury,int w){ if(f[curx][cury]>=w) return; f[curx][cury] = w; for(int i=0;i<4;i++){ int nx = curx+fx[i],ny = cury+fy[i]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m){ if(a[nx][ny]>a[curx][cury]) dfs(nx,ny,w+1); else if(a[nx][ny]==a[curx][cury]) dfs(nx,ny,w); } } } void solve() { cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; f[i][j] = -1; } } int ans = 0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dfs(i,j,0); } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) ans = max(ans,f[i][j]); } cout<<ans<<endl; }
题目链接:https://ac.nowcoder.com/acm/contest/58871/I
大意是建立n-1条连通n个点的树,给出每个点可以链接的边数,求最小花费。链接两个点的代价是i*i+j*j。
做法:这个题很好,首先我们需要确定的是每个都应该被连接,先预处理一下每个点。我们需要链接n-1条边,所需的代价就是(n-1)*2次代价,然而我们已经给出了n个代价,也就是还有n-2个代价需要我们给出。从小到大依次给出这些代价即可。很巧妙的题,好评!
code:
void solve() { int n; cin>>n; ll ans = 0; for(ll i=1;i<=n;i++){ cin>>a[i]; ans+=i*i; a[i]--; } int num = n-2; for(ll i=1;i<=n;i++){ while(a[i]){ ans+=i*i; num--; a[i]--; if(num==0){ cout<<ans<<endl; return; } } } cout<<-1<<endl; }
题目链接:https://ac.nowcoder.com/acm/contest/58177/C
大意是构造一颗数,使得树有n种状态。规则为,如果该点为僵尸,则它的子树点全为僵尸,如果该点为猫,则它的子树点不受限制。
做法:这个题比赛的时候没想出来。这个题应该要倒着做,首先可以确定的是如果直连,状态只会+1,倒着做对应-1,对于任意分叉的节点,贡献为*2+1,这里想到了,其实就是可以在n为奇数时直接/2整除。2特判一下,然后就是3的时候直接连一条边就可以了,这些特判条件还是挺难想到的。
总结一下就是,n&1时,n为3直接链接,否则从上一个点分两支。n&1=0时,直接直连一条边,然后更新即可。
code:
void solve() { ll n; cin>>n; ll cu = 2; if(n==2){ cout<<1<<endl; return; } vector<ii> ve; int pre = 1; for(int i=2;i<=1e5&&n>2;i++){ if(n&1){ if(n==3){ ve.push_back(make_pair(pre,i)); break; } ve.push_back(make_pair(pre,i)); i++; ve.push_back(make_pair(pre,i)); pre = i; n/=2; }else{ ve.push_back(make_pair(pre,i)); pre = i; n--; } } cout<<ve.size()+1<<endl; for(auto c:ve){ cout<<c.fi<<' '<<c.se<<endl; } }
题目链接:https://ac.nowcoder.com/acm/contest/58177/M
这个题快气死我了。啊啊啊啊啊。大意就是说给出一个n*m的矩阵仅含01,最外面一圈都是0,要求构造两个矩阵,满足a矩阵和b矩阵共同的1在原矩阵为1,否则为0。a和b的构造需要能够四连通,注意是连通不是四面有1。
做法,直接首先初始化ab为原,然后奇a为1,偶b为1(对行操作吧),然后对于列第一列初始a1 b0 ,最后一列a0 b1,类似这种构造。
code:
void solve() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ string s; cin>>s; for(int j=0;j<s.size();j++){ c[i][j+1] = s[j]-'0'; a[i][j+1] = b[i][j+1] = c[i][j+1]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(i&1){ a[i][j] = 1; }else b[i][j] = 1; } } for(int i=1;i<=n;i++){ a[i][1] = 1; b[i][1] = 0; a[i][m] = 0; b[i][m] = 1; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cout<<a[i][j]; cout<<endl; } // cout<<endl; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cout<<b[i][j]; cout<<endl; } }
————