牛客小白月赛26 （A 二分 B 水 C 偏序问题 D 思维 E bfs F 区间因子之和奇偶 G 几何 H 思维 I 水 J 水）ccsudeer-

题目链接

A-牛牛爱学习

做法：二分天数mid，最大的mid分发给mid天，剩余的尽量插在mid天，判断是否能达到m即可。

 #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=1e6+10; ll sum[N],a[N],m; int n; bool cmp(ll x,ll y) {     return x>y; } int run(int mid) {     ll s=0;       for(int k=0;mid*k+1<=n;++k){         for(int j=1,i=mid*k+1;j<=mid;++j,++i){             if(a[i]-k>0) s+=a[i]-k;         }     }     //if(mid==1) printf(":%lldn",s);     return s>=m; } int main() {     n=read(),m=read();     rep(i,1,n) a[i]=read();     sort(a+1,a+1+n,cmp);       int l=1,r=n;     int ans=1e9;     while(l<=r)     {         int mid=l+r>>1;         if(run(mid)) ans=mid,r=mid-1;         else l=mid+1;     }     if(ans==1e9) ans=-1;       printf("%dn",ans); }

B-牛牛爱数学

做法：求根公式简单化简下，答案就是b*c/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; } int main() {     int _=read();while(_--)     {         ll a=read(),b=read(),c=read();         ll fz=b*c;         if(fz%a==0) printf("%lldn",fz/a);         else puts("-1");     } }

C-牛牛种花

做法:偏序的经典问题。对一维排序，另一维 用线段树或者树状数组维护前缀和即可。

 #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=2e5+10; struct node {     int x,y,ty,id; }a[N]; int X[N],Y[N],lx,ly,len,ans[N],sum[4*N]; bool cmp(node a,node b) {     if(a.x!=b.x) return a.x<b.x;     return a.y<b.y; } int qu(int id,int l,int r,int ql,int qr) {     if(ql<=l&&r<=qr) return sum[id];     int mid=l+r>>1;     int ans=0;     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 pos) {     sum[id]++;     if(l==r) return ;     int mid=l+r>>1;     if(pos<=mid) up(id<<1,l,mid,pos);     else up(id<<1|1,mid+1,r,pos); } int main() {     int n=read(),m=read();     rep(i,1,n)     {         int x=read(),y=read();         X[++lx]=x;         Y[++ly]=y;         a[++len]={x,y,1};     }     rep(i,1,m)     {         int x=read(),y=read();         X[++lx]=x;         Y[++ly]=y;         a[++len]={x,y,0,i};     }     sort(X+1,X+1+lx);     sort(Y+1,Y+1+ly);     lx=unique(X+1,X+1+lx)-X-1;     ly=unique(Y+1,Y+1+ly)-Y-1;     //printf("lx:%d ly:%dn",lx,ly);         rep(i,1,len){         a[i].x=lower_bound(X+1,X+1+lx,a[i].x)-X;         a[i].y=lower_bound(Y+1,Y+1+ly,a[i].y)-Y;     }       //puts("***");       sort(a+1,a+1+len,cmp);     //rep(i,1,len)     rep(i,1,len)     {         //printf("i:%dn",i);           if(a[i].ty==0){             ans[a[i].id]=qu(1,1,ly,1,a[i].y);         }         else{             up(1,1,ly,a[i].y);         }     }     rep(i,1,m) printf("%dn",ans[i]);   }

D-失忆药水

做法: 其实很简单的一道题，二分图是不含奇环的图，所以就是完全图的边数减去 最佳二分图的边数即可。

二分图边数怎么算？一边是n/2 另一边是n-n/2  两边点数相乘即可。

 #include<bits/stdc++.h> using namespace std;  const int N=1e6+10,M=2e7+10,mod=998244353; int n,m; long long  dp[N]; int main() {     dp[2]=1;     for(int i=3;i<N;i++)dp[i]=dp[i-1]+(i)/2;     while(~scanf("%d",&n)){         printf("%lldn",1ll*n*(n-1)/2-dp[n]);     }     return 0; }

E-牛牛走迷宫

做法：简单的输出路径的bfs

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #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=5e2+10,inf=0x3f3f3f3f; char s[N][N]; int n,m,dir[4][2]={1,0,0,-1,0,1,-1,0}; int vs[N][N]; pair<int,int> ans[N][N]; void bfs() {     memset(vs,inf,sizeof(vs));     queue<pair<int,int> >que;     que.push({1,1});     vs[1][1]=0;       while(que.size()){         auto now=que.front();que.pop();           for(int i=0;i<4;++i){             int x=now.first+dir[i][0];             int y=now.second+dir[i][1];             if(x<1||y<1||x>n||y>m||s[x][y]=='1') continue;               if(vs[x][y]<=vs[now.first][now.second]+1) continue;             //printf("x:%d y:%dn",x,y);             ans[x][y]={now.first,now.second};             //printf("x:%d y:%d fi:%d se:%dn",x,y,ans[x][y].first,ans[x][y].second);               vs[x][y]=vs[now.first][now.second]+1;             que.push({x,y});         }     } } int main() {     n=read(),m=read();     rep(i,1,n) scanf("%s",s[i]+1);     bfs();     if(vs[n][m]==inf)         puts("-1");       else{         int x=n,y=m;         stack<char>sta;         while(x!=1||y!=1){             int nx=ans[x][y].first;             int ny=ans[x][y].second;             if(x==nx+1) sta.push('D');             if(y==ny+1) sta.push('R');             if(y==ny-1) sta.push('L');             if(x==nx-1) sta.push('U');               x=nx,y=ny;         }           printf("%dn",sta.size());         while(sta.size()){             printf("%c",sta.top());sta.pop();         }         //sta.push(s[1][1]);     } }

F-牛牛的序列

做法：不太会，看的官方题解：

最后答案就是求区间的奇数平方数及其二次幂的个数。

[1,n] 的区间平方数个数  

 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=1000000000; const double pi=acos(-1);  ll num(ll x) {     ll l=0,r=x,ans;     while(l<=r)     {         ll p=(l+r)/2;         if(p*p<=x)l=p+1,ans=p;         else r=p-1;     }     return l; }   int main() {     //for(int i=1;i<=1000;i++)printf("i=%d %dn",i,sum(i));     ll T;     scanf("%lld",&T);     while(T--)     {         ll a,b;         scanf("%lld%lld",&a,&b);         if(a>b)swap(a,b);         ll ans=num(b)-num(a-1)+num(b/2)-num((a+1)/2-1);         //printf("ans=%lldn",ans);         printf("%lldn",ans%2);     }     return 0; } 

G-牛牛爱几何

做法：简单几何题

 #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; const double pi=acos(-1); 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; } int main() {     double n;     while(cin>>n)     {         double r=n/2;         double ans=pi*r*r/4-r*r/2;         ans*=8;         printf("%.6fn",ans);     } }

H-保卫家园

做法：很思维的一道题，智商题，做法参考官解：

不用管 每时每刻必须达到最大编制，都是忽悠人的，只需要考虑最多能有多少区间能加入即可，那当能加入区间大于k时，就删掉区间最长的那个最长的那个就可以了。

 #include<bits/stdc++.h> using namespace std; const int N=1e6+10; vector<int>G[N]; int n,k; int main() {     scanf("%d%d",&n,&k);     for(int i=1;i<=n;++i){         int l,r;         scanf("%d%d",&l,&r);         G[l].push_back(r);     }     multiset<int>st;     int ans=0;     for(int i=1;i<=1000000;++i){         while(st.size()&&*(st.begin())<i) st.erase(st.begin());         for(int v:G[i]){             if(st.size()<k) st.insert(v);             else{                 st.insert(v);                 st.erase(--st.end());                 ans++;             }         }     }     printf("%dn",ans); } 

I-恶魔果实

做法：建有向图，然后求每个数值的能到达数的个数，组合数乘起来就是答案了。

 #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 mod=1e4+7; int x,n,vis[12],vs[12][12],dp[12];   vector<int>G[12];   int run(int u) {     if(dp[u]!=0) return dp[u];       memset(vis,0,sizeof(vis));     int ans=0;     queue<int>que;que.push(u);       while(que.size()){         int now=que.front();que.pop();         ans++;vis[now]=1;         for(int v:G[now]) if(!vis[v]) {             que.push(v);             vis[v]=1;         }     }     dp[u]=ans;     return ans; } int main() {     x=read(),n=read();     rep(i,1,n)     {         int u=read(),v=read();         if(vs[u][v]) continue;         vs[u][v]=1;         G[u].push_back(v);     }       int ans=1;     while(x)     {         int d=x%10;         ans=ans*run(d)%mod;         x=x/10;     }     printf("%dn",ans); }

J-牛牛喜欢字符串

做法：水题，记录每个串内的位置字符个数，总个数减去最大的数即可。

 #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; const double pi=acos(-1); 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=1e6+10; char s[N]; int dp[N][26],n,k; int main() {     n=read(),k=read();     scanf("%s",s+1);     int tot=n/k;       for(int i=1;i+k-1<=n;i=i+k){         for(int j=1,t=i;j<=k;++j,++t){             dp[j][s[t]-'a']++;         }     }       ll ans=0;     for(int i=1;i<=k;++i){         int mx=0;         for(int j=0;j<26;++j) mx=max(mx,dp[i][j]);         ans+=tot-mx;     }     printf("%lldn",ans); }