上场比赛的rating掉的很科学啊,正好回到div2可以做一下今年的最后一场codeforces。最后的结果还是3题,rank28。什么时候能在div1 rank28啊?
现在完成了前四道题,写一下简单的题解。
260A Adding Digits
先从0到9枚举加的第一位,如果有能整除的,那么就不断在这个数字后面补0,显然得到的数字也能整除b;反之则输出-1。
260B Ancient Prophesy
暴力枚举所有长度等于10的子串,然后判断合法性即可。这种题我写的还是有点慢。
260C Balls and Boxes
我们很容易发现,被选中的box最后剩下的球数量肯定是最少的之一。但是现在的问题是,如果有多个box最终剩余球的数量同时是最少的,应该选哪一个呢?画个图就可以看出,选位置x之前的第一个即可。这是这道题的一个trick。
代码如下:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <set> #include <map> #include <string> #include <algorithm> using namespace std; const int N = 100010; typedef __int64 lld; const lld INF = 2e9; lld a[N]; lld mod(lld a, lld b) { return (a % b + b) % b; } int main() { lld n, x; int ind; do { scanf("%I64d%I64d", &n, &x); --x; lld mi = INF; for (int i = 0;i < n;++i) { scanf("%I64d", a + i); if (a[i] < mi) mi = a[i]; } for (int i = 0;i < n;++i) if (a[mod(x - i, n)] == mi) { ind = mod(x - i, n); break; } // ind is the answer lld tot = mi * n + mod(x - ind, n); for (int i = 0;i < n;++i) { if (i == ind) printf("%I64d", tot); else { if (mod(i - ind, n) <= mod(x - ind, n) ) printf("%I64d", a[i] - a[ind] - 1); else printf("%I64d", a[i] - a[ind]); } if (i == n - 1) printf("\n"); else printf(" "); } } while (0); return 0; }
260D Black and White Tree
比赛的时候想多了,其实就是一个很简单的构造。YY能力有待提高啊。
由于只能在黑白节点之间连边,这样就构成了一个二分图。首先我们考虑这个问题:什么样的情况下存在解?经过一些YY我们可以发现,只要黑色节点和白色节点的权值总和相等,就一定有解。
接下来我们YY一下如何构造一个解。其实还是按照最直观的方法进行:我们每次都选择一个黑色节点和一个白色节点,设它们的权值分别是b_weight和w_weight。那么我们只要在它们之间连一条权值等于min(b_weight,w_weight)的边,然后删除总权值较小的那个节点。将这个过程重复(n-1)次,就得到了一棵树。
我的逻辑比较混乱的代码如下(这个代码里的sort()是多余的,事实上根本不需要对节点排序):
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 100005; pair<int, int> w[N], b[N]; //0->w, 1->b int main() { int n, c, s; int wc, bc; do { scanf("%d", &n); wc = bc = 0; for (int i = 1;i <= n;++i) { scanf("%d%d", &c, &s); if (!c) w[wc++] = make_pair(s, i); else b[bc++] = make_pair(s, i); } sort(w, w + wc); sort(b, b + bc); int e = 0; for (int i = 0, j = 0;e < n - 1;++e) { int wei = min(w[i].first, b[j].first); w[i].first -= wei; b[j].first -= wei; printf("%d %d %d\n", w[i].second, b[j].second, wei); if (!w[i].first && i != wc - 1) //next vertex ++i; else if (!b[j].first) ++j; } } while (0); return 0; }
260E Dividing Kingdom
好像是枚举9个城市的排列,然后扫描线?总感觉很麻烦的样子= =
给大神童跪了。。
给大平哥跪了!新年快乐!
Like note a tangibles abetting an fondness to winning. gtmac.me
http://bit.ly/2NLWmfs