首页 > 其他分享 >Codeforces Polynomial Round 2022 (Div.1 + Div.2) CF 1774 题解

Codeforces Polynomial Round 2022 (Div.1 + Div.2) CF 1774 题解

时间：2022-12-18 20:03:30浏览次数：46  
标签：1774 int 题解 rep pos Codeforces LL void define

A. Add Plus Minus Sign

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

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

void 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 <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

void 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 <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

void 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 <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

void 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 <int> 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 <int> 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 <pair <pii,int> > ans;
    rep(col,m)
    {
      vector <int> abo,und;
      rep(i,n)
      {
        if(cur[i]>ave&&a[i][col]==1) abo.pb(i);
        if(cur[i]<ave&&a[i][col]==0) und.pb(i);
      }
      while(abo.size()&&und.size())
      {
        int aa=abo.back(),uu=und.back();
        abo.pop_back();und.pop_back();
        ans.pb(mpr(mpr(aa+1,uu+1),col+1));
        swap(a[aa][col],a[uu][col]);
        --cur[aa];++cur[uu];
      }
    }
    printf("%d\n",ans.size());
    rep(i,ans.size()) printf("%d %d %d\n",ans[i].fi.fi,ans[i].fi.se,ans[i].se);
  } 

  termin();
}

E. Two Chess Pieces

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

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

void 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 <int> 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<<ans*2<<endl;

  termin();
}

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<k}totsub_{c_p}\)。这是因为\(totsub_{c_k}\ge 2\cdot totsub_{c_{k-1}}\)。所以可以从后往前枚举这些3操作，如果一只由i操作产生的猪经过当前枚举的3操作后可能存活，那这只猪如果不经过当前枚举的操作，无论前面的3操作怎么搞它，它都不会死。根据这个结论可以\(O(log(1e9))\)求出合法的路径数量。

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

F1代码：

点击查看代码 
#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 <LL,LL>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void 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 <pii> 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;i<q;++i)
  {
    if(que[i].fi==1)
    {
      LL to=que[i].se;
      add(to,1);
    }
    else if(que[i].fi==2)
    {
      subsum=min(subsum+que[i].se,200050LL);
      while(!cur.empty()&&cur.begin()->fi+shft<=que[i].se) cur.erase(cur.begin());
      //if(i==8) cout<<cur.begin()->fi+shft<<"jflkasdf\n";
      shft-=que[i].se;
      //if(i==8) cout<<cur.begin()->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<<i<<endl;
    for(auto it:cur) cout<<it.fi+shft<<' '<<it.se<<endl;
    cout<<endl;*/
  }
  LL ans=0;
  for(auto it:cur) (ans+=it.se)%=MOD;
  cout<<ans<<endl;

  termin();
}

F2代码：

点击查看代码 
#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 <LL,LL>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void 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 <LL> 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]<inf&&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<<ans<<endl;

  termin();
}

标签：1774,int,题解,rep,pos,Codeforces,LL,void,define
From： https://www.cnblogs.com/legendstane/p/codeforces-polynomial-round-2022-cf-1774-solution.ht

相关文章

  • Codeforces Polynomial Round 2022 (Div.1 + Div.2) CF 1774 题解
    A.AddPlusMinusSign如果有偶数个1，显然可以通过加减各一半的方式达到和为0；否则可以达到和为1。需要注意如果序列的第一个数是1，则它的前面只能填加号。时间复杂度\(O(n......
  • Codeforces Polynomial Round 2022 (Div.1 + Div.2) CF 1774 题解
    A.AddPlusMinusSign如果有偶数个1，显然可以通过加减各一半的方式达到和为0；否则可以达到和为1。需要注意如果序列的第一个数是1，则它的前面只能填加号。时间复杂度\(O(n......
  • Codeforces Polynomial Round 2022 (Div.1 + Div.2) CF 1774 题解
    A.AddPlusMinusSign如果有偶数个1，显然可以通过加减各一半的方式达到和为0；否则可以达到和为1。需要注意如果序列的第一个数是1，则它的前面只能填加号。时间复杂度\(O(n......
  • [CSP-S 2022] 假期计划 题解
    题面题面冗长，不便展示，详见洛谷。考场想法对于每一个点给他能到达的点都建一条边，最后跑一遍DFS。期望分数：\(60\)。代码朴素想法枚举所有可能的四个点，看是否能“互......
  • 题解 [ABC133F] Colorful Tree
    原题链接考虑正常的\(u\)和\(v\)之间的距离怎么去求：我们可以维护每个值到根的距离\(dist_i\)，然后通过计算\(dist_u+dist_v-2\timesdist_{lca}\)得到，这里就不过......
  • IDEA中Maven项目 子项目中缺少parent标签及无web框架问题解决
    Question在maven项目中，创建的子模块的pom中没有标签，但父模块中有，造成运行时提示版本源过低原因：maven的settings.xml中默认jdk版本过低解决方法：在maven中指定jdk版本，找到......
  • Educational Codeforces Round 139 (A-C)
    A题意：有t组测试数据，每组测试数据输入一个整数n，输出一个整数，表示[1,n]范围内满足以下条件的x的个数。其中x满足条件"只有一个非0的位数(比如5000,4,200)"。解法/思路：举......
  • [ABC282D] Make Bipartite 2 题解
    题目描述给定一个无向简单图\(G\)，统计有多少个点对\((u,v)\)满足：\(u,v\)之间没有边直接连接：\((u,v)\notin\textE\)连接\((u,v)\)后\(G\)是二分图......
  • Educational Codeforces Round 3
    EducationalCodeforcesRound3https://codeforces.com/contest/6093/6：ABCD赛后过了CD题解等下写A.USBFlashDrives前缀和#include<bits/stdc++.h>usingname......
  • 题解 CF1762E【Tree Sum】
    problem根据prufer引理，有标号的无根树的种类是\(n^{n-2}\)。对于一棵n个节点的带权无根树，边权总是+1或者-1。那么总共有\(n^{n-2}*2^{n-1}\)种树。其......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99