COCR 入门赛#1 T1-T5题解！

复仇者_帅童

2025-01-08 14:46:42

发布于：广东

37阅读

0回复

0点赞

个人难度： $\color{red}1.2\color{black},\color{red}1.1\color{black},\color{orange}2.3\color{black},\color{orange}2.5\color{black},\color{yellow}3.9\color{black},\color{green}4.3$ （数字越大代表难度越高，其中 $2.0$ 为红橙分界线， $3.0$ 为橙黄分界线， $4.0$ 为黄绿分界线）.

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)$ ），自行尝试.

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$ ：

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

$B$ ：

可以由上一个 $B$ 填上 $3,5,7$ 中的两个数字获得，情况数 $\times 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;
}