比赛记录:Codeforces Global Round 25 A~E (猜猜题场)

传送门:CF

[前题提要]:其实这场打的不是很好.A题一个sb错误看不出来,50min后才过,B题上来就Wa了一发,C题用了没必要的线段树,D题刚开始被60诈骗,一直在想按位考虑.幸好赛时猜出了E,然后又猜出来D,本来掉大分变成上大分…但是这场前几题大都是猜猜题,所以本来不想写题解的.但是一想到对于这种结论题,肯定没多少人解释证明结论,所以还是逼自己一把来写这玩意了…

---

A. Dual Trigger

显然1的个数是奇数的时候是不合法的.那么现在只需要判断1的个数是偶数的时候.考虑只有两个1的时候,并且这两个1是相邻的时候是不满足要求的,其他偶数情况都是合法的.
考虑证明:对于只有两个1并且不相邻的情况,我们只要选择这两个1操作一次即可.对于$k$个1,且$k$是偶数的情况,我们每次都选择相对位置在第$i$和第$(i+k/2)$位置的1,不难发现这种构造方式是合法的.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
inline void print(__int128 x){if(x<0) {putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int main() {int T=read();while(T--) {int n=read();string s;cin>>s;vector<int>v;for(int i=0;i<s.length();i++) {if(s[i]=='1') {v.push_back(i);}}if((int)v.size()&1) {cout<<"NO"<<endl;}else {int cnt=0;for(int i=0;i<s.length();i++) {if(s[i]=='1') {cnt++;while(i+1<s.length()&&s[i+1]=='1') {i++;}}}if(cnt==1&&(int)v.size()==2) {cout<<"NO"<<endl;}else {cout<<"YES"<<endl;}}}return 0;
}

B. Battle Cows

感觉做法应该有很多.我的做法是考虑枚举每一个位置作为与$k$交换的位置,然后求得每种情况的贡献最后取一个$max$.
那么显然的,当我们枚举到第$i$个奶牛,如果$i$之前的所有奶牛的值比$k$大,那此时已经被必要继续枚举下去了,因为对于$i$以及$i$之后的所有位置来说,无论我们怎么交换,最后的贡献都是0.
然后对于交换的位置我们考虑它的贡献是什么,对于前缀的贡献显然是1,因为前面都比它要小(对吗?不对,此时需要进行分类讨论,如果交换到的位置是第一个,那么此时前缀没有贡献,并且如果当前的a[i]>a[k],k<i,的时候,你会发现所有无前缀贡献也无后缀贡献,所以此处需要进行分类讨论).那么对于后缀的贡献来说,显然是交换后(也就是当前位置是$i$)后续第一个比它大的数的位置.考虑如何维护这个,只要提前用$set$记录所有比k大的数位置,如果当前的$i$在其中,先将其删除,求完贡献之后再插入即可.如果不在直接查即可.感觉凭空说比较麻烦,直接看代码理解或许会更好

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
inline void print(__int128 x){if(x<0) {putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn];int lmax[maxn];
int main() {int T=read();while(T--) {int n=read();int k=read();for(int i=1;i<=n;i++) {a[i]=read();lmax[i]=max(lmax[i-1],a[i]);}set<int>st;for(int i=1;i<=n;i++) {if(a[i]>a[k]) {st.insert(i);	}}st.insert(n+1);//注意边界问题int ans=0;for(int i=1;i<=n;i++) {if(lmax[i-1]>a[k]) {break;}if(a[i]>a[k]) {if(k<i) continue;st.erase(i);st.insert(k);auto pos=st.lower_bound(i);if(i==1) {ans=max(ans,*pos-i-1);}else {ans=max(ans,1+*pos-i-1);}st.erase(k);st.insert(i);}else {auto pos=st.lower_bound(i);if(i==1) {ans=max(ans,*pos-i-1);}else {ans=max(ans,1+*pos-i-1);}}}cout<<ans<<endl; }return 0;
}

C. Ticket Hoarding

赛时没有细想,想了个自以为很正确的贪心过了样例就交了.赛后发现这道题证明起来还是挺麻烦的.

先讲做法,就是贪心地取便宜的东西,然后尽量的将其拿满$m$个(显然最后一次是拿k%m),考虑如何维护这个东西,我是拿线段树进行维护的.假设你当前枚举到的是第$i$个,那么这个东西现在的单价上升的数值等同于之前拿的$id$在其之前的个数.然后你拿了这个东西,同样会影响之前拿的所有$id$在其之后的东西.具体关系很好推,就不赘述了(不会看具体代码也应该能理解).那么现在我们的问题就是如何维护$id$在当前之前的东西的个数以及在当前之后的东西的个数,这个可以使用权值线段树或者权值树状数组维护.

那么为什么上述贪心是正确的呢.下面来简单证明一下:
考虑设数组$a$表示$1$~$n$每一个物品买的个数;数组$b$表示每一个的原始单价.那么对于当前的第$i$个物品,此时它的真实购买价格就是${\sum }_{j=1}^{i-1}{a}_j+b_i$,那么此时的总价格就是${\sum }_{i=1}^n(({\sum }_{j=1}^{i-1}{a}_j+b_i)\ast a_i)$,化简一下不难发现就是下面这个东西${\sum }_{i=1}^n{a}_i{b}_i+\sum a_i{a}_j[i\ne j]$,发现后面那个式子只跟a有关,所以我们考虑对于固定数字的a数组来说,我们可以随意交换其位置,对于后面答案是没有影响的.但是显然的对于前面的式子来说,我们将a中大的数与b中小的数搭配才是最优的,那么显然的,我们此时假设b数组是单调增的,我们应该尽量的将前的每一个位置都填满对于前面的式子来说贡献才是最小的.也就是a数组此时的值应该为$[m,m...,k\%m,...,0,0,0]$.但是这个只是对于前面的式子来说是最优的,我们后面的式子该怎么办呢.其实可以证明上述这种贪心策略同样适用于后面的式子.

对于$\sum a_i{a}_j[i\ne j]$,我们将其换个方式表示$({\sum }_{i=1}^n{a}_i{)}^2-{\sum }_{i=1}^n{a}_i^2$,不难发现$\sum a_i$是固定的.所以就是后面那个式子尽量的取最大.对于平方和来说,什么时候取最大呢,显然是最不平均的时候(这个应该是可以使用某个基础的不等式证明的,太久没学数学了,忘了,就不证明了),而我们上述的分法刚好是最不平均的分法.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
inline void print(__int128 x){if(x<0) {putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{int l,r,mn,mx,sum;
}tree[maxn<<2];
void pushup(int rt) {tree[rt].mn=min(tree[ls].mn,tree[rs].mn);tree[rt].mx=max(tree[ls].mx,tree[rs].mx);tree[rt].sum=tree[ls].sum+tree[rs].sum;
}
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;tree[rt].mn=int_INF;tree[rt].mx=-int_INF;tree[rt].sum=0;if(l==r) {return ;}int mid=(l+r)>>1;build(lson);build(rson);pushup(rt);
}
void update(int pos,int rt,int val) {if(tree[rt].l==pos&&tree[rt].r==pos) {tree[rt].mn=tree[rt].mx=val;tree[rt].sum+=val;return ;}int mid=(tree[rt].l+tree[rt].r)>>1;if(pos<=mid) update(pos,ls,val);else update(pos,rs,val);pushup(rt);
} 
int query_min(int l,int r,int rt) {if(tree[rt].l==l&&tree[rt].r==r) {return tree[rt].mn;}int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid) return query_min(l,r,ls);else if(l>mid) return query_min(l,r,rs);else return min(query_min(l,mid,ls),query_min(mid+1,r,rs));
}
int query_max(int l,int r,int rt) {if(tree[rt].l==l&&tree[rt].r==r) {return tree[rt].mx;}int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid) return query_max(l,r,ls);else if(l>mid) return query_max(l,r,rs);else return max(query_max(l,mid,ls),query_max(mid+1,r,rs));
}
int query(int l,int r,int rt) {if(tree[rt].l==l&&tree[rt].r==r) {return tree[rt].sum;}int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid) return query(l,r,ls);else if(l>mid) return query(l,r,rs);else return query(l,mid,ls)+query(mid+1,r,rs);
}
struct Node{int val,id;bool operator < (const Node &rhs) const {return val<rhs.val;}
}node[maxn];
signed main() {int T=read();while(T--) {int n=read();int m=read();int k=read();build(1,n,1);for(int i=1;i<=n;i++) {node[i].val=read();node[i].id=i;}sort(node+1,node+n+1);int ans=0;for(int i=1;i<=n;i++) {if(k>=m) {int num=query(node[i].id,n,1);int num2=query(1,node[i].id,1);ans+=(node[i].val+m*num2)*m+num*m*m;k-=m;update(node[i].id,1,1);}else {int num=query(node[i].id,n,1);int num2=query(1,node[i].id,1);ans+=(node[i].val+m*num2)*k+num*m*k;break;}}cout<<ans<<endl;}return 0;
}

D. Buying Jewels

猜猜题.经典先猜后证
显然我们会发现当n<k的时候我们的答案是NO,因为我们至少也要花1换取1个东西.
当n=k时候,显然只要设置金额是1即可
当n>k的时候,显然此时1号摊位不能设置1,然后我们经过某种神奇的思考(或者手模几个样例找找规律).例如20,9,此时的答案是12,1,就会发现我们可以设置1号摊位为$n-k+1$,然后二号摊位为$1$,这样似乎就可以了?因为我们发现只要我们给2号摊位剩下k-1块钱,然后1号摊位用掉n-k+1块钱并获得1贡献即可.但是上述这种方法是有范围限制的.我们发现当$n/(n-k+1)>1$的时候,就会出问题,例如8,4.然后就会想这个时候该怎么构造呢?其实这个时候的答案就是NO.考虑简单证明一下这个.
因为我们此时的1号摊位不能是1了,那么此时我们能获得的最大物品数显然是$\lfloor \frac{n}{2}\rfloor +n\%2$,考虑$n/(n-k+1)>1$是什么情况,因为是整数,所以我们可以将其改写为$n\ge 2\ast (n-k+1)$,化简一下就会发现$2\ast k-2\ge n$,也就是$k\ge \lceil \frac{n+2}{2}\rceil$,然后我们会发现什么,我们会发现此时的$\lceil \frac{n+2}{2}\rceil >\lfloor \frac{n}{2}\rfloor +n\%2$(这个可以通过分类n的奇偶性证明).这说明了什么,说明了这种情况下我们获得最大物品数都不及k,所以必然不可能得到一个可行解.所以此时的答案必然是NO

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
inline void print(__int128 x){if(x<0) {putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
signed main() {int T=read();while(T--) {int n=read();int k=read();if(n%k==0) {cout<<"YES"<<endl;cout<<1<<endl;cout<<n/k<<endl;continue;}if(n>k) {if(n/(n-k+1)==1) {cout<<"YES"<<endl;cout<<2<<endl;cout<<n-k+1<<" "<<1<<endl;continue;}}cout<<"NO"<<endl;}return 0;
}

E. No Palindromes

猜猜题.经典先猜后证
赛时想了一下,直觉告诉我能分成2个以上的非回文串的难度应该是大于分成两个非回文串的难度的.所以当时直接钦定只能分成两个非回文串,然后使用$Manacher$判断回文串.没想到真给我过了,当时很怕被FST,结果正解还真是这个…
考虑证明下面这个结论:如果一个字符串能分成若干个非回文子串,那么一定可以通过分成两段的方式来满足该题意.
首先我们会发现如果一个字符串S,它本身就是非回文串,那么我们直接输出它即可.那么下面的讨论将基于S是回文串开始讨论.

对于一个非回文串来说,我们首先应该想到如果一个子串的两个端点不同,那么它显然就是一个非回文串那么假设我们存在$S(1,pos)$满足$S[1]!=S[pos]$,那么只要$S[pos+1,n]$不是一个回文串,我们就可以直接把上述两个子串当做我们此时的答案.并且我们会发现此时满足分成两个子串的结论

那么假设不存在上述这种情况该怎么办呢.考虑不存在上述情况,我们的S会是什么形式.
首先可能我们的S只有一个字符,此时这种情况是不能分成两个非回文子串的.但是此时确确实实应该是NO.所以与上述结论不矛盾.

那么此时我们的S有多个字符,我们会发现S一定是AbAbAb…AbAbA这种形式.其中A是若干个相同的字符,b是一个字符.我们考虑从后往前枚举,那么最后一个b显然是一个位置与开头不同的端点,所以此时最后一个A一定是多干个相同的字符(我们此时假设所有的A我们不知道他们是相同的,b也不知道是相同的).我们继续枚举,到倒数第二个b,我们会发现,此时需要AbA需要是一个回文串,因为A中的字符和b不同,所以倒数第二个A一定和最后一个A相同.所以倒数第二个A也是若干个相同字符.类似的枚举到倒数第三个b,我们会发现后两个b一定相同.并且因为S是一个回文串,我们最后能得到最后一个A和开头的A也是相同的,那么我们可以根据不完全归纳法得出上述这种形式是正确的.

很好,那么此时我们考虑根据A的字符的个数来进行枚举.不难发现,当A中的字符个数是1个时,此时的A是ababababa这种形式,我们无法将其分为两个非回文子串,但是我们此时也会发现该字符本就无法分成多个非回文子串;考虑当A中的字符个数大于1时(假设有t个),我们假设a是A的单个字符,我们只要将其分为$Aba$以及$aaa...aaabAbA$的两个子串即可.其中第二子串的开头是$t-1$个a.第一个子串的结尾是1个a.我们会发现这种构造必然是两个非回文子串,因为两个子串开头和结尾的a的个数不同.

至此,证毕.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
inline void print(__int128 x){if(x<0) {putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
class Manacher {
public:Manacher(const std::string &s) {construct(s);};void getLongestPalindromeString(int &position, int &length) {// 找到最长的回文子串的位置与长度。position = -1, length = -1;for(int i = 0; i < len.size(); i++) {if(len[i] > length) {length = len[i];position = i;}}// 映射到原始字符串中的位置。position = position/2 - length/4;length = length/2;return;}// s[L:R] 是否是回文的bool isPalindrome(int L, int R) {L = L*2 + 1;R = R*2 + 1;int mid = (L+R)/2;if(0 <= mid && mid < len.size() && R-L+1 <= len[mid]) {return true;}return false;}
private:vector<int> len;void construct(const std::string &s) {vector<char> vec;// 用 0 作为分隔符vec.resize(s.size()*2+1);for(int i = 0; i < s.size(); i++) {vec[i<<1|1] = s[i];}int L = 0, R = -1;len.resize(vec.size());for(int i = 0, n = vec.size(); i < n; i++) {if(i <= R) { // 被覆盖了，尝试加速len[i] = min((R-i)*2+1, len[L+R-i]);} else { // 未被覆盖，那就没办法加速了，从 1 开始。len[i] = 1;}// 尝试继续探测int l = i - len[i]/2 - 1;int r = i + len[i]/2 + 1;while(0 <= l && r < vec.size() && vec[l] == vec[r]) {--l;++r;}// 更新len[i] = r-l-1;if(r > R) {L = l+1;R = r-1;}}}
};
int main() {cin.sync_with_stdio(false);cin.tie();cout.tie();int T;cin>>T;while(T--) {string s;cin>>s;int n=s.length();s=" "+s;Manacher Ma(s);if(!Ma.isPalindrome(1,n)) {cout<<"YES"<<endl;cout<<1<<endl;cout<<s.substr(1)<<endl;continue;}int flag=0;string ans1="",ans2="";for(int i=1;i<=n;i++) {if(!Ma.isPalindrome(1,i)&&!Ma.isPalindrome(i+1,n)) {ans1=s.substr(1,i);ans2=s.substr(i+1);flag=1;break;}}if(flag) {cout<<"YES"<<endl;cout<<2<<endl;cout<<ans1<<" "<<ans2<<endl;}else {cout<<"NO"<<endl;}}return 0;
}