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 + , M = 1e5 + ;

const int MOD = 1e9 + ;

pii a[N];

int fac[M];

bool cmp(pii a, pii b) {

    return a.se < b.se;

}

void init() {

    fac[] = ;

    for (int i = ; i < M; i++) fac[i] = (1LL * fac[i-] * i) % MOD;

}

int main() {

    int T, n;

    init();

    scanf("%d", &T);

    while(T--) {

        scanf("%d", &n);

        for (int i = ; i <= *n; i++) scanf("%d %d", &a[i].fi, &a[i].se);

        bool f = false;

        sort(a+, a++*n);

        double x = , y = ;

        if(a[n].fi != a[n+].fi) x = (a[n].fi + a[n+].fi) / 2.0;

        else f = true;

        sort(a+, a++*n, cmp);

        if(a[n].se != a[n+].se) y = (a[n].se + a[n+].se) / 2.0;

        else f = true;

        int cnt = ;

        for (int i = ; i <= *n; i++) if(a[i].fi > x && a[i].se > y) cnt++;

        if(f) printf("0\n");

        else printf("%lld\n", (1LL * fac[cnt] * fac[n-cnt]) % MOD);

    }

    return ;

}

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 + ;

const int MOD = 1e9 + ;

int a[N];

LL fac[N], inv[N];

LL q_pow(LL n, LL k) {

    LL ans = ;

    while(k) {

        if(k&) ans = (ans * n) % MOD;

        n = (n * n) % MOD;

        k >>= ;

    }

    return ans;

}

void init() {

    fac[] = ;

    for (int i = ; i < N; i++) fac[i] = fac[i-] * i % MOD;

    inv[N-] = q_pow(fac[N-], MOD-);

    for (int i = N-; i >= ; i--) inv[i] = inv[i+] * (i+) % 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 = ; i <= n; i++) scanf("%d", &a[i]);

        LL ans = ;

        for (int i = ; i <= n; i++) {

            (ans = ans + (C(n+, i) - ) * a[i] % MOD) %= MOD;

        }

        printf("%lld\n", (ans + MOD) % MOD);

    }

    return ;

}

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 + ;

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 = ; i <= n; i++) scanf("%d", &a[i]), s.insert(a[i]);

        for (int i = ; i <= n; i++) scanf("%d", &b[i]);

        for (int i = ; 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() == ) puts("YES");

        else if((int)vc.size() == ) {

            if(*s.begin() - k <= vc[] && vc[] <= *s.begin() + k) puts("YES");

            else puts("NO");

        }

        else puts("NO");

    }

    return ;

} 

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 + ;

vector<pii> g[N];

int send[N], rev[N];

LL ans = ;

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 = ; i <= n; i++) g[i].clear(), send[i] = rev[i] = ;

        for (int i = ; 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 = ;

        dfs(, , );

        printf("%lld\n", ans);

    }

    return ;

}

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 + ;

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 = ; i <= n; i++) scanf("%d %d", &a[i].fi, &a[i].se);

        for (int i = ; i <= L; i++) dp[i] = ;

        for (int i = ; i <= n; i++) {

            for (int j = L; j >= a[i].se; j--) {

                if(j-a[i].se +  >= a[i].fi) dp[j] = max(dp[j], dp[j-a[i].se] + );

            }

        }

        printf("%d\n", dp[L]);

    }

    return ;

}

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 + ;

vector<int> a[N];

int T, m, n, r, t, tmp[N];

bool check(int x) {

    int pre = ;

    for (int i = ; i <= n; i++) {

        if(i == ) {

            int tot = ;

            for (int j = ; j <= m; j++) {

                tmp[j] = (a[j][i] + r - ) / r;

                tot += tmp[j];

            }

            if(tot > x) return false;

            pre = x - tot;

        }

        else {

            int tot = ;

            for (int j = ; j <= m; j++) {

                if(tmp[j] >= (a[j][i] + r - ) / r) tmp[j] = (a[j][i] + r - ) / r;

                else {

                    if(pre >= (a[j][i] + r - ) / r - tmp[j]) pre -= (a[j][i] + r - ) / r - tmp[j];

                    else return false;

                    tmp[j] = (a[j][i] + r - ) / r;

                }

                tot += (a[j][i] + r - ) / 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 = ; i <= m; i++) {

            a[i].clear();

            a[i].pb();

            for (int j = ; j <= n; j++) {

                scanf("%d", &t);

                a[i].pb(t);

            }

        }

        int l = , r = 5e5, mid = l+r >> ;

        while(l < r) {

            if(check(mid)) r = mid;

            else l = mid+;

            mid = l+r >> ;

        }

        printf("%d\n", mid);

    }

    return ;

}

J Restricted Vertex Cover

思路:2-sat

建边:

对于一条mark的边,

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

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

对于一条unmark的边,

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

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

代码:

#include<bits/stdc++.h>

using namespace std;

const int N=;

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]=;

        while((u=sta[--top])!=x)ins[u]=,scc[u]=scccnt;

    }

}

int main(){

    int T;

    int n,m;

    int u,v,w;

    scanf("%d",&T);

    for(int t=;t<=T;t++){

        scanf("%d%d",&n,&m);

        memset(head,,sizeof(int)*(n*+));

        memset(dfn,,sizeof(int)*(n*+));

        top=;

        tot=;

        memset(scc,,sizeof(int)*(n*+));

        memset(low,,sizeof(int)*(n*+));

        scccnt=;

        memset(ins,,sizeof(int)*(n*+));

        cnt=;

        memset(sta,,sizeof(int)*(n*+));

        for(int i=;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=;i<=*n;i++){

            if(!dfn[i])tarjan(i);

        }

        bool ok=;

        for(int i=;i<=n;i++){

            ok&=(scc[i]!=scc[i+n]);

        }

        if(ok)puts("YES");

        else puts("NO");

    }

    return ;

}