[题解] Codeforces Global Round 22 1738 A B C D E F 题解

时间:2022-10-01 14:08:34

很久没rated打过cf的比赛了,这次打得还行,至少进前100了

点我看题

A. Glory Addicts

把类型0的数放进数组a里,类型1的数放进数组b里。如果\(|a|=|b|\),你可以把所有数里最小的放在第一个,其他的交错排列,这样除了最小的其他都能取到2的系数。这个需要特判。否则假设\(|a|>|b|\),则可以把a中最小的放第一个,然后分别把b和a中最大的\(|b|\)个拿出来交替排列,这样能使b和a中最大的\(|b|\)个都取到2的系数。容易发现没有更好的排法了。

时间复杂度\(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+2\)项为x(已经确定了)。则它前面的数最大只能都是x。所以就看\(x \cdot (n-k+1)\)是否\(\geq s_{n-k+1}\)就行了。最后就是注意要开long long。

时间复杂度\(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\leq 100\),那不是直接暴力算就行嘛

Alice想要尽量取到偶数个奇数,Bob想要尽量让Alice取到奇数个奇数。\(dp_{player,val,o,e}\)表示当前玩家是player(值为0/1 表示Alice/Bob),当前Alice取到的奇数个数奇偶性为val,还剩o个奇数没取,e个偶数没取,此时的先手能不能胜利。转移也是很简单的,枚举接下来取奇数还是偶数就行。如果能转移到的状态有任意一个是必败,那当前状态就是必胜;否则当前状态为必败。边界情况就是\(o=e=0\),根据player和val的值确定胜败即可。可以在所有询问之前先\(O(100^2)\)把dp的表打出来。

时间复杂度\(O(100^2)\)

点击查看代码
#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类,\(\leq k\)的和\(>k\)的。观察题目中的定义可知,\(b_i\)的含义是:在a序列中,从为i的元素往前找,第一个与i不同类的元素的。最终的a序列是会被划分成若干块的,每一块内的元素类型都相同,且相邻两个块内的元素类型不同。发现\(b_i=0或n+1\),当且仅当i在第一块内。所以我们可以快速地找出第一块内的所有元素(通过检查\(b_i\))。但是每一块内的所有元素顺序也不能乱排,其实每一块内有且仅有1个元素x,满足存在若干y使得\(b_y=x\)(最后一块除外),这也是容易看出的(回顾\(b_i\)的含义)。这个x必须排在当前块的最后一个,而块内其他元素可以按任意顺序排。同时发现,所有满足\(b_y=x\)的y就是下一块的所有元素。到这里这题就做完了,按照上面说的模拟即可。

时间复杂度\(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>0\)),满足x严格递增,y严格递减,x和y中的所有元素都在[1,n]中
  • 并且满足\(x_k<y_k\)
  • 那么我们就可以把\([1,x_1]和[y_1,n]\)各缩成一个数并匹配;\([x_1+1,x_2]和[y_2,y_1-1]\)各缩成一个数并匹配\(\cdots\)\([x_{k-1}+1,x_k]和[y_k,y_{k-1}-1]\)各缩成一个数并匹配。这里还要要求每两个匹配区间内的数之和相等。
  • \(x_k和y_k\)之间如果还有空隙,把中间的数缩成一个,作为回文序列的最中间一个数。

发现每一对合法的(x,y)都对应了一种划分序列的方案。还要加上整个序列合并成一个数的1种方案。

可以令\(dp_{i,j}\)表示当前已经选择了x和y的一段长度都为p的前缀,其中\(x_p=i,y_p=j\)的方案数。如果p=0则用\(dp_{0,n+1}\)表示。发现每个\(dp_{i,j}\)可以从某些满足条件的\(dp_{i',j'}(i'<i,j'>j)\)转移。但是有这些还是没法写这题的

处理出原序列的前缀和和后缀和。发现对于每一对合法的(x,y)和任意i,都满足\(x_i\)位置的前缀和=\(y_i\)位置的后缀和。因此可以按照值从小到大,枚举每一段极长连续且相等的前缀和,令其范围为[l,r],前缀和值为val。显然,\(a_l \neq 0\),区间内其他位置都满足\(a_i=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 \cdot wys\)即可。如果[l,r]和[l',r']相交,那么肯定满足l'=l+1,r'=r+1,我们在[l,r']中选择偶数个位置即可。并且我们就不能再接着枚举前缀和的值了,因为我们对(x,y)的要求是x的最后一个数 < y的最后一个数。此时需要break。

时间复杂度\(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

稍微有点诈骗。

我们染色的要求是,同种颜色必须连通,每种颜色都满足度数之和\(\leq\)点数的平方。这启发我们可以拿出度数最大的点(注意度数序列是题目初始时输入的),直接询问出所有与他相连的点,并把这些所有点都染成同一种颜色。此时被染成这种颜色的点集大小已经超过了其中点的度数的最大值,所以就算我们不断向点集中加入到原来点集中的点有边的其他点(不管加多少都行),点集仍然满足度数之和\(\leq\)点数的平方(称其为万能点集,每个万能点集中的点颜色都相同)。把度数最大的点和他所连接的点都染色后,我们再拿出没被染色的点中度数最大的,令其为点x。仍然是询问出所有与x连接的点,如果所有这些点都没被染色,那么恭喜,你又找到一个"万能点集",可以把其中的点再都染成同一种颜色,以后也可以再向其中加点。如果询问过程中发现有一个连到的点y已经被染色,那么干脆把x,以及在询问y之前询问到的所有点(都是没染色的),都加到y所属的万能点集中(可以用并查集),与y染成同一种颜色。容易发现这是符合题目中的染色规则的。重复找出度数最大的未染色点并询问的这种操作,直到没有未染色点。我们每询问一次,都有至少1个点被染色。所以总询问次数不会超过n。

时间复杂度\(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原题链接
原题是这题的强化版?