contest链接
A.Andryusha and Socks
一道很无聊的题目
1 #include2 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 }
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 #include2 #include 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 }
三分代码:
1 #include2 #include 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 }
最后提醒一点今天刚知道的东西！
二分或者三分的时候，跳出循环的条件最好写成类似于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 #include2 #include 3 #include 4 5 using namespace std; 6 7 vector 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\n", k);36 redfs(1, 0, 0, 1);37 for(int i = 1;i <= n;i ++)38 printf("%d ", c[i]);39 return 0;40 }
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
E.Underground Lab
题意:
n个点，m条边的无向联通图，可以存在自环和重边
你有k个人，每个人初始位置由你来摆放
每个人最多走过(2n/k向上取整)个点(重复经过的点也要重复计入)
要求最后k个人能visit过所有n个点
要求输出一种可行方案(保证存在可行方案)
解法:
一开始拿到题我是毫无头绪的
然而参考了别人比赛代码感觉自己是zz
可以从图中随便找个包含了n个点的树
然后2n/k中的2n你能联想到什么呢！
没错！欧拉序列！欧拉序列中的点数=2n - 1
而且欧拉序列的一个特点，随便在欧拉序列中截一段，都是可以直接走的路径！
所以就直接一遍dfs求出一棵树的欧拉序列，然后再把它们分成k份
并且每份都满足要求就好了
(今天刚认识向上取整和向下取整的符号QAQ
1 #include2 #include 3 #include 4 5 using std::min; 6 using std::max; 7 using std::vector; 8 9 const int maxn = 500010;10 11 vector 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 }
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开始走：
第一个是0，每次复制当前序列，取反后贴在当前序列后面构成新的序列
eg:0, 01, 0110, 01101001, 0110100110010110, ...
假如你找了一条长度为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 #include2 3 #define bt bitset 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 }