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 <bits/stdc++.h>
#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<int> ans;
int res = 0;
int L[N], R[N];
set<int> 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<int> 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 <bits/stdc++.h>
#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, r
inline 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]\)。
我们简单化一下式子。
\]
\]
\]
我们可以在\(O(\sqrt{p})\)的时间内求出\(p\)所有约数
（大约有\(p^{1/3}\)个）。然后就可以直接求了。
总时间复杂度为\(O(T (\log 2e9 \cdot p^{1/3} + \sqrt p))\)。
那个\(2e9\)是因为我不知道右边界有多大啊QAQ，随便取的，取小会WA。
代码
#include <bits/stdc++.h>
#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<N> 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<int> 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