2022.11.20

T2：

首先看出，答案肯定与 \(X\) 有关, 所以肯定有一层循环用来枚举 \(X\)

然后考虑每个州对答案的贡献，只会是某个兵种的范围

所以需要求出当前 \(X\) 下，某个兵种的范围，下面以步兵为例

\(O(n)\) 求出步兵的上界，需要求步兵的下界，显然步兵的下界就是 总数 - 空军的上界，所以还需要维护空军的上界

最后答案加上步兵上界和下界的范围即可

复杂度 \(O(n * k)\)

代码如下：

/*

　　　　　／＞　   フ
　　　　　| 　_　 _|
　 　　　／`ミ _x 彡
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

*/
#include<bits/stdc++.h>
using namespace std;

long long read()
{
    long long x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

int n;

int a[5010], b[5010], k = 0x3f3f3f3f;

long long ans;

int main()
{
	n = read();
	for(int i = 1; i <= n; i++)
	{
		a[i] = read();
		b[i] = read();
		k = min(k, a[i] + b[i]);
	}
	for(int i = 1; i <= k; i++)
	{
		int maxlu = 0, maxkong = 0;
		for(int j = 1; j <= n; j++)
		{
			maxlu += min(a[j], i);
			maxkong += min(b[j], i);
		}
		int minlu = n * i - maxkong;
		ans += maxlu - minlu + 1;
	}
	cout << ans << "\n";
    return 0;
}

T3

很明显是块状链表的裸题(可惜考试之前没学过不会用，写了个50分的普通链表)

下面介绍一下块状链表：传送门

很显然每次给出的 \(l\), \(r\)。

要让原来的链表变成 \(1\) ~ \(l\) + \(l\) ~ \(r\) + \(l\) ~ \(n\)

最后长度会超过 \(n\),需要把多余的部分删去只留下 \(1\) ~ \(n\)。

代码如下

/*

　　　　　／＞　   フ
　　　　　| 　_　 _|
　 　　　／`ミ _x 彡
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

*/
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;

long long read()
{
    long long x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

rope <int> x; 

int n, q;

int main()
{
	n = read(), q = read();
	x.push_back(0);
	for(int i = 1; i <= n; i++)
	{
		int a = read();
		x.push_back(a);
	}
	while(q--)
	{
		int op = read();
		if(op == 1)
		{
			int l = read(), r = read();
			x = x.substr(x.begin(), x.begin() + l) + x.substr(x.begin() + l, x.begin() + r + 1) + x.substr(x.begin() + l, x.end());
			if(x.length() > n + 1) x = x.substr(x.begin(), x.begin() + 1 + n);
		}
		else
		{
			int k = read();
			cout << x[k] << "\n";
		}
	}
    return 0;
}