【组队训练】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 = ;

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

    while (n > ) {

        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 = ; i < G[u].size(); ++i) {

        int v = G[u][i];

        dfs(v);

    }

    int tmp2 = sum(lowu);

    add(a[u], , n);

    cntv++;

    //printf(">>%d %d %d\n", u, tmp, tmp2);

    ans += tmp2 - tmp;

}

void init() {

    memset(c, , sizeof c);

    memset(low, , sizeof low);

    memset(par, , 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 = ; i <= n; ++i) {

            G[i].clear();

            scanf("%d", &a[i]);

            b[i] = a[i];

        }

        sort(b+, b++n);

        int cnt = unique(b+, b++n) - (b+);

        //printf("cnt=%d\n",cnt);

        //for (int i = 1; i <= cnt; ++i) printf("|%d ", b[i]); printf("\n");

        int idx = cnt;

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

            a[i] = lower_bound(b+, b++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 = ; i < n; ++i) {//printf("i=%d\n", i);

            scanf("%d%d", &u, &v);

            G[u].push_back(v);

            par[v] = u;

        }

        int root = ;

        while (par[root]) root = par[root];

        //printf("root=%d\n", root);

        cntv = ;

        ans = ;

        dfs(root);

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

    }

    return ;

}

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

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

typedef long long ll;

using namespace std;

const int N = ;

vector<int> G[N];

int ans[N];

void up(int &x, int y) {

    if (x == - || x > y+) x = y+;

}

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 = ; i <= n; ++i) G[i].clear();

        int u, v;

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

        for (int i = ; i <= n; ++i) ans[i] = ; ans[s] = -;

        queue<int> q[];

        int now = ;

        for (unsigned i = ; i < G[s].size(); ++i) {

            int v = G[s][i];

            ans[v] = -;

            q[now].push(v);

            cnt++;

        }

        for (int i = ; i <= *m; ++i) {

            if (q[now].empty()) break;

            int num = ;

            while (q[now].size()) {

                int u = q[now].front(); q[now].pop();

                //printf("u=%d \n", u);

                int tmp = ;

                int sz = G[u].size();

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

                    int v = G[u][j];

                    if (ans[v] == -) 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+;

                    num++;

                } else {

                    q[now^].push(u);

                }

            }

            cnt -= num;

            now ^= ;

        }

        bool ok = true;

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

            if (s == i) continue;

            if (ok) ok = false; else printf(" ");

            printf("%d", ans[i]);

        }

        printf("\n");

    }

    return ;

}

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 == ) puts("T");

        else if ((m/)*(m-m/) > n) puts("F");

        else puts("T");

   }

   return ;

}

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