点击跳转比赛

前言

本次竞赛难度T1、T2难度为简单，T3、T4难度为中档，T5、T6难度为困难.各位选手可以通过这次竞赛摸底自己的实力.

---

下面是正文题解部分：

T1 这是一种病：字符串模拟

点击跳转

模拟，判断有没有 APT 在其中就行.

#include <iostream>
#include <cstdio>
using namespace std;
int a[100005];
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        if(s.find("APT") != string::npos) cout << "YES\n";//寻找APT
        else cout << "NO\n";
    }

	return 0;
}

时间复杂度：$O(|S|)$

---

T2 找到最小值：函数化简

点击跳转

推一下式子， $F(a,b)=a-c-c-b+2c=a-b$，所以函数的值为 $a,b$ 的差，与 $c$ 无关.

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[100005];
signed main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        cout << n - m << '\n';
    }

	return 0;
}

对于每次询问，时间复杂度：$O(1)$.

---

T3 规律数列：高精递推

点击跳转

显然规律是将上一个数+3,*3,+3,*3...

结果太大了，用 long long 也存不下.

我们可以尝试用数组模拟+3和*3操作.

但是如果每次查询都进行 $N$ 次运算就浪费太大了.

我们可以预处理，这样每次查询就只需要直接输出答案了.

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
struct bigInt{
	int a[1005];
	int len;
	bigInt(){
		memset(a, 0, sizeof(a));
		a[1] = 1;//第一位设为1 
		len = 1;
	}
	void print(){
		for(int i = len; i >= 1; i--) cout << a[i];
		cout << '\n';
	}
	void add_3(){
		a[1] += 3;//末位加3 
		for(int i = 1; i <= len; i++){
			if(a[i] >= 10){//逐位进位 
				if(i == len) len++;//首位进位要把位数+1 
				a[i + 1]++;
				a[i] -= 10;
			}
		}
	}
	void mul_3(){
		for(int i = 1; i <= len; i++){
			a[i] *= 3;//给每个位都乘3 
		}
		for(int i = 1; i <= len; i++){
			a[i + 1] += a[i] / 10;//逐位进位 
			a[i] %= 10;
		}
		if(a[len + 1]) len++;//首位进位要把位数+1 
	}
}a[1005];
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	for(int i = 2; i <= 1000; i++){//预处理
		a[i] = a[i - 1];
		if(i % 2 == 0) a[i].add_3();
		else a[i].mul_3();
	}
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		a[n].print();
	}

	return 0;
}

对于预处理，时间复杂度：$O(N^2)$.

对于每次查询，时间复杂度：$O(N)$.

总时间复杂度：$O(TN+N^2)$.

---

T4 废品回收：贪心策略

点击跳转

贪心，将价值减去价格，每次挑选最大的即可（注意！不需要拿满 $k$ 件！如果处理这个废品后的收益小于等于 $0$ 就不要再拿了）

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm> 
using namespace std;
vector <int> a, b;
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		char c;
		int x, y;
		cin >> c >> x >> y;
		if(c == 'A') a.push_back(x - y);
		else b.push_back(x - y);
	}
	sort(a.begin(), a.end(), greater <int>());//排序，这样就能挑最大的
	sort(b.begin(), b.end(), greater <int>());
	int ct = 0;
	for(int i = 0; i < m && i < a.size() && a[i] > 0; i++) ct += a[i];//拿取
	for(int i = 0; i < m && i < b.size() && b[i] > 0; i++) ct += b[i];
	cout << ct;

	return 0;
}

时间复杂度：$O(N\log N)$.

当然，你也可以使用堆来实现在线得出最优解（$O(N\log N)$），或者用背包DP（$O(N\times V_i)$），以下给出背包DP的代码：

#include<bits/stdc++.h>
using namespace std;
int A_v[1005],B_v[1005];
bool cmp(int a,int b){return a > b;}
int main(){
    int n,k; cin >> n >> k;
    int A_idx = 1,B_idx = 1;
    while(n--){
        char op; cin >> op;
        int v,p; cin >> v >> p;
        if(op == 'A') A_v[A_idx++] = v - p;
        else B_v[B_idx++] = v - p;
    }
    sort(A_v + 1,A_v + A_idx + 1,cmp);
    sort(B_v + 1,B_v + B_idx + 1,cmp);
    long long ans = 0;
    for(int i = 1;i <= k;i++){
        if(A_v[i] > 0) ans += A_v[i];
        else break;
    }
    for(int i = 1;i <= k;i++){
        if(B_v[i] > 0) ans += B_v[i];
        else break;
    }
    cout << ans;
    return 0;
}

---

T5 计数改良：组合数学

点击跳转

20pts

深搜，参考下面的代码.

#include <iostream>
#include <cstdio>
using namespace std;
int n;
int dfs(int ct, bool a, bool b, bool c){//a代表有没有3，b代表有没有5，c代表有没有7 
	if(ct > n) return (a && b && c);
	return dfs(ct + 1, 1, b, c) + dfs(ct + 1, a, 1, c) + dfs(ct + 1, a, b, 1);
}
int main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	int t;
	cin >> t;
	while(t--){
		cin >> n;
		cout << dfs(1, 0, 0, 0) << '\n';
	}

	return 0;
}

对于每次查询，时间复杂度：$O(3^N)$.

---

40pts

我们发现前四个测试点答案也就不超过 $15$ 种，考虑记忆化.

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int n;
const int mod = 1e9 + 7;
int ans[1005];
int dfs(int ct, bool a, bool b, bool c){//a代表有没有3，b代表有没有5，c代表有没有7 
	if(ct > n) return (a && b && c);
	return (dfs(ct + 1, 1, b, c) + dfs(ct + 1, a, 1, c) + dfs(ct + 1, a, b, 1)) % mod;
}
signed main(){
	cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	int t;
	cin >> t;
	while(t--){
		cin >> n;
		if(ans[n]) cout << ans[n] << '\n';//记忆化
		else cout << (ans[n] = dfs(1, 0, 0, 0)) << '\n';
	}

	return 0;
}

对于每次查询，时间复杂度：$O(1)$ 或 $O(3^N)$.

总时间复杂度：$O(3^N)$.

---

100pts

既然最终答案能记忆化，那能不能每个过程都记忆化一遍呢？

我们可以记录第 $i$ 位每种 $357$​ 出现情况的种类数，分类讨论.

将 $357$ 都出现的情况记作 $A$，将 $357$ 出现两个的情况记作 $B$，将 $357$ 出现一个的情况记作 $C$.

$A$：

1. 可以由上一个 $A$ 填上 $3,5,7$ 获得，情况数 $\times 3$.
2. 可以由上一个 $B$ 填上所缺的数获得.

$B$：

1. 可以由上一个 $B$ 填上 $3,5,7$ 中的两个数字获得，情况数 $\times 2$.
2. 可以由上一个 $C$ 填上所缺的数获得.

$C$：

可以由一个都没有获得.

#include <iostream>
#include <cstdio>
using namespace std;
const int mod = 1e9 + 7;
int dp[10000005][8];
signed main(){
    cin.tie(nullptr) -> sync_with_stdio(0);
	cout.tie(nullptr) -> sync_with_stdio(0);
	dp[0][0] = 1;
    for(int i = 1; i <= 10000000; i++){
		for(int j = 1; j <= 7; j++){
			dp[i][j] = 1ll * __builtin_popcount(j) * dp[i - 1][j] % mod;//由上一个相同的
			if(j & 1) dp[i][j] = (dp[i][j] + dp[i - 1][j ^ 1]) % mod;//无 -> C
			if(j & 2) dp[i][j] = (dp[i][j] + dp[i - 1][j ^ 2]) % mod;//C -> B
			if(j & 4) dp[i][j] = (dp[i][j] + dp[i - 1][j ^ 4]) % mod;//B -> A
		}
	}
    int t;
    cin >> t;
    while(t--){
        int n;
    	cin >> n;
    	cout << dp[n][7] << endl;
    }
	return 0;
}

对于每次查询，时间复杂度：$O(1)$.

预处理时间复杂度：$O(N)$.

总时间复杂度：$O(N)$​.

如果你嫌内存占用太大了，你可以多花费 $O(T\log T)$ 的时间复杂度转离线，把空间复杂度降至 $O(1)$.

---

120pts

Macw老师提出来一个快速的办法，理论上可以通过 $T=1,N\le 10^{10^7}$ 的数据！

首先是随便选取 $357$ 中的任意一位，总共有 $3^N$ 种情况.

然后减去只选择两个数的，即只选 $35$ 的，只选 $37$ 的和只选 $57$ 的，共有 $3\times 2^N$ 种情况.

我们发现只选一个数的情况多选了一次，所以需要加回，即将结果 $+3$.

这样就可以以 $O(\log N)$ 的时间复杂度求出答案了！

我们注意到 $10^9+7$ 与 $2,3$ 均互质，所以对于更大的数可以用费马小定理来将 $N$ 降至 $10^9+5$ 以内.

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int pow(int n, int k){//快速幂
	int ans = 1;
	while(k){
		if(k & 1) ans = ans * n % mod;
		n = n * n % mod, k >>= 1;
	}
	return ans;
}
signed main(){
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		if(n < 3) cout << "0\n";//特判不足3的
		else cout << ((pow(3, n) - pow(2, n) * 3 % mod + 3) % mod + mod) % mod << '\n';//计算结果
	}
	
	return 0;
}

对于每次查询，时间复杂度：$O(\log N)$​.

---

T6 加固：多维动态规划

点击跳转

这道题得90分的同学大多就是因为没有特判n = 1 的情况，这次也算是提醒了大家看测试点数据的重要性了。

下面给出 $2$ 种对于这道题的解法：

$A$：三维动态规划

在这个问题中，我们需要最大化在森林环形结构中小猪家园存活后保留的金币总数。由于家园是环形的，每个小猪有两个邻居，强化一个小猪的家会从其两个邻居那里各拿走 c 个金币。我们的目标是决定哪些小猪的家应该被强化，使得在攻击后幸存的家园中的金币总数最大.

为了解决这个问题，我们可以使用动态规划（DP）。我们需要记录到当前小猪为止，考虑强化或不强化当前小猪时，能够获得的最大金币数。由于问题涉及环形结构，我们可以将其转化为线性问题，通过两次DP处理来解决.

动态规划状态定义

我们使用三维数组 dp[i][j][k] 来表示状态，其中：

• i 表示当前考虑到第 i 只小猪.
• j 表示第 i-1 只小猪是否被强化（0 表示未强化，1 表示强化）.
• k 表示第 i 只小猪是否被强化（0 表示未强化，1 表示强化）.

状态转移方程

• 如果第 i 只小猪不强化 (k = 0)：
  • 如果第 i-1 只小猪强化 (j = 1)：dp[i][0][0] = max(dp[i-1][1][0], dp[i-1][1][1] - 2*c)
  • 如果第 i-1 只小猪不强化 (j = 0)：dp[i][0][0] = max(dp[i-1][0][0], dp[i-1][0][1])
  • 加上第 i 只小猪的初始金币：dp[i][0][0] += a[i]
• 如果第 i 只小猪强化（k = 1）：
  • 如果第 i-1 只小猪强化 (j = 1)：dp[i][1][0] = max(dp[i-1][1][0] - 2*c, dp[i-1][0][0]) - 2*c
  • 如果第 i-1 只小猪不强化 (j = 0)：dp[i][1][0] = max(dp[i-1][0][0], dp[i-1][0][1]) - 2*c
  • 加上第 i 只小猪的初始金币：dp[i][1][0] += a[i]

注意：这里的 dp[i][1][0] 应该是 dp[i][1][1]，因为我们在考虑第 i 只小猪强化的情况.

修正后的状态转移方程为：

• dp[i][0][0] = max(dp[i-1][1][0], dp[i-1][0][0]) + a[i]
• dp[i][0][1] = max(dp[i-1][1][1] - 2*c, dp[i-1][0][1]) + a[i]
• dp[i][1][0] = max(dp[i-1][1][0] - 2*c, dp[i-1][0][0]) - 2*c + a[i] (这种情况实际不会用到，因为 k 表示当前小猪的强化状态)
• dp[i][1][1] = max(dp[i-1][1][1] - 2*c, dp[i-1][0][1]) - 2*c + a[i]

由于我们只关心最后一只小猪之前的状态，并且我们最终需要的结果是在第 n 只小猪考虑强化或不强化时的最大值，所以最终答案应该从 dp[n][0][0], dp[n][0][1], dp[n][1][0] (这里实际上不需要考虑，因为最终小猪不能单独强化而不考虑最后一个邻居), dp[n][1][1] - 2*c (如果第 n 只小猪强化，并且考虑从第 1 只小猪不再拿走金币的情况) 中选取.

边界条件

• 初始化 dp[1][...] 时，由于第 0 只小猪不存在（环形结构），我们需要单独处理第一只小猪的情况.

#include<bits/stdc++.h>
using namespace std;
long long a[200010],n,c;
long long dp[200010][2][2];
int main(){
    cin >> n >> c;
    for(long long i = 1;i <= n;i++) cin >> a[i];
    dp[1][1][1] = a[1];
    dp[1][0][1] = dp[1][1][0] = -0x3f3f3f3f;
    dp[1][0][0] = 0;
    for(long long i = 2;i <= n;i++){
        dp[i][0][0] = max(dp[i - 1][1][0],dp[i - 1][0][0]);
        dp[i][0][1] = max(dp[i - 1][1][1],dp[i - 1][0][1]);
        dp[i][1][0] = max(dp[i - 1][1][0] - 2 * c,dp[i - 1][0][0]) + a[i];
        dp[i][1][1] = max(dp[i - 1][1][1] - 2 * c,dp[i - 1][0][1]) + a[i];
    }
    long long ans = 0;
    ans = max(ans,max(dp[n][0][1],dp[n][0][0]));
    ans = max(ans,dp[n][1][0]);
    ans = max(ans,dp[n][1][1] - 2 * c);
    cout << ans;
    return 0;
}

时间复杂度：$O(N)$.

---

$B$：二维动态规划

这种解法是我通过观察Macw老师的代码想到的（真是太妙啦！）.

在这个问题中，我们需要最大化在森林环形结构中小猪家园存活后保留的金币总数。由于家园是环形的，每个小猪有两个邻居，且强化一个小猪的家会从其两个邻居那里各拿走 m 个金币（题目中的 c 在此解答中用 m 表示，以与代码一致）。我们的目标是决定哪些小猪的家应该被强化，使得在攻击后幸存的家园中的金币总数最大。

由于问题涉及环形结构，直接应用动态规划（DP）会比较复杂。为了简化问题，我们可以将环形结构拆分为两个线性问题：

1. Case A：假设不强化第1只小猪的家园。
2. Case B：假设强化第1只小猪的家园。

对于每种情况，我们可以使用动态规划来计算到第 n 只小猪时能够获得的最大金币数。

动态规划状态定义

我们使用二维数组 dp[i][j] 来表示状态，其中：

• i 表示当前考虑到第 i 只小猪。
• j 表示第 i 只小猪是否被强化（0 表示未强化，1 表示强化）。

状态转移方程

• 如果第i只小猪不强化 (j = 0)：
  • dp[i][0] = max(dp[i-1][0], dp[i-1][1])
• 如果第i只小猪强化 (j = 1)：
  • dp[i][1] = max(dp[i-1][0] + a[i], dp[i-1][1] + a[i] - 2*m)

其中，a[i] 表示第 i 只小猪家里初始的金币数。

边界条件

• 对于Case A：
  • dp[1][0] = 0（不强化第1只小猪）
  • dp[1][1] = -∞（禁用强化第1只小猪的情况）
• 对于Case B：
  • dp[1][0] = -∞（禁用不强化第1只小猪的情况）
  • dp[1][1] = a[1]（强化第1只小猪）

考虑环形特性

在 Case B 中，由于我们假设强化了第1只小猪，当计算到第 n 只小猪时，还需要考虑从第 n 只小猪到第1只小猪的额外金币扣除（因为它们是邻居）。但由于我们是线性处理，这个额外的扣除已经在 dp[n][1] 的计算中隐含处理了（即如果第 n 只小猪也强化，那么从 dp[n-1][1] 到 dp[n][1] 的转移已经扣除了 2m）。因此，在最终比较 Case A 和 Case B 的结果时，不需要再额外处理环形特性。

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

static const long long NEG_INF = - (1LL << 60);

long long solveCaseA(int n, long long m, const vector<long long> &a)
{
    // Case A：固定“不选 1 号”
    // dp[i][0] = 考虑到第 i 只小猪，且第 i 只不加固时的最大收益
    // dp[i][1] = 考虑到第 i 只小猪，且第 i 只被加固时的最大收益

    vector<vector<long long>> dp(n+1, vector<long long>(2, NEG_INF));
    // 不选 1 号
    dp[1][0] = 0;      // 不加固 1 号
    dp[1][1] = NEG_INF; // “加固 1 号”这条路径在 Case A 里直接禁用

    for (int i = 2; i <= n; i++)
    {
        // i 不加固
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]);

        // i 被加固
        // 若 i-1 不加固
        long long candidate1 = dp[i-1][0] + a[i];
        // 若 i-1 也加固，则要多扣 2m
        long long candidate2 = dp[i-1][1] + a[i] - 2LL*m;
        dp[i][1] = max(candidate1, candidate2);
    }

    // 返回末尾的最大值
    return max(dp[n][0], dp[n][1]);
}

long long solveCaseB(int n, long long m, const vector<long long> &a)
{
    // Case B：固定“选了 1 号”
    // 同样的 DP 定义
    vector<vector<long long>> dp(n+1, vector<long long>(2, NEG_INF));

    // 1 号被加固
    dp[1][0] = NEG_INF; 
    dp[1][1] = a[1];   // 选了 1 号，收益为 a[1]

    for (int i = 2; i <= n; i++)
    {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
        long long candidate1 = dp[i-1][0] + a[i];
        long long candidate2 = dp[i-1][1] + a[i] - 2LL*m;
        dp[i][1] = max(candidate1, candidate2);
    }

    // 若第 n 号也加固，则因为它与 1 号相邻，多扣 2m
    // 因此要取 max(dp[n][0], dp[n][1] - 2m)
    long long ansWhenNChosen = dp[n][1] - 2LL*m;
    return max(dp[n][0], ansWhenNChosen);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long m;
    cin >> n >> m;


    // 小猪的编号从 1 到 n，为了方便和上面 DP 的下标对应
    vector<long long> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    // 分两种情况
    if(n == 1){
        cout << 0 << endl;
        return 0;
    }

    long long ansA = solveCaseA(n, m, a);
    long long ansB = solveCaseB(n, m, a);
    cout << max(ansA, ansB) << "\n";
    
    return 0;
}

时间复杂度：$O(N)$.

---

希望各位能在期末考试中获得一个好成绩！