Educational Codeforces Round 31 题解

比赛链接：http://codeforces.com/contest/884

A. Book Reading

题意：略

解法：水题，模拟。

#include <bits/stdc++.h>
using namespace std;
int a[110];
int main(){
    int n, t;
    scanf("%d %d", &n,&t);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    int ans = 0;
    for(int i=1; i<=n; i++){
        ans += 86400-a[i];
        if(ans>=t){
            return 0*printf("%d\n", i);
        }
    }
}

B. Japanese Crosswords Strike Back

题意：给了一个01串编码，记录1的个数放到数组里，问是否能唯一确定一个01串。

解法：判断n-1+数组的和和字符串长度是否相等就ok。

#include <bits/stdc++.h>
using namespace std;
int a[100010];
int main(){
    int n, x;
    scanf("%d %d", &n,&x);
    int sum = 0;
    for(int i=1; i<=n; i++) scanf("%d", &a[i]), sum += a[i];
    if((n-1+sum)==x){
        puts("YES");
    }else{
        puts("NO");
    }
    return 0;
}

C. Bertown Subway

题意：给了一个排列，最多可以交换一对数，问最多有多少个不同的pair(i,j)使得从i出发可以到j。

解法：随手猜一下，应该是最大的两个环合成一个环，剩下的算个组合数就好，特判只有一个环，由于是排列，直接wihle找环。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+6;
typedef long long LL;
int n, p[maxn];
bool vis[maxn];
vector <int> v;
LL cal(LL x){
    return x*(x-1)+x;
}
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d",&p[i]);
    memset(vis, false, sizeof(vis));
    for(int i=1; i<=n; i++){
        int cnt = 0;
        if(vis[p[i]]) continue;
        int x = p[i];
        while(!vis[x]){
            ++cnt;
            vis[x]=1;
            x=p[x];
        }
        v.push_back(cnt);
    }
    sort(v.begin(),v.end());
    LL ans = 0;
    if(v.size()==1) return 0*printf("%lld\n", cal(1LL*v[0]));
    for(int i=0; i<v.size()-2; i++){
        ans += cal(1LL*v[i]);
    }
    printf("%lld\n", ans+cal(v[v.size()-1]+v[v.size()-2]));
    return 0;
}

D. Boxes And Balls

题意：有n个不同的盒子，并且有n种不同的颜色，询问最后要把第i种颜色放在i位置需要的代价，这个人每次操作分2步，第一步是把所有的没有在对应的位置的颜色拿到手里，第二步是可以放2个或者3个颜色在指定位置，问整个游戏的最小代价。

解法：样例已经提醒我们需要选最大的2个或3个，对于奇数我们直接选3个就好，对于偶数在堆里面拍一个0就转化成了第一种case。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5+6;
int a[maxn];
priority_queue<LL,vector<LL>,greater<LL> >q;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    if(n%2==0) q.push(0);
    for(int i=1; i<=n; i++) q.push(a[i]);
    LL ans = 0;
    while(q.size()>1){
        LL t1=q.top(); q.pop();
        LL t2=q.top(); q.pop();
        LL t3=q.top(); q.pop();
        ans += t1+t2+t3;
        q.push(t1+t2+t3);
    }
    printf("%lld\n", ans);
    return 0;
}

E. Binary Matrix

题意：超大矩阵超小内存求联通块数量。

解法：按行扫描，保留上一行的状态以及上一行的并查集。扫描到第i行时候，把第i行值为1且相邻的元素加入到并查集中去。然后根据上一行的并查集，把第i行与上一行都为1且上下相邻的元素以上一行的元素的father点为标志，做一个等价类（等价类中包含的元素全都是第i行的）。等价类中的元素意义是他们都可以通过i-1行进行互联，然后把他们加入到并查集里面去。然后新的一行的并查集就建立完成了。把新的并查集和旧的并查集交换，这样一直做下去。

#include <bits/stdc++.h>
using namespace std;
const int maxn = (1<<14)+10;
int n, m;
char s[maxn];
short a[maxn], fa[maxn];
inline short find_set(short x){
    if(x==fa[x]) return x;
    else return fa[x]=find_set(fa[x]);
}

int main(){
    scanf("%d%d",&n,&m);
    memset(fa, -1, sizeof(fa));
    int ans = n*m;
    for(int i=0; i<n; i++){
        scanf("%s", s);
        int g = 0;
        for(int j=0; j<(m>>2); j++){
            int v = (s[j]<='9'?s[j]-'0':s[j]-'A'+10);
            for(int k=3; k>=0; --k,++g){
                a[g] = v>>k&1;
                if(a[g] == 0){
                    --ans;
                    fa[g]=-1;
                }else{
                    //先和上面的考虑联通
                    if(fa[g]!=-1){//联通成功
                        --ans;
                        int f = find_set(g);
                        fa[f] = fa[g] = g;
                    }else{
                        fa[g] = g;
                    }
                    if(g&&fa[g-1]!=-1&&find_set(g)!=find_set(g-1)){
                        --ans;
                        int fx = find_set(g);
                        int fy = find_set(g-1);
                        fa[fx] = fa[fy] = fa[g] = g;
                    }
                }
            }
        }
    }
    return 0*printf("%d\n", ans);
}

F. Anti-Palindromize

CF官方题解还提供了一个优雅的贪心解法，可以看一下。

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3FFFFFFF;
const int maxn = 2222;
struct node{
    int st, en, flow, cost, next;
    node(){}
    node(int st, int en, int flow, int cost, int next):st(st),en(en),flow(flow),cost(cost),next(next){}
}E[101000];

int num, p[maxn];
void init(){
    memset(p, -1, sizeof(p));
    num = 0;
}
void add(int st, int en, int flow, int cost){
    E[num] = node(st, en, flow, cost, p[st]);
    p[st] = num++;
    E[num] = node(en, st, 0, -cost, p[en]);
    p[en] = num++;
}
int pre[maxn];
int dis[maxn];
bool fg[maxn];
bool spfa(int st, int en)
{
    for(int i=0;i<=en;i++){
        fg[i] = 0, dis[i] = inf, pre[i]=-1;
    }
    queue<int>q;
    q.push(st);
    fg[st]=1;
    dis[st]=0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        fg[u]=0;
        for(int i=p[u];~i;i=E[i].next){
            int v = E[i].en;
            if(E[i].flow&&dis[v]>dis[u]+E[i].cost){
                dis[v] = dis[u]+E[i].cost;
                pre[v]=i;
                if(!fg[v]){
                    fg[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(dis[en] < inf) return 1;
    return 0;
}

int solve(int st, int en){
    int ans=0;
    while(spfa(st,en)){
        int d = inf;
        for(int i=pre[en];i+1;i=pre[E[i].st]) d = min(d, E[i].flow);
        for(int i=pre[en];i+1;i=pre[E[i].st]){
            E[i].flow -= d;
            E[i^1].flow += d;
            ans += d*E[i].cost;
        }
    }
    return ans;
}
int n, a[111];
int cnt[30];

int main(){
    scanf("%d", &n);
    string s;
    cin >> s;
    for(int i=0; i<n; i++) cnt[s[i]-'a']++;
    for(int i=0; i<n; i++) scanf("%d",&a[i]);
    init();
    int st=n+48, en = st+1;
    for(int i=0; i<26; i++){
        add(st, i+n, cnt[i], 0);
        for(int j=0; j<n/2; j++){
            if(s[j]==s[n-1-j]){
                int cost=0;
                if(s[j]=='a'+i) cost = -max(a[j],a[n-1-j]);
                add(i+n,j,1,cost);
            }else{
                int cost=0;
                if(s[j]=='a'+i) cost=-a[j];
                if(s[n-1-j]=='a'+i) cost=-a[n-1-j];
                add(i+n,j,1,cost);
            }
        }
    }
    for(int i=0; i<n/2; i++) add(i,en,2,0);
    return 0*printf("%d\n", -solve(st,en));
}