Codeforces Wunder fund 618ABCDEF

Codeforces Wunder fund
题目链接：http://codeforces.com/contest/618
最后一题过了12个人就不改了……
通过数 3
Standing： 506/6671
Rating change： 1811 - 1862
ABC忘记什么题了。

A：
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int a[60];
int main()
{int n;while(scanf("%d", &n) != EOF){int now = 0;int cnt = 0;int num = 0;while((1 << now) <= n){if((1 << now) & n) a[cnt++] = num + 1;num++;now++;}for(int i = cnt - 1 ; i >= 0 ; i--){printf("%d", a[i]);if(i == 0) printf("\n");else printf(" ");}}return 0;
}B：
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 50 + 5;
int g[MAXN][MAXN];
int use[MAXN], ans[MAXN];
int cnt[MAXN];
int main()
{int n;while(scanf("%d", &n) != EOF){memset(ans, 0, sizeof(ans));memset(use, 0, sizeof(use));for(int i = 1 ; i <= n ; i++) for(int j = 1 ; j <= n ; j++) scanf("%d", &g[i][j]);for(int i = 1 ; i <= n ; i++){for(int j = 1 ; j <= n ; j++) cnt[j] = 0;for(int j = 1 ; j <= n ; j++) cnt[g[i][j]]++;for(int j = 1 ; j <= n ; j++){if(cnt[j] > 1){ans[i] = j;use[j] = 1;break;}}}int head = 1;for(int i = 1 ; i <= n ; i++){if(ans[i] == 0){while(use[head] == 1) head++;ans[i] = head;use[head] = 1;}}for(int i = 1 ; i <= n ; i++){printf("%d", ans[i]);if(i == n) printf("\n");else printf(" ");}}return 0;
}C：
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 100000 + 5;
struct D
{int x, y;int id;
}d[MAXN];
bool cmp(D a, D b)
{if(a.x == b.x) return a.y < b.y;return a.x < b.x;
}
bool cal(int u1, int v1, int u2, int v2, int u3, int v3)
{long long t1 = v1 - v2;t1 = t1 * (u1 - u3);long long t2 = v1 - v3;t2 = t2 * (u1 - u2);
//    printf("t1 = %I64d, t2 = %I64d\n", t1, t2);if(t1 == t2) return true;else return false;
}
int main()
{int n;while(scanf("%d", &n) != EOF){for(int i = 1 ; i <= n ; i++){scanf("%d%d", &d[i].x, &d[i].y);d[i].id = i;}sort(d + 1, d + 1 + n, cmp);
//        for(int i = 1 ; i <= n ; i++){
//            printf("x = %d, y = %d, id = %d\n", d[i].x, d[i].y, d[i].id);
//        }int rx1 = d[1].x, ry1 = d[1].y;int rx2, ry2;int f = 1;int a1 = d[1].id, a2, a3;for(int i = 2 ; i <= n ; i++){if(f){rx2 = d[i].x, ry2 = d[i].y;f = 0;a2 = d[i].id;}else{if(cal(rx1, ry1, rx2, ry2, d[i].x, d[i].y)) continue;else{a3 = d[i].id;break;}}}printf("%d %d %d\n", a1, a2, a3);}return 0;
}

D：
给一个完全图，图中边有权值，其中给出的一颗生成树上的边权值为x，非此树上的边权值为y。
求不重复的走完所有点的最小代价。

赛中猜测是分类讨论。
X>y的时候不知道怎么考虑，随便写了一发。
X

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LL long long
const int MAXN = 200000 + 5;
vector<int>lin[MAXN];
queue<int>que;
int du[MAXN];
int vis[MAXN];
int n;
LL x, y;
int dfs(int u, int pre, int &cnt)
{int temp = 0;for(int i = 0 ; i < (int)lin[u].size() ; i++){int v = lin[u][i];if(v == pre) continue;if(dfs(v, u, cnt)) temp++;}if(u == 1){cnt += max(temp - 2, 0);return 0;}else{if(temp > 1){cnt += temp - 1;return 0;}else return 1;}
}
LL solve1()
{for(int i = 1 ; i <= n ; i++){if(du[i] == 1){que.push(i);vis[i] = 1;break;}}int cnt = 0;dfs(1, -1, cnt);
//    printf("cnt = %d\n", cnt);return x * (n - 1 - cnt) + y * cnt;
}
LL solve2()
{int cnt = 0;for(int i = 1 ; i <= n ; i++){if(du[i] == n - 1){cnt++;break;}}return y * (n - 1 - cnt) + x * cnt;
}
int main()
{while(scanf("%d%I64d%I64d", &n, &x, &y) != EOF){int u, v;for(int i = 1 ; i <= n ; i++) lin[i].clear() ,vis[i] = du[i] = 0;while(!que.empty()) que.pop();for(int i = 0 ; i < n - 1 ; i++){scanf("%d%d", &u, &v);lin[u].push_back(v);lin[v].push_back(u);du[u]++;du[v]++;}for(int i = 1 ; i <= n ; i++) sort(lin[i].begin(), lin[i].end());LL ans = 0;if(x == y){ans = x * (n - 1);}else if(x < y){ans = solve1();}else ans = solve2();printf("%I64d\n", ans);}return 0;
}

E：
赛中听老耿说是计算几何没看，实际上是线段树。
线段树我也不会啊……
先导题POJ 2991，然后这题就很简单了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 300000 + 5;
const double PI = acos(-1.0);
int n, m;
double x[MAXN * 4], y[MAXN * 4];
int angle[MAXN * 4], flag[MAXN * 4];
void func(int o, int ang)
{double tx = x[o], ty = y[o];x[o] = ty * sin(ang * PI / 180.0) + tx * cos(ang * PI / 180.0);y[o] = ty * cos(ang * PI / 180.0) - tx * sin(ang * PI / 180.0);flag[o] = (flag[o] + ang) % 360;angle[o] = (angle[o] + ang) % 360;
}
void push_up(int o)
{x[o] = x[o << 1] + x[o << 1 | 1];y[o] = y[o << 1] + y[o << 1 | 1];
}
void push_down(int o)
{if(flag[o]){func(o << 1, flag[o]);func(o << 1 | 1, flag[o]);flag[o] = 0;}
}
void build(int l, int r, int o)
{x[o] = y[o] = 0;angle[o] = 90;flag[o] = 0;if(l == r){x[o] = 1;}else{int mid = (l + r) >> 1;build(l, mid, o << 1);build(mid + 1, r, o << 1 | 1);push_up(o);}
}
void update1(int u, int v, int L, int R, int o)
{if(L == R){x[o] = x[o] + v * sin(angle[o] * PI / 180.0);y[o] = y[o] + v * cos(angle[o] * PI / 180.0);}else{push_down(o);int mid = (L + R) >> 1;if(u <= mid) update1(u, v, L, mid, o << 1);else update1(u, v, mid + 1, R, o << 1 | 1);push_up(o);}
}
void update2(int l, int r, int v, int L, int R, int o)
{if(l <= L && r >= R){func(o, v);}else{push_down(o);int mid = (L + R) >> 1;if(l <= mid) update2(l, r, v, L, mid, o << 1);if(mid < r) update2(l, r, v, mid + 1, R, o << 1 | 1);push_up(o);}
}
int main()
{
//    freopen("CF 618E.in", "r", stdin);while(scanf("%d%d", &n, &m) != EOF){build(1, n, 1);
//        printf("x[1] = %f, y[1] = %f\n", x[1], y[1]);for(int i = 1 ; i <= m ; i++){int op, u, v;scanf("%d%d%d", &op, &u, &v);if(op == 1){update1(u, v, 1, n, 1);}else{update2(u, n, v, 1, n, 1);}printf("%.10f %.10f\n", x[1], y[1]);}}return 0;
}

F：
两个序列，任取数使得两个序列取出的数和相等。
感觉是很重要的模型。
/*
容斥原理中的鸽笼原理。
因为前缀和是递增的，记录值SumOfa - SumOfb，其中SumOfb为小于等于SumOfa的最大值
然后由于每个数都属于[1,n - 1]，所以这个值的范围[0,n - 1]。
因为一共有n+1中取法（包括不取任意一个数，视为SumOfa - SumOfb = 0)
故必定有两个差值相等
然后看代码就知道了
*/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LL long long
const int MAXN = 1000000 + 5;
int a[MAXN], b[MAXN];
pair<int,int> vis[MAXN];
vector<int>o1, o2;
int main()
{int n;while(scanf("%d", &n) != EOF){for(int i = 1 ; i <= n ; i++) scanf("%d", &a[i]);for(int i = 1 ; i <= n ; i++) scanf("%d", &b[i]);for(int i = 0 ; i <= n ; i++) vis[i] = make_pair(-1, -1);vis[0] = make_pair(0, 1);int head = 1;LL s1 = 0, s2 = 0;o1.clear(), o2.clear();for(int i = 1 ; i <= n ; i++){s1 += a[i];while(head <= n && s2 + b[head] <= s1) s2 += b[head++];int mark = s1 - s2;
//            printf("mark = %d, i = %d, head = %d\n")if(vis[mark].first == -1) vis[mark] = make_pair(i, head);else{for(int j = vis[mark].first + 1; j <= i ; j++) o1.push_back(j);for(int j = vis[mark].second; j <= head - 1; j++) o2.push_back(j);
//                printf("vis[mark] = %d %d, i = %d, head = %d\n", vis[mark].first, vis[mark].second, i, head);
//                printf("s1 = %I64d, s2 = %I64d\n", s1, s2);break;}}printf("%d\n", (int)o1.size());for(int i = 0 ; i < (int)o1.size() ; i++){printf("%d", o1[i]);if(i == (int)o1.size() - 1) printf("\n");else printf(" ");}printf("%d\n", (int)o2.size());for(int i = 0 ; i < (int)o2.size() ; i++){printf("%d", o2[i]);if(i == (int)o2.size() - 1) printf("\n");else printf(" ");}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！