COCR普及赛题解

‮队团加不）童帅_者仇复

2025-04-16 12:50:23

发布于：广东

45阅读

17回复

1点赞

T1

根据组合的定义可知，题目要求的是 $N$ 个数中取 $1$ 个数的方案数。显然答案为 $N$ 。所以直接输出输入的内容即可。

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	string s;
	cin >> s;
	cout << s; 

	return 0;
}

时间复杂度： $O(|N|)$ 。

T2

由题意得，试剂的大小为 $\pi\times h\times (r_0)^2$ ，一个弹珠的大小为 $\dfrac{4\pi}{3}\times (r_1)^3$ 。

设在激活 $x$ 秒以内是安全的。

则可列不等式：

$k^x\times\dfrac{4\pi}{3}\times (r_1)^3\le\pi\times h\times (r_0)^2\\ k^x\times\dfrac{4}{3}\times (r_1)^3\le h\times (r_0)^2\\ k^x\le \frac{\frac{3}{4}h\times (r_0)^2}{(r_1)^3}\\ x\le \log_k^{\frac{4\times h\times (r_0)^2}{3\times (r_1)^3}}.$

注意到 $h,r_0,r_1\le 10^8$ ，记得开 __int128。

#include <iostream>
#include <cstdio>
#include <cmath>
#define int __int128
using namespace std;
void r(int &n){
	signed a;
	cin >> a;
	n = a;
}
void solve(){
	int a, b, c, d;
	r(a), r(b), r(c), r(d);
	int v1 = a * b * b * 3;
	int v2 = d * d * d * 4;
	if(v1 < v2){
		cout << "-1\n";
		return;
	}
	cout << (signed)(logl((long double)v1 / v2) / logl(c)) << '\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	signed t;
	cin >> t;
	while(t--) solve(); 

	return 0;
}

时间复杂度： $O(T)$ 。

T3

水题，看样例解释即可，不做解释。

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << 2 * a + d << ' ' << b + c;

	return 0;
}

时间复杂度： $O(1)$ 。

T4

这难度安排的真不合理啊...

矩阵快速幂板子题。

你可以按照我的巨大的表格题解推理，最终的结果为

$\begin{bmatrix} 1&2&3&5&8\\ 1&0&0&0&0\\ 0&1&0&0&0\\ 0&0&1&0&0\\ 0&0&0&1&0 \end{bmatrix}^{N-5}\times \begin{bmatrix} 1\\1\\1\\1\\1 \end{bmatrix}$

的第一行的数。

注意最后的 $Ans$ 输出形式。

//直接自然溢出毛事没有^_^ 
#include <iostream>
#include <cstdio>
#include <memory.h>
#pragma GCC optimize(3)
using namespace std;
struct Matrix{
	unsigned f[5][5];
	Matrix(){
		memset(f, 0, sizeof(f));
	}
	void setfirst(){
		for(int i = 0; i < 5; i++) f[i][0] = 1;
	}
	void setmul(){
		f[0][0] = 1;
		f[0][1] = 2;
		f[0][2] = 3;
		f[0][3] = 5;
		f[0][4] = 8;
		f[1][0] = 1;
		f[2][1] = 1;
		f[3][2] = 1;
		f[4][3] = 1;
	}
	Matrix operator * (const Matrix &b) const{
		Matrix tmp;
		for(int i = 0; i < 5; i++){
			for(int k = 0; k < 5; k++){
				if(f[i][k] == 0) continue;
				for(int j = 0; j < 5; j++){
					tmp.f[i][j] += f[i][k] * b.f[k][j];
				}
			}
		}
		return tmp;
	}
};
Matrix pow(unsigned long long n){
	Matrix tmp, mul;
	tmp.setfirst(), mul.setmul();
	while(n){
		if(n & 1) tmp = mul * tmp;
		mul = mul * mul, n >>= 1;
	}
	return tmp;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--){
		unsigned long long n;
		cin >> n;
		if(n <= 5){
			cout << "1\n";
			continue;
		}
		auto ans = pow(n - 5).f[0][0];
		if(ans > 2147483647) cout << ans - 4294967296ll << '\n';
		else cout << ans << '\n'; 
	}

	return 0;
}

时间复杂度： $O(T\times K^3\log N)$ ，其中 $K=5$ 。

T5

我有一种绝妙的方法，但这里空太小，写不下。

T6

唯一真史。

这题又是模板套模板，难度叠难度，只要会模板就行。

游戏1

优先队列广搜模板。

namespace Game1{
	struct node{
		int x, y, val;
		bool operator < (const node &b) const{
			return val > b.val;
		}
	};
	bool vis[1005][1005];
	int dir[4][2]{-1, 0, 0, -1, 0, 1, 1, 0};
	priority_queue <node> q;//使用优先队列
	int solve(){
		q.push({1, 1, a[1][1]});
		while(!q.empty()){
			node head = q.top();
			q.pop();
			if(head.x == n && head.y == m) return head.val;
			for(int i = 0; i < 4; i++){
				int xx = head.x + dir[i][0];
				int yy = head.y + dir[i][1];
				if(xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy]) continue;
				vis[xx][yy] = 1;
				q.push({xx, yy, head.val + a[xx][yy]});
			}
		}
	}
}

时间复杂度： $O(N\times M\log (N\times M))$ 。

游戏2

马拉车模板。懒得学了，直接复制。

namespace Game2{
	const int maxn=500005;
	char data[maxn<<1];
	int p[maxn<<1],cnt,ans;
	inline void qr(){
	      data[0]='~',data[cnt=1]='|';
	      for(char c:t) data[++cnt]=c,data[++cnt]='|';
	}
	int solve(){//不演了 
		qr();
		for(int t=1,r=0,mid=0;t<=cnt;++t){
		    if(t<=r) p[t]=min(p[(mid<<1)-t],r-t+1);
		    while(data[t-p[t]]==data[t+p[t]]) ++p[t];
		    //暴力拓展左右两侧,当t-p[t]==0时，由于data[0]是'~'，自动停止。故不会下标溢出。
		    //假若我这里成功暴力扩展了，就意味着到时候r会单调递增，所以manacher是线性的。
		    if(p[t]+t>r) r=p[t]+t-1,mid=t;
		    //更新mid和r,保持r是最右的才能保证我们提前确定的部分回文半径尽量多。
		    if(p[t]>ans) ans=p[t];
	      }
		
		return ans - 1;
	}
}

时间复杂度： $O(|t|)$ 。

游戏3

最简单的一个游戏。

我们把 $s$ 分成前后两半，把后半部分反转，如果两半中某一位置的字符不同，就加上花费的最小值。

namespace Game3{
	string s1, s2;
	vector <int> cost1, cost2;
	int solve(){
		int len = s.size() / 2;
		for(int i = 0; i < len; i++){//正者存储前半段
			s1.push_back(s[i]);
			cost1.push_back(costs[i]);
		}
		for(int i = s.size() - 1; i >= s.size() - len; i--){//倒着存储后半段
			s2.push_back(s[i]);
			cost2.push_back(costs[i]);
		}
		int ans = 0;
		for(int i = 0; i < s1.size(); i++){
			if(s1[i] != s2[i]){//如果不同就加上花费的最小值
				ans += min(cost1[i], cost2[i]);
			}
		}
		return ans;
	}
}

时间复杂度： $O(s)$ 。

总代码如下：

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
int a[1005][1005];
string s, t;
int n, m;
int costs[500005];
namespace Game1{
	struct node{
		int x, y, val;
		bool operator < (const node &b) const{
			return val > b.val;
		}
	};
	bool vis[1005][1005];
	int dir[4][2]{-1, 0, 0, -1, 0, 1, 1, 0};
	priority_queue <node> q;
	int solve(){
		q.push({1, 1, a[1][1]});
		while(!q.empty()){
			node head = q.top();
			q.pop();
			if(head.x == n && head.y == m) return head.val;
			for(int i = 0; i < 4; i++){
				int xx = head.x + dir[i][0];
				int yy = head.y + dir[i][1];
				if(xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy]) continue;
				vis[xx][yy] = 1;
				q.push({xx, yy, head.val + a[xx][yy]});
			}
		}
	}
}
void add(string &s, int n){
	string tmp;
	while(n){
		tmp.push_back(n % 10);
		n /= 10;
	}
	reverse(tmp.begin(), tmp.end());
	for(char c:tmp){
		if(!c){
			s.push_back(s.back());
		}else{
			s.push_back(c + 'a' - 1);
		}
	}
}
namespace Game2{
	const int maxn=500005;
	char data[maxn<<1];
	int p[maxn<<1],cnt,ans;
	inline void qr(){
	      data[0]='~',data[cnt=1]='|';
	      for(char c:t) data[++cnt]=c,data[++cnt]='|';
	}
	int solve(){//不演了 
		qr();
		for(int t=1,r=0,mid=0;t<=cnt;++t){
		    if(t<=r) p[t]=min(p[(mid<<1)-t],r-t+1);
		    while(data[t-p[t]]==data[t+p[t]]) ++p[t];
		    //暴力拓展左右两侧,当t-p[t]==0时，由于data[0]是'~'，自动停止。故不会下标溢出。
		    //假若我这里成功暴力扩展了，就意味着到时候r会单调递增，所以manacher是线性的。
		    if(p[t]+t>r) r=p[t]+t-1,mid=t;
		    //更新mid和r,保持r是最右的才能保证我们提前确定的部分回文半径尽量多。
		    if(p[t]>ans) ans=p[t];
	      }
		
		return ans - 1;
	}
}
namespace Game3{
	string s1, s2;
	vector <int> cost1, cost2;
	int solve(){
		int len = s.size() / 2;
		for(int i = 0; i < len; i++){
			s1.push_back(s[i]);
			cost1.push_back(costs[i]);
		}
		for(int i = s.size() - 1; i >= s.size() - len; i--){
			s2.push_back(s[i]);
			cost2.push_back(costs[i]);
		}
		int ans = 0;
		for(int i = 0; i < s1.size(); i++){
			if(s1[i] != s2[i]){
				ans += min(cost1[i], cost2[i]);
			}
		}
		return ans;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	cin >> s >> t;
	int ans = Game1::solve();
	//cout << ans;
	add(s, ans);
	t += s;
	for(char &c:s) c = c % 2 + '0';
	for(char &c:t) c = c % 2 + '0';
	for(int i = 0; i < s.size(); i++) cin >> costs[i];
	cout << Game2::solve() + Game3::solve();

	return 0;
}

本题数据有误，导致我的正确解法无法通过。

有帮助，赞一个

去预览

0/2000

全部评论 5

key0213
"我有一种绝妙的方法，但这里空太小，写不下。"
想起了费马小定理的故事

1周前来自福建
1
- ‮队团加不）童帅_者仇复
  回复key0213
  你说的应该是费马大定理吧
  费马小定理是 $a^x\equiv a^{x\mod (p-1)}(\mod p)$
  
  1周前来自广东
  0
- key0213
  回复‮队团加不）童帅_者仇复
  哦
  
  1周前来自福建
  0
key0213
D

4天前来自福建
0
key0213
d

6天前来自福建
0
key0213
d

1周前来自福建
0
‮队团加不）童帅_者仇复
顶

1周前来自广东
0
- 不会C++的noah
  回复‮队团加不）童帅_者仇复
  有意思的是，这次数据我一点没出
  
  1周前来自浙江
  0
- 不会C++的noah
  回复‮队团加不）童帅_者仇复
  但更加有意思的是，我刚刚产了依托大的和一个好的
  
  1周前来自浙江
  0
- ‮队团加不）童帅_者仇复
  回复不会C++的noah
  666最好是
  
  1周前来自广东
  0

T1

T2

T3

T4

T5

T6

游戏1

游戏2

游戏3

全部评论 5

热门讨论