2018 AICCSA Programming Contest

2018 AICCSA Programming Contest

A Tree Game

B Rectangles

思路:如果存在大于0的交面积的话, 那么肯定能找到一条水平的直线 和 一条垂直的直线,

使得水平直线的左右两边点的个数相等且为n, 垂直直线的左右两边点的个数相等且为n

也就是说不能有点在这两条线上, 否则交面积为0

然后左上角的点和右下角的点配对, 左下角的点和右上角的点配对

代码:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head

const int N = 2e5 + 5, M = 1e5 + 5;
const int MOD = 1e9 + 7;
pii a[N];
int fac[M];
bool cmp(pii a, pii b) {
    return a.se < b.se;
}
void init() {
    fac[0] = 1;
    for (int i = 1; i < M; i++) fac[i] = (1LL * fac[i-1] * i) % MOD;
}
int main() {
    int T, n;
    init();
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for (int i = 1; i <= 2*n; i++) scanf("%d %d", &a[i].fi, &a[i].se);
        bool f = false;
        sort(a+1, a+1+2*n);
        double x = 0, y = 0;
        if(a[n].fi != a[n+1].fi) x = (a[n].fi + a[n+1].fi) / 2.0;
        else f = true;

        sort(a+1, a+1+2*n, cmp);
        if(a[n].se != a[n+1].se) y = (a[n].se + a[n+1].se) / 2.0;
        else f = true;
        int cnt = 0;
        for (int i = 1; i <= 2*n; i++) if(a[i].fi > x && a[i].se > y) cnt++;
        if(f) printf("0
");
        else printf("%lld
", (1LL * fac[cnt] * fac[n-cnt]) % MOD);
    }
    return 0;
}
View Code

C Function

思路:打表找规律, 发现ai的系数为C(n+1, i) - 1

代码:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head

const int N = 1e6 + 10;
const int MOD = 1e9 + 7;
int a[N];
LL fac[N], inv[N];
LL q_pow(LL n, LL k) {
    LL ans = 1;
    while(k) {
        if(k&1) ans = (ans * n) % MOD;
        n = (n * n) % MOD;
        k >>= 1; 
    }
    return ans;
}
void init() {
    fac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = fac[i-1] * i % MOD;
    inv[N-1] = q_pow(fac[N-1], MOD-2);
    for (int i = N-2; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % MOD; 
}
LL C(int n, int m) {
    return fac[n] * inv[m] % MOD * inv[n-m] % MOD;
}
int main() {
    int T;
    init();
    scanf("%d", &T);
    while(T--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        LL ans = 0;
        for (int i = 1; i <= n; i++) {
            (ans = ans + (C(n+1, i) - 1) * a[i] % MOD) %= MOD;
        } 
        printf("%lld
", (ans + MOD) % MOD);
    }
    return 0;
}
View Code

D Two Sequences

思路:将a数组放到集合里, 方便查找删除

代码:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head

const int N = 1e5 + 100;
int a[N], b[N];
multiset<int> s;
vector<int> vc;
int main() {
    int T, n, k;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n, &k);
        s.clear();
        vc.clear();
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]), s.insert(a[i]);
        for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
        for (int i = 1; i <= n; i++) {
            multiset<int>:: iterator it = s.lower_bound(b[i]);
            if(it == s.end() || *it != b[i]) {
                vc.pb(b[i]);
            }
            else s.erase(it);
        }
        if((int)vc.size() == 0) puts("YES");
        else if((int)vc.size() == 1) {
            if(*s.begin() - k <= vc[0] && vc[0] <= *s.begin() + k) puts("YES");
            else puts("NO");
        }
        else puts("NO");
    }
    return 0;
}
View Code

E Connecting Components

F Mirror

G TeddyBearsDay

思路:对于每个点, 它连向父亲的边只有当它的子树中不能自销的多余部分才会用到

代码:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head

const int N = 1e4 + 5;
vector<pii> g[N];
int send[N], rev[N];
LL ans = 0;

pii dfs(int u, int o, int w) {
    pii tmp = {send[u], rev[u]};
    for (pii p : g[u]) {
        if(p.fi != o) {
             pii pp = dfs(p.fi, u, p.se);
             tmp.fi += pp.fi;
             tmp.se += pp.se;
        }
    }
    ans += 1LL * abs(tmp.fi - tmp.se) * w;
    return tmp;
}
int main() {
    int T, n, u, v, w, q;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) g[i].clear(), send[i] = rev[i] = 0;
        for (int i = 1; i < n; i++) {
            scanf("%d %d %d", &u, &v, &w);
            g[u].pb({v, w});
            g[v].pb({u, w});
        } 
        scanf("%d", &q);
        while(q--) {
            scanf("%d %d", &u, &v);
            send[u]++;
            rev[v]++;
        }
        ans = 0;
        dfs(1, 1, 0);
        printf("%lld
", ans);
    }
    return 0;
}
View Code

H Win Strategy

思路:背包dp变形

代码:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head

const int N = 1e3 + 5;
pii a[N];
int dp[N]; 
int main() {
    int T, n, L;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n, &L);
        for (int i = 1; i <= n; i++) scanf("%d %d", &a[i].fi, &a[i].se);
        for (int i = 0; i <= L; i++) dp[i] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = L; j >= a[i].se; j--) {
                if(j-a[i].se + 1 >= a[i].fi) dp[j] = max(dp[j], dp[j-a[i].se] + 1);
            }
        }
        printf("%d
", dp[L]);
    }
    return 0;
}
View Code

I Tours

思路:二分答案, check时对于每辆bus, 如果它上一天是空闲的, 才能填补今天的空缺, 然后今天原本的车就是昨天需要的车, 不够的拿昨天剩余的补

代码:

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head

const int N = 1e5 + 5;
vector<int> a[N];
int T, m, n, r, t, tmp[N];
bool check(int x) {
    int pre = 0;
    for (int i = 1; i <= n; i++) {
        if(i == 1) {
            int tot = 0;
            for (int j = 1; j <= m; j++) {
                tmp[j] = (a[j][i] + r - 1) / r;
                tot += tmp[j];
            }
            if(tot > x) return false;
            pre = x - tot;
        }
        else {
            int tot = 0;
            for (int j = 1; j <= m; j++) {
                if(tmp[j] >= (a[j][i] + r - 1) / r) tmp[j] = (a[j][i] + r - 1) / r;
                else {
                    if(pre >= (a[j][i] + r - 1) / r - tmp[j]) pre -= (a[j][i] + r - 1) / r - tmp[j];
                    else return false;
                    tmp[j] = (a[j][i] + r - 1) / r;
                }
                tot += (a[j][i] + r - 1) / r;
            }
            if(tot > x) return false;
            pre = x - tot;
        }
    }
    return true;
}
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d %d", &m, &n, &r);
        for (int i = 1; i <= m; i++) {
            a[i].clear();
            a[i].pb(0);
            for (int j = 1; j <= n; j++) {
                scanf("%d", &t);
                a[i].pb(t);
            }
        }
        int l = 1, r = 5e5, mid = l+r >> 1;
        while(l < r) {
            if(check(mid)) r = mid;
            else l = mid+1;
            mid = l+r >> 1;
        }
        printf("%d
", mid);
    }
    return 0;
}
View Code

J Restricted Vertex Cover

思路:2-sat

建边:

对于一条mark的边,

如果其中一点在点覆盖中, 那么另外一点肯定不在点覆盖中

如果其中一点不在点覆盖中, 那么另外一点肯定在点覆盖中

对于一条unmark的边,

如果其中一点在点覆盖中, 那么另外一点不确定

如果其中一点不在点覆盖中, 那么另外一点肯定在点覆盖中

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=500000;
int ins[N],dfn[N],low[N],cnt,sta[N];
int top,v,u;
int Next[N],head[N],to[N];
int tot;
int scc[N];
int scccnt;
void make_list(int u,int v){
    Next[++tot]=head[u],head[u]=tot,to[tot]=v;
}
void tarjan(int x){
    ins[x]=dfn[x]=low[x]=++cnt,sta[top++]=x;
    for(int p=head[x],v=to[p];p;p=Next[p],v=to[p])
        if(!dfn[v])tarjan(v),low[x]=min(low[x],low[v]);
        else if(ins[v])low[x]=min(low[x],dfn[v]);
    if(low[x]==dfn[x]){
        scc[x]=++scccnt,ins[x]=0;
        while((u=sta[--top])!=x)ins[u]=0,scc[u]=scccnt;
    }
}
int main(){
    int T;
    int n,m;
    int u,v,w;
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        scanf("%d%d",&n,&m);
        memset(head,0,sizeof(int)*(n*2+5));
        memset(dfn,0,sizeof(int)*(n*2+5));
        top=0;
        tot=0;
        memset(scc,0,sizeof(int)*(n*2+5));
        memset(low,0,sizeof(int)*(n*2+5));
        scccnt=0;
        memset(ins,0,sizeof(int)*(n*2+5));
        cnt=0;
        memset(sta,0,sizeof(int)*(n*2+5));
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&u,&v,&w);
            if(w){
                make_list(u,v+n);
                make_list(v,u+n);
                make_list(u+n,v);
                make_list(v+n,u);
            }
            else{
                make_list(u+n,v);
                make_list(v+n,u);
            }
        }
        for(int i=1;i<=2*n;i++){
            if(!dfn[i])tarjan(i);
        }
        bool ok=1;
        for(int i=1;i<=n;i++){
            ok&=(scc[i]!=scc[i+n]);
        }
        if(ok)puts("YES");
        else puts("NO");
    }
    return 0; 
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/widsom/p/9987220.html