Codeforces Round 545 (Div. 1)

https://codeforces.com/contest/1137

A. Skyscrapers

看懂题意就很简单了，直接对每一行每一列离散化一下就行了。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e3+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int a[maxn][maxn],b[maxn][maxn],n,m,t[maxn];
 
void get(int *r,int p) {
    for(int i=1;i<=p;i++) t[i]=r[i];
    sort(t+1,t+p+1);r[0]=unique(t+1,t+p+1)-t-1;
    for(int i=1;i<=p;i++) r[i]=lower_bound(t+1,t+r[0]+1,r[i])-t;
}
 
int main() {
    read(n),read(m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) read(a[i][j]),b[j][i]=a[i][j];
    for(int i=1;i<=n;i++) get(a[i],m);
    for(int i=1;i<=m;i++) get(b[i],n);
    for(int i=1;i<=n;i++,puts(""))
        for(int j=1;j<=m;j++)
            printf("%d ",max(a[i][j],b[j][i])+max(a[i][0]-a[i][j],b[j][0]-b[j][i]));
    return 0;
}

B. Camp Schedule

这个B怎么比A还水啊…

直接$\rm kmp$，每次到结尾就跳$\rm next$。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int n,m,a,b,nxt[maxn];
char s[maxn],t[maxn];
 
void get_nxt() {
    for(int j=0,i=2;i<=n;i++) {
        if(t[j+1]==t[i]) j++,nxt[i]=j;
        else {
            while(j&&t[j+1]!=t[i]) j=nxt[j];
            if(t[j+1]==t[i]) j++;nxt[i]=j;
        }
    }
}
 
int main() {
    scanf("%s",s+1);m=strlen(s+1);
    for(int i=1;i<=m;i++) if(s[i]=='0') a++;b=m-a;
    scanf("%s",t+1);n=strlen(t+1);
    get_nxt();
    int p=n-nxt[n];//cerr<<p<<endl;
    int c=0,d;
    for(int i=1;i<=p;i++) if(t[i]=='0') c++;d=p-c;
    while(a-c>=0&&b-d>=0) {
        a-=c,b-=d;
        for(int i=1;i<=p;i++) putchar(t[i]);
    }
    for(int i=1;i<=p;i++)
        if(t[i]=='0') {if(a) a--,putchar('0');else break;}
        else {if(b) b--,putchar('1');else break;}
    for(int i=1;i<=a;i++) putchar('0');
    for(int i=1;i<=b;i++) putchar('1');puts("");
    return 0;
}

C. Museums Tour

思路很简单，一个点拆成$d$个，第$i$个代表一星期的第$i$天。

那么每个点有个权值表示在这个环里绕圈圈可以去的博物馆的种类最多有多少。

注意到如果$(i,a)$可以到达$(i,b)$（其中$i$是点$a,b$是时间），那么$(i,b)$必然能到$(i,a)$，所以任意一条路径的权值之和就是种类数，不会算重复。

然后缩点跑$\rm DAG$上$\rm dp$就行了。

不过我好像写太丑$\text{MLE on test 73}$。。但是也有$AC$代码用的一样的思路。

代码还是贴出来吧，注意仅供参考

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 6e6+10;
const int N = 2e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
char s[100];
int n,m,d,bel[maxn],scc;
int dfn[maxn],low[maxn],sta[maxn],top,dfn_cnt;
bool in[maxn],t[N];
 
int ihead[maxn],itot,f[maxn];
struct edge{int to,nxt;}ie[maxn],e[maxn];
 
void iins(int u,int v) {ie[++itot]=(edge){v,ihead[u]},ihead[u]=itot,sta[v]++;}
 
void fuck() {
    queue<int > q;
    for(int i=1;i<=scc;i++) if(!sta[i]) q.push(i);
    while(!q.empty()) {
        int x=q.front();q.pop();f[x]+=low[x];
        for(int v,i=ihead[x];i;i=ie[i].nxt) {
            v=ie[i].to;f[v]=max(f[v],f[x]);
            if(!(--sta[v])) q.push(v);
        }
    }
}
 
int head[maxn],tot;
 
void ins(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}
 
int id(int a,int b) {return (b-1)*n+a;}
 
void tarjan(int x) {
    sta[++top]=x;int tt=top;low[x]=dfn[x]=++dfn_cnt;in[x]=1;
    for(int v,i=head[x];i;i=e[i].nxt)
        if(!dfn[v=e[i].to]) tarjan(v),low[x]=min(low[x],low[v]);
        else if(in[v]) low[x]=min(low[x],dfn[v]);
    if(dfn[x]==low[x]) {
        scc++;
        for(int i=tt,v;i<=top;i++) in[v=sta[i]]=0,bel[v]=scc;
        top=tt-1;
    }
}
 
int main() {
    read(n),read(m),read(d);
    for(int i=1;i<=m;i++) {
        int a,b;read(a),read(b);
        for(int j=1;j<d;j++) ins(id(a,j),id(b,j+1));
        ins(id(a,d),id(b,1));
    }tarjan(1);memset(dfn,0,sizeof dfn);
    memset(low,0,sizeof low);
    memset(sta,0,sizeof sta);
    for(int i=1;i<=n;i++) {
        scanf("%s",s+1);
        for(int x,j=1;j<=d;j++)
            if(s[j]-'0'&&dfn[x=bel[id(i,j)]]!=i) low[x]++,dfn[x]=i;
    }
    for(int x=1;x<=n*d;x++)
        for(int i=head[x];i;i=e[i].nxt) 
            if(bel[x]!=bel[e[i].to]) iins(bel[e[i].to],bel[x]);
    fuck();write(f[bel[1]]);
    return 0;
}

D. Cooperative Game

挺巧妙的交互题，但是$cf$讨论版有人说是原题而且可以直接$\rm google$到？

首先$10$个人是吓人的，只需要三个就可以完成这个题目。

我们记这三个人分别叫$a,b,c$。

那么我们进行若干轮，每次让$a$走两步，$b$走一步，这需要花费两次交互。

直到$a,b$相遇我们停止，那么分析一下，假设现在$b$走了$x$步，$a$绕了$k$圈，并且显然$b$不可能走完一圈，可以得到：

$$kc+t+(x-t)=2x\\ x\equiv 0 \pmod{c}$$

也就是说$b$在环上走的步数为$(x-t)$，则可以得到：

$$x-t\equiv -t\pmod c$$

那么就是说只要在让所有人一起走，知道他们集合到一个点，那么这个点必然为所求的点。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int get_ans() {
    fflush(stdout);int x;read(x);for(int i=1;i<=x;i++) scanf("%*s");return x;
}
 
int main() {
    while(1) {
        puts("next 0 1");get_ans();
        puts("next 0");if(get_ans()==2) break;
    }
    while(1) {
        puts("next 0 1 2 3 4 5 6 7 8 9");
        if(get_ans()==1) break;
    }
    puts("done");fflush(stdout);
    return 0;
}

E. Train Car Selection

首先可以得到几个显然的结论：一段只取第一个数就好了，如果往前面加$0$那么后面的都没用了。

那么把每个数看做点$(x,a_x)$，统计一下$b,s$的总和。

注意到对于$i,j,i<j$，何时$i$将来会比$j$优。

首先显然$a_isj+b+a_j$，化一下就是斜率式子。

那么维护下凸壳就好了。

#include<bits/stdc++.h>
using namespace std;
 
#define int long long 
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf long double
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int n,q,top,sum[maxn],suma,sumb;
struct P {
    int x,y;
    P operator - (const P &a) const {return (P){x-a.x,y-a.y};}
    lf operator * (const P &a) const {return (lf)x*a.y-(lf)y*a.x;}
}sta[maxn];
 
signed main() {
    read(n),read(q);n--;
    sta[++top]=(P){0,0};
    for(int i=1;i<=q;i++) {
        int op,a;read(op),read(a);
        if(op==1) {
            suma=sumb=0;top=0;n+=a;
            sta[++top]=(P){0,0};
        } else if(op==2) {
            int x=n+1,y=-suma*(n+1)-sumb;n+=a;
            while(top>1&&(sta[top-1]-sta[top])*((P){x,y}-sta[top])>1.00) top--;
            sta[++top]=(P){x,y};
        } else {
            int b;read(b);suma+=b,sumb+=a;
        }
        while(top>1&&(lf)sta[top].x*suma+sta[top].y>=(lf)sta[top-1].x*suma+sta[top-1].y) top--;
        printf("%lld %lld\n",sta[top].x+1,sta[top].y+sta[top].x*suma+sumb);
    }
    return 0;
}

F. Matches Are Not a Child’s Play

首先显然两个询问是本质相同的。

然后最大的那个一定是最后删除的，我们不妨把它设为根。

假设现在要进行$\rm up~x$的操作，那么可以发现只会改变$x$到根的相对大小关系，具体来说就是一定是删除到只剩这条链的时候在把这条链删掉。

那么我们用$\rm LCT$来维护这个过程，对于每个修改我们把这个点到根的链染上一个新的颜色，然后$\text{make_root}$一下就好了。

那么对于询问我们用一个树状数组来记录颜色的前缀和，假设询问$x$那么答案就是前缀和加上深度比$x$大并且颜色相同的点数，这个$\rm LCT$里就是右儿子的大小。

复杂度$O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
#define ls son[x][0]
#define rs son[x][1]
 
int fa[maxn],son[maxn][2],sz[maxn],rev[maxn],sta[maxn],top,n,m,col[maxn],cov[maxn];
 
void update(int x) {sz[x]=sz[ls]+sz[rs]+1;}
 
int which(int x) {return son[fa[x]][1]==x;}
int nrt(int x) {return son[fa[x]][0]==x||son[fa[x]][1]==x;}
 
void push_cov(int x,int v) {col[x]=cov[x]=v;}
void push_rev(int x) {swap(ls,rs);rev[x]^=1;}
 
void pushdown(int x) {
    if(cov[x]) push_cov(ls,cov[x]),push_cov(rs,cov[x]),cov[x]=0;
    if(rev[x]) rev[x]=0,push_rev(ls),push_rev(rs);
}
 
void rotate(int x) {
    int y=fa[x],z=fa[y],w=which(x);
    if(nrt(y)) son[z][son[z][1]==y]=x;
    fa[x]=z,fa[y]=x,fa[son[x][w^1]]=y,son[y][w]=son[x][w^1],son[x][w^1]=y;
    update(y),update(x);
}
 
void splay(int x) {
    int t=x;while(nrt(t)) sta[++top]=t,t=fa[t];
    sta[++top]=t;while(top) pushdown(sta[top--]);
    while(nrt(x)) {
        int y=fa[x],z=fa[y];
        if(nrt(y)) rotate(((son[z][1]==y)^(son[y][1]==x))?x:y);
        rotate(x);
    }update(x);
}
 
struct BIT {
    int t[maxn];
    void modify(int x,int v) {if(!x) return ;for(;x<=n+m;x+=x&-x) t[x]+=v;}
    int query(int x,int ans=0) {for(;x;x-=x&-x) ans+=t[x];return ans;}
}T;
 
void access(int x,int c) {
    for(int t=0;x;t=x,x=fa[x]) {
        splay(x);
        T.modify(col[x],-sz[ls]-1);
        rs=t;push_cov(ls,c);pushdown(ls);col[x]=c;
        T.modify(c,sz[ls]+1);update(x);
    }
}
 
void link(int x,int y) {
    access(x,0);splay(x);push_rev(x);
    fa[x]=y;
}
 
int query(int x) {
    splay(x);
    int res=T.query(col[x]-1);
    splay(x);res+=sz[rs]+1;return res;
}
 
char s[20];int cnt;
 
void up(int x) {
    access(x,cnt),splay(x),push_rev(x),pushdown(x);
    T.modify(cnt,-1);push_cov(x,++cnt),sz[x]=1,rs=0;
    T.modify(cnt,1);
}
 
int main() {
    read(n),read(m);
    for(int i=1,x,y;i<n;i++) read(x),read(y),link(x,y);
    for(int i=1;i<=n;i++) up(i);
    // for(int i=1;i<=n;i++) printf("%d ",col[i]);puts("");
    for(int i=1;i<=m;i++) {
        scanf("%s",s+1);int x,y;read(x);
        if(s[1]=='u') up(x);
        else if(s[1]=='w') write(query(x));
        else read(y),write(query(x)<query(y)?x:y);
        // if(s[1]=='u') {for(int i=1;i<=n;i++) printf("%d ",col[i]);puts("");}
    }
    return 0;
}