AGC032

A - Limited Insertion

这题就是从后面找一个最靠后而且当前可以放的，可以放的条件是它的前面正好放了它的数值-1个数

如果不符合条件就退出

#include 
    
     #define fi first#define se second#define pii pair
     
      #define mp make_pair#define pb push_back#define space putchar(' ')#define enter putchar('\n')#define eps 1e-10#define MAXN 200005//#define ivorysiusing namespace std;typedef long long int64;typedef unsigned int u32;typedef double db;template
      
       void read(T &res) {    res = 0;T f = 1;char c = getchar();    while(c < '0' || c > '9') {        if(c == '-') f = -1;        c = getchar();    }    while(c >= '0' && c <= '9') {        res = res * 10 +c - '0';        c = getchar();    }    res *= f;}template
       
        void out(T x) {    if(x < 0) {x = -x;putchar('-');}    if(x >= 10) {        out(x / 10);    }    putchar('0' + x % 10);}int a[MAXN],N,cnt[MAXN];bool vis[MAXN];void Solve() {    read(N);    for(int i = 1 ; i <= N ; ++i) read(a[i]);    for(int i = 1 ; i <= N ; ++i) {        int cnt = 0;        for(int j = 1 ; j < i ; ++j) {            if(a[j] <= a[i]) ++cnt;        }        if(cnt + 1 < a[i]) {puts("-1");return;}    }    for(int i = 1 ; i <= N ; ++i) {        cnt[0] = 0;        for(int j = 1 ; j <= N ; ++j) cnt[j] = cnt[j - 1] + vis[j];        for(int j = N ; j >= 1 ; --j) {            if(!vis[j] && cnt[j - 1] + 1 == a[j]) {                vis[j] = 1;                out(a[j]);enter;                break;            }        }    }}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();    return 0;}
       
      
     
    

B - Balanced Neighbors

如果是偶数个，分成和相等的\(\frac{N}{2}\)份

如果是奇数个，最后一个点单独为一组，前\(N - 1\)个两个一组分成和相等的\(\frac{N - 1}{2}\)份

然后把一组作为一个点，建一个完全图，两组(一组1,2，一组3,4)之间连边就是

1-2,1-4,2-3,2-4

#include 
    
     #define fi first#define se second#define pii pair
     
      #define mp make_pair#define pb push_back#define space putchar(' ')#define enter putchar('\n')#define eps 1e-10#define MAXN 200005//#define ivorysiusing namespace std;typedef long long int64;typedef unsigned int u32;typedef double db;template
      
       void read(T &res) {    res = 0;T f = 1;char c = getchar();    while(c < '0' || c > '9') {        if(c == '-') f = -1;        c = getchar();    }    while(c >= '0' && c <= '9') {        res = res * 10 +c - '0';        c = getchar();    }    res *= f;}template
       
        void out(T x) {    if(x < 0) {x = -x;putchar('-');}    if(x >= 10) {        out(x / 10);    }    putchar('0' + x % 10);}int N;vector
        
          v;void Solve() {    read(N);    if(N & 1) {        for(int i = 1 ; i < N ; ++i) {            v.pb(mp(i,N));        }        --N;    }    for(int i = 1 ; i <= N ; ++i) {        for(int j = i + 1 ; j <= N ; ++j) {            if(i + j != N + 1) v.pb(mp(i,j));        }    }    out(v.size());enter;    for(auto t : v) {        out(t.fi);space;out(t.se);enter;    }}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();    return 0;}
        
       
      
     
    

C - Three Circuits

必定存在一个欧拉回路

如果一个点有六个或以上点度必定存在

如果有三个点以上有四个点度必定存在

如果只有两个点有四个点度

那么如果这四条路都在这两个点之间，那么就无解

否则有解

#include 
    
     #define fi first#define se second#define pii pair
     
      #define mp make_pair#define pb push_back#define space putchar(' ')#define enter putchar('\n')#define eps 1e-10#define MAXN 100005//#define ivorysiusing namespace std;typedef long long int64;typedef unsigned int u32;typedef double db;template
      
       void read(T &res) {    res = 0;T f = 1;char c = getchar();    while(c < '0' || c > '9') {        if(c == '-') f = -1;        c = getchar();    }    while(c >= '0' && c <= '9') {        res = res * 10 +c - '0';        c = getchar();    }    res *= f;}template
       
        void out(T x) {    if(x < 0) {x = -x;putchar('-');}    if(x >= 10) {        out(x / 10);    }    putchar('0' + x % 10);}struct node {    int to,next;}E[MAXN * 2];int head[MAXN],sumE;int N,M;int cnt[MAXN];bool vis[MAXN];void add(int u,int v) {    E[++sumE].to = v;    E[sumE].next = head[u];    head[u] = sumE;}void dfs(int u) {    vis[u] = 1;    for(int i = head[u] ; i ; i = E[i].next) {        int v = E[i].to;        if(!vis[v]) dfs(v);    }}void Solve() {    read(N);read(M);    int a,b;    for(int i = 1 ; i <= M ; ++i) {        read(a);read(b);        cnt[a]++;cnt[b]++;        add(a,b);add(b,a);    }    for(int i = 1 ; i <= N ; ++i) {        if(cnt[i] & 1) {puts("No");return;}    }    int t = 0;    int p = 0,q = 0;    for(int i = 1 ; i <= N ; ++i) {        if(cnt[i] >= 6) {puts("Yes");return;}        if(cnt[i] >= 4) {            ++t;            if(!p) p = i;            else if(!q) q = i;        }    }    if(t > 2) {puts("Yes");return;}    if(t == 2) {        vis[p] = 1;        dfs(q);        for(int i = 1 ; i <= N ; ++i) {            if(!vis[i]) {puts("Yes");return;}        }    }    puts("No");}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();    return 0;}
       
      
     
    

D - Rotation Sort

把操作改成数轴上，我可以把一个点移动到左边或右边任意一个位置上，可以不必要是整数点

显然对于每个点操作只进行一次

然后拆成\((-\infty,1),(1,2),(2,3),(3,4)....(N - 1,N),(N,+\infty)\)和整数点\(1,2,3,4,5,6..N\)

然后根据位置dp即可

#include 
    
     #define fi first#define se second#define pii pair
     
      #define mp make_pair#define pb push_back#define space putchar(' ')#define enter putchar('\n')#define eps 1e-10#define MAXN 5005//#define ivorysiusing namespace std;typedef long long int64;typedef unsigned int u32;typedef double db;template
      
       void read(T &res) {    res = 0;T f = 1;char c = getchar();    while(c < '0' || c > '9') {        if(c == '-') f = -1;        c = getchar();    }    while(c >= '0' && c <= '9') {        res = res * 10 +c - '0';        c = getchar();    }    res *= f;}template
       
        void out(T x) {    if(x < 0) {x = -x;putchar('-');}    if(x >= 10) {        out(x / 10);    }    putchar('0' + x % 10);}int N;int64 A,B;int64 dp[MAXN][2 * MAXN],s[MAXN][2 * MAXN];int p[MAXN],pos[MAXN];void Solve() {    read(N);read(A);read(B);    for(int i = 1 ; i <= N ; ++i) {read(p[i]);pos[p[i]] = i;}    for(int i = 1 ; i <= N ; ++i) {        s[i][0] = 1e18;        for(int j = 1 ; j <= 2 * N + 1 ; ++j) {            if(j & 1) {                dp[i][j] = s[i - 1][j] + (j < pos[i] * 2 ? B : A);            }            else {                dp[i][j] = s[i - 1][j - 1] + (j != pos[i] * 2 ? (j < pos[i] * 2 ? B : A): 0);            }            s[i][j] = min(s[i][j - 1],dp[i][j]);        }    }    out(s[N][2 * N + 1]);enter;}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();    return 0;}
       
      
     
    

E - Modulo Pairing

用蓝色表示相加小于M的，红色表示大于M的

然后就会变成前面是蓝的，后面是红的

简单分析发现蓝的越小越好，红的越大越好，所以求出能向左最长的红色序列

#include 
    
     #define fi first#define se second#define pii pair
     
      #define mp make_pair#define pb push_back#define space putchar(' ')#define enter putchar('\n')#define eps 1e-10#define MAXN 200005//#define ivorysiusing namespace std;typedef long long int64;typedef unsigned int u32;typedef double db;template
      
       void read(T &res) {    res = 0;T f = 1;char c = getchar();    while(c < '0' || c > '9') {        if(c == '-') f = -1;        c = getchar();    }    while(c >= '0' && c <= '9') {        res = res * 10 +c - '0';        c = getchar();    }    res *= f;}template
       
        void out(T x) {    if(x < 0) {x = -x;putchar('-');}    if(x >= 10) {        out(x / 10);    }    putchar('0' + x % 10);}int N,M;int a[MAXN];void Solve() {    read(N);read(M);    for(int i = 1 ; i <= 2 * N ; ++i) read(a[i]);    sort(a + 1,a + 2 * N + 1);    int r = -1;    for(int i = 2 * N ; i >= 1 ; --i) {        int t = lower_bound(a + 1,a + 2 * N + 1,M - a[i]) - a;        if((t & 1) == (i & 1)) ++t;        if(r == -1) r = i + t;        else r = max(r,i + t);    }    if(r == -1) r = 4 * N + 1;    int ans = 0;    for(int i = 2 * N ; i >= 1 ; --i) {        if(r - i < i) ans = max(ans,(a[i] + a[r - i]) % M);        else break;    }    r = 1 + r - 2 * N - 1;    for(int i = 1 ; i <= 2 * N ; ++i) {        if(i < r - i) ans = max(ans,a[i] + a[r - i]);        else break;    }    out(ans);enter;}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();    return 0;}
       
      
     
    

F - One Third

切一刀，画一条红线，然后正120画一条蓝线，反120画一条绿线

我们要求的就是任意1/3中最短两个颜色不同之间的线的角度大小

然后我们取第一刀红线和蓝线之间的 1/3区间，然后里面被分成了\(N\)份，我们递推一个\(f(i)\)，表示有\(i\)份左右两边区间颜色不同的概率

然后\(g(i)\)表示\(i\)份中最短的一段的期望长度，\(\frac{1}{3}\)长度里\(N\)份中选\(i\)份期望长度是\(\frac{i}{3N}\)，可以认为分成\(N\)份中选\(i\)份每个点被选中的概率是\(\frac{i}{N} = \frac{\binom{i - 1}{N - 1}}{\binom{i}{N}}\)

那\(i\)段中的期望最小长度呢

是\(E(min) = \int_{t = 0}^{1/i}P(min \geq t) dt = \int_{t = 0}^{1/i}(1 - it)^{i - 1}dt = \int_{t = 0}^{1}\frac{t^{i - 1}}{i} dt = \frac{1}{i^2}\)

所以\(g(i) = \frac{1}{3iN}\)

答案就是所有的\(f(i)g(i)\)的和

#include 
    
     #define fi first#define se second#define pii pair
     
      #define mp make_pair#define pb push_back#define space putchar(' ')#define enter putchar('\n')#define eps 1e-10#define MAXN 1000005//#define ivorysiusing namespace std;typedef long long int64;typedef unsigned int u32;typedef double db;template
      
       void read(T &res) {    res = 0;T f = 1;char c = getchar();    while(c < '0' || c > '9') {    if(c == '-') f = -1;    c = getchar();    }    while(c >= '0' && c <= '9') {    res = res * 10 +c - '0';    c = getchar();    }    res *= f;}template
       
        void out(T x) {    if(x < 0) {x = -x;putchar('-');}    if(x >= 10) {    out(x / 10);    }    putchar('0' + x % 10);}const int MOD = 1000000007;int N;int f[MAXN][3],g[MAXN],fac[MAXN],invfac[MAXN],inv[MAXN];int inc(int a,int b) {    return a + b >= MOD ? a + b - MOD : a + b;}int mul(int a,int b) {    return 1LL * a  * b % MOD;}int fpow(int x,int c) {    int res = 1,t = x;    while(c) {    if(c & 1) res = mul(res,t);    t = mul(t,t);    c >>= 1;    }    return res;}int C(int n,int m) {    if(n < m) return 0;    return mul(fac[n],mul(invfac[m],invfac[n - m]));}void Solve() {    read(N);    fac[0] = 1;    for(int i = 1 ; i <= N; ++i) fac[i] = mul(fac[i - 1],i);    invfac[N] = fpow(fac[N],MOD - 2);    for(int i = N - 1 ; i >= 0 ; --i) invfac[i] = mul(invfac[i + 1],i + 1);    inv[1] = 1;    for(int i = 2 ; i <= 1000000 ; ++i) inv[i] = mul(inv[MOD % i],MOD - MOD / i);    f[0][0] = 1;    int iv3= fpow(inv[3],N - 1);    int ans = 0;    for(int i = 1 ; i <= N ; ++i) {    f[i][1] = inc(f[i - 1][0],f[i - 1][2]);    f[i][0] = inc(f[i - 1][1],f[i - 1][2]);    f[i][2] = inc(f[i - 1][0],f[i - 1][1]);    g[i] = mul(mul(inv[3],inv[N]),inv[i]);    int p = mul(mul(f[i][1],C(N,i)),iv3);    ans = inc(ans,mul(g[i],p));    }    out(ans);enter;}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();}