Codeforces Round #545 (Div. 1)

短命女 2021-12-24 08:37 294阅读 0赞

A - Skyscrapers

暴力离散化之后再乱搞一搞就好了。

  1. #include<bits/stdc++.h> #define qmin(x,y) (x=min(x,y)) #define qmax(x,y) (x=max(x,y)) #define vi vector<int> #define vit vector<int>::iterator #define pir pair<int,int> #define fr first #define sc second #define mp(x,y) make_pair(x,y) using namespace std; inline char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; return getchar(); } template<class T> int read(T &ans) { ans=0;char ch=gc();T f=1; while(!isdigit(ch)) { if(ch==EOF) return -1; if(ch=='-') f=-1; ch=gc(); } while(isdigit(ch)) ans=ans*10+ch-'0',ch=gc(); ans*=f;return 1; } template<class T1,class T2> int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF; } template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF; } typedef long long ll; const int Maxn=1100; const int inf=0x3f3f3f3f; int n,m,mp[Maxn][Maxn],l[Maxn][Maxn],h[Maxn][Maxn],b[Maxn],num[Maxn],num2[Maxn]; int main() { // freopen("test.in","r",stdin); read(n,m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(mp[i][j]); for(int i=1;i<=n;i++) { map<int,int> ma; for(int j=1;j<=m;j++) b[j]=mp[i][j]; sort(b+1,b+m+1); for(int j=1;j<=m;j++) if(!ma[b[j]]) ma[b[j]]=++num[i]; for(int j=1;j<=m;j++) h[i][j]=ma[mp[i][j]]; } for(int i=1;i<=m;i++) { map<int,int> ma; for(int j=1;j<=n;j++) b[j]=mp[j][i]; sort(b+1,b+n+1); for(int j=1;j<=n;j++) if(!ma[b[j]]) ma[b[j]]=++num2[i]; for(int j=1;j<=n;j++) l[j][i]=ma[mp[j][i]]; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) printf("%d ",max(l[i][j],h[i][j])+max(num[i]-h[i][j],num2[j]-l[i][j])); putchar('\n'); } return 0; }

B - Camp Schedule

首先用kmp求出next[n]，然后先弄出来一个串，然后每次从next[n]一直到最后，如果有一种用完了就不弄了。

  1. #include<bits/stdc++.h> #define qmin(x,y) (x=min(x,y)) #define qmax(x,y) (x=max(x,y)) #define vi vector<int> #define vit vector<int>::iterator #define pir pair<int,int> #define fr first #define sc second #define mp(x,y) make_pair(x,y) using namespace std; inline char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; return getchar(); } template<class T> int read(T &ans) { ans=0;char ch=gc();T f=1; while(!isdigit(ch)) { if(ch==EOF) return -1; if(ch=='-') f=-1; ch=gc(); } while(isdigit(ch)) ans=ans*10+ch-'0',ch=gc(); ans*=f;return 1; } template<class T1,class T2> int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF; } template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF; } typedef long long ll; const int Maxn=1100000; const int inf=0x3f3f3f3f; int nxt[Maxn],bj[3]; char s[Maxn],t[Maxn]; void find_next(char *a) { nxt[0]=0; int len=strlen(a); int temp=0; for(int i=1;i<len;i++) { while(temp>0&&a[temp]!=a[i])temp=nxt[temp]; if(a[temp]==a[i]) nxt[i+1]=++temp; else nxt[i+1]=0; } } int print() { while(bj[0]--) putchar('0'); while(bj[1]--) putchar('1'); putchar('\n'); return 0; } int main() { // freopen("test.in","r",stdin); scanf("%s",s); scanf("%s",t); find_next(t); int ls=strlen(s),lt=strlen(t); for(int i=0;i<ls;i++) bj[s[i]-'0']++; for(int i=0;i<lt;i++) { if(!bj[t[i]-'0']) return print(); putchar(t[i]); bj[t[i]-'0']--; } while(1) { for(int i=nxt[lt];i<lt;i++) { if(!bj[t[i]-'0']) return print(); putchar(t[i]); bj[t[i]-'0']--; } } return 0; }

C - Museums Tour

首先构造分层图，新的点可以用二元组\((i,j)\)来表示第\(i\)天位于\(j\)号点的状态，对于原图上的一条边，直接连接对应点的每一天即可，然后跑强连通分量，对于每个强连通分量记录一下总共会经过多少个不同的博物馆，然后就可以DP了。

  1. #include<bits/stdc++.h> #define qmin(x,y) (x=min(x,y)) #define qmax(x,y) (x=max(x,y)) #define vi vector<int> #define vit vector<int>::iterator #define pir pair<int,int> #define fr first #define sc second #define mp(x,y) make_pair(x,y) using namespace std; inline char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; return getchar(); } template<class T> int read(T &ans) { ans=0;char ch=gc();T f=1; while(!isdigit(ch)) { if(ch==EOF) return -1; if(ch=='-') f=-1; ch=gc(); } while(isdigit(ch)) ans=ans*10+ch-'0',ch=gc(); ans*=f;return 1; } template<class T1,class T2> int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF; } template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF; } typedef long long ll; const int Maxn=5100000; const int inf=0x3f3f3f3f; int to[Maxn],nxt[Maxn],first[Maxn],tot=1; int du[Maxn],belong[Maxn],flag[Maxn],bj[Maxn],f[Maxn]; int n,m,d,u,v,num,dp[Maxn]; queue<int> q; inline void add(int u,int v) { to[tot]=v; nxt[tot]=first[u]; first[u]=tot++; du[v]++; } struct graph { int to[Maxn],nxt[Maxn],first[Maxn],tot; int s[Maxn],ran[Maxn],cnt,vis[Maxn],bj[Maxn],top; inline void add(int u,int v) { to[tot]=v; nxt[tot]=first[u]; first[u]=tot++; } int dfs(int root) { vis[root]=1,bj[root]=1; s[++top]=root; ran[root]=++cnt; int low=cnt; for(int i=first[root];i;i=nxt[i]) if(!vis[to[i]]) qmin(low,dfs(to[i])); else if(bj[to[i]]) qmin(low,ran[to[i]]); if(low==ran[root]) { num++; int temp=top; do { int sxz=s[top]; belong[sxz]=num; bj[sxz]=0; if(::bj[sxz]&&!flag[(sxz-1)/d]) f[num]++,flag[(sxz-1)/d]=1; } while(s[top--]!=root); for(int i=top+1;i<=temp;i++) flag[(s[i]-1)/d]=0; } return low; } void tarjan() { for(int i=1;i<=n*d;i++) if(!vis[i]) dfs(i); for(int i=1;i<=n*d;i++) for(int j=first[i];j;j=nxt[j]) if(belong[i]!=belong[to[j]]) ::add(belong[to[j]],belong[i]); } }t1; void topo() { for(int i=1;i<=num;i++) if(!du[i]) q.push(i),dp[i]=f[i]; while(!q.empty()) { int now=q.front();q.pop(); for(int i=first[now];i;i=nxt[i]) { qmax(dp[to[i]],dp[now]); if(!--du[to[i]]) { dp[to[i]]+=f[to[i]]; q.push(to[i]); } } } } int main() { // freopen("test.in","r",stdin); read(n,m,d); t1.tot=1; for(int i=1;i<=m;i++) { read(u,v); u--,v--; u*=d,v*=d; for(int j=1;j<d;j++) t1.add(u+j,v+j+1); t1.add(u+d,v+1); } for(int i=1,temp=1;i<=n;i++) for(int j=1;j<=d;j++,temp++) scanf("%1d",&bj[temp]); t1.tarjan(); topo(); printf("%d\n",dp[belong[1]]); return 0; }

D - Cooperative Game

首先让两个点开始跑，每次一个跑一步，另一个跑两步，那么他们相遇时，跑一步的很显然没有超过一圈，设为\(t+x\)步，那么另一个跑了\(2*(t+x)\)步。

由于第二个人多跑的一定是一些整圈，所以\(c|(t+x)\)，这两个人都在圈上的第\(x\)个位置，那么如果再让他们都跑\(t\)步，最终一定是都在终点了。

  1. #include<bits/stdc++.h> #define qmin(x,y) (x=min(x,y)) #define qmax(x,y) (x=max(x,y)) #define vi vector<int> #define vit vector<int>::iterator #define pir pair<int,int> #define fr first #define sc second #define mp(x,y) make_pair(x,y) using namespace std; inline char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; return getchar(); } template<class T> int read(T &ans) { ans=0;char ch=gc();T f=1; while(!isdigit(ch)) { if(ch==EOF) return -1; if(ch=='-') f=-1; ch=gc(); } while(isdigit(ch)) ans=ans*10+ch-'0',ch=gc(); ans*=f;return 1; } template<class T1,class T2> int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF; } template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF; } typedef long long ll; const int Maxn=1100000; const int inf=0x3f3f3f3f; char s[110]; int getnum() { int x; read(x); gets(s); return x; } int main() { // freopen("test.in","r",stdin); do { printf("next 0 1\n"); fflush(stdout); getnum(); printf("next 0\n"); fflush(stdout); } while(getnum()>2); do { printf("next 0 1 2 3 4 5 6 7 8 9\n"); fflush(stdout); } while(getnum()>1); printf("done\n"); fflush(stdout); return 0; }

E - Train Car Selection

答案一定是在一个凸壳上的，那么从前面插入一个点时，就重置一下，凸壳上只有一个点\((0,0)\)，等差数列公差\(a\)和首项\(b\)也置为0。

从后面插入时要插入\((n,-(an+b))\)，然后维护凸壳即可。

  1. #include<bits/stdc++.h> #define qmin(x,y) (x=min(x,y)) #define qmax(x,y) (x=max(x,y)) #define vi vector<int> #define vit vector<int>::iterator #define pir pair<int,int> #define fr first #define sc second #define mp(x,y) make_pair(x,y) using namespace std; inline char gc() { // static char buf[100000],*p1,*p2; // return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; return getchar(); } template<class T> int read(T &ans) { ans=0;char ch=gc();T f=1; while(!isdigit(ch)) { if(ch==EOF) return -1; if(ch=='-') f=-1; ch=gc(); } while(isdigit(ch)) ans=ans*10+ch-'0',ch=gc(); ans*=f;return 1; } template<class T1,class T2> int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF; } template<class T1,class T2,class T3> int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF; } typedef long long ll; const int Maxn=1100000; const int inf=0x3f3f3f3f; int m,opt; ll a,b,n,x; pair<ll,ll> p[Maxn]; ll calc(pair<ll,ll> x) { return a*x.fr+x.sc+b; } int main() { // freopen("test.in","r",stdin); read(n,m); int l=1,r=1; p[1]=mp(0,0); while(m--) { read(opt); if(opt==1) { l=r=1; p[1]=mp(0,0); read(x); a=b=0; n+=x; } else if(opt==2) { pair<ll,ll> now=mp(n,-(n*a+b)); while(r>l&&(long double)(now.sc-p[r].sc)*(p[r].fr-p[r-1].fr)<(long double)(p[r].sc-p[r-1].sc)*(now.fr-p[r].fr)) r--; p[++r]=now; read(x); n+=x; } else if(opt==3) { read(x);b+=x; read(x);a+=x; } while(r>l&&calc(p[r])>=calc(p[r-1])) r--; printf("%lld %lld\n",p[r].fr+1,calc(p[r])); } return 0; }

转载于:https://www.cnblogs.com/shanxieng/p/10499304.html

发表评论

表情：
评论列表 （有 0 条评论，294人围观）

还没有评论，来说两句吧...

相关阅读

    相关 Codeforces Round #564 (Div. 1)

    A 太难了，一半时间刚这题还没做出来，简直自闭了。实际上分两种情况，一种很简单直接放，另一种就是要0,0,…,0,1,2,…,n，然后直接贪心，显然我是把情况判断错误一直没调

    比眉伴天荒比眉伴天荒/ 0 赞/ 321 阅读