1001 害死人不偿命的(3n+1)猜想
传送门
知识点：简单模拟
思路：判断奇偶，根据题意即可
参考代码：
点击查看代码
#include<iostream>
using namespace std;
int main()
{
int n,cnt=0;
cin>>n;
while(n!=1){
if(n%2)//奇数
n=(3*n+1);
n/=2;
cnt++;
}
cout<<cnt<<endl;
return 0;
}
1002 写出这个数
传送门
知识点：模拟，递归，映射
思路：
输入数据过大，无法用int或long long存储，只能用string；
遍历string，ch-'0'即可得到该位数字，将各位数字相加得到sum，100位数字相加数据小于1000，使用int存储；
将sum拆分为数组，然后遍历输出映射的拼音，数字与拼音的映射使用string数组即可。
参考代码：
点击查看代码
#include<iostream>
using namespace std;
string num[10]={"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
int cnt=0;
int a[110];
//将数x拆分为数组，递归
void fun(int x){
if(x>=10) fun(x/10);
a[cnt++]=x%10;
}
int main()
{
string st;
int sum=0;
cin>>st;
//各位数字相加
for(char ch:st)
sum+=(ch-'0');
fun(sum);
//按位输出各数字映射的拼音
for(int i=0;i<cnt;i++){
cout<<num[a[i]];
if(i!=cnt-1) cout<<" ";
}
cout<<endl;
return 0;
}
1003 我要通过！
传送么
知识点：模拟，找规律
思路：
根据题意可以得出；
1、不含有PAT以外的字符；
2、P、T有且仅有一个；
3、字符串的格式为xPA..ATx..x，PT之间的A个数与T后面x的个数相等，而x也是由A组成的字符串，以cnt0、cnt1、cnt2表示其中A的个数，cnt0*cnt1==cnt2；
4、PT之间至少有一个A
参考代码：
点击查看代码
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--){
string st;
cin>>st;
bool flag=true;
int cnt=0;
int cnt0=0,cnt1=0,cnt2=0;
int cntp=0,cntt=0;
for(char ch:st){
if(ch=='P'){
//记录P之前的A
cnt0=cnt;
cnt=0;
cntp++;
}
else if(ch=='A')
cnt++;
else if(ch=='T'){
//记录PT之间的A
cnt1=cnt;
cnt=0;
cntt++;
}
//不能含有PAT以外的字符
else flag=false;
}
//记录T之后的A
cnt2=cnt;
//P、T有且仅有一个
if(cntp!=1||cntt!=1) flag=false;
//PT之间至少有一个A，xPA..ATx..x
if(cnt1==0||cnt1*cnt0!=cnt2) flag=false;
if(flag==true) cout<<"YES";
else cout<<"NO";
if(n!=0) cout<<endl;
}
return 0;
}
1004 成绩排名
传送门
知识点：结构体，排序
思路：使用结构体存储数据，使用sort以成绩为基准来排序，输出最高和最低成绩
参考代码：
点击查看代码
#include<iostream>
#include<algorithm>
using namespace std;
//使用结构体存储数据
struct STU{
int sorce;
string num;
string name;
};
STU stu[110];
bool cmp(STU A,STU B){
return A.sorce<B.sorce;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>stu[i].name>>stu[i].num>>stu[i].sorce;
}
//使用sort以成绩为基准来排序
sort(stu,stu+n,cmp);
//输出最高和最低成绩
cout<<stu[n-1].name<<" "<<stu[n-1].num<<endl;
cout<<stu[0].name<<" "<<stu[0].num<<endl;
return 0;
}
1005 继续(3n+1)猜想
传送门
知识点：模拟，排序
思路：每个数x，经过一步步计算到达1，途中标记每一个中间量，表示他们被遍历过，可以由前面的数推算得到；剩下没有被标记过的就是关键数，从大到小排序后输出
参考代码：
点击查看代码
#include<iostream>
#include<algorithm>
using namespace std;
int a[110],b[110];
bool v[110];
//从大到小排序
bool cmp(int a,int b){
return a>b;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
int x=a[i];
while(x!=1){
if(x%2) x=(3*x+1);
x/=2;
//数据范围为1~100
if(x>100) continue;
//标记数字x被遍历
v[x]=true;
}
}
//将关键数存到到另一个数组，方便排序
int cnt=0;
for(int i=0;i<n;i++)
if(v[a[i]]==false)
b[cnt++]=a[i];
sort(b,b+cnt,cmp);
cout<<b[0];
for(int i=1;i<cnt;i++)
cout<<" "<<b[i];
cout<<endl;
return 0;
}
1006 换个格式输出整数
传送门
知识点：简单模拟
思路：分离百十个位上的数，按照题意输出
参考代码：
点击查看代码
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
//分离百十个上的数
int b=n/100,s=(n/10)%10,g=n%10;
for(int i=0;i<b;i++)
cout<<"B";
for(int i=0;i<s;i++)
cout<<"S";
for(int i=1;i<=g;i++)
cout<<i;
cout<<endl;
return 0;
}
1007 素数对猜想
传送门
知识点：模拟
思路：遍历所有差为2的数对，判断两个数是否都是素数
参考代码：
点击查看代码
#include<iostream>
using namespace std;
//判断素数
bool check(int x){
for(int i=2;i*i<=x;i++)
if(x%i==0)
return false;
return true;
}
int main()
{
int n,cnt=0;
cin>>n;
for(int i=3;i<=n-2;i++)
if(check(i)&&check(i+2))
cnt++;
cout<<cnt<<endl;
return 0;
}
1008 数组元素循环右移问题
传送门
知识点：数组
思路：将数组整体翻转，再将前半和后半数组分别翻转，可以达到右移效果
参考代码：
点击查看代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
//移动所有数字相当没动
m=m%n;
vector<int> a(n);
for(int i=0;i<n;i++)
cin>>a[i];
reverse(a.begin(),a.end());
reverse(a.begin(),a.begin()+m);
reverse(a.begin()+m,a.end());
cout<<a[0];
for(int i=1;i<n;i++)
cout<<" "<<a[i];
cout<<endl;
return 0;
}
1009 说反话
传送门
知识点：字符串
思路：使用string数组存储数据，reverse将数组翻转
参考代码：
点击查看代码
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
vector<string> words;
string w;
while(cin>>w)
words.push_back(w);
reverse(words.begin(),words.end());
cout<<words[0];
for(int i=1;i<words.size();i++)
cout<<" "<<words[i];
cout<<endl;
return 0;
}
1010 一元多项式求导
传送门
知识点：模拟
思路：根据题意求导就行，注意零多项式
参考代码：
点击查看代码
#include<iostream>
using namespace std;
int main()
{
int m,n;
cin>>m>>n;
//特判零多项式
if(n==0){
puts("0 0");
return 0;
}
if(m*n!=0)
cout<<m*n<<" "<<n-1;
while(cin>>m>>n){
if(m*n!=0)
cout<<" "<<m*n<<" "<<n-1;
}
return 0;
}
1011 A+B 和 C
传送门
知识点：数据范围
思路：int取值范围：-231~231-1；long long取值范围：-263~263-1
参考代码：
点击查看代码
#include<iostream>
using namespace std;
int main()
{
int T;
cin>>T;
for(int i=1;i<=T;i++){
cout<<"Case #"<<i<<": ";
long long a,b,c;
cin>>a>>b>>c;
if(a+b>c)
puts("true");
else puts("false");
}
return 0;
}
1012 数字分类
传送门
知识点：模拟
思路：不难发现，将数字对5取模就得到了分类，使用switch-case语句来更清楚的表达多分支；由于A4为小数，需要特判
关键信息：若分类之后某一类不存在数字，则在相应位置输出 N。
参考代码：
点击查看代码
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
int n;
cin>>n;
int a[6]={0},cnt=0;
bool flag=true,flag2=false;//表示加,表示A2这组没有数字
for(int i=0;i<n;i++){
int x;
cin>>x;
switch(x%5){
case 0:
if(x%2==0) a[1]+=x;
break;
case 1:
flag2=true;
a[2]+=(flag?x:-x);
flag=!flag;
break;
case 2:
a[3]++;
break;
case 3:
cnt++;
a[4]+=x;
break;
case 4:
a[5]=max(a[5],x);
break;
}
}
cout<<fixed<<setprecision(1);
for(int i=1;i<=5;i++){
int t=a[i];
//A2的运算中有加有减，所以最终结果为0不能表示这类没有数字
if((i!=2&&t==0)||(i==2&&flag2==false))
cout<<"N";
else{
if(i==4)
cout<<double(t)/cnt;
else cout<<t;
}
if(i!=5) cout<<" ";
}
return 0;
}
1013 数素数
传送门
知识点：数学知识-素数
思路：先求出足够多的素数，然后输出；
参考代码：
点击查看代码
#include<iostream>
#include<vector>
using namespace std;
bool check(int x){
for(int i=2;i*i<=x;i++)
if(x%i==0)
return false;
return true;
}
int main()
{
vector<int> a;
a.push_back(0);//让数组从1开始存储
for(int i=2;i<2e5;i++)
if(check(i))
a.push_back(i);
int m,n;
cin>>m>>n;
for(int i=m;i<=n;i++){
cout<<a[i];
if((i-m)%10==9)
cout<<endl;
else if(i!=n) cout<<" ";
}
return 0;
}
1014 福尔摩斯的约会
传送门
知识点：模拟
思路：
第一个条件：第一对相同的大写英文字母，以大写字母来代指星期，那么只有'A'~'G'是有效的
第二个条件：第一对相同的字符，24小时以'0''9'和'A''N'来代指
第三个条件：第一对相同英文字母，不区分大小写
参考代码：
点击查看代码
#include<iostream>
using namespace std;
string d[7]={"MON","TUE","WED","THU","FRI","SAT","SUN"};
bool check0(char ch){//判断是否为大写字母
return ch>='A'&&ch<='Z';
}
bool check1(char ch){//判断是否为数字
return ch>='0'&&ch<='9';
}
bool check2(char ch){//判断是否为小写字母
return ch>='a'&&ch<='z';
}
int main()
{
string s0,s1,t0,t1;
cin>>s0>>s1>>t0>>t1;
bool flag=false;
for(int i=0;i<s0.size()&&i<s1.size();i++){
//第二个条件：第一对相同的字符
if(flag&&s0[i]==s1[i]){
if(check1(s0[i])){
cout<<"0"<<s0[i]-'0'<<":";
break;
}
else if(s0[i]>='A'&&s0[i]<='N'){
cout<<s0[i]-'A'+10<<":";
break;
}
}
//第一个条件：第一对相同的大写英文字母
if(s0[i]==s1[i]&&s0[i]>='A'&&s0[i]<='G'){
cout<<d[s0[i]-'A']<<" ";
flag=true;//表示开始判断第二对
}
}
//第三个条件：第一对相同英文字母
for(int i=0;i<t0.size()&&i<t1.size();i++){
if(t0[i]==t1[i]&&(check0(t0[i])||check2(t1[i]))){
if(i<10)
cout<<"0"<<i;
else cout<<i;
break;
}
}
return 0;
}
1015 德才论
传送门
知识点：结构体排序
思路：根据题意来划分组；编写cmp函数用于排序，先以组别然后德分最后准考证据
参考代码：
点击查看代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct STU{
string num;//学号
int x,y;//德分，才分
int score;//总分
int group;//组别
};
vector<STU> stu;
bool cmp(STU a,STU b){
if(a.group!=b.group)
return a.group<b.group;
else if(a.score!=b.score)
return a.score>b.score;
else if(a.x!=b.x)
return a.x>b.x;
return a.num<b.num;
}
int main()
{
int n,l,h;
cin>>n>>l>>h;
for(int i=0;i<n;i++){
STU t;
int g;
cin>>t.num>>t.x>>t.y;
if(t.x<l||t.y<l) continue;
if(t.x>=h&&t.y>=h) g=1;
else if(t.x>=h) g=2;
else if(t.x>=t.y) g=3;
else g=4;
t.group=g;
t.score=t.x+t.y;
stu.push_back(t);
}
sort(stu.begin(),stu.end(),cmp);
cout<<stu.size()<<endl;
for(int i=0;i<stu.size();i++)
cout<<stu[i].num<<" "<<stu[i].x<<" "<<stu[i].y<<endl;
return 0;
}
1016 部分A+B
传送门
知识点：模拟
思路：遍历每一位数，记录目标数D出现次数cnt，根据目标数D和出现次数cnt构造P
参考代码：
点击查看代码
#include<iostream>
using namespace std;
//记录d在x中的出现次数
int fun(int x,int d){
int cnt=0;
while(x>1){
if(d==x%10) cnt++;
x/=10;
}
return cnt;
}
//构造cnt位的x
int p(int x,int cnt){
int ans=0;
for(int i=0;i<cnt;i++)
ans=ans*10+x;
return ans;
}
int main()
{
int a,da,b,db;
cin>>a>>da>>b>>db;
cout<<p(da,fun(a,da))+p(db,fun(b,db));
return 0;
}
1017 A除以B
传送门
知识点：高精度
思路：高精度除法的模板题
参考代码：
点击查看代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> dev(vector<int> &A,int b,int &r){
vector<int> C;
for(int i=A.size()-1;i>=0;i--){
r=r*10+A[i];
C.push_back(r/b);
r%=b;
}
//去除前导0
reverse(C.begin(),C.end());
while(C.size()>1&&C.back()==0) C.pop_back();
return C;
}
int main()
{
string a;
int b;
vector<int> A;
cin>>a>>b;
//逆序输入、逆序输出，和其他高精度运算保持一致
for(int i=a.size()-1;i>=0;i--)
A.push_back(a[i]-'0');
//余数
int r=0;
vector<int> q=dev(A,b,r);
for(int i=q.size()-1;i>=0;i--) cout<<q[i];
cout<<" "<<r;
return 0;
}
1018 锤子剪刀布
传送门
知识点：映射，模拟
思路：将字符和数字做映射，‘BCJ’映射为‘012’；平局两字符相等，相减为0；甲胜的情况BC、CJ、JB相减为-1、-1、2，加3模3后都为2；甲负即乙胜的情况为两字符相减后加3模3为1；在判断胜负的过程中记录每种字符胜利的次数
参考代码：
点击查看代码
#include<iostream>
#include<map>
using namespace std;
map<char,int> h={{'B',0},{'C',1},{'J',2}};
char s[3]={'B','C','J'};
int j[3];//甲的胜、负、平
int x[3],y[3];//布，锤子，剪刀
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++){
char ch0,ch1;
cin>>ch0>>ch1;
int flag=(h[ch0]-h[ch1]+3)%3;
j[flag]++;
if(flag==2)//甲胜
x[h[ch0]]++;
else if(flag==1)//乙胜
y[h[ch1]]++;
}
cout<<j[2]<<" "<<j[0]<<" "<<j[1]<<endl;
cout<<j[1]<<" "<<j[0]<<" "<<j[2]<<endl;
char J='B',Y='B';
int num0=x[0],num1=y[0];
for(int i=1;i<=2;i++)
if(num0<x[i]){
num0=x[i];
J=s[i];
}
for(int i=1;i<=2;i++)
if(num1<y[i]){
num1=y[i];
Y=s[i];
}
cout<<J<<" "<<Y;
return 0;
}
1019 数字黑洞
传送门
知识点：模拟
思路：
将输入的数字拆分为数组，排一次升序一次降序，再转化为数字，作相减操作，差作为下次循环的输入数字；
判断循环结束条件为差为0或者6174，当升序降序得到的数字相同时差为0，也意味着原来的数字各位相同；
注意不可以在开头判断输入为6174，因为当输入为6174时也应该走一遍这个过程即7641 - 1467 = 6174
参考代码：
点击查看代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//将数字转化为数组
vector<int> fun0(int n){
vector<int> a;
while(n>0){
a.push_back(n%10);
n/=10;
}
//加前导0
if(a.size()<4){
while(a.size()<4)
a.push_back(0);
}
reverse(a.begin(),a.end());
return a;
}
//将数组转化为数字
int fun1(vector<int> a){
int res=0;
for(int num:a)
res=res*10+num;
return res;
}
bool cmp(int a,int b){
return a>b;
}
int main()
{
int n;
cin>>n;
while(true){
vector<int> x=fun0(n);
sort(x.begin(),x.end(),cmp);
int a=fun1(x);
reverse(x.begin(),x.end());
int b=fun1(x);
n=a-b;
printf("%04d - %04d = %04d\n",a,b,n);
if(n==0||n==6174) break;
}
return 0;
}
1020 月饼
传送门
知识点：结构体排序，贪心
思路：要想获取最大收益，那么在需求量固定的情况下，应该尽可能卖更贵即单价更高的；输入为总量和总价，算出单价，根据单价排降序
参考代码：
点击查看代码
#include<iostream>
#include<algorithm>
using namespace std;
struct CAKE{
double stock,sell,unit;
};
CAKE cake[1010];
bool cmp(CAKE a,CAKE b){
return a.unit>b.unit;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>cake[i].stock;
for(int i=0;i<n;i++){
cin>>cake[i].sell;
cake[i].unit=cake[i].sell/cake[i].stock;
}
//贪心法，按照单价来排序，优先选最贵的
sort(cake,cake+n,cmp);
double ans=0;
for(int i=0;i<n;i++)
if(m>=cake[i].stock){
ans+=cake[i].sell;
m-=cake[i].stock;
}
else{
ans+=(m*cake[i].unit);
break;
}
printf("%.2f\n",ans);
return 0;
}