牛客算法周周练11 (A模拟,B 分组 染色,C 线段树 区间求和，区间异或 ,D 思维 ,E 思维+差分)ccsudeer-

题目链接

A-切题之路

做法：按照题意 模拟一下就好了，得用longlong

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=1e5+10; ll mi,mx; ll t[N],h[N],n,s; int main() {     n=read(),s=read();     mi=read(),mx=read();     rep(i,1,n) t[i]=read();     rep(i,1,n) h[i]=read();         ll ans1=0,tmp1=s;     rep(i,1,n)     {         if(h[i]>=mi) continue;         if(tmp1>=t[i]) ans1++,tmp1-=t[i];     }      ll ans2=0,tmp2=s;     rep(i,1,n)     {         if(h[i]<mx) {             if(tmp2>=t[i]) ans2++,tmp2-=t[i];         }         else{             if(tmp2>=2ll*t[i]) ans2++,tmp2-=2ll*t[i];         }      }     printf("%lld %lldn",ans1,ans2);    } 

B-分组

做法：首先，根据题意，合理分组的答案一定是存在的，用01染色开始染色，染完色 再判断一下当前节点是否连有两个跟自己一组的，有  自己则换组，这题不知道是不是数据的问题，vector正向建图wa   用链式前向星建图却A了

 #include<iostream>//非 using namespace std; const int k=3e5+3; int n,m,cnt,shu[k],head[k],nxt[k],ans[k]; void add(int x,int y){shu[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;} void dfs(int x){     int s=0;     for(int i=head[x];i;i=nxt[i]){         if(!ans[shu[i]]) ans[shu[i]]=ans[x]^3,dfs(shu[i]);         if(ans[shu[i]]==ans[x]) s++;     }     if(s>=2) ans[x]^=3; } int main(){     cin>>n>>m;     for(int i=1,x,y;i<=m;i++) cin>>x>>y,add(x,y),add(y,x);     for(int i=1;i<=n;i++) if(!ans[i]) ans[i]=1,dfs(i);     for(int i=1;i<=n;i++) cout<<ans[i]<<" "; return 0; }

vector：

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;   inline ll read() {     ll x=0,w=1; char c=getchar();     while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}     while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}     return w==1?x:-x; } const int N=1e5+10; vector<int>G[N]; int n,m,col[N]; void dfs(int u) {     int cnt=0;     for(int v:G[u]){         if(!col[v])  col[v]=3-col[u],dfs(v);         if(col[u]==col[v]) cnt++;     }     if(cnt>=2) col[u]=3-col[u]; } int main() {     n=read(),m=read();     rep(i,1,m)     {         int u=read(),v=read();         G[u].push_back(v);         G[v].push_back(u);     }     rep(i,1,n) if(!col[i]) col[i]=1,dfs(i);     rep(i,1,n) printf("%d ",col[i]); }

C-红球进黑洞

做法:这题很有意思，但看到好多暴力就过了，数据是真水，正解应该是对每一个数 进行 二进制拆分，然后对30 位01数字进行区间求和 和异或的维护。 sum[id][i] 记录id节点第i位 为1的个数，异或的话  0  和 1的数量互换就可以了。

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;   inline ll read() {     ll x=0,w=1; char c=getchar();     while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}     while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}     return w==1?x:-x; } const int N=1e5+10; ll sum[4*N][32],lazy[4*N],n,m,f[32]; void build(int id,int l,int r) {     if(l==r){         ll x=read();         for(int i=30;~i;--i){             if(x&f[i]) sum[id][i]++;         }         return ;     }     int mid=l+r>>1;     build(id<<1,l,mid);     build(id<<1|1,mid+1,r);     for(int i=0;i<=30;++i) sum[id][i]=sum[id<<1][i]+sum[id<<1|1][i]; }   void push(int id,int l,int r) {     if(lazy[id]){         lazy[id<<1]^=lazy[id];         lazy[id<<1|1]^=lazy[id];         for(int i=0;i<=30;++i){             if(lazy[id]&f[i]) {                 int mid=l+r>>1;                 sum[id<<1][i]=mid-l+1-sum[id<<1][i];                 sum[id<<1|1][i]=r-mid-sum[id<<1|1][i];               }         }         lazy[id]=0;     } } ll qu(int id,int l,int r,int ql,int qr) {     if(ql<=l&&r<=qr){         ll ans=0;         for(int i=0;i<=30;++i) ans=ans+sum[id][i]*f[i];         return ans;     }     push(id,l,r);     ll ans=0,mid=l+r>>1;     if(ql<=mid) ans+=qu(id<<1,l,mid,ql,qr);     if(qr>mid) ans+=qu(id<<1|1,mid+1,r,ql,qr);     return ans; } void up(int id,int l,int r,int ql,int qr,ll k) {     if(ql<=l&&r<=qr){         lazy[id]^=k;         for(int i=0;i<=30;++i) {             if(k&f[i]) sum[id][i]=r-l+1-sum[id][i];         }         return ;     }     push(id,l,r);     int mid=l+r>>1;     if(ql<=mid) up(id<<1,l,mid,ql,qr,k);     if(qr>mid) up(id<<1|1,mid+1,r,ql,qr,k);     for(int i=0;i<=30;++i) sum[id][i]=sum[id<<1][i]+sum[id<<1|1][i]; } int main() {     f[0]=1;     for(int i=1;i<=30;++i) f[i]=f[i-1]*2;     n=read(),m=read();     build(1,1,n);     while(m--)     {         int ty=read(),l=read(),r=read();         if(ty==1){             ll ans=qu(1,1,n,l,r);             printf("%lldn",ans);         }         else{             ll k=read();             up(1,1,n,l,r,k);         }     } }

D-游戏

没写出来，百度的做法：博客

其实只需要看左上角就行了,因为题目描述写的很清楚,三个人的操作都是为了
BLUESKY007能赢,所以游戏一定会结束,那么当横纵坐标最大的非 B 颜色方格变为 B 颜
色时,可操作的方格范围显然是趋向收敛的,又因为操作规则的要求,左上角的方格在每
次操作中都会按规则进行变换,当可操作范围收敛到左上角且左上角变为 B 颜色时,游
戏结束,所以无论中间的操作是怎样进行的,最终左上角的方格一定会变为 B 颜色,而且
进行操作的人数和操作变换长度相同,所以我们只需要判断左上角方格的颜色即可。
 

 #include<bits/stdc++.h> using namespace std; char maze[1000 + 5][1000 + 5]; int main() {  int t;  cin>>t;  int n,m;  while(t--) {   scanf("%d%d",&n,&m);   for(int i=0; i<n; i++) {    cin>>maze[i];   }   if(maze[0][0]=='R') puts("dreagonm");   else if(maze[0][0]=='G') puts("fengxunling");   else puts("BLUESKY007");  } }

E-积木大赛

做法：做了这么多这类题，区间加一减一  首先就考虑差分去了。然后发现答案就是等于 正的 差分之和，试一发，A了。

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=1e5+10; ll a[N]; int n; int main() {    n=read();    rep(i,1,n) a[i]=read();    ll ans=0;    rep(i,1,n)    {        if(a[i]-a[i-1]>0) ans+=a[i]-a[i-1];    }    cout<<ans<<endl;   }