Educational Codeforces Round 37
这场有点炸，题目比较水，但只做了3题QAQ。还是实力不够啊！
写下题解算了……（写的比较粗糙，细节或者bug可以私聊2333）
A. Water The Garden
题意
给你一个长度为\(n\)的池子，告诉你哪些地方一开始有水，每秒可以向左和向右增加一格的水，问什么时候全部充满水。(\(n \le 200\))
题解
按题意模拟。每次进来一个水龙头，就更新所有点的答案（取\(min\))。最后把所有点取个\(max\)就可以了。
B. Tea Queue
题意
有\(n\)个人来喝咖啡。咖啡店每个时刻只能有一个人在喝咖啡。第\(i\)个人有进来的时间\(l_i\)和离开的时间\(r_i\)，这意味着他会在\(l_i\)时间来排队，如果到\(r_i\)的时候还没喝到咖啡，他就会离开队列。
同时有多个人来排的话，编号小的在前面。问每个人最早喝到咖啡的时间，如果不能喝到就输出\(0\)。
(\(n \le 1000 \ \ l_i,r_i \le 5000\)) 输入数据已经按照\(l_i\)非降序排列。有\(T\)组数据。(\(T \le 1000\))
题解
又是一个模拟...我没有用队列去写，而用一个\(set\)去模拟这个队列。定义一个pair<int, int> set S，第一关键字是他进来的时间，第二关键字是他的编号，每秒取S.begin()就行了。中间删除也很好用。
C. Swap Adjacent Elements
题意
给你一个长度为\(n\)的排列，然后告诉你一些位置（这些位置相邻）能进行交换，判断是否能将原序列变得有序。(\(n \le 200000\))
题解
考虑一个分组，将这个段分成很多子段。这些段内部可以相互任意交换，所以这种段就直接能排好序。然后我们就可以对于每段check一下，看它（这个段）是否本身就是在这个位置上。
即这个段为\([l,r]\)时，\(\forall i \in [l,r]\) 满足\(a_i \in [l,r]\)。这是因为段与段之间不可能有互换的操作，所以是相对独立的子段，本身位置不会有任何变动。
D. Tanks
- 这题我没看，也没做QAQ，似乎是一道构造？还是dp？全场A的最少的。。不想改了（
绝对不是因为我懒，而是因为我菜2333）。
yyb过了Orz
E. Connected Components?
题意
给你一个有\(n\)个点的无向完全图，然后在里面删除\(m\)条边，求联通块数量和联通块大小。（\(n,m \le 200000\)）
题解
这个题就是个暴力优化……考虑一开始先找出大的联通块，然后不难想到按照点的度数从大到小进行排序。然后我们再维护一个剩余点集。
每次Dfs一个点，再枚举点集中的点，看是否连边。（一开始程序过了system test 后来被hack了QAQ 只是因为有些没搞到一起来）时间复杂度我不会分析QAQ……
但是第一次总能带走特别多的点，使得这个集合不是很大。
代码
#include#define For(i, l, r) for(register int i = (l), _end_ = (int)(r); i <= _end_; ++i)#define Fordown(i, r, l) for(register int i = (r), _end_ = (int)(l); i >= _end_; --i)#define Set(a, v) memset(a, v, sizeof(a))using namespace std;bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}inline int read() { int x = 0, fh = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1; for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0'); return x * fh;}void File() {#ifdef zjp_shadow freopen ("e.in", "r", stdin); freopen ("e.out", "w", stdout);#endif}const int N = 200100;int n, m;struct point { int deg, no; bool operator < (const point &rhs) const {return deg > rhs.deg; }};point lt[N];vector ans;int res = 0;int L[N], R[N];set Ban[N];int fa[N];int find(int x) { return fa[x] == x ? x : (fa[x] = find(fa[x]) );}int sum[N];bool vis[N];inline void Delete(int x) { vis[x] = true; L[R[x]] = L[x]; R[L[x]] = R[x];}inline void Connect(int a, int b) { int r1 = find(a), r2 = find(b); if (r1 == r2) return ; fa[r1] = r2;}int Col[N];void Dfs(int u) { vector Go; for (register int v = R[0]; v <= n; v = R[v]) if (!vis[v] && Ban[u].find(v) == Ban[u].end() ) Connect(u, v), Delete(v), Go.push_back(v); for (register auto v : Go) Dfs(v);}int main () { File(); cin >> n >> m; For (i, 1, n) lt[i].no = i, lt[i].deg = n - 1; For (i, 1, m) { int u = read(), v = read(); Ban[v].insert(u); Ban[u].insert(v); --lt[u].deg; --lt[v].deg; } R[0] = 1; For (i, 1, n) L[i] = i - 1, R[i] = i + 1; sort (lt + 1, lt + 1 + n); For (i, 1, n) fa[i] = i; For (i, 1, n) if (!vis[lt[i].no]) Delete(lt[i].no), Dfs(lt[i].no); For (i, 1, n) ++ sum[find(i)]; For (i, 1, n) if (sum[i]) ans.push_back(sum[i]); sort (ans.begin(), ans.end() ); cout << ans.size() << endl; for (auto i : ans) printf ("%d ", i); return 0;}
F. SUM and REPLACE
题意
给你一个长为\(n\)的序列，每个数为\(a_i\)。共有\(m\)个操作，分为两种类别。第一种就是对于一个区间\([l,r]\)中的所有数变为它们约数个数的数，第二种就是求区间\([l,r]\)的和。（\(n,m \le 3 \cdot 10^5 \ \ a_i \le 10^6\)）
题解
这和之前两道题十分类似，一个是开方，一个是除以2。不难发现这些操作有效次数特别少。我用暴力筛，筛的约数个数，然后发现在\(10^6\)范围内最多操作6次。
然后可以直接裸一个线段树上去，支持单点修改和区间查询。
代码
#include#define For(i, l, r) for(register int i = (l), _end_ = (int)(r); i <= _end_; ++i)#define Fordown(i, r, l) for(register int i = (r), _end_ = (int)(l); i >= _end_; --i)#define Set(a, v) memset(a, v, sizeof(a))using namespace std;bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}inline int read() { int x = 0, fh = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1; for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0'); return x * fh;}void File() {#ifdef zjp_shadow freopen ("f.in", "r", stdin); freopen ("f.out", "w", stdout);#endif}const int N = 1e6 + 1e3;int n, m;int d[N];void Init(int maxn) { For (i, 1, maxn) for (register int j = i; j <= maxn; j += i) ++ d[j];}int maxv[N << 2], sumv[N << 2];#define lson o << 1, l, mid#define rson o << 1 | 1, mid + 1, rinline void push_up(int o) { maxv[o] = max(maxv[o << 1], maxv[o << 1 | 1]); sumv[o] = sumv[o << 1] + sumv[o << 1 | 1];}void Build(int o, int l, int r) { if (l == r) {maxv[o] = sumv[o] = read(); return ;} int mid = (l + r) >> 1; Build(lson); Build(rson); push_up(o);}int ul, ur;void Update(int o, int l, int r) { if (maxv[o] <= 2) return ; if (l == r) { maxv[o] = d[maxv[o]]; sumv[o] = d[sumv[o]]; return ; } int mid = (l + r) >> 1; if (ul <= mid) Update(lson); if (ur > mid) Update(rson); push_up(o);}int ql, qr;int Query(int o, int l, int r) { if (ql <= l && r <= qr) return sumv[o]; int mid = (l + r) >> 1, res = 0; if (ql <= mid) res += Query(lson); if (qr > mid) res += Query(rson); return res;}int main () { File(); Init((int)1e6); n = read(); m = read(); Build(1, 1, n); For (i, 1, m) { int opt = read(); if (opt == 1) { ul = read(); ur = read(); Update(1, 1, n); } else { ql = read(); qr = read(); printf ("%d\n", Query(1, 1, n) ); } } return 0;}
G. List Of Integers
题意
给你三个整数\(x\),\(p\),\(k\)。求满足条件\(y > x\)且\(gcd(y,p)=1\)的第\(k\)个\(y\)。
（\(x,p,k \le 10^6\)）题解
一开始看错题，以为直接给你\(y\)求和，直接上莫比乌斯反演就行了。
但没关系，不难发现可以二分这个\(y\)。只要满足\(sum_y-sum_x \ge k\) 的第一个就行了，此处的\(sum_q\) 就是 \(\sum \limits _{i=1}^{q} [gcd(i,p)=1]\)。我们简单化一下式子。
\[\sum \limits _{i=1}^{q} [gcd(i,p)=1]\]
\[=\sum \limits _{i=1}^{q} \sum \limits_{d | gcd(i,p)} \mu(d)\]
\[=\sum \limits _{d|p} \mu(d) \cdot \lfloor \frac {q}{d} \rfloor\]
我们可以在\(O(\sqrt{p})\)的时间内求出\(p\)所有约数
（大约有\(p^{1/3}\)个）。然后就可以直接求了。总时间复杂度为\(O(T (\log 2e9 \cdot p^{1/3} + \sqrt p))\)。
那个\(2e9\)是因为我不知道右边界有多大啊QAQ，随便取的，取小会WA。代码
#include#define For(i, l, r) for(register int i = (l), _end_ = (int)(r); i <= _end_; ++i)#define Fordown(i, r, l) for(register int i = (r), _end_ = (int)(l); i >= _end_; --i)#define Set(a, v) memset(a, v, sizeof(a))using namespace std;bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}inline int read() { int x = 0, fh = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1; for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0'); return x * fh;}int x, p, k;const int N = 1e6 + 1e3;int mu[N], prime[N], cnt;int fac[N];bitset is_prime;void Init(int maxn) { is_prime.set(); int res; is_prime[0] = is_prime[1] = false; mu[1] = 1; For (i, 2, maxn) { if (is_prime[i]) { prime[++cnt] = i; mu[i] = -1; fac[i] = i; } For (j, 1, cnt) { res = prime[j] * i; if (res > maxn) break ; is_prime[res] = false; if (!fac[res]) fac[res] = prime[j]; if (i % prime[j]) mu[res] = -mu[i]; else { mu[res] = 0; break; } } }}vector V;bool have[N];inline void Resolve() { V.clear(); For (i, 1, sqrt(p) ) if (!(p % i) ) { V.push_back(i); if (i * i != p) V.push_back(p / i); }}inline int Calc(int maxn) { int res = 0; for (auto i : V) res += mu[i] * (maxn / i); return res;}int main () { int cases = read(); Init((int)1e6); while (cases --) { x = read(); p = read(); k = read(); Resolve(); int res1 = Calc(x), res2; int l = x, r = 1e9; int ans; while (l <= r) { int mid = (l + r) >> 1; res2 = Calc(mid); if (res2 - res1 >= k) { ans = mid; r = mid - 1; } else l = mid + 1; } cout << ans << endl; } return 0;}
ps：yyb 把我吊起来打 Orz