---

layout: post

title: Codeforces Round #532 (Div. 2)

author: "luowentaoaa"

catalog: true

tags:

mathjax: true

- codeforces

---

A. [(水题)

题意

太水不想写

B. (水题)

题意

给出一个n,m, 接下来吗每一时刻出现m个数,如果在某一时刻N种数字都出现过就输出'1'并同时把1-n种数字各删去一个

题解

很明显和每个数出现的最小值有关,如果出现数的最小值都大于等于1代表这n个数都出现过了,那么如何解决删去呢，如果每时刻都判断每个数都是否大于1就太浪费时间了,我们可以用个变量记录已经出现了多少个数,如果达到n再删去，这样复杂度并不会达到(n*m);

同时也可以换方向,如果我不删去呢？

#include
    
     using namespace std;typedef long long ll;#define pp pair
     
      const ll mod=998244353;const int maxn=1e6+50;const ll inf=0x3f3f3f3f3f3f3f3fLL;int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}int lcm(int a,int b){return a*b/gcd(a,b);}int a[maxn],mx[maxn];int flag[maxn];set
      
       st;int num[maxn];double pi=acos(-1.0);void update(int now,int l,int r,int pos){    if(l==r){        mx[now]++;        return;    }    int mid=(l+r)/2;    if(pos<=mid)update(now<<1,l,mid,pos);    else update(now<<1|1,mid+1,r,pos);    mx[now]=min(mx[now<<1],mx[now<<1|1]);}int main(){    std::ios::sync_with_stdio(false);    std::cin.tie(0);    std::cout.tie(0);    int n,m;    cin>>n>>m;    int k=1;    for(int i=1;i<=m;i++)cin>>a[i];    for(int i=1;i<=m;i++){        update(1,1,n,a[i]);        if(mx[1]==k)k++,cout<<1;        else cout<<0;    }    return 0;}//#include
       
        using namespace std;typedef long long ll;#define pp pair
        
         const ll mod=998244353;const int maxn=1e5+50;const ll inf=69;int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}int lcm(int a,int b){return a*b/gcd(a,b);}int a[maxn];int aa[maxn];int main(){    std::ios::sync_with_stdio(false);    std::cin.tie(0);    std::cout.tie(0);    int n,m;    cin>>n>>m;    int now=1;    for(int i=1;i<=m;i++){        int p;        cin>>p;        a[p]++;        aa[a[p]]++;        if(aa[now]>=n){            cout<<1;now++;        }        else cout<<0;    }    return 0;}
        
       
      
     
    

C. (简单几何)

一个圆均匀得被许多大小相等的小圆包围给你小圆个数和小圆半径 让你求出大圆半径.

#include
    
     using namespace std;typedef long long ll;#define pp pair
     
      const ll mod=998244353;const int maxn=1e6+50;const ll inf=69;int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}int lcm(int a,int b){return a*b/gcd(a,b);}int sx,sy;struct node{    int x,y;    int id;}my[700];double pi=acos(-1.0);int main(){   /* std::ios::sync_with_stdio(false);    std::cin.tie(0);    std::cout.tie(0);*/  //  cin>>sx>>sy;  //  for(int i=1;i<=666;i++)cin>>my[i];    double n,r;    cin>>n>>r;    printf("%.7f\n",sin(pi/n)*r/(1.0-sin(pi/n)));    return 0;}
     
    

D. （鸽笼定理）

题意

你操控白棋可以八连通走动，电脑操控黑棋会直接跳到任意没棋的格子，

如果你操纵白棋走到和某个黑棋的行或者列你就赢了

棋盘999*999，黑棋个数666个

题解

首先666/4=166.5

先把棋子挪到中间，这时棋子就会分布在四个方位中,假设最分散的情况 比较多的三个方位中的棋子数肯定是大于或者等于666-166=500个的

然后让棋子往最多棋子的那三个方向中的对角线的走去，因为棋子每次移动都向三个方向都移动一格，相当于同时把三个方向都扫了过去，而500.500到顶点只需要499步，所以肯定会有黑棋跑不掉

#include
    
     using namespace std;typedef long long ll;#define pp pair
     
      const ll mod=998244353;const int maxn=1e6+50;const ll inf=69;int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}int lcm(int a,int b){return a*b/gcd(a,b);}int sx,sy;struct node{    int x,y;    int id;}my[700];int u,v,w;int vis[1005][1005];void go(int x,int y){    sx+=x;sy+=y;    if(vis[sx][sy])sx-=x;    cout<
      
       <<" "<
       
        <
        
         >u>>v>>w;    if(u==-1)exit(0);    vis[my[u].x][my[u].y]=0;    vis[v][w]=1;    my[u].x=v;my[u].y=w;}int main(){    std::ios::sync_with_stdio(false);    std::cin.tie(0);    std::cout.tie(0);    cin>>sx>>sy;    for(int i=1;i<=666;i++)cin>>my[i].x>>my[i].y,vis[my[i].x][my[i].y]=1;    int ok=1;    while(sx<500)go(1,0);    while(sx>500)go(-1,0);    while(sy<500)go(0,1);    while(sy>500)go(0,-1);    int a=0,b=0,c=0,d=0;    for(int i=1;i<=499;i++)        for(int j=1;j<=499;j++)a+=vis[i][j];    for(int i=1;i<=499;i++)        for(int j=501;j<=999;j++)b+=vis[i][j];    for(int i=501;i<=999;i++)        for(int j=1;j<=499;j++)c+=vis[i][j];    for(int i=501;i<=999;i++)        for(int j=501;j<=999;j++)d+=vis[i][j];    int aa=a+b+c,bb=a+b+d,cc=a+c+d,dd=c+b+d;    int mx=max(max(aa,bb),max(cc,dd));    if(aa==mx)while(true)go(-1,-1);    if(bb==mx)while(true)go(-1,1);    if(cc==mx)while(true)go(1,-1);    else while(true)go(1,1);    return 0;}
        
       
      
     
    

E. (二分答案+拓扑判环)

题意

给出一个有向图，让你把一些边反转需要花费费用Ci ,问你把这个图变成一个无环图需要的反转边的最大值最小是多少

题意

问最大最小值那必须是二分答案；

首先可以二分答案，然后把大于答案的边 拿去进行拓扑判断是否有环,如果没环,那么这个答案就是合法的

如果有环说明答案还要加，然后小于答案的边我们就把他们当成双向的就行了，因为题目要输出反转哪些边，所以我们可以记录拓扑序处理一下

#include
    
     using namespace std;typedef long long ll;#define pp pair
     
      const ll mod=998244353;const int maxn=1e5+50;const ll inf=69;int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}int lcm(int a,int b){return a*b/gcd(a,b);}int n,m;struct node{    int u,v;    ll c;}my[maxn];vector
      
       e[maxn];int in[maxn];int cnt[maxn];vector
       
        anw;bool isok(ll mid){    for(int i=1;i<=n;i++)e[i].clear();    memset(in,0,sizeof(in));    for(int i=1;i<=m;i++){        if(my[i].c>mid)e[my[i].u].push_back(my[i].v),++in[my[i].v];    }    queue
        
         p;    int now=0;    memset(cnt,0,sizeof(cnt));    for(int i=1;i<=n;i++)if(in[i]==0)p.push(i),cnt[i]=++now;    while(!p.empty()){        int no=p.front();p.pop();        for(int i=0;i
         
          cnt[my[i].v]){ anw.push_back(i); } } return true;}int main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); cin>>n>>m; ll l=0,r=0; for(int i=1;i<=m;i++){ cin>>my[i].u>>my[i].v>>my[i].c; r=max(r,my[i].c); } ll ans=0; while(l<=r){ ll mid=(l+r)/2; if(isok(mid)){ ans=mid; r=mid-1; } else l=mid+1; } isok(ans); cout<
          
           <<" "<
           
            <<"\n"; for(int i=0;i
            
             <
             
              <<" "; return 0;}
             
            
           
          
         
        
       
      
     
    

F. （线性基）

题意

题意进行翻译就是求出区间的最大异或值了,因为n^(n^a^b^c)==a^b^c

题解

考虑贪心，对于每个位的贡献 如果大就留下来，如果同样大那就把比较后面的留下来 ，当然，需要离线处理区间

#include
    
     using namespace std;typedef long long ll;#define pp pair
     
      const ll mod=998244353;const int maxn=5e5+50;const ll inf=69;int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}int lcm(int a,int b){return a*b/gcd(a,b);}const int maxbit=32;int n;int c[maxn];int q;struct node{    int id;    int l,r;    bool operator <(const node &a)const{        return this->r
      
       =0;i--){        if(num&(1<
       
        >n;    for(int i=1;i<=n;i++)cin>>c[i];    cin>>q;    for(int i=1;i<=q;i++){        cin>>Q[i].l>>Q[i].r;Q[i].id=i;    }    sort(Q+1,Q+1+q);    int now=1;    for(int i=1;i<=q;i++){        while(now<=Q[i].r)ins(c[now],now),now++;        for(int j=31;j>=0;j--){            if(my[j].id>=Q[i].l&&((ans[Q[i].id]^my[j].num)>ans[Q[i].id]))ans[Q[i].id]^=my[j].num;        }    }    for(int i=1;i<=q;i++)cout<
        
         <