GDUT2022校赛题解

博主： zclll
发布时间：2022 年 04 月 12 日
1154 次浏览
暂无评论
348字数
分类：算法

出了6题，赛中的话大概刚好Page1的程度，就先这样吧……

# A 区间最大值

A题经典数论分块，要求

$$
\max_{i=N}^L{n\%i}

显然等价于求

$$
n-\min_{i=L}^R{\lfloor \frac ni\rfloor *i}

那么数论分块求后一部分就好了，对于每一块，$i$显然在$L$处取得最小。

## 代码

```cpp
ll n, m;
int main()
{
	cin >> n >> m;
	while (m--)
	{
		ll L, R;
		cin >> L >> R;
		ll ans = INT_MAX;
		for (ll l = L, r; l <= R; l = r + 1)
		{
			r = min(R, n/(n/l));
			UPDmin(ans, n/l*l);
		}
		cout << n - ans << endl;
	}
	return 0;
}
```

这个地方因为是对$[1,n]$里取区间$[L,R]$，所以不用担心整除$0$的问题。如果有这个问题，那么提前特判一下$L,R$最大为$n$即可。

# B 模块改造

签到水题

# CD不会

# E 爬塔

题意略。

由于保证无论从任何地方出发，最远不超过走10步，那么可以维护10个st表（线段树也行），下标为起点，值为终点。

查询的时候就是看$[L,R]$范围内最小值是否超过查询的$R$即可。

这样暴力预处理st表即可，复杂度$\Theta(nk\log n+q)$。

## 代码

```cpp
#define N 200005
int n, q;
int av[N], mx[N];
vector<pii> lr[11];
int lg2[N];
int st[11][N][30];
int main()
{
	scanf("%d", &n);
	lg2[1] = 0, lg2[2] = 1;
	FOR(i, 3, n)
	lg2[i] = lg2[i / 2] + 1;
	FOR(i, 1, n)
	{
		char ch;
		scanf(" %c", &ch);
		av[i] = ch - '0';
	}
	//preprocess
	FOR(k,1,10)
		FOR(i,1,n)
			st[k][i][0] = INT_MAX;

FOR(i, 1, n)
	for (int hp = 1, j = i; hp > 0 && j <= n && j-i <= 10; j++)
	{
		if (av[j] == 1)
			hp++;
		else
			hp--;
		if (hp == 1)
			st[j - i + 1][i][0] = j;
	}
	//update st-table
	FOR(k, 1, 10)
	FOR(j, 1, lg2[n])
	for (int i = 1; i <= n; i++)
		st[k][i][j] = min(st[k][i][j - 1], st[k][i + (1 << (j - 1))][j - 1]);

scanf("%d", &q);
	while (q--)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		bool flg = true;
		for (int i = 10; i >= 2; i--)
			if (st[i][l][lg2[r-l+1]] <= r || st[i][r - (1 << lg2[r-l+1]) + 1][lg2[r-l+1]] <= r)
			{
				flg = false;
				cout << i << endl;
				break;
			}
		if (flg)
			cout << 0 << endl;
	}
	return 0;
}
```

## 最优做法

其实一张st表就足够了，维护每个点作为起点的最大长度和**所有符合条件区间**。

这样对于询问$[L,R]$，$[L,R-10]$部分一定不会越界，那么直接st表维护就行，然后每次暴力用$(R-10,R]$范围所有区间更新一下答案就行了。这样复杂度是$\Theta(n\log n+q)$。

### 代码

```cpp
#define N 200005
int n, q;
int av[N], mx[N];
vector<pii> lr[11];
int lg2[N];
int st[N][30]; // begin, log(len)
vector<int> g[N];
int main()
{
	scanf("%d", &n);

lg2[1] = 0, lg2[2] = 1;
	FOR(i, 3, n)
	lg2[i] = lg2[i / 2] + 1;

FOR(i, 1, n)
	{
		char ch;
		scanf(" %c", &ch);
		av[i] = ch - '0';
	}

FOR(i, 1, n)
	for (int hp = 1, j = i; hp > 0 && j <= n && j - i <= 10; j++)
	{
		if (av[j] == 1)
			hp++;
		else
			hp--;
		if (hp == 1)
		{
			st[i][0] = j - i + 1;
			g[i].pb(j - i + 1);
		}
	}
	// update st-table
	FOR(j, 1, lg2[n])
	for (int i = 1; i + (1 << j) - 1 <= n; i++)
		st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);

scanf("%d", &q);
	while (q--)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		int ans = 0;
		int len = r - 10 - l + 1;
		if (len > 0)
			ans = max(st[l][lg2[len]], st[r - 10 - (1 << lg2[len]) + 1][lg2[len]]);
		for (int i = max(l, r - 9); i <= r; i++)
		{
			for (auto v : g[i])
				if (i + v - 1 <= r)
					ans = max(ans, v);
				else
					break;
		}
		cout << ans << endl;
	}
	return 0;
}
```

# F 一个很大的数

给出$x$的质因子表示

$$
x=\prod_{i=1}^n{{p_i}^{c_i}}

求它有多少对互质因子？

## 分析

由于已知质因子，考虑每个数字由哪些质因子构成很复杂，那么换个思路：每个质因子能够如何分配给目标因子？显然要么都给其中一个，要么都不给，所以每种因子分配方案数是$2*c_i+1$，然后对此求和即可。

## 代码

```cpp
int t;
#define N 10004
#define M 1000000007
int main()
{
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		ll ans = 1, p, c;
		FOR(i, 1, n)
		{
			cin >> p >> c;
			ans *= 2 * c + 1;
			ans %= M;
		}
		cout<<ans<<endl;
	}
	return 0;
}
```

# G题不会

# H 变换01串

给定一个01串，每次操作可以将某个前缀或后缀全部取反。

要求支持两种操作：

* 将某个子串全部取反
* 询问通过前后缀操作将某个字串变为相同的最少次数

## 分析

维护差分序列即可。每有一个1就需要一次操作，那么可以分块维护差分序列中的1数量。暴力搞搞就行了。

## 代码

还没调出来（sad

若干个小时后：终于调出来了

```cpp
int n, q;
#define N 100005
int a[N], b[N], blk[N];
int sz;
int get(int x)
{
	return x / sz + (bool)(x % sz);
}
void change(int x)
{
	if (x > n || x <= 1)
		return;
	if (b[x] == 1)
	{
		b[x] = 0;
		blk[get(x)]--;
	}
	else
	{
		b[x] = 1;
		blk[get(x)]++;
	}
}
int main()
{
	cin >> n >> q;
	string str;
	cin >> str;
	for (int i = 1; i <= n; i++)
		a[i] = str[i - 1] - '0';
	sz = sqrt(n);
	FOR(i, 2, n)
	if (a[i] != a[i - 1])
		b[i] = 1, blk[get(i)]++;
	while (q--)
	{
		int t, l, r;
		cin >> t >> l >> r;
		if (t == 1)
		{
			int beg = get(l) + 1, ed = get(r) - 1;
			int ans = 0;
			for (int i = beg; i <= ed; i++)
				ans += blk[i];
			if (get(l) == get(r))
			{
				l++;
				for (int i = l; i <= r; i++)
					if (b[i])
						ans++;
			}
			else
			{
				l++;
				for (int i = l; i <= (beg - 1) * sz; i++)
					if (b[i])
						ans++;
				for (int i = ed * sz + 1; i <= r; i++)
					if (b[i])
						ans++;
			}
			cout << ans << endl;
		}
		else
			change(l), change(r + 1);
	}
	return 0;
}
```

## debug：

注意左右端点的特别处理，注意特判单独一个点！！！

# I V字钩爪

一个数组，任意次取$i$和$i+k$的数字，每个数字只能被取一次，问最大取到多少。

注意到每次钩爪所取得的数都是$\%(k+1)$等价类里面的，各个等价类互不干涉，所以按照等价类去分组，就变成连续取数对问题了，偶数个可以全取，奇数个的话，必有一个取不到，且这个取不到的只能是**在这一类里排名奇数的**——因为如果是偶数个，那么它的左右又会变成奇数个的情形，会产生更多不能取的数字。

## 代码

```cpp
int n, k;
#define N 1000006
vector<int> cls[N];
ll ans;
int main()
{
	cin >> n >> k;
	FOR(i,1,n)
	{
		int t;
		cin >> t;
		cls[i % k].pb(t);
		ans += t;
	}
	for (int i = 0; i < k; i++)
		if (cls[i].size() & 1)
		{
			int t = cls[i][0];
			for (int j = 2; j < cls[i].size(); j+=2)
				if (cls[i][j] < t)
					t = cls[i][j];
			ans -= t;
		}
	cout << ans;
	return 0;
}
```