CSP-J 2018 T1 标题统计（字符串）

思路

直接用$for$循环枚举每个字符，判断是否满足条件。

代码

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

signed main(){
	string s;
	getline(cin,s);
	int cnt=0;
	for(int i=0;i<s.size();i++){
		if(s[i]>='a'&&s[i]<='z'){
			cnt++;
		}else if(s[i]>='A'&&s[i]<='Z'){
			cnt++;
		}else if(s[i]>='0'&&s[i]<='9'){
			cnt++;
		} 
	}
	cout <<cnt;
	return 0;
} 

CSP-J 2018 T2 龙虎斗（模拟）

思路

1. 先根据初始情况，计算龙、虎双方各自的势力，包括$p1$号兵营增加$s1$个士兵；

2. 在枚举在1~n号兵营增加$s2$个士兵时，龙、虎双方的势力之差的最小值，如果是最小值则更新答案；

3. 输出答案，全程注意用long long！

代码

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

const int tt=1e5+10;
int a[tt];

signed main(){
	freopen("fight.in","r",stdin);
	freopen("fight.out","w",stdout);
	int n;
	cin >>n;
	for(int i=1;i<=n;i++){
		cin >>a[i];
	}
	int m,p1,s1,s2;
	cin >>m>>p1>>s1>>s2;
	a[p1]+=s1;
	int l=0,r=0;
	for(int i=1;i<m;i++){
		l+=(m-i)*a[i];
	}
	for(int i=m+1;i<=n;i++){
		r+=(i-m)*a[i];
	}
	int min_n=2e9;
	int cnt=0;
	for(int i=1;i<=n;i++){
		int res_l=l,res_r=r;
		if(i<m){
			res_l+=(m-i)*s2;
		}else{
			res_r+=(i-m)*s2;
		}
		if(abs(res_l-res_r)<min_n){
			cnt=i;
			min_n=abs(res_l-res_r);
		}
	}
	cout <<cnt;
	return 0;
}

CSP-J 2019 T1 数字游戏（字符串）

思路

直接枚举每一位，如果是字符'1'，就cnt++。

代码

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

int main(){
	string s;
	getline(cin,s);
	int cnt=0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='1'){
			cnt++;
		}
	}
	cout <<cnt;
	return 0;
} 

CSP-J 2019 T2 公交换乘（模拟）

思路

这道题可以使用模拟的方式，使用数组存储可用的优惠票，对于每一次公交，从头到尾遍历优惠票即可，但是会超时。

由于优惠票是按时间排序的，超过$45$分钟的失效，我们可以每次排除掉失效的票，这样就可以过了。

代码

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

const int tt=1e5+10;
int best[tt],sj[tt];
bool flag[tt];

int main(){
	int n;
	cin >>n;
	int ans=0;
	int h=0,t=0;
	for(int i=1;i<=n;i++){
		int x,y,z;
		cin >>x>>y>>z;
		if(x==0){
			ans+=y;
			t++;
			sj[t]=z;
			best[t]=y;
			flag[t]=1;
		}else{
			while(h<t&&z-sj[h]>45){
				h++;
			}
			bool op=1;
			for(int j=h;j<=t;j++){
				if(z-sj[j]<=45&&best[j]>=y&&flag[j]){
					op=0;
					flag[j]=0;
					break;
				}
			}
			if(op){
				ans+=y;
			}
		}
	}
	cout <<ans;
	return 0;
}

CSP-J 2020 T1 优秀的拆分（二进制&模拟）

思路

由题意分析，若$n$是奇数，必然出现加数$1$，即不存在优秀的拆分，其他加数按二进制逐位分解就可以了。

代码

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

int main(){
	int n;
	cin >>n;
	if(n%2!=0){
		cout <<"-1";
		return 0;
	}
	for(int i=25;i>=0;i--){
		if((n>>i)&1!=0){
			cout <<(1<<i)<<" ";
		}
	}
	return 0;
}

CSP-J 2020 T2 直播获奖（模拟）

思路

因为选手的分数最多只有$600$分，所以直接枚举就行了。

然后当遇上满足条件的分数，就输出这个分数。

代码

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

const int tt=1e5+10;
int f[tt];

int main(){
	int n,w;
	cin >>n>>w;
	for(int i=1;i<=n;i++){
		int a;
		cin >>a;
		f[a]++;
		int ans=0;
		for(int j=600;j>=0;j--){
			ans+=f[j];
			if(ans>=max(1,i*w/100)){
				cout <<j<<" ";
				break;
			}
		}
	}
	return 0;
}

CSP-J 2021 T1 分糖果（模拟&数学）

思路

我们可以发现，只要$l$和$r$除以$n$的结果是一样的，就输出$r\%n$。

否则，输出$n-1$。

代码

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

signed main(){
	freopen("candy.in","r",stdin);
	freopen("candy.out","w",stdout);
	int n,l,r;
	cin >>n>>l>>r;
	if(l/n==r/n) cout <<r%n;
	else cout <<n-1;
	return 0;
}

CSP-J 2021 T2 插入排序（模拟）

待更新……

CSP-J 2022 T1 乘方（模拟）

思路

直接枚举$b$次，然后让$ans$乘上$a$，如果$ans$大于$1e9$，就输出-1；

如果循环结束，$ans$还是没有大于$1e9$，就输出$ans$。

代码

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

signed main(){
	int a,b;
    cin >>a>>b;
    if(a==1){
        cout <<"1";
        return 0;
    }
    int ans=1;
    for(int i=1;i<=b;i++){
    	ans*=a; 
        if(ans>1e9){
            cout <<"-1";
            return 0;
        }
    }
    cout <<ans;
    return 0;
}

CSP-J 2022 T2 解密（数学）

思路

一道很简单的数学题。我们已知：

$n=p*q$

$e*d=(p-1)(q-1)+1$

$m=n-e*d+2$

这是你就会发现$m$就等于$p+q$的和。这时候我们就要用到平方和与平方差了公式了，我们先来复习一下平方和与平方差公式：

$(p+q)^2=p^2+q^2+2pq$

$(p+q)^2=p^2+q^2-2pq$

我们发现因为$m$就等于$p+q$，再减去$2pq$，那这两个公式就成为了：

$m^2-4n=p^2-2*q+q^2$

$(p-q)^2=p^2-2*p*q+q^2$

那么$p-q$的式子：

$ans=\sqrt{(m^2-4*n)}$

$ans$表示$p-q$

那么为什么有$4$这个系数呢？

举个栗子🌰：

$n=12,p+q=7$

$7^2=49$

$49/12=4......1$

再举个栗子🌰：

$n=6,p+q=5$

$5^2=25$

$25/6=4......1$

所以$4$这个数字就是我们要找的系数。

然后，因为$m$与$n$都是正整数，所以要判断一下$ans$是否为完全平方数。

是完全平方数，输出$(m-ans)/2$与$(m+ans)/2$。

不是完全平方数，输出$NO$。

代码

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

signed main(){
	freopen("decode.in","r",stdin);
	freopen("decode.out","w",stdout);
	int k;
	cin >>k;
	while(k--){
		int n,d,e;
		cin >>n>>d>>e;
		int m=n-e*d+2;
		int res=m*m-4*n;
		int ans=sqrt(res);
		if(ans*ans==res){
			cout <<(m-ans)/2<<" "<<(m+ans)/2<<endl;
		}else{
			cout <<"NO"<<endl;
		}
	}
	return 0;
}

CSP-J 2023 T1 小苹果（数学）

思路

如果最后一个苹果编号$n\%3$等于1，表示本轮被拿走，返回$1$。

否则，递归调用$solve$函数，传入$n-(n+2)/3$作为参数，并将返回结果加$1$。

在主函数中，读入$n$表示初始的苹果数量。

调用$solve$函数计算被拿走的苹果个数。

每轮处理，轮数$cnt$加$1$。

更新苹果数量，每次减去$(apple+2)/3$个苹果。

输出总的轮数$cnt$和第一次选中最后一个的轮数$solve(n)$。

代码

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

int main(){
    int n;
    cin >>n;
    int ans=0;
    int op=0;
    while(n){
        ans++;
        if((n-1)%3==0&&op==0){
            op=ans;
        }
        n-=((n-1)/3+1);
    }
    cout <<ans<<" "<<op;
    return 0;
}

CSP-J 2023 T2 公路（贪心）

思路

首先，我们使用两个数组$v$和$a$来记录站点的信息。数组$v$记录到当前站点的总路程，数组$a$记录每个站点的油价。

接下来，我们读取输入的站点数量$n$和每升油可以让车前进的距离$d$。

然后，使用一个循环来读取每个站点的距离并计算到当前站点的总路程。注意，我们将路程累加到数组$v$中，以便后续计算。接着，使用另一个循环来读取每个站点的油价。接下来，我们使用贪心算法来计算最少的加油费用。我们使用两个变量$minn$和$cnt$来记录当前的最低油价和已购买油的体积。

在循环中，我们计算当前需要多少升油，即总路程除以每升油可以前进的距离$d$。如果有余数，表示需要多买一升油。然后，我们更新当前的最低油价$minn$，取当前站点的油价和$minn$中的较小值。接着，计算当前需要购买的油的体积。如果需要的油量大于已购买的油量$cnt$，说明需要花钱购买更多的油。

最后，将花费的费用累加到$ans$中，计算方式为（需要的油-已购的油）乘当前最低油价。

循环结束后，输出最少的加油费用$ans$。

代码

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

const int tt=1e5+10;
int v[tt],a[tt];

signed main(){
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	int n,d;
	cin >>n>>d;
	for(int i=0;i<n-1;i++){
		cin >>v[i];
		if(i!=0){
			v[i]+=v[i-1];
		}
	}
	for(int i=0;i<n;i++){
		cin >>a[i];
	}
	int ans=0;
	int min_n=a[0],cnt=0;
	for(int i=0;i<n-1;i++){
		int t=v[i]/d;
		if(v[i]%d!=0){
			t++;
		}
		min_n=min(min_n,a[i]);
		ans+=(t-cnt)*min_n;
		cnt=t;
	}
	cout <<ans;
	return 0;
}

谢谢