【AtCoder】AGC001

桃扇骨 2021-11-01 13:42 191阅读 0赞

# AGC001 #

### A - BBQ Easy ###

从第\\(2n - 1\\)个隔一个加一下加到1即可

### B - Mysterious Light ###

在拐第二次的时候，设\\(A = N - x,B = x\\)

如果\\(B\\)小就交换A和B

这个时候相当于用A在B上走，每走A的长度用掉两个A

最后一次回到原点时会少走一个A距离

### C - Shorten Diameter ###

枚举中心点使得直径不大于某个偶数

枚举两个相邻点作为奇数直径的两个中心，使得直径不大于某个奇数

#include <bits/stdc++.h>
    #define fi first
    #define se second
    #define pii pair<int,int>
    #define mp make_pair
    #define pb push_back
    #define space putchar(' ')
    #define enter putchar('\n')
    #define eps 1e-10
    #define MAXN 2005
    #define MOD 99994711
    #define ba 47
    //#define ivorysi
    using namespace std;
    typedef long long int64;
    typedef unsigned int u32;
    typedef double db;
    template<class T>
    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<class T>
    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 N,sumE,head[MAXN],dep[MAXN],K,fa[MAXN],ans,cnt[MAXN];
    vector<pii > Ed;
    void add(int u,int v) {
        E[++sumE].to = v;
        E[sumE].next = head[u];
        head[u] = sumE;
    }
    void dfs(int u) {
        cnt[dep[u]]++;
        for(int i = head[u] ; i ; i = E[i].next) {
            int v = E[i].to;
            if(v != fa[u]) {
                fa[v] = u;
                dep[v] = dep[u] + 1;
                dfs(v);
            }
        }
    }
    void Solve() {
        read(N);read(K);
        int a,b;
        for(int i = 1 ; i < N ; ++i) {
            read(a);read(b);
            add(a,b);add(b,a);
            Ed.pb(mp(a,b));
        }
        int ans = N;
        for(int i = 1 ; i <= N ; ++i) {
            int u = i;
            fa[u] = 0;dep[u] = 0;
            memset(cnt,0,sizeof(cnt));
            dfs(u);
            int res = 0;
            for(int j = K / 2 + 1 ; j <= N ; ++j) res += cnt[j];
            ans = min(ans,res);
        }
        if(K % 2 == 0) --K;
        for(auto t : Ed) {
            fa[t.fi] = t.se;fa[t.se] = t.fi;dep[t.fi] = dep[t.se] = 0;
            memset(cnt,0,sizeof(cnt));
            dfs(t.fi);dfs(t.se);
            int res = 0;
            for(int i = K / 2 + 1 ; i <= N ; ++i) res += cnt[i];
            ans = min(ans,res);
        }
        out(ans);enter;
    }
    
    int main() {
    #ifdef ivorysi
        freopen("f1.in","r",stdin);
    #endif
        Solve();
        return 0;
    }

### D - Arrays and Palindrome ###

硬核构造。。。

奇数段只能放在最前或最后，如果超过两个就不合法

否则构造出第一段-1，第2到M-1段一样，第M段+1的b即可

#include <bits/stdc++.h>
    #define fi first
    #define se second
    #define pii pair<int,int>
    #define mp make_pair
    #define pb push_back
    #define space putchar(' ')
    #define enter putchar('\n')
    #define eps 1e-10
    #define MAXN 2005
    #define MOD 99994711
    #define ba 47
    //define ivorysi
    using namespace std;
    typedef long long int64;
    typedef unsigned int u32;
    typedef double db;
    template<class T>
    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<class T>
    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[105];
    vector<int> v,ans[2];
    void Solve() {
        read(N);read(M);
        for(int i = 1 ; i <= M ; ++i) read(a[i]);
        for(int i = 1 ; i <= M ; ++i) {
        if(a[i] & 1) v.pb(a[i]);
        }
        if(v.size() > 2) {puts("Impossible");return;}
        if(v.size()) {
        int t = v.back();
        ans[0].pb(t);
        v.pop_back();
        }
        for(int i = 1 ; i <= M ; ++i) {
        if(a[i] % 2 == 0) {
            ans[0].pb(a[i]);
        }
        }
        if(v.size()) {
        int t = v.back();
        ans[0].pb(t);
        v.pop_back();
        }
        
        for(int i = 0 ; i < ans[0].size() ; ++i) {
        if(i == 0) {
            if(ans[0][i] != 1) ans[1].pb(ans[0][i] - 1);
        }
        else if(i == ans[0].size() - 1){
            ans[1].pb(ans[0][i] + 1);
        }
        else ans[1].pb(ans[0][i]);
        }
        if(ans[0].size() == 1) ans[1].pb(1);
        for(auto t : ans[0]) {
        out(t);space;
        
        }
        enter;
        out(ans[1].size());enter;
        for(auto t : ans[1]) {
        out(t);space;
        }
        enter;
    }
    
    int main() {
    #ifdef ivorysi
        freopen("f1.in","r",stdin);
    #endif
        Solve();
        return 0;
    }

### E - BBQ Hard ###

实际上就是匹配两个点就是从\\((-A\_\{i\},-B\_\{i\})\\)走到\\((A\_\{j\},B\_\{j\})\\)

我们把所有\\((-A\_\{i\},-B\_\{i\})\\)设成1，然后dp到所有\\((A\_\{i\},A\_\{i\})\\)的方案数

最后去重只要减掉自己到自己的方案数再除二即可

#include <bits/stdc++.h>
    #define fi first
    #define se second
    #define pii pair<int,int>
    #define mp make_pair
    #define pb push_back
    #define space putchar(' ')
    #define enter putchar('\n')
    #define eps 1e-10
    #define MAXN 200005
    #define ba 47
    //#define ivorysi
    using namespace std;
    typedef long long int64;
    typedef unsigned int u32;
    typedef double db;
    template<class T>
    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<class T>
    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,V = 2000;
    int A[MAXN],B[MAXN],dp[4005][4005];
    int fac[100005],invfac[100005];
    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;
    }
    void update(int &x,int y) {
        x = inc(x,y);
    }
    int C(int n,int m) {
        if(n < m) return 0;
        return mul(fac[n],mul(invfac[m],invfac[n - m]));
    }
    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;
    }
    void Solve() {
        read(N);
        for(int i = 1 ; i <= N ; ++i) {read(A[i]);read(B[i]);dp[V - A[i]][V - B[i]]++;}
        fac[0] = 1;
        for(int i = 1 ; i <= 100000 ; ++i) fac[i] = mul(fac[i - 1],i);
        invfac[100000] = fpow(fac[100000],MOD - 2);
        for(int i = 99999 ; i >= 0 ; --i) invfac[i] = mul(invfac[i + 1],i + 1);
        for(int i = 0 ; i <= 2 * V ; ++i) {
        for(int j = 0 ; j <= 2 * V ; ++j) {
            if(!dp[i][j]) continue;
            update(dp[i + 1][j],dp[i][j]);
            update(dp[i][j + 1],dp[i][j]);
        }
        }
        int ans = 0;
        for(int i = 1 ; i <= N ; ++i) {
        update(ans,dp[V + A[i]][V + B[i]]);
        update(ans,MOD - C(2 * (A[i] + B[i]),2 * A[i]));
        }
        ans = mul(ans,(MOD + 1) / 2);
        out(ans);enter;
    }
    
    int main() {
    #ifdef ivorysi
        freopen("f1.in","r",stdin);
    #endif
        Solve();
        return 0;
    }

### F - Wide Swap ###

建出一个反排列使得\\(q\_\{p\_\{i\}\} = i\\)

我们就是尽可能的把1往前移，然后再把2尽可能的往前移

这个反排列相当于交换相邻的两个数，然后要求这相临两个数差值大于等于K

而某一个数在它之前且差值小于K的，是无法被越过的

这个关系有传递性，我们只需要在排在这个数后面的数中，小于这个数差值不小于K的连一个最近的，大于这个数差值不小于K连一个最近的，表示这个数必须在这些数的前面

这样的话每次取一个最小值做拓扑排序即可

#include <bits/stdc++.h>
    #define fi first
    #define se second
    #define pii pair<int,int>
    #define mp make_pair
    #define pb push_back
    #define space putchar(' ')
    #define enter putchar('\n')
    #define eps 1e-10
    #define MAXN 500005
    #define ba 47
    //#define ivorysi
    using namespace std;
    typedef long long int64;
    typedef unsigned int u32;
    typedef double db;
    template<class T>
    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<class T>
    void out(T x) {
        if(x < 0) {x = -x;putchar('-');}
        if(x >= 10) {
        out(x / 10);
        }
        putchar('0' + x % 10);
    }
    int N,K,q[MAXN],deg[MAXN],ans[MAXN];
    vector<int> to[MAXN];
    struct node {
        int v,l,r;
    }tr[MAXN * 4];
    void update(int u) {
        tr[u].v = min(tr[u << 1].v,tr[u << 1 | 1].v);
    }
    void build(int u,int l,int r) {
        tr[u].l = l;tr[u].r = r;tr[u].v = N + 1;
        if(l == r) return; 
        int mid = (l + r) >> 1;
        build(u << 1,l,mid);
        build(u << 1 | 1,mid + 1,r);
        update(u);
    }
    void add(int u,int x,int v) {
        if(tr[u].l == tr[u].r) {tr[u].v = v;return;}
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(x <= mid) add(u << 1,x,v);
        else add(u << 1 | 1,x,v);
        update(u);
    }
    int Query(int u,int l,int r) {
        l = max(l,1);r = min(r,N);
        if(r < l) return N + 1;
        if(l == tr[u].l && r == tr[u].r) return tr[u].v;
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(r <= mid) return Query(u << 1,l,r);
        else if(l > mid) return Query(u << 1 | 1,l,r);
        else return min(Query(u << 1,l,mid),Query(u << 1 | 1,mid + 1,r));
    }
    set<int> S;
    void Solve() {
        read(N);read(K);
        int a = 0;
        build(1,1,N);
        for(int i = 1 ; i <= N ; ++i) {
        read(a);q[a] = i;
        }
        for(int i = N ; i >= 1 ; --i) {
        int r = Query(1,q[i] + 1,q[i] + K - 1);
        if(r != N + 1) {
            to[q[i]].pb(q[r]);
            ++deg[q[r]];
        }
        int l = Query(1,q[i] - K + 1,q[i] - 1);
        if(l != N + 1) {
            to[q[i]].pb(q[l]);
            ++deg[q[l]];
        }
        add(1,q[i],i);
        }
        for(int i = 1 ; i <= N ; ++i) {
        if(!deg[i]) S.insert(i);
        }
        int cnt = 0;
        while(S.size()) {
        int u =  *S.begin();
        S.erase(S.begin());
        ans[u] = ++cnt;
        for(auto v : to[u]) {
            if(!(--deg[v])) {
            S.insert(v);
            }
        }
        }
        for(int i = 1 ; i <= N ; ++i) {
        out(ans[i]);enter;
        }
    }
    
    int main() {
    #ifdef ivorysi
        freopen("f1.in","r",stdin);
    #endif
        Solve();
        return 0;
    }

转载于:https://www.cnblogs.com/ivorysi/p/10917266.html