Educational Codeforces Round 29 题解

A. Quasi-palindrome

题意：去掉前导0和后导0是不是回文数。

解法：直接模拟即可。

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

char s[20];

int main()
{
    scanf("%s", s);
    int pos1, pos2;
    int len = strlen(s);
    for(int i=0; i<len; i++){
        if(s[i]!='0'){
            pos1=i;
            break;
        }
    }
    for(int i=len-1; i>=0; i--){
        if(s[i]!='0'){
            pos2=i;
            break;
        }
    }
    while(pos1<=pos2){
        if(s[pos1]!=s[pos2]){
            puts("NO");
            return 0;
        }
        pos1++;
        pos2--;
    }
    puts("YES");
    return 0;
}

B. Kayaking

题意：2*n个人，有n-1条双人船，2条双人船，问如何安排使得所有的船的差值的和最小。

解法：直接枚举下2个人在担任船上，剩下直接排序顺序计算即可。

#include <bits/stdc++.h>
using namespace std;
int n, a[200];

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=2*n; i++) scanf("%d", &a[i]);
    sort(a+1, a+2*n+1);
    int ans = 1e9;
    for(int i=1; i<=2*n; i++){
        for(int j=i+1; j<=2*n; j++){
           int tmp = 0;
           vector <int> v;
           for(int k=1; k<=2*n; k++){
                if(k==i||k==j) continue;
                v.push_back(a[k]);
           }
           for(int k=0; k<v.size(); k+=2){
                tmp += v[k+1]-v[k];
           }
           ans = min(ans, tmp);
        }
    }
    printf("%d\n", ans);
    return 0;
}

C：

题意：两个人做简单石头步的游戏，给了2个3*3的矩阵，代表第一个人和第二个人在上次出了(x,y)这次改出a[x][y],b[x][y]，对于每个分数，出了x=y都有一个人会赢，问进行k轮之后两人的分数分别是多少？

解法：这个游戏是有循环节的，我们直接暴力出循环节直接计算即可。注意细节。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[4][4], b[4][4];
bool vis[4][4];
LL l1, l2;
int main()
{
    LL x, y;
    LL k;
    cin >> k >> x >> y;
    for (LL i = 1; i <= 3; i++)
        for (LL j = 1; j <= 3; j++)
            cin >> a[i][j];
    for (LL i = 1; i <= 3; i++)
        for (LL j = 1; j <= 3; j++)
            cin >> b[i][j];
    LL ans1 = 0, ans2 = 0;
    if (x == 3 && y == 2) ans1 = 1, ans2 = 0;
    else if (x == 2 && y == 1) ans1 = 1, ans2 = 0;
    else if (x == 1 && y == 3) ans1 = 1, ans2 = 0;
    else if (x == y) ans1 = 0, ans2 = 0;
    else ans1 = 0, ans2 = 1;
    LL cnt = 1;
    vis[x][y] = 1;
    l1 = l2 = 0;
    k--;
    while (1)
    {
        ++cnt;
        LL t1, t2;
        t1 = a[x][y];
        t2 = b[x][y];
        x = t1;
        y = t2;
        if (vis[x][y]) break;
        if (k)
        {
            k--;
        }
        else
        {
            break;
        }
        vis[x][y] = 1;
        LL tmp1 = 0, tmp2 = 0;
        if (x == 3 && y == 2) tmp1 = 1, tmp2 = 0;
        else if (x == 2 && y == 1) tmp1 = 1, tmp2 = 0;
        else if (x == 1 && y == 3) tmp1 = 1, tmp2 = 0;
        else if (x == y) tmp1 = 0, tmp2 = 0;
        else tmp1 = 0, tmp2 = 1;
        ans1 += tmp1;
        ans2 += tmp2;
    }
    LL curx = x, cury = y;
    memset(vis, 0, sizeof(vis));
    vis[curx][cury] = 1;
    if (x == 3 && y == 2) l1 = 1, l2 = 0;
    else if (x == 2 && y == 1) l1 = 1, l2 = 0;
    else if (x == 1 && y == 3) l1 = 1, l2 = 0;
    else if (x == y) l1 = 0, l2 = 0;
    else l1 = 0, l2 = 1;
    LL loop = 1;
    while (1)
    {
        LL t1, t2;
        t1 = a[curx][cury];
        t2 = b[curx][cury];
        curx = t1;
        cury = t2;
        if (vis[curx][cury]) break;
        vis[curx][cury] = 1;
        LL tmp1 = 0, tmp2 = 0;
        if (curx == 3 && cury == 2) tmp1 = 1, tmp2 = 0;
        else if (curx == 2 && cury == 1) tmp1 = 1, tmp2 = 0;
        else if (curx == 1 && cury == 3) tmp1 = 1, tmp2 = 0;
        else if (curx == cury) tmp1 = 0, tmp2 = 0;
        else tmp1 = 0, tmp2 = 1;
        l1 += tmp1;
        l2 += tmp2;
        ++loop;
    }
    LL pre = k / loop, afe = k % loop;
    ans1 += pre * l1;
    ans2 += pre * l2;
    if (afe)
    {
        LL tmp1 = 0, tmp2 = 0;
        if (x == 3 && y == 2) tmp1 = 1, tmp2 = 0;
        else if (x == 2 && y == 1) tmp1 = 1, tmp2 = 0;
        else if (x == 1 && y == 3) tmp1 = 1, tmp2 = 0;
        else if (x == y) tmp1 = 0, tmp2 = 0;
        else tmp1 = 0, tmp2 = 1;
        ans1 += tmp1;
        ans2 += tmp2;
    }
    for (LL i = 0; i < afe - 1; i++)
    {
        LL t1, t2;
        t1 = a[x][y];
        t2 = b[x][y];
        x = t1;
        y = t2;
        LL tmp1 = 0, tmp2 = 0;
        if (x == 3 && y == 2) tmp1 = 1, tmp2 = 0;
        else if (x == 2 && y == 1) tmp1 = 1, tmp2 = 0;
        else if (x == 1 && y == 3) tmp1 = 1, tmp2 = 0;
        else if (x == y) tmp1 = 0, tmp2 = 0;
        else tmp1 = 0, tmp2 = 1;
        ans1 += tmp1;
        ans2 += tmp2;
    }
    printf("%lld %lld\n", ans1, ans2);
    return 0;
}

D. Yet Another Array Queries Problem

题意：1个序列，2个操作，一个是翻转l,r区间，一个是移位使得[l,r]区间里面大于l,r的数a[x+1]=a[x]，a[l]=a[r]。然后问最后给出的m个位置的数是多少，m<=100,n<=2e5。

解法：m比较小，离线反向暴力做即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int b[maxn];
int n, q, m;
struct node{
    int t,l,r;
};
int a[maxn];
vector <node> v;

int main()
{
    scanf("%d%d%d",&n,&q,&m);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=q; i++){
        node x;
        scanf("%d %d %d", &x.t,&x.l,&x.r);
        v.push_back(x);
    }
    for(int i=1; i<=m; i++){
        int pos;
        scanf("%d", &pos);
        int sz = v.size();
        for(int j=sz-1; j>=0; j--){
            node x = v[j];
            if(x.l<=pos&&pos<=x.r){
                if(x.t==1){
                    pos = (pos==x.l)?x.r:pos-1;
                }else{
                    pos = x.r-pos+x.l;
                }
            }
        }
        printf("%d ", a[pos]);
    }
    return 0;
}

E. Turn Off The TV

题意：给出n个电视节目的播出时间，问能不能找到一个电视节目，使得去掉之后，播放电视节目的时间点不会变少。一个时间点至少有一个电视节目在播放就算做一个满足条件的时间点。

解法：典型O(1）打表计，然后维护前缀和然后check。数比较大需要离散化。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5+6;
pair <int, int> p[maxn];
vector <int> v;
int getid(int x){
    return lower_bound(v.begin(),v.end(),x) - v.begin();
}
int n;
int add[maxn], sum[maxn];

int main()
{
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d %d", &p[i].first,&p[i].second);
        p[i].first--;
        v.push_back(p[i].first);
        v.push_back(p[i].second);

    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=0; i<n; i++){
        p[i].first = getid(p[i].first);
        p[i].second = getid(p[i].second);
        ++add[p[i].first];
        --add[p[i].second];
    }
    memset(sum, 0, sizeof(sum));
    for(int i=1; i<maxn; i++){
        add[i] += add[i-1];
    }
    for(int i=0; i<maxn; i++){
        sum[i+1] = sum[i]+(add[i]>=2);
    }
    for(int i=0; i<n; i++){
        if(sum[p[i].second]-sum[p[i].first]==p[i].second-p[i].first){
            printf("%d\n", i+1);
            return 0;
        }
    }
    puts("-1");
    return 0;
}

F. Almost Permutation

题意：一个n个数的序列，但是哪个位置是什么数不能确定，但是通过给的条件，可以确定某些位置的最大和最小值。问可能的排列中最小的sigma(cnt[i]^2)。

解法：拆点最小费用最大流。把1-n个点拆成2*n个点，源点0到1-n这n个点连费用为0容量为1的边，从(1,n)到(n+1,2*n)连容量为1，费用为0的边。对于(n+1,2*n)每个点像汇点链接容量为1链接j^2-(j-1)^2的边，因为连第一条边费用为1，第二条就是3了，因为选1和2的话，费用为2^2=4。所以第二条边的费用为3，讲的比较混乱，自己还是寻找最适合的理解方式比较好。

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3FFFFFFF;
const int maxn = 305;
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[1000010];

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, q, L[maxn], R[maxn];

int main()
{
    init();
    scanf("%d %d", &n,&q);
    int st = 0, en = 2*n+1;
    for(int i=1; i<=n; i++) L[i]=1,R[i]=n;
    while(q--){
        int t,l,r,v;
        scanf("%d %d %d %d", &t,&l,&r,&v);
        if(t == 1){
            for(int i=l; i<=r; i++) L[i] = max(L[i], v);
        }else{
            for(int i=l; i<=r; i++) R[i] = min(R[i], v);
        }
    }
    for(int i=1; i<=n; i++){
        add(st, i, 1, 0);
        if(L[i]>R[i]){
            puts("-1");
            return 0;
        }
        for(int j=L[i]; j<=R[i]; j++){
            add(i, j+n, 1, 0);
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            add(n+i, en, 1, 2*j-1);
        }
    }
    int ans = solve(st, en);
    printf("%d\n", ans);
    return 0;
}

G：留坑。