赛后都不敢vp

A.Night at the Museum

Problem：一个转轮，问你转出给定字符串所需的最少步数

Analysis：每次取正反的最小就行了

Tags：Implementation

B.Coupons and Discounts

Problem: 给定一串数列，每次可以给相邻两个数字进行-1操作或者给一个数字进行-2操作，问最终是否可以都变为0

Analysis：由于两次-1和-2其实一样，而且只需考虑左端和右端的数即可，故扫描，按0分段，每段查询是否为Sig为偶数即可

Tags：Greedy

C.Socks

Problem: 给定一个染色的图和一些点之间的关系，可以重染色使部分关系合法，问使所有关系合法的最小代价

Analysis：首先想到对于一个有关系的点集合，最小代价符合贪心的原则，即修改成该集合中拥有点数量最多的颜色即可，这样就可直接dfs过了

Tags：Greedy，Dfs and similar

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 1000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 200010
#define Maxe 400010
typedef long long ll;

vector<int > V;
int n, m, k, Head[Maxn], To[Maxe], Next[Maxe], Cnt, Col[Maxn];
int l, r, Clr[Maxn], Ans;
bool used[Maxn], Men[Maxn];

inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }

inline void dfs(int u, int father)
{
    V.push_back(u);
    for (int p=Head[u]; p!=-1; p=Next[p])
    {
        int v=To[p];
        if ((v!=father) && (!used[v]))
        {
            used[v]=1;
            dfs(v, u);
        }
    }
}

int main()
{
    read(n); read(m); read(k); Clear(Head, -1); Cnt=0;
    for (int i=1; i<=n; i++) read(Col[i]);
    for (int i=1; i<=m; i++) read(l), read(r), Insert(l, r), Insert(r, l), Men[l]=Men[r]=1;
    for (int i=1; i<=n; i++)
        if ((!used[i]) && (Men[i]))
        {
            V.clear(); used[i]=1;
            dfs(i, -1); int Max=0;
            //for (int j=0; j<V.size(); j++) printf("%d ", V[j]); puts("");
            for (int j=0; j<V.size(); j++) Clr[Col[V[j]]]++, Max=max(Max, Clr[Col[V[j]]]);
            for (int j=0; j<V.size(); j++) Clr[Col[V[j]]]--;
            //printf(" All = %d Max = %d\n", V.size(), Max);
            Ans+=(V.size()-Max);
        }
    printf("%d\n", Ans);
}

D.80-th Level Archeology

Problem: 给定n个序列和上限c，每次操作会让序列中所有的数字+1，溢出后从1开始，问几次可以使所有序列按字典序排列，若不存在输出-1

Analysis：首先若存在答案，则在[0,c]中必然存在解。其次考虑相邻两个串，找出第一个不同的位置即可，证明过程很显然，前趋同时变化，而后继的改变不影响字典序的大小，当然要注意特别的是后者是前者子串时的特殊情况（-1），之后就是统计方案集合取并即可

Tags：Brute Force，Implementation

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 1000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 1000010
#define Maxc 1000010
typedef long long ll;

struct Data
{
    int l, r;
}Queue[Maxn];
int n, c, Cnt, x[Maxn], v[2][Maxn], Escort, Res;
bool Endd;

inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }
inline bool cmp(const Data &a, const Data &b) { return (a.l<b.l) || ((a.l==b.l) && (a.r<b.r)); }
int main()
{
    read(n); read(c);
    for (int i=1; i<=n; i++)
    {
        read(x[i]);
        for (int j=1; j<=x[i]; j++) read(v[i&1][j]);
        if (i==1) continue;
        int pos=-1, Len=min(x[i], x[i-1]);
        for (int j=1; j<=Len; j++)
            if (v[i&1][j]!=v[(i-1)&1][j]) { pos=j; break; }
        if (pos==-1) if (x[i-1]>x[i]) { puts("-1"); return 0; }
        if (v[i&1][pos]<v[(i-1)&1][pos])
        {
            Queue[++Cnt].l=0, Queue[Cnt].r=c-v[(i-1)&1][pos];
            Queue[++Cnt].l=c-v[i&1][pos]+1; Queue[Cnt].r=c+1;
        }
        else
            if (v[i&1][pos]>v[(i-1)&1][pos])
                Queue[++Cnt].l=c-v[i&1][pos]+1, Queue[Cnt].r=c-v[(i-1)&1][pos];
    }
    //if (Endd) return 0;
    //for (int i=0; i<=c; i++) printf("%d ", Way[i]); puts("");
    //printf("%d\n", Way[0]);
    sort(Queue+1, Queue+Cnt+1, cmp);
    for (int i=1; i<=Cnt; i++)
    {
        if (Queue[i].l>Res) { printf("%d\n", Res); return 0; }
        else Res=max(Res, max(Queue[i].l+1, Queue[i].r+1));
    }
    if (Res<=c) printf("%d\n", Res); else puts("-1");
}

E.Funny Game

Problem：给定一串序列，两人轮流选数字，每次可以选择前n项，求和后放回，问两者得分差的最大值

Analysis: 令f[i]表示到第i个数的最大分差，f[i]=Max{Sig[j]-f[j]}，其中Sig为前缀和

Tags：Dp，Prefix sum

F.Night at the Museum

Problem: 给定一串序列，可以选定一个数x作为基底，将其他数改成比自身小的x的倍数，求修改过后的最大和

Analysis：排序，枚举x，对于一个区间[(i-1)*x,i*x-1]，该区间的贡献值为Count*(i-1)*x, 其中Count为该区间内原序列数的个数，之后前缀和维护一下Count即可

Tags:Number theory, Prefix sum

#include<cstdio>
#include<cstring>
#include<algorithm>
//#include<iostream>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
#define INF 1000000000
#define Clear(x, Num) memset(x, Num, sizeof(x))
#define Dig(x) ((x>='0') && (x<='9'))
#define Neg(x) (x=='-')
#define G_c() getchar()
#define Maxn 1000010
typedef long long ll;

int n, a[Maxn], Mx_c;
ll Sig[Maxn], Ans;
bool used[Maxn];

inline int gcd(int x, int y) { if (!y) return x; return gcd(y, x%y); }
inline void read(int &x){ char ch; int N=1; while ((ch=G_c()) && (!Dig(ch)) && (!Neg(ch))); if (Neg(ch)) { N=-1; while ((ch=G_c()) && (!Dig(ch))); } x=ch-48; while ((ch=G_c()) && (Dig(ch))) x=x*10+ch-48; x*=N; }
//inline void Insert(int u, int v) { To[Cnt]=v; Next[Cnt]=Head[u]; Head[u]=Cnt++; }

int main()
{
    read(n);
    for (int i=1; i<=n; i++) read(a[i]), Sig[a[i]]++, Mx_c=max(Mx_c, a[i]);
    sort(a+1, a+n+1);
    for (int i=1; i<=Maxn; i++) Sig[i]+=Sig[i-1];
    for (int i=1; i<=n; i++)
        if (!used[a[i]])
        {
            used[a[i]]=1; ll Tmp=0;
            for (int j=2; (j-1)*a[i]<=a[n]; j++)
            {
                int L=(j-1)*a[i], R=j*a[i]-1;
                Tmp+=(Sig[R]-Sig[L-1])*L;
            }
            Ans=max(Ans, Tmp);
        }
    printf("%lld\n", Ans);
}

总之D题写的时候基本已经没什么状态了、连着WA了N发，AB也各犯了一个zz错误，总之当时比赛的时候肯定会被吊起来打，心痛自己的状态（不到）一秒钟