COCR 入门赛#1 T1-T6题解
2025-01-11 11:33:25
发布于：浙江
T1
(本题数据较小，可以直接暴力枚举）
设字符串为S,字符串长度为n，枚举i=0至n-3,若s[i] == 'A' && s[i+1] == 'P' && s[i+2] == 'T'，则符合“这是一种病”。
#include<bits/stdc++.h>
using namespace std;
int t;
string s;
void solve(){
for(int i=0;i<s.size()-2;i++){
if(s[i]=='A' && s[i+1]=='P' && s[i+2]=='T'){
cout<<"YES\n";
return ;
}
}
cout<<"NO\n";
}
int main(){
cin>>t;
while(t--){
cin>>s;
solve();
}
}
（可以写一个函数，会更简单）
（不要忘了换行和输出为大写）
T2
F(a,b)=(a−c)−(c+b)+2c
如果你上过小学二年级，就知道F=a-b
直接输出就好
#include<bits/stdc++.h>
using namespace std;
int t;
long long a,b;
int main(){
cin>>t;
while(t--){
cin>>a>>b;
cout<<a-b<<endl;
}
return 0;
}
（注意数据范围，要开 long long；不要忘了换行）
T3
l=1,4,12,15,45,48,144,…
读题得,l[0]=1,若i>0 && i%2==-1,则l[i]=l[i-1]+3,若i>0 && i%2==0,则l[i]=l[i]*3;
T<=10^4 , n<=10^3
可以用O(Tn)直接暴力，但是......ans大概率会爆long long（因为ans可以大概算是3^(n/2))
所以直接用高精度乘法和除法（即用string存数字）
普通版:
#include<bits/stdc++.h>
using namespace std;
int t,n;
//此处S[0]是个位，以此类推
string s;
void add(){
int num=3;
for(int i=0;i<s.size();i++){
if(!num) return ;
if(s[i]+num>'9'){
s[i]+=num-10;
num=1;
}
else{
s[i]+=num;
num=0;
}
}
if(num) s+='1';
return ;
}
void multiply(){
int num=0;
for(int i=0;i<s.size();i++){
int x=s[i]-48;
x*=3;
x+=num;
num=x/10;
x%=10;
//不要忘了转成char
s[i]=x+48;
}
if(num) s+=num+48;
return ;
}
void solve1(){
int cnt=1;
long long ans=1;
while(n--){
if(cnt%2) ans+=3;
else ans*=3;
cnt++;
}
cout<<ans;
return ;
}
void solve2(){
int cnt=1;
s="1";
while(n--){
// cout<<s<<" ";
if(cnt%2) add();
else multiply();
cnt++;
}
//倒着输出
for(int i=s.size()-1;i>-1;i--) cout<<s[i];
return ;
}
int main(){
cin>>t;
while(t--){
cin>>n;
//因为此处本人ans初始值为1,所以操作次数减一
n--;
//数据范围较小，普通做法
if(n<50) solve1();
//数据范围较大，高精度
else solve2();
cout<<endl;
}
return 0;
}
极简版：
#include<bits/stdc++.h>
using namespace std;
int t,n;
//此处S[0]是个位，以此类推
string s;
//num:余数 cnt:若是加法则为1(*=1),乘法则为3(*=3)
void multiply(int num,int cnt){
for(int i=0;i<s.size();i++){
//若为加法且不用进位了,则直接结束
if(cnt==1 && !num) return ;
int x=s[i]-48;
x*=cnt;
x+=num;
num=x/10;
x%=10;
//不要忘了转成char
s[i]=x+48;
}
if(num) s+=num+48;
return ;
}
void solve2(){
int cnt=1;
s="1";
while(n--){
// cout<<s<<" ";
if(cnt%2) multiply(3,1);
else multiply(0,3);
cnt++;
}
//倒着输出
for(int i=s.size()-1;i>-1;i--) cout<<s[i];
return ;
}
int main(){
cin>>t;
while(t--){
cin>>n;
//因为此处本人ans初始值为1,所以操作次数减一
n--;
solve2();
cout<<endl;
}
return 0;
}
我因为一开始没有看数据范围，然后就错了一次,www
T4
本题很简单。但题目有点问题。
“利用有限的空间回收最有价值k的件废品（即件数≤k ）"
"输出仅一行一个整数，表示A,B 种类废品各拿取k件后的最优结果价值"
根据题意，每件物品的实际价值为v-p，可以直接排个序然后求answer
#include<bits/stdc++.h>
using namespace std;
int n,sum,ans;
priority_queue<int> q[2];
int main(){
cin>>n>>sum;
while(n--){
char k;
int v,p;
cin>>k>>v>>p;
q[k-65].push(v-p);
}
for(int i=0;i<2;i++){
int cnt=sum;
while(cnt-- && !q[i].empty() && q[i].top()>0){
ans+=q[i].top();
q[i].pop();
}
}
cout<<ans;
return 0;
}
(每种废品不超过k件，若一件废品价格<0,则肯定不选）
此处使用的是优先队列（由题意得，sort等其他排序方法皆可)
T5
由题意得:
(若n<3 ans=0)
设sum为n位数字中只由3、5、7组成（3、5、7不需要只出现一次）的数字的个数。
设a为n位数字中只由3、5组成（3、5、7不需要只出现一次）的数字的个数。
设b为n位数字中只由3、7组成（3、5、7不需要只出现一次）的数字的个数。
设c为n位数字中只由5、7组成（3、5、7不需要只出现一次）的数字的个数。
若你像我一样是初二的学生，则知sum=3^n , a=b=c=2^3;
如果你再聪明一点，就知道answer=sum-(a+b+c)-3
For exemple:
如图所示，未被划线的则是题目中所规定的357数
所以ans=n-a-b-c+3(a,b,c为sum种可能中不合格的可能，333、555、777都被画了也就是减两次，所以要加回来）
我们可以运用快速幂来求解
(快速幂的原理是x^(2 * y) = (x^y) ^2 )
#include<bits/stdc++.h>
using namespace std;
int t;
long long n;
long long p=1e9+7;
long long power(long long a,long long b){
if(b==0) return 1;
long long t=power(a,b/2);
if(b%2==0) return t*t%p;
return t*t%p*a%p;
}
int main() {
cin>>t;
while(t--){
cin>>n;
cout<<(power(3,n)-3*power(2,n)+3+100*p)%p<<endl;
}
return 0;
}
注意，n要开long long ,且 power(3,n)-3power(2,n)+3可能为负数，所以要进行操作来使其成为非负数(只+p是不行的，因为power(3,n)-3power(2,n)+3可以达到-3e9+4)
我因此错了好几遍,yyy
T6
这道题应该可以用贪心或动态规划来解决,我这里用的是动态规划
因为房子是环形分布的，所以第一个房子难以确定它的初始值（我认为），于是可以分四类来讨论:
1、第一个和最后一个都选选
2、选第一个不选最后一个
3、选最后一个不选第一个
4、最后一个和第一个都不选
应为就这四类，所以可以直接写
l[i]:第i只小猪家的的初始初始金币,a[i]:加固第i只小猪家后的所得金币,b[i]不加固第i只小猪家后的所得金币
转移方程:
a[i]=max(a[i-1]+l[i]-2c,b[i-1]+l[i]);
b[i]=max(a[i-1],b[i-1]);
//-2c是因为：“强化一只小猪的家园会从其每个邻居的家园里每次拿走c 个金币，来为自己的家园建设更好的防御措施。然而，强化操作并不会改变这只小猪的金币数量，只有它的邻居们的金币数量会减少。”，若选择第i-1、i只小猪，则他们会相互拿走c个金币，即-2c
#include<bits/stdc++.h>
using namespace std;
int n,c;
long long ans;
long long l[200005],a[200005],b[200005];
//第一个和最后一个都选选
void check0(){
a[0]=b[1]=l[0]-2*c;
a[1]=a[0]+l[1]-2*c;
for(int i=2;i<n-1;i++){
a[i]=max(a[i-1]+l[i]-2*c,b[i-1]+l[i]);
b[i]=max(a[i-1],b[i-1]);
}
a[n-1]=max(a[n-2]-2*c,b[n-2])+l[n-1];
ans=max(ans,a[n-1]);
return ;
}
//选第一个不选最后一个
void check1(){
a[0]=b[1]=l[0];
a[1]=a[0]+l[1]-2*c;
for(int i=2;i<n-1;i++){
a[i]=max(a[i-1]+l[i]-2*c,b[i-1]+l[i]);
b[i]=max(a[i-1],b[i-1]);
}
b[n-1]=max(a[n-2],b[n-2]);
ans=max(ans,b[n-1]);
return ;
}
//选最后一个不选第一个
void check2(){
a[1]=l[1];
b[1]=0;
for(int i=2;i<n-1;i++){
a[i]=max(a[i-1]+l[i]-2*c,b[i-1]+l[i]);
b[i]=max(a[i-1],b[i-1]);
}
a[n-1]=max(a[n-2]-2*c,b[n-2])+l[n-1];
ans=max(ans,a[n-1]);
return ;
}
//最后一个和第一个都不选
void check3(){
a[1]=l[1];
b[1]=0;
for(int i=2;i<n-1;i++){
a[i]=max(a[i-1]+l[i]-2*c,b[i-1]+l[i]);
b[i]=max(a[i-1],b[i-1]);
}
b[n-1]=max(a[n-2],b[n-2]);
ans=max(ans,b[n-1]);
return ;
}
int main(){
cin>>n>>c;
for(int i=0;i<n;i++) cin>>l[i];
if(n<2){
cout<<0;
return 0;
}
check0();
check1();
check2();
check3();
cout<<ans;
return 0;
}
作者C++才学了1年多,第一次写题解,写不好请见谅（快期末考试了！没时间所以写的很快，不是很细致)
有帮助，赞一个