Codeforces Round #403 (Div. 2)

contest链接

A.Andryusha and Socks

一道很无聊的题目

 1 #include <cstdio>
 2 
 3 int n, m, k, a[100010];
 4 
 5 int main() {
 6     int x;
 7     scanf("%d", &n);
 8     for(int i = n << 1;i --;) {
 9         scanf("%d", &x);
10         if(a[x]) k --;
11         else a[x] = 1, k ++;
12         if(k > m) m = k; 
13     }
14     printf("%d", m);
15     return 0;
16 }

View Code

B.The Meeting Place Cannot Be Changed

题意很容易读懂，要求精度到1e-6，保险起见我把eps设为了1e-8

耿直的我首先想到的是三分目的地的位置

凭借以前做题经验猜测time随destination是先减后增的单峰函数

事实证明这样做是正确的

另一个妙一些的解法是直接二分ans，也就是time

那么judge函数呢，传进来一个time

我们计算出所有人都以最大速度往正方向走时，所有人到达的坐标中的最小坐标R

再同时计算出所有人都以最大速度往负方向走时，所有人到达的坐标中的最大坐标L

如果R >=L，就说明这个time很充足，ans <= time，否则...

二分代码:

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 int n;
 7 
 8 double x[60010], v[60010];
 9 
10 int main() {
11     scanf("%d", &n);
12     for(int i = 1;i <= n;i ++)
13         scanf("%lf", &x[i]);
14     for(int i = 1;i <= n;i ++)
15         scanf("%lf", &v[i]);
16     double l = 0, r = 1e9, mid, L, R;
17     while(l + 1e-8 <= r) {
18         L = 0, R = 1e9, mid = (l + r) / 2;
19         for(int i = 1;i <= n;i ++) {
20             L = max(L, x[i] - v[i] * mid);
21             R = min(R, x[i] + v[i] * mid);
22         }
23         if(R <= L) l = mid + 1e-8;
24         else r = mid - 1e-8;
25     }
26     printf("%.6f", l);
27     return 0;
28 }

View Code

三分代码:

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 const int maxn = 60010;
 7 
 8 const double eps = 1e-8;
 9 
10 int n;
11  
12 double x[maxn], v[maxn];
13 
14 double abs(double x) {
15     if(x < 0) return -x;
16     return x;
17 }
18 
19 double calc(double des) {
20     double tim = 0;
21     for(int i = 1;i <= n;i ++)
22         tim = max(tim, abs(x[i] - des) / v[i]);
23     return tim;
24 }
25 
26 int main() {
27     double l = 1e9, r = 1, mid1, mid2, tim1, tim2;
28     scanf("%d", &n);
29     for(int i = 1;i <= n;i ++)
30         scanf("%lf", &x[i]), l = min(l, x[i]), r = max(r, x[i]);
31     for(int i = 1;i <= n;i ++)
32         scanf("%lf", &v[i]);
33     for(int i = 140;i --;) {
34         mid1 = (l + r) / 2;
35         mid2 = (mid1 + r) / 2;
36         tim1 = calc(mid1);
37         tim2 = calc(mid2);
38         if(tim1 >= tim2 + eps) l = mid1 + eps;
39         else r = mid2 - eps; 
40     }
41     printf("%.6f", calc(mid1));
42     return 0;
43 }

View Code

最后提醒一点今天刚知道的东西！

二分或者三分的时候，跳出循环的条件最好写成类似于for(int i = 150;i --;)

不建议写成while(l + eps <= r)，因为可能精度问题，这样写始终跳不出循环

当然int不存在这种情况，使用double类型，而且eps比较小的话可能就是会

跳不出循环最终TLE，已经以身试法。

C.Andryusha and Colored Balloons

若有一点a，那么要保证a和所有与它相邻的k个点

一共这(k +１)个点，都要染上各不相同的颜色

所以显然最少需要的颜色数k = max(1 + edge[i].size())

然后又因为是一棵树的样子，所以在处理 i 点时

直接给它的儿子们分配不同于color[i]和color[fa[i]]的颜色即可

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 vector <int> e[200010];
 8 
 9 int n, k, c[200010];
10 
11 void dfs(int x, int f) {
12     k = max(1 + (int)e[x].size(), k);
13     for(int i = 0;i < e[x].size();i ++)
14         if(e[x][i] != f)
15             dfs(e[x][i], x);
16 }
17 
18 void redfs(int x, int f, int c1, int c2) {
19     for(int i = 0, j = 1;i < e[x].size();i ++) 
20         if(e[x][i] != f) {
21         while(j == c1 || j == c2) j ++;
22         c[e[x][i]] = j, redfs(e[x][i], x, c2, j), j ++;
23     }
24 }
25 
26 int main() {
27     int u, v;
28     scanf("%d", &n);
29     for(int i = 1;i < n;i ++) {
30         scanf("%d %d", &u, &v);
31         e[u].push_back(v);
32         e[v].push_back(u);
33     }
34     dfs(1, 0), c[1] = 1;
35     printf("%d
", k);
36     redfs(1, 0, 0, 1);
37     for(int i = 1;i <= n;i ++)
38         printf("%d ", c[i]);
39     return 0;
40 }

View Code

D.Innokenty and a Football League

翻译整合后的题意:

1000个队伍，每个队伍 i 有两个字符串s1[i]和s2[i]

每个队伍可以选择

1.s1[i]前三个字母构成的字符串(字符顺序唯一)

2.s1[i]前两个字母和s2[i]第一个字母构成的字符串(字符顺序唯一)

中的一种作为自己队伍的名字

而且如果有多个不同队伍的第一种名字相同，那么他们都只能选第二种作为自己队伍的名字

解法:

题目描述的条件和要求整合好以后解法其实就简单了

写起来感觉就是hungary算法

作为懒人，大力推荐string + map

比char* + hash不知道方便到哪里去了:(

 1 #include <map>
 2 #include <cstdio>
 3 #include <iostream>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 const int maxn = 1010;
 9 
10 int n, m, bad[maxn];
11 
12 map <string, int> p, pre;
13 
14 string s1[maxn], s2[maxn], ans[maxn];
15 
16 bool dfs(int u) {
17     string s3 = s1[u].substr(0, 3);
18     if(!bad[u]) {
19         if(p[s3] != m) {
20             p[s3] = m;
21             if(!pre[s3] || dfs(pre[s3])) {
22                 ans[u] = s3;
23                 pre[s3] = u;
24                 return 1;
25             }
26         }    
27     }
28     s3.erase(s3.end() - 1), s3 += s2[u][0];
29     if(p[s3] != m) {
30         p[s3] = m;
31         if(!pre[s3] || dfs(pre[s3])) {
32             ans[u] = s3;
33             pre[s3] = u;
34             return 1;
35         }
36     }
37     return 0;
38 }
39 
40 int main() {
41     string s3;
42     scanf("%d", &n); 
43     for(int i = 1;i <= n;i ++) {
44         cin >> s1[i] >> s2[i];
45         s3 = s1[i].substr(0, 3);
46         if(!p[s3]) p[s3] = i;
47         else bad[i] = 1, bad[p[s3]] = 1;
48     }
49     for(int i = 1;i <=n ;i ++)
50         p[s1[i].substr(0, 3)] = 0;
51     for(m = 1;m <= n;m ++)
52         if(!dfs(m)) {
53             puts("NO");
54             return 0;
55         }
56     puts("YES");
57     for(int i = 1;i <= n;i ++)
58         cout << ans[i] << endl;
59     return 0;
60 }

View Code

E.Underground Lab

题意:

n个点，m条边的无向联通图，可以存在自环和重边

你有k个人，每个人初始位置由你来摆放

每个人最多走过(2n/k向上取整)个点(重复经过的点也要重复计入)

要求最后k个人能visit过所有n个点

要求输出一种可行方案(保证存在可行方案)

解法:

一开始拿到题我是毫无头绪的

然而参考了别人比赛代码感觉自己是zz

可以从图中随便找个包含了n个点的树

然后2n/k中的2n你能联想到什么呢！

没错！欧拉序列！欧拉序列中的点数=2n - 1

而且欧拉序列的一个特点，随便在欧拉序列中截一段，都是可以直接走的路径！

所以就直接一遍dfs求出一棵树的欧拉序列，然后再把它们分成k份

并且每份都满足要求就好了

(今天刚认识向上取整和向下取整的符号QAQ

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 
 5 using std::min;
 6 using std::max;
 7 using std::vector;
 8 
 9 const int maxn = 500010;
10 
11 vector <int> e[maxn];
12 
13 int n, m, k, cnt, vis[maxn], ans[maxn];
14 
15 void dfs(int x) {
16     ans[++ cnt] = x, vis[x] = 1;
17     for(int i = 0;i < e[x].size();i ++) {
18         if(vis[e[x][i]]) continue;
19         dfs(e[x][i]), ans[++ cnt] = x;
20     }
21 }
22 
23 int main() {
24     int u, v;
25     scanf("%d %d %d", &n, &m, &k);
26     for(int i = 1;i <= m;i ++) {
27         scanf("%d %d", &u, &v);
28         e[u].push_back(v);
29         e[v].push_back(u);
30     }
31     dfs(1);
32     int l, r, cn = (2 * n + k - 1) / k;
33     for(int i = 1;i <= k;i ++) {
34         l = (i - 1) * cn + 1;
35         l = min(l, cnt), r = min(l + cn, cnt + 1);
36         printf("%d ", r - l);
37         for(int j = l;j < r;j ++) printf("%d ", ans[j]);
38         puts("");
39     }
40     return 0;
41 }

View Code

F.Axel and Marston in Bitland

一开始没读懂题目中描述的构造规则

于是似董非董地写了个垃圾的最短路还说这不傻逼题么

题意:

最多500个点，50W条单向边，起点为1

每条单向边有u,v,w，代表从u到v，且这条边属性为w(w只能为0或1)，每条边长度都为1

可能存在两条边u,v相同，但不存在两条边u,v,w都相同，一条边的u和v可以相同

要求按如下规则构造一个w的序列然后从1开始走：

第一个是

假如你找了一条长度为13的路径，那么这条路径上

按顺序经过的边，它们的w必须满足0110100110010(即上面加粗部分

你需要找到一条满足条件的最长路并输出其长度

若答案>1e18则输出-1

解法:

(参考了别人代码)

序列取反后贴在当前序列后面

我们假如把一开始的0换成1，我们能构造出如下序列

1, 10, 1001, 10010110, ...

可以看到

原来的第4个序列是原来的第3个序列+新的第3个序列

且新的第4个序列是新的第3个序列+原来的第3个序列

而且这种构造是倍增的，即log级别的

所以我们考虑矩阵乘法

g[0/1][i].c[u][v] = 1

代表从u到v有满足原/新(0/1)序列且长度为 2^i 的路径

显然递推公式

g[0][i] = g[0][i - 1] * g[1][i - 1]

g[1][i] = g[1][i - 1] * g[0][i - 1]

然后我们开始考虑统计结果

c[i] = 1表示在已经走了ans步的情况下能够到达 i

这里当然要从大到小枚举并且最后枚举到0，因为0意味着2^0

补充:if(t.count())中的w^=1也是同样由构造规则得来

例如满足题目要求的长度13的路径等于

原来长度为8的序列+新的长度为4的序列+原来的长度为1的序列

 1 #include <bits/stdc++.h>
 2 
 3 #define bt bitset<maxn>
 4 
 5 using namespace std;
 6 
 7 typedef long long ll;
 8 
 9 const int maxn = 510;
10 
11 const ll inf = 1e18;
12 
13 int n, m;
14 
15 ll ans;
16 
17 struct matrix {
18     bt c[maxn]; 
19 }g[2][62];
20 
21 bt c, t;
22 
23 matrix operator * (const matrix &a, const matrix &b) {
24     matrix r;
25     for(int k = 1;k <= n;k ++)
26         for(int i = 1;i <= n;i ++)
27             if(a.c[i][k])
28                 r.c[i] |= b.c[k];
29     return r;
30 }
31 
32 int main() {
33     int u, v, w;
34     scanf("%d %d", &n, &m);
35     for(int i = 1;i <= m;i ++) {
36         scanf("%d %d %d", &u, &v, &w);
37         g[w][0].c[u][v] = 1;
38     }
39     for(int i = 1;i < 61;i ++) {
40         g[0][i] = g[0][i - 1] * g[1][i - 1];
41         g[1][i] = g[1][i - 1] * g[0][i - 1];
42     }
43     c.reset(), c[1] = 1, w = 0;
44     for(int i = 60;~i;i --) {
45         t.reset();
46         for(int j = 1;j <= n;j ++)
47             if(c[j]) t |= g[w][i].c[j];
48         if(t.count()) {
49             c = t;
50             w ^= 1;
51             ans |= 1ll << i;
52         }
53     }
54     if(ans > inf) puts("-1");
55     else printf("%I64d", ans);
56     return 0;
57 }

View Code