Vijos题解
题库地址：https://vijos.org/p
P1001 谁拿了最多奖学金
题意：按照指定要求计算奖学金，直接用if判断即可
#include<iostream>
using namespace std;
struct STUDENT{
string name;
int n1,n2;
char xsgb,xb;
int lw;
int jxj;
};
int main(){
int n;
int sum=0;
cin>>n;
struct STUDENT stu[n];
struct STUDENT zdz;
zdz.jxj=0;
for(int i=0;i<n;i++)stu[i].jxj=0;
for(int i=0;i<n;i++){
cin>>stu[i].name>>stu[i].n1>>stu[i].n2>>stu[i].xsgb>>stu[i].xb>>stu[i].lw;
if(stu[i].n1>80&&stu[i].lw>=1)stu[i].jxj+=8000;
if(stu[i].n1>85&&stu[i].n2>80)stu[i].jxj+=4000;
if(stu[i].n1>90)stu[i].jxj+=2000;
if(stu[i].n1>85&&stu[i].xb=='Y')stu[i].jxj+=1000;
if(stu[i].n2>80&&stu[i].xsgb=='Y')stu[i].jxj+=850;
if(stu[i].jxj>zdz.jxj)zdz=stu[i];
sum+=stu[i].jxj;
}
cout<<zdz.name<<endl<<zdz.jxj<<endl<<sum;
return 0; }
P1007 绕钉子的长绳子
题意：求两点距离
#include<bits/stdc++.h>
using namespace std;
const double pi=3.14159265359;
struct POINT{
double x;
double y;
};
int n;
double r,ans=0;
POINT p[100001];
inline double dis(POINT a,POINT b){
double x=a.x-b.x;
double y=a.y-b.y;
return sqrt(x*x+y*y);//两点距离
}
int main(){
cin>>n>>r;
for(int i=0;i<n;i++)cin>>p[i].x>>p[i].y;
for(int i=1;i<n;i++){
ans+=dis(p[i],p[i-1]);
}
ans+=dis(p[0],p[n-1]);//第一个和最后一个之间
ans+=2*pi*r;//绕钉子的长度
cout<<fixed<<setprecision(2)<<ans<<endl;
return 0;
}
P1025 小飞侠的游园方案
题意：同P1104，01背包问题，只是输入的顺序改了
#include<bits/stdc++.h>
using namespace std;
int Time[10000],Value[10000];
int dp[100000];
int main(){
int a,n;
cin>>n>>a;
for(int i=0;i<n;i++){
cin>>Value[i]>>Time[i];
}
for(int i=0;i<n;i++){
for (int j=a;j>=Time[i];j--){
dp[j]=max(dp[j],dp[j-Time[i]]+Value[i]);
}
}
cout<<dp[a];
return 0;
}
P1040 高精度乘法
题意：标准高精度乘法
#include<iostream>
#include<cstring>
using namespace std;
string sa,sb;
int a[100000],b[100000],c[100000],lena,lenb,lenc;
int main() {
cin>>sa;
cin>>sb; //读入数字a和b，将其存入字符串sa和sb中
lena=sa.size();
lenb=sb.size(); //求出2个数字的位数长度
for (int i=1;i<=lena;i++) a[i]=sa[lena-i]-48;
for (int i=1;i<=lenb;i++) b[i]=sb[lenb-i]-48;
//将字符串中的存储的数字字符转换为数字逆序存于a、b数组中
//a、b数组是从第1格开始存储，方便后续计算
for (int i=1;i<=lena;i++)
for (int j=1;j<=lenb;j++) {
c[i+j-1]+=a[i]*b[j];
c[i+j]+=c[i+j-1]/10;
c[i+j-1]%=10;
}
lenc=lena+lenb;
while (c[lenc]==0 && lenc>1) lenc--;
//从高位开始找非零值，确定乘积的位数
for (int i=lenc;i>0;i--) cout<<c[i]; //输出答案
return 0;
}
P1058 粘贴文本
题意：剪切和粘贴操作，模拟
Windows操作系统中有一个“剪贴板”的功能，把待粘贴的东西临时存放在那里。我们也可以使用类似的思路。主要步骤：
第一步，把文本放进剪贴板。
第二步，把已经剪切掉的部分后面的东西前移上去。
第三步，把要粘贴的地方所有后面的文本后移，腾出位子留给要粘贴的文本。
第四步，把剪贴板上的文本粘贴进去。
所有步骤都可以使用memmove操作。关于memmove和memcpy的区别可以自行网上搜索。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int text[maxn],temp[maxn];
int n,k,a,b,c;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)text[i]=i;
for(int i=0;i<k;i++){
cin>>a>>b>>c;
int len=b-a+1;
memmove(temp,text+a,sizeof(int)*len);//待粘贴数字
memmove(text+a,text+b+1,sizeof(int)*(n-b));//把数字剪切掉
memmove(text+c+len+1,text+c+1,sizeof(int)*(n-len-c));//粘贴位置数字后移
memmove(text+c+1,temp,sizeof(int)*len);//粘贴进去
}
for(int i=1;i<=10;i++)cout<<text[i]<<endl;
return 0;
}
P1066 弱弱的战壕
题意：判断一个点是否在另一个点的左下角，枚举
#include<bits/stdc++.h>
using namespace std;
const int MAXN=20000+10;
int n;
int x[MAXN],y[MAXN],ans[MAXN],ans1[MAXN];
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j&&(x[i]>=x[j])&&(y[i]>=y[j]))ans[i]++;//统计第i个战壕的保护对象数量
}
}
for(int i=1;i<=n;i++)ans1[ans[i]]++;//保护数量为ans[i]的战壕个数
for(int i=0;i<n;i++)cout<<ans1[i]<<endl;
return 0;
}
P1093 文科生的悲哀
题意：本质就是求斐波那契数列的第n项，递推法
#include<iostream>
using namespace std;
int n,fibo[100000];
int main(){
cin>>n;
fibo[1]=fibo[2]=1;
for(int i=3;i<=n;i++)fibo[i]=(fibo[i-1]+fibo[i-2])%7654321;
cout<<fibo[n];
return 0;
}
P1096 津津的储蓄计划
题意：使用变量记录在身边的钱和存的钱
PS：存的钱就是所有的钱向下舍入到百位，例如320向下舍入到百位就是300，也就是整百的钱。
（一些关于向下舍入的文字，来源《30天自制操作系统》第十章）
#include<bits/stdc++.h>
using namespace std;
int a[12];
int main(){
int money=0/*自己的*/,cun=0;/*存的钱*/
for(int i=0;i<12;i++){
cin>>a[i];
}
for(int i=0;i<12;i++){
money+=300;
money-=a[i];
if(money<0){
cout<<"-"<<i+1<<endl;
return 0;
}
cun+=money/100*100;//舍入到整百位
money%=100;
}
cout<<money+cun*1.2<<endl;
return 0;
}
P1097 合并果子
题意：每次找最小的两堆进行合并，边合并边排序
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)cin>>a[i];
int ans=0;
sort(a,a+n);
for(int i=1;i<n;i++){
a[i]=a[i]+a[i-1];
ans+=a[i];
sort(a+i,a+n);
}
cout<<ans<<endl;
return 0;
}
（来源CCF基础篇）维护小根堆
#include<bits/stdc++.h>
using namespace std;
int N,ans;
const int MAXN=10000+10;
int a[MAXN];
bool cmp(int a,int b){
return a>b;
}
int main(){
cin>>N;
for(int i=0;i<N;i++)cin>>a[i];
make_heap(a,a+N,cmp);//建小根堆
ans=0;
for(int i=N;i>1;i--){//每次合并2堆，一共N-1次
pop_heap(a,a+i,cmp);
pop_heap(a,a+i-1,cmp);//最小值弹到堆底
a[i-2]+=a[i-1];
ans+=a[i-2];
push_heap(a,a+i-1,cmp);//新元素在a[i-2]，插入堆中
}
cout<<ans<<endl;
return 0;
}
P1103 校门外的树
题意：开数组把树的状态记录下来
#include <bits/stdc++.h>
using namespace std;
int main(){
int l,m;
cin>>l>>m;
int left,right,road[100000];
for(int i=1;i<=m;i++){
cin>>left>>right;
for(int j=left;j<=right;j++)road[j]=1;
}
int s=0;
for(int i=0;i<=l;i++){
if(!road[i])s++;
}
cout<<s;
return 0;
}
P1104 采药
题意：标准01背包问题
#include<bits/stdc++.h>
using namespace std;
int Time[10000],Value[10000];
int dp[100000];
int main(){
int a,n;
cin>>a>>n;
for(int i=0;i<n;i++){
cin>>Time[i]>>Value[i];
}
for(int i=0;i<n;i++){
for (int j=a;j>=Time[i];j--){
dp[j]=max(dp[j],dp[j-Time[i]]+Value[i]);
}
}
cout<<dp[a];
return 0;
}
P1113 不高兴的津津
题意：找最大值
#include <iostream>
using namespace std;
int bgx,a,b,zdz;
int main(){
for(int i=0;i<7;i++){
cin>>a>>b;
if(a+b>8&&a+b>bgx)bgx=a+b,zdz=i+1;
}
cout<<zdz;
return 0;
}
P1115 火星人
题意：求一组数的第N个排列，可以用STL的next_permutation函数
#include<bits/stdc++.h>
using namespace std;
int A[10000];
int n;
int a;
int main(){
int n;
cin>>n>>a;
for(int i=0;i<n;i++)
cin>>A[i];
for(int i=0;i<a;i++)
next_permutation(A,A+n);
for(int i=0;i<n;i++)
cout<<A[i]<<' ';
return 0;
}
P1116 一元三次方程求解
题意：枚举一元方程的解
PS：算式的绝对值小于0.01就可以看做是等于
#include<bits/stdc++.h>
using namespace std;
int main(){
float a,b,c,d,x;
scanf("%f%f%f%f",&a,&b,&c,&d);
for(int i=-10000;i<=10000;i++){//枚举解
x=i/100.0;
if(fabs(a*x*x*x+b*x*x+c*x+d)<=0.01) printf("%.2f ",x);//可以看做是等于0
}
return 0;
}
P1123 均分纸牌
题意： 模拟，使每堆纸牌到达平均值
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n;
int a[n],tot=0;
for(int i=0;i<n;i++)cin>>a[i],tot+=a[i];
int ave=tot/n;
int ans=0;
for(int i=0;i<n;i++){//模拟，把所有的移动到平均值
if(a[i]>ave)a[i+1]+=a[i]-ave,a[i]=ave,ans++;//太多，向右移动
else if(a[i]<ave)a[i+1]-=ave-a[i],a[i]=ave,ans++;//太少，向右移动
}
cout<<ans; }
P1127 级数求和
题意：计算1+1/2+1/3+1/4+...+1/n，用一个while循环即可
#include<bits/stdc++.h>
using namespace std;
int main(){
int k;
cin>>k;
double ans=0;
int i=1;
while(ans<k){
ans+=1.0/i;
++i;
}
cout<<i-1;
}
P1130 数的计数
题意：用动态规划的方法，我们假设第i个数生成的个数为dp[i]，那么它的左边还可以加上的数的个数就是dp[1]+dp[2]+...+dp[i/2]，dp[1]=1
#include<bits/stdc++.h>
using namespace std;
int dp[1100];
int main(){
int n;
cin>>n;
dp[1]=1;
for(int i=1;i<=n;i++){
int tot=0;
for(int j=1;j<=i/2;j++)tot+=dp[j];
dp[i]=tot+1;
}
cout<<dp[n];
}
P1199 核弹危机
题意：四层循环枚举左上角和右下角点，计算核弹范围内房屋数量最大值
#include<bits/stdc++.h>
using namespace std;
char a[10000][10000];
int m,n;
int main(){
cin>>m>>n;
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
}
}
int total=0,ans=0;
for(int i=0;i<m;i++){//攻击的左上角点
for(int j=0;j<m;j++){
total=0;
for(int k=i;k<=i+n-1;k++){//攻击的右下角点
for(int l=j;l<=j+n-1;l++){
if(a[k][l]=='#')total++;//房屋
if(total>ans)ans=total;
}
}
}
}
cout<<ans;
return 0;
}
P1201 高低位交换
方法一：使用C++自带的位运算，先用<<和>>进行移位，得到高16位和低16位，然后用“或”运算进行合并
#include<bits/stdc++.h>
using namespace std;
int main(){
unsigned int a;
cin>>a;
unsigned int b=(a<<16)|(a>>16);//直接用位运算
cout<<b;
}
方法二：模拟
十进制转换为二进制：循环做除法，倒取余数
二进制转换为十进制：按位组合，第32-i位的权值是2的i-1次方
其实这道题目在转换的时候不需要把二进制的顺序倒过来，在转换为十进制的时候也反一下，i位的权值为2的i-1次方，这样即可
#include<bits/stdc++.h>
using namespace std;
int binary[33];
int main(){
int x=0,len=0;
cin>>x;
while(x){//十转二
binary[++len]=x%2;
x/=2;
}
for(int i=1;i<=16;i++)swap(binary[i],binary[i+16]);
unsigned int ans=0;
for(int i=1;i<=32;i++)ans+=pow(2,i-1)*binary[i];//二转十
cout<<ans;
return 0;
}
P1211 生日日数
题意：计算指定日期过10000天后的日期，注意判断闰年和日期进制，可以使用数组保存每个月的天数
判断闰年：“四年一闰，百年不闰，四百年又一闰”
每个月的天数：口诀：“一三五七八十腊，三十一日总不差” 。其中的“腊月”就是十二月。
另外注意保存天数的数组不可以用const，因为要根据闰年来修改2月是28天还是29天。
#include<bits/stdc++.h>
using namespace std;
int daynum[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int main(){
int year,month,day;
cin>>year>>month>>day;
for(int i=0;i<10000;i++){
if((year%4==0&&year%100!=0)||year%400==0)daynum[2]=29;
else daynum[2]=28;
++day;
if(day>daynum[month]){
day=1;++month;
}
if(month>12){
month=1;++year;
}
}
printf("%d-%d-%d",year,month,day);
}
P1217 乒乓球
题意：根据不同比分制进行比分计算
PS：最后一次完整比赛输出完后还要再输出一次
#include<bits/stdc++.h>
using namespace std;
int main(){
char c;string s;
int w=0,l=0;
while((c=getchar())!='E'){
s+=c;
}
for(int i=0;i<s.size();i++){
if(s[i]=='W')++w;
else if(s[i]=='L')++l;
if((w>=11||l>=11)&&abs(w-l)>=2)printf("%d:%d\n",w,l),w=0,l=0;
}
printf("%d:%d\n\n",w,l);
w=0;l=0;
for(int i=0;i<s.size();i++){
if(s[i]=='W')++w;
else if(s[i]=='L')++l;
if((w>=21||l>=21)&&abs(w-l)>=2)printf("%d:%d\n",w,l),w=0,l=0;
}
printf("%d:%d\n\n",w,l);
return 0;
}
P1223 麦林数
题意：高精度计算2^P-1，快速幂
#include<bits/stdc++.h>
using namespace std;
const int Max_M=510;
int n;
int Out[Max_M];
int Power[2*Max_M]; void DFS(int n){
int i,j;
if (n==0) return;
DFS(n/2);
for (i=1;i<=500;i++)
for (j=1;j<=500;j++)//分拆为两个数
if(n%2==0) Power[i+j-1]=Power[i+j-1]+Out[i]*Out[j];//偶数，分拆两个
else
Power[i+j-1]=Power[i+j-1]+Out[i]*Out[j]*2;//奇数，分拆两个，再加上剩余的2
for(i=1;i<=500;i++){//进位
Out[i]=Power[i]%10;
Power[i+1]=Power[i+1]+Power[i]/10;
}
memset(Power,0,sizeof(Power));
} int main(){
//freopen("mason.in","r",stdin);freopen("mason.out","w",stdout);
cin>>n;
cout<<int((log(2)/log(10)*n)+1)<<endl;//对数换底，求位数
Out[1]=1;
DFS(n);
for(int i=500;i>=2;i--){
cout<<Out[i];
if (i%50==1) cout<<endl;
}
cout<<Out[1]-1<<endl;
return 0;
}
P1229 分解因式
题意：计算因数个数
#include <iostream>
using namespace std;
int f(int x){
int ans=0;
for(int i=1;i<=x;i++)
if(x%i==0)ans++;
return ans;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=20000;i++){
if(f(i)==n){
cout<<i;return 0;
}
}
cout<<"NO SOLUTION";
return 0;
}
P1258 多项式表示
PS：与P1812有区别，模拟
#include<bits/stdc++.h>
using namespace std;
int main(){
int flag=0,data;
for(int i=8;i>=0;i--){
scanf("%d",&data);
if(data==0)continue;
if(data*flag==0&&data<0)printf("-");//首项无空格
else if(data<0) printf(" - ");
if(data*flag>0) printf(" + ");
if(data*data-1>0) printf("%d",data>0 ? data : -data);//负数已经有负号了，输出相反数
if(i>1) printf("x^%d",i);//有次数
else if (i==1) printf("x");
else if (i==0&&(data==1||data==-1)) printf("1");
flag=1;
}
if(flag==0)printf("0");
return 0;//全零标记
}
P1282 佳佳的魔法照片
题意：多关键字排序
#include<bits/stdc++.h>
using namespace std;
struct people{
int w,d;
}p[50010];
bool cmp(people a,people b){
if(a.w!=b.w)return a.w>b.w;
return a.d<b.d;
}
int main(){
int n,k;
cin>>n>>k;
int E[10];
for(int i=0;i<10;i++)cin>>E[i];
for(int i=0;i<n;i++)cin>>p[i].w,p[i].d=i+1;
sort(p,p+n,cmp);
for(int i=0;i<n;i++)p[i].w+=E[i%10];
sort(p,p+n,cmp);
for(int i=0;i<k;i++)cout<<p[i].d<<' ';
}
P1307 黑皮的正方形
题意：计算总正方形的个数，如果边长为n，那么单个组成的正方形个数为n*n，四个拼成的正方形个数为(n-1)*(n-1)，九个拼成的正方形个数为(n-2)*(n-2)，以此类推，总数就是从1-n的平方相加。
#include<bits/stdc++.h>
using namespace std;
long long n,ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++)ans+=i*i;
cout<<ans;
}
P1316 明明的随机数
题意：先去掉重复的，然后做排序，直接STL的sort函数即可
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
scanf("%d",&n);
int f=n;
int a[n];
for(int i=0;i<n;i++)scanf("%d",a+i);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(i!=j && a[i]==a[j] && a[i]!=-1 && a[j]!=-1 )f--,a[j]=-1;//重复的标记为-1
}
}
sort(a,a+n);
printf("%d\n",f);
for(int i=0;i<n;i++){
if(a[i]!=-1)printf("%d ",a[i]);
}
return 0;
}
P1389 婚礼上的小杉
题意：多关键字排序
PS：本题的难点在于如何输入数据，我们可以同时使用cin（输入数据）以及getchar（判断行是否结束）
#include<bits/stdc++.h>
using namespace std;
struct LETTER{
int id;
string x;
}a[1001];
bool cmp(LETTER a, LETTER b){
return a.id<b.id;
}
int main(){
int n;
for(;;){
scanf("%d",&a[n++].id);
if(getchar()=='\n')break;//第一行是否结束
}
for(int i=0;i<n;i++){
cin>>a[i].x;
}
sort(a,a+n,cmp);
for(int i=0;i<n;i++){
cout<<a[i].x<<endl;
}
return 0;
}
P1398 奖学金
题意：多关键字排序，使用sort的第三个参数cmp函数
#include<iostream>
#include<algorithm>
#define sum(i) i.yw+i.sx+i.yy
using namespace std;
struct STU{
int xh;
int yw,sx,yy;
};
bool cmp(STU a,STU b){
if(sum(a)!=sum(b))return sum(a)>sum(b);
else if(a.yw!=b.yw)return a.yw>b.yw;
else return a.xh<b.xh;
}
int main(){
int n;
scanf("%d",&n);
struct STU stu[n];
for(int i=0;i<n;i++)scanf("%d %d %d",&stu[i].yw,&stu[i].sx,&stu[i].yy),stu[i].xh=i+1;
sort(stu,stu+n,cmp);
for(int i=0;i<5;i++)printf("%d %d\n",stu[i].xh,sum(stu[i])) ;
return 0;
}
P1431 守望者的逃离
题意：动态规划，综合考虑使用魔法和跑步的最大值
CCF书上的思路分析：
#include<iostream>
#include<cstring>
using namespace std;
#define MAXN 300010
int main(){
int m,s,t,i;
int f[MAXN];
cin>>m>>s>>t;
f[0]=0;
for(int i=1;i<=t;i++){//计算只用闪烁法术时的每秒最大距离
if(m>9)f[i]=f[i-1]+60,m-=10;
else f[i]=f[i-1],m+=4;
}
for(int i=1;i<=t;i++){//计算加入跑步选择时的每秒最大距离
if(f[i]<f[i-1]+17)f[i]=f[i-1]+17;
if(f[i]>=s){//刚好离岛
cout<<"Yes"<<endl<<i;return 0;
}
}
cout<<"No"<<endl<<f[t];//不能离岛
return 0;
}
P1484 ISBN号码
PS：10在ISBN中表示为'X'
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
for(int i=0;i<s.size();i++){
if(s[i]!='-'&&s[i]!='X')s[i]-='0';
if(s[i]=='X')s[i]=10;
}
int x=(s[0]*1+s[2]*2+s[3]*3+s[4]*4+s[6]*5+s[7]*6+s[8]*7+s[9]*8+s[10]*9)%11;
if(x==s[12])printf("Right\n");
else{
for(int i=0;i<s.size();i++){
if(s[i]!='-')s[i]+='0';
}
for(int i=0;i<s.size()-1;i++)cout<<s[i];
if(x!=10)cout<<x;
else cout<<'X';
}
}
P1496 火柴棒等式
题意：枚举A,B,C
CCF书上的思路分析：
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[10]={6,2,5,5,4,5,6,3,7,6},ans=0,temp=0,k;
//a[i]表示数字i需要几根火柴棒
int num[2016];
int n;
cin>>n;
num[0]=6;
for(int i=1;i<2000;i++){//预处理0-2000数对应的火柴数目
k=i;
while(k){
temp+=a[k%10];
k/=10;
}
num[i]=temp;//num[i]存放i的火柴个数
temp=0;
}
for(int i=0;i<999;i++){
for(int j=0;j<999;j++){//枚举A,B
if(num[i]+num[j]>=n)continue;//超过
else if(num[i+j]+num[i]+num[j]+4==n){//C为A+B即i+j
ans++;
}
}
}
cout<<ans;
return 0;
}
P1597 2的幂次方
思路：设递归函数dfs(x)用于输出x的幂次方
最容易的思路：0不输出，1输出为2(0)，2输出2，剩下的递归执行。
每一次递归：例如7，拆分为4+3，先拆出最大的是2的次方的数出来，输出4，再把3分拆输出。
对于3，拆分为2+1。
//flag用于标记输出时前面是否需要加+号
#include<bits/stdc++.h>
using namespace std;
int n;
void dfs(int n,bool flag){
if(n==0)return;
if(flag)cout<<"+";
if(n==2)cout<<"2";
else if(n==1)cout<<"2(0)";
//else if(n==0)return;
else{
int i;
for(i=0;;i++){
if(pow(2,i)>n)break;
}
i--;
if(i==1)cout<<"2";
else{
cout<<"2(";
dfs(i,0);
cout<<")";
}
dfs(n-pow(2,i),1);
}
}
int main(){
cin>>n;
dfs(n,0);
}
P1762 统计变量
题意：找':'和','的个数即可，因为变量名是用它们分隔的。另外变量都定义在主程序之前，所以读取到第一个begin就需要结束了
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
int ans=0;
while(cin>>s){
if(s=="begin")break;
for(int i=0;i<s.size();i++){
if(s[i]==','||s[i]==':')ans++;
}
}
cout<<ans;
}
P1772 巧妙填数
题意：将1,2,...,9共9个数分成三组，分别组成三个三位数，且使这三个三位数构成1:2:3的比例。
可以使用枚举的方法，只枚举a，然后把b,c计算出来，数位分离并且用数组记录下每个数字出现的个数。
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,c;
for(int a=123;a<=333;a++){
b=2*a;c=3*a;
char s[10];
sprintf(s,"%d%d%d",a,b,c);
int flag[10];
memset(flag,0,sizeof(flag));
for(int i=0;i<9;i++)
flag[s[i]-'0']++;
for(int i=1;i<=9;i++){
if(flag[i]!=1)goto next;
}
cout<<a<<' '<<b<<' '<<c<<endl;
next:
continue;
}
}
P1784 数字统计
题意：在数字中数位分离找到指定的数字，可以直接sprintf数字转字符串，然后逐位判断
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,ans=0;
char s[15];
cin>>a>>b;
for(int i=a;i<=b;i++){
sprintf(s,"%d",i);
for(int j=0;j<15;j++){
if(s[j]=='2')ans++;
}
}
cout<<ans<<endl;
return 0;
}
手动数位分离
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,ans=0;
char s[15];
cin>>a>>b;
for(int i=a;i<=b;i++){
int temp=i;
while(i>0){
if(i%10==2)ans++;
i/=10;
}
i=temp;
}
cout<<ans<<endl;
return 0;
}
P1788 第k大
题意：排序，找第k大的数，注意sort默认从小到大排序
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
cout<<a[n-k];
}
二分法（来源NOIP2008普及组初赛的完善程序，有微调）
每一次把数组分为两部分，大于基准数和小于基准数
#include <iostream>
using namespace std;
int a[1000001],n,ans =-1;
void swap(int &a,int &b){
int c;
c=a;a=b;b=c;
}
int FindKth(int left, int right, int n){
int tmp,value,i,j;
if (left==right) return left;//区间只有一个数
tmp=rand()%(right-left)+left;//随机的中间数
swap(a[tmp],a[left]);
value=a[left];//基准数
i=left;
j=right;
while (i<j){//对区间进行二分
while (i<j && a[j]<value) j--;
if (i<j) {a[i]=a[j]; i++;} else break;
while (i<j && a[i]>value) i++;
if (i<j) {a[j]=a[i]; j--;} else break;
}
a[i]=value;//i为排序下来的中间数
if (i<n) return FindKth(i+1,right,n);//在左区间继续
if (i>n) return FindKth(left,i-1,n); //在右区间继续
return i;//i=n的情况
}
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
ans=FindKth(1,n,k);
cout<<a[ans];
return 0;
}
P1812 多项式输出
题意：按照题目指定的格式输出多项式
注意事项：
如果是n次，不需要输出+号。
从n-1次到2次，直接输出。注意，输出负数的时候，会自动带上负号，输出正数不会自动输出+号，需要自己写。例如，
cout<<a;//输出-1
cout<<"-"<<a;//输出--1
1次需要注意不用输出x后面的^和次数
0次只需要输出系数。
如果系数为1或-1，不输出1。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,a;
cin>>n;
int i;
for(i=n;i>=0;i--){
cin>>a;
if(a==0)continue;
if(i==n){
if(a!=1 && a!=-1)cout<<a<<"x^"<<i;
if(a==1)cout<<"x^"<<i;
if(a==-1)cout<<"-x^"<<i;
continue;
}
else if(i==0){
if(a>0){
cout<<"+"<<a;continue;
}
if(a<0){
cout<<a;continue;
}
}
else if(i==1){
if(a>0){
if(a!=1)cout<<"+"<<a<<"x";
else cout<<"+x";
}
if(a<0){
if(a!=-1)cout<<a<<"x";
else cout<<"-x";
}
}
else {
if(a>0){
if(a!=1)cout<<"+"<<a<<"x^"<<i;
else cout<<"+x^"<<i;
}
if(a<0){
if(a!=-1)cout<<a<<"x^"<<i;
else cout<<"-x^"<<i;
}
continue;
}
}
return 0;
}
P1813 分数线划定
题意：多关键字排序
#include<bits/stdc++.h>
using namespace std;
int N,M,n,m;
struct Node{
int k,s;
}P[10001];
bool Compare(Node a,Node b){
if(a.s==b.s)return a.k<b.k;
return a.s>b.s;
}
int main(){
scanf("%d %d",&N,&M);
for(int i=1;i<=N;i++){
scanf("%d %d",&P[i].k,&P[i].s);
}
sort(P+1,P+N+1,Compare);
m=floor(M*1.5);
for(int i=1;;i++){
if(P[i].s>=P[m].s)++n;
else break;
}
printf("%d %d\n",P[m].s,n);
for(int i=1;;i++){
if(P[i].s>=P[m].s)printf("%d %d\n",P[i].k,P[i].s);
else break;
}
return 0;
}
P1848 计数问题
题意：同P1784
sprintf数位分离法
#include<iostream>
using namespace std;
int main(){
int n,x,ans=0;
cin>>n>>x;
char s[8];
for(int i=1;i<=n;i++){
sprintf(s,"%8d",i);
for(int j=0;j<8;j++){
if(s[j]-'0'==x)ans++;
}
}
cout<<ans;
}
手动数位分离法：
使用一个while循环，不断取除以10的余数，除一位后就去掉这位，从下一位继续
#include<iostream>
using namespace std;
int main(){
int n,x,ans=0;
cin>>n>>x;
for(int i=1;i<=n;i++){
int temp=i;
while(i>0){
if(i%10==x)ans++;
i/=10;
}
i=temp;
}
cout<<ans;
}
CCF程序设计基础篇书上的题解，也是手动数位分离法
#include<iostream>
using namespace std;
int main(){
int ans=0,i,n,x,tmp;
cin>>n>>x;
for(int i=1;i<=n;i++){//重复对1-n中的每一个数进行计数
tmp=i;
while(tmp>=1){//对于数字逐位判断，计数
if(tmp%10==x)ans++;//如果当前的末尾数字是x，则计数器加一
tmp/=10;//为下一次取得末尾数字做准备
}
}
cout<<ans;
return 0;
}
P1911 珠心算
题意：找出集合中一个数等于其他两数之和，三层循环枚举
#include<bits/stdc++.h>
using namespace std;
int n,*a,s,t,u,ans;
bool f[10001];
int main(){
cin>>n;
a=(int*)malloc(n*sizeof(int));
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++){
s=a[i];
for(int j=0;j<n;j++){
if(j==i)continue;//不同的数
t=a[j];
for(int k=0;k<n;k++){
if(k==i||k==j)continue;
u=a[k];
if(s+t==u && !f[u]){
ans++;f[u]=1;//已经算过的
}
}
}
}
cout<<ans<<endl;
return 0;
}
P1912 比例简化
题意：将 A 比 B 化简为 A’比 B’，要求在 A’和 B’均不大于 L 且 A’和 B’互质（两个整数的最大公约数是 1）的前提下，A’/B’ ≥ A/B 且 A’/B’ - A/B 的值尽可能小。
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
if(y==0)return x;
return gcd(y,x%y);
}
int main(){
int a,b,l,a1=100000,b1=1;
cin>>a>>b>>l;
for(int i=1;i<=l;i++){
for(int j=1;j<=l;j++){
if(gcd(i,j)==1 && i*b>=j*a)
if(i*b1<=j*a1)a1=i,b1=j;//分数的大小比较可以用十字相乘法
}
}
cout<<a1<<' '<<b1;
return 0;
}
P1913 螺旋矩阵
题意：模拟，按照顺序构造符合条件的螺旋矩阵
#include<stdio.h>
int n,x,y;
int min(int n1,int n2){
if(n1<n2)return n1;
else return n2;
}
int solve(){
scanf("%d%d%d",&n,&x,&y);
int layer=min(x,n+1-x);//确定层，n方阵，如n=7,x=5就是第二层
layer=min(layer,min(y,n+1-y));
int num=0,side=n-1;
for(int i=1;i<layer;i++,side-=2){
int layer_total;
if(side==0)layer_total=1;
else layer_total=side*4;//当前层一圈总个数
num+=layer_total;
}
num++;
int nx=layer,ny=layer;
if(nx==x && ny==y)return num;
for(int i=1;i<=side;i++){
ny++;num++;//y列向右递增
if(nx==x && ny==y)return num;
}
for(int i=1;i<=side;i++){
nx++;num++;//x行向下递增
if(nx==x && ny==y)return num;
}
for(int i=1;i<=side;i++){
ny--;num++;//y列向左递增
if(nx==x && ny==y)return num;
}
for(int i=0;i<side;i++){
nx--;num++;//x行向上递增
if(nx==x && ny==y)return num;
}
return -1;
}
int main(){
int res=solve();printf("%d",res);
return 0;
}