CF Edu 143 A-D vp补题+每日一茶_Showball.

网络投稿 02-07 1898

CF Edu 143 A-D vp补题

最近在打数模，导致这场cf也没有参加，于是就在抽空补一下题，题目难度还可以。自己的状态也还可以。等数模结束，就恢复一天一vp(和群友一起)。题目链接

A. Two Towers 题意：给你两个只含有“B”，“R”的字符串，你可以将一个字符串的任意倒数的n个字母（至少要剩下一个）拼接到另外一个字符串上，问你能否保证两个字符串中均没有出现相邻字母相同的情况。思路：我们发现如果能够构成，那么需要满足一些条件，两个字符串中相邻相等字符数最多只能为1.并且两个字符串的尾部字符不能相同，否则没办法进行拼接。对这些条件判断一下即可。

void Showball(){ int n,m; cin>>n>>m; string a,b; cin>>a>>b; int cnt=0; for(int i=0;i<n-1;i++){ if(a[i]==a[i+1]) cnt++; } for(int i=0;i<m-1;i++){ if(b[i]==b[i+1]) cnt++; } if(a[n-1]==b[m-1]) cnt++; if(cnt<=1) cout<<"YES"<<endl; else cout<<"NO"<<endl; }

B. Ideal Point 题意：定义一个函数f(x)，表示x在所给的区间中出现的次数。现在给你一些区间，和一个k。要求你判断能否去除一些区间使得f(k)，是所有值中的最大值。思路：我们要保证k出现次数最多，那么k一定要至少作为区间左端点一次，区间右端点一次。那么我们将除去这两个区间的其余区间全部删去，这样只有k出现两次，这两个区间的其他数都只出现了一次。

void Showball(){ int n,k; cin>>n>>k; bool L=false,R=false; while(n--){ int l,r; cin>>l>>r; if(l==k) L=true; if(r==k) R=true; } if(L&&R) cout<<"YES"<<endl; else cout<<"NO"<<endl; }

C. Tea Tasting前缀和+差分+二分题意：有n杯茶和n位品茶者。第 i i i杯茶的容量是 a i a_i ai?，第 i i i个品茶者每次最多能喝 b i b_i bi?的茶。第 i i i个人从第 i i i个位置开始到第1个位置，根据实际情况，对于第 j j j个位置的茶。品茶者只能喝掉 m i n ( b i , a j ) min(b_i,a_j) min(bi?,aj?)。询问最终每个品茶者都喝了多少茶。思路：我们知道对于第 i i i杯茶，只有第 i i i到第 j j j个品茶者可以喝到。这个 j j j我们可以通过二分去查找，我们只需要去计算出每个品茶者能够喝几次自己最大饮茶量 b i b_i bi?，对于不足的我们就直接维护答案即可。对于次数维护，我们发现每次是对于区间 i i i到 j j j都加1，那么就可以用差分去维护即可。

LL a[N],b[N],s[N],d[N],ans[N]; void Showball(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i],ans[i]=0,d[i]=0,s[i]=0; for(int i=1;i<=n;i++) cin>>b[i],s[i]=s[i-1]+b[i]; for(int i=1;i<=n;i++){ int l=i-1,r=n;//注意二分的区间范围，需要考虑b[i]<a[i]的情况，所以l从i-1开始 while(l<r){ int mid=(l+r+1)>>1; if(s[mid]-s[i-1]>a[i]) r=mid-1; else l=mid; } d[i]++,d[r+1]--; if(r<n) ans[r+1]+=a[i]-(s[r]-s[i-1]); } for(int i=1;i<=n;i++){ d[i]+=d[i-1]; ans[i]+=b[i]*d[i]; } for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n]; }

D. Triangle Coloring 计数问题+组合数题意：给定你一个n个点n条边的无向图，n可以整除6。每三个点一组（即连成一个三角形），给定你所有点的权重，每条边的权重等于不同颜色两点权重之和。你现在可以给一半的点染成蓝色，一半的点染成红色。让你去求最大权重的染色方案数思路：由于我们要使权值最大，所以我们一定是选两个同色，一个不同色。这样每个三角形都会贡献两条边。所以 n / 3 n/3 n/3个三角形中一定是一半染两个点为红色，一半染两个点为蓝色。这样方案数为 C n 3 n 6 C_{\frac{n}{3}}^{\frac{n}{6}} C3n?6n??。

另外每个连通块还需要选择最大的两条边。分情况讨论，对于三边相等的三角形，我们任选2个染成相同的颜色。一共有3种方案。对于两边相等的情况，并且第三边大于这两边的情况，有两种情况。其他都为1种情况。

最后对情况进行计算即可。根据数据范围，我们计算组合数需要使用预处理阶乘然后公式法计算。

int fact[N],infact[N]; int qmi(int a,int k,int p){ int res=1%p; while(k){ if(k&1) res=(LL)res*a%p; a=(LL)a*a%p; k>>=1; } return res; } void init(int n){ fact[0]=infact[0]=1; for(int i=1;i<=n;i++){ fact[i]=(LL)fact[i-1]*i%mod; infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod; } } int C(int a,int b){ return (LL)fact[a]*infact[b]%mod*infact[a-b]%mod; } void Showball(){ int n; cin>>n; init(n/3); int cnt0=0,cnt1=0; for(int i=1;i<=n;i+=3){ int a[4]; cin>>a[0]>>a[1]>>a[2]; sort(a,a+3); if(a[0]==a[2]) cnt0++; else if(a[0]==a[1]) cnt1++; } cout<<C(n/3,n/6)*(LL)qmi(3,cnt0,mod)%mod*(LL)qmi(2,cnt1,mod)%mod; }

每日一茶 C. Make Palindrome 题意：输入字符串 s，长度不超过 2e5，由小写字母组成。你可以修改多个 s[i]，但要尽量少地修改，使得修改后的 s，通过重新排列，可以得到回文串。设最少修改 x 次。输出修改 x 次且重排后字典序最小的回文串。输入 aabc 输出 abba

输入 aabcd 输出 abcba 思路：贪心+构造,因为我们要最小修改次数，并且保证重新排列后，是一个字典序最小的回文字符串。那么对于出现偶数次数的字母就不用处理，对于出现奇数次数的我们就需要将按字典序排序，并且从两边到中间开始，将右面的修改成左边的。注意n为奇数的情况。我们需要留一个奇数的不更改，并且放到中间位置。

void Showball(){ string s; cin>>s; int n=s.size(); vector<char> ans;//用来存回文的前半部分字符串，输出时，再逆序输出一遍即可 map<char,int> mp;//记录字母数量 set<char> ss; for(int i=0;i<n;i++) { mp[s[i]]++; ss.insert(s[i]); } int m=0;//记录奇数个数字母的个数 for(auto x:ss) if(mp[x]&1) m++; int cnt=0; char mid; for(auto x:ss){ if(mp[x]&1){//对于奇数个数的字母 cnt++; if(cnt<=m/2) ans.pb(x);/*由于后一半有一个被修改成了对应的前一半，所以前一半就需要多添加一个*/ if(n&1&&cnt==m/2+1) mid=x;/*对于奇数个奇数的情况，我们标记中间那个字母，后面放到中间输出*/ for(int j=0;j<mp[x]/2;j++) ans.pb(x); }else for(int j=0;j<mp[x]/2;j++) ans.pb(x); } for(auto x:ans) cout<<x; if(n&1) cout<<mid; reverse(all(ans)); for(auto x:ans) cout<<x; }