【AtCoder】ARC103-白红宇

【AtCoder】ARC103

阅读量：5337 次

发布时间：2019-06-15

本文共 7802 字，大约阅读时间需要 26 分钟。

C -

为了防止一些多余的判断，我选择直接记录每个数的个数，然后枚举第一个数，找第一个数之外第二个数改变最少的情况下应该选什么

代码

#include 
    
     #define fi first#define se second#define pii pair
     
      #define mp make_pair#define pb push_back#define enter putchar('\n')#define space putchar(' ')//#define ivorysi#define MAXN 100005typedef long long int64;using namespace std;template
      
       void read(T &res) {    res = 0;char c = getchar();T f = 1;    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,a[MAXN];int L[MAXN],tot,ans,cnt1[MAXN],cnt2[MAXN],pre[MAXN],suf[MAXN];void Solve() {    read(N);    for(int i = 1 ; i <= N ; ++i) read(a[i]);    for(int i = 1 ; i <= N ; i += 2) {        cnt1[a[i]]++;    }    for(int i = 2 ; i <= N ; i += 2) {        cnt2[a[i]]++;    }    for(int i = 1 ; i <= 100000 ; ++i) {        pre[i] = max(pre[i - 1],cnt2[i]);    }    for(int i = 100000 ; i >= 1 ; --i) {        suf[i] = max(suf[i + 1],cnt2[i]);    }    ans = N;    for(int i = 1 ; i <= 100000 ; ++i) {        ans = min(ans,N / 2 - cnt1[i] + N / 2 - max(pre[i - 1],suf[i + 1]));    }    out(ans);enter;}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();    return 0;}

D - Robot Arms

103真是构造题大荟萃

如果所有的\(X_i + Y_i\)奇偶性不同，那么显然不行

那么我们考虑一下所有\(X_i + Y_i\)为奇数的情况

我们找一个集合\({1,2,4,8...2^k}\)他们的总和大于\(|X_i| + |Y_i|\)的最大值

我们证明一下\({1,2,4,8..2^k}\)这个集合可以达到所有\(|X_i| + |Y_i| <= 2^{k +1} - 1\)的所有\(X_i +Y_i\)和为奇数的点

首先集合中只有\(1\)的时候，我们可以达到

集合中有\({1,2}\)的时候，我们通过向上下左右移动\(2\)，是可以达到距离原点距离为\(1\)的位置的

这样递归证明，最后就是对的

代码

#include 
    
     #define fi first#define se second#define pii pair
     
      #define mp make_pair#define pb push_back#define enter putchar('\n')#define space putchar(' ')//#define ivorysi#define MAXN 100005typedef long long int64;using namespace std;template
      
       void read(T &res) {    res = 0;char c = getchar();T f = 1;    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;int M = 0;int64 op[35],sum,X[1005],Y[1005];int64 dx[] = {1,0,-1,0},dy[] = {0,-1,0,1};char s[1005][45];const char *dir = "RDLU";void Solve() {    read(N);    for(int i = 1 ; i <= N ; ++i) {        read(X[i]);read(Y[i]);    }    for(int i = 2 ; i <= N ; ++i) {        if((abs(X[i]) + abs(Y[i])) % 2 != (abs(X[1]) + abs(Y[1])) % 2)  {            puts("-1");return ;        }    }    bool flag = 0;    flag = ((abs(X[1]) + abs(Y[1])) % 2 == 0);    if(flag) {op[++M] = 1;}    for(int i = 30 ; i >= 0 ; --i) {op[++M] = 1 << i;sum += op[M];}    pii st = mp(0,0);    if(flag) st = mp(1,0);    for(int i = 1 ; i <= N ; ++i) {        if(flag) s[i][1] = 'R';        pii p = st;        int64 tmp = sum;        for(int j = flag ? 2 : 1 ; j <= M ; ++j) {            for(int k = 0 ; k <= 3 ; ++k) {                int64 tx = p.fi + dx[k] * op[j],ty = p.se + dy[k] * op[j];                int64 a = abs(tx - X[i]) + abs(ty - Y[i]);                if(a <= tmp - op[j]) {                    tmp -= op[j];                    s[i][j] = dir[k];                    p = mp(tx,ty);                    break;                }            }        }    }    out(M);enter;    for(int i = 1 ; i <= M ; ++i) {        out(op[i]);space;    }    enter;    for(int i = 1 ; i <= N ; ++i) {        for(int j = 1 ; j <= M ; ++j) {            putchar(s[i][j]);        }        enter;    }}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();}

E - Tr/ee

很容易发现1必须合法

我们想要某个大小的树可以被割出来

用一种节约节点的方式，可以用上一个可以拼出来的树，接上一个根，不足的用大小为1的叶子作为补充

然后只要拼到n / 2，再直接加叶子拼到n即可

代码

#include 
    
     #define fi first#define se second#define pii pair
     
      #define mp make_pair#define pb push_back#define enter putchar('\n')#define space putchar(' ')//#define ivorysi#define MAXN 100005typedef long long int64;using namespace std;template
      
       void read(T &res) {    res = 0;char c = getchar();T f = 1;    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,dp[100005];char s[100005];void add(int u,int v) {    out(u);space;out(v);enter;}void Solve() {    scanf("%s",s + 1);    N = strlen(s + 1);    for(int i = 1 ; i <= N ; ++i) dp[i] = s[i] - '0';    if(!dp[1] || dp[N]) {puts("-1");return;}    for(int i = 2 ; i <= N - 1 ; ++i) {        if(dp[i]) {            if(!dp[N - i]) {puts("-1");return;}        }    }    int p = 1,rt = 1;    for(int i = 2 ; i <= N / 2 ; ++i) {        if(dp[i]) {            add(rt,++p);rt = p;            while(p < i) {add(rt,++p);}        }    }    add(rt,++p);rt = p;    while(p < N) {add(rt,++p);}}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();}

F - Distance Sums

Di最大的点一定是一个叶子，我们找到Di - (n - 2)的点是连向它的点

然后以此类推，我们可以一边从大到小枚举D来算父亲边，同时维护每个点的子树大小

但是这必要但不充分，我们可以构造这棵树出来时候重新算一遍D值来检验

#include 
    
     #define fi first#define se second#define pii pair
     
      #define mp make_pair#define pb push_back#define enter putchar('\n')#define space putchar(' ')//#define ivorysi#define MAXN 100005typedef long long int64;using namespace std;template
      
       void read(T &res) {    res = 0;char c = getchar();T f = 1;    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 D[MAXN],L[MAXN],dep[MAXN],C[MAXN];int id[MAXN],s[MAXN],t[MAXN],tot,siz[MAXN]; struct node {    int to,next;}E[MAXN * 2];int head[MAXN],sumE;void add(int u,int v) {    E[++sumE].to = v;    E[sumE].next = head[u];    head[u] = sumE;}bool cmp(int a,int b) {    return D[a] < D[b];}void dfs(int u,int fa) {    siz[u] = 1;    for(int i = head[u] ; i ; i = E[i].next) {        int v = E[i].to;        if(v != fa){            dep[v] = dep[u] + 1;            dfs(v,u);            siz[u] += siz[v];        }    }}bool dfs1(int u,int fa) {    if(C[u] != D[u]) return false;    for(int i = head[u] ; i ; i = E[i].next) {        int v = E[i].to;        if(v != fa) {            C[v] = C[u] - siz[v] + N - siz[v];            if(!dfs1(v,u)) return false;        }    }    return true;}void Solve() {    read(N);    for(int i = 1 ; i <= N ; ++i) {        read(D[i]);id[i] = i;siz[i] = 1;    }    sort(id + 1,id + N + 1,cmp);    for(int i = 1 ; i <= N ; ++i) L[i] = D[id[i]];    for(int i = N ; i > 1 ; --i) {        s[++tot] = id[i];        int p = lower_bound(L + 1,L + i,L[i] + 2 * siz[s[tot]] - N) - L;        if(L[p] != L[i] + 2 * siz[s[tot]] - N) {puts("-1");return;}        t[tot] = id[p];        siz[id[p]] += siz[id[i]];    }    for(int i = 1 ; i <= tot ; ++i) {add(s[i],t[i]);add(t[i],s[i]);}    dfs(1,0);    for(int i = 1 ; i <= N ; ++i) C[1] += dep[i];    if(!dfs1(1,0)) {puts("-1");return;}    for(int i = 1 ; i <= tot ; ++i) {        out(s[i]);space;out(t[i]);enter;    }}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();    return 0;}