微动态丨Codeforces Polynomial Round 2022 (Div.1 + Div.2) CF 1774 题解

A. Add Plus Minus Sign

如果有偶数个1，显然可以通过加减各一半的方式达到和为0；否则可以达到和为1。需要注意如果序列的第一个数是1，则它的前面只能填加号。

时间复杂度\(O(n)\)。

点击查看代码

#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;int t;string s;int main(){  fileio();  cin>>t;  rep(tn,t)  {    int n;    cin>>n>>s;    int cnt=(s[0]=="1" ? 1:0);    repn(i,s.size()-1)    {      if(s[i]=="0") printf("+");      else      {        if(cnt==1) printf("-"),cnt=0;        else printf("+"),cnt=1;      }    }    puts("");  }  termin();}

B. Coloring

~~是一道挺难的题~~，我是做完了A~F1才回去做这题的。现在cf比赛的前面几道题越来越偏向于猜结论了，可是场上又有多少人来得及去证明这些结论呢？我认为这是个不好的现象。

(相关资料图)

所以还是来猜个结论吧：令\(x=\lceil\frac nk \rceil\)。如果\(a_{max}>x\)显然无解。其余情况，当\(k|n\)时，\(a_{max}\)的数量不应超过k；否则，\(a_{max}\)的数量不应超过\(n\ mod\ k\)。这个条件的必要性显然，充分性不知道，看着是对的。反正是猜结论题嘛。

可能有80%的人都只判了前面一个条件，几乎全被hack掉了，pretest还贼弱。这事儿直接把这场比赛提高到了它不该有的高度，可以竞争cf史上最烂比赛了。

时间复杂度\(O(m)\)。

点击查看代码

#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;LL t,n,m,k,a[100010];int main(){  fileio();  cin>>t;  rep(tn,t)  {    scanf("%lld%lld%lld",&n,&m,&k);    rep(i,m) scanf("%lld",&a[i]);    LL most=(n+k-1)/k,num=n%k;    if(num==0) num=k;    LL cnt=0,bad=0;    rep(i,m)    {      if(a[i]>most) bad=1;      else if(a[i]==most) ++cnt;    }    if(bad||cnt>num) puts("NO");    else puts("YES");  }  termin();}

C. Ice and Fire

仍然是猜结论题。如果我们总是把现在场上还剩余的人按照编号从小到大排序，那么一个0可以淘汰掉任意一个不是最左侧(最小)的人；1可以淘汰掉任意一个不是最右侧的人。假设现在用输入的01序列的前i项进行比赛，第i项为0，从第i项往前有k个连续的0。这个情况下，能成为冠军的位置在比赛开始前，它右边至少要有k个人。因为如果右边不到k个人，在比赛还剩k轮的时候，它左边必定还有没消掉的。由于剩下的全是0，它左边的东西不可能全消掉。第i项为1同理。所以i的答案就是i+2-k。~~充分性照常不证明~~

时间复杂度\(O(n)\)。

点击查看代码

#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;int t,n;string s;int main(){  fileio();  cin>>t;  rep(tn,t)  {    cin>>n>>s;--n;    int con=0;    rep(i,n)    {      if(i==0||s[i]!=s[i-1]) con=1;      else ++con;      printf("%d ",i+1-con+1);    }    puts("");  }  termin();}

D. Same Count One

如果1的总数不是n的倍数，显然无解。否则一定有解。令\(ave=\frac {tot_1}n\)，也就是最终每行应该有的1的个数。令初始1的个数超过ave的行，它们比ave多出的1的个数总和为sum，显然至少需要sum步才能达成目标，因为我们最好的情况就是每次把一个1从平均线之上的行搬运到平均线之下的行。只操作sum不其实是可以达到的。我们一列一列地看，每次把这一列中能做的这种操作都做完。把这一列所有的在平均线上且对应位置为1的行都拿出来，把所有在平均线下且对应位置为0的行也都拿出来。把这两类行尽量配对。容易发现，依次对每一行把能配对的都配了，也就达成目标了。

时间复杂度\(O(nm)\)。

点击查看代码

#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;int t,n,m,cur[100010];vector  a[100010];int main(){  fileio();  cin>>t;  rep(tn,t)  {    scanf("%d%d",&n,&m);    rep(i,n+3) a[i].clear();    int tot=0;    rep(i,n)    {      vector  tmp;int x;      cur[i]=0;      rep(j,m){scanf("%d",&x);tmp.pb(x);tot+=x;cur[i]+=x;}      a[i]=tmp;    }    if(tot%n!=0)    {      puts("-1");      continue;    }    int ave=tot/n;    vector  > ans;    rep(col,m)    {      vector  abo,und;      rep(i,n)      {        if(cur[i]>ave&&a[i][col]==1) abo.pb(i);        if(cur[i]

`E. Two Chess Pieces`

其实某种程度上也是靠猜。既然要求两个棋子距离不超过d，那如果两个人要去同一个目的地，不如一起行动。具体来说，两个人都是一个子树一个子树地访问，如果某一个子树内同时有这两个人需要访问的点，那就两个人一起去；否则如果只有第一个人需要访问的，那第二个人去了就是浪费，不如第二个人直接留在当前点，让第一个人去。但是如果当前点到子树内最深的第一个人需要访问的点的距离>d，那第二个人还是需要去一下的，他只需要去子树内所有满足"下方所有第一个人需要到达的点的深度最大值-当前点深度>=d"的点就行了，多一个都是浪费。如果只有第二个人需要访问的，同理。所以这题其实只要dfs就能解决。

时间复杂度\(O(n)\)。

点击查看代码

#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;int n,d,b1[200010],b2[200010],sum1[200010],sum2[200010],ans=0,dep[200010],opt1[200010],opt2[200010];vector  g[200010];void dfsPre(int pos,int par){  sum1[pos]=b1[pos];sum2[pos]=b2[pos];  if(b1[pos]) opt1[pos]=dep[pos];  if(b2[pos]) opt2[pos]=dep[pos];  rep(i,g[pos].size()) if(g[pos][i]!=par)  {    dep[g[pos][i]]=dep[pos]+1;    dfsPre(g[pos][i],pos);    sum1[pos]+=sum1[g[pos][i]];sum2[pos]+=sum2[g[pos][i]];    opt1[pos]=max(opt1[pos],opt1[g[pos][i]]);    opt2[pos]=max(opt2[pos],opt2[g[pos][i]]);  }}void dfs1(int pos,int par){  ++ans;  if(opt1[pos]-dep[pos]>=d) ++ans;  rep(i,g[pos].size()) if(g[pos][i]!=par&&sum1[g[pos][i]]) dfs1(g[pos][i],pos);}void dfs2(int pos,int par){  ++ans;  if(opt2[pos]-dep[pos]>=d) ++ans;  rep(i,g[pos].size()) if(g[pos][i]!=par&&sum2[g[pos][i]]) dfs2(g[pos][i],pos);}void dfs(int pos,int par){  rep(i,g[pos].size()) if(g[pos][i]!=par)  {    if(sum1[g[pos][i]]&&sum2[g[pos][i]])    {      ans+=2;      dfs(g[pos][i],pos);    }    else if(sum1[g[pos][i]]) dfs1(g[pos][i],pos);    else if(sum2[g[pos][i]]) dfs2(g[pos][i],pos);  }}int main(){  fileio();  cin>>n>>d;  int x,y;  rep(i,n-1)  {    scanf("%d%d",&x,&y);    g[x].pb(y);g[y].pb(x);  }  int mm;  cin>>mm;rep(i,mm){scanf("%d",&x);b1[x]=1;}  cin>>mm;rep(i,mm){scanf("%d",&x);b2[x]=1;}  dfsPre(1,0);  dfs(1,0);  cout<

`F2. Magician and Pigs (Hard Version)`

其实F1和F2是差不多的，所以F2只配了800分。

考虑能不能维护一个set，依次遍历所有询问的同时，用set维护一些数对{a,b}，表示生命值为a的猪现在有b只。1操作的时候直接往set中插入，2操作就把set中a最小的一些删掉，并把其他的数一并减去一个值。令\(totsub\)表示到当前为止，2操作一共减少了多少生命值(如果一个2操作被3操作重复了多次，也要计算多次)。则一次3操作对这个set的影响是：把set中原有的所有数拿出来，\(>totsub\)的，减去\(totsub\)之后加入set，其余的则不再次加入。这是因为把1~i-1中所有的操作重新做一遍相当于把之前集合中的每头猪都复制了一遍，并且把原有的猪的生命值都减去了\(totsub\)。最后，3操作还会令\(totsub*=2\)。发现在第一次2操作之后，每次3操作都会至少令totsub*2。当\(totsub\ge 1e9\)的时候3操作就完全没用了。所以有效的3操作最多只有\(log_2(1e9)\)次。直接用set维护的复杂度是\((n+X)log^2n\)，可以通过F1。F2需要更好的方法。

观察上面维护set的过程，可以想到对每一个1操作求出由它产生的所有猪里面最终活下来的有几只。假设现在正在遍历第i次1操作，从第i次操作往后的每一次3操作j其实都给了从第i次1操作产生的猪两种选择：把生命值减去\(totsub_j\)，或是不减去。我们可以把一种选择序列看成一条"路径"。把\(totsub_j=0\)的和\(totsub_j>1e9\)的特殊处理，剩下的3操作最多\(log(1e9)\)种。如果把这些有用的3操作按在题目输入中出现的顺序从前往后排好(令其下标组成的序列为\(c_1,c_2\cdots c_m\))，发现对于其中的第k次3操作，\(totsub_{c_k}>\sum_{p

时间复杂度\(O(nlog(1e9))\)。

F1代码：

点击查看代码

#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;const LL MOD=998244353;LL q,subsum=0,shft,tmp[200010];pii que[200010];set  cur;namespace st{  LL n2=1,dat[800100],tag[800100];  void pushDown(LL k)  {    if(tag[k]==1) return;    (tag[k+k+1]*=tag[k])%=MOD;(tag[k+k+2]*=tag[k])%=MOD;    tag[k]=1;  }  void upd(LL k,LL lb,LL ub,LL to)  {    if(lb==ub)    {      (dat[k]*=tag[k])%=MOD;      (++dat[k])%=MOD;      tag[k]=1;      return;    }    pushDown(k);    LL mid=(lb+ub)/2;    if(to<=mid) upd(k+k+1,lb,mid,to);    else upd(k+k+2,mid+1,ub,to);  }  void build(LL k,LL lb,LL ub)  {    if(lb==ub)    {      (dat[k]*=tag[k])%=MOD;      if(lb>0&&lb<=200005&&dat[k]>0) cur.insert(mpr(lb,dat[k]));      return;    }    pushDown(k);    build(k+k+1,lb,(lb+ub)/2);build(k+k+2,(lb+ub)/2+1,ub);  }}void add(LL k,LL val){  LL in=k-shft;  auto it=cur.lower_bound(mpr(in,0LL));  if(it!=cur.end()&&it->fi==in)  {    LL nv=(it->se+val)%MOD;    cur.erase(it);    cur.insert(mpr(in,nv));  }  else cur.insert(mpr(in,val));}int main(){  fileio();  cin>>q;  LL x,y;  rep(i,q)  {    scanf("%lld",&x);    if(x==3) y=0;else scanf("%lld",&y);    que[i]=mpr(x,y);  }  LL to=q-1;  rep(i,q) if(que[i].fi==2)  {    to=i-1;    break;  }  while(st::n2<200001) st::n2*=2;  rep(i,st::n2*2+3) st::tag[i]=1;  rep(i,to+1)  {    if(que[i].fi==1) st::upd(0,0,st::n2-1,que[i].se);    else (st::tag[0]+=st::tag[0])%=MOD;  }  st::build(0,0,st::n2-1);  //cur中位置+shft=实际位置  for(int i=to+1;ifi+shft<=que[i].se) cur.erase(cur.begin());      //if(i==8) cout<fi+shft<<"jflkasdf\n";      shft-=que[i].se;      //if(i==8) cout<fi+shft<<"????????\n";    }    else    {      LL sv=subsum;      subsum=min(subsum*2LL,200050LL);      if(cur.empty()||sv>=cur.rbegin()->fi+shft) continue;      rep(j,200005) tmp[j]=0;      for(auto it:cur)      {        LL act=it.fi+shft;        (tmp[act]+=it.se)%=MOD;        if(act-sv>0) (tmp[act-sv]+=it.se)%=MOD;      }      cur.clear();      repn(j,200003) if(tmp[j]>0) cur.insert(mpr(j,tmp[j]));      shft=0;    }/*    cout<

F2代码：

点击查看代码

#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;const LL MOD=998244353;const LL inf=1100000000;LL n,totsub[800010],pw2[100];pii que[800010];vector  v;int main(){  fileio();  pw2[0]=1;repn(i,48) pw2[i]=pw2[i-1]*2%MOD;  cin>>n;  rep(i,n)  {    scanf("%lld",&que[i].fi);    if(que[i].fi!=3) scanf("%lld",&que[i].se);  }  LL tmp=0;  rep(i,n)  {    if(que[i].fi==2) tmp=min(tmp+que[i].se,inf);    else if(que[i].fi==3)    {      totsub[i]=tmp;      tmp=min(tmp+tmp,inf);    }  }  LL ans=0,addi=0,mul=1;  for(int i=n-1;i>=0;--i)  {    if(que[i].fi==2) addi=min(addi+que[i].se,inf);    else if(que[i].fi==3)    {      if(totsub[i]0) v.pb(totsub[i]);      else if(totsub[i]==0) (mul+=mul)%=MOD;    }    else    {      if(que[i].se-addi<=0) continue;      LL val=que[i].se-addi,res=1;      rep(j,v.size())      {        if(val-v[j]>0)        {          (res+=pw2[v.size()-j-1])%=MOD;          val-=v[j];        }      }      (ans+=res*mul)%=MOD;    }  }  cout<