Codeforces Round #545 (Div. 1)

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

### A - Skyscrapers ###

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

### B - Camp Schedule ###

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

### C - Museums Tour ###

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

#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\\)步，最终一定是都在终点了。

### E - Train Car Selection ###

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

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

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