标签：ch 比赛记录 int times rc 校赛 textcolor lc

$\textcolor{orange}{义中常规赛 20230319}$

$\textcolor{green}{time:2023.3.19}$
$\textcolor{red}{Performance:180/252(实际分数/期望分数)}$

$\textcolor{purple}{A.天平}$

根据裴蜀定理及扩展可知，我们只需要找到最少的数字使他们的 gcd 与所有数字的 gcd 相等就行了。
我赛时打了一个 dp，拿到了 98 分，一个 WA,一个 TLE。赛后看题解发现直接暴搜就行了，因为 $10^7$ 内的数不同质因数的个数不超过 8。
$2\times 3\times 5\times 7\times 11\times 13\times 17\times 19 = 9699690‬ $
那么只要每次选的数字使得当前 gcd 变小，这样每次质因数种数至少少 1，最多 8 个数就行了。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e7;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, ans;
int a[55];
int gcd(int x, int y){return y ? gcd(y, x % y) : x;}
void dfs(int x, int t, int cnt){
	if(cnt >= ans) return ;
	if(t == 1) return ans = cnt, void();
	if(x > n) return ;
	int gc = gcd(a[x], t);
	if(gc != t) dfs(x + 1, gc, cnt + 1);
	dfs(x + 1, t, cnt);
}
int main(){
//	freopen("weights.in", "r", stdin);
//	freopen("weights.out", "w", stdout);
	ans = n = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	int t = a[1];
	for(int i = 1; i <= n; ++i) t = gcd(a[i], t);
	for(int i = 1; i <= n; ++i) a[i] /= t;
	dfs(1, 0, 0);
	printf("%d\n", ans);
	return 0;
}

$\textcolor{purple}{B.支配数据}$

开始以为是树套树，就只打了个 50 分暴力就润了。
没想到动态开点线段树就行了，原序列用一个 ST 表维护最小值，区间覆盖用线段树维护即可。

点击查看代码

#include<bits/stdc++.h>
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
const int N = 1e5 + 51;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, k, q, rt, cnt;
int b[N], st[N][20], lg[N];
int lc[N * 100], rc[N * 100], minn[N * 100], lazy[N * 100];
inline int f(int l, int r){
	int t = lg[r - l + 1];
	return min(st[l][t], st[r - (1 << t) + 1][t]);
}
inline int getmin(int l, int r){
	if(r - l + 1 >= n) return f(1, n);
	l = (l - 1) % n + 1, r = (r - 1) % n + 1;
	if(l <= r) return f(l, r);
	else return min(f(l, n), f(1, r));
}
inline void newnode(int &u, int l, int r){
	u = ++cnt, minn[u] = getmin(l, r);
}
inline void pushup(int u, int l, int r){
	int mid = (l + r) >> 1;
	if(!lc[u]) newnode(lc[u], l, mid);
	if(!rc[u]) newnode(rc[u], mid + 1, r);
	minn[u] = min(minn[lc[u]], minn[rc[u]]);
}
inline void PushDown(int u){
	if(lazy[u]){
		if(!lc[u]) lc[u] = ++cnt;
		if(!rc[u]) rc[u] = ++cnt;
		lazy[lc[u]] = lazy[rc[u]] = lazy[u];
		minn[lc[u]] = minn[rc[u]] = lazy[u];
		lazy[u] = 0;
	}
}
inline void UpDate(int &u, int l, int r, int L, int R, int v){
	if(!u) newnode(u, l, r);
	if(L <= l && r <= R) return lazy[u] = minn[u] = v, void();
	PushDown(u);
	int mid = (l + r) >> 1;
	if(L <= mid) UpDate(lc[u], l, mid, L, R, v);
	if(R > mid) UpDate(rc[u], mid + 1, r, L, R, v);
	pushup(u, l, r);
} 
inline int Query(int &u, int l, int r, int L, int R){
	if(!u) newnode(u, l, r);
	if(L <= l && r <= R) return minn[u];
	PushDown(u);
	int mid = (l + r) >> 1, ans = 0x3f3f3f3f;
	if(L <= mid) ans = min(ans, Query(lc[u], l, mid, L, R));
	if(R > mid) ans = min(ans, Query(rc[u], mid + 1, r, L, R));
	return ans;
}
int main(){
//	freopen("data.in", "r", stdin);
//	freopen("data.out", "w", stdout);
	n = read(), k = read();
	memset(st, 0x3f, sizeof(st));
	memset(minn, 0x3f, sizeof(minn));
	for(int i = 1; i <= n; ++i) st[i][0] = b[i] = read();
	for(int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
	for(int i = 1; i <= lg[n]; ++i)
		for(int j = 1; j + (1 << i) - 1 <= n; ++j)
			st[j][i] = min(st[j][i - 1], st[j + (1 << i - 1)][i - 1]);
	q = read();
	while(q--){
		int opt = read(), l = read(), r = read();
		if(opt == 1) UpDate(rt, 1, n * k, l, r, read());
		else printf("%d\n", Query(rt, 1, n * k, l, r));
	}
	return 0;
}