cf4 近日补题
19ecA:city 这题 是今年蓝桥省赛的一个加强版,求一个组合数即可。 令e1,e2,o1,o2分别为横竖的奇数对和偶数对数(因为两个奇数或两个偶数才能让中点是格点,即两数之和为偶数),结果如代码所示。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 int get (int n) { return n*(n-1 )/2 ; } signed main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); int n,m;cin >>n>>m; n+=1 ;m+=1 ; int e1=n/2 ; int e2=m/2 ; int o1=n-e1; int o2=m-e2; cout <<(get(e1)+get(o1))*(get(e2)+get(o2))*2 +m*(get(e1)+get(o1))+n*(get(e2)+get(o2))<<endl ; }
19ecE:Flow 题 中每条路不共用节点,且等长,目标容量可以直接算出,计算cost时,可以只记录添加的,不用管从哪来。 在移动过后,每一段的多条边(第一条路的第i段,第二条路的第i段。。。)容量的和即为目标容量,但是,每条路上的边其实是不用分先后的,最后每条边的流量应该都一样,如果按原来的顺序,那么可能有2-4与5-3这样的对应出现,我们其实期望的是4向2移动,5向3移动,即根据大小关系移动,而上述情况相当于出现了一个虚伪的交换(通过错位),我们要消除这个影响,可以对一条路上的边按边权排序,只从后向前移动。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 const int maxn=2e5 +100 ;int ver[maxn],head[maxn],nxt[maxn],edge[maxn];int tot;void add (int x,int y,int z) { ver[++tot]=y,nxt[tot]=head[x],head[x]=tot; edge[tot]=z; } vector <int > v[maxn];int d[maxn];void dfs (int x,int num) { for (int i=head[x];i;i=nxt[i]){ int y=ver[i]; v[num].push_back(edge[i]); dfs(y,num); } } signed main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); int n,m;cin >>n>>m; ll x,y,z; tot=0 ; ll totflow=0 ; for (int i=1 ;i<=m;++i){ cin >>x>>y>>z; add(x,y,z); totflow+=z; } int num=0 ; for (int i=head[1 ];i;i=nxt[i]){ int y=ver[i]; v[++num].push_back(edge[i]); dfs(y,num); sort(v[num].begin(),v[num].end()); } int len=v[1 ].size(); for (int i=1 ;i<=len;++i){ for (int j=1 ;j<=num;++j){ d[i]+=v[j][i-1 ]; } } ll pf=totflow/len; ll ans=0 ; for (int i=1 ;i<=len;++i){ if (d[i]<pf)ans+=pf-d[i]; } cout <<ans<<endl ; }
19ec M:Value 读错题 了。。。b会减去多次。 因为次幂不相交(即若a的b次方是c,那么不存在一个d,不是a的幂且d的e次方是c)那么就可以根据这一列中最小的那个分组,则每一列直接不互相影响,且每一列都只有20以内元素,爆算也只有1e5,总共只有1e2数量级的非平凡列(只有一个数的列).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 const int maxn=1e5 +100 ;const int M=1e5 +10 ;ll a[maxn]; ll b[maxn]; int v[maxn];ll sz=0 ; vector <int > vs[M];ll dfs (vector <int > &v,bitset <40 > &bt,int now) { ll ans=0 ; if (now==sz){ for (int i=0 ;i<sz;++i){ if (bt[i]==0 )continue ; ll tmp=a[v[i]]; for (int j=0 ;j<i;++j){ if ((i+1 )%(j+1 )==0 &&bt[j]==1 ){ tmp-=b[v[i]]; } if (tmp<0 )break ; } if (tmp>0 )ans+=tmp; } return ans; } ans=dfs(v,bt,now+1 ); bt[now]=1 ; ans=max(dfs(v,bt,now+1 ),ans); bt[now]=0 ; return ans; } signed main () { std ::ios::sync_with_stdio(false );std ::cin .tie(0 ); int n;cin >>n; ll ans=0 ; for (int i=1 ;i<=n;++i){ cin >>a[i]; } for (int i=1 ;i<=n;++i){ cin >>b[i]; } ans+=a[1 ]; int tot=0 ; for (ll i=2 ;i<=n;++i){ if (v[i]==1 )continue ; tot++; for (ll j=i;j<=n;j*=i){ vs[tot].push_back(j); v[j]=1 ; } } for (int i=1 ;i<=tot;++i){ bitset <40> bt; sz=vs[i].size(); ans+=dfs(vs[i],bt,0 ); } cout <<ans<<endl ; }
1527C|1600|Sequence Pair Weight 题意 是有多少有序对,使对应下标的数字相等,只要将相同数字的下标抽出来计算贡献即可,先维护一个后缀和,然后扫一遍即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 per(){ ll n;cin >>n; ll tmp; map <ll,vector <ll> > ma; for (int i=1 ;i<=n;++i){ cin >>tmp; ma[tmp].push_back(i); } ll ans=0 ; for (auto i:ma){ if (i.second.size()>=2 ){ int sz=i.second.size(); l[sz+1 ]=0 ; for (int j=sz-1 ;j>=0 ;--j){ l[j+1 ]=l[j+2 ]-i.second[j]+n+1 ; } for (int j=1 ;j<=sz;++j){ ans+=i.second[j-1 ]*l[j+1 ]; } } } cout <<ans<<endl ; }
1527B|1900|Palindrome Game 题意为ab可以花费1将0变1,结束后谁花的多谁输。 分为两个阶段:
1:将其变为回文串
如果一开始就是回文,就直接第二轮
如果有一个0需要变,a直接变,让b做下一轮先手,这样他必输2分,直接判负,除法第二轮没有0,就直接翻转让b变,赢他一分
如果有多个0,先翻转,让b一直做,最后看情况最后一个要不要自己变。
2:第二轮,除法没有0,否者先手亏两分
3:特殊情况是中间一个0,这时a要先填这里,然后让b继续填第一轮,然后抢最后一手,让b在第二轮再次先手。
(这ALICE真tnd聪明!)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 per(){ int n;cin >>n; cin >>in+1 ; int cnt1=0 ; int cnt2=0 ; for (int i=1 ;i<=n/2 ;++i){ if (in[i]!=in[n-i+1 ]){ cnt1++; } if (in[i]=='0' &&in[n-i+1 ]=='0' ){ cnt2++; } } if (cnt1==0 &&cnt2==0 &&in[n/2 +1 ]=='1' ){ cout <<D<<endl ; continue ; } if (n&1 &&in[n/2 +1 ]=='0' ){ if (cnt2==0 &&cnt1==1 ){ cout <<D<<endl ; }else if (cnt1==0 &&cnt2==0 ){ cout <<B<<endl ; }else cout <<A<<endl ; }else { if (cnt2==0 ){ cout <<A<<endl ; }else { if (cnt1==0 ){ cout <<B<<endl ; }else cout <<A<<endl ; } } }