--------------------------------------------------------------------------------
1001-1110（已更新至最新！）
链接：https://pan.baidu.com/s/1Zs7rZn_Z3fyARkwUusviJA
提取码：xkyq
链接：https://pan.baidu.com/s/1hR8bLuuWiDYb2z9XnRxpOQ
提取码：c2yj
--------------------------------------------------------------------------------
更多详见>>
OJ题解系列 目录导航帖
--------------------------------------------------------------------------------
PAT乙级1001-1100
--------------------------------------------------------------------------------
这里是PAT乙级考试真题的第一部分（1001-1100）
首先总结一下PAT乙级考试的常考内容：
1.模拟：根据题目的描述/步骤，模拟题目的步骤编写算法
2.程序结构类：考察分支、循环、选择语句，如分段函数、分段计价、遍历数组
3.基础算法类：贪心、数论、枚举、排序等，一般情况下主要考察这几类，难度不会特别大，需注意算法的细节，对特殊数据的处理。
4.基础数据结构：主要就两种——数组和链表（静态或动态）、栈和队列
5.C++的STL模板类：简单了解stack,queue,priority_queue,map,vector,string,pair的用法
接下来就是题解部分了，每道算法题都标注有对应的算法标签，对于那些易错、较难或是测试点比较特殊的题目会着重标注，本章推荐的题目有：
| 1003 我要通过！ (20 分) | 字符串 + 文法生成式 |
|---|---|
| 1024 科学计数法 (20 分) 1054 求平均值 (20 分) |
字符串 |
| 1030 完美数列 (25 分) | 二分/two pointers |
| 1035 插入与归并 (25 分) | 排序 |
| 1040 有几个PAT (25 分) | DP |
| 1045 快速排序 (25 分) | 排序（枢轴选取） |
| 1070 结绳 (25 分) | 贪心 |
最后，希望大家都能在PAT乙级考试中取得自己理想的成绩！
--------------------------------------------------------------------------------
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int step = 0 ;
while(n!=1){
if(n % 2 == 0){
n = n / 2;
}else{
n = 3 * n + 1;
n = n / 2;
}
step++;
}
cout << step << endl;
return 0;
}
算法标签: 字符串 + 模拟
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
int total = 0;
for(int i=0;i<s.size();i++){
total += s[i] - '0';
}
int a[3];
bool flag = false;
a[0] = total / 100;
a[1] = total / 10 % 10;
a[2] = total % 10;
if(a[0]==0 && a[1]!=0){
a[0] = -1;
}else if(a[0]==0 && a[1]==0){
a[0] = -1;
a[1] = -1;
}
for(int i=0;i<3;i++){
switch(a[i]){
case 0:cout << "ling";break;
case 1:cout << "yi";break;
case 2:cout << "er";break;
case 3:cout <<"san";break;
case 4:cout <<"si";break;
case 5:cout <<"wu";break;
case 6:cout <<"liu";break;
case 7:cout <<"qi";break;
case 8:cout <<"ba";break;
case 9:cout <<"jiu";break;
default:break;
}
if(i==2){
}else{
if(a[i]==-1){
}else{
cout <<" ";
}
}
}
return 0;
}
算法标签: 字符串 + 文法生成式
注意: 三种文法均符合字符串表达式，依次判断
#include<bits/stdc++.h>
using namespace std;
int isPTA(string s){
int flag = 1;
for(int i=0;i<s.size();i++){
if(s[i] == 'P' || s[i] == 'A' || s[i] == 'T'){
continue;
}else{
flag = 0;
break;
}
}
return flag;
}
int isR2(string s){
int site;
for(int i=0;i<s.size();i++){
if(s[i] == 'P'){
site = i;
break;
}else if(s[i]!='A'){
return 0;
}
}
if(s[site] == 'P' && s[site+1] == 'A' && s[site+2] == 'T'){
}else{
return 0;
}
if(s.size()-site-3!=site){
return 0;
}
for(int i=site+3;i<s.size();i++){
if(s[i]!='A'){
return 0;
}
}
return 1;
}
int isR3(string s){
int site1;
int site2;
int cnt = 0;
for(int i=0;i<s.size();i++){
if(s[i] == 'P'){
site1 = i;
break;
}else if(s[i]!='A'){
return 0;
}
}
for(int i=site1+1;i<s.size();i++){
if(s[i] == 'T'){
site2 = i;
break;
}else if(s[i] =='A'){
cnt++;
}else{
return 0;
}
}
if(!cnt){
return 0;
}else{
site1 *= cnt;
}
if(s.size()-1-site2!=site1){
return 0;
}
for(int i=site2+1;i<s.size();i++){
if(s[i]!='A'){
return 0;
}
}
return 1;
}
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++){
string s;
cin >> s;
int f1 = isPTA(s);
int f2,f3;
if(f1){
f2 = isR2(s);
f3 = isR3(s);
if(f2 || f3){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}else{
cout << "NO" << endl;
}
}
return 0;
}
算法标签: 排序
#include<bits/stdc++.h>
using namespace std;
typedef struct score{
char name[15];
char classname[15];
int scorenum;
}score;
int n;
bool cmp(score s1,score s2){
if(s1.scorenum>s2.scorenum){
return true;
}else{
return false;
}
}
int main(){
cin >> n;
score s[n];
for(int i=0;i<n;i++){
cin >> s[i].name >> s[i].classname >> s[i].scorenum;
}
sort(s,s+n,cmp);
cout << s[0].name << " " << s[0].classname<<endl;
cout << s[n-1].name << " " << s[n-1].classname << endl;
return 0;
}
算法标签: 模拟
注意: 类比1001题
#include<bits/stdc++.h>
using namespace std;
int K;
int a[105];
int b[10005];
int main(){
cin >> K;
for(int i=0;i<K;i++){
cin >> a[i];
}
for(int i=0;i<K;i++){
int num = a[i];
while(num!=1){
if(num % 2 == 1){
num = num*3 +1;
num = num /2 ;
}else{
num = num / 2;
}
if(b[num]==1){
break;
}else{
b[num] = 1;
}
}
}
sort(a,a+K);
bool flag = false;
for(int i=K-1;i>=0;i--){
//cout << a[i] << endl;
if(b[a[i]]==0){
if(flag == true){
cout << " ";
}
cout << a[i];
flag = true;
}
}
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin >> N;
int b = N /100;
int s = (N/10) % 10;
for(int i=0;i<b;i++){
cout <<"B";
}
for(int i=0;i<s;i++){
cout << "S";
}
int g = N % 10;
for(int i=1;i<=g;i++){
cout << i;
}
cout << endl;
return 0;
}
算法标签: 素数判断 + Eratosthenes筛法
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int a[maxn]={
1,1,0};
int N;
int b[maxn];
int main(){
cin >> N;
for(int i=2;i<=N;i++){
if(!a[i]){
for(int j=2*i;j<=N;j+=i){
a[j] = 1;
}
}
}
int count = 0;
for(int i=0;i<=N;i++){
if(!a[i]){
b[count++] = i;
}
}
int result = 0;
for(int i=0;i<count-1;i++){
if(b[i+1]-b[i]==2){
result++;
}
}
cout << result << endl;
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
int N,M;
int main(){
cin >> N >> M;
M = M % N;
int a[N];
for(int i=0;i<N;i++){
cin >> a[i];
}
for(int i=0;i<N;i++){
if(i!=N-1){
cout << a[(N-M+i)%N] <<" ";
}else{
cout << a[(N-M+i)%N] << endl;
}
}
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
string s[100];
int main(){
int j = 0;
while((cin >> s[j])){
j++;
}
for(int i=j-1;i>=0;i--){
if(i!=0){
cout << s[i] << " ";
}else{
cout << s[i] <<endl;
}
}
return 0;
}
算法标签: 模拟
注意: 特判0的求导 输出0 0
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;
int j = 0;
while((cin >> a && cin >> b)){
if(j == 0 && b!=0){
cout << a*b << " " << b-1;
}else if(j==0 && b==0){
cout << "0 0" << endl;
break;
}else if(j!=0 && b==0){
break;
}else if (j!=0 && b!=0){
cout << " " << a*b << " " << b-1;
}
j++;
}
return 0;
}
算法标签: 数字加法
注意: 上溢、下溢需判断
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin >> T;
long long A,B,C;
for(int i=0;i<T;i++){
cin >> A >> B >> C;
if(A + B > C){
cout << "Case #" << i+1 << ": true"<<endl;
}else{
cout << "Case #" << i+1 << ": false"<<endl;
}
}
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
int a[1005];
int A1,A2,A3,A4,A5;
int q = 1;
int main(){
int N;
int num = 0;
bool flag1 =false,flag2=false,flag3=false,flag4=false,flag5=false;
cin >> N;
for(int i=0;i<N;i++){
cin >> a[i];
}
for(int i=0;i<N;i++){
if(a[i]%5 ==0 && a[i]%2==0){
A1 += a[i];
flag1 = true;
}else if(a[i]%5==1){
A2 += q*a[i];
q *= -1;
flag2 =true;
}else if(a[i]%5==2){
A3++;
flag3 = true;
}else if(a[i]%5==3){
A4 += a[i];
flag4 = true;
num++;
}else if(a[i]%5==4){
if(a[i]>A5){
A5 = a[i];
}
flag5 =true;
}
}
if(flag1 == false){
cout << "N" << " ";
}else{
cout << A1 << " ";
}
if(flag2 == false){
cout <<"N" << " ";
}else{
cout <<A2 << " ";
}
if(flag3 == false){
cout <<"N" << " ";
}else{
cout <<A3 << " ";
}
if(flag4 == false){
cout << "N" << " ";
}else{
double A4r = A4 * 1.0/(num * 1.0);
printf("%.1f ",A4r);
}
if(flag5 == false){
cout << "N" <<endl;
}else{
cout << A5 <<endl;
}
return 0;
}
算法标签: 数论 + 素数筛
#include<bits/stdc++.h>
using namespace std;
int a[200005]={
1,1,0};
int b[50005];
int main(){
int M,N;
cin >> M >> N;
for(int i=2;i<200002;i++){
if(!a[i]){
for(int j=2*i;j<200002;j = j+i){
a[j] = 1;
}
}
}
int s = 0;
for(int i=0;i<200002;i++){
if(!a[i]){
b[s++] = i;
}
}
int sum = 0;
for(int i=M;i<=N;i++){
sum++;
if(i!=N){
if(sum!=0 && sum%10==0){
cout << b[i-1] << endl;
}else{
cout << b[i-1] << " ";
}
}else{
cout << b[i-1];
}
}
return 0;
}
算法标签: 字符串
#include<bits/stdc++.h>
using namespace std;
string str[7] = {
"MON","TUE","WED","THU","FRI","SAT","SUN"};
int isupper(char c){
if(c>='A' && c<='G'){
return 1;
}else{
return 0;
}
}
int isalpha(char c){
if(c>='A' && c<='Z'){
return 1;
}else if(c>='a' && c<='z'){
return 1;
}else{
return 0;
}
}
int main(){
string s1,s2,s3,s4;
char day,hour;
int minute;
cin >> s1 >> s2 >> s3 >> s4;
int size1 = min(s1.size(),s2.size());
int size2 = min(s3.size(),s4.size());
int count = 0;
for(int i=0;i<size1;i++){
if(s1[i]==s2[i] && count == 0 && isupper(s1[i]) && isupper(s2[i])){
day = s1[i];
count++;
}else if(s1[i]==s2[i] && ((s1[i]>='0' && s1[i]<='9')||(s2[i]>='A' && s2[i]<='N')) && count!=0){
hour = s1[i];
break;
}
}
for(int i=0;i<size2;i++){
if(s3[i]==s4[i] && isalpha(s3[i]) && isalpha(s4[i])){
minute = i;
break;
}
}
string daystr = str[(int)(day-'A')];
int h;
if(isalpha(hour)){
h = hour - 'A' + 10;
}else{
h = hour -'0';
}
cout << daystr << " ";
if(h<10){
cout << "0" << h;
}else{
cout << h ;
}
cout << ":";
if(minute<10){
cout << "0" << minute;
}else{
cout << minute;
}
cout << endl;
return 0;
}
算法标签: 排序
注意: 结构体排序，常考点
#include<bits/stdc++.h>
using namespace std;
int N,L,H;
typedef struct score{
int IDnum;
int Dscore;
int Cscore;
}score;
const int maxn = 1e5+5;
score DC1[maxn];
score DC2[maxn];
score DC3[maxn];
score DC4[maxn];
bool cmp(score s1,score s2){
if(s1.Cscore+s1.Dscore>s2.Cscore+s2.Dscore){
return true;
}else if(s1.Cscore+s1.Dscore == s2.Cscore+s2.Dscore){
if(s1.Dscore>s2.Dscore){
return true;
}else if (s1.Dscore == s2.Dscore){
if(s1.IDnum<s2.IDnum){
return true;
}else{
return false;
}
}else{
return false;
}
}else{
return false;
}
}
int main(){
cin >> N >> L >> H;
int first = 0,second =0,third =0,fourth =0;
int nopass = 0;
for(int i=0;i<N;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(b<L || c<L){
nopass++;
continue;
}else if(b>=H && c>=H){
DC1[first].IDnum = a;
DC1[first].Dscore = b;
DC1[first++].Cscore = c;
}else if(b>=H && c<H){
DC2[second].IDnum = a;
DC2[second].Dscore = b;
DC2[second++].Cscore = c;
}else if(b<H && c<H && b>=c){
DC3[third].IDnum = a;
DC3[third].Dscore = b;
DC3[third++].Cscore = c;
}else{
DC4[fourth].IDnum = a;
DC4[fourth].Dscore = b;
DC4[fourth++].Cscore = c;
}
}
cout << N-nopass << endl;
sort(DC1,DC1+first,cmp);
sort(DC2,DC2+second,cmp);
sort(DC3,DC3+third,cmp);
sort(DC4,DC4+fourth,cmp);
for(int i=0;i<first;i++){
printf("%d %d %d\n",DC1[i].IDnum,DC1[i].Dscore,DC1[i].Cscore);
}
for(int i=0;i<second;i++){
printf("%d %d %d\n",DC2[i].IDnum,DC2[i].Dscore,DC2[i].Cscore);
}
for(int i=0;i<third;i++){
printf("%d %d %d\n",DC3[i].IDnum,DC3[i].Dscore,DC3[i].Cscore);
}
for(int i=0;i<fourth;i++){
printf("%d %d %d\n",DC4[i].IDnum,DC4[i].Dscore,DC4[i].Cscore);
}
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
int main(){
long long a,b,Da,Db;
int anum = 0, bnum = 0;
cin >> a >> Da >> b >> Db;
while(a>0){
if(a%10==Da){
anum++;
}
a = a/10;
}
while(b>0){
if(b%10==Db){
bnum++;
}
b = b / 10;
}
long long result = 0;
long long muti = 1;
for(int i=0;i<anum;i++){
result += muti*Da;
muti *=10;
}
muti = 1;
for(int i=0;i<bnum;i++){
result += muti*Db;
muti*=10;
}
cout << result << endl;
return 0;
}
算法标签: 高精除低精
注意: 仿照竖式计算的方法，建数组来模拟除法
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
int a[maxn];
int main(){
string s;
int n;
cin >> s;
cin >> n;
int result = 0;
for(int i=0;i<s.size();i++){
result = result + s[i] - '0';
a[i] = result / n;
result = result % n;
result *=10;
}
if(s.size()==1 && a[0]==0){
cout << "0 " << result/10 << endl;
return 0;
}
for(int i=0;i<s.size();i++){
if(i==0){
if(a[i]==0){
continue;
}else{
cout << a[i];
}
}else{
cout << a[i];
}
}
cout << " " << result/10 <<endl;
return 0;
}
算法标签: 模拟
注意: 可能出现9种情况，都需要判断
#include<bits/stdc++.h>
using namespace std;
int N;
int a[3];
int as[3];
int b[3];
int bs[3];
char x[3] = {
'B','C','J'};
int main(){
cin >> N;
for(int i=0;i<N;i++){
string s1,s2;
cin >> s1 >> s2;
if(s1=="C" && s2=="J"){
a[1]++;
as[0]++;
bs[2]++;
}else if(s1=="C" && s2=="C"){
as[1]++;
bs[1]++;
}else if(s1=="C" && s2=="B"){
b[0]++;
as[2]++;
bs[0]++;
}else if(s1=="J" && s2=="C"){
b[1]++;
as[2]++;
bs[0]++;
}else if(s1=="J" && s2=="J"){
as[1]++;
bs[1]++;
}else if(s1=="J" && s2=="B"){
a[2]++;
as[0]++;
bs[2]++;
}else if(s1=="B" && s2=="C"){
a[0]++;
as[0]++;
bs[2]++;
}else if(s1=="B" && s2=="J"){
b[2]++;
as[2]++;
bs[0]++;
}else if(s1=="B" && s2=="B"){
as[1]++;
bs[1]++;
}
getline(cin,s1);
}
for(int i=0;i<3;i++){
if(i!=2){
cout << as[i] << " ";
}else{
cout << as[i] << endl;
}
}
for(int i=0;i<3;i++){
if(i!=2){
cout << bs[i] << " ";
}else{
cout << bs[i] << endl;
}
}
int maxn = -1;
int site = 0;
for(int i=0;i<3;i++){
if(a[i]>maxn){
maxn = a[i];
site = i;
}
}
cout << x[site] <<" ";
maxn = -1;
site = 0;
for(int i=0;i<3;i++){
if(b[i]>maxn){
maxn = b[i];
site = i;
}
}
cout << x[site] << endl;
return 0;
}
算法标签: 模拟
注意: 竖式计算减法
#include<bits/stdc++.h>
using namespace std;
int N;
int a[4];
int b[4];
int c[4];
bool cmp(int a,int b){
return a>b;
}
int main(){
cin >> N;
a[0] = N / 1000;
a[1] = (N / 100) % 10;
a[2] = (N / 10) % 10;
a[3] = N % 10;
if((a[0]==a[1])&&(a[1]==a[2])&&(a[2]==a[3])){
cout << a[0] << a[1] << a[2] << a[3] << " - " << a[0] << a[1] << a[2] << a[3] << " = 0000" << endl;
return 0;
}else{
while(1){
sort(a,a+4,cmp);
cout << a[0] << a[1] << a[2] << a[3] << " - " ;
for(int i=0;i<4;i++){
b[i] = a[i];
}
sort(b,b+4);
cout << b[0] << b[1] << b[2] << b[3] << " = ";
for(int i=3;i>=0;i--){
if(a[i]-b[i]<0){
c[i] = a[i] + 10 - b[i];
a[i-1]--;
}else{
c[i] = a[i] - b[i];
}
}
cout << c[0] << c[1] << c[2] << c[3] << endl;
if(c[0]==6 && c[1]==1 && c[2]==7 && c[3]==4){
break;
}else{
for(int i=0;i<4;i++){
a[i] = c[i];
}
}
}
}
return 0;
}
算法标签: 贪心
注意: 完全背包问题的简单版
#include<bits/stdc++.h>
using namespace std;
int N,D;
int maxn = 1005;
typedef struct mooncake{
double num;
double price;
double singleprice;
}mooncake;
bool cmp(mooncake m1,mooncake m2){
return m1.singleprice > m2.singleprice;
}
int main(){
cin >> N >> D;
mooncake m[N];
for(int i=0;i<N;i++){
cin >> m[i].num;
}
for(int i=0;i<N;i++){
cin >> m[i].price;
}
for(int i=0;i<N;i++){
m[i].singleprice = (m[i].price * 1.0) /(m[i].num * 1.0);
}
sort(m,m+N,cmp);
int site = 0;
double totalprice = 0.0;
while(D!=0){
if(m[site].num <= D){
D -= m[site].num;
totalprice = totalprice + m[site].price;
}else{
totalprice = totalprice + m[site].singleprice * D;
D = 0;
}
site++;
}
printf("%.2lf\n",totalprice);
return 0;
}
算法标签: 模拟
注意: 输出0
#include<bits/stdc++.h>
using namespace std;
int a[15];
int main(){
string s;
cin >> s;
for(int i=0;i<s.size();i++){
a[s[i]-'0']++;
}
for(int i=0;i<10;i++){
if(a[i]!=0){
cout << i << ":" << a[i] << endl;
}
}
return 0;
}
算法标签: 进制
注意: 栈模拟进制转换
#include<bits/stdc++.h>
using namespace std;
long long A,B;
int D;
int main(){
cin >> A >> B;
if(A==0 && B==0){
cout << "0" << endl;
return 0;
}
cin >> D;
long long result = A+B;
stack<int>a;
while(result>0){
a.push(result%D);
result = result/D;
}
while(!a.empty()){
int num = a.top();
cout << num;
a.pop();
}
cout << endl;
return 0;
}
算法标签: 数字
注意: 特判0的输出，先输出1-9最小的一个数字，然后依次按照0-9输出结果
#include<bits/stdc++.h>
using namespace std;
int a[15];
int main(){
for(int i=0;i<10;i++){
cin >> a[i];
}
if(a[0]>0){
int site =1;
while(a[site]==0){
site++;
}
cout << site;
a[site]--;
for(int i=0;i<10;i++){
for(int j=0;j<a[i];j++){
cout << i;
}
}
cout << endl;
}else{
for(int i=1;i<10;i++){
for(int j=0;j<a[i];j++){
cout << i;
}
}
cout << endl;
}
return 0;
}
算法标签: 字符串
注意: 这道题目主要考察字符串的分解，根据正则表达式得知，首先读入正负号，然后输出结果的正负号（正数不输出，负数输出-），接着读入科学计数法的有效数字部分（注意对小数点的位置记录），然后读入E之后的指数部分，指数>0，意味着小数点右移（注意低位补0），指数<0，意味着小数点左移（注意高位补0），然后输出结果即可
#include<bits/stdc++.h>
using namespace std;
int main(){
string str;
cin >> str;
int site = str.find('E');
string n = str.substr(1,site-1);
string e = str.substr(site+1);
int en = stoi(e);
if(str[0] == '-'){
cout << "-";
}
if(en>=0){
cout << str[1];
int j=2,cnt=0;
for(j=2;j<site && cnt<en;j++){
if(str[j]=='.'){
continue;
}else{
cout << str[j];
cnt++;
}
}
if(j==site){
for(int i=0;i<en-cnt;i++){
cout << "0" ;
}
}else{
cout <<".";
for(int i=j;j<site;j++){
cout << str[j];
}
}
}else{
cout << "0.";
for(int i=0;i<abs(en)-1;i++){
cout << "0";
}
cout << str[1];
for(int j=2;j<site;j++){
if(str[j]=='.'){
continue;
}else{
cout << str[j];
}
}
}
return 0;
}
算法标签: 模拟 + 链表
注意: 以K个元素为单位，对链表进行反转
#include<bits/stdc++.h>
using namespace std;
int start,N,K;
const int maxn = 1e5+5;
int data[maxn];
int eadd[maxn];
int listnum[maxn];
int main(){
cin.tie(0);
cout.tie(0);
cin >> start >> N >> K;
for(int i=0;i<N;i++){
int addr;
cin >> addr;
cin >> data[addr] >> eadd[addr];
}
int nextadd = start;
int count = 0;
while(nextadd!=-1){
listnum[count++] = nextadd;
nextadd = eadd[nextadd];
}
for(int i=0;i<(count-count%K);i+=K){
reverse(listnum+i,listnum+i+K);
}
for(int i=0;i<count;i++){
if(i!=count-1){
printf("%05d %d %05d\n",listnum[i],data[listnum[i]],listnum[i+1]);
}else{
printf("%05d %d %d\n",listnum[i],data[listnum[i]],-1);
}
}
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
const int CLK=100;
int main(){
int C1,C2;
cin >> C1 >> C2;
int C = C2-C1;
double times = C*1.0 / (CLK*1.0);
int second = round(times);
int hour = second / 3600;
int minute = (second % 3600) / 60;
int s = second % 60;
if(hour<10){
cout << "0" << hour << ":";
}else{
cout << hour << ":";
}
if(minute<10){
cout << "0" << minute << ":";
}else{
cout << minute << ":";
}
if(s<10){
cout << "0" << s << endl;
}else{
cout << s << endl;
}
return 0;
}
算法标签: 模拟 + 字符串
注意: 先计算最大的打印行数，这个数比较容易计算，根据高斯公式列出表达式 n ∗ ( n − 1 ) 2 ∗ 2 − 1 < = N \frac{n*(n-1)}{2}*2-1<=N 2n∗(n−1)∗2−1<=N，n即为打印行数，然后按照普通的打印方法将其输出即可！
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
char c;
cin >> N >> c;
double n = sqrt((1+N)*1.0/2.0);
int maxn = int(n);
int rest = N -(2*maxn*maxn-1);
for(int i=n;i>0;i--){
for(int j=0;j<(2*maxn-2*i)/2;j++){
printf(" ");
}
for(int j=0;j<2*i-1;j++){
printf("%c",c);
}
printf("\n");
}
for(int i=2;i<=n;i++){
for(int j=0;j<(2*maxn-2*i)/2;j++){
printf(" ");
}
for(int j=0;j<2*i-1;j++){
printf("%c",c);
}
printf("\n");
}
cout << rest << endl;
return 0;
}
算法标签: 模拟 + 排序
#include<bits/stdc++.h>
using namespace std;
int N;
int check(int year,int month ,int day){
if(abs(2014-year>200)){
return 0;
}else if(abs(2014-year)==200 && (9-month)>0){
return 0;
}else if(abs(2014-year)==200 && (9-month)==0 && (6-day)>0){
return 0;
}else if(year-2014>0){
return 0;
}else if(year==2014 && month>9){
return 0;
}else if(year==2014 && month==9 && day>6){
return 0;
}else{
return 1;
}
}
const int maxn = 1e5+5;
typedef struct birth{
string name;
int year;
int month;
int day;
}birth;
birth b[maxn];
bool cmp(birth b1,birth b2){
if(b1.year<b2.year){
return true;
}else if(b1.year==b2.year && b1.month<b2.month){
return true;
}else if(b1.year==b2.year && b1.month==b2.month && b1.day<b2.day){
return true;
}else{
return false;
}
}
int main(){
cin >> N;
int count = 0;
for(int i=0;i<N;i++){
string name,birthday;
cin >> name >> birthday;
int year = 0;
int month = 0;
int day = 0;
for(int i=0;i<4;i++){
year = year*10 +birthday[i]-'0';
}
for(int i=5;i<7;i++){
month = month*10 + birthday[i] -'0';
}
for(int i=8;i<10;i++){
day = day*10 + birthday[i] -'0';
}
if(check(year,month,day)){
b[count].name = name;
b[count].year = year;
b[count].month = month;
b[count++].day = day;
}
}
sort(b,b+count,cmp);
if(count == 0){
cout << "0" << endl;
}else{
cout << count << " " << b[0].name << " " << b[count-1].name <<endl;
}
return 0;
}
算法标签: 字符串
注意: 从左到右依次线性扫描字符串，若该字母未出现，则直接输出，并记录当前缺省的键，下次再遇到时直接跳过
#include<bits/stdc++.h>
using namespace std;
int a[55];
int isUpper(char c){
if(c>='A' && c<='Z'){
return 1;
}else{
return 0;
}
}
int isdigit(char c){
if(c>='0' && c<='9'){
return 1;
}else{
return 0;
}
}
int isLower(char c){
if(c>='a' && c<='z'){
return 1;
}else{
return 0;
}
}
int main(){
string s1,s2;
cin >> s1 >> s2;
int j=0;
for(int i=0;i<s1.size();i++){
if(s1[i]!=s2[j]){
if(s1[i]=='_'){
if(!a[10]){
a[10] = 1;
cout << s1[i];
}
}else if(isdigit(s1[i])){
if(!a[s1[i]-'0']){
a[s1[i]-'0'] = 1;
cout << s1[i];
}
}else if(isLower(s1[i])){
if(!a[11+s1[i]-'a']){
a[11+s1[i]-'a'] = 1;
char alpha = s1[i] - 'a' + 'A';
cout << alpha;
}
}else if(isUpper(s1[i])){
if(!a[11+s1[i]-'A']){
a[11+s1[i]-'A'] = 1;
cout << s1[i];
}
}
}else{
j++;
}
}
return 0;
}
算法标签: 二分/two pointers
注意: 本题有若干种解法，如枚举m，二分M=mp，或者将头指针i指向数列头部，将另一个指针j指向mp的位置，由于单调性，指针i/j均只能向尾部移动，此时的算法复杂度均能满足题意要求
#include "iostream"
#include "string"
#include "algorithm"
using namespace std;
int main(){
int N,maxCount=1;
double p,a[100010];
scanf("%d %lf",&N,&p);
for (int i=0;i<N;i++)
{
scanf("%lf",&a[i]);
}
sort(a,a+N);
for(int i=0;i<N;i++){
double beginNum=a[i];
for(int j=i+maxCount;j<N;j++){
double endNum=a[j];
if(beginNum*p<endNum){
break;
}
if (j-i+1>maxCount)
{
maxCount=j-i+1;
}
}
}
cout<<maxCount;
}
算法标签: 模拟
注意: 按照题目所给出的权重，模拟计算校验码即可
#include<bits/stdc++.h>
using namespace std;
int a[20] = {
7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
int check[11] = {
1,0,10,9,8,7,6,5,4,3,2};
int isdigit(char c){
if(c>='0' && c<='9'){
return 1;
}else{
return 0;
}
}
int main(){
int N;
cin >> N;
int count = 0;
for(int i=0;i<N;i++){
string str;
cin >> str;
int result = 0;
bool flag = true;
for(int j=0;j<str.size()-1;j++){
if(isdigit(str[j])){
result += (str[j] -'0')*a[j];
}else{
flag = false;
break;
}
}
if(flag==false){
cout << str << endl;
count++;
}else{
int r = result % 11;
if(r==2 && str[17]!='X'){
cout << str << endl;
count++;
}else if(r!=2 && str[17]-'0' != check[r]){
cout << str << endl;
count++;
}
}
}
if(count==0){
cout << "All passed" << endl;
}
return 0;
}
算法标签: 模拟 + 排序
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int s[maxn];
int main(){
int N;
cin >> N;
for(int i=0;i<N;i++){
int a,score;
cin >> a >> score;
s[a] += score;
}
int maxs = 0;
int num = 0;
for(int i=0;i<maxn;i++){
if(s[i]>maxs){
maxs = s[i];
num = i;
}
}
cout << num <<" " << maxs<<endl;
return 0;
}
算法标签: 字符串
注意: 本题可先开一个桶，记录缺省的键，然后从左到右依次扫描字符串，遇到桶里的键时，跳过不输出
#include<bits/stdc++.h>
using namespace std;
int a[50];
int isupper(char c){
if(c>='A' && c<='Z'){
return 1;
}else{
return 0;
}
}
int islower(char c){
if(c>='a' && c<='z'){
return 1;
}else{
return 0;
}
}
int isdigit(char c){
if(c>='0' && c<='9'){
return 1;
}else{
return 0;
}
}
string bad,str;
int main(){
getline(cin,bad);
getline(cin,str);
for(int i=0;i<bad.size();i++){
if(bad[i] == '_'){
a[10] = 1;
}else if(bad[i]==','){
a[11] = 1;
}else if(bad[i]=='.'){
a[12] = 1;
}else if(bad[i]=='-'){
a[13] = 1;
}else if(bad[i]=='+'){
a[14] = 1;
}else if(isdigit(bad[i])){
a[bad[i]-'0'] = 1;
}else if(islower(bad[i])){
a[bad[i]-'a'+15] = 1;
}else if(isupper(bad[i])){
a[bad[i]-'A'+15] = 1;
}
}
for(int i=0;i<str.size();i++){
if(str[i]=='_' && a[10]==1){
}else if(str[i]==',' && a[11]==1){
}else if(str[i]=='.' && a[12]==1){
}else if(str[i]=='-' && a[13]==1){
}else if(isupper(str[i]) && (a[14]==1 || a[str[i]-'A'+15]==1)){
}else if(islower(str[i]) && a[str[i]-'a'+15]==1){
}else if(isdigit(str[i]) && a[str[i]-'0']==1){
}else{
cout << str[i];
}
}
cout << endl;
return 0;
}
算法标签: 数论
注意: 本题可参考分数类模板，注意long long的数据范围
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b){
long long tmp;
if(a<b){
tmp = a;
a = b;
b = tmp;
}
return a%b? gcd(b,a%b) : b;
}
long long lcd(long long a,long long b){
long long g = gcd(a,b);
return(1LL*(a/g)*(b/g));
}
void process(long long a,long long b,int T){
bool flag = false,flag1 = false,flag2=false;
if(a<0){
flag1 = true;
}
if(b<0){
flag2 = true;
}
if(flag1 && flag2){
a = -a;
b = -b;
flag = false;
}else if(flag1 && !flag2){
a = -a;
flag = true;
}else if(!flag1 && flag2){
b = -b;
flag = true;
}
if(a==0 && b!=0){
cout << "0";
}else if(b==0 && T==1){
cout << "Inf";
}else{
long long g = gcd(a,b);
a = a/g;
b = b/g;
if(flag){
cout << "(-";
}
if(a>=b){
int p = a/b;
int q = a%b;
if(q!=0){
cout << p <<" " << q << "/" << b;
}else{
cout << p ;
}
}else{
cout << a << "/" << b;
}
if(flag){
cout <<")";
}
}
}
int main(){
char str1[50],str2[50];
cin >> str1 >> str2;
long long a,b,c,d;
sscanf(str1,"%lld/%lld",&b,&a);
sscanf(str2,"%lld/%lld",&d,&c);
long long plus1 = b*c + a*d;
long long plus2 = a*c;
long long minus1 = b*c - a*d;
long long minus2 = a*c;
long long mutl1 = b*d;
long long mutl2 = a*c;
long long div1 = b*c;
long long div2 = a*d;
process(b,a,0);
cout << " + " ;
process(d,c,0);
cout << " = " ;
process(plus1,plus2,0);
cout << endl;
process(b,a,0);
cout << " - " ;
process(d,c,0);
cout << " = " ;
process(minus1,minus2,0);
cout << endl;
process(b,a,0);
cout << " * " ;
process(d,c,0);
cout << " = " ;
process(mutl1,mutl2,0);
cout << endl;
process(b,a,0);
cout << " / " ;
process(d,c,0);
cout << " = " ;
process(div1,div2,1);
cout << endl;
return 0;
}
算法标签: 排序
注意: 本题考察两种排序的过程，插入排序 VS 归并排序，首先我们看插入排序，选择一个数并插入无序的序列中，这也就意味着序列的前半段必定是有序的，而后半段是无序的；归并排序是每一个子序列可能是有序的，但是总体是无序的，因此我们根据两个排序的不同方法，模拟排序的过程，检验出是其中的一种排序，然后迭代下一轮排序，并输出即可！
#include<bits/stdc++.h>
using namespace std;
int N;
const int maxn = 1e2+5;
int a[maxn];
int b[maxn];
int main(){
cin >> N;
for(int i=0;i<N;i++){
cin >> a[i];
}
for(int i=0;i<N;i++){
cin >> b[i];
}
int j=0;
while(j<N-1 && b[j]<=b[j+1]){
j++;
}
int site1 = j;
j++;
while(j<N && a[j]==b[j]){
j++;
}
if(j==N){
cout << "Insertion Sort" << endl;
sort(b,b+site1+2);
for(int i=0;i<N;i++){
if(i!=N-1){
cout << b[i] << " ";
}else{
cout << b[i];
}
}
}else{
cout <<"Merge Sort" << endl;
int k = 1;
while(1){
k *= 2;
for(int i=0;i<N-N%k;i+=k){
sort(a+i,a+i+k);
}
sort(a+N-N%k,a+N);
bool flag = true;
for(int i=0;i<N;i++){
if(a[i]!=b[i]){
flag = false;
break;
}
}
if(flag){
break;
}
}
k *= 2;
for(int i=0;i<N-N%k;i+=k){
sort(a+i,a+i+k);
}
sort(a+N-N%k,a+N);
for(int i=0;i<N;i++){
if(i!=N-1){
cout << a[i] << " ";
}else{
cout << a[i];
}
}
}
return 0;
}
算法标签: 字符串
注意: 字符串打印题
#include<bits/stdc++.h>
using namespace std;
string str;
int N;
int main(){
cin >> N;
cin >> str;
for(int i=0;i<N;i++){
cout << str;
}
cout << endl;
int h = (round)(N*0.5) - 2;
for(int i=0;i<h;i++){
cout << str;
for(int j=0;j<N-2;j++){
cout << " ";
}
cout << str;
cout << endl;
}
for(int i=0;i<N;i++){
cout << str;
}
cout << endl;
return 0;
}
算法标签: 数论
注意: 模拟高精减法的过程
#include<bits/stdc++.h>
using namespace std;
string str1,str2;
int a[3];
int b[3];
int c[3];
bool check(int a[3],int b[3]){
if(a[0]<b[0]){
return true;
}else if(a[0]==b[0] && a[1]<b[1]){
return true;
}else if(a[0]==b[0] && a[1]==b[1] && a[2]<=b[2]){
return true;
}else{
return false;
}
}
int main(){
cin >> str1 >> str2;
int site1 = str1.find('.');
int site2 = str1.find('.',site1+1);
for(int i=0;i<site1;i++){
a[0] = a[0]*10 + str1[i] - '0';
}
for(int i=site1+1;i<site2;i++){
a[1] = a[1]*10 + str1[i] - '0';
}
for(int i=site2+1;i<str1.size();i++){
a[2] = a[2]*10 + str1[i] - '0';
}
site1 = str2.find('.');
site2 = str2.find('.',site1+1);
for(int i=0;i<site1;i++){
b[0] = b[0]*10 + str2[i] - '0';
}
for(int i=site1+1;i<site2;i++){
b[1] = b[1]*10 + str2[i] - '0';
}
for(int i=site2+1;i<str2.size();i++){
b[2] = b[2]*10 + str2[i] - '0';
}
bool flag = check(a,b);
if(flag == false){
for(int i=0;i<3;i++){
c[i] = b[i];
}
for(int i=0;i<3;i++){
b[i] = a[i];
}
for(int i=0;i<3;i++){
a[i] = c[i];
}
}
if(b[2]-a[2]<0){
b[1]--;
b[2] = b[2] + 29 -a[2];
}else{
b[2] = b[2] -a[2];
}
if(b[1]-a[1]<0){
b[0]--;
b[1] = b[1] +17 -a[1];
}else{
b[1] = b[1] - a[1];
}
b[0] = b[0] -a[0];
if(flag==false){
cout << "-";
}
cout << b[0] << "." << b[1] << "." << b[2] << endl;
return 0;
}
算法标签: 哈希
注意: 由于成绩的范围比较窄，因此可以开一个桶记录分数，统计并输出！
#include<bits/stdc++.h>
using namespace std;
int N,K;
int a[105];
int main(){
cin >> N;
int score;
for(int i=0;i<N;i++){
scanf("%d",&score);
a[score]++;
}
cin >> K;
for(int i=0;i<K;i++){
scanf("%d",&score);
cout << a[score];
if(i!=K-1){
cout << " ";
}
}
cout << endl;
return 0;
}
算法标签: 字符串
注意: 统计指定的字符个数是否满足题意
#include<bits/stdc++.h>
using namespace std;
string str1,str2;
int a[105];
int b[105];
int isupper(char c){
if(c>='A' && c<='Z'){
return 1;
}else{
return 0;
}
}
int islower(char c){
if(c>='a' && c<='z'){
return 1;
}else{
return 0;
}
}
int isdigit(char c){
if(c>='0' && c<='9'){
return 1;
}else{
return 0;
}
}
int main(){
cin >> str1 >> str2;
for(int i=0;i<str1.size();i++){
if(isdigit(str1[i])){
a[str1[i]-'0']++;
}else if(isupper(str1[i])){
a[str1[i]-'A'+10]++;
}else if(islower(str1[i])){
a[str1[i]-'a'+40]++;
}
}
for(int i=0;i<str2.size();i++){
if(isdigit(str2[i])){
b[str2[i]-'0']++;
}else if(isupper(str2[i])){
b[str2[i]-'A'+10]++;
}else if(islower(str2[i])){
b[str2[i]-'a'+40]++;
}
}
bool flag = true;
int rest = 0;
int count1=0,count2=0;
for(int i=0;i<100;i++){
count1 += a[i];
count2 += b[i];
if(a[i]<b[i]){
flag = false;
rest += (b[i]-a[i]);
}
}
if(flag==false){
cout << "No ";
cout << rest << endl;
}else{
cout << "Yes ";
cout << count1-count2 << endl;
}
return 0;
}
算法标签: 动态规划
注意: 把字符串分成3个部分,left/mid/right，若mid=‘A’,那么这个点处PAT的数量等于 l e f t ( P ) ∗ r i g h t ( T ) left(P)*right(T) left(P)∗right(T)，因此 ∑ \sum ∑累加即可
#include<bits/stdc++.h>
using namespace std;
const long long M = 1000000007;
long long result;
const int maxn = 1e5+5;
string str;
int main(){
cin >> str;
int Tcount = 0;
int Pcount = 0;
for(int i=0;i<str.size();i++){
if(str[i]=='T'){
Tcount++;
}
}
for(int i=0;i<str.size();i++){
if(str[i]=='T'){
Tcount--;
}else if(str[i]=='P'){
Pcount++;
}else if(str[i]=='A'){
result = (result + Tcount*Pcount)%M;
}
}
cout << result << endl;
return 0;
}
算法标签: 排序
#include<bits/stdc++.h>
using namespace std;
int N;
int M;
typedef struct test{
string num;
int testnum;
int normalnum;
}test;
const int maxn = 1e3 +5;
test t[maxn];
bool cmp(test t1,test t2){
if(t1.testnum<t2.testnum){
return true;
}else{
return false;
}
}
int main(){
cin >> N;
for(int i=0;i<N;i++){
cin >> t[i].num >> t[i].testnum >> t[i].normalnum;
}
sort(t,t+N,cmp);
cin >> M;
for(int i=0;i<M;i++){
int a;
cin >> a;
cout << t[a-1].num << " " << t[a-1].normalnum <<endl;
}
return 0;
}
算法标签: 哈希
注意: 和之前一道用桶统计分数的题目类似，本题需要开一个桶记录大小写共52个字母出现的次数
#include<bits/stdc++.h>
using namespace std;
int A[60];
int isupper(char c){
if(c>='A' && c<='Z'){
return 1;
}else{
return 0;
}
}
int islower(char c){
if(c>='a' && c<='z'){
return 1;
}else{
return 0;
}
}
int main(){
string str;
getline(cin,str);
for(int i=0;i<str.size();i++){
if(isupper(str[i])){
A[str[i]-'A']++;
}else if(islower(str[i])){
A[str[i]-'a']++;
}
}
int site,maxn=-1;
for(int i=0;i<26;i++){
if(A[i]>maxn){
maxn = A[i];
site = i;
}
}
printf("%c %d",site+'a',maxn);
return 0;
}
算法标签: 字符串 + 哈希
注意: 先统计输入的字符串中PATEST的个数，然后顺序遍历数组，挨个输出即可
#include<bits/stdc++.h>
using namespace std;
string str;
int a[6];
int main(){
cin >> str;
for(int i=0;i<str.size();i++){
if(str[i]=='P'){
a[0]++;
}else if(str[i]=='A'){
a[1]++;
}else if(str[i]=='T'){
a[2]++;
}else if(str[i]=='e'){
a[3]++;
}else if(str[i]=='s'){
a[4]++;
}else if(str[i]=='t'){
a[5]++;
}
}
int count = 0;
for(int i=0;i<6;i++){
count+=a[i];
}
while(count>0){
for(int i=0;i<6;i++){
if(i==0 && a[i]>0){
a[i]--;
count--;
cout << "P";
}else if(i==1 && a[i]>0){
a[i]--;
count--;
cout << "A";
}else if(i==2 && a[i]>0){
a[i]--;
count--;
cout << "T";
}else if(i==3 && a[i]>0){
a[i]--;
count--;
cout << "e";
}else if(i==4 && a[i]>0){
a[i]--;
count--;
cout << "s";
}else if(i==5 && a[i]>0){
a[i]--;
count--;
cout << "t";
}
}
}
return 0;
}
算法标签: 字符串 + 进制
注意: 首先是进制转换，转换成13进制后，再输出字符数组的结果
#include<bits/stdc++.h>
using namespace std;
string D[13] = {
"tret","jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};
string G[13] = {
"","tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};
int isdigit(char c){
if(c>='0' && c<='9'){
return 1;
}else{
return 0;
}
}
int iscase(char c){
if(c>='a' && c<='z'){
return 1;
}else{
return 0;
}
}
int main(){
int N;
cin >> N;
string s;
getline(cin,s);
for(int i=0;i<N;i++){
string str;
getline(cin,str);
int num = 0;
if(isdigit(str[0])){
for(int i=0;i<str.size();i++){
num = num *10 + str[i]-'0';
}
int g = num / 13;
int d = num % 13;
if(g!=0 && d==0){
cout << G[g] << endl;
}else if(g!=0 && d!=0){
cout << G[g] << " ";
cout << D[d] << endl;
}else{
cout << D[d] << endl;
}
}else{
string s1 = "";
string s2 = "";
bool f1 = true;
for(int i=0;i<str.size();i++){
if(iscase(str[i]) && f1){
s1 += str[i];
}else if(str[i] == ' '){
f1 = false;
}else if(iscase(str[i])&& !f1){
s2 += str[i];
}
}
if(s2 == ""){
for(int i=0;i<13;i++){
if(s1 == D[i]){
cout << i << endl;
break;
}
}
for(int i=1;i<13;i++){
if(s1 == G[i]){
cout << i*13 << endl;
break;
}
}
}else{
int g,d;
for(int i=1;i<13;i++){
if(s1 == G[i]){
g = i;
break;
}
}
for(int i=0;i<13;i++){
if(s2 == D[i]){
d = i;
break;
}
}
cout << g*13 + d << endl;
}
}
}
return 0;
}
算法标签: 排序（枢轴选取）
注意: 这道题目考察的知识点为快速排序的子算法——枢轴的选取，一个序列中，能成为枢轴的元素A必定是左边全部小于等于A而右边全部大于等于A的点！因此，直接遍历序列即可，复杂度 O ( n ) O(n) O(n)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int minx[maxn] = {
0};
int maxx[maxn] = {
0};
int a[maxn];
const int maxnum = INT_MAX;
int b[maxn];
int main(){
int N;
cin >> N;
for(int i=1;i<=N;i++){
cin >> a[i];
}
minx[N+1] = maxnum;
maxx[N+1] = maxnum;
for(int i=1;i<=N;i++){
maxx[i] = max(maxx[i-1],a[i]);
}
for(int i=N;i>=1;i--){
minx[i] = min(minx[i+1],a[i]);
}
int cnt = 0;
for(int i=1;i<=N;i++){
if(a[i]>maxx[i-1] && a[i]<minx[i+1]){
b[cnt++] = a[i];
}
}
sort(b,b+cnt);
cout << cnt << endl;
for(int i=0;i<cnt;i++){
if(i==cnt-1){
cout << b[i];
}else{
cout << b[i] << " ";
}
}
cout << endl;
return 0;
}
算法标签: 模拟
注意: 按照题意简单模拟即可
#include<bits/stdc++.h>
using namespace std;
int N;
int main(){
cin >> N;
int count1 = 0,count2 = 0;
for(int i=0;i<N;i++){
int a,b,c,d;
cin >> a >> b >> c >> d;
bool flag1=false,flag2=false;
if(b==(a+c)){
flag1=true;
}
if(d==(a+c)){
flag2=true;
}
if(flag1 && flag2){
continue;
}else if(!flag1 && !flag2){
continue;
}else if(!flag1 && flag2){
count1++;
}else if(flag1 && !flag2){
count2++;
}
}
cout << count1 << " " << count2;
return 0;
}
算法标签: 模拟 + 字符串
注意: 字符串“-”分离，并找出最大值
#include<bits/stdc++.h>
using namespace std;
int N;
const int maxn = 1e3+5;
int a[maxn];
int main(){
cin >> N;
for(int i=0;i<N;i++){
string name;
cin >> name;
int score;
cin >> score;
int site = name.find('-');
int groupnum = 0;
for(int i=0;i<site;i++){
groupnum = groupnum * 10 + name[i]-'0';
}
a[groupnum] += score;
}
int number = 0;
int maxs = -1;
for(int i=0;i<maxn;i++){
if(a[i]>maxs){
maxs = a[i];
number = i;
}
}
cout << number << " " << maxs;
return 0;
}
算法标签: 高精 + 进制
注意: 两个100位数字相加，这里需要用到高精加法（高精模板详见数据结构专题系列-数论），由于JQK的引入，是13进制下的高精加法，注意输出时若数位>9,需转换成JQK
#include<bits/stdc++.h>
using namespace std;
string str1,str2;
int main(){
cin >> str1 >> str2;
int len1 = str1.size();
int len2 = str2.size();
int maxlen = max(len1,len2);
reverse(str1.begin(),str1.end());
reverse(str2.begin(),str2.end());
if(len1<len2){
str1.append(len2-len1,'0');
}else if(len1>len2){
str2.append(len1-len2,'0');
}
//cout << str1 << endl << str2 << endl;
string result="";
for(int i=0;i<maxlen;i++){
if(i%2!=0){
int num = str2[i] - str1[i];
if(num<0){
num += 10;
}
result += (num+'0');
}else{
int num = str1[i] -'0' + str2[i] -'0';
num = num % 13;
if(num == 10){
result += "J";
}else if(num==11){
result += "Q";
}else if(num==12){
result += "K";
}else{
result += (num+'0');
}
}
}
//cout << result << endl;
for(int i=result.size()-1;i>=0;i--){
cout << result[i];
}
return 0;
}
算法标签: 数论
注意: 片段的每个数被加了 i ∗ ( N − i + 1 ) i*(N-i+1) i∗(N−i+1)次，注意强制类型转换！
#include<bits/stdc++.h>
using namespace std;
int main(){
double a;
int N;
scanf("%d",&N);
long long result = 0;
for(int i=1;i<=N;i++){
scanf("%lf",&a);
result = result + ((long long)(1000.0*a))*(i) * (N-i+1);
}
double r = result*1.0/1000.0;
printf("%.2lf",r);
return 0;
}
算法标签: 模拟
注意: 模拟螺旋矩阵的4个边界，判断不越界并且转角
#include<bits/stdc++.h>
using namespace std;
int N;
int m,n;
int b[10005];
int main(){
cin >> N;
for(int i=(ceil)(sqrt(N));i<=N;i++){
if(N%i==0){
m = i;
n = N/i;
break;
}
}
for(int i=0;i<N;i++){
cin >> b[i];
}
sort(b,b+N);
int a[m+1][n+1];
memset(a,0,sizeof(a));
int i = 0;
int j = 0;
while(N){
while(j<n && !a[i][j]){
a[i][j++] = b[--N];
}
j--;
i++;
while(i<m && !a[i][j]){
a[i++][j] = b[--N];
}
i--;
j--;
while(j>=0 && !a[i][j]){
a[i][j--] = b[--N];
}
j++;
i--;
while(i>=0 && !a[i][j]){
a[i--][j] = b[--N];
}
i++;
j++;
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(j!=n-1){
cout << a[i][j] << " ";
}else{
cout << a[i][j];
}
}
cout << endl;
}
return 0;
}
算法标签: 数论
注意: 复数乘法模拟 ( a + b i ) ∗ ( c + d i ) = ( a c − b d ) + ( a d + b c ) i (a+bi)*(c+di)=(ac-bd)+(ad+bc)i (a+bi)∗(c+di)=(ac−bd)+(ad+bc)i
#include<bits/stdc++.h>
using namespace std;
int main(){
double R1,P1,R2,P2;
cin >> R1 >> P1 >> R2 >> P2;
double front = 0.0,behind =0.0;
front = cos(P1)*cos(P2) -sin(P1)*sin(P2);
behind = sin(P1)*cos(P2) + sin(P2)*cos(P1);
front = front * R1 *R2;
behind = behind *R1 *R2;
if(front+0.005>=0 && front<0){
printf("0.00");
}else{
printf("%.2lf",front);
}
if(behind>=0){
cout << "+";
printf("%.2lf",behind);
}else if(behind+0.005>=0 && behind<0){
cout << "+0.00";
}else{
printf("%.2lf",behind);
}
cout << "i" << endl;
return 0;
}
算法标签: 字符串
注意: 按照题目所给的每个表情符号，输出对应的字符序列即可
#include<bits/stdc++.h>
using namespace std;
char a[3][15];
int K;
int p[5];
int check(int h1,int h2,int h3,int h4,int h5){
if(h1<=p[0] && h2<=p[1] &&h3<=p[2] && h4<=p[1] && h5<=p[0]
&& h1>0 && h2>0 && h3>0 && h4>0 && h5>0){
return 1;
}else{
return 0;
}
}
int init(vector<string> &v,string str){
str.clear();
getline(cin,str);
int start,count=0,res=0;
for(int i=0;i<str.size();i++){
if(str[i]=='['){
start = i+1;
count = 0;
}else if(str[i]==']'){
v.push_back(str.substr(start,count));
res++;
}else{
count++;
}
}
return res;
}
int main(){
vector<string> v1,v2,v3;
string str;
int r = init(v1,str);
p[0] = r;
r = init(v2,str);
p[1] = r;
r = init(v3,str);
p[2] = r;
cin >>K;
for(int i=0;i<K;i++){
int h1,h2,h3,h4,h5;
cin >> h1>> h2 >>h3 >> h4 >> h5;
if(check(h1,h2,h3,h4,h5)){
cout << v1[h1-1] << "(" << v2[h2-1] << v3[h3-1] << v2[h4-1] << ")" << v1[h5-1] << endl;
}else{
cout << "Are you kidding me? @\\/@" << endl;
}
}
return 0;
}
算法标签: 模拟
注意: 根据阈值模拟即可
#include<bits/stdc++.h>
using namespace std;
int N,D;
double e;
int p1 = 0;
int p2 = 0;
int main(){
cin.tie(0);
cout.tie(0);
cin >> N >> e >> D;
for(int i=0;i<N;i++){
int K;
cin >>K;
int res = 0;
for(int j=0;j<K;j++){
double n;
cin >> n;
if(n<e){
res++;
}
}
if(K>D && res*2>K){
p2++;
}else if(res*2>K){
p1++;
}
}
double r1 = p1*1.0 / (N*1.0) * 100;
double r2 = p2*1.0 / (N*1.0) * 100;
printf("%.1lf%% %.1lf%%",r1,r2);
return 0;
}
算法标签: 字符串
注意: 这道题的关键在于如何判断输入的信息不是数字，这里分几种情况，含有英文字母的肯定不是数字；含有2个以上的小数点也不是数字，其余是数字的直接累加，求平均值后输出！(用到2个新的函数，sscanf/sprintf)
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin.tie(0);
cout.tie(0);
cin >> N;
int count = 0;
double res = 0.0;
for(int i=0;i<N;i++){
char str1[100];
scanf("%s",str1);
double num = 0.0;
sscanf(str1,"%lf",&num);
char str2[100];
sprintf(str2,"%.2lf",num);
bool flag = false;
for(int j=0;str1[j]!='\0';j++){
if(str1[j]!=str2[j]){
flag = true;
break;
}
}
if(flag || num<-1000 || num>1000){
cout << "ERROR: "<< str1 << " is not a legal number" << endl;
}else{
count ++;
res += num;
}
}
if(count==1){
printf("The average of 1 number is %.2lf\n",res);
}else if(count==0){
cout << "The average of 0 numbers is Undefined" << endl;
}else{
res = res / count;
printf("The average of %d numbers is %.2lf\n",count,res);
}
return 0;
}
算法标签: 排序
#include<bits/stdc++.h>
using namespace std;
typedef struct photo{
string name;
int height;
}photo;
const int maxn = 1e4+5;
photo p[maxn];
int a[maxn];
int N,K;
bool cmp(photo p1,photo p2){
if(p1.height>p2.height){
return true;
}else if(p1.height==p2.height){
if(p1.name<p2.name){
return true;
}else{
return false;
}
}else{
return false;
}
}
int main(){
cin.tie(0);
cout.tie(0);
cin >> N >> K;
int num = (int)(N/K);
for(int i=0;i<N;i++){
cin >> p[i].name >> p[i].height;
}
sort(p,p+N,cmp);
int start = (N - num*K) + num;
for(int i=0;i<start;i++){
if(i%2==1){
int site = (start/2)-((ceil)(i*1.0/2.0));
a[site] = i;
}else{
int site = (start/2)+((ceil)(i*1.0/2.0));
a[site] = i;
}
}
for(int i=0;i<start;i++){
if(i==0){
cout << p[a[i]].name;
}else{
cout << " " << p[a[i]].name;
}
}
cout << endl;
for(int i=1;i<K;i++){
for(int j=0;j<num;j++){
if(j%2==1){
int site = (num/2)-((ceil)(j*1.0/2.0));
a[site] = (i-1)*num + start + j;
}else{
int site = (num/2)+((ceil)(j*1.0/2.0));
a[site] = (i-1)*num + start + j;
}
}
for(int j=0;j<num;j++){
if(j==0){
cout << p[a[j]].name;
}else{
cout << " " << p[a[j]].name;
}
}
cout << endl;
}
return 0;
}
算法标签: 数论
注意: 找规律组合，发现答案一定是 ( N − 1 ) ∗ 11 ∗ D (N-1)*11*D (N−1)∗11∗D
#include<bits/stdc++.h>
using namespace std;
int N;
int a[15];
int result = 0;
int main(){
cin >> N;
for(int i=0;i<N;i++){
cin >> a[i];
}
for(int i=0;i<N;i++){
result += a[i] * 11;
}
result *=(N-1);
cout << result << endl;
return 0;
}
算法标签: 字符串 + 进制
注意: 先遍历字符串，按照大小写字母求出数字之和，然后转换成二进制，统计0/1即可
#include<bits/stdc++.h>
using namespace std;
string str;
int isupper(char c){
if(c>='A' && c<='Z'){
return 1;
}else{
return 0;
}
}
int islower(char c){
if(c>='a' && c<='z'){
return 1;
}else{
return 0;
}
}
int result = 0;
int a[5];
int main(){
getline(cin,str);
for(int i=0;i<str.size();i++){
if(isupper(str[i])){
result += (str[i]-'A'+1);
}else if(islower(str[i])){
result += (str[i]-'a'+1);
}
}
while(result>0){
a[result%2]++;
result /= 2;
}
cout << a[0] << " " << a[1];
return 0;
}
算法标签: 字符串 + 模拟
注意: 先读入正确的选项，然后再读入每个人各自的选项，比较后，按照多选少选给分，最后统计每个人的得分，并排序输出！
#include<bits/stdc++.h>
using namespace std;
int N,M;
const int maxn = 1e3+5;
typedef struct score{
int point;
int choice;
int correct;
int c[10];
int error;
int number;
}score;
score s[maxn];
int islower(char c){
if(c>='a' && c<='e'){
return 1;
}else{
return 0;
}
}
bool cmp(score s1,score s2){
if(s1.error>s2.error){
return true;
}else if(s1.error==s2.error){
if(s1.number<s2.number){
return true;
}else{
return false;
}
}else{
return false;
}
}
int main(){
cin >> N >> M;
for(int i=0;i<M;i++){
cin >> s[i].point >> s[i].choice >> s[i].correct;
s[i].number = i+1;
string x;
for(int j=0;j<s[i].correct;j++){
cin >> x;
s[i].c[x[0]-'a']++;
}
}
string tmp;
getline(cin,tmp);
for(int i=0;i<N;i++){
string str;
int b[5];
int count = -1;
int fenshu = 0;
bool flag = false;
for(int k=0;k<5;k++){
b[k] = 0;
}
getline(cin,str);
for(int j=0;j<str.size();j++){
if(str[j]=='('){
count++;
flag = true;
}else if(str[j]==')'){
for(int k=0;k<5;k++){
if(s[count].c[k]!=b[k]){
flag=false;
break;
}
}
if(flag==false){
s[count].error++;
}else{
fenshu += s[count].point;
}
for(int k=0;k<5;k++){
b[k] = 0;
}
}else if(islower(str[j])){
int p = str[j] -'a';
b[p]++;
}
}
cout << fenshu << endl;
}
sort(s,s+M,cmp);
if(s[0].error==0){
cout << "Too simple" << endl;
}else{
cout << s[0].error;
for(int i=0;i<M;i++){
if(s[i].error==s[0].error){
cout << " " << s[i].number;
}else{
break;
}
}
}
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
int N,K;
const int maxn = 1e4+5;
typedef struct competition{
int ID;
int rank;
bool check;
bool isin;
}competition;
competition c[maxn];
int isprime(int num){
if(num<2){
return 0;
}else{
for(int i=2;i<=sqrt(num);i++){
if(num%i==0){
return 0;
}
}
return 1;
}
}
int main(){
cin >> N;
for(int i=0;i<N;i++){
int id;
cin >> id;
c[id].ID = id;
c[id].rank = i+1;
c[id].check = false;
c[id].isin = true;
}
cin >> K;
for(int i=0;i<K;i++){
int id;
cin >> id;
int g,s,b,q;
g = id % 10;
s = id/10 %10;
b = id/100 %10;
q = id /1000;
cout << q << b << s << g;
if(c[id].isin==true){
if(c[id].check==true){
cout << ": Checked"<< endl;
}else{
if(c[id].rank==1){
cout << ": Mystery Award"<<endl;
c[id].check=true;
}else if(isprime(c[id].rank)){
cout << ": Minion" << endl;
c[id].check=true;
}else{
cout << ": Chocolate" << endl;
c[id].check=true;
}
}
}else{
cout << ": Are you kidding?" << endl;
}
}
return 0;
}
算法标签: 数论 + 排序
注意: 先按照从大到小的顺序排序，然后按序枚举，只要满足 a [ i ] > i a[i]>i a[i]>i，就更新E的值，否则输出答案
#include<bits/stdc++.h>
using namespace std;
int N;
const int maxn = 1e5+5;
int a[maxn];
int E;
bool cmp(int a,int b){
return a>b;
}
int main(){
cin >> N;
cin.tie(0);
cout.tie(0);
for(int i=1;i<=N;i++){
cin >> a[i];
}
sort(a+1,a+N+1,cmp);
for(int i=1;i<=N;i++){
if(a[i]>i){
E = i;
}else{
break;
}
}
cout << E << endl;
return 0;
}
算法标签: 模拟
注意: 模拟打分的过程即可
#include<bits/stdc++.h>
using namespace std;
int N,M;
const int maxn = 1e2+5;
int a[maxn];
int c[maxn];
int main(){
cin >> N >> M;
for(int i=0;i<M;i++){
cin >> a[i];
}
for(int i=0;i<M;i++){
cin >> c[i];
}
for(int i=0;i<N;i++){
int score = 0;
for(int j=0;j<M;j++){
int num;
cin >> num;
if(num==c[j]){
score += a[j];
}
}
cout << score << endl;
}
return 0;
}
算法标签: 数论
注意: 先确定分子的范围，然后按序枚举，求gcd，若gcd为1，表示是最简分数，直接输出
#include<bits/stdc++.h>
using namespace std;
string str1,str2;
int K;
int top1,bottom1,top2,bottom2;
int main(){
cin >> str1 >> str2;
cin >> K;
int site1 = str1.find('/');
int site2 = str2.find('/');
string top = str1.substr(0,site1);
string bottom = str1.substr(site1+1,str1.size()-1-site1);
for(int i=0;i<top.size();i++){
top1 = top1*10 + top[i] -'0';
}
for(int i=0;i<bottom.size();i++){
bottom1 = bottom1 * 10 +bottom[i] -'0';
}
top = str2.substr(0,site2);
bottom = str2.substr(site2+1,str2.size()-1-site2);
for(int i=0;i<top.size();i++){
top2 = top2*10 + top[i] -'0';
}
for(int i=0;i<bottom.size();i++){
bottom2 = bottom2 * 10 +bottom[i] -'0';
}
double f1 = top1* K * 1.0 / (bottom1*1.0);
double f2 = top2 * K * 1.0/ (bottom2*1.0);
int n1 ;
if(f1>=f2){
double tmp;
tmp = f2;
f2 = f1;
f1 = tmp;
}
if((ceil)(f1)==(floor)(f1)){
n1 = (ceil)(f1) + 1;
}else{
n1 = (ceil)(f1);
}
int n2;
if((floor)(f2)==(ceil)(f2)){
n2 = (floor)(f2) -1 ;
}else{
n2 = (floor)(f2);
}
int count = 0;
for(int i=n1;i<=n2;i++){
if(__gcd(i,K)==1){
if(count==0){
cout << i <<"/" << K;
}else{
cout << " " << i << "/" << K;
}
count++;
}
}
return 0;
}
算法标签: 模拟
注意: 计算模长的最大值
#include<bits/stdc++.h>
using namespace std;
int N;
double maxn = 0.0;
int main(){
cin.tie(0);
cout.tie(0);
cin >> N;
for(int i=0;i<N;i++){
int a,b;
cin >> a >> b;
double tmp;
tmp = sqrt(a*a+b*b);
if(tmp>maxn){
maxn = tmp;
}
}
printf("%.2lf\n",maxn);
return 0;
}
算法标签: 哈希
注意: 开一个桶记录数字，遍历一下非0即不同朋友数的个数
#include<bits/stdc++.h>
using namespace std;
int N;
int a[40];
int main(){
cin.tie(0);
cout.tie(0);
cin >> N;
for(int i=0;i<N;i++){
int s;
int result = 0;
cin >> s;
while(s>0){
result += s%10;
s /= 10;
}
a[result] = 1;
}
int count = 0;
for(int i=0;i<40;i++){
if(a[i]){
count++;
}
}
cout << count << endl;
count = 0;
for(int i=0;i<40;i++){
if(a[i]){
if(count==0){
cout << i;
}else{
cout << " " << i;
}
count++;
}
}
return 0;
}
算法标签: 哈希
注意: 统计未成对出现的数字，需注意不在对中的数字肯定“单身”，在对中的数字必须满足一对都出现才可以
#include<bits/stdc++.h>
using namespace std;
int N,M;
const int maxn = 1e5+5;
int a[maxn];
int out[maxn];
int pairs[maxn];
typedef struct man{
int pair1;
int pair2;
bool flag1;
bool flag2;
}man;
man m[maxn];
int main(){
cin.tie(0);
cout.tie(0);
cin >> N;
for(int i=0;i<N;i++){
int p,q;
cin >> p >> q;
a[p] = 1;
a[q] = 1;
m[i+1].pair1 = p;
m[i+1].pair2 = q;
m[i+1].flag1 = false;
m[i+1].flag2 = false;
pairs[p] = i+1;
pairs[q] = i+1;
}
cin >> M;
int count = 0;
for(int i=0;i<M;i++){
int n;
cin >> n;
if(!a[n]){
out[count++] = n;
}else{
int pairnum = pairs[n];
if(n==m[pairnum].pair1){
m[pairnum].flag1 = true;
}else if(n==m[pairnum].pair2){
m[pairnum].flag2 = true;
}
}
}
for(int i=1;i<=N;i++){
if(m[i].flag1 == false && m[i].flag2 == true){
out[count++] = m[i].pair2;
}else if(m[i].flag1 == true && m[i].flag2 == false){
out[count++] = m[i].pair1;
}
}
sort(out,out+count);
cout << count << endl;
for(int i=0;i<count;i++){
int w,q,b,s,g;
w = out[i] / 10000;
q = out[i] / 1000 % 10;
b = out[i] / 100 % 10;
s = out[i] / 10 % 10;
g = out[i] % 10;
if(i==0){
cout << w << q << b << s << g;
}else{
cout << " " << w << q << b << s << g;
}
}
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
int M,N;
const int maxn = 5e2+5;
int a[maxn][maxn];
int lleft,lright,lreplace;
int main(){
cin.tie(0);
cout.tie(0);
cin >> M >> N >> lleft >> lright >> lreplace;
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
cin >> a[i][j];
if(a[i][j]>=lleft && a[i][j]<=lright){
a[i][j] = lreplace;
}
}
}
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
int b,s,g;
b = a[i][j] / 100;
s = a[i][j] /10 % 10;
g = a[i][j] % 10;
if(j==0){
cout << b << s << g ;
}else{
cout << " " << b << s << g;
}
}
cout << endl;
}
return 0;
}
算法标签: 字符串 + 模拟
#include<bits/stdc++.h>
using namespace std;
string str;
int N;
int main(){
cin >> str;
cin >> N;
string input;
getline(cin,input);
while((getline(cin,input)) && input!="#"){
if(input!=str){
cout << "Wrong password: " << input << endl;
}else{
cout << "Welcome in" << endl;
break;
}
N--;
if(N==0){
cout << "Account locked" << endl;
break;
}
}
return 0;
}
算法标签: 模拟
注意: 枚举二维数组中的每个点，观察其是否满足上下左右都在阈值范围内
#include<bits/stdc++.h>
using namespace std;
int a[1005][1005];
int res_x;
int res_y;
map<int,int> mp;
int TOL;
int cnt = 0;
int isvalid(int x,int y){
if(abs(a[x][y]-a[x+1][y])>TOL &&
abs(a[x][y]-a[x-1][y])>TOL &&
abs(a[x][y]-a[x][y+1])>TOL &&
abs(a[x][y]-a[x][y-1])>TOL &&
abs(a[x][y]-a[x+1][y+1])>TOL &&
abs(a[x][y]-a[x+1][y-1])>TOL &&
abs(a[x][y]-a[x-1][y+1])>TOL &&
abs(a[x][y]-a[x-1][y-1])>TOL &&
mp[a[x][y]] == 1){
return 1;
}else{
return 0;
}
}
int main(){
int M,N;
cin >> M >> N;
cin >> TOL;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
cin >> a[i][j];
mp[a[i][j]]++;
}
}
//input
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
if(isvalid(i,j)){
res_x = i;
res_y = j;
cnt++;
}
}
}
if(cnt>1){
cout << "Not Unique" << endl;
}else if(cnt == 0){
cout << "Not Exist" << endl;
}else{
cout << "(" << res_y << ", " << res_x << "): " << a[res_x][res_y]<< endl;
}
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
int M,N,S;
const int maxn = 1e3+5;
string award[maxn];
int main(){
cin >> M >> N >> S;
string str;
int count = 1;
int num = 0;
for(int i=0;i<M;i++){
cin >> str;
if((count-S)%N==0 && count>=S){
bool flag = false;
for(int i=0;i<num;i++){
if(award[i]==str){
flag = true;
break;
}
}
if(flag==true){
continue;
}else if(flag==false){
cout << str << endl;
award[num++] = str;
count++;
}
}else{
count++;
}
}
if(num==0){
cout << "Keep going..." << endl;
}
return 0;
}
算法标签: 排序 + 贪心
注意: 不难证明，绳子长度越大的需要越向后处理，这样在整根绳子的贡献比中最大，因此先排序，然后从小到大，模拟绳子打结的过程，输出答案
#include<bits/stdc++.h>
using namespace std;
int N;
const int maxn = 1e5+5;
int a[maxn];
int main(){
cin.tie(0);
cout.tie(0);
cin >> N;
for(int i=0;i<N;i++){
cin >> a[i];
}
sort(a,a+N);
double res = (a[0]+a[1])*1.0/2.0;
for(int i=2;i<N;i++){
res = (res +a[i])/2.0;
}
int result = (floor)(res);
cout << result << endl;
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
int T,K;
int main(){
cin.tie(0);
cout.tie(0);
cin >> T >> K;
for(int i=0;i<K;i++){
int n1,n2,t,b;
cin >> n1 >> b >> t >> n2;
if(t>T){
cout << "Not enough tokens. Total = " << T << "." << endl;
continue;
}else if(n1>n2 && b==0){
T += t;
cout << "Win " << t << "! Total = " << T << "." <<endl;
}else if(n1>n2 && b==1){
T-=t;
cout << "Lose " << t <<". Total = " << T << "." << endl;
}else if(n1<n2 && b==0){
T-=t;
cout << "Lose " << t <<". Total = " << T << "." << endl;
}else if(n1<n2 && b==1){
T += t;
cout << "Win " << t << "! Total = " << T << "." <<endl;
}
if(T==0){
cout << "Game Over." << endl;
return 0;
}
}
return 0;
}
算法标签: 字符串
注意: 输入需要匹配的字符串，然后依次读入每个人的信息，若出现了相同的字符串，那么统计结果，并输出该人的物品信息
#include<bits/stdc++.h>
using namespace std;
int M,N;
int a[10];
int b[15];
int c[15];
int result = 0;
int people = 0;
int main(){
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i=0;i<M;i++){
cin >> a[i];
}
for(int i=0;i<N;i++){
int count = 0;
string name;
cin >> name;
int K;
cin >> K;
for(int j=0;j<15;j++){
b[j] = 0;
}
for(int j=0;j<K;j++){
cin >> b[j];
}
for(int k=0;k<15;k++){
c[k] = 0;
}
for(int j=0;j<K;j++){
for(int k=0;k<M;k++){
if(b[j]==a[k]){
c[count++] = b[j];
break;
}
}
}
if(count>0){
cout << name << ": ";
for(int i=0;i<count;i++){
int q,b,s,g;
q = c[i] / 1000;
b = c[i] / 100 %10;
s = c[i] / 10 % 10;
g = c[i] % 10;
if(i==0){
cout << q << b << s << g;
}else{
cout << " " << q << b << s << g;
}
}
cout << endl;
result += count;
people ++;
}
}
cout << people << " " << result << endl;
return 0;
}
算法标签: 字符串
注意: 本题可参考P1058，解法类似
#include<bits/stdc++.h>
using namespace std;
int score[105];
int number[105];
int rightnum[105];
int rightanswer[105][15];
int wronganswer[105][15];
double score_s[1005];
int main(){
int N,M;
cin >> N >> M;
//N个人，M个问题
for(int i=1;i<=M;i++){
cin >> score[i] >> number[i]; //score—具体得分;number—具体选项数
cin >> rightnum[i]; //正确选项数
for(int j=1;j<=rightnum[i];j++){
string s;
cin >> s;
rightanswer[i][s[0]-'a'+1] = 1;
}
}
//读入基本信息
string tt;
getline(cin,tt);
//缓冲
for(int i=1;i<=N;i++){
//N个人
for(int k=1;k<=M;k++){
//k个问题
string s;
cin >> s;
int t = 0;
for(int j=1;j<s.size();j++){
t = t*10 + s[j] -'0';
}
int ans[15];
memset(ans,0,sizeof(ans));
for(int j=1;j<=t;j++){
cin >> s;
ans[s[0]-'a'+1] = 1;
}
int ans_s[15];
for(int j=1;j<=number[k];j++){
ans_s[j] = ans[j] ^ rightanswer[k][j];
}
bool flag1 = true;
bool flag2 = true;
for(int j=1;j<=number[k];j++){
if(ans_s[j]){
//题目选错了，可能漏选、错选
flag1 = false;
wronganswer[k][j]++;
if(rightanswer[k][j]!=1){
//错选了
flag2 = false;
}
}
}
if(flag1 && flag2){
//选对了
score_s[i] += score[k];
}else if(!flag1 && flag2){
//漏选了
score_s[i] += 0.5*score[k];
}
}
}
for(int i=1;i<=N;i++){
printf("%.1lf\n",score_s[i]);
}
int maxn = -1;
for(int i=1;i<=M;i++){
for(int j=1;j<=number[i];j++){
if(wronganswer[i][j]>maxn){
maxn = max(maxn,wronganswer[i][j]);
}
}
}
if(maxn == 0){
cout << "Too simple" << endl;
return 0;
}
for(int i=1;i<=M;i++){
for(int j=1;j<=number[i];j++){
if(wronganswer[i][j] == maxn){
printf("%d %d-%c\n",wronganswer[i][j],i,(char)(j-1+'a'));
}
}
}
return 0;
}
算法标签: 进制
#include<bits/stdc++.h>
using namespace std;
int main(){
string s,s1,s2;
cin >> s >> s1 >> s2;
while(s1[0] == '0'){
s1 = s1.substr(1);
}
while(s2[0] == '0'){
s2 = s2.substr(1);
}
if(s1 == "" && s2 != ""){
cout << s2 << endl;
}else if(s1 != "" && s2 == ""){
cout << s1 << endl;
}else if(s1 == "" && s2 == ""){
cout << "0" << endl;
}else{
reverse(s.begin(),s.end());
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
string ans = "";
int len1 = s1.size();
int len2 = s2.size();
if(len1<len2){
for(int i=0;i<len2-len1;i++){
s1 += "0";
}
}else if(len2<len1){
for(int i=0;i<len1-len2;i++){
s2 += "0";
}
}
int jw = 0;
for(int i=0;i<max(len1,len2);i++){
int x = jw + s1[i] -'0' + s2[i] -'0';
int Oct = s[i] -'0';
if(Oct == 0){
Oct = 10;
}
jw = x / Oct;
x = x % Oct;
ans += (char)(x+'0');
}
if(jw){
ans += (char)(jw+'0');
}
reverse(ans.begin(),ans.end());
cout << ans << endl;
}
return 0;
}
算法标签: 链表 + 模拟
#include<bits/stdc++.h>
using namespace std;
map<int,int>mp1;
map<int,int> mp2;
struct node{
int s1;
int val;
};
node n[100005];
int main(){
int N,K;
int start;
cin >> start >> N >> K;
for(int i=0;i<N;i++){
int pos,next;
int v;
cin >> pos >> v >>next;
mp1[pos] = next;
mp2[pos] = v;
}
int cnt = 0;
int start1 = start;
while(start1!=-1){
if(mp2[start1]<0){
n[cnt].s1 = start1;
n[cnt++].val = mp2[start1];
}
start1 = mp1[start1];
}
start1 = start;
while(start1!=-1){
if(mp2[start1]>=0 && mp2[start1]<=K){
n[cnt].s1 = start1;
n[cnt++].val = mp2[start1];
}
start1 = mp1[start1];
}
start1 = start;
while(start1!=-1){
if(mp2[start1]>K){
n[cnt].s1 = start1;
n[cnt++].val = mp2[start1];
}
start1 = mp1[start1];
}
for(int i=0;i<cnt;i++){
if(i==cnt-1){
printf("%05d %d %d\n",n[i].s1,n[i].val,-1);
}else{
printf("%05d %d %05d\n",n[i].s1,n[i].val,n[i+1].s1);
}
}
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
int N;
int main(){
cin >> N;
string tmp;
getline(cin,tmp);
for(int i=0;i<N;i++){
string str;
getline(cin,str);
char c;
for(int j=0;j<str.size();j++){
if(str[j]=='T'){
c = str[j-2];
break;
}
}
if(c=='A'){
cout << 1;
}else if(c=='B'){
cout << 2;
}else if(c=='C'){
cout << 3;
}else if(c=='D'){
cout << 4;
}
}
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
int N,M;
const int maxn = 1e2+5;
int a[maxn];
int c[maxn];
int check(int num){
if(num>=0 && num<=M){
return 1;
}else{
return 0;
}
}
int main(){
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cin >> a[j];
}
int count = 0;
double group = 0.0;
for(int j=1;j<N;j++){
if(check(a[j])){
c[count++] = a[j];
}
}
sort(c,c+count);
for(int j=1;j<count-1;j++){
group += c[j];
}
group = group *1.0 / (count-2) * 1.0;
group = (group + a[0]) / 2.0;
int result = (round)(group);
cout << result << endl;
}
return 0;
}
算法标签: 字符串
注意: 顺序遍历字符串，统计相邻的字符个数，并输出结果
#include<bits/stdc++.h>
using namespace std;
int main(){
string s1;
string s2;
getline(cin,s1);
getline(cin,s2);
if(s1=="C"){
char c = '\0';
int cnt = 0;
for(int i=0;i<s2.size();i++){
if(c!=s2[i]){
if(cnt){
if(cnt==1){
cout << c;
}else{
cout << cnt << c;
}
}
cnt = 1;
c = s2[i];
}else{
cnt++;
}
}
if(cnt==1){
cout << c;
}else{
cout << cnt << c;
}
}else{
int sum = 0;
for(int i=0;i<s2.size();i++){
if(isdigit(s2[i])){
sum = sum*10 + s2[i] -'0';
}else{
for(int j=0;j<max(1,sum);j++){
cout << s2[i];
}
sum = 0;
}
}
}
return 0;
}
算法标签: 高精 + 数论
注意: 首先两个数相加可能超过18位，因此需使用高精加法，判断一个数是否是回文数 a [ i ] = = a [ l e n − i ] a[i]==a[len-i] a[i]==a[len−i]
#include<bits/stdc++.h>
using namespace std;
int a[1050];
int b[1050];
int c[1050];
bool isright(int c[],int len){
bool flag = true;
for(int i=0;i<len/2;i++){
if(c[i] == c[len-i-1]){
continue;
}else{
flag = false;
break;
}
}
return flag;
}
int main(){
string s;
cin >> s;
int len = s.size();
for(int i=0;i<len;i++){
a[len-i-1] = s[i] -'0';
b[i] = s[i] -'0';
}
if(isright(a,len)){
for(int i=len-1;i>=0;i--){
cout << a[i];
}
cout << " is a palindromic number.";
return 0;
}
int lena = len,lenb = len;
for(int j=0;j<10;j++){
memset(c,0,sizeof(c));
int jw = 0;
for(int i=0;i<len;i++){
c[i] = jw + a[i] + b[i];
jw = c[i] / 10;
c[i] = c[i] % 10;
}
if(jw){
c[len] = jw;
len++;
}
//print
for(int i=lena-1;i>=0;i--){
cout << a[i];
}
cout << " + ";
for(int i=lenb-1;i>=0;i--){
cout << b[i];
}
cout << " = ";
for(int i=len-1;i>=0;i--){
cout << c[i];
}
cout << endl;
//
bool f = isright(c,len);
if(f){
for(int i=len-1;i>=0;i--){
cout << c[i];
}
cout << " is a palindromic number.";
return 0;
}else{
for(int i=0;i<len;i++){
a[i] = c[i];
b[i] = c[len-1-i];
}
lena = len;
lenb = len;
}
}
cout << "Not found in 10 iterations.";
return 0;
}
算法标签: 模拟 + 排序
#include<bits/stdc++.h>
using namespace std;
typedef struct student{
string s;
int score1;
int score2;
int score3;
int score4;
}stu;
vector<stu> v;
bool cmp(stu s1,stu s2){
if(s1.score4!=s2.score4){
return s1.score4>s2.score4;
}else{
return s1.s < s2.s;
}
}
map<string,int> A;
map<string,int> B;
map<string,int> C;
int main(){
int P,M,N;
cin >> P >> M >> N;
for(int i=0;i<P;i++){
string s;
int score;
cin >> s >> score;
A[s] = score;
B[s] = -1;
C[s] = -1;
}
for(int i=0;i<M;i++){
string s;
int score;
cin >> s >> score;
B[s] = score;
}
for(int i=0;i<N;i++){
string s;
int score;
cin >> s >> score;
C[s] = score;
}
for(auto it = A.begin();it!=A.end();it++){
stu student;
student.s = it->first;
student.score1 = it->second;
student.score2 = B[it->first];
student.score3 = C[it->first];
double f;
if(student.score2!=-1 && student.score3!=-1){
f = student.score2 * 0.4 + student.score3 * 0.6;
}else if(student.score2!=-1){
f = student.score2 * 0.4;
}else if(student.score3!=-1){
f = student.score3;
}else{
f = 0;
}
int f0 = (round)(f);
if(student.score3>f0){
student.score4 = student.score3;
}else{
student.score4 = f0;
}
v.push_back(student);
}
sort(v.begin(),v.end(),cmp);
for(int i=0;i<v.size();i++){
if(v[i].score1>=200 && v[i].score4>=60){
cout << v[i].s << " " << v[i].score1 << " " << v[i].score2 << " " << v[i].score3
<< " " << round(v[i].score4) << endl;
}
}
return 0;
}
算法标签: 字符串
#include<bits/stdc++.h>
using namespace std;
int N;
int isdigit(char c){
if(c>='0' && c<='9'){
return 1;
}else{
return 0;
}
}
int isalpha(char c){
if((c>='a' && c<='z')||(c>='A' && c<='Z')){
return 1;
}else{
return 0;
}
}
int ispoint(char c){
if(c == '.'){
return 1;
}else{
return 0;
}
}
int main(){
cin >> N;
string tmp;
getline(cin,tmp);
for(int i=0;i<N;i++){
string str;
getline(cin,str);
if(str.size()<6){
cout << "Your password is tai duan le." << endl;
}else{
bool flag1=false,flag2=false;
bool flag = true;
for(int i=0;i<str.size();i++){
if(isdigit(str[i]) || isalpha(str[i]) || ispoint(str[i])){
if(isdigit(str[i])){
flag1 = true;
}else if(isalpha(str[i])){
flag2 = true;
}
}else{
cout << "Your password is tai luan le." <<endl;
flag = false;
break;
}
}
if(flag && flag1 && !flag2){
cout << "Your password needs zi mu." <<endl;
}else if(flag && !flag1 && flag2){
cout << "Your password needs shu zi." << endl;
}else if(flag && flag1 && flag2){
cout << "Your password is wan mei." << endl;
}
}
}
return 0;
}
算法标签: 计算几何
注意: 计算平面两点之间距离的公式为 ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 \sqrt {(x_1-x_2)^2+(y_1-y_2)^2} (x1−x2)2+(y1−y2)2
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+5;
typedef struct shoot{
string num;
int x;
int y;
double distance;
}shoot;
shoot s[maxn];
int N;
bool cmp(shoot s1,shoot s2){
if(s1.distance<s2.distance){
return true;
}else{
return false;
}
}
int main(){
cin.tie(0);
cout.tie(0);
cin >> N;
for(int i=0;i<N;i++){
cin >> s[i].num >> s[i].x >> s[i].y;
s[i].distance = sqrt(s[i].x*s[i].x*1.0+s[i].y*s[i].y*1.0);
}
sort(s,s+N,cmp);
cout << s[0].num << " " << s[N-1].num << endl;
return 0;
}
算法标签: 哈希
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+5;
int a[maxn];
int main(){
int N;
cin.tie(0);
cout.tie(0);
cin >> N;
for(int i=1;i<=N;i++){
int n;
cin >> n;
a[abs(i-n)]++;
}
for(int i=maxn-1;i>=0;i--){
if(a[i]>1){
cout << i <<" " << a[i] << endl;
}
}
return 0;
}
算法标签: 数论
注意: 找规律
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2+5;
string str[maxn];
int main(){
int d,N;
cin >> d >> N;
str[0] += (d+'0');
for(int i=1;i<N;i++){
char start = str[i-1][0];
int count = 0;
for(int j=0;j<str[i-1].size();j++){
if(str[i-1][j]==start){
count++;
}else{
str[i] += start;
str[i] += (count+'0');
count = 1;
start = str[i-1][j];
}
}
str[i] += start;
str[i] += (count+'0');
}
cout << str[N-1] << endl;
return 0;
}
算法标签: 模拟 + 排序
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
struct node{
string name;
int res;
int num;
};
unordered_map<string,double> Tscore;
unordered_map<string,int> Man;
bool cmp(node n1,node n2){
if(n1.res!=n2.res){
return n1.res>n2.res;
}else if(n1.num!=n2.num){
return n1.num<n2.num;
}else{
return n1.name < n2.name;
}
}
int main(){
int N;
cin.tie(0);
cout.tie(0);
cin >> N;
for(int i=0;i<N;i++){
string number;
cin >> number;
int score;
cin >> score;
double r;
string sname;
cin >> sname;
for(int j=0;j<sname.size();j++){
sname[j] = tolower(sname[j]);
}
if(number[0]=='B'){
r = score*1.0/1.5;
}else if(number[0]=='A'){
r = score *1.0;
}else if(number[0]=='T'){
r = score *1.5;
}
Tscore[sname] += r;
Man[sname] ++;
}
vector<node> ans;
int ch = 0;
for(auto it =Tscore.begin();it!=Tscore.end();it++){
ans.push_back(node{
it->first,(int)(it->second),Man[it->first]});
}
sort(ans.begin(),ans.end(),cmp);
int rank = 1;
double snum=0.0;
cout << ans.size() << endl;
for(int i=0;i<ans.size();i++){
if(snum!=ans[i].res){
snum = ans[i].res;
rank = i+1;
}
cout << rank << " " << ans[i].name << " " << ans[i].res << " " << ans[i].num << endl;
}
return 0;
}
算法标签: 数论
#include<bits/stdc++.h>
using namespace std;
int a,b;
int main(){
cin >> a >> b;
int result = a*b;
bool flag = false;
while(result>0){
int r = result % 10;
if(flag==false && r==0){
}else{
flag = true;
cout << r ;
}
result /= 10;
}
if(flag==false){
cout << 0 ;
}
return 0;
}
算法标签: 哈希
#include<bits/stdc++.h>
using namespace std;
int N;
const int maxn = 2e4+5;
int a[maxn];
int main(){
cin >> N;
for(int i=1;i<=N;i++){
int result;
result = (floor)(i/2) +(floor)(i/3) +(floor)(i/5);
a[result] = 1;
}
int count = 0;
for(int i=0;i<maxn;i++){
if(a[i]==1){
count++;
}
}
cout << count << endl;
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
int M,X,Y;
int main(){
cin >> M >> X >> Y;
bool flag = false;
int a,b;
double c;
for(int i=99;i>=10;i--){
int jia = i;
int yi = jia/10 + (jia%10)*10;
double bing = abs(jia-yi)*1.0 / (X*1.0);
if(fabs(bing * Y-yi)<1e-3){
flag = true;
a = jia;
b = yi;
c = bing;
break;
}
}
if(flag == false){
cout << "No Solution" << endl;
}else{
cout << a;
if(a>M){
cout << " " << "Cong" ;
}else if(a==M){
cout << " " << "Ping" ;
}else if(a<M){
cout << " " << "Gai";
}
if(b>M){
cout << " " << "Cong" ;
}else if(b==M){
cout << " " << "Ping" ;
}else if(b<M){
cout << " " << "Gai";
}
if(c>M){
cout << " " << "Cong" ;
}else if(c==M){
cout << " " << "Ping" ;
}else if(c<M){
cout << " " << "Gai";
}
cout << endl;
}
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2+5;
int a[maxn];
int c[maxn];
int main(){
int N;
cin >> N;
for(int i=1;i<=N;i++){
cin >> a[i];
}
for(int i=1;i<=N-1;i++){
for(int j=i+1;j<=N;j++){
for(int k=1;k<=N;k++){
if(k==i || k==j){
c[k] = -1;
}else{
c[k] = 1;
}
}
vector<int> l;
for(int k=1;k<=N;k++){
if(a[k]<0 && abs(a[k])!=i && abs(a[k])!=j){
l.push_back(k);
}else if(a[k]>0 && (a[k]==i || a[k]==j)){
l.push_back(k);
}
}
if(l.size()==2 && (c[l[0]]+c[l[1]]==0)){
cout << i << " " << j << endl;
return 0;
}
}
}
cout << "No Solution" << endl;
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int a[maxn];
int c[maxn];
unordered_map<int,vector<int>> good;
int main(){
int N,M;
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++){
int g1,g2;
cin >> g1 >> g2;
good[g1].push_back(g2);
good[g2].push_back(g1);
}
for(int i=0;i<M;i++){
int K;
cin >> K;
memset(a,0,sizeof(a));
bool flag = false;
for(int j=0;j<K;j++){
cin >> c[j];
a[c[j]] = 1;
}
for(int j=0;j<K;j++){
for(int k=0;k<good[c[j]].size();k++){
if(!a[good[c[j]][k]]){
continue;
}else{
flag = true;
break;
}
}
if(flag){
break;
}
}
if(flag){
cout << "No" << endl;
}else{
cout << "Yes" << endl;
}
}
return 0;
}
算法标签: 模拟（循环枚举）
#include<bits/stdc++.h>
using namespace std;
int N;
int main(){
cin >> N;
for(int i=0;i<N;i++){
string str;
cin >> str;
int len = str.size();
int M = 1;
for(int j=0;j<len;j++){
M*=10;
}
int res = 0;
for(int j=0;j<len;j++){
res = res *10 + str[j]-'0';
}
int p;
bool flag = false;
for(int j=1;j<10;j++){
p = j*res*res;
int r = p % M;
if(r == res){
flag = true;
cout << j << " " << p << endl;
break;
}
}
if(flag==false){
cout << "No" << endl;
}
}
return 0;
}
算法标签: 排序
#include<bits/stdc++.h>
using namespace std;
int N,M;
const int maxn = 1e3+5;
const int maxm = 1e2+5;
int a[maxm][maxn];
int b[2*maxn];
typedef struct moon{
int number;
int sale;
}moon;
moon m[maxn];
bool cmp(moon m1,moon m2){
if(m1.sale>m2.sale){
return true;
}else{
return false;
}
}
int main(){
cin >> N >> M;
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
cin >> a[i][j];
}
}
for(int i=0;i<N;i++){
m[i].number = i+1;
m[i].sale = 0;
for(int j=0;j<M;j++){
m[i].sale += a[j][i];
}
}
sort(m,m+N,cmp);
int maxs = m[0].sale;
cout << maxs << endl;
vector<int> s;
for(int i=0;i<N;i++){
if(m[i].sale == maxs){
s.push_back(m[i].number);
}
}
sort(s.begin(),s.end());
for(int i=0;i<s.size();i++){
if(i==0){
cout << s[i];
}else{
cout << " " << s[i];
}
}
return 0;
}
算法标签: 哈希（字符串）
#include<bits/stdc++.h>
using namespace std;
string str1,str2;
int a[200];
int check(char c){
int d = c;
if(d>=32 && d<=126){
if(!a[d]){
a[d] = 1;
return 1;
}else{
return 0;
}
}else{
return 0;
}
}
int main(){
getline(cin,str1);
getline(cin,str2);
for(int i=0;i<str1.size();i++){
if(check(str1[i])){
cout << str1[i];
}
}
for(int i=0;i<str2.size();i++){
if(check(str2[i])){
cout << str2[i];
}
}
return 0;
}
算法标签: 字符串 + 模拟
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
int a[maxn];
int L,K;
int isprime(long long a){
for(long long i =2;i<=sqrt(a);i++){
if(a%i==0){
return 0;
}
}
return 1;
}
int main(){
string str;
cin >> L >> K;
cin >> str;
for(int i=0;i<L;i++){
a[i] = str[i] - '0';
}
bool flag = false;
for(int i=0;i<L-K+1;i++){
long long num = 0;
for(int j=0;j<K;j++){
num = num *10+a[i+j];
}
if(isprime(num)){
for(int j=0;j<K;j++){
cout << a[i+j];
}
flag = true;
break;
}
}
if(flag==false){
cout << "404" << endl;
}
return 0;
}
算法标签: 字符串 + 排序
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
struct node {
string t;
int value;
};
bool cmp(const node &a, const node &b) {
return a.value != b.value ? a.value > b.value : a.t < b.t;
}
int main() {
int n, k, num;
string s;
cin >> n >> k;
vector<node> v(n);
for (int i = 0; i < n; i++)
cin >> v[i].t >> v[i].value;
for (int i = 1; i <= k; i++) {
cin >> num >> s;
printf("Case %d: %d %s\n", i, num, s.c_str());
vector<node> ans;
int cnt = 0, sum = 0;
if (num == 1) {
for (int j = 0; j < n; j++)
if (v[j].t[0] == s[0]) ans.push_back(v[j]);
} else if (num == 2) {
for (int j = 0; j < n; j++) {
if (v[j].t.substr(1, 3) == s) {
cnt++;
sum += v[j].value;
}
}
if (cnt != 0) printf("%d %d\n", cnt, sum);
} else if (num == 3) {
unordered_map<string, int> m;
for (int j = 0; j < n; j++)
if (v[j].t.substr(4, 6) == s) m[v[j].t.substr(1, 3)]++;
for (auto it : m) ans.push_back({
it.first, it.second});
}
sort(ans.begin(), ans.end(),cmp);
for (int j = 0; j < ans.size(); j++) printf("%s %d\n", ans[j].t.c_str(), ans[j].value);
if (((num == 1 || num == 3) && ans.size() == 0) || (num == 2 && cnt == 0)) printf("NA\n");
}
return 0;
}
算法标签: 数论
#include<bits/stdc++.h>
using namespace std;
int N;
int cnt = 0;
int b[10005];
int main(){
int K;
scanf("%d",&K);
for(int i=0;i<K;i++){
memset(b,0,sizeof(b));
cnt = 0;
scanf("%d",&N);
for(int j=1;j<=N;j++){
if(N%j==0){
b[cnt++] = j;
}
}
bool f = false;
for(int j=0;j<cnt;j++){
for(int k=j+1;k<cnt;k++){
for(int p=k+1;p<cnt;p++){
for(int q=p+1;q<cnt;q++){
if((b[j]+b[k]+b[p]+b[q])%N==0){
f = true;
break;
}
}
if(f){
break;
}
}
if(f){
break;
}
}
if(f){
break;
}
}
if(f){
printf("Yes\n");
}else{
printf("No\n");
}
}
return 0;
}
算法标签: 模拟
#include<bits/stdc++.h>
using namespace std;
int a[105][105];
int b[105][105];
int ans[105];
int main(){
int n,k,x;
scanf("%d%d%d",&n,&k,&x);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
}
}
int cnt;
if(n%2==0){
cnt = n/2;
}else{
cnt = n/2+1;
}
for(int i=1;i<=cnt;i++){
for(int j=1;j<=n;j++){
b[i*2][j] = a[i*2][j];
}
int index = (i-1) % k + 1;
for(int j=1;j<=n-index;j++){
b[2*i-1][j+index] = a[2*i-1][j];
}
for(int j=1;j<=index;j++){
b[2*i-1][j] = x;
}
}
for(int j=1;j<=n;j++){
for(int i=1;i<=n;i++){
ans[j] += b[i][j];
}
}
for(int j=1;j<=n;j++){
if(j==1){
printf("%d",ans[j]);
}else{
printf(" %d",ans[j]);
}
}
printf("\n");
return 0;
}
算法标签: 排序
注意: 求前缀最小高度和前缀最大高度，两者差值的最小正数即为岩洞的高度
#include<bits/stdc++.h>
using namespace std;
int minn = 1005;
int maxn = -1;
int main(){
int N;
scanf("%d",&N);
for(int i=0;i<N;i++){
int t;
scanf("%d",&t);
minn = min(minn,t);
}
for(int i=0;i<N;i++){
int t;
scanf("%d",&t);
maxn = max(maxn,t);
}
if(minn>maxn){
printf("Yes %d",minn-maxn);
}else{
printf("No %d",maxn-minn+1);
}
printf("\n");
return 0;
}
算法标签: 素数
注意: 注意枚举p+6和p-6，有两个枚举方向
#include<bits/stdc++.h>
using namespace std;
int isprime(int N){
if(N==1 || N==0){
return 0;
}
for(int i=2;i<=sqrt(N);i++){
if(N%i==0){
return 0;
}
}
return 1;
}
int main(){
int N;
cin >> N;
if(isprime(N)){
if(N-6>1 && isprime(N-6)){
printf("Yes\n");
printf("%d\n",N-6);
}else if(isprime(N+6)){
printf("Yes\n");
printf("%d\n",N+6);
}else{
printf("No\n");
N++;
while(1){
if(isprime(N)){
if(N-6>1 && isprime(N-6)){
printf("%d\n",N);
return 0;
}else if(isprime(N+6)){
printf("%d\n",N);
return 0;
}
}
N++;
}
}
}else{
printf("No\n");
N++;
while(1){
if(isprime(N)){
if(N-6>1 && isprime(N-6)){
printf("%d\n",N);
return 0;
}else if(isprime(N+6)){
printf("%d\n",N);
return 0;
}
}
N++;
}
}
return 0;
}
算法标签: 排序
注意: 用map存储信息，代码相对简洁一些，此外也可采用哈希表解决此问题
#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
int isold(int y,int m,int d,int yy,int mm,int dd){
if(y!=yy){
return y<yy;
}else if(m!=mm){
return m<mm;
}else{
return d<dd;
}
}
int main(){
int N,M;
scanf("%d",&N);
for(int i=0;i<N;i++){
char s[25];
scanf("%s",s);
mp[s]++;
}
scanf("%d",&M);
for(int i=0;i<M;i++){
char s[25];
scanf("%s",s);
mp[s]--;
}
int cnt = 0;
for(auto it=mp.begin();it!=mp.end();it++){
if(it->second == 0){
cnt++;
}
}
printf("%d\n",cnt);
int y = 9999;
int m = 99;
int d = 99;
string res;
if(cnt==0){
for(auto it=mp.begin();it!=mp.end();it++){
string s = it->first.substr(6,8);
int l = s.size();
int cal = 0;
for(int i=0;i<l;i++){
cal = cal*10 + s[i]-'0';
}
int yy = cal/10000;
int mm = cal/100%100;
int dd = cal%100;
int f = isold(yy,mm,dd,y,m,d);
if(f){
res = it->first;
y = yy;
m = mm;
d = dd;
}
}
}else{
for(auto it=mp.begin();it!=mp.end();it++){
if(it->second==0){
string s = it->first.substr(6,8);
int l = s.size();
int cal = 0;
for(int i=0;i<l;i++){
cal = cal*10 + s[i]-'0';
}
int yy = cal/10000;
int mm = cal/100%100;
int dd = cal%100;
int f = isold(yy,mm,dd,y,m,d);
if(f){
res = it->first;
y = yy;
m = mm;
d = dd;
}
}
}
}
printf("%s\n",res.c_str());
return 0;
}
文章浏览阅读451次。dev/mem: 物理内存的全镜像。可以用来访问物理内存。/dev/kmem: kernel看到的虚拟内存的全镜像。可以用来访问kernel的内容。调试嵌入式Linux内核时，可能需要查看某个内核变量的值。/dev/kmem正好提供了访问内核虚拟内存的途径。现在的内核大都默认禁用了/dev/kmem，打开的方法是在 make menuconfig中选中 device drivers --> ..._dev/mem 源码实现
文章浏览阅读7.1k次，点赞2次，收藏19次。vxe-table，一个小众但功能齐全并支持excel操作的vue表格组件_vxe-table
文章浏览阅读62次。参考：http://www.ruanyifeng.com/blog/2016/01/babel.htmlBabelBabel是一个广泛使用的转码器，可以将ES6代码转为ES5代码，从而在现有环境执行// 转码前input.map(item => item + 1);// 转码后input.map(function (item) { return item..._让开发环境支持bable
文章浏览阅读2.8k次，点赞6次，收藏29次。摘要：FPGA视频处理FIFO的典型应用，视频输入FIFO的作用，视频输出FIFO的作用，视频数据跨时钟域FIFO，视频缩放FIFO的作用_fpga 频分复用 视频
文章浏览阅读575次。【代码】R语言：设置工作路径为当前文件存储路径。_r语言设置工作目录到目标文件夹
文章浏览阅读452次。格式：background: linear-gradient(direction, color-stop1, color-stop2, ...);<linear-gradient> = linear-gradient([ [ <angle> | to <side-or-corner>] ,]? &l..._background线性渐变
文章浏览阅读1k次，点赞26次，收藏8次。第十三届蓝桥杯青少年组python编程省赛真题一、题目要求（注：input（）输入函数的括号中不允许添加任何信息）1、编程实现给定一个正整数N，输出正整数N中各数位最大的那个数字。例如:N=132，则输出3。2、输入输出输入描述：只有一行，输入一个正整数N输出描述：只有一行，输出正整数N中各数位最大的那个数字输入样例：
文章浏览阅读2.2k次。一个网络协议主要由以下三个要素组成：1.语法数据与控制信息的结构或格式，包括数据的组织方式、编码方式、信号电平的表示方式等。2.语义即需要发出何种控制信息，完成何种动作，以及做出何种应答，以实现数据交换的协调和差错处理。3.时序即事件实现顺序的详细说明，以实现速率匹配和排序。不完整理解：语法表示长什么样，语义表示能干什么，时序表示排序。转载于:https://blog.51cto.com/98..._网络协议三要素csdn
文章浏览阅读153次。主要的思想，将所有的系统都可以看作两部分，真正的数据log系统和各种各样的query engine所有的一致性由log系统来保证，其他各种query engine不需要考虑一致性，安全性，只需要不停的从log系统来同步数据，如果数据丢失或crash可以从log系统replay来恢复可以看出kafka系统在linkedin中的重要地位，不光是d..._the log: what every software engineer should know about real-time data's uni
文章浏览阅读746次。伟大是熬出来的 目录 前言 引言 时间熬成伟大：领导者要像狼一样坚忍 第一章 内圣外王——领导者的心态修炼 1. 天纵英才的自信心 2. 上天揽月的企图心 3. 誓不回头的决心 4. 宠辱不惊的平常心 5. 换位思考的同理心 6. 激情四射的热心 第二章 日清日高——领导者的高效能修炼 7. 积极主动，想到做到 8. 合理掌控自己的时间和生命 9. 制定目标，马..._当狼拖着受伤的右腿逃生时,右腿会成为前进的阻碍,它会毫不犹豫撕咬断自己的腿, 以
文章浏览阅读285次。在当今的大数据时代，人们对高速度和高带宽的需求越来越大，迫切希望有一种新型产品来作为高性能计算和数据中心的主要传输媒质，所以有源光缆（AOC）在这种环境下诞生了。有源光缆究竟是什么呢？应用在哪些领域，有什么优势呢？易天将为您解答！有源光缆（Active Optical Cables，简称AOC）是两端装有光收发器件的光纤线缆，主要构成部件分为光路和电路两部分。作为一种高性能计..._aoc 光缆
文章浏览阅读2.2k次。在“桌面”上按快捷键“Ctrl+R”，调出“运行”窗口。接着，在“打开”后的输入框中输入“Gpedit.msc”。并按“确定”按钮。如下图 找到“用户配置”下的“Windows设置”下的“Internet Explorer 维护”的“连接”，双击选择“自动浏览器配置”。如下图 选择“自动启动配置”，并在下面的“自动代理URL”中填写相应的PAC文件地址。如下..._設置proxy腳本