首页 > 代码库 > 【组队训练】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;}
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;}
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;}
02补题吧。。太弱了。。。。
【组队训练】2016 ACM/ICPC Asia Regional Dalian Online
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。