Educational Codeforces Round 37

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]\)。

我们简单化一下式子。

\[\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 <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