Codeforces Round #578 (Div. 2)

柔情只为你懂 2021-10-29 07:31 154阅读 0赞

# Codeforces Round \#578 (Div. 2) #

第一次打CF，，，

很水的第三题把题读错了，现在rating还没有初始rating高

### A Hotelier ###

模拟

#include <iostream> #include <cstdio> #include <cstring> using namespace std; string str; int n; int a[20]={}; int find_L() { for(register int i=0;i<=9;i++) if(!a[i])return i; } int find_R() { for(register int i=9;i>=0;i--) if(!a[i])return i; } int main() { scanf("%d",&n);cin>>str; for(register int i=0;i<str.size();i++) { if(str[i]=='L') { int p=find_L();a[p]=1; } if(str[i]=='R') { int p=find_R();a[p]=1; } if(str[i]>='0'||str[i]<='9')a[str[i]-'0']=0; } for(int i=0;i<=9;i++)printf("%d",a[i]); return 0; }

### B Block Adventure ###

贪心

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int n,m,k; int main() { int T;scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&k); int cnt=m;int pre=0;int pd=0; scanf("%d",&pre); for(int i=2;i<=n;i++) { int x;scanf("%d",&x); if(pd==1)continue; if(x-k>pre) { cnt-=(x-k-pre); if(cnt<0) { printf("NO\n");pd=1; } } if(x-pre<=k) { cnt+=(pre-max(x-k,0)); } pre=x; } if(!pd)printf("YES\n"); } return 0; }

### C Round Corridor ###

gcd

#include <iostream> #include <cstdio> using namespace std; #define ll long long ll n,m,q; ll gcd(ll x,ll y) { return y==0?x:gcd(y,x%y); } int main() { cin>>n>>m>>q; ll g=gcd(n,m); for(int i=1;i<=q;i++) { ll sx,sy,ex,ey; cin>>sx>>sy>>ex>>ey; ll area1,area2; if(sx==1)area1=(sy-1)/(n/g)+1;else area1=(sy-1)/(m/g)+1; if(ex==1)area2=(ey-1)/(n/g)+1;else area2=(ey-1)/(m/g)+1; if(area1!=area2)printf("NO\n"); else printf("YES\n"); } return 0; }

### D White Lines ###

行、列分开处理

有关前缀和应用的dp

#include <iostream> #include <cstdio> #include <cstring> using namespace std; int n,k; string str; int mp[2010][2010],x[2010][2010],y[2010][2010]; int fx[2010][2010],fy[2010][2010]; int sx[2010][2010],sy[2010][2010]; int cnt=0; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { cin>>str; for(int j=0;j<str.size();j++) { if(str[j]=='W')mp[i][j+1]=0;else mp[i][j+1]=1;x[i][j+1]=x[i][j]+mp[i][j+1];y[i][j+1]=y[i-1][j+1]+mp[i][j+1]; } } for(int i=1;i<=n;i++)if(x[i][n]==0)cnt++; for(int i=1;i<=n;i++)if(y[n][i]==0)cnt++; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(x[i][n]!=0) if(x[i][j+k-1]-x[i][j-1]==x[i][n])fx[i][j]=1; if(y[n][j]!=0) if(y[i+k-1][j]-y[i-1][j]==y[n][j])fy[i][j]=1; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { sx[i][j]=sx[i-1][j]+fx[i][j]; sy[i][j]=sy[i][j-1]+fy[i][j]; } int ans=0; for(int i=1;i<=n-k+1;i++) for(int j=1;j<=n-k+1;j++) { ans=max(ans,sx[i+k-1][j]-sx[i-1][j]+sy[i][j+k-1]-sy[i][j-1]+cnt); } printf("%d",ans); return 0; }

转载于:https://www.cnblogs.com/LianQ/p/11340007.html