「解题报告」Codeforces Round 597 (Div. 2)

真香警告.jpg……

A. Good ol’ Numbers Coloring

Source

看完样例就很显然了，切掉就好了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int read(){
    int s = 0,ne = 1; char c = getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c == '-') ne = -1;
    for(;c>='0'&&c<='9';c=getchar()) s = (s<<1)+(s<<3)+c-'0';
    return s * ne;
}
int t,a,b;
int gcd(int a,int b){return !b ? a : gcd(b, a % b);}
int main()
{
    t = read();
    while(t--){
        a = read(); b = read();
        if(gcd(a,b) == 1) printf("Finite\n");
        else printf("Infinite\n");
    }
    return 0;
}

B. Restricted RPS

Source

每步贪心，能干就干。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int CN = 2e5+5;
int read(){
    int s = 0,ne = 1; char c = getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c == '-') ne = -1;
    for(;c>='0'&&c<='9';c=getchar()) s = (s<<1)+(s<<3)+c-'0';
    return s * ne;
}
int t,n,s0,s1,s2,opt[CN],ans[CN]; bool bt[CN];
int main()
{
    t = read();
    while(t--){
        n = read(); s1 = read(); s0 = read(); s2 = read();
        for(int i=1;i<=n;i++){
            char c; cin>>c;
            if(c == 'P') opt[i] = 0;
            if(c == 'R') opt[i] = 1;
            if(c == 'S') opt[i] = 2;
        }

        memset(bt,0,sizeof(bt));
        int cnt = 0;
        for(int i=1;i<=n;i++){
            if(!opt[i] && s2) bt[i] = true,s2--;
            if(opt[i] == 1 && s0) bt[i] = true,s0--;
            if(opt[i] == 2 && s1) bt[i] = true,s1--;
        }
        for(int i=1;i<=n;i++){
            if(bt[i]) ans[i] = (opt[i] + 2) % 3,cnt++;
            else{
                if(s0) ans[i] = 0,s0--;
                else if(s1) ans[i] = 1,s1--;
                else if(s2) ans[i] = 2,s2--;
            }
        }

        int vs = n / 2;
        if(n % 2) vs += 1;
        if(cnt >= vs){
            printf("Yes\n");
            for(int i=1;i<=n;i++){
                if(!ans[i]) cout<<'P';
                if(ans[i] == 1) cout<<'R';
                if(ans[i] == 2) cout<<'S';
            }
            printf("\n");
        }
        else printf("No\n");
    }
    return 0;
}

C. Constanze’s Machine

Source

这题看上去还是比较有感觉的，只不过式子错了，这就很dl了（真香）。

首先显然可以把每个连续字段的方案数算出来然后再乘法原理，剩下的问题是求一个“连续字段”的方案数。

关于“连续字段”的方案，这个问题可以抽象成给你一段序列类似于“uuuuuu”这个样子，让你在其中划若干条长度为 2 的线，两两线不能相交，求方案数。那么显然这个东西可以设个状态写写方程，于是设 f[i] 表示考虑长度为 i 的序列的方案数。考虑新加入的这个元素，我们可以把它和元素 i-1 划成一段，方案数 f[i-2] ；也可以不划到任何一段，方案数 f[i-1] 。于是 f[i]=f[i-1]+f[i-2] ，又是 fibonacci 数列…然后做完了。

比赛的时候方程推成了 f[i]=f[i-1]+i-2 ，因为实际上我只考虑了划两段的情况…然后pretest9一直WA，自闭了，看来还是不够熟练…

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
 
#define LL long long
 
const int CN = 2e5+5;
const LL R = 1e9+7;
 
char ch[CN]; int n;
LL f[CN],ans = 1;
 
int main()
{
    cin>>ch; n = strlen(ch);
 
    f[1] = 1; f[2] = 2;
    for(LL i=3;i<=n;i++) f[i] = (f[i-1] + f[i-2]) % R;
 
    bool flag = true;
    for(int i=0;i<n;i++) if(ch[i] == 'm' || ch[i] == 'w') flag = false;
 
    if(!flag) printf("0");
    else{
        for(int i=0;i<n;i++){
            if(ch[i] != 'n' && ch[i] != 'u') continue;
            int p = i,l = 1;
            while(p < n && ch[p] == ch[p+1]) p++,l++;
            (ans *= f[l]) %= R;
            i = p;
        }
        printf("%I64d",ans);
    }
 
    return 0;
}

D. Shichikuji and Power Grid

Source

第一眼没什么感觉，看了 tutorial 发现就是个 mst … 建一个虚点向每个点连边，表示建电站就好了，看来还是不够熟练…

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
 
#define LL long long
 
const int CN = 2010;
 
class fs{
  public: int fr,to; LL di;
    void init(int f,int t,LL d) {fr=f;to=t;di=d;}
    bool operator < (const fs& a)const {return di < a.di;}
}E[CN * CN];
int ecnt = 0;
void add(int x,int y,LL z) {E[++ecnt].init(x,y,z);}
class ufs{
  public: int fa[CN];
    ufs() {for(int i=1;i<CN;i++) fa[i] = i;}
    int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
    bool exm(int x,int y) {return find(x) != find(y);}
    void merge(int x,int y) {fa[find(x)] = find(y);} 
}ck;
 
int n,px[CN],py[CN],pc[CN],pk[CN];
int abs(int x) {return x<0 ? -x : x;}
int dist(int a,int b) {return abs(px[a] - px[b]) + abs(py[a] - py[b]);}
 
bool sel[CN * CN]; LL si = 0;
void MST(){
    memset(sel,false,sizeof(sel));
    sort(E+1,E+ecnt+1);
    int cnt = 0;
    for(int i=1;i<=ecnt;i++){
        if(!ck.exm(E[i].fr, E[i].to)) continue;
        ck.merge(E[i].fr, E[i].to); 
        cnt++; si += E[i].di; sel[i] = true;
        if(cnt == n - 1) break;
    }
}
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&px[i],&py[i]);
    for(int i=1;i<=n;i++) scanf("%d",&pc[i]);
    for(int i=1;i<=n;i++) scanf("%d",&pk[i]);
 
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            add(i,j,1ll*(pk[i]+pk[j])*dist(i,j));
    for(int i=1;i<=n;i++) add(i,n+1,pc[i]);
    n += 1;
 
    MST();
 
    printf("%I64d\n",si);
    int cnt = 0;
    for(int i=1;i<=ecnt;i++) if(sel[i] && E[i].to == n) cnt++;
    printf("%d\n",cnt);
    for(int i=1;i<=ecnt;i++) if(sel[i] && E[i].to == n) printf("%d ",E[i].fr);
    printf("\n");
    cnt = n - 1 - cnt;
    printf("%d\n",cnt);
    for(int i=1;i<=ecnt;i++) if(sel[i] && E[i].to != n) printf("%d %d\n",E[i].fr,E[i].to);
    
    return 0;
}