[题解] Codeforces Global Round 22 1738 A B C D E F 题解 - LegendStane
source link: https://www.cnblogs.com/legendstane/p/Codeforces-Global-Round-22-CF-1738-Addicts-Solution.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
很久没rated打过cf的比赛了，这次打得还行，至少进前100了
求点赞
A. Glory Addicts
把类型0的数放进数组a里，类型1的数放进数组b里。如果|a|=|b||a|=|b|，你可以把所有数里最小的放在第一个，其他的交错排列，这样除了最小的其他都能取到2的系数。这个需要特判。否则假设|a|>|b||a|>|b|，则可以把a中最小的放第一个，然后分别把b和a中最大的|b||b|个拿出来交替排列，这样能使b和a中最大的|b||b|个都取到2的系数。容易发现没有更好的排法了。
时间复杂度O(nlogn)O(nlogn)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
using namespace std;
LL t,n,tt[100010],vv[100010];
vector <LL> a,b;
int main()
{
cin>>t;
rep(tn,t)
{
scanf("%lld",&n);
a.clear();b.clear();
rep(i,n) scanf("%lld",&tt[i]);
rep(i,n) scanf("%lld",&vv[i]);
LL ans=0;
LL mn=1e18;
rep(i,n)
{
if(tt[i]==0) a.pb(vv[i]);else b.pb(vv[i]);
ans+=vv[i];
mn=min(mn,vv[i]);
}
sort(a.begin(),a.end());reverse(a.begin(),a.end());
sort(b.begin(),b.end());reverse(b.begin(),b.end());
if(a.size()==b.size())
{
printf("%lld\n",ans*2-mn);
continue;
}
LL sz=min(a.size(),b.size()),v1=0,v2=0;
rep(i,sz) v1+=a[i];rep(i,sz) v1+=b[i];
ans+=v1;
printf("%lld\n",ans);
}
return 0;
}
B. Prefix Sum Addicts
应该是比较容易错的题吧，我最后几分钟想着来不及做G了就去叉这题，结果叉了两个都失败了，喜提-100pts
首先k=1的时候一定是YES。否则a数组最后的k-1项已经确定了，先看已经确定的有没有违反不降。令a的第n−k+2n−k+2项为x(已经确定了)。则它前面的数最大只能都是x。所以就看x⋅(n−k+1)x⋅(n−k+1)是否≥sn−k+1≥sn−k+1就行了。最后就是注意要开long long。
时间复杂度O(n)O(n)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
using namespace std;
LL t,n,k,s[100010];
int main()
{
cin>>t;
rep(tn,t)
{
scanf("%lld%lld",&n,&k);
for(int i=n-k+1;i<=n;++i) scanf("%lld",&s[i]);
LL lst=1e12,ok=1;
for(int i=n-1;i>=n-k+1;--i)
{
LL cur=s[i+1]-s[i];
if(cur>lst)
{
ok=0;
break;
}
lst=cur;
}
LL can=(n-k+1)*lst;
if(can<s[n-k+1]) ok=0;
puts(ok==1 ? "YES":"NO");
}
return 0;
}
C. Even Number Addicts
一开始以为是要观察什么神奇的性质，结果一看数据范围哦豁n≤100n≤100，那不是直接暴力算就行嘛
Alice想要尽量取到偶数个奇数，Bob想要尽量让Alice取到奇数个奇数。dpplayer,val,o,edpplayer,val,o,e表示当前玩家是player(值为0/1 表示Alice/Bob)，当前Alice取到的奇数个数奇偶性为val，还剩o个奇数没取，e个偶数没取，此时的先手能不能胜利。转移也是很简单的，枚举接下来取奇数还是偶数就行。如果能转移到的状态有任意一个是必败，那当前状态就是必胜；否则当前状态为必败。边界情况就是o=e=0o=e=0，根据player和val的值确定胜败即可。可以在所有询问之前先O(1002)O(1002)把dp的表打出来。
时间复杂度O(1002)O(1002)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
using namespace std;
int t,n,a[110],dp[2][2][110][110];
int dfs(int p,int v,int o,int e)
{
int &ret=dp[p][v][o][e];
if(ret!=-1) return ret;
if(o==0&&e==0)
{
if(p==0) return ret=(v==0 ? 1:0);
return ret=(v==1 ? 1:0);
}
ret=0;
if(p==0)
{
if(o>0) ret|=(dfs(1,v^1,o-1,e)==0);
if(e>0) ret|=(dfs(1,v,o,e-1)==0);
}
else
{
if(o>0) ret|=(dfs(0,v,o-1,e)==0);
if(e>0) ret|=(dfs(0,v,o,e-1)==0);
}
return ret;
}
int main()
{
rep(i,2) rep(ii,2) rep(j,105) rep(k,105) dp[i][ii][j][k]=-1;
rep(i,2) rep(ii,2) rep(j,103) rep(k,103) if(dp[i][ii][j][k]==-1) dfs(i,ii,j,k);
cin>>t;
rep(tn,t)
{
cin>>n;
int o=0,e=0;
rep(i,n)
{
scanf("%d",&a[i]);
if(abs(a[i])%2!=0) ++o;
else ++e;
}
puts(dp[0][0][o][e]==1 ? "Alice":"Bob");
}
return 0;
}
D. Permutation Addicts
把数值分成2类，≤k≤k的和>k>k的。观察题目中的定义可知，bibi的含义是：在a序列中，从值为i的元素往前找，第一个与i不同类的元素的值。最终的a序列是会被划分成若干块的，每一块内的元素类型都相同，且相邻两个块内的元素类型不同。发现bi=0或n+1bi=0或n+1，当且仅当i在第一块内。所以我们可以快速地找出第一块内的所有元素(通过检查bibi)。但是每一块内的所有元素顺序也不能乱排，其实每一块内有且仅有1个元素x，满足存在若干y使得by=xby=x(最后一块除外)，这也是容易看出的(回顾bibi的含义)。这个x必须排在当前块的最后一个，而块内其他元素可以按任意顺序排。同时发现，所有满足by=xby=x的y就是下一块的所有元素。到这里这题就做完了，按照上面说的模拟即可。
时间复杂度O(n)O(n)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
using namespace std;
int t,n,b[100010],k,ans[100010];
vector <int> v[100010];
int main()
{
cin>>t;
rep(tn,t)
{
scanf("%d",&n);
rep(i,n+3) v[i].clear();
repn(i,n)
{
scanf("%d",&b[i]);
v[b[i]].pb(i);
}
int curnode,startpos=1,stat;
if(v[0].size()>0) curnode=0,stat=1;
else curnode=n+1,stat=0;
k=0;
while(startpos<=n)
{
int nxt=-1;vector <int> tmp;
rep(i,v[curnode].size())
{
int u=v[curnode][i];
if(v[u].size()>0) nxt=u;
else tmp.pb(u);
}
rep(i,tmp.size()) ans[startpos+i]=tmp[i];
ans[startpos+tmp.size()]=nxt;
if(stat==0) k+=v[curnode].size();
startpos+=v[curnode].size();
curnode=nxt;
stat^=1;
}
printf("%d\n",k);
repn(i,n) printf("%d ",ans[i]);
puts("");
}
return 0;
}
E. Balance Addicts
似乎有很多群友写的很烦还被卡，我的做法还是比较好写的。
原数组下标从1开始。题目中的划分序列，其实等价于：
- 选出2个序列x、y(下标从1开始)，长度都为k(k>0k>0)，满足x严格递增，y严格递减，x和y中的所有元素都在[1,n]中
- 并且满足xk<ykxk<yk
- 那么我们就可以把[1,x1]和[y1,n][1,x1]和[y1,n]各缩成一个数并匹配；[x1+1,x2]和[y2,y1−1][x1+1,x2]和[y2,y1−1]各缩成一个数并匹配⋯⋯[xk−1+1,xk]和[yk,yk−1−1][xk−1+1,xk]和[yk,yk−1−1]各缩成一个数并匹配。这里还要要求每两个匹配区间内的数之和相等。
- xk和ykxk和yk之间如果还有空隙，把中间的数缩成一个，作为回文序列的最中间一个数。
发现每一对合法的(x,y)都对应了一种划分序列的方案。还要加上整个序列合并成一个数的1种方案。
可以令dpi,jdpi,j表示当前已经选择了x和y的一段长度都为p的前缀，其中xp=i,yp=jxp=i,yp=j的方案数。如果p=0则用dp0,n+1dp0,n+1表示。发现每个dpi,jdpi,j可以从某些满足条件的dpi′,j′(i′<i,j′>j)dpi′,j′(i′<i,j′>j)转移。但是有这些还是没法写这题的
处理出原序列的前缀和和后缀和。发现对于每一对合法的(x,y)和任意i，都满足xixi位置的前缀和=yiyi位置的后缀和。因此可以按照值从小到大，枚举每一段极长连续且相等的前缀和，令其范围为[l,r]，前缀和值为val。显然，al≠0al≠0，区间内其他位置都满足ai=0ai=0。如果没有任何一个位置满足其后缀和为val，则跳过这个区间。否则，令值为val的极长后缀和区间为[l',r']。如果[l,r]和[l',r']不相交，我们可以在这两个区间内分别选择相同数量的位置，并分别接在之前提到的x序列和y序列的最后。可以记录一个变量pre，表示满足x序列的最后一个数<l，且y的最后一个数>r'的(x,y)的数量。令在[l,r]和[l',r']内选择>0个数的方案数为wys，每次令pre+=pre⋅wyspre+=pre⋅wys即可。如果[l,r]和[l',r']相交，那么肯定满足l'=l+1,r'=r+1，我们在[l,r']中选择偶数个位置即可。并且我们就不能再接着枚举前缀和的值了，因为我们对(x,y)的要求是x的最后一个数 < y的最后一个数。此时需要break。
时间复杂度O(n)O(n)。题解看着长但是代码好写。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
using namespace std;
const LL MOD=998244353;
LL qpow(LL x,LL a)
{
LL res=x,ret=1;
while(a>0)
{
if((a&1)==1) ret=ret*res%MOD;
a>>=1;
res=res*res%MOD;
}
return ret;
}
LL t,n,a[100010],pref[100010],suf[100010],fac[100010],inv[100010];
vector <pair <LL,pii> > v;
map <LL,pii> mp;
LL C(LL nn,LL mm){return fac[nn]*inv[mm]%MOD*inv[nn-mm]%MOD;}
int main()
{
fac[0]=1;repn(i,100005) fac[i]=fac[i-1]*i%MOD;
rep(i,100003) inv[i]=qpow(fac[i],MOD-2);
cin>>t;
rep(tn,t)
{
scanf("%lld",&n);
repn(i,n)
{
scanf("%lld",&a[i]);
pref[i]=pref[i-1]+a[i];
}
suf[n+1]=0;
for(int i=n;i>0;--i) suf[i]=suf[i+1]+a[i];
v.clear();
repn(i,n)
{
int p=i;
while(p+1<=n&&pref[p+1]==pref[i]) ++p;
v.pb(mpr(pref[i],mpr(i,p)));
i=p;
}
mp.clear();
for(int i=n;i>0;--i)
{
int p=i;
while(p-1>0&&suf[p-1]==suf[i]) --p;
mp[suf[i]]=mpr(p,i);
i=p;
}
LL pre=1;
rep(i,v.size()) if(mp.find(v[i].fi)!=mp.end())
{
LL l1=v[i].se.fi,r1=v[i].se.se,l2=mp[v[i].fi].fi,r2=mp[v[i].fi].se;
if(r1<l2)
{
LL tot=0;
repn(cho,min(r1-l1+1,r2-l2+1)) (tot+=C(r1-l1+1,cho)*C(r2-l2+1,cho))%=MOD;
(pre+=tot*pre)%=MOD;
}
else
{
LL tot=0;
repn(cho,(r2-l1+1)/2) (tot+=C(r2-l1+1,cho+cho))%=MOD;
(pre+=tot*pre)%=MOD;
break;
}
}
printf("%lld\n",pre);
}
return 0;
}
F. Connectivity Addicts
稍微有点诈骗。
我们染色的要求是，同种颜色必须连通，每种颜色都满足度数之和≤≤点数的平方。这启发我们可以拿出度数最大的点(注意度数序列是题目初始时输入的)，直接询问出所有与他相连的点，并把这些所有点都染成同一种颜色。此时被染成这种颜色的点集大小已经超过了其中点的度数的最大值，所以就算我们不断向点集中加入到原来点集中的点有边的其他点(不管加多少都行)，点集仍然满足度数之和≤≤点数的平方(称其为万能点集，每个万能点集中的点颜色都相同)。把度数最大的点和他所连接的点都染色后，我们再拿出没被染色的点中度数最大的，令其为点x。仍然是询问出所有与x连接的点，如果所有这些点都没被染色，那么恭喜，你又找到一个"万能点集"，可以把其中的点再都染成同一种颜色，以后也可以再向其中加点。如果询问过程中发现有一个连到的点y已经被染色，那么干脆把x，以及在询问y之前询问到的所有点(都是没染色的)，都加到y所属的万能点集中(可以用并查集)，与y染成同一种颜色。容易发现这是符合题目中的染色规则的。重复找出度数最大的未染色点并询问的这种操作，直到没有未染色点。我们每询问一次，都有至少1个点被染色。所以总询问次数不会超过n。
时间复杂度O(nlogn)O(nlogn)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
using namespace std;
int t,n,d[1010],fa[1010],c[10010];
bool con[1010];
set <pii> st;
int qry(int u)
{
cout<<"? "<<u<<endl;
cout.flush();
int x;cin>>x;return x;
}
int Find(int x)
{
if(fa[x]!=x) fa[x]=Find(fa[x]);
return fa[x];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>t;
rep(tn,t)
{
cin>>n;
repn(i,n) cin>>d[i];
repn(i,n) fa[i]=i,con[i]=0;
st.clear();
repn(i,n) st.insert(mpr(-d[i],i));
LL cnt=0;
while(cnt<n)
{
pii bg=*st.begin();st.erase(st.begin());
bg.fi=-bg.fi;
con[bg.se]=true;
++cnt;
rep(i,bg.fi)
{
int v=qry(bg.se);
if(con[v])
{
fa[Find(bg.se)]=Find(v);
break;
}
con[v]=true;fa[Find(v)]=Find(bg.se);
st.erase(mpr(-d[v],v));
++cnt;
}
}
cout<<"! ";
int len=0;
repn(i,n) if(Find(i)==i) c[i]=++len;
repn(i,n) if(Find(i)!=i) c[i]=c[Find(i)];
repn(i,n) cout<<c[i]<<' ';cout<<endl;
cout.flush();
}
return 0;
}
有一说一，H不仅有原题而且据说还是板子。。。有群友半小时不到就切了/fad
LOJ原题链接
原题是这题的强化版？
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK