COCR普及赛题解
2025-04-16 12:50:23
发布于：广东
53阅读
0回复
0点赞
T1
根据组合的定义可知，题目要求的是 个数中取 个数的方案数。显然答案为 。所以直接输出输入的内容即可。
#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;
}
时间复杂度：。
T2
由题意得，试剂的大小为 ，一个弹珠的大小为 。
设在激活 秒以内是安全的。
则可列不等式：
注意到 ，记得开 __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;
}
时间复杂度：。
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;
}
时间复杂度：。
T4
这难度安排的真不合理啊...
矩阵快速幂板子题。
你可以按照我的巨大的表格题解推理，最终的结果为
的第一行的数。
注意最后的 输出形式。
//直接自然溢出毛事没有^_^
#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;
}
时间复杂度：，其中 。
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]});
}
}
}
}
时间复杂度：。
游戏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;
}
}
时间复杂度：。
游戏3
最简单的一个游戏。
我们把 分成前后两半，把后半部分反转，如果两半中某一位置的字符不同，就加上花费的最小值。
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;
}
}
时间复杂度：。
总代码如下：
#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;
}
本题数据有误，导致我的正确解法无法通过。
有帮助，赞一个