首页 > 代码库 > 【组队训练】2016 ACM/ICPC Asia Regional Dalian Online

【组队训练】2016 ACM/ICPC Asia Regional Dalian Online

因为不是一队……毫无晋级的压力……反正有压力也进不去呵呵呵……

开场zr看1006我看1010。。

1010我一直在wa。。。

zr的1006倒是比较轻松的过了。。。然后我让他帮我看10。。。。

跟他讲了半天我代码的逻辑。。。然后我自己看出来的。。。。比赛的代码。。。。写的十分混乱。。。。

技术分享
#include <cstdio>#include <cstring>#include <algorithm>#include <vector>typedef long long ll;using namespace std;const int N = 100005;vector<int> G[N];int a[N], b[N];int low[N];int par[N];int c[N];int cntv;ll ans;int n;int lowbit(int x){    return x & (-x);}int sum(int n)                //前n个数的和{    int ans = 0;    while (n > 0) {        ans +=  c[n];        n -= lowbit(n);    }    return ans;}void add(int pos, int num, int n)    //在pos处加num{    while (pos <= n) {         c[pos] += num;        pos += lowbit(pos);    }}void dfs(int u) {    //printf("==%d %d %d\n", u, a[u], low[ a[u] ]);    //printf("n = %d\n", n);    int lowu = low[ a[u] ];    int tmp = sum(lowu);    for (unsigned i = 0; i < G[u].size(); ++i) {        int v = G[u][i];        dfs(v);    }    int tmp2 = sum(lowu);    add(a[u], 1, n);    cntv++;    //printf(">>%d %d %d\n", u, tmp, tmp2);    ans += tmp2 - tmp;}void init() {    memset(c, 0, sizeof c);    memset(low, 0, sizeof low);    memset(par, 0, sizeof par);}int main(){    //freopen("in.txt", "r", stdin);    int T;    scanf("%d", &T);    while (T--) {        ll k;        init();        scanf("%d%lld", &n, &k);        //printf("%d %lld\n", n, k);        for (int i = 1; i <= n; ++i) {            G[i].clear();            scanf("%d", &a[i]);            b[i] = a[i];        }        sort(b+1, b+1+n);        int cnt = unique(b+1, b+1+n) - (b+1);        //printf("cnt=%d\n",cnt);        //for (int i = 1; i <= cnt; ++i) printf("|%d ", b[i]); printf("\n");        int idx = cnt;        for (int i = 1; i <= cnt; ++i) {            while ((ll)b[i]*b[idx--] > k) ;            idx++; low[i] = idx;        }//low[i]记录的是i*low[i]<=k的最大值        //for (int i = 1; i <= n; ++i) printf("%d ", low[i]); printf("\n");        for (int i = 1; i <= n; ++i) {            a[i] = lower_bound(b+1, b+1+cnt, a[i]) - b;        }        //for (int i = 1; i <= n; ++i) { printf("%d %d\n", a[i], low[ a[i] ]); }        int u, v;        for (int i = 1; i < n; ++i) {//printf("i=%d\n", i);            scanf("%d%d", &u, &v);            G[u].push_back(v);            par[v] = u;        }        int root = 1;        while (par[root]) root = par[root];        //printf("root=%d\n", root);        cntv = 0;        ans = 0;        dfs(root);        printf("%lld\n", ans);    }    return 0;}
View Code

 

1009总体思路也是我想出来的,但是代码出了一些十分隐蔽的逻辑错误。。。zr比较强大。。。竟然看出来并改对了。。。

技术分享
#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>typedef long long ll;using namespace std;const int N = 200005;vector<int> G[N];int ans[N];void up(int &x, int y) {    if (x == -1 || x > y+1) x = y+1;}int main(){//freopen("in.txt", "r", stdin);    int T;    scanf("%d", &T);    while (T--) {        int n, m;        scanf("%d%d", &n, &m);        for (int i = 0; i <= n; ++i) G[i].clear();        int u, v;        for (int i = 0; i < m; ++i) {            scanf("%d%d", &u, &v);            G[u].push_back(v);            G[v].push_back(u);        }        int s;        scanf("%d", &s);        int cnt = 1;        for (int i = 1; i <= n; ++i) ans[i] = 1; ans[s] = -1;        queue<int> q[2];        int now = 0;        for (unsigned i = 0; i < G[s].size(); ++i) {            int v = G[s][i];            ans[v] = -1;            q[now].push(v);            cnt++;        }        for (int i = 1; i <= 2*m; ++i) {            if (q[now].empty()) break;            int num = 0;            while (q[now].size()) {                int u = q[now].front(); q[now].pop();                //printf("u=%d \n", u);                int tmp = 0;                int sz = G[u].size();                for (int j = 0; j < sz; ++j) {                    int v = G[u][j];                    if (ans[v] == -1) tmp++;                }                //printf("%d: %d %d %d\n", u, sz, tmp, n);                if (n - sz > cnt - tmp) {                    //printf(">>%d %d\n", u, ans[u]);                    ans[u] = i+1;                    num++;                } else {                    q[now^1].push(u);                }            }            cnt -= num;            now ^= 1;        }        bool ok = true;        for (int i = 1; i <= n; ++i) {            if (s == i) continue;            if (ok) ok = false; else printf(" ");            printf("%d", ans[i]);        }        printf("\n");    }    return 0;}
View Code

 

1007坑题。竟然是推公式。。。两个人讨论了下,wa了几次推出来了。。。

技术分享
#include <cstdio>#include <cstring>#include <vector>#include <algorithm>#include <iostream>#include <map>#include <queue>#include <stack>#include <cmath>typedef long long ll;#define CLR(x, v) sizeof (x, v, sizeof(x))using namespace std;ll n,m;int main(){   //freopen("in.txt","r",stdin);   while(cin >> m >> n){        if (m == 1) puts("T");        else if ((m/2)*(m-m/2) > n) puts("F");        else puts("T");   }   return 0;}
View Code

 

02补题吧。。太弱了。。。。

【组队训练】2016 ACM/ICPC Asia Regional Dalian Online