admin 管理员组

文章数量: 887021

【PTA】

目录

• 知识框架
• No.1 L1题目：
• • • (!!!!!)**L1-002 打印沙漏 (20 分)**
    • **L1-003 个位数统计 (15 分)**
    • **L1-005 考试座位号 (15 分)**
    • (!!!!!)**L1-006 连续因子 (20 分)**
    • **L1-008 求整数段和 (10 分)**
    • (!!!!!)**L1-009 N个数求和 (20 分)**
    • **L1-011 A-B (20 分)**
    • **L1-015 跟奥巴马一起画方块 (15 分)**
    • **L1-016 查验身份证 (15 分)**
    • **L1-017 到底有多二 (15 分)**
    • **L1-018 大笨钟 (10 分)**
    • **L1-019 谁先倒 (15 分)**
    • **L1-020 帅到没朋友 (20 分)**
    • **L1-023 输出GPLT (20 分)**
    • **L1-025 正整数A+B (15 分)**
    • **L1-027 出租 (20 分)**
    • **L1-030 一帮一 (15 分)**
    • **L1-032 Left-pad (20 分)**
    • (!!!!!)**L1-033 出生年 (15 分)**
    • **L1-034 点赞 (20 分)**
    • **L1-035 情人节 (15 分)**
    • L1-039 古风排版 (20 分)**
    • **L1-042 日期格式化 (5 分)**
    • (!!!!!)**L1-043 阅览室 (20 分)**
    • **L1-044 稳赢 (15 分)**
    • （今）**L1-046 整除光棍 (20 分)**
    • **L1-048 矩阵A乘以B (15 分)**
    • (!!!!!)**L1-049 天梯赛座位分配 (20 分)**
    • (!!!!!)**L1-050 倒数第N个字符串 (15 分)**
    • **L1-054 福到了 (15 分)**
    • **L1-056 猜数字 (20 分)**
    • **L1-058 6翻了 (15 分)**
    • **L1-059 敲笨钟 (20 分)**
    • **L1-062 幸运彩票 (15 分)**
    • (!!!!!)**L1-064 估值一亿的AI核心代码 (20 分)**
    • **L1-069 胎压监测 (15 分)**
    • **L1-070 吃火锅 (15 分)**
    • **L1-071 前世档案 (20 分)**
    • **L1-072 刮刮彩票 (20 分)**
    • **L1-077 大笨钟的心情 (15 分)**
    • **L1-078 吉老师的回归 (15 分)**
    • **L1-079 天梯赛的善良 (20 分)**
    • **L1-080 乘法口诀数列 (20 分)**
• No.2 L2题目
• • • **L2-001 紧急救援 (25 分)**
    • **L2-002 链表去重 (25 分)**
    • **L2-003 月饼 (25 分)**
    • （三）**L2-004 这是二叉搜索树吗？ (25 分)**
    • **L2-005 集合相似度 (25 分)**
    • （三）**L2-006 树的遍历 (25 分)**
    • **L2-007 家庭房产 (25 分)**
    • **L2-008 最长对称子串 (25 分)**
    • **L2-009 抢红包 (25 分)**
    • **L2-010 排座位 (25 分)**
    • （四）**L2-011 玩转二叉树 (25 分)**
    • （四）**L2-012 关于堆的判断 (25 分)**
    • **L2-013 红色警报 (25 分)**
    • **L2-014 列车调度 (25 分)**
    • **L2-015 互评成绩 (25 分)**
    • **L2-016 愿天下有情人都是失散多年的兄妹 (25 分)**
    • **L2-017 人以群分 (25 分)**
    • （五）**L2-018 多项式A除以B (25 分)**
    • **L2-019 悄悄关注 (25 分)**
    • **L2-020 功夫传人 (25 分)**
    • **L2-021 点赞狂魔 (25 分)**
    • **L2-022 重排链表 (25 分)**
    • **L2-023 图着色问题 (25 分)**
    • **L2-024 部落 (25 分)**
    • **L2-025 分而治之 (25 分)**
    • **L2-026 小字辈 (25 分)**
    • **L2-027 名人堂与代金券 (25 分)**
    • **L2-028 秀恩爱分得快 (25 分)**
    • **L2-029 特立独行的幸福 (25 分)**
    • （五）**L2-030 冰岛人 (25 分)**
    • **L2-031 深入虎穴 (25 分)**
    • **L2-032 彩虹瓶 (25 分)**
    • **L2-033 简单计算器 (25 分)**
    • **L2-034 口罩发放 (25 分)**
    • **L2-035 完全二叉树的层序遍历 (25 分)**
    • **L2-036 网红点打卡攻略 (25 分)**
    • **L2-037 包装机 (25 分)**
    • **L2-038 病毒溯源 (25 分)**
    • **L2-039 清点代码库 (25 分)**
    • **L2-040 哲哲打游戏 (25 分)**
• No.3 PTA总结进行所属分类：
• • 初始模板：
  • 小知识：
  • 输入格式规范：
  • 输出格式规范
  • 普通题模板：
  • • **L1-003 个位数统计 (15 分)**
    • **L1-011 A-B (20 分)**
    • **L1-015 跟奥巴马一起画方块 (15 分)**
    • **L1-020 帅到没朋友 (20 分)**
    • **L1-034 点赞 (20 分)**
    • **L1-062 幸运彩票 (15 分)**
    • **L1-069 胎压监测 (15 分)**
    • **L1-077 大笨钟的心情 (15 分)**
    • **L1-079 天梯赛的善良 (20 分)**
    • **L2-005 集合相似度 (25 分)**
    • **L2-014 列车调度 (25 分)**
    • **L2-017 人以群分 (25 分)**
    • **L2-040 哲哲打游戏 (25 分)**
  • 字符矩阵模拟模板：
  • • **L1-002 打印沙漏 (20 分)**
    • **L1-039 古风排版 (20 分)**
    • **L1-048 矩阵A乘以B (15 分)**
    • **L1-049 天梯赛座位分配 (20 分)**
    • **L1-054 福到了 (15 分)**
    • **L1-072 刮刮彩票 (20 分)**
    • **L2-028 秀恩爱分得快 (25 分)**
  • 字符串捉个搜索模拟模板：
  • • **L1-016 查验身份证 (15 分)**
    • **L1-017 到底有多二 (15 分)**
    • **L1-025 正整数A+B (15 分)**
    • **L1-027 出租 (20 分)**
    • **L1-032 Left-pad (20 分)**
    • **L1-058 6翻了 (15 分)**
    • **L1-059 敲笨钟 (20 分)**
    • **L1-064 估值一亿的AI核心代码 (20 分)**
    • **L2-008 最长对称子串 (25 分)**
  • 辗转除法相除转换模拟模板：
  • • **L1-006 连续因子 (20 分)**
    • **L1-009 N个数求和 (20 分)**
    • **L1-033 出生年 (15 分)**
    • **L1-046 整除光棍 (20 分)**
    • **L1-050 倒数第N个字符串 (15 分)**
    • **L1-080 乘法口诀数列 (20 分)**
    • **L2-018 多项式A除以B (25 分)**
    • **L2-029 特立独行的幸福 (25 分)**
  • 记录次数数据循环模拟模板：
  • • **L1-019 谁先倒 (15 分)**
    • **L1-023 输出GPLT (20 分)**
    • **L1-035 情人节 (15 分)**
    • **L1-044 稳赢 (15 分)**
    • **L1-070 吃火锅 (15 分)**
    • **L1-078 吉老师的回归 (15 分)**
  • 结构体设计固定时间间隔模拟模板：
  • • **L1-043 阅览室 (20 分)**
  • 结构体查询模板：
  • • **L1-005 考试座位号 (15 分)**
    • **L1-030 一帮一 (15 分)**
    • **L1-056 猜数字 (20 分)**
    • **L2-019 悄悄关注 (25 分)**
  • 结构体简单到复杂的排序模板：
  • • **L2-003 月饼 (25 分)**
    • **L2-007 家庭房产 (25 分)**
    • **L2-009 抢红包 (25 分)**
    • **L2-015 互评成绩 (25 分)**
    • **L2-021 点赞狂魔 (25 分)**
    • **L2-027 名人堂与代金券 (25 分)**
  • map<vector< int >,int>mp;模板
  • • **L2-039 清点代码库 (25 分)**
  • map<string,int>mp;模板
  • • L2-030 冰岛人 (25 分)
    • **L2-034 口罩发放 (25 分)**
  • V[N]版本BFS搜索统计层数模板：
  • • **L2-026 小字辈 (25 分)**
    • **L2-031 深入虎穴 (25 分)**
    • **L3-008 喊山 (30 分)**
  • V[N]版本DFS搜索统计连通分量个数模板：
  • • **L2-013 红色警报 (25 分)**
    • **L2-025 分而治之 (25 分)**
  • V[N]版本DFS搜索根据条件判断正否模板：
  • • **L2-016 愿天下有情人都是失散多年的兄妹 (25 分)**
    • **L2-023 图着色问题 (25 分)**
  • V[N]版本DFS搜索储存路径模板：
  • • **L2-020 功夫传人 (25 分)**
    • **L2-038 病毒溯源 (25 分)**
    • **L3-025 那就别担心了 (30 分)**
  • 二叉树模拟模板：
  • • 普通+完全：模板
    • **L1-071 前世档案 (20 分)**
    • L2-006 树的遍历 (25 分)
    • L2-011 玩转二叉树 (25 分)
    • **L2-035 完全二叉树的层序遍历 (25 分)**
  • 二叉搜索树的相关模拟：
  • • 普通+完全：模板
    • L2-004 这是二叉搜索树吗？ (25 分)
    • **L3-010 是否完全二叉搜索树 (30 分)**
    • **L3-016 二叉搜索树的结构 (30 分)**
  • 顶堆的模拟模板：
  • • L2-012 关于堆的判断 (25 分)
  • 栈与队列模板：
  • • **L2-037 包装机 (25 分)**
    • **L2-032 彩虹瓶 (25 分)**
    • **L2-033 简单计算器 (25 分)**
    • **L3-002 特殊堆栈 (30 分)**
  • 简单并查集：
  • • **L2-010 排座位 (25 分)**
    • **L2-024 部落 (25 分)**
    • **L3-003 社交集群 (30 分)**
  • 链表模拟模板：
  • • **L2-002 链表去重 (25 分)**
    • **L2-022 重排链表 (25 分)**
  • 经典DP问题模块模板：
  • • 背包问题模板：
    • **L3-001 凑零钱 (30 分)**
    • **L3-2 拼题A打卡奖励 (30 分)**
    • **L3-020 至多删三个字符 (30 分)**
  • MP[ N ][N】版本Dijs最短路径模板：
  • • 第一类：给出路径让判断是否可行：
    • • **L2-036 网红点打卡攻略 (25 分)**
    • 第二类：完全体求各种东西的dijs
    • • **L2-001 紧急救援 (25 分)**
      • **L3-005 垃圾箱分布 (30 分)**
      • **L3-007 天梯地图 (30 分)**
      • L3-011 直捣黄龙 (30 分)
  • Edge版本dijs最短路径模板：
  • 几何凸包问题模板：
  • • 不会：能得分就行，满分要求奇思妙想！！
    • **L3-029 还原文件 (30 分)**
• No.4 睿抗
• • 初赛：
  • • 7-1 懂的都懂 (20 分)【简单 / 暴力 + [哈希](=哈希&spm=1001.2101.3001.7020)表】
    • 7-4 疫情防控 (30 分)【难度: 难 / 并查集 思维】
  • 复赛：
  • • **7-1 冒险者分队**
  • 2022初赛
  • R5**树与二分图**
  • **RC-u3 跑团机器人**

知识框架

No.1 L1题目：

(!!!)L1-002 打印沙漏 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
vector<int>v[N];int main() {cin>>n>>ch;//h 为上面的行数==下面的行数。//累加规律：1行有1个，2行有4个，3行有9个。即几行和为几平方。//该行规律：1行有1个，2行有3个，3行有5个。2*i-1；int h=sqrt((n+1)/2);for(int i=h;i>=1;i--){for(int j=1;j<=h-i;j++)cout<<" ";for(int j=1;j<=2*i-1;j++)cout<<ch;cout<<endl;}for(int i=2;i<=h;i++){for(int j=1;j<=h-i;j++)cout<<" ";for(int j=1;j<=2*i-1;j++)cout<<ch;cout<<endl;}cout<<n-(2*h*h-1)<<endl;return 0;
}

L1-003 个位数统计 (15 分)

//int num=str[i]-'0' 的好处。
#include<bits/stdc++.h>
using namespace std;
int book[11]={0};
int main(){string str;cin>>str;for(int i=0;i<str.size();i++){int num=str[i]-'0';book[num]++;}for(int i=0;i<=9;i++){if(book[i]>0){cout<<i<<":"<<book[i]<<endl;}}
return 0;
}

L1-005 考试座位号 (15 分)

//结构体更方便点，然后再循环
//由 16 位数字组成要用到long 
#include<bits/stdc++.h>
using namespace std;
struct node{long a;int b;int c;
}stu[1000];
int main(){int n,m,k;int x,y,z;cin>>n;for(int i=0;i<n;i++){cin>>stu[i].a>>stu[i].b>>stu[i].c;}cin>>k;while(k--){cin>>x;for(int i=0;i<n;i++){if(stu[i].b==x){cout<<stu[i].a<<" "<<stu[i].c<<endl;}}}
return 0;
}

(!!!)L1-006 连续因子 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
vector<int>v[N];int main() {cin>>n;int start=0;int maxx=0;int count=0;//只是找其中部分因子是连续的for(int i=2;i<=sqrt(n);i++){//这里只有count在这循环为0count=0;int cur=n;int j=i;while(cur%j==0){cur=cur/j;j++;count++;}if(count>maxx){maxx=count;start=i;}}if(maxx==0){cout<<"1"<<endl<<n<<endl;}else{cout<<maxx<<endl;for(int i=0;i<maxx;i++){if(i==0){cout<<start+i;}else{cout<<"*"<<start+i;}}}return 0;
}

L1-008 求整数段和 (10 分)

//记住怎么进行填充的
#include <iostream>
#include <iomanip>
using namespace std;int main()
{int a,b,cou=0;cin>>a>>b;long sum=0;for(int i=a;i<=b;i++){cout<<setfill(' ')<<setiosflags(ios::right)<<setw(5);cout<<i;sum=sum+i;cou++;if(cou%5==0){cout<<endl;}}if(cou%5!=0)cout<<endl;cout<<"Sum = "<<sum<<endl;return 0;
}

(!!!)L1-009 N个数求和 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
vector<int>v[N];
int gcd(int x, int y){if(y==0){return x;}return gcd(y,x%y);
}
int main() {cin>>n;//这个听巧妙地cin>>x>>ch>>y;int fenzi = x, fenmu = y;for (int i = 1; i< n; i++){cin>>x>>ch>>y;fenzi=fenzi*y+x*fenmu;fenmu=fenmu*y;int maxyue=gcd(fenzi,fenmu);fenzi=fenzi/maxyue;fenmu=fenmu/maxyue;}if(fenzi%fenmu==0){cout<<fenzi/fenmu<<endl;}else if(fenzi<fenmu){cout<<fenzi<<"/"<<fenmu<<endl;}else{cout<<fenzi/fenmu<<" "<<fenzi%fenmu<<"/"<<fenmu<<endl;}return 0;
}

L1-011 A-B (20 分)

#include<bits/stdc++.h>
using namespace std;int main(){int n,m,k;int x,y,z;string a,b;getline(cin,a);getline(cin,b);int flag;for(int i=0;i<a.size();i++){flag=0;for(int j=0;j<b.size();j++){if(a[i]==b[j]){flag=1;break;}}if(flag==0){cout<<a[i];}}
return 0;
}

L1-015 跟奥巴马一起画方块 (15 分)

#include<bits/stdc++.h>
using namespace std;
int main(){int n,m,k;int x,y,z;char ch;cin>>n>>ch;int hang;if(n%2==0){hang=n/2;}else{hang=n/2+1;}for(int i=1;i<=hang;i++){for(int j=1;j<=n;j++){cout<<ch;}cout<<endl;}
return 0;
}

L1-016 查验身份证 (15 分)

 注意权重和duiying 都要自己打上去
#include<bits/stdc++.h>
using namespace std;
int quan[17]={7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
char z[11]={'1' ,'0','X' ,'9' ,'8' ,'7' ,'6' ,'5', '4' ,'3', '2'};
int main(){int n,m,k;cin>>n;string s;int sum;int flag;int flagz=0;while(n--){flag=0;sum=0;cin>>s;for(int i=0;i<s.size()-1;i++){if((s[i]-'0')<=9 && (s[i]-'0')>=0){sum=sum+(s[i]-'0')*quan[i];}else{flag=1;break;}}int mod=sum%11;if(z[mod]!=s[17] || flag==1){flagz=1;cout<<s<<endl;}}if(flagz==0){cout<<"All passed"<<endl;}
return 0;
}

L1-017 到底有多二 (15 分)

//记得增加一倍是*2 ， 增加0.5倍是*1.5
#include<bits/stdc++.h>
using namespace std;int main(){int n,m,k;string s;cin>>s;float bei=1.0;float weishu=s.size();float geshu=0.0;if(s[0]=='-'){bei=bei*1.5;weishu=weishu-1;}if((s[s.size()-1]-'0')%2==0){bei=bei*2;}for(int i=0;i<s.size();i++){if(s[i]=='2'){geshu++;}}float num=(geshu/weishu)*bei*100;printf("%.2f" ,num);cout<<"%"<<endl;return 0;
}

L1-018 大笨钟 (10 分)

#include<iostream>using namespace std;
int main()
{    int h=0,m=0;char temp=':';    cin>>h>>temp>>m;    int count=h-12;    if(m>0)    {        count+=1;    }    if(count<=0)    {        printf("Only %02d:%02d.  Too early to Dang.",h,m);    }    else    {        for(int i=0;i<count;i++)        {            cout<<"Dang";        }     } 
} 

L1-019 谁先倒 (15 分)

 注意通赢的时候都不喝
//注意第二个输出的是已经喝了多少了
#include<bits/stdc++.h>
using namespace std;int main(){int n,m,k;int amax,bmax,a=0,b=0;int ahua,ahan,bhua,bhan;cin>>amax>>bmax;cin>>n;while(n--){cin>>ahan>>ahua>>bhan>>bhua;if(ahua==ahan+bhan){a++;}if(bhua==ahan+bhan){b++;}if(ahua==ahan+bhan && bhua==ahan+bhan){a--;b--;}if(amax-a<0){cout<<"A"<<endl;cout<<b<<endl;break;}if(bmax-b<0){cout<<"B"<<endl;cout<<a<<endl;break;}}return 0;
}

L1-020 帅到没朋友 (20 分)

 注意补齐0
#include<bits/stdc++.h>
using namespace std;
int book[100000]={0};
int main(){int n,m,k;int x,y,z;cin>>n;for(int i=0;i<n;i++){cin>>k;if(k==1){cin>>x;continue;}while(k--){cin>>x;book[x]++;}}int flag=0;vector<int>ans;cin>>m;int book2[100000]={0};for(int i=0;i<m;i++){cin>>x;if(book[x]==0 && book2[x]==0){book2[x]++;ans.push_back(x);flag=1;}}if(flag==0){cout<<"No one is handsome"<<endl;}else{for( int i=0;i<ans.size();i++){if(i==0){printf("%05d",ans[i]);}else{cout<<" ";printf("%05d" ,ans[i]);}}}return 0;
}

L1-023 输出GPLT (20 分)

#include<bits/stdc++.h>
using namespace std;
int main(){int n,m,k;int gcou=0,pcou=0,lcou=0,tcou=0;string s;cin>>s;for(int i=0;i<s.size();i++){if(s[i]=='G' || s[i]=='g'){gcou++;}else if(s[i]=='p' || s[i]=='P'){pcou++;}else if(s[i]=='l' || s[i]=='L'){lcou++;}else if(s[i]=='t' || s[i]=='T'){tcou++;}}while( gcou>0 || pcou>0 || lcou>0 || tcou>0){if(gcou>0){cout<<"G";gcou--;}if(pcou>0){cout<<"P";pcou--;}if(lcou>0){cout<<"L";lcou--;}if(tcou>0){cout<<"T";tcou--;}}
return 0;
}

L1-025 正整数A+B (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
vector<int>v[N];
int flag=0;
int check(string str){for(int i=0;i<str.size();i++){if(str[i]<'0' || str[i]>'9'){return 1;}}if(stoi(str)<1 || stoi(str)>1000){return 1;}return 0;
}int main() {string s1,s2;cin>>s1;ch=getchar();getline(cin,s2);int flag1=check(s1);int flag2=check(s2);if(flag1==0 && flag2==0){cout<<s1<<" + "<<s2<<" = "<<stoi(s1)+stoi(s2)<<endl;}else if(flag1==1 && flag2==1){cout<<"? + ? = ?"<<endl;}else if(flag1==1 && flag2==0){cout<<"? + "<<s2<<" = ?"<<endl;}else{cout<<s1<<" + ? = ?"<<endl;}return 0;
}

L1-027 出租 (20 分)

#include<bits/stdc++.h>
using namespace std;
bool cmp(int x, int y){return x>y;
}
int main(){int n,m,k;string s;cin>>s;vector<int> ans;int book[15]={0};for(int i=0;i<s.size();i++){int num=s[i]-'0';if(book[num]==0){ans.push_back(num);book[num]++;}}sort(ans.begin() , ans.end() ,cmp);cout<<"int[] arr = new int[]{";for(int i=0;i<ans.size();i++){if(i==0){cout<<ans[i];}else{cout<<","<<ans[i];}}cout<<"};"<<endl;cout<<"int[] index = new int[]{";for(int i=0;i<s.size();i++){int num=s[i]-'0';for(int j=0;j<ans.size();j++){if(ans[j]==num){if(i==0){cout<<j;}else{cout<<","<<j;}}}}cout<<"};"<<endl;return 0;
}

L1-030 一帮一 (15 分)

#include<bits/stdc++.h>
using namespace std;
struct node{string name;int sex;int flag=0;
}stu[1001];
int main(){int n,m,k;cin>>n;for(int i=0;i<n;i++){cin>>stu[i].sex>>stu[i].name;}for(int i=0;i<n/2;i++){if(stu[i].flag==1){continue;}cout<<stu[i].name<<" ";for(int j=n-1; j>=0;j--){if(stu[j].sex!=stu[i].sex && stu[j].flag==0){cout<<stu[j].name<<endl;stu[j].flag=1;break;}}}return 0;
}

L1-032 Left-pad (20 分)

#include<bits/stdc++.h>
using namespace std;int main(){int n,m,k;cin>>n;char ch;cin>>ch;getchar();string s;getline(cin,s);if(s.size()==n){cout<<s<<endl;}else if(s.size()>n){for(int i=n; i>0;i--){cout<<s[s.size()-i];}}else if(s.size() < n){for(int i=1;i<=n-s.size();i++){cout<<ch;}cout<<s<<endl;}return 0;
}

(!!!)L1-033 出生年 (15 分)

#include<bits/stdc++.h>
using namespace std;
int geshu(int x){int book[12]={0};int n1=x/1000;int n2=(x-n1*1000)/100;int n3=(x-n1*1000-n2*100)/10;int n4=x-n1*1000-n2*100-n3*10;book[n1]=book[n2]=book[n3]=book[n4]=1;int cnt=0;for(int i=0;i<12;i++){if(book[i]>0){cnt++;}}return cnt;}
int main(){int n,m,k;int a,b;cin>>a>>b;for(int i=0;i<=3000;i++){if(geshu(a+i)==b){cout<<i<<" ";printf("%04d",a+i);break;}}return 0;
}

L1-034 点赞 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
vector<int>v[N];
int book[N]={0};
int main() {cin>>n;while(n--){cin>>k;while(k--){cin>>x;book[x]++;}}int maxx=0;for(int i=0;i<1001;i++){maxx=max(maxx,book[i]);}for(int i=1001;i>=0;i--){if(book[i]==maxx){cout<<i<<" "<<book[i]<<endl;break;}}return 0;
}

L1-035 情人节 (15 分)

#include<bits/stdc++.h>
using namespace std;
int main(){int n,m,k;int x,y,z;string name;string stu[100];int i;for( i=1; ; i++){cin>>name;if(name=="."){i=i-1;break;}stu[i]=name;}if(i<2){cout<<"Momo... No one is for you ..."<<endl;}else if( i<14){cout<<stu[2]<<" is the only one for you..."<<endl;}else{cout<<stu[2]<<" and "<<stu[14]<<" are inviting you to dinner..."<<endl;}return 0;
}

L1-039 古风排版 (20 分)**

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1007
int n,m,k,g,d;
int x,y,z;
char ch;
vector<int>v[N];int main() {cin>>n;getchar();string str;getline(cin,str);int length=str.size();int lie;if(length%n==0){lie=length/n;}else{lie=length/n+1;}int a=0;char c[N][N];for(int i=lie;i>=1;i--){for(int j=1;j<=n;j++){//因为a比需要的大一//str[0]开始的，所以【a】最大为length-1；即当【】内最大时，a++之后 a==lengthif(a<length){c[j][i]=str[a++];}else{c[j][i]=' ';}}}for(int i=1;i<=n;i++){for(int j=1;j<=lie;j++){cout<<c[i][j];}cout<<endl;}return 0;
}

L1-042 日期格式化 (5 分)

#include <bits/stdc++.h>using namespace std;int main()
{string mei;cin>>mei;string nian,yue,ri;nian=mei.substr(6,4);yue=mei.substr(0,2);ri=mei.substr(3,2);cout<<nian<<'-'<<yue<<'-'<<ri<<endl;return 0;
}

(!!!)L1-043 阅览室 (20 分)

//由于线路偶尔会有故障，可能出现不完整的纪录，即只有S没有E，或者只有E没有S的纪录，系统应能自动忽略这种无效纪录。另外，题目保证书号是书的唯一标识，同一本书在任何时间区间内只可能被一位读者借阅。#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
vector<int>v[N];
struct node{bool vis;//是否被借int time;//借阅时间
}book[N];int main(){cin>>n;char s;while(n--){for(int i=0;i<N;i++)book[i].vis=0,book[i].time=0;int id,cnt=0,time=0;while(cin>>id>>s>>x>>ch>>y &&id!=0){int t=60*x+y;if(s=='S'){//if(!book[id].vis)//连续两次出现可能是中间一个E未记录到，所以直接替换初始时间，就因为这个细节第二个样例过不了//只要出现S，就直接换上去。book[id].vis=1,book[id].time=t;}else{if(book[id].vis==1){cnt++;time+=t-book[id].time;book[id].vis=0;}}}if(cnt==0){cout<<cnt<<" "<<cnt<<endl;}else{//cnt=0时直接输出，不能相除，double自动进位cout<<cnt<<" "<<(int)(time*1.0/cnt*1.0+0.5)<<endl;;}}return 0;
}

L1-044 稳赢 (15 分)

//cnt表是第几局局势，#include<bits/stdc++.h>
using namespace std;
int main(){int n,m,k;int x,y,z;cin>>n;string s;int cnt=1;for(int i=0; ; i++){cin>>s;if(s=="End"){break;}//因为这个是平局不算赢的局数；n赢+1平算是一个循环if(cnt%(n+1)==0){cout<<s<<endl;}else{if(s=="ChuiZi"){cout<<"Bu"<<endl;}else if(s=="Bu"){cout<<"JianDao"<<endl;}else if(s=="JianDao"){cout<<"ChuiZi"<<endl;}}cnt++;}return 0;
}

（今）L1-046 整除光棍 (20 分)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9MkRWOG8-1679672875234)(C:\Users\86177\AppData\Roaming\Typora\typora-user-images\image-20220316125946215.png)]

#include<bits/stdc++.h>
using namespace std;int main()
{int n,ans=0,cnt=0;cin>>n;while(ans<n){ans=ans*10+1;cnt++; }//跳出循环后导致 ans>=n;即可以进行除法了while(1){cout<<ans/n;ans=ans%n;if(ans==0){break;}//下面这个是进行时ans=ans*10+1;cnt++;}cout<<" "<<cnt;return 0;
} 

L1-048 矩阵A乘以B (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];int main() {int ah,al,bh,bl;cin>>ah>>al;int a[ah+1][al+1];for(int i=1;i<=ah;i++){for(int j=1;j<=al;j++){cin>>a[i][j];}}cin>>bh>>bl;int b[bh+1][bl+1];for(int i=1;i<=bh;i++){for(int j=1;j<=bl;j++){cin>>b[i][j];}}if(al!=bh){cout<<"Error: "<<al<<" != "<<bh<<endl;}else{int c[ah+1][bl+1];for(int i=1;i<=ah;i++){for(int j=1;j<=bl;j++){int sum=0;for(int k=1;k<=al;k++){sum=sum+a[i][k]*b[k][j];}c[i][j]=sum;}}cout<<ah<<" "<<bl<<endl;for(int i=1;i<=ah;i++){for(int j=1;j<=bl;j++){if(j==1){cout<<c[i][j];}else{cout<<" "<<c[i][j];}}cout<<endl;}}return 0;
}

(!!!)L1-049 天梯赛座位分配 (20 分)

//记住N为大于100的但是不能太大
//记住那个 j<=num[i]
#include<bits/stdc++.h>
using namespace std;
int num[111];//记录每个学校的队伍数量
int pos[111][11][11];//i学校j队伍中k队员的位置
int maxx,pre;//maxx记录学校中队伍数量的最大值，pre记录上一个被编号的学校
int x;//记录编号
int main()
{int n;//学校数量cin>>n;for(int i=1; i<=n; i++){cin>>num[i];//每个学校的队伍数量maxx=max(maxx,num[i]);//记录最大队伍数量}for(int j=1; j<=maxx; j++) //以最大队伍数量为上界，为了让每个人都能在这个循环里添加上位置{for(int k=1; k<=10; k++)//循环每个队员{for(int i=1; i<=n; i++)//遍历学校开始编号{if(j<=num[i])//如果当前的队伍数量j小于等于当前学校的队伍数量，说明可以编号，否则不可以，因为该学校里没有队员可以被编号了，都编完号了{if(pre==i)//相邻学校的两个队员必须隔位就坐x+=2;elsex++;//不是同一个学校的，连续编排pos[i][j][k]=x;//特别有意思的循环，i学校j队伍中k队员的编号就是xpre=i;//记录上一个被编号的学校}}}}for(int i=1;i<=n;i++){cout<<"#"<<i<<endl;for(int j=1;j<=num[i];j++){for(int k=1;k<=10;k++){if(k<=9)cout<<pos[i][j][k]<<" ";elsecout<<pos[i][j][k]<<endl;}}}return 0;}

(!!!)L1-050 倒数第N个字符串 (15 分)

//26的L次方就是当取L时，L个字母组成的所有的个数，然后减去N，得到的数，就是我们要输出的数对应的十进制的位置，接着再转换为26进制，就变成我们想要的字符串了
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {int l;cin>>l>>n;int cur=pow(26,l)-n;vector<int>ans;while(l--){//转换L次，就可以从10进制转换为16进制，其他进制也是这个德行 ans.push_back(cur%26);//这里的转换都是倒着存放的 cur=cur/26;}//接着倒序输出，就是正回来了for(int i=ans.size()-1;i>=0;i--){cout<<(char)('a'+ans[i]);}return 0;
}

L1-054 福到了 (15 分)

//这道题主要考察吃回车。。。
//在使用c=getchar()的时候要特别注意。。。
#include <bits/stdc++.h>
using namespace std;
vector<int> ans;
int main() {char ch;int n;char c;cin>>ch>>n;getchar();char aa[n+1][n+1];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){c=getchar();aa[i][j]=c;}getchar();}int flag=0;char bb[n+1][n+1];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){bb[i][j]=aa[n+1-i][n+1-j];if(aa[i][j]!=bb[i][j]){flag=1;}}}if(flag==0){cout<<"bu yong dao le"<<endl;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(bb[i][j]=='@'){cout<<ch;}else{cout<<bb[i][j];}}cout<<endl;}return 0;
}

L1-056 猜数字 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];
struct node{string name;int num;
}stu[N];
int main() {cin>>n;//平均数的一半。double sum=0.0;for(int i=0;i<n;i++){cin>>stu[i].name>>stu[i].num;sum+=stu[i].num;}double avesum=sum/n/2;int minn=inf;string name;for(int i=0;i<n;i++){if(abs(avesum-stu[i].num)<minn){minn=abs(avesum-stu[i].num);name=stu[i].name;}}cout<<(int)avesum<<" "<<name;return 0;
}

L1-058 6翻了 (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];int main() {string str;getline(cin,str);int count=0;//需要注意的是，使用getline函数输入会以换行为结束，所以在循环时 i <= str.length()for(int i=0;i<=str.size();i++){if(str[i]=='6'){count++;continue;}else{//走到这里count表示已经累积了多少个6if(count!=0){if(count>9){cout<<"27";}else if(count>3){cout<<"9";}else{while(count--){cout<<"6";}}//记得恢复原状count=0;}cout<<str[i];}}return 0;
}

L1-059 敲笨钟 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];int main() {cin>>n;getchar(); //这个一定要吃回车while(n--){int flag1=0;int flag2=0;string str;getline(cin,str);vector<int>ans;for(int i=0;i<str.size();i++){if(str[i]==' '){ans.push_back(i);}if(str[i]==',' &&str[i-1]=='g'&&str[i-2]=='n'&&str[i-3]=='o'){flag1=1;}if(str[i]=='.' &&str[i-1]=='g'&&str[i-2]=='n'&&str[i-3]=='o'){flag2=1;}}if(flag1==1&&flag2==1){m=ans[ans.size()-3];for(int j=0;j<=m;j++){cout<<str[j];}cout<<"qiao ben zhong."<<endl;}else{cout<<"Skipped"<<endl;}}return 0;
}

L1-062 幸运彩票 (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];int main() {cin>>n;while(n--){string str;cin>>str;int n1=str[0]-'0';int n2=str[1]-'0';int n3=str[2]-'0';int n4=str[3]-'0';int n5=str[4]-'0';int n6=str[5]-'0';if(n1+n2+n3-n4-n5-n6==0){cout<<"You are lucky!"<<endl;}else{cout<<"Wish you good luck."<<endl;}}return 0;
}

(!!!)L1-064 估值一亿的AI核心代码 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int pan1(string s,int x){if(s[x]>='a'&&s[x]<='z')return 1;else if(s[x]>='A' &&s[x]<='Z')return 2;else if(s[x]>='0'&&s[x]<='9')return 3;else if(s[x]==' ')return 4;else return 5;// 除空格以外的标点符号
}
//判断 独立性
int pan2(string s, int x ,int y){if((x<0 ||s[x]==' '||pan1(s,x)==5)&&(y>=s.size() || s[y]==' ' || pan1(s,y)==5)){return 1;}return 0;
}
int main() {cin>>n;getchar();while(n--){getline(cin,str);cout<<str<<endl<<"AI: ";string b="";//b是修改后的字符串 int l=0,r=str.size()-1;while(str[l]==' ')l++; // 去掉全部首空格while(str[r]==' ')r--;// 去掉全部尾空格 for(int i=l;i<=r;i++){if(str[i]==' ' &&(str[i+1]==' ' || pan1(str,i+1)==5)){ // 去掉多余空格（单词间的空格、标点符号前的空格） continue;}else if(str[i]=='?'){// ?变！b+='!';}else if(str[i]!='I'&&pan1(str,i)==2){ // 大写变小写 b+=str[i]+32;}else{b+=str[i]; // 其他字符}}for(int i=0;i<b.size();i++){if(b[i]=='I'&&pan2(b,i-1,i+1)){cout<<"you";}else if(b.substr(i,2)=="me"&&pan2(b,i-1,i+2)){// b.substr(i,2)代表截取b字符串从i下标开始的两个字符 cout<<"you";i=i+1;}else if(b.substr(i,7)=="can you"&&pan2(b,i-1,i+7)){cout<<"I can";i+=6;}else if(b.substr(i,9)=="could you"&&pan2(b,i-1,i+9)){cout<<"I could";i+=8;}else{cout<<b[i];}}cout<<endl;}return 0;
}

L1-069 胎压监测 (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];int main() {int maxx=0;int num[10]={0};for(int i=1;i<=4;i++){cin>>num[i];maxx=max(maxx,num[i]);}cin>>m>>k;vector<int>ans;for(int i=1;i<=4;i++){if(abs(num[i]-maxx)>k || num[i]<m ){ans.push_back(i);}}if(ans.size()==0){cout<<"Normal"<<endl;}else if(ans.size()==1){cout<<"Warning: please check #"<<ans[0]<<"!"<<endl;}else if(ans.size()>1){cout<<"Warning: please check all the tires!"<<endl;}return 0;
}

L1-070 吃火锅 (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];int main() {string str;vector<int>ans;int zongcount=0;for(int i=1; ; i++){getline(cin,str);if(str=="."){break;}zongcount++;if(str.find("chi1 huo3 guo1")!=string::npos){ans.push_back(zongcount);}}cout<<zongcount<<endl;if(ans.size()){cout<<ans[0]<<" "<<ans.size()<<endl;}else{cout<<"-_-#"<<endl;}return 0;
}

L1-071 前世档案 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];int main() {cin>>n>>m;while(m--){string str;cin>>str;int pos=1;for(int i=0;i<n;i++){if(str[i]=='y'){pos=pos*2-1;}else{pos=pos*2;}}cout<<pos<<endl;}return 0;
}

L1-072 刮刮彩票 (20 分)

#include<iostream>
using namespace std;
int main(){int a[4][4],value[25]={0,0,0,0,0,0,10000,36,720,360,80,252,108,72,54,180,72,180,119,36,306,1080,144,1800,3600};int i,j,ii,jj;int book[10]={0};for(i=1;i<=3;i++){for(j=1;j<=3;j++){cin>>a[i][j];int w=a[i][j];book[w]=1;if(a[i][j]==0){ii=i;jj=j;}} }   for(i=1;i<=9;i++){if(book[i]==0){a[ii][jj]=i;}}   for(i=0;i<3;i++){int n,m;cin>>n>>m;cout<<a[n][m]<<endl;}int x,sum=0;cin>>x;if(x==1){sum=a[1][1]+a[1][2]+a[1][3];}if(x==2){sum=a[2][1]+a[2][2]+a[2][3];}if(x==3){sum=a[3][1]+a[3][2]+a[3][3];}if(x==4){sum=a[1][1]+a[2][1]+a[3][1];}if(x==5){sum=a[1][2]+a[2][2]+a[3][2];}if(x==6){sum=a[1][3]+a[2][3]+a[3][3];}if(x==7){sum=a[1][1]+a[2][2]+a[3][3];}if(x==8){sum=a[1][3]+a[2][2]+a[3][1];}cout<<value[sum]<<endl;return 0;
} 

L1-077 大笨钟的心情 (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];int main() {int num[25]={0};for(int i=0;i<=23;i++){cin>>num[i];}while(cin>>x){if(x<0 || x>23){break;}if(num[x]>50){cout<<num[x]<<" Yes"<<endl;}else{cout<<num[x]<<" No"<<endl;}}return 0;
}

L1-078 吉老师的回归 (15 分)

// 这个注意点是那个getchar();;#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];int main() {cin>>n>>k;int cnt=0;//这个注意要进行吃回车。。getchar();for(int i=1;i<=n;i++){string str;getline(cin,str);int ix=str.find("qiandao");int iy=str.find("easy");if(ix==string::npos && iy==string::npos ){cnt++;}//cnt表示这道题在吉老师的面前是第几道题。//老师已经做完了k道题，，所以就是，在老师面前的k道题之前都不需要。if(i==n && cnt<=k){cout<<"Wo AK le"<<endl;    }if(cnt>k){cout<<str<<endl;break;}}return 0;
}

L1-079 天梯赛的善良 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];
map<int , int >mp;
int main() {cin>>n;vector<int>ans;for(int i=0;i<n;i++){cin>>x;mp[x]++;ans.push_back(x);}sort(ans.begin(),ans.end());cout<<ans[0]<<" "<<mp[ans[0]]<<endl;cout<<ans[ans.size()-1]<<" "<<mp[ans[ans.size()-1]]<<endl;return 0;
}

L1-080 乘法口诀数列 (20 分)

//用for可以标记次数。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];
vector<int>ans;
int main() {cin>>x>>y>>k;ans.push_back(x);ans.push_back(y);for(int i=0;i<=k;i++){int a=ans[i];int b=ans[i+1];if(a*b>=10){ans.push_back(a*b/10);ans.push_back(a*b%10);}else{ans.push_back(a*b);}}for(int i=0;i<k;i++){if(i==0){cout<<ans[i];}else{cout<<" "<<ans[i];}}return 0;
}

No.2 L2题目

L2-001 紧急救援 (25 分)

//这道题给的教训就是：：#define N 要恰到好处不能太大，也不能太小。。切记
#include <bits/stdc++.h>using namespace std;
#define inf 0x3f3f3f3f
#define N 1000
int n,m,s,d;
int x,y,z;
int mp[N][N];
int dis[N];
int vis[N]={0};//根据题意填的
int way[N];
int num[N];
int cnt[N];
int people[N];void dij(int start){//初始化dis等信息dis[start]=0;way[start]=start;cnt[start]=1;num[start]=people[start];for(int i=0;i<n;i++){dis[i]=mp[start][i];}//初始化结束。//找 n个 点for(int i=0;i<n;i++){int u=-1;int mind=inf;for(int j=0;j<n;j++){if(vis[j]==0 && dis[j]<mind){u=j;mind=dis[j];}}if(u==-1){break;}vis[u]=1;//更新最短距离：for(int j=0;j<n;j++){if(vis[j]==0 && dis[j]>dis[u]+mp[u][j]){dis[j]=dis[u]+mp[u][j];num[j]=num[u]+people[j];cnt[j]=cnt[u];way[j]=u;//c出现下面这个条件啊，就会再出来一个最优判断。}else if(vis[j]==0 && dis[j]==dis[u]+mp[u][j]){cnt[j]=cnt[j]+cnt[u];if(num[j]<num[u]+people[j]){num[j]=num[u]+people[j];way[j]=u;}}}}
}void Print(int t){if(t==s){cout<<t;return ;}Print(way[t]);cout<<" "<<t;
}int main()
{cin>>n>>m>>s>>d;for(int i=0;i<n;i++){cin>>people[i];}//初始化mpmemset(mp,inf,sizeof(mp));for(int i=0;i<N;i++){mp[i][i]=0;}for(int i=0;i<m;i++){cin>>x>>y>>z;mp[x][y]=mp[y][x]=z;}//初始化mp结束dij(s);cout<<cnt[d]<<" "<<num[d]<<endl;Print(d);return 0;
}

L2-002 链表去重 (25 分)

//这道题要注意的是 可能 b1的数量为0 即没有重复的
#include <bits/stdc++.h>using namespace std;
#define inf 0x3f3f3f3f
#define N 100000
int n,m,s,d;
int x,y,z;
struct node{int data;int next;
}aa[N];
int main()
{int fisadd,add;cin>>fisadd>>n;for(int i=0;i<n;i++){cin>>add;cin>>aa[add].data>>aa[add].next;}int book[N]={0};int a[N],b[N];int a1=0;int b1=0;for(int i=fisadd; i!=-1 ;i=aa[i].next){int num=abs(aa[i].data);if(book[num]==0){book[num]=1;a[a1++]=i;}else{b[b1++]=i;}}printf("%05d %d ",a[0] , aa[a[0] ].data);for(int i=1;i<a1;i++){printf("%05d\n" ,a[i]);printf("%05d %d ",a[i] ,aa[a[i] ].data);}cout<<"-1"<<endl;//记住判断b1的数量if(b1>0){printf("%05d %d ",b[0] , aa[b[0] ].data);for(int i=1;i<b1;i++){printf("%05d\n" ,b[i]);printf("%05d %d ",b[i] ,aa[b[i] ].data);}cout<<"-1"<<endl;}//        cout<<a[0]<<" "<<aa[a[0]].data<<" ";
//        for(int i=1;i<a1;i++){
//            cout<<a[i]<<endl;
//            cout<<a[i]<<" "<<aa[a[i] ].data<<" ";
//        }
//        cout<<"-1"<<endl;
//
//        cout<<b[0]<<" "<<aa[b[0] ].data<<" ";
//        for(int i=1;i<b1;i++){
//            cout<<b[i]<<endl;
//            cout<<b[i]<<" "<<aa[b[i] ].data<<" ";
//        }
//        cout<<"-1"<<endl;return 0;
}

L2-003 月饼 (25 分)

#include <bits/stdc++.h>using namespace std;
#define inf 0x3f3f3f3f
#define N 100000
int n,m,s,d;
int x,y,z;
struct node{double kucun;double zongsale;double avesale;
}moon[N];int cmp(node a, node b){return a.avesale>b.avesale;
}
int main()
{cin>>n>>d;for(int i=0;i<n;i++){cin>>moon[i].kucun;}for(int i=0;i<n;i++){cin>>moon[i].zongsale;}for(int i=0;i<n;i++){moon[i].avesale=moon[i].zongsale/moon[i].kucun;}sort(moon,moon+n,cmp);double sumsale=0.0;for(int i=0;i<n;i++){if(moon[i].kucun <d){sumsale=sumsale+moon[i].zongsale;d=d-moon[i].kucun;}else if(moon[i].kucun == d){sumsale=sumsale+moon[i].zongsale;break;}else if(moon[i].kucun >d){sumsale=sumsale+d*moon[i].avesale;break;}}printf("%.2f\n",sumsale);return 0;
}

（三）L2-004 这是二叉搜索树吗？ (25 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int pre[N];
bool ism=false;
vector<int>now;
void f(int l, int r){if(l>r)return ;int tl=l+1;//左孩子的区间的尽头。int tr=r;// 右孩子的区间的尽头。if(!ism){//正常while(tl<=r && pre[tl]<pre[l]) tl++;while(tr>=l+1 && pre[tr]>=pre[l]) tr--;}else{while(tl<=r && pre[tl]>=pre[l]) tl++;while(tr>=l+1 && pre[tr]<pre[l]) tr--;}if(tl-tr!=1)return;///如果不是二叉搜索树//类似输出前序遍历，中序遍历，后序遍历的写法//如果 要求输出中序遍历，则push_back()操作放在中间f(l+1,tr); //左,注意区间要去掉根f(tl,r);    //右now.push_back(pre[l]);//根，注意为pre[l];
}
int main() {cin>>n;for(int i=1;i<=n;i++){cin>>pre[i];}f(1,n);///第一次不成功可能因为是镜像if(now.size()!=n){now.clear();ism=true;f(1,n);}///镜像还不成功就说明不是搜索二叉树if(now.size()!=n){cout<<"NO"<<endl;}else{cout<<"YES"<<endl;for(int i=0;i<now.size();i++){if(i==0){cout<<now[i];}else{cout<<" "<<now[i];}}}return 0;
}判断给出的插入序列是否为建立的二叉搜索树的前序遍历，如果是，则输入二叉搜索树的后序遍历，不是再判断是否为二叉搜索树镜像的前序遍历，如果是，则输出二叉搜索树镜像的后序遍历，二者都不是则输出NO。
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
using namespace std;
const int N = 1005;
int n, pre[N], post[N], cnt, flag;typedef struct BST {int data;BST* lchild, * rchild;
}BSTNode,*BSTree;// 建树
bool BST_Insert(BSTree &T,int data)
{if (T == NULL) {T = new BSTNode;T->data = data;T->lchild = T->rchild = NULL;return true;}else if (data < T->data) {return BST_Insert(T->lchild, data);}else {return BST_Insert(T->rchild, data);}
}// 建镜像树
bool RBST_Insert(BSTree& T, int data)
{if (T == NULL) {T = new BSTNode;T->data = data;T->lchild = T->rchild = NULL;return true;}else if (data >= T->data) {return RBST_Insert(T->lchild, data);}else {return RBST_Insert(T->rchild, data);}
}void Prior_Order(BSTree T)
{if (T != NULL) {// 验证所给序列if (pre[++cnt] != T->data) {flag = 1;return;}Prior_Order(T->lchild);Prior_Order(T->rchild);}
}// 后序遍历
void Post_Order(BSTree T)
{if (T != NULL){Post_Order(T->lchild);Post_Order(T->rchild);post[++cnt] = T->data;}
}int main()
{ios::sync_with_stdio(false);BSTree T = NULL, R = NULL;cin >> n;for (int i = 1; i <= n; i++) {cin >> pre[i];BST_Insert(T, pre[i]);RBST_Insert(R, pre[i]);}Prior_Order(T);if (!flag) {cnt = 0;// 下标初始化cout << "YES\n";Post_Order(T);for (int i = 1; i < n; i++) {cout << post[i] << ' ';}cout << post[n];}else {cnt = 0; flag = 0;// 下标初始化Prior_Order(R);if (!flag) {cnt = 0;// 下标初始化cout << "YES\n";Post_Order(R);for (int i = 1; i < n; i++) {cout << post[i] << ' ';}cout << post[n];}else {cout << "NO\n";}}return 0;
}//第二种
#include <bits/stdc++.h>
using namespace std;
typedef struct node
{
int data;
struct node*left;
struct node*right;
} tree;
tree*creat(tree*root,int x)//建立搜索二叉树
{
if(!root)
{
root=new node;
root->data=x;
root->right=root->left=NULL;
}
else
{
if(x<root->data)
{root->left=creat(root->left,x);}else{root->right=creat(root->right,x);}}return root;
}
int first1[1010];
int first2[1010];
int flag1=0;
int flag2=0;
void first1_tree(tree*root)//二叉搜索树的前序遍历
{if(root){first1[flag1]=root->data;flag1++;first1_tree(root->left);first1_tree(root->right);}
}
void first2_tree(tree*root)//二叉搜索树的镜像的前序遍历
{if(root){first2[flag2]=root->data;flag2++;first2_tree(root->right);first2_tree(root->left);
}
}
int f=0;
void last1_tree(tree*root)//二叉搜索树的后序遍历
{
if(root)
{last1_tree(root->left);last1_tree(root->right);if(f==0){printf("%d",root->data);f=1;}else{printf(" %d",root->data);}}
}
void last2_tree(tree*root)//二叉搜索树镜像的后序遍历
{if(root)
{last2_tree(root->right);last2_tree(root->left);
if(f==0){printf("%d",root->data);f=1;}else{printf(" %d",root->data);}}
}
int main()
{int n;tree*root;
root=NULL;
scanf("%d",&n);
int num[1010];
for(int i=0; i<n; i++)
{int x;scanf("%d",&x);num[i]=x;root=creat(root,x);}first1_tree(root);first2_tree(root);int fflag1=0;int fflag2=0;for(int i=0; i<n; i++){if(first1[i]!=num[i]){fflag1=1;}}for(int i=0; i<n; i++){if(first2[i]!=num[i]){fflag2=1;}}if(fflag1==1&&fflag2==1){printf("NO\n");}else{printf("YES\n");if(fflag1==0){last1_tree(root);printf("\n");}else{last2_tree(root);printf("\n");}}return 0;
}

L2-005 集合相似度 (25 分)

#include <bits/stdc++.h>using namespace std;
#define inf 0x3f3f3f3f
#define N 100000
int n,m,s,d,k;
int x,y,z;set<int>sc[55];
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>m;for(int j=0;j<m;j++){cin>>x;sc[i].insert(x);}}cin>>k;while(k--){int a,b;cin>>a>>b;int sum1=sc[a].size();int sum2=sc[b].size();int sum3=0;set<int>::iterator it;for(it=sc[a].begin(); it!=sc[a].end(); it++){//共有的if(sc[b].find(*it)!=sc[b].end())sum3++;}printf("%.2lf",1.0*sum3/(sum1+sum2-sum3)*100);cout<<"%"<<endl;}return 0;
}

（三）L2-006 树的遍历 (25 分)

#include<bits/stdc++.h>
const int N = 1005;
using namespace std;int n;
int post[35], mid[35];
struct node{int lson, rson;//左右孩子
}f[35];int build(int lmid, int rmid, int lpost, int rpost){//中序遍历的左边界与右边界，后序遍历的左边界与右边界if(lmid > rmid || lpost > rpost)return 0;int root = post[rpost];int fa = lmid;while(mid[fa]!=root) fa++;int len = fa-lmid;f[root].lson = build(lmid, fa-1, lpost, lpost+len-1);f[root].rson = build(fa+1, rmid, lpost+len, rpost-1);return root;
}void bfs(int root){vector<int> ve;queue<int> qu;qu.push(root);while(!qu.empty()){int w = qu.front();qu.pop();ve.push_back(w);if(f[w].lson){qu.push(f[w].lson);}if(f[w].rson){qu.push(f[w].rson);}}for(int i = 0; i < ve.size(); i ++){if(i==0){cout<<ve[i];}else{cout<<" "<<ve[i];}}
}int main(){cin >> n;for(int i = 0; i < n; i ++) cin >> post[i];for(int i = 0; i < n; i ++) cin >> mid[i];int root = build(0, n-1, 0, n-1);bfs(root);return 0;
}对于给出后序和中序来重建二叉树, 因为后序的根一定在最后, 我们依次从后往前遍历post(见1处), 对于每一个post[postR], 找出其在in中的位置k, 然后递归重建即可
同理, 如果是给出前序和中序求得后序的话, 仅仅对顺序进行改动即可
#include<bits/stdc++.h>
using namespace std;
//思路：递归求解 分两个部分 恢复二叉树restree和利用队列层次遍历函数leveltra
vector<int> posord;
vector<int> midord;
//定义一个二叉树结构体
typedef struct btnode{int Data;struct btnode *Left,*Right;
}BTnode,*BTree;
//restree函数三个参数分别是后序遍历中的根节点，中序遍历的起点，中序遍历的终点
BTree restree(int root,int begin,int end){if(begin>end) return NULL;//叶子节点无子树int rnt;for(rnt=begin;rnt<end;rnt++)//在中序里找到根节点的位置{if(midord[rnt]==posord[root])break;}BTree Bt=BTree(malloc(sizeof(struct btnode)));Bt->Data=posord[root];Bt->Left=restree(root-1-(end-rnt),begin,rnt-1);Bt->Right=restree(root-1,rnt+1,end);return Bt;
}
void leveltra(BTree bt){queue<BTree> que;int flag=1;BTree temp = NULL;que.push(bt);while(!que.empty()){temp = que.front();if(flag){cout<<temp->Data; flag=0;}elsecout<<" "<<temp->Data;que.pop();if(temp->Left)que.push(temp->Left);if(temp->Right)que.push(temp->Right);}
}
int main(){int n;cin>>n;int m;for(int i=0;i<n;i++){cin>>m;posord.push_back(m);}for(int i=0;i<n;i++){cin>>m;midord.push_back(m);}leveltra(restree(n-1,0,n-1));return 0;
}///第二种
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1<<30;
const LL maxn = 35;struct node{int data;node *l, *r;
};
int N, pre[maxn], in[maxn], post[maxn];
//当前二叉树后序序列区间为[postL, postR], 中序序列区间为[inL, inR]
node* create(int postL, int postR, int inL, int inR){if(postL > postR)return NULL; //后序序列长度<=0node* root = new node;root->data = post[postR];int k;for(k = inL; k <= inR; k++)if(in[k] == post[postR])break;int numLeft = k - inL;  //左子树的节点个数root->l = create(postL, postL+numLeft-1, inL, k-1); //重建左子树root->r = create(postL+numLeft, postR-1, k+1, inR); //重建右子树 1处return root;
}
int indx = 1;
void Bfs(node* root){queue<node*> q;q.push(root);while(!q.empty()){node* cur = q.front();q.pop();if(indx++ != 1) cout << ' ' << cur->data;else cout << cur->data;if(cur->l != NULL) q.push(cur->l);if(cur->r != NULL) q.push(cur->r);}
}
int main()
{cin >> N;for(int i = 0; i < N; i++)cin >> post[i];for(int i = 0; i < N; i++)cin >> in[i];node* root = create(0, N-1, 0, N-1);//建树Bfs(root);                          //层序遍历return 0;
}

L2-007 家庭房产 (25 分)

//注意N的取值要大于id 不只是4位数，要五位数#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10050
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct message{int id,area,num;
}peo[N];
struct node{int id,people,area,num;double avearea,avenum;int flag;
}fami[N];
int f[N];
bool cmp(node a,node b){if(a.avearea!=b.avearea){return a.avearea>b.avearea;}return a.id<b.id;
}
void Init(){for(int i=0;i<=N;i++){f[i]=i;}
}
int find(int x){if(x!=f[x]){f[x]=find(f[x]);}return f[x];
}void merge(int x,int y){int fx=find(x);int fy=find(y);if(fx<fy){f[fy]=fx;}else{f[fx]=fy;}
}
int main() {cin>>n;Init();int id,fa,ma,child;int vis[N]={0};for(int i=0;i<n;i++){cin>>id>>fa>>ma>>k;vis[id]=1;peo[i].id=id;if(fa!=-1){vis[fa]=1;merge(id,fa);}if(ma!=-1){vis[ma]=1;merge(id,ma);}for(int j=0;j<k;j++){cin>>child;vis[child]=1;merge(id,child);}cin>>peo[i].num>>peo[i].area;}for(int i=0;i<n;i++){int idx=find(peo[i].id);fami[idx].id=idx;fami[idx].flag=1;fami[idx].area+=peo[i].area;fami[idx].num+=peo[i].num;}int cnt=0;for(int i=0;i<N;i++){if(vis[i]==1){fami[find(i)].people++;}if(fami[i].flag==1){cnt++;}}for(int i=0;i<N;i++ ){if(fami[i].flag==1){fami[i].avenum=fami[i].num*1.0/fami[i].people*1.0;fami[i].avearea=fami[i].area*1.0/fami[i].people*1.0;}}sort(fami,fami+N,cmp);cout<<cnt<<endl;for(int i=0;i<cnt;i++){printf("%04d %d %.3f %.3f\n",fami[i].id,fami[i].people ,fami[i].avenum ,fami[i].avearea);}return 0;
}

L2-008 最长对称子串 (25 分)

//记住 x=max(x,j-i+1);
#include<iostream>
using namespace std;
int main(){string s;getline(cin,s);int x=1;for(int i=0;i<s.size();i++){for(int j=s.size()-1;j>=i;j--){if(s[i]==s[j]){int l=i,r=j;while(l<=r&&s[l++]==s[r--]){if(l>r)x=max(x,j-i+1);}}}}cout<<x<<endl;return 0;
}

L2-009 抢红包 (25 分)

//这里注意输入的value 是分，所以单位换算成元。#include<bits/stdc++.h>
using namespace std;
struct node
{int id;//人的编号;int num;//人抢到红包的个数;int value;//抢到红包的金额;	
}person[10000];
bool f(struct node a,struct node b)
{if(a.value!=b.value)//如果金额没有并列,则按照总金额从达到小的顺序递减输出; {return a.value>b.value;}else if(a.num != b.num)//金额有并列，则按照抢到红包的个数递减输出;{return a.num>b.num;	} else if(a.id != b.id)//如果金额和抢到红包的个数都有并列,则按照人的编号递增输出;{return a.id<b.id;	} 
}
int main()
{int n,k,p,i,j,sum=0,n1;//k指的是抢到红包的个数,n指的是抢红包人的编号,p指的是抢到红包的金额;cin>>n;for(i=1;i<=n;i++){person[i].id = i;//编号是i的人对应的id值是i; cin>>k;sum=0;for(j=1;j<=k;j++){cin>>n1>>p;
//			person[n1].id = n1;易错点，因为你不知道每个人都抢了红包,当有的人没有抢，那么对应的id值就变成了0; person[n1].value = person[n1].value + p;//记录抢到红包的金额; person[n1].num ++;//记录抢到红包的个数; sum = sum + p;//记录第i个人发红包的总金额; }person[i].value = person[i].value - sum;//更新编号为i的人剩余的总金额;} //因为人的编号n是正整数,故需要将person加1;//person+n+1包含的范围是person+n，不包括那个1;//[person+1,person+n+1)---->[1,n]sort(person+1,person+n+1,f);//自动调用f()函数,包含在头文件 ----> #include<algorithm>for(i=1;i<=n;i++){//抢到红包的进金额是按照分这个单位来计算的,故需要在输出是转换成元; printf("%d %.2lf\n",person[i].id,person[i].value*1.0/100);}
}

L2-010 排座位 (25 分)

//这题别忘了把初始化给 在主函数进行调用实现。#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 101
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];
int mp[N][N]={0};
int f[N];
void Init(){for(int i=1;i<=n;i++){f[i]=i;}
}int find( int x){if(x!=f[x]){f[x]=find(f[x]);}return f[x];
}void merge(int x, int y){int fx=find(x);int fy=find(y);if(fx>fy){f[fx]=fy;}else{f[fy]=fx;}
}int main() {cin>>n>>m>>k;Init();for(int i=0;i<m;i++){cin>>x>>y>>z;if(z==-1){mp[x][y]=mp[y][x]=-1;}else{merge(x,y);}}while(k--){cin>>x>>y;int fx=find(x);int fy=find(y);if(fx==fy && mp[x][y]==0){cout<<"No problem"<<endl;}else if(fx!=fy && mp[x][y]==0){cout<<"OK"<<endl;}else if(fx==fy &&mp[x][y]==-1){cout<<"OK but..."<<endl;}else if(fx!=fy &&mp[x][y]==-1){cout<<"No way"<<endl;}}return 0;
}

（四）L2-011 玩转二叉树 (25 分)

镜像反转只需将层次遍历中先遍历右边的即可 ，其他就是建树的操作了～～
#include<bits/stdc++.h>
const int N = 1005;
using namespace std;int n;
int pre[35], mid[35];
struct node{int lson, rson;//左右孩子
}f[35];int build(int lmid, int rmid, int lpre, int rpre){//中序遍历的左边界与右边界，中序遍历的左边界与右边界if(lmid > rmid )return 0;int root = pre[lpre];int fa = lmid;while(mid[fa]!=root) fa++;//len是表示左子树的结点个数数量。int len = fa-lmid;f[root].lson = build(lmid, fa-1, lpre+1, lpre+len);f[root].rson = build(fa+1, rmid, lpre+len+1, rpre);return root;
}void bfs(int root){vector<int> ve;queue<int> qu;qu.push(root);while(!qu.empty()){int w = qu.front();qu.pop();ve.push_back(w);if(f[w].rson){qu.push(f[w].rson);}if(f[w].lson){qu.push(f[w].lson);}}for(int i = 0; i < ve.size(); i ++){if(i==0){cout<<ve[i];}else{cout<<" "<<ve[i];}}
}int main(){cin >> n;for(int i = 0; i < n; i ++) cin >> mid[i];for(int i = 0; i < n; i ++) cin >> pre[i];int root = build(0, n-1, 0, n-1);bfs(root);return 0;
}

（四）L2-012 关于堆的判断 (25 分)

//下一行给出区间[−10000,10000]内的N个要被插入一个初始为空的小顶堆的整数
//即要根据给的进行建立堆，，
//且根据层序进行创建储存。。
//因为是堆总是一棵完全二叉树。所以可以用 2*i or 2*i+1#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int h[N];
int find(int x){for(int i=1;i<=n;i++){if(h[i]==x){return i;}}return -1;
}
int main() {cin>>n>>m;for(int i=1;i<=n;i++){cin>>h[i];int k=i;while(k>1 && h[k]<h[k/2]){swap(h[k],h[k/2]);k=k/2;}}while(m--){cin>>x;int a=find(x);//根据结点的值找到该节点值的位置；string s;cin>>s;if(s=="and"){cin>>y>>s>>s;int b=find(y);if(a/2==b/2){cout<<"T"<<endl;}else{cout<<"F"<<endl;}}else{cin>>s;if(s=="a"){cin>>s>>s>>y;int b=find(y);if(a/2==b){cout<<"T"<<endl;}else{cout<<"F"<<endl;}}else{cin>>s;if(s=="root"){if(a==1){cout<<"T"<<endl;}else{cout<<"F"<<endl;}}else{cin>>s>>y;int b=find(y);if(a==b/2){cout<<"T"<<endl;}else{cout<<"F"<<endl;}}}}}return 0;
}

L2-013 红色警报 (25 分)

//这道题注意更新 sum=cur
//这次因为输出的字符串少了最后那个句号标点
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1001
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];
int vis[N]={0};
void dfs(int index){vis[index]=1;for(int i=0;i<v[index].size();i++){if(vis[v[index][i]]==0){dfs(v[index][i]);}}}
int cnt(){int count=0;for(int i=0;i<n;i++){if(vis[i]==0){count++;dfs(i);}}memset(vis,0,sizeof(vis));return count;
}
int main() {cin>>n>>m;for(int i=0;i<m;i++){cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}int sum=cnt();cin>>k;vector<int>lost;while(k--){cin>>x;lost.push_back(x);for(int i=0;i<lost.size();i++){vis[lost[i]]=1;}int cur=cnt();//目前这个cur是不算lost的其它的连通分量，//连通区域越多，说明城市间越不连通，月危险if(cur>sum){cout<<"Red Alert: City "<<x<<" is lost!"<<endl;}else if(cur<=sum){// 这个是因为如果失去的那个是独立的，则cur会比一开始的-1；cout<<"City "<<x<<" is lost."<<endl;}sum=cur;}if(lost.size()==n){cout<<"Game Over."<<endl;}return 0;
}

L2-014 列车调度 (25 分)

//更新通道的下限最大值。
#include<iostream>
#include<set>
using namespace std;
int main()
{int n;cin>>n;set<int>sc;for(int i=0;i<n;i++){int k;scanf("%d",&k);set<int>::iterator it=sc.lower_bound(k);//一条轨道多辆车if(it!=sc.end()){sc.erase(it);sc.insert(k);}elsesc.insert(k);}cout<<sc.size();
}

L2-015 互评成绩 (25 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
bool cmp(double a,double b){return a>b;
}
int main() {vector<double> ans;cin>>n>>k>>m;for(int i=0;i<n;i++){double sum=0;int maxx=0,minn=inf;for(int j=0;j<k;j++){cin>>x;sum=sum+x;maxx=max(x,maxx);minn=min(x,minn);}sum=(sum-maxx-minn)/(k-2);ans.push_back(sum);}sort(ans.begin(),ans.end(),cmp);for(int i=m-1;i>=0;i--){if(i==m-1){printf("%.3f",ans[i]);}else{printf(" %.3f",ans[i]);}}return 0;
}

L2-016 愿天下有情人都是失散多年的兄妹 (25 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];
int sex[N];
int flag=0;
int vis[N]={0};
void dfs(int index , int dai){if(dai>4){return;}for(int i=0;i<v[index].size();i++){if(vis[v[index][i]]==0){vis[v[index][i]]=1;dfs(v[index][i],dai+1);}else{flag=1;}}
}
int main() {cin>>n;int id,fa,ma ;char s;for(int i=0;i<n;i++){cin>>id>>s>>fa>>ma;sex[id]=s;if(fa!=-1){sex[fa]='M';v[id].push_back(fa);}if(ma!=-1){sex[ma]='F';v[id].push_back(ma);}}cin>>k;while(k--){cin>>x>>y;if(sex[x]==sex[y]){cout<<"Never Mind"<<endl;}else{//每次都要初始化一次。。。flag=0;memset(vis,0,sizeof(vis));vis[x]=vis[y]=1;bfs(x,1);bfs(y,1);if(flag==0){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}}return 0;
}

L2-017 人以群分 (25 分)

升序排序然后直接算差值就行，如果个数奇数一定是外向的比内向的多一个。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
int num[N]={0};
int main() {cin>>n;for(int i=0;i<n;i++){cin>>num[i];}sort(num,num+n);int peo=0;int ple=0;if(n%2==0){peo=n/2;ple=peo;}else{peo=n/2;ple=n-peo;}int sum1=0;int sum2=0;for(int i=0;i<peo;i++){sum1=sum1+num[i];}for(int i=peo;i<n;i++){sum2=sum2+num[i];}cout<<"Outgoing #: "<<ple<<endl;cout<<"Introverted #: "<<peo<<endl;cout<<"Diff = "<<sum2-sum1<<endl;return 0;
}

（五）L2-018 多项式A除以B (25 分)

定义两个数组：a,b，分别表示多项式A和多项式B；两个数组的下标表示指数，数组值代表系数；所以要定义double类型并求出两个多项式中最大指数index1和index2；在进行每一次除法之后，商的最高次幂是(max1-max2)，最高次幂的系数是（a[index1]/b[index2]）；然后继续循环，并更新a，直至被除数的最高次幂小于除数；#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
void pout(double arr[],int x)
{int num=0;for(int i=0;i<=x;i++){//因为保留一位小数，所以+0.05与0.1比较if(abs(arr[i])+0.05>=0.1)num++;}cout<<num;if(num==0){cout<<" 0 0.0";}else{for(int i=x;i>=0;i--){if(abs(arr[i])+0.05>=0.1){cout<<" "<<i;printf(" %.1f",arr[i]);}}}
}
int main()
{double a[N],b[N],c[N];int index1=-1,index2=-1;//两个多项式的最大指数 cin>>n;for(int i=1;i<=n;i++){cin>>x;cin>>a[x];if(x>index1)index1=x;}cin>>m;for(int i=1;i<=m;i++){cin>>x;cin>>b[x];if(x>index2)index2=x;}int temp=index1-index2;//商的最大指数while(index1>=index2)//中余数的阶数必须小于除数的阶数。{double q=a[index1]/b[index2];//cout<<index1<<" "<<index2<<" "<<q<<endl;c[index1-index2]=q;for(int i=index1,j=index2;i>=0&&j>=0;i--,j--){a[i]-=b[j]*q;}while(a[index1]==0)index1--;//系数为0 } pout(c,temp);cout<<endl;pout(a,index1);return 0;
}

L2-019 悄悄关注 (25 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{string name;int num;
}stu[N];
bool cmp(node a,node b){return a.name<b.name;
}
int main() {getline(cin,str);cin>>n;int sum=0;for(int i=0;i<n;i++){cin>>stu[i].name>>stu[i].num;sum=sum+stu[i].num;}int avesum=sum/n;sort(stu,stu+n,cmp);int flag=0;for(int i=0;i<n;i++){if(stu[i].num>avesum && str.find(stu[i].name)==string::npos){cout<<stu[i].name<<endl;flag=1;}}if(flag==0){cout<<"Bing Mei You"<<endl;}return 0;
}

L2-020 功夫传人 (25 分)

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 101000
vector<int>v[N];
vector<int>cur; //存储最终的
vector<int>upda; //存储随时更新的
double cnt=0;
int de[N]={0};
double f,k;
void dfs(int index, vector<int>&upda  ,double gong){//增添判断区域。if(de[index]!=0){cnt=cnt+gong*de[index];}for( int i=0;i<v[index].size();i++){upda.push_back(v[index][i]);dfs(v[index][i], upda , gong*(1-0.01*k));upda.pop_back(); //记得回溯！！}
}
int main() {int n;int x,y;cin>>n>>f>>k;for(int i=0;i<n;i++){cin>>x;if(x==0){cin>>y;de[i]=y;}else{while(x--){cin>>y;v[i].push_back(y);}}}upda.push_back(0);dfs(0, upda, f );cout<<(int)cnt<<endl;return 0;
}

L2-021 点赞狂魔 (25 分)

#include <bits/stdc++.h>
using namespace std;
int n,m,k;
int x,y,z;
set<int> sc;
struct node{string name;int num;int ave;
}aa[101];
bool cmp(node a, node b){if(a.num==b.num){return a.ave<b.ave;}return a.num>b.num;
}
int main() {cin>>n;for(int i=0;i<n;i++){cin>>aa[i].name;cin>>k;//一定要记得清空sc.clear();//标签出现次数平均值最小的那个aa[i].ave=k;while(k--){cin>>x;sc.insert(x);}aa[i].num=sc.size();}sort(aa,aa+n,cmp);if(n==1){cout<<aa[0].name<<" -"<<" "<<"-"<<endl;}else if(n==2){cout<<aa[0].name<<" "<<aa[1].name<<" "<<"-"<<endl;}else{cout<<aa[0].name<<" "<<aa[1].name<<" "<<aa[2].name<<endl;}return 0;
}

L2-022 重排链表 (25 分)

#include<bits/stdc++.h>
#define N 100030
using namespace std;
int n,m,s,k,d;
int x,y,z;
struct node{int data;int next;
}v[N];
int main() {int firadd,add;cin>>firadd>>n;for(int i=0;i<n;i++){cin>>add;cin>>v[add].data>>v[add].next;}//a用来存一开始的所有点的顺序地址//b用来存后来按要求需要的地址输出的位置int a[N],b[N];int a1=0,b1=0;for(int i=firadd ; i!=-1 ; i=v[i].next){a[a1++]=i;}int l=0,r=a1-1;while(l<=r){//b里面先存a里面最后一个，然后a里面第一个依次累存if(l<=r){     b[b1++]=a[r--];             }if(l<=r){     b[b1++]=a[l++];             }}for(int i=0;i<b1-1;i++){printf("%05d %d %05d\n" , b[i] , v[b[i] ].data , b[i+1]);}printf("%05d %d -1\n",b[b1-1] , v[b[b1-1] ].data);return 0;
}

L2-023 图着色问题 (25 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>n>>m>>d;for(int i=0;i<m;i++){cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}cin>>k;while(k--){set<int>co;int color[n+1]={0};for(int i=1;i<=n;i++ ){cin>>color[i];co.insert(color[i]);}if(co.size()!=d){cout<<"No"<<endl;continue;}int flag=0;for(int i=1;i<=n;i++){for(int j=0;j<v[i].size();j++){if(color[i]==color[v[i][j]]){flag=1;break;}}if(flag==1){break;}}if(flag==1){cout<<"No"<<endl;}else{cout<<"Yes"<<endl;}}return 0;
}

L2-024 部落 (25 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int f[N];
void Init(){for(int i=1;i<=N;i++){f[i]=i;}
}
int find(int x){if(x!=f[x]){f[x]=find(f[x]);}return f[x];
}void merge(int x, int y){int fx=find(x);int fy=find(y);if(fx>fy){f[fx]=fy;}else{f[fy]=fx;}
}
int flag[N]={0};
int main() {Init();int a,b;set<int>people;cin>>n;for(int i=1;i<=n;i++){cin>>k;cin>>a;people.insert(a);for(int i=1;i<k;i++){cin>>b;people.insert(b);merge(a,b);}}int book[N]={0};set<int>::iterator it;for(it=people.begin();it!=people.end();it++){book[find(*it)]++;}int cnt=0;for(int i=0;i<N;i++){if(book[i]>0)cnt++;}cout<<people.size()<<" "<<cnt<<endl;cin>>k;while(k--){cin>>x>>y;if(find(x)==find(y))cout<<"Y"<<endl;else cout<<"N"<<endl;}return 0;
}

L2-025 分而治之 (25 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int vis[N];void dfs(int index){vis[index]=1;for(int i=0;i<v[index].size();i++){if(vis[v[index][i]]==0){vis[v[index][i]]=1;dfs(v[index][i]);}}
}
int cnt(){int count=0;for(int i=1;i<=n;i++){if(vis[i]==0){count++;dfs(i);}}memset(vis,0,sizeof(vis));return count;
}
int main() {cin>>n>>m;for(int i=0;i<m;i++){cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}int sum=cnt();cin>>k;while(k--){vector<int>lost;cin>>d;for(int i=0;i<d;i++){cin>>x;lost.push_back(x);}for(int i=0;i<lost.size();i++){vis[lost[i]]=1;}int cur=cnt();if(n==cur+d){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0;
}

L2-026 小字辈 (25 分)

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 101000
vector<int>v[N];
int level[N],vis[N]={0};
void bfs(int u)
{memset(vis,0,sizeof vis);memset(level,0,sizeof level);queue<int>q;q.push(u);while(!q.empty()){int x=q.front();vis[x]=1;q.pop();for(int i=0;i<v[x].size();i++){if(!level[v[x][i]]&&!vis[v[x][i]]){level[v[x][i]]=level[x]+1;	//level[x]表示x点在第几层次vis[v[x][i]]=1;q.push(v[x][i]);}}}}int main() {int n,m,k;int x,y,z;int start;cin>>n;if(n==1){cout<<"1"<<endl;cout<<"1"<<endl;return 0;}for(int i=1;i<=n;i++){cin>>x;if(x==-1){start=i;}else{v[x].push_back(i);}}bfs(start);int maxx=0;for(int i=1;i<=n;i++)if(maxx<level[i]) maxx=level[i];//保存最大层数cout<<maxx+1<<endl;int ok=1;for(int i=1;i<=n;i++)if(maxx==level[i]) {if(ok==1){cout<<i;ok=0;}else{cout<<" "<<i;}}//返回最大层数的最小编号，无相连的跳过return 0;
}

L2-027 名人堂与代金券 (25 分)

// 这一题是一个简单的结构体自定义排序，但是要解决一个输出前k名(有可能并列)的问题我们的解决方法是在排序完成之后重新遍历一次list数组，如果当前的人的成绩等于前一个人，那么我们就让当前的人的排名等于前一个人，如果不等于，他的成绩就等于他的下标加一。当然,在此之前，我们把第一个人的排名等于一
#include<bits/stdc++.h>
#define N 10005
using namespace std;
#define inf 0x3f3f3f3fint n,m,k,g,d;
int x,y,z;
vector<int>v[N];
struct node{string name;int fen;
}stu[N];
bool cmp(node a, node b){if(a.fen==b.fen){return a.name<b.name;}return a.fen>b.fen;
}
int main() {cin>>n>>g>>k;//这个一定要赋予初值0int sum=0;for(int i=0;i<n;i++){cin>>stu[i].name>>stu[i].fen;if(stu[i].fen>=g){sum=sum+50;}else if(stu[i].fen>=60){sum=sum+20;}}sort(stu,stu+n,cmp);cout<<sum<<endl;int rank[N];rank[0]=1;for(int i=1;i<n;i++){if(stu[i].fen==stu[i-1].fen){rank[i]=rank[i-1];}else{rank[i]=i+1;}}//输出的时候要注意。。for(int i=0;rank[i]<=k &&i<n;i++){cout<<rank[i]<<" "<<stu[i].name<<" "<<stu[i].fen<<endl;}return 0;
}

L2-028 秀恩爱分得快 (25 分)

思路：用一个二维数组g来存储在同一张照片的不同人之间的亲密度，maxn来记录和A和异性的最大亲密度和B和异性的最大亲密度，因为题目要求按他们编号的绝对值递增输出，所以我们采用set分别存储男性和女性，最后遍历输出就行了注：stoi是将string类型转换成int型//这个1010会超时，1001不会超时。。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>using namespace std;const int N=1001;double g[N][N],maxn[N];
vector<int>a,b;
set<int>A,B;
int n,m;int main()
{cin>>n>>m;while(m--){int k;a.clear();b.clear();cin>>k;for(int i=0;i<k;i++){string s;cin>>s;if(s[0]=='-')//女性{a.push_back(abs(stoi(s)));A.insert(abs(stoi(s)));}else//男性{b.push_back(stoi(s));B.insert(stoi(s));}}for(int i=0;i<a.size();i++){for(int j=0;j<b.size();j++){g[a[i]][b[j]]+=1.0/k;g[b[j]][a[i]]+=1.0/k;if(maxn[a[i]]<g[a[i]][b[j]]) maxn[a[i]]=g[a[i]][b[j]];if(maxn[b[j]]<g[b[j]][a[i]]) maxn[b[j]]=g[b[j]][a[i]];}}}string s1,s2;int aa,bb;cin>>s1>>s2;aa=abs(stoi(s1)),bb=abs(stoi(s2));if(maxn[aa]==g[aa][bb]&&maxn[bb]==g[bb][aa])//s1和s2正是彼此亲密度最高的{cout<<s1<<' '<<s2;return 0;}if(s1[0]=='-')//第一个人是女性{for(auto p:B)//遍历异性if(maxn[aa]==g[p][aa])cout<<s1<<' '<<p<<endl;}else{for(auto p:A)if(maxn[aa]==g[p][aa])cout<<s1<<' '<<'-'<<p<<endl;}if(s2[0]=='-'){for(auto p:B)if(maxn[bb]==g[bb][p])cout<<s2<<' '<<p<<endl;}else{for(auto p:A)if(maxn[bb]==g[bb][p])cout<<s2<<' '<<'-'<<p<<endl;}return 0;
}//
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>using namespace std;
#define N 1001
int n,m,k;
int x,y,z;
string str;
int main() {cin>>n>>m;set<int>A;set<int>B;vector<int>a;vector<int>b;double g[N][N];double maxx[N];while(m--){vector<int>a;vector<int>b;cin>>k;for(int i=0;i<k;i++){cin>>str;x=abs(stoi(str));if(str[0]=='-'){A.insert(x);a.push_back(x);}else{B.insert(x);b.push_back(x);}}for(int i=0;i<a.size();i++){for(int j=0;j<b.size();j++){g[a[i]][b[j]]=g[b[j]][a[i]]+=1.0/k;maxx[a[i]]=max(maxx[a[i]],g[a[i]][b[j]]);maxx[b[j]]=max(maxx[b[j]],g[a[i]][b[j]]);}}}string s1,s2;cin>>s1>>s2;int a1=abs(stoi(s1));int a2=abs(stoi(s2));if(maxx[a1]==g[a1][a2] &&maxx[a2]==g[a2][a1]){cout<<s1<<" "<<s2<<endl;return 0;}if(s1[0]=='-'){for(auto p:B){if(maxx[a1]==g[a1][p]){cout<<s1<<" "<<p<<endl;}}}else{for(auto p:A){if(maxx[a1]==g[a1][p]){cout<<s1<<" -"<<p<<endl;}}}if(s2[0]=='-'){for(auto p:B){if(maxx[a2]==g[a2][p]){cout<<s2<<" "<<p<<endl;}}}else{for(auto p:A){if(maxx[a2]==g[a2][p]){cout<<s2<<" -"<<p<<endl;}}}return 0;
}

L2-029 特立独行的幸福 (25 分)

思路有点暴力，一开始这么想觉得可能会超时，幸好比赛的时候过了。1、for循环对区间的每一个数进行判断是否是幸福数2、迭代：对这个数一直求各位的平方和，直到平方和为1，或者平方和重复出现，平且标记出现过的平方和（用于排除非独立的幸福数）3、如果是因为平方和为1而结束循环，说明这个数是一个幸福数，那么可以对它进行存储。4、输出时注意，需要排除非独立的幸福数（本身出现在另一个数的求平方和过程中，就不是独立的幸福数（前面已标记））#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int isP(int x){for(int i=2;i<=sqrt(x);i++){if(x%i==0)return 1;}return 2;
}
int book[N]={0};
int main() {int l,r;cin>>l>>r;map<int,int>mp;for(int i=l;i<=r;i++){vector<int>ans;int t=i;while(t!=1){int sum=0;while(t){sum+=(t%10)*(t%10);t=t/10;}t=sum;if(find(ans.begin(),ans.end(),sum)!=ans.end()){break;}ans.push_back(sum);//第一个本身并不会被标记。只会标记其他过程中的。。book[t]=1;//标记出现过的数}if(t==1){mp[i]=ans.size();//存储辛福数}}int flag=0;for(int i=l;i<=r;i++){if(book[i]==0 &&mp[i]>0){cout<<i<<" "<<mp[i]*isP(i)<<endl;flag=1;}}if(flag==0){cout<<"SAD"<<endl;}return 0;
}

（五）L2-030 冰岛人 (25 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{char gen;string father;
};
map<string,node>mp;bool check(string a, string b){map<string,int>vis;for(int i=1;;i++){vis[a]=i;a=mp[a].father;if(a.empty())break;}for(int i=1;;i++){//在b内只需呀循环遍历看是否vis>0;如果>0表示在a的已经出现过了if(vis[b]>0 &&(i<5 || vis[b]<5))return false;b=mp[b].father;if(b.empty())break;}return true;}
int main() {string a,b,a1,b1;cin>>n;while(n--){cin>>a>>b;if(b.back()=='n'){mp[a].gen='m';mp[a].father=b.substr(0,b.size()-4); }else if(b.back()=='r'){mp[a].gen='f';mp[a].father=b.substr(0,b.size()-7);}else{mp[a].gen=b.back();}}cin>>k;while(k--){cin>>a>>a1>>b>>b1;if(mp.find(a)==mp.end() || mp.find(b)==mp.end()){cout<<"NA"<<endl;}else if(mp[a].gen==mp[b].gen){cout<<"Whatever"<<endl;}else{if(check(a,b))cout<<"Yes"<<endl;else cout<<"No"<<endl;}}return 0;
}

L2-031 深入虎穴 (25 分)

//从1开始且最后是输出编号
#include<bits/stdc++.h>
#define N 10003
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,d;
int x,y,z;
vector<int>v[N];
int root[N]={0};int level[N],vis[N];
void bfs(int index){memset(level,0,sizeof(level));memset(vis,0,sizeof(vis));queue<int>q;q.push(index);while(!q.empty()){int num=q.front();vis[num]=1;q.pop();for(int i=0;i<v[num].size();i++){if(vis[v[num][i]]==0 && level[v[num][i]]==0){level[v[num][i]]=level[num]+1;vis[v[num][i]]=1;q.push(v[num][i]);}}}
}
int main() {cin>>n;if(n==1){cout<<"1"<<endl;return 0;}for(int i=1;i<=n;i++){cin>>k;while(k--){cin>>x;root[x]=1;v[i].push_back(x);}}int start;for(int i=1;i<=n;i++){if(root[i]==0){start=i;}}bfs(start);int maxx=0;for(int i=1;i<=n;i++){if(level[i]>maxx){maxx=level[i];}}for(int i=1;i<=n;i++){if(level[i]==maxx){cout<<i<<endl;break;}}    return 0;
}

L2-032 彩虹瓶 (25 分)

//记住stack' 没有 s.clear（）
#include <bits/stdc++.h>
using namespace std;int main()
{int N,M,K;   //彩虹瓶的颜色数量N、临时货架的容量M、需要判断的发货顺序的数量Kcin >> N >> M >> K;while(K--){stack<int> s;   //这个stack表示临时货架bool flag = true;  //判断工人能否愉快完工int cnt = 1;  //用来记录彩虹瓶当前需要填装的货号for(int i = 1; i <= N; i++){int temp;cin >> temp;if(temp != cnt)  //如果不是当前需要填装的货号{s.push(temp);   //放在临时货架上if(s.size() > M)   //只要大于临时货架容量就直接GG{flag = false;}}else{cnt++;   //填装下一个货号while(!s.empty()){if(s.top() == cnt)  //若放在货架最上方的货能装填就继续{s.pop();cnt++;}else break;}}}if(flag && cnt>=N)  //工人能愉快完工,且填装的货号达到了彩虹瓶颜色数量N{cout << "YES" << endl;}else{cout << "NO" << endl;}}return 0;
}

L2-033 简单计算器 (25 分)

//这里面是num2 op num1 #include<bits/stdc++.h>
using namespace std;
int main() {int n;cin >> n;stack<int>s1;for (int i = 0; i < n;i++) {int temp; cin >> temp;s1.push(temp);}stack<char>s2;for (int i = 1; i < n;i++) {char tem; cin >> tem;s2.push(tem);}while (!s2.empty()) {char top = s2.top();s2.pop();int a = s1.top(); s1.pop();  int b = s1.top(); s1.pop();if (top == '/' && a == 0) {cout << "ERROR: " << b << "/" << a;return 0;}else {if (top == '+') {s1.push(a+b);}else if (top == '-') {s1.push(b-a);}else if (top=='*') {s1.push(b*a);}else if (top=='/') {s1.push(b/a);}}}cout << s1.top();return 0;
}

L2-034 口罩发放 (25 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1005
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{string id,name;int hh;int mm;int time;int flag;int cixu;
}stu[N];
bool cmp(node a,node b){if(a.time!=b.time){return a.time<b.time;}return a.cixu<b.cixu;
}
int main() {int p,sum,flag=0;map<string,int>vis;map<string,int>day;cin>>d>>p;vector<node>vv;vector<node>ww;for(int i=1;i<=d;i++){vv.clear();cin>>k>>sum;for(int j=1;j<=k;j++){flag=0;cin>>stu[j].name>>stu[j].id>>stu[j].flag>>stu[j].hh>>ch>>stu[j].mm;stu[j].cixu=j;stu[j].time=stu[j].hh*60+stu[j].mm;for(int l=0;l<stu[j].id.length();l++){if(!isdigit(stu[j].id[l])){flag=1;}}if(stu[j].id.size()==18 && flag==0){vv.push_back(stu[j]);ww.push_back(stu[j]);}           }sort(vv.begin(),vv.end(),cmp);for(auto n:vv){if(sum==0)break;if(day[n.id]<=i){day[n.id]=i+p+1;cout<<n.name<<" "<<n.id<<endl;sum--;}}}for(auto n:ww){if(n.flag==1 &&vis[n.id]==0){cout<<n.name<<" "<<n.id<<endl;vis[n.id]=1;}}return 0;
}

L2-035 完全二叉树的层序遍历 (25 分)

#include <iostream>
using namespace std;int n, tree[31];void create(int i) {if (i > n)return;create(2 * i);create(2 * i + 1);cin >> tree[i];
}int main() {cin >> n;create(1);for (int i = 1; i <= n; i++) {if (i > 1)cout << " ";cout << tree[i];}return 0;
}

L2-036 网红点打卡攻略 (25 分)

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 202
int mp[N][N];
int cnt=0;
int main() {//输入：int n,m,s,k;int x,y,z;cin>>n>>m;memset(mp,inf,sizeof(mp));while(m--){cin>>x>>y>>z;mp[x][y]=mp[y][x]=z;}cin>>k;int minn=inf;int ans=0;for(int i=1;i<=k;i++){int t;int mon=0;cin>>t;int a[t+1];a[0]=0;int flag=0;int vis[t+1]={0};int num=0;for(int j=1;j<=t;j++){ //对每一个点都进行检验。cin>>a[j];if(vis[a[j]]) flag=1; // 访问一次的检验else{vis[a[j]]=1;num++;if(mp[a[j]][a[j-1]]==inf){	// 是否连通的检验flag=1;}else{mon=mon+mp[a[j]][a[j-1]];}}}mon=mon+mp[0][a[t]];if(num!=n ||mp[0][a[t]]==inf){flag=1;}if(flag==0){cnt++;if(mon<minn){minn=mon;ans=i;}}}cout<<cnt<<endl;cout<<ans<<" "<<minn<<endl;return 0;
}

L2-037 包装机 (25 分)

// 这个主要是注意 N 别<101  也不能太大，要恰到好处才能行。
#include <bits/stdc++.h>
using namespace std;
#define N 10100
queue<char> v[N];
stack<char> sc;
int main() {//输入：int n,m,s,k;char ch;int x,y,z;cin>>n>>m>>s;// i从1开始for(int i=1;i<=n;i++){for(int j=0;j<m;j++){cin>>ch;v[i].push(ch);}}while(cin>>k){if(k==-1){break;}if(k==0){if(sc.size()>0){   cout<<sc.top();sc.pop();}}else{if(v[k].size()>0){if(sc.size()==s){cout<<sc.top();sc.pop();}sc.push(v[k].front());v[k].pop();}}}return 0;
}

L2-038 病毒溯源 (25 分)

//内存超了的，但是可以是一个模板
#include <bits/stdc++.h>
using namespace std;
#define N 10001
vector<int>v[N];
vector<int>cur; //存储最终的
int root[N]={0};struct node {int num;vector<int>ff;
}aa[N];
bool cmp(node a, node b){if(a.num==b.num){return a.ff<b.ff;}return a.num>b.num;}
int p=0;
int q=0;
void dfs(int index, vector<int>&upda){if(upda.size()>=cur.size()){cur.clear();cur=upda;aa[p++].ff=cur;aa[q++].num=cur.size();}for(int i=0;i<v[index].size();i++){upda.push_back(v[index][i]);dfs(v[index][i],upda);upda.pop_back(); //记得回溯！！}}
int main() {int n,m,k;int x,y,z;cin>>n;for(int i=0;i<n;i++){cin>>k;while(k--){cin>>x;v[i].push_back(x);root[x]=1;}}//找出发点int start;for(int i=0;i<n;i++){if(root[i]==0){start=i;}}//进行dfs的过程vector<int>upda;upda.push_back(start);dfs(start, upda);sort(aa,aa+n,cmp);cout<<aa[0].num<<endl;for(int i=0;i<aa[0].num;i++){if(i==0){cout<<aa[0].ff[i];}else{cout<<" "<<aa[0].ff[i];}}return 0;
}//对于超内存的进行更改
#include <bits/stdc++.h>
using namespace std;
#define N 10001
vector<int>v[N];
vector<int>cur; //存储最终的
vector<int>upda;
int root[N]={0};void dfs(int index, vector<int>&upda){if(upda.size()>cur.size()){cur.clear();cur=upda;}for(int i=0;i<v[index].size();i++){upda.push_back(v[index][i]);dfs(v[index][i],upda);upda.pop_back(); //记得回溯！！}}
int main() {int n,m,k;int x,y,z;cin>>n;for(int i=0;i<n;i++){cin>>k;while(k--){cin>>x;v[i].push_back(x);root[x]=1;}//这个排序之后，就不用再结构体排序了。if(v[i].size()){sort(v[i].begin(),v[i].end());}}//找出发点int start;for(int i=0;i<n;i++){if(root[i]==0){start=i;}}//进行dfs的过程upda.push_back(start);dfs(start, upda);cout<<cur.size()<<endl;for(int i=0;i<cur.size();i++){if(i==0){cout<<cur[i];}else{cout<<" "<<cur[i];}}return 0;
}

L2-039 清点代码库 (25 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{vector<int>ff;int num;
}stu[N];
bool cmp(node a,node b){if(a.num!=b.num){return a.num>b.num;}return a.ff<b.ff;
}
int main() {map<vector<int> , int>mp;set<vector<int>>sc;cin>>n>>m;for(int i=1;i<=n;i++){vector<int>ans;for(int j=0;j<m;j++){cin>>x;ans.push_back(x);}mp[ans]++;sc.insert(ans);}int a=0;for(auto n:sc){stu[a].ff=n;stu[a].num=mp[n];a++;}sort(stu,stu+a,cmp);cout<<sc.size()<<endl;for(int i=0;i<a;i++){cout<<stu[i].num;for(auto q:stu[i].ff)cout<<" "<<q; cout<<endl;}return 0;
}

L2-040 哲哲打游戏 (25 分)

//注意 int cur=1 和存档：ans[N];#include<bits/stdc++.h>
using namespace std;
#define N 100100
#define inf 0x3f3f3f3f
int n,m,k,d;
int x,y,z;
vector<int>v[N];int main()
{cin>>n>>m;//剧情点从1标记for(int i=1;i<=n;i++){cin>>k;while(k--){cin>>x;v[i].push_back(x);}}int ans[N];//因为从剧情点1开始进行的游戏int cur=1;while(m--){cin>>x>>y;if(x==0){cur=v[cur][y-1];}else if(x==1){ans[y]=cur;cout<<cur<<endl;}else if(x==2){cur=ans[y];}}//最后要输出一下最终到达的地方cout<<cur<<endl;return 0;
}

No.3 PTA总结进行所属分类：

初始模板：

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {return 0;
}

小知识：

//1不是素数，2是素数
//push_back与pop_back均为容器vector操作函数
//求string的最后一个字符：此函数返回对字符串最后一个字符的直接引用。这只能用于非空字符串。
char ch=str.back()//
string a="abcd";
1.获取字符串最后一个字符
auto b=a.back(); //结果为 b='d';2.修改字符串最后一个字符
a.back()='!'; //结果为 a="abc!";3.获取字符串第一个字符
auto b=a.front(); //结果为 b='a';4.修改字符串第一个字符
a.front()='!'; //结果为 a="!bcd";//substr是C++语言函数，主要功能是复制子字符串，要求从指定位置开始，并具有指定的长度。如果没有指定长度则子字符串将延续到源字符串//的结尾。
string s=str.substr(i,几个);//字符串的倒置：getline(cin, str);reverse(str.begin(), str.end());cout << str << endl;//数字转字符串：
string str=to_string(int x);
cin>>x;
string s=to_string(x);

输入格式规范：

用getchar()吃回车当第一行是n
第二行是getline	getline会自动吃回车。所以第三行的getline两个相隔不需要吃回车,但第一行与第二行要吃回车当第一行是n时，
第二行读取字符用c=getchar()的时候当用cin>>ch的时候不需要进行吃回车，会自动过滤空格；好像

输出格式规范

//每5个数字占一行，每个数字占5个字符宽度，向右对齐。for(int i=a;i<=b;i++){cout<<setfill(' ')<<setiosflags(ios::right)<<setw(5);cout<<i;sum=sum+i;cou++;if(cou%5==0){cout<<endl;}}if(cou%5!=0)cout<<endl;cout<<"Sum = "<<sum<<endl;//

普通题模板：

L1-003 个位数统计 (15 分)

//int num=str[i]-'0' 的好处。
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {getline(cin,str);int book[15]={0};for( auto i:str){int num=i-'0';book[num]++;}for(int i=0;i<15;i++){if(book[i]>0)cout<<i<<":"<<book[i]<<endl;}return 0;
}

L1-011 A-B (20 分)

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {string s1,s2;getline(cin,s1);getline(cin,s2);map<char,int>mp;for(auto i:s2)mp[i]=1;for(auto i:s1){if(mp[i]!=1)cout<<i;}return 0;
}

L1-015 跟奥巴马一起画方块 (15 分)

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>n>>ch;int h=(n%2==0)?n/2:n/2+1;for(int i=1;i<=h;i++){for(int j=1;j<=n;j++)cout<<ch;cout<<endl;}return 0;
}

L1-020 帅到没朋友 (20 分)

 注意补齐0
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>n;int book[N]={0};while(n--){cin>>k;if(k==1){cin>>x;}else{while(k--){cin>>x;book[x]++;}}}cin>>k;int ok=0;int book2[N]={0};int flag=0;while(k--){cin>>x;if(book[x]==0 &&book2[x]==0){if(ok==0){printf("%05d",x);ok=1;}else{printf(" %05d",x);}flag=1;book2[x]=1;}}if(flag==0)cout<<"No one is handsome"<<endl;return 0;
}

L1-034 点赞 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int book[N]={0};
int main() {cin>>n;while(n--){cin>>k;while(k--){cin>>x;book[x]++;}}int maxx=0;for(int i=0;i<1001;i++){maxx=max(maxx,book[i]);}for(int i=1001;i>=0;i--){if(book[i]==maxx){cout<<i<<" "<<book[i]<<endl;break;}}return 0;
}

L1-062 幸运彩票 (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>n;while(n--){cin>>str;int num1=str[0]-'0'+str[1]-'0'+str[2]-'0';int num2=str[3]-'0'+str[4]-'0'+str[5]-'0';if(num1==num2){cout<<"You are lucky!"<<endl;}else{cout<<"Wish you good luck."<<endl;}}return 0;
}

L1-069 胎压监测 (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];int main() {int maxx=0;int num[10]={0};for(int i=1;i<=4;i++){cin>>num[i];maxx=max(maxx,num[i]);}cin>>m>>k;vector<int>ans;for(int i=1;i<=4;i++){if(abs(num[i]-maxx)>k || num[i]<m ){ans.push_back(i);}}if(ans.size()==0){cout<<"Normal"<<endl;}else if(ans.size()==1){cout<<"Warning: please check #"<<ans[0]<<"!"<<endl;}else if(ans.size()>1){cout<<"Warning: please check all the tires!"<<endl;}return 0;
}

L1-077 大笨钟的心情 (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];int main() {int num[25]={0};for(int i=0;i<=23;i++){cin>>num[i];}while(cin>>x){if(x<0 || x>23){break;}if(num[x]>50){cout<<num[x]<<" Yes"<<endl;}else{cout<<num[x]<<" No"<<endl;}}return 0;
}

L1-079 天梯赛的善良 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];
map<int , int >mp;
int main() {cin>>n;vector<int>ans;for(int i=0;i<n;i++){cin>>x;mp[x]++;ans.push_back(x);}sort(ans.begin(),ans.end());cout<<ans[0]<<" "<<mp[ans[0]]<<endl;cout<<ans[ans.size()-1]<<" "<<mp[ans[ans.size()-1]]<<endl;return 0;
}

L2-005 集合相似度 (25 分)

//        set<int>::iterator it;for(it=sc[x].begin();it!=sc[x].end();it++){if(sc[y].find(*it)!=sc[y].end())num3++;}
//#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100000
int n,m,s,d,k;
int x,y,z;set<int>sc[55];
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>m;for(int j=0;j<m;j++){cin>>x;sc[i].insert(x);}}cin>>k;while(k--){int a,b;cin>>a>>b;int sum1=sc[a].size();int sum2=sc[b].size();int sum3=0;set<int>::iterator it;for(it=sc[a].begin(); it!=sc[a].end(); it++){//共有的if(sc[b].find(*it)!=sc[b].end())sum3++;}printf("%.2lf",1.0*sum3/(sum1+sum2-sum3)*100);cout<<"%"<<endl;}return 0;
}

L2-014 列车调度 (25 分)

//对于N要进行适应性的更改，对于字段错误
//    set<int>::iterator it=sc.lower_bound(x);
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {set<int>sc;cin>>n;for(int i=0;i<n;i++){cin>>x;set<int>::iterator it=sc.lower_bound(x);if(it==sc.end()){sc.insert(x);}else{sc.erase(it);sc.insert(x);}}cout<<sc.size()<<endl;return 0;
}

L2-017 人以群分 (25 分)

升序排序然后直接算差值就行，如果个数奇数一定是外向的比内向的多一个。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
int num[N]={0};
int main() {cin>>n;for(int i=0;i<n;i++){cin>>num[i];}sort(num,num+n);int peo=0;int ple=0;if(n%2==0){peo=n/2;ple=peo;}else{peo=n/2;ple=n-peo;}int sum1=0;int sum2=0;for(int i=0;i<peo;i++){sum1=sum1+num[i];}for(int i=peo;i<n;i++){sum2=sum2+num[i];}cout<<"Outgoing #: "<<ple<<endl;cout<<"Introverted #: "<<peo<<endl;cout<<"Diff = "<<sum2-sum1<<endl;return 0;
}

L2-040 哲哲打游戏 (25 分)

//注意 int cur=1 和存档：ans[N];
//以及最后要输出一下最后那个景点cur
#include<bits/stdc++.h>
using namespace std;
#define N 100100
#define inf 0x3f3f3f3f
int n,m,k,d;
int x,y,z;
vector<int>v[N];int main()
{cin>>n>>m;//剧情点从1标记for(int i=1;i<=n;i++){cin>>k;while(k--){cin>>x;v[i].push_back(x);}}int ans[N];//因为从剧情点1开始进行的游戏int cur=1;while(m--){cin>>x>>y;if(x==0){cur=v[cur][y-1];}else if(x==1){ans[y]=cur;cout<<cur<<endl;}else if(x==2){cur=ans[y];}}//最后要输出一下最终到达的地方cout<<cur<<endl;return 0;
}

字符矩阵模拟模板：

L1-002 打印沙漏 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
vector<int>v[N];int main() {cin>>n>>ch;//h 为上面的行数==下面的行数。//累加规律：1行有1个，2行有4个，3行有9个。即几行和为几平方。//该行规律：1行有1个，2行有3个，3行有5个。2*i-1；int shang = (n+1)/2;int h=sqrt(shang);for(int i=h;i>=1;i--){for(int j=1;j<=h-i;j++)cout<<" ";for(int j=1;j<=2*i-1;j++)cout<<ch;cout<<endl;}for(int i=2;i<=h;i++){for(int j=1;j<=h-i;j++)cout<<" ";for(int j=1;j<=2*i-1;j++)cout<<ch;cout<<endl;}cout<<n-(2*h*h-1)<<endl;return 0;
}

L1-039 古风排版 (20 分)

//    char a[N][N]; 注意是 char#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>n;getchar();getline(cin,str);int len=str.size();int lie=len%n==0?len/n:len/n+1;int a=0;char cc[105][105];for(int i=lie;i>=1;i--){for(int j=1;j<=n;j++){//因为a比需要的大一//str[0]开始的，所以【a】最大为length-1；即当【】内最大时，a++之后 a==lengthif(a<len){cc[j][i]=str[a++];}else{cc[j][i]=' ';}}}for(int i=1;i<=n;i++){for(int j=1;j<=lie;j++){cout<<cc[i][j];}cout<<endl;}return 0;
}

L1-048 矩阵A乘以B (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1001
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {int ah,al,bh,bl;int a[N][N],b[N][N];cin>>ah>>al;for(int i=1;i<=ah;i++){for(int j=1;j<=al;j++){cin>>a[i][j];}}cin>>bh>>bl;for(int i=1;i<=bh;i++){for(int j=1;j<=bl;j++){cin>>b[i][j];}}if(al!=bh){cout<<"Error: "<<al<<" != "<<bh<<endl;}else{cout<<ah<<" "<<bl<<endl;for(int i=1;i<=ah;i++){for(int j=1;j<=bl;j++){int sum=0;for(int k=1;k<=al;k++){sum=sum+a[i][k]*b[k][j];}if(j==1)cout<<sum;else cout<<" "<<sum;}cout<<endl;}}return 0;
}

L1-049 天梯赛座位分配 (20 分)

//记住N为大于100的但是不能太大
//记住那个 j<=num[i]
#include<bits/stdc++.h>
using namespace std;
int num[111];//记录每个学校的队伍数量
int pos[111][11][11];//i学校j队伍中k队员的位置
int maxx,pre;//maxx记录学校中队伍数量的最大值，pre记录上一个被编号的学校
int x;//记录编号
int main()
{int n;//学校数量cin>>n;for(int i=1; i<=n; i++){cin>>num[i];//每个学校的队伍数量maxx=max(maxx,num[i]);//记录最大队伍数量}for(int j=1; j<=maxx; j++) //以最大队伍数量为上界，为了让每个人都能在这个循环里添加上位置{for(int k=1; k<=10; k++)//循环每个队员{for(int i=1; i<=n; i++)//遍历学校开始编号{if(j<=num[i])//如果当前的队伍数量j小于等于当前学校的队伍数量，说明可以编号，否则不可以，因为该学校里没有队员可以被编号了，都编完号了{if(pre==i)//相邻学校的两个队员必须隔位就坐x+=2;elsex++;//不是同一个学校的，连续编排pos[i][j][k]=x;//特别有意思的循环，i学校j队伍中k队员的编号就是xpre=i;//记录上一个被编号的学校}}}}for(int i=1;i<=n;i++){cout<<"#"<<i<<endl;for(int j=1;j<=num[i];j++){for(int k=1;k<=10;k++){if(k<=9)cout<<pos[i][j][k]<<" ";elsecout<<pos[i][j][k]<<endl;}}}return 0;}

L1-054 福到了 (15 分)

//这道题主要考察吃回车。。。
//在使用c=getchar()的时候要特别注意。。。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 105
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {char a[N][N],b[N][N];cin>>ch>>n;char c;getchar();for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){c=getchar();a[i][j]=c;}getchar();}int flag=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){b[i][j]=a[n-i+1][n-j+1];if(a[i][j]!=b[i][j]){flag=1;}}}if(flag==0){cout<<"bu yong dao le"<<endl;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(b[i][j]=='@'){cout<<ch;}else{cout<<b[i][j];}}cout<<endl;}return 0;
}

L1-072 刮刮彩票 (20 分)

#include<iostream>
using namespace std;
int x,y,k;
int main(){int a[4][4],value[25]={0,0,0,0,0,0,10000,36,720,360,80,252,108,72,54,180,72,180,119,36,306,1080,144,1800,3600};int ix=0,iy=0;int book[15]={0};for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){cin>>x;if(x==0){ix=i;iy=j;}else{a[i][j]=x;book[x]=1;}}}for(int i=1;i<=9;i++){if(book[i]==0){a[ix][iy]=i;}}for(int i=0;i<3;i++){cin>>x>>y;cout<<a[x][y]<<endl;}cin>>k;int sum=0;if(k<=3){sum=a[k][1]+a[k][2]+a[k][3];cout<<value[sum]<<endl;}else if(k<=6){sum=a[1][k-3]+a[2][k-3]+a[3][k-3];cout<<value[sum]<<endl;}else if(k==7){sum=a[1][1]+a[2][2]+a[3][3];cout<<value[sum]<<endl;}else if(k==8){sum=a[3][1]+a[2][2]+a[1][3];cout<<value[sum]<<endl;}return 0;
} 

L2-028 秀恩爱分得快 (25 分)

思路：用一个二维数组g来存储在同一张照片的不同人之间的亲密度，maxn来记录和A和异性的最大亲密度和B和异性的最大亲密度，因为题目要求按他们编号的绝对值递增输出，所以我们采用set分别存储男性和女性，最后遍历输出就行了//注意一定要将cin>>str的转化为abs(stoi(str));
注：stoi是将string类型转换成int型//1010 1000 1001
//这个1010会超时，1001不会超时。。#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>using namespace std;
#define N 1010
int n,m,k;
int x,y,z;
char ch;
string str;
int main() {cin>>n>>m;double g[N][N]={0.0};double maxx[N]={0};set<int>A,B;for(int i=0;i<m;i++){cin>>k;vector<int>a;vector<int>b;for(int j=0;j<k;j++){cin>>str;int num=abs(stoi(str));if(str[0]=='-'){a.push_back(num);A.insert(num);}else{b.push_back(num);B.insert(num);}}for(auto p:a){for(auto q:b){g[q][p]=g[p][q]+=1.0/k;maxx[p]=max(maxx[p],g[p][q]);maxx[q]=max(maxx[q],g[p][q]);}}}string s1,s2;cin>>s1>>s2;x=abs(stoi(s1));y=abs(stoi(s2));if(maxx[x]==g[x][y]&&maxx[y]==g[x][y]){cout<<s1<<" "<<s2<<endl;return 0;}//下面对于s1;if(s1[0]=='-'){for(auto i:B){if(maxx[x]==g[x][i]){cout<<s1<<" "<<i<<endl;}}}else{for(auto i:A){if(maxx[x]==g[x][i]){cout<<s1<<" -"<<i<<endl;}}}//下面对于s2；if(s2[0]=='-'){for(auto i:B){if(maxx[y]==g[y][i]){cout<<s2<<" "<<i<<endl;}}}else{for(auto i:A){if(maxx[y]==g[y][i]){cout<<s2<<" -"<<i<<endl;}}}return 0;
}

字符串捉个搜索模拟模板：

L1-016 查验身份证 (15 分)

 注意权重和duiying 都要自己打上去
// for(int j=0;j<str.size()-1;j++){  十八位的，要进行前十七位的遍历#include <bits/stdc++.h>
using namespace std;
#define N 100100
#define inf 0x3f3f3f3f
int n,m,k,s,d;
int x,y,z;
string str;
char ch;
vector<int>v[N];
int value[17]={7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
char dui[11]={'1','0','X','9','8','7','6','5','4','3','2'};
int main()
{cin>>n;int flag2=0;for(int i=0;i<n;i++){cin>>str;int sum=0;int flag=0;for(int j=0;j<str.size()-1;j++){if(str[j]<'0' || str[j]>'9'){flag=1;break;}int num=str[j]-'0';sum+=num*value[j];}if(flag==1||dui[sum%11]!=str[17]){cout<<str<<endl;flag2=1;}}if(flag2==0)cout<<"All passed"<<endl;return 0;
}

L1-017 到底有多二 (15 分)

//记得增加一倍是*2 ， 增加0.5倍是*1.5
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {int geshu,weishu;double beishu=1.0;cin>>str;if(str[0]=='-')beishu=beishu*1.5;if(str[0]=='-')weishu=str.size()-1;else weishu=str.size();if(str[str.size()-1]%2==0)beishu=beishu*2.0;for(auto i:str){if(i=='2')geshu++;}printf("%.2f",geshu*1.0/weishu*1.0*beishu*100);cout<<"%"<<endl;return 0;
}

L1-025 正整数A+B (15 分)

//这里注意点：判断是否为？  1：各个位置为0~9数字  2：且整数在1~1000#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int isZ(string s){for(auto i:s){if(i<'0' || i>'9')return 0;}//下面这个判断在数字范围i内的必须在判断是否为数字之后，只有在是//数字的情况下才能使用stoiif(stoi(s)<1 || stoi(s)>1000)return 0;return 1;
}
int main() {string s1,s2;cin>>s1;getchar();getline(cin,s2);if(isZ(s1)==1&&isZ(s2)==1){cout<<s1<<" + "<<s2<<" = "<<stoi(s1)+stoi(s2)<<endl;}else if(isZ(s1)==0 && isZ(s2)==1){cout<<"? + "<<s2<<" = ?"<<endl;}else if(isZ(s1)==1&&isZ(s2)==0){cout<<s1<<" + ? = ?"<<endl;}else if(isZ(s1)==0&&isZ(s2)==0){cout<<"? + ? = ?"<<endl;}return 0;
}

L1-027 出租 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>str;int book[15]={0};for(auto i:str){int num=i-'0';book[num]++;}vector<int>ans;for(int i=9;i>=0;i--){if(book[i]>0)ans.push_back(i);}cout<<"int[] arr = new int[]{";for(auto nn:ans){if(nn==ans[0])cout<<nn;else cout<<","<<nn;}cout<<"};"<<endl;cout<<"int[] index = new int[]{";for(int i=0;i<str.size();i++){int num=str[i]-'0';for(int j=0;j<ans.size();j++){if(ans[j]==num){if(i==0)cout<<j;else cout<<","<<j;break;}}}cout<<"};"<<endl;return 0;
}

L1-032 Left-pad (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>n>>ch;getchar();getline(cin,str);int len=str.size();if(n==len)cout<<str<<endl;else if(len <n){for(int i=0;i<n-len;i++)cout<<ch;cout<<str<<endl;}else if(len>n){for(int i=len-n;i<len;i++)cout<<str[i];}return 0;
}

L1-058 6翻了 (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {int count=0;getline(cin,str);//需要注意的是，使用getline函数输入会以换行为结束，所以在循环时 i <= str.length()for(int i=0;i<=str.size();i++){if(str[i]=='6'){count++;continue;}else{//走到这里count表示已经累积了多少个6if(count>9){cout<<"27";}else if(count>3){cout<<"9";}else{while(count--){cout<<"6";}}count=0;cout<<str[i];}}return 0;
}

L1-059 敲笨钟 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>n;getchar();while(n--){int flag1=0,flag2=0;getline(cin,str);int len=str.size();vector<int>ans;for(int i=0;i<len;i++){if(str[i]==' '){ans.push_back(i);}if(str[i]==',' &&str[i-1]=='g' && str[i-2]=='n' && str[i-3]=='o'){flag1=1;}if(str[i]=='.' &&str[i-1]=='g' && str[i-2]=='n' && str[i-3]=='o'){flag2=1;}}if(flag1 && flag2){m=ans[ans.size()-3];for(int i=0;i<=m;i++){cout<<str[i];}cout<<"qiao ben zhong."<<endl;}else{cout<<"Skipped"<<endl;}}return 0;
}

L1-064 估值一亿的AI核心代码 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int pan1(string s,int x){if(s[x]>='a'&&s[x]<='z')return 1;else if(s[x]>='A' &&s[x]<='Z')return 2;else if(s[x]>='0'&&s[x]<='9')return 3;else if(s[x]==' ')return 4;else return 5;// 除空格以外的标点符号
}
//判断 独立性
int pan2(string s, int x ,int y){if((x<0 ||s[x]==' '||pan1(s,x)==5)&&(y>=s.size() || s[y]==' ' || pan1(s,y)==5)){return 1;}return 0;
}
int main() {cin>>n;getchar();while(n--){getline(cin,str);cout<<str<<endl<<"AI: ";string b="";//b是修改后的字符串 int l=0,r=str.size()-1;while(str[l]==' ')l++; // 去掉全部首空格while(str[r]==' ')r--;// 去掉全部尾空格 for(int i=l;i<=r;i++){if(str[i]==' ' &&(str[i+1]==' ' || pan1(str,i+1)==5)){ // 去掉多余空格（单词间的空格、标点符号前的空格） continue;}else if(str[i]=='?'){// ?变！b+='!';}else if(str[i]!='I'&&pan1(str,i)==2){ // 大写变小写 b+=str[i]+32;}else{b+=str[i]; // 其他字符}}for(int i=0;i<b.size();i++){if(b[i]=='I'&&pan2(b,i-1,i+1)){cout<<"you";}else if(b.substr(i,2)=="me"&&pan2(b,i-1,i+2)){// b.substr(i,2)代表截取b字符串从i下标开始的两个字符 cout<<"you";i=i+1;}else if(b.substr(i,7)=="can you"&&pan2(b,i-1,i+7)){cout<<"I can";i+=6;}else if(b.substr(i,9)=="could you"&&pan2(b,i-1,i+9)){cout<<"I could";i+=8;}else{cout<<b[i];}}cout<<endl;}return 0;
}

L2-008 最长对称子串 (25 分)

//记住 x=max(x,j-i+1);
//                while(l<=r&&str[l++]==str[r--]){
#include<iostream>
using namespace std;
int main(){string s;getline(cin,s);int x=1;for(int i=0;i<s.size();i++){for(int j=s.size()-1;j>=i;j--){if(s[i]==s[j]){int l=i,r=j;while(l<=r&&s[l++]==s[r--]){if(l>r)	//当符合while条件并且l>r时说明此时内部全部是对称的走完了。x=max(x,j-i+1);}}}}cout<<x<<endl;return 0;
}

辗转除法相除转换模拟模板：

L1-006 连续因子 (20 分)

    //只是找其中部分因子是连续的        //这里只有count在这循环为0
//注意要注意那个 输出为1，即没有连续因子的状况！！！！！
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {int start=0,maxx=0,count=0;cin>>n;for(int i=2;i<=sqrt(n);i++){int cur=n;count=0;int j=i;while(cur%j==0){count++;cur=cur/j;j++;}if(count>maxx){maxx=count;start=i;}}if(maxx==0){cout<<"1"<<endl;cout<<n<<endl;}else{cout<<maxx<<endl;for(int i=0;i<maxx;i++){if(i==0)cout<<start+i;else cout<<"*"<<start+i;}}return 0;
}

L1-009 N个数求和 (20 分)

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int gcd(int x,int y){if(y==0)return x;return gcd(y,x%y);
}
int main() {cin>>n;int fenzi,fenmu;cin>>fenzi>>ch>>fenmu;for(int i=1;i<n;i++){cin>>x>>ch>>y;fenzi=fenzi*y+fenmu*x;fenmu=fenmu*y;int yue=gcd(fenzi,fenmu);fenzi=fenzi/yue;fenmu=fenmu/yue;}if(fenzi%fenmu==0){cout<<fenzi/fenmu<<endl;}else if(fenzi<fenmu){cout<<fenzi<<"/"<<fenmu<<endl;}else if(fenzi>fenmu){cout<<fenzi/fenmu<<" "<<fenzi%fenmu<<"/"<<fenmu<<endl;}return 0;
}

L1-033 出生年 (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int shu(int x){int num1=x%10;int num2=(x/10)%10;int num3=(x/100)%10;int num4=(x/1000)%10;int book[15]={0};book[num1]=book[num2]=book[num3]=book[num4]=1;int cnt=0;for(int i=0;i<15;i++){if(book[i]==1)cnt++;}return cnt;
}
int main() {cin>>x>>y;for(int i=0;; i++){if(shu(x+i)==y){cout<<i<<" ";printf("%04d",x+i);break;}}return 0;
}

L1-046 整除光棍 (20 分)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZKqZE0vw-1679672875237)(C:\Users\86177\AppData\Roaming\Typora\typora-user-images\image-20220319223103847.png)]

//注意：    while(ans<n){  不能是：while(ans<=n){}#include<bits/stdc++.h>
using namespace std;int main()
{int n,ans=0,cnt=0;cin>>n;while(ans<n){ans=ans*10+1;cnt++; }//跳出循环后导致 ans>=n;即可以进行除法了while(1){cout<<ans/n;ans=ans%n;if(ans==0){break;}//下面这个是进行时ans=ans*10+1;cnt++;}cout<<" "<<cnt;return 0;
} 

L1-050 倒数第N个字符串 (15 分)

//26的L次方就是当取L时，L个字母组成的所有的个数，然后减去N，得到的数，就是我们要输出的数对应的十进制的位置，接着再转换为26进制，就变成我们想要的字符串了
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {int l;cin>>l>>n;int cur=pow(26,l)-n;vector<int>ans;while(l--){//转换L次，就可以从10进制转换为16进制，其他进制也是这个德行 ans.push_back(cur%26);//这里的转换都是倒着存放的 cur=cur/26;}//接着倒序输出，就是正回来了for(int i=ans.size()-1;i>=0;i--){cout<<(char)('a'+ans[i]);}return 0;
}

L1-080 乘法口诀数列 (20 分)

//用for可以标记次数。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];
vector<int>ans;
int main() {cin>>x>>y>>k;ans.push_back(x);ans.push_back(y);for(int i=0;i<=k;i++){int a=ans[i];int b=ans[i+1];if(a*b>=10){ans.push_back(a*b/10);ans.push_back(a*b%10);}else{ans.push_back(a*b);}}for(int i=0;i<k;i++){if(i==0){cout<<ans[i];}else{cout<<" "<<ans[i];}}return 0;
}

L2-018 多项式A除以B (25 分)

定义两个数组：a,b，分别表示多项式A和多项式B；两个数组的下标表示指数，数组值代表系数；所以要定义double类型并求出两个多项式中最大指数index1和index2；在进行每一次除法之后，商的最高次幂是(max1-max2)，最高次幂的系数是（a[index1]/b[index2]）；然后继续循环，并更新a，直至被除数的最高次幂小于除数；#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
void pout(double arr[],int x)
{int num=0;for(int i=0;i<=x;i++){//因为保留一位小数，所以+0.05与0.1比较if(abs(arr[i])+0.05>=0.1)num++;}cout<<num;if(num==0){cout<<" 0 0.0";}else{for(int i=x;i>=0;i--){if(abs(arr[i])+0.05>=0.1){cout<<" "<<i;printf(" %.1f",arr[i]);}}}
}
int main()
{double a[N],b[N],c[N];int index1=-1,index2=-1;//两个多项式的最大指数 cin>>n;for(int i=1;i<=n;i++){cin>>x;cin>>a[x];if(x>index1)index1=x;}cin>>m;for(int i=1;i<=m;i++){cin>>x;cin>>b[x];if(x>index2)index2=x;}int temp=index1-index2;//商的最大指数while(index1>=index2)//中余数的阶数必须小于除数的阶数。{double q=a[index1]/b[index2];//cout<<index1<<" "<<index2<<" "<<q<<endl;c[index1-index2]=q;for(int i=index1,j=index2;i>=0&&j>=0;i--,j--){a[i]-=b[j]*q;}while(a[index1]==0)index1--;//系数为0 } pout(c,temp);cout<<endl;pout(a,index1);return 0;
}

L2-029 特立独行的幸福 (25 分)

思路有点暴力，一开始这么想觉得可能会超时，幸好比赛的时候过了。1、for循环对区间的每一个数进行判断是否是幸福数2、迭代：对这个数一直求各位的平方和，直到平方和为1，或者平方和重复出现，平且标记出现过的平方和（用于排除非独立的幸福数）3、如果是因为平方和为1而结束循环，说明这个数是一个幸福数，那么可以对它进行存储。4、输出时注意，需要排除非独立的幸福数（本身出现在另一个数的求平方和过程中，就不是独立的幸福数（前面已标记））#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int isP(int x){for(int i=2;i<=sqrt(x);i++){if(x%i==0)return 1;}return 2;
}
int book[N]={0};
int main() {int l,r;cin>>l>>r;map<int,int>mp;for(int i=l;i<=r;i++){vector<int>ans;int t=i;while(t!=1){int sum=0;while(t){sum+=(t%10)*(t%10);t=t/10;}t=sum;if(find(ans.begin(),ans.end(),t)==ans.end()){ans.push_back(t);//第一个本身并不会被标记。只会标记其他过程中的。。book[t]=1;//标记出现过的数}else{break;}}//判断   //判断是由于异常跳出的还是正常出来的；；if(t==1){mp[i]=ans.size();//存储辛福数}}int flag=0;for(int i=l;i<=r;i++){if(book[i]==0 &&mp[i]>0){cout<<i<<" "<<mp[i]*isP(i)<<endl;flag=1;}}if(flag==0){cout<<"SAD"<<endl;}return 0;
}

记录次数数据循环模拟模板：

L1-019 谁先倒 (15 分)

 注意通赢的时候都不喝
//注意第二个输出的是已经喝了多少了
#include<bits/stdc++.h>
using namespace std;int main(){int n,m,k;int amax,bmax,a=0,b=0;int ahua,ahan,bhua,bhan;cin>>amax>>bmax;cin>>n;while(n--){cin>>ahan>>ahua>>bhan>>bhua;if(ahua==ahan+bhan){a++;}if(bhua==ahan+bhan){b++;}if(ahua==ahan+bhan && bhua==ahan+bhan){a--;b--;}if(amax-a<0){cout<<"A"<<endl;cout<<b<<endl;break;}if(bmax-b<0){cout<<"B"<<endl;cout<<a<<endl;break;}}return 0;
}

L1-023 输出GPLT (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
vector<int>v[N];int main() {string str;cin>>str;int pnum=0,gnum=0,lnum=0,tnum=0;for(auto i:str){if(i=='p' || i=='P')pnum++;if(i=='g' || i=='G')gnum++;if(i=='l' ||i=='L')lnum++;if(i=='t' || i=='T')tnum++;}int maxx=max({lnum,tnum,gnum,pnum});for(int i=1;i<=maxx;i++){if(gnum>0){cout<<"G";gnum--;}if(pnum>0){cout<<"P";pnum--;}if(lnum>0){cout<<"L";lnum--;}if(tnum>0){cout<<"T";tnum--;}}return 0;
}

L1-035 情人节 (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {vector<string>ans;for(int i=1; ;i++){cin>>str;if(str=="."){break;}ans.push_back(str);}int num=ans.size();if(num<2){cout<<"Momo... No one is for you ..."<<endl;}else if(num<14){cout<<ans[1]<<" is the only one for you..."<<endl;}else{cout<<ans[1]<<" and "<<ans[13]<<" are inviting you to dinner..."<<endl;}return 0;
}

L1-044 稳赢 (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>k;for(int i=1; ;i++){cin>>str;if(str=="End"){break;}if(i%(k+1)==0){cout<<str<<endl;continue;}else{if(str=="ChuiZi"){cout<<"Bu"<<endl;}else if(str=="Bu"){cout<<"JianDao"<<endl;}else{cout<<"ChuiZi"<<endl;}}}return 0;
}

L1-070 吃火锅 (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];int main() {string str;vector<int>ans;int zongcount=0;for(int i=1; ; i++){getline(cin,str);if(str=="."){break;}zongcount++;if(str.find("chi1 huo3 guo1")!=string::npos){ans.push_back(zongcount);}}cout<<zongcount<<endl;if(ans.size()){cout<<ans[0]<<" "<<ans.size()<<endl;}else{cout<<"-_-#"<<endl;}return 0;
}

L1-078 吉老师的回归 (15 分)

// 这个注意点是那个getchar();;#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];int main() {cin>>n>>k;int cnt=0;//这个注意要进行吃回车。。getchar();for(int i=1;i<=n;i++){string str;getline(cin,str);int ix=str.find("qiandao");int iy=str.find("easy");if(ix==string::npos && iy==string::npos ){cnt++;}//cnt表示这道题在吉老师的面前是第几道题。//老师已经做完了k道题，，所以就是，在老师面前的k道题之前都不需要。if(i==n && cnt<=k){cout<<"Wo AK le"<<endl;    }if(cnt>k){cout<<str<<endl;break;}}return 0;
}

结构体设计固定时间间隔模拟模板：

L1-043 阅览室 (20 分)

//由于线路偶尔会有故障，可能出现不完整的纪录，即只有S没有E，或者只有E没有S的纪录，系统应能自动忽略这种无效纪录。另外，题目保证书号是书的唯一标识，同一本书在任何时间区间内只可能被一位读者借阅。#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1001
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{int vis;int time;
}book[N];
int main() {cin>>n;int id;char s;while(n--){int sum=0,sumtime=0;while(cin>>id>>s>>x>>ch>>y &&id!=0){int t=x*60+y;if(s=='S'){//if(!book[id].vis)//连续两次出现可能是中间一个E未记录到，所以直接替换初始时间，就因为这个细节第二个样例过不了//只要出现S，就直接换上去。book[id].vis=1;book[id].time=t;}else{if(book[id].vis==1){sumtime=sumtime+t-book[id].time;book[id].vis=0;sum++;}}}if(sum==0){cout<<"0 0"<<endl;}else{//cnt=0时直接输出，不能相除，double自动进位，，因为是精确到个位，不是只要整数部分cout<<sum<<" "<<(int)(sumtime*1.0/sum*1.0+0.5)<<endl;}}return 0;
}

结构体查询模板：

L1-005 考试座位号 (15 分)

//结构体更方便点，然后再循环
//由 16 位数字组成要用到long 
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1001
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{string name;int a,b;
}stu[N];// 尝试使用map<string,int>mp;
int main() {cin>>n;for(int i=0;i<n;i++){cin>>stu[i].name>>stu[i].a>>stu[i].b;}cin>>k;while(k--){cin>>x;for(int i=0;i<n;i++){if(stu[i].a==x)cout<<stu[i].name<<" "<<stu[i].b<<endl;}}return 0;
}

L1-030 一帮一 (15 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{int sex;string name;int flag;
}stu[N];int main() {cin>>n;for(int i=0;i<n;i++){cin>>stu[i].sex>>stu[i].name;stu[i].flag=0;}for(int i=0;i<n;i++){if(stu[i].flag==0){stu[i].flag=1;cout<<stu[i].name<<" ";for(int j=n-1;j>=0;j--){if(stu[j].flag==0 && stu[j].sex!=stu[i].sex){cout<<stu[j].name<<endl;stu[j].flag=1;break;}}}}return 0;
}

L1-056 猜数字 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{string name;int num;
}stu[N];int main() {cin>>n;double sum=0;for(int i=0;i<n;i++){cin>>stu[i].name>>stu[i].num;sum=sum+stu[i].num;}int avenum=sum/n/2;cout<<avenum<<" ";int minn=inf;vector<int>ans;for(int i=0;i<n;i++){int numx=abs(avenum-stu[i].num);if(numx<minn){minn=numx;ans.push_back(i);}}cout<<stu[ ans[ans.size()-1]].name<<endl;return 0;
}

L2-019 悄悄关注 (25 分)

//        if(stu[i].num>sum && str.find(stu[i].name)==string::npos){#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{string name;int num;
}stu[N];
bool cmp(node a,node b){return a.name<b.name;
}
int main() {getline(cin,str);cin>>n;int sum=0;for(int i=0;i<n;i++){cin>>stu[i].name>>stu[i].num;sum=sum+stu[i].num;}int avesum=sum/n;sort(stu,stu+n,cmp);int flag=0;for(int i=0;i<n;i++){if(stu[i].num>avesum && str.find(stu[i].name)==string::npos){cout<<stu[i].name<<endl;flag=1;}}if(flag==0){cout<<"Bing Mei You"<<endl;}return 0;
}

结构体简单到复杂的排序模板：

L2-003 月饼 (25 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{double kucun,sale,avesale;
}moon[N];
bool cmp(node a, node b){return a.avesale>b.avesale;
}
int main() {cin>>n>>d;for(int i=0;i<n;i++){cin>>moon[i].kucun;}for(int i=0;i<n;i++){cin>>moon[i].sale;moon[i].avesale=moon[i].sale/moon[i].kucun;}sort(moon,moon+n,cmp);double sum=0.0;for(int i=0;i<n;i++){if(moon[i].kucun==d){sum+=moon[i].sale;break;}else if(moon[i].kucun<d){sum+=moon[i].sale;d=d-moon[i].kucun;}else if(moon[i].kucun>d){sum+=moon[i].avesale*d;break;}}printf("%.2f",sum);return 0;
}

L2-007 家庭房产 (25 分)

//注意N的取值要大于id 不只是4位数，要五位数
//如果出现cnt=0的时候就是忘了初始化Init了了了
#include <bits/stdc++.h>
using namespace std;
string str;
char ch;
#define N 10050
#define inf 0x3f3f3f3f
int n,m,k,s,d;
int x,y,z;
vector<int>v[N];
int f[N];
void Init(){for(int i=0;i<N;i++)f[i]=i;
}
int find(int x){if(x!=f[x]){f[x]=find(f[x]);}return f[x];
}
void merge(int x,int y){int fx=find(x);int fy=find(y);if(fx>fy){f[fx]=fy;}else{f[fy]=fx;}
}
struct me{int id;int num,area;
}member[N];
struct node{int flag;int id;int area , num;int peo;double avearea,avenum;
}fami[N];
bool cmp(node a, node b){if(a.avearea!=b.avearea){return a.avearea>b.avearea;}return a.id<b.id;}
int main()
{Init();cin>>n;set<int>people;int id,fa,ma,child;for(int i=0;i<n;i++){cin>>id>>fa>>ma>>k;member[i].id=id;people.insert(id);if(fa!=-1){people.insert(fa);merge(id,fa);}if(ma!=-1){people.insert(ma);merge(id,ma);}while(k--){cin>>child;people.insert(child);merge(id,child);}cin>>member[i].num>>member[i].area;}for(int j=0;j<n;j++){int idx=find(member[j].id);fami[idx].id=idx;fami[idx].flag=1;fami[idx].num+=member[j].num;fami[idx].area+=member[j].area;}int cnt=0;for(auto j:people){fami[find(j)].peo++;if(fami[j].flag==1)cnt++;}for(auto j:people){if(fami[j].flag==1){fami[j].avearea=fami[j].area*1.0/fami[j].peo;fami[j].avenum=fami[j].num*1.0/fami[j].peo;}}sort(fami,fami+N,cmp);cout<<cnt<<endl;for(int i=0;i<cnt;i++){printf("%04d %d %.3f %.3f\n",fami[i].id,fami[i].peo,fami[i].avenum,fami[i].avearea);}return 0;
}

L2-009 抢红包 (25 分)

//这里注意输入的value 是分，所以单位换算成元。printf(" %.2f\n",stu[i].value/100);#include<bits/stdc++.h>
using namespace std;
struct node
{int id;//人的编号;int num;//人抢到红包的个数;int value;//抢到红包的金额;	
}person[10000];
bool f(struct node a,struct node b)
{if(a.value!=b.value)//如果金额没有并列,则按照总金额从达到小的顺序递减输出; {return a.value>b.value;}else if(a.num != b.num)//金额有并列，则按照抢到红包的个数递减输出;{return a.num>b.num;	} else if(a.id != b.id)//如果金额和抢到红包的个数都有并列,则按照人的编号递增输出;{return a.id<b.id;	} 
}
int main()
{int n,k,p,i,j,sum=0,n1;//k指的是抢到红包的个数,n指的是抢红包人的编号,p指的是抢到红包的金额;cin>>n;for(i=1;i<=n;i++){person[i].id = i;//编号是i的人对应的id值是i; cin>>k;sum=0;for(j=1;j<=k;j++){cin>>n1>>p;
//			person[n1].id = n1;易错点，因为你不知道每个人都抢了红包,当有的人没有抢，那么对应的id值就变成了0; person[n1].value = person[n1].value + p;//记录抢到红包的金额; person[n1].num ++;//记录抢到红包的个数; sum = sum + p;//记录第i个人发红包的总金额; }person[i].value = person[i].value - sum;//更新编号为i的人剩余的总金额;} //因为人的编号n是正整数,故需要将person加1;//person+n+1包含的范围是person+n，不包括那个1;//[person+1,person+n+1)---->[1,n]sort(person+1,person+n+1,f);//自动调用f()函数,包含在头文件 ----> #include<algorithm>for(i=1;i<=n;i++){//抢到红包的进金额是按照分这个单位来计算的,故需要在输出是转换成元; printf("%d %.2lf\n",person[i].id,person[i].value*1.0/100);}
}

L2-015 互评成绩 (25 分)

//    for(int i=m-1;i>=0;i--){#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
bool cmp(double a,double b){return a>b;
}
int main() {vector<double> ans;cin>>n>>k>>m;for(int i=0;i<n;i++){double sum=0;int maxx=0,minn=inf;for(int j=0;j<k;j++){cin>>x;sum=sum+x;maxx=max(x,maxx);minn=min(x,minn);}sum=(sum-maxx-minn)/(k-2);ans.push_back(sum);}sort(ans.begin(),ans.end(),cmp);for(int i=m-1;i>=0;i--){if(i==m-1){printf("%.3f",ans[i]);}else{printf(" %.3f",ans[i]);}}return 0;
}

L2-021 点赞狂魔 (25 分)

//        stu[i].ave=k;#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 105
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{string name;int count;int num;
}stu[N];
bool cmp(node a,node b){if(a.num!=b.num){return a.num>b.num;}else if(a.count!=b.count){return a.count<b.count;}
}
int main() {cin>>n;set<int>sc;for(int i=0;i<n;i++){cin>>stu[i].name;cin>>k;stu[i].count=k;sc.clear();while(k--){cin>>x;sc.insert(x);}stu[i].num=sc.size();}sort(stu,stu+n,cmp);if(n==1){cout<<stu[0].name<<" - -"<<endl;}else if(n==2){cout<<stu[0].name<<" "<<stu[1].name<<" -"<<endl;}else if(n>=3){cout<<stu[0].name<<" "<<stu[1].name<<" "<<stu[2].name<<endl;}return 0;
}

L2-027 名人堂与代金券 (25 分)

// 这一题是一个简单的结构体自定义排序，但是要解决一个输出前k名(有可能并列)的问题我们的解决方法是在排序完成之后重新遍历一次list数组，如果当前的人的成绩等于前一个人，那么我们就让当前的人的排名等于前一个人，如果不等于，他的成绩就等于他的下标加一。当然,在此之前，我们把第一个人的排名等于一//    for(int i=0;rank[i]<=k&&i<n;i++){
#include<bits/stdc++.h>
#define N 10005
using namespace std;
#define inf 0x3f3f3f3fint n,m,k,g,d;
int x,y,z;
vector<int>v[N];
struct node{string name;int fen;
}stu[N];
bool cmp(node a, node b){if(a.fen==b.fen){return a.name<b.name;}return a.fen>b.fen;
}
int main() {cin>>n>>g>>k;//这个一定要赋予初值0int sum=0;for(int i=0;i<n;i++){cin>>stu[i].name>>stu[i].fen;if(stu[i].fen>=g){sum=sum+50;}else if(stu[i].fen>=60){sum=sum+20;}}sort(stu,stu+n,cmp);cout<<sum<<endl;int rank[N];rank[0]=1;for(int i=1;i<n;i++){if(stu[i].fen==stu[i-1].fen){rank[i]=rank[i-1];}else{rank[i]=i+1;}}//输出的时候要注意。。for(int i=0;rank[i]<=k &&i<n;i++){cout<<rank[i]<<" "<<stu[i].name<<" "<<stu[i].fen<<endl;}return 0;
}

map<vector< int >,int>mp;模板

L2-039 清点代码库 (25 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{vector<int>ff;int num;
}stu[N];
bool cmp(node a,node b){if(a.num!=b.num){return a.num>b.num;}return a.ff<b.ff;
}
int main() {map<vector<int> , int>mp;set<vector<int>>sc;cin>>n>>m;for(int i=1;i<=n;i++){vector<int>ans;for(int j=0;j<m;j++){cin>>x;ans.push_back(x);}mp[ans]++;sc.insert(ans);}int a=0;//结构体的创建以及赋值。。for(auto n:sc){stu[a].ff=n;stu[a].num=mp[n];a++;}sort(stu,stu+a,cmp);cout<<sc.size()<<endl;for(int i=0;i<a;i++){cout<<stu[i].num;for(auto q:stu[i].ff)cout<<" "<<q; cout<<endl;}return 0;
}

map<string,int>mp;模板

L2-030 冰岛人 (25 分)

// 但五代以内（不包括第五代）有公共祖先
//第一点：五代以内，不包括第五代：表示 cong i=1 to i<5 ;
//所以分两种情况：在男方的五代以内出现了女方的祖先，or 在女方的五代以内出现了男方的祖先。
//注意问题：因为k次调用函数check 所以在函数内定义vis，，//名用来区分人，姓用来区分男女和父类；；其他人则是在姓的后面加 m 表示男性、f 表示女性。
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{char sex;string father;
};
map<string , node>mp;
bool check(string a, string b){map<string , int>vis;for(int i=1; ; i++){vis[a]=i;a=mp[a].father;if(a.empty())break;}for(int i=1;  ;i++){//首先男方五代以内出现：if(vis[b]>0 && vis[b]<5)return false;//然后女方这边五代以内出现的话if(vis[b]>0 && i<5)return false;b=mp[b].father;if(b.empty())break;}return true;
}
int main() {cin>>n;string a,b;while(n--){cin>>a>>b;if(b.back()=='n'){mp[a].sex='m';mp[a].father=b.substr(0,b.size()-4);}else if(b.back()=='r'){mp[a].sex='f';mp[a].father=b.substr(0,b.size()-7);}else{mp[a].sex=b.back();}}string a1,b1;cin>>k;while(k--){cin>>a>>a1>>b>>b1;if(mp.find(a)==mp.end() || mp.find(b)==mp.end())cout<<"NA"<<endl;else if(mp[a].sex==mp[b].sex) cout<<"Whatever"<<endl;else {if(check(a,b))cout<<"Yes"<<endl;else cout<<"No"<<endl;}}return 0;
}

L2-034 口罩发放 (25 分)

//就算是flag=0 的也可以申请；；
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1005
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{string id,name;int hh;int mm;int time;int flag;int cixu;
}stu[N];
bool cmp(node a,node b){if(a.time!=b.time){return a.time<b.time;}return a.cixu<b.cixu;
}
int main() {int p,sum;map<string,int>day;cin>>d>>p;vector<node>vv;vector<node>ww;for(int i=1;i<=d;i++){vv.clear();cin>>k>>sum;for(int j=1;j<=k;j++){int flag=0;cin>>stu[j].name>>stu[j].id>>stu[j].flag>>stu[j].hh>>ch>>stu[j].mm;stu[j].cixu=j;stu[j].time=stu[j].hh*60+stu[j].mm;for(auto l:stu[j].id){if(l<'0'||l>'9')flag=1;}if(stu[j].id.size()==18 && flag==0){vv.push_back(stu[j]);ww.push_back(stu[j]);}           }sort(vv.begin(),vv.end(),cmp);for(auto n:vv){if(day[n.id]<=i &&sum>0){day[n.id]=i+p+1;cout<<n.name<<" "<<n.id<<endl;sum--;}}}map<string,int>vis;for(auto n:ww){if(n.flag==1 &&vis[n.id]==0){cout<<n.name<<" "<<n.id<<endl;vis[n.id]=1;}}return 0;
}

V[N]版本BFS搜索统计层数模板：

L2-026 小字辈 (25 分)

//    v[x].push_back(i);#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 101000
vector<int>v[N];
int level[N],vis[N]={0};
void bfs(int u)
{memset(vis,0,sizeof vis);memset(level,0,sizeof level);queue<int>q;q.push(u);while(!q.empty()){int x=q.front();vis[x]=1;q.pop();for(int i=0;i<v[x].size();i++){if(!vis[v[x][i]]){level[v[x][i]]=level[x]+1;	//level[x]表示x点在第几层次vis[v[x][i]]=1;q.push(v[x][i]);}}}}int main() {int n,m,k;int x,y,z;int start;cin>>n;if(n==1){cout<<"1"<<endl;cout<<"1"<<endl;return 0;}for(int i=1;i<=n;i++){cin>>x;if(x==-1){start=i;}else{v[x].push_back(i);}}bfs(start);int maxx=0;for(int i=1;i<=n;i++)if(maxx<level[i]) maxx=level[i];//保存最大层数cout<<maxx+1<<endl;int ok=1;for(int i=1;i<=n;i++)if(maxx==level[i]) {if(ok==1){cout<<i;ok=0;}else{cout<<" "<<i;}}//返回最大层数的最小编号，无相连的跳过return 0;
}

L2-031 深入虎穴 (25 分)

//从1开始且最后是输出编号
//
#include<bits/stdc++.h>
#define N 10003
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,d;
int x,y,z;
vector<int>v[N];
int root[N]={0};int level[N],vis[N];
void bfs(int index){memset(level,0,sizeof(level));memset(vis,0,sizeof(vis));queue<int>q;q.push(index);while(!q.empty()){int num=q.front();vis[num]=1;q.pop();for(int i=0;i<v[num].size();i++){if(vis[v[num][i]]==0 && level[v[num][i]]==0){level[v[num][i]]=level[num]+1;vis[v[num][i]]=1;q.push(v[num][i]);}}}
}
int main() {cin>>n;if(n==1){cout<<"1"<<endl;return 0;}for(int i=1;i<=n;i++){cin>>k;while(k--){cin>>x;root[x]=1;v[i].push_back(x);}}int start;for(int i=1;i<=n;i++){if(root[i]==0){start=i;}}bfs(start);int maxx=0;for(int i=1;i<=n;i++){if(level[i]>maxx){maxx=level[i];}}for(int i=1;i<=n;i++){if(level[i]==maxx){cout<<i<<endl;break;}}    return 0;
}

L3-008 喊山 (30 分)

#include<bits/stdc++.h>using namespace std;const int N=10010;
int n,m,k;int level[N],vis[N];
vector<int>v[N];int bfs(int u)
{memset(vis,0,sizeof vis);memset(level,0,sizeof level);queue<int>q;q.push(u);while(!q.empty()){int x=q.front();vis[x]=1;q.pop();for(int i=0;i<v[x].size();i++){if(!level[v[x][i]]&&!vis[v[x][i]]){level[v[x][i]]=level[x]+1;vis[v[x][i]]=1;q.push(v[x][i]);}}}int maxx=0;for(int i=1;i<=n;i++)if(maxx<level[i]) maxx=level[i];//保存最大层数for(int i=1;i<=n;i++)if(maxx&&maxx==level[i]) return i;//返回最大层数的最小编号，无相连的跳过return 0;
}
int main()
{cin>>n>>m>>k;while(m--){int a,b;cin>>a>>b;v[a].push_back(b);v[b].push_back(a);}int x;while(k--){cin>>x;cout<<bfs(x)<<endl;}return 0;
}

V[N]版本DFS搜索统计连通分量个数模板：

L2-013 红色警报 (25 分)

//这道题注意更新 sum=cur
//这次因为输出的字符串少了最后那个句号标点
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1001
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];
int vis[N]={0};
void dfs(int index){vis[index]=1;for(int i=0;i<v[index].size();i++){if(vis[v[index][i]]==0){dfs(v[index][i]);}}}
int cnt(){int count=0;for(int i=0;i<n;i++){if(vis[i]==0){count++;dfs(i);}}memset(vis,0,sizeof(vis));return count;
}
int main() {cin>>n>>m;for(int i=0;i<m;i++){cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}int sum=cnt();cin>>k;vector<int>lost;while(k--){cin>>x;lost.push_back(x);for(int i=0;i<lost.size();i++){vis[lost[i]]=1;}int cur=cnt();//目前这个cur是不算lost的其它的连通分量，//连通区域越多，说明城市间越不连通，月危险if(cur>sum){cout<<"Red Alert: City "<<x<<" is lost!"<<endl;}else if(cur<=sum){// 这个是因为如果失去的那个是独立的，则cur会比一开始的-1；cout<<"City "<<x<<" is lost."<<endl;}sum=cur;}if(lost.size()==n){cout<<"Game Over."<<endl;}return 0;
}

L2-025 分而治之 (25 分)

//        if(vis[v[index][i]]==0){#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int vis[N];void dfs(int index){vis[index]=1;for(int i=0;i<v[index].size();i++){if(vis[v[index][i]]==0){dfs(v[index][i]);}}
}
int cnt(){int count=0;for(int i=1;i<=n;i++){if(vis[i]==0){count++;dfs(i);}}memset(vis,0,sizeof(vis));return count;
}
int main() {cin>>n>>m;for(int i=0;i<m;i++){cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}cin>>k;while(k--){vector<int>lost;cin>>d;for(int i=0;i<d;i++){cin>>x;lost.push_back(x);}for(int i=0;i<lost.size();i++){vis[lost[i]]=1;}int cur=cnt();if(n==cur+d){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0;
}

V[N]版本DFS搜索根据条件判断正否模板：

L2-016 愿天下有情人都是失散多年的兄妹 (25 分)

//共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚
// 即dfs(x,1)  到4的时候就行了   if(dai>4){#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];
int sex[N];
int flag=0;
int vis[N]={0};
void dfs(int index , int dai){if(dai>4){return;}for(int i=0;i<v[index].size();i++){if(vis[v[index][i]]==0){vis[v[index][i]]=1;dfs(v[index][i],dai+1);}else{flag=1;}}
}
int main() {cin>>n;int id,fa,ma ;char s;for(int i=0;i<n;i++){cin>>id>>s>>fa>>ma;sex[id]=s;if(fa!=-1){sex[fa]='M';v[id].push_back(fa);}if(ma!=-1){sex[ma]='F';v[id].push_back(ma);}}cin>>k;while(k--){cin>>x>>y;if(sex[x]==sex[y]){cout<<"Never Mind"<<endl;}else{//每次都要初始化一次。。。flag=0;memset(vis,0,sizeof(vis));vis[x]=vis[y]=1;bfs(x,1);bfs(y,1);if(flag==0){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}}return 0;
}

L2-023 图着色问题 (25 分)

//                if(color[i]==color[v[i][j] ] || sc.size()!=d){//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {cin>>n>>m>>d;for(int i=0;i<m;i++){cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}cin>>k;while(k--){int flag=0;vector<int>color;set<int>sc;color.push_back(0);for(int i=0;i<n;i++){cin>>x;sc.insert(x);color.push_back(x);}for(int i=1;i<=n;i++){for(int j=0;j<v[i].size();j++){if(color[i]==color[v[i][j]] || sc.size()!=d){flag=1;}}}if(flag==0)cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

V[N]版本DFS搜索储存路径模板：

L2-020 功夫传人 (25 分)

//有向图
//只保留其整数部分//   cout<<(int)sum<<endl;
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 101000
vector<int>v[N];
vector<int>cur; //存储最终的
vector<int>upda; //存储随时更新的
double cnt=0;
int de[N]={0};
double f,k;
void dfs(int index, vector<int>&upda  ,double gong){//增添判断区域。if(de[index]!=0){cnt=cnt+gong*de[index];}for( int i=0;i<v[index].size();i++){upda.push_back(v[index][i]);dfs(v[index][i], upda , gong*(1-0.01*k));upda.pop_back(); //记得回溯！！}
}
int main() {int n;int x,y;cin>>n>>f>>k;for(int i=0;i<n;i++){cin>>x;if(x==0){cin>>y;de[i]=y;}else{while(x--){cin>>y;v[i].push_back(y);}}}upda.push_back(0);dfs(0, upda, f );//只保留其整数部分cout<<(int)cnt<<endl;return 0;
}

L2-038 病毒溯源 (25 分)

//对于N要进行适应性的更改，对于字段错误
//     if(v[i].size()>0)sort(v[i].begin(),v[i].end());
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];vector<int>upda;
vector<int>cur;
void dfs(int index, vector<int>&upda){if(upda.size()>cur.size()){cur.clear();cur=upda;}for(int i=0;i<v[index].size();i++){upda.push_back(v[index][i]);dfs(v[index][i] ,upda);upda.pop_back();//vector的跳出用pop_back();;;}
}
int main() {cin>>n;int start;int book[N]={0};for(int i=0;i<n;i++){cin>>k;while(k--){cin>>x;book[x]=1;v[i].push_back(x);}if(v[i].size())sort(v[i].begin(),v[i].end());}for(int i=0;i<n;i++){if(book[i]==0)start=i;}upda.push_back(start);dfs(start,upda);cout<<cur.size()<<endl;for(auto i:cur){if(i==start)cout<<i;else cout<<" "<<i;}return 0;
}

L3-025 那就别担心了 (30 分)

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10100
vector<int>v[N];
vector<int>cur; //存储最终的
vector<int>upda; //存储随时更新的
int cnt=0;
int flag=1;void dfs(int index, vector<int>&upda  ,int en){
//    if(upda.size()>=cur.size()){
//        cur.clear();
//        cur=upda;
//    }if(index==en){cnt++;}if(v[index].size()==0 && index!=en){flag=0;}for(int i=0;i<v[index].size();i++){upda.push_back(v[index][i]);dfs(v[index][i],upda , en);upda.pop_back(); //记得回溯！！}
}int main() {int n,m,k;int x,y,z;cin>>n>>m;while(m--){cin>>x>>y;v[x].push_back(y);}int start,en;cin>>start>>en;vector<int>upda;upda.push_back(start);dfs(start, upda , en);if(flag==1){cout<<cnt<<" Yes"<<endl;}else{cout<<cnt<<" No"<<endl;}return 0;
}

二叉树模拟模板：

普通+完全：模板

//主要思考以下问题：
1：创建给出中+后or前  得到root+f[w];;2：先序+中序+后序+层序+深度 等的求解对于：先序+中序+后序采用递归的方法；；对于：层序+深度；采用当时想出来的新方法；；#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 35
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{int lson,rson;
}f[N];
int post[N],mid[N];
int creat(int lmid , int rmid ,int lpost ,int rpost){if(lmid>rmid || lpost >rpost){return 0;}int root=post[rpost];int fa=lmid;while(mid[fa]!=root)fa++;int len=fa-lmid;f[root].lson=creat(lmid,fa-1,lpost,lpost+len-1);f[root].rson=creat(fa+1,rmid,lpost+len,rpost-1);return root;
}void prePrint(int x){cout<<x<<" ";if(f[x].lson)prePrint(f[x].lson);if(f[x].rson)prePrint(f[x].rson);return ;
}void midPrint(int x){if(f[x].lson)midPrint(f[x].lson);cout<<x<<" ";if(f[x].rson)midPrint(f[x].rson);return ;
}
void postPrint(int x){if(f[x].lson)postPrint(f[x].lson);if(f[x].rson)postPrint(f[x].rson);cout<<x<<" ";
}int main() {cin>>n;for(int i=1;i<=n;i++)cin>>post[i];for(int i=1;i<=n;i++)cin>>mid[i];int root=creat(1,n,1,n);v[1].push_back(root);for(int i=1; ; i++){if(v[i].size()==0)break;for(int j=0;j<v[i].size();j++){if(f[v[i][j]].lson)v[i+1].push_back(f[v[i][j]].lson);if(f[v[i][j]].rson)v[i+1].push_back(f[v[i][j]].rson);}}//层序输出for(int i=1; ; i++){if(v[i].size()==0)break;for(int j=0;j<v[i].size();j++){if(i==1)cout<<v[i][j];else cout<<" "<<v[i][j];}}//求深度int dep=0;for(int i=1; ;i++){if(v[i].size()==0)break;dep++;}cout<<"深度"<<dep<<endl;//先序遍历prePrint(root);cout<<endl;//中序遍历midPrint(root);cout<<endl;//后序遍历postPrint(root);return 0;
}#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 35
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int tree[N];
//创建，随着给出的前序or中序or后序 进而调整 cin>>tree[i] 的位置；；
void create(int i) {if (i > n)return;create(2 * i);create(2 * i + 1);cin >> tree[i];//给出后序
}void prePrint(int x){cout<<tree[x]<<" ";if(2*x<=n)prePrint(2*x);if(2*x+1<=n)prePrint(2*x+1);
}void midPrint(int x){if(2*x<=n)midPrint(2*x);cout<<tree[x]<<" ";if(2*x+1<=n)midPrint(2*x+1);}
void postPrint(int x){if(2*x<=n)postPrint(2*x);if(2*x+1<=n)postPrint(2*x+1);cout<<tree[x]<<" ";
}
int main() {cin >> n;create(1);//层序for (int i = 1; i <= n; i++) {if (i > 1)cout << " ";cout << tree[i];}cout<<endl;//先序prePrint(1);cout<<endl;//中序midPrint(1);cout<<endl;//后序postPrint(1);cout<<endl;//存到v[N]中去,求深度int dep=0;int b=2;v[1].push_back(tree[1]);for(int i=2;  ; i++){for(int j=1;j<=(i-1)*2;j++){if(b>n)break;v[i].push_back(tree[b++]);}if(b>n)break;}for(int i=1;   ;i++){if(v[i].size()==0)break;dep++;}cout<<dep<<endl;//求深度for(int i=0; ; i++){if(n>pow(2,i)-1 &&n<=pow(2,i+1)-1){dep=i+1;break;}}cout<<dep<<" ";return 0;
}

L1-071 前世档案 (20 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];int main() {cin>>n>>m;while(m--){string str;cin>>str;int pos=1;for(int i=0;i<n;i++){if(str[i]=='y'){pos=pos*2-1;}else{pos=pos*2;}}cout<<pos<<endl;}return 0;
}

L2-006 树的遍历 (25 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 35
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{int lson,rson;
}f[N];
int post[N],mid[N];
int creat(int lmid , int rmid ,int lpost ,int rpost){if(lmid>rmid || lpost >rpost){return 0;}int root=post[rpost];int fa=lmid;while(mid[fa]!=root)fa++;int len=fa-lmid;f[root].lson=creat(lmid,fa-1,lpost,lpost+len-1);f[root].rson=creat(fa+1,rmid,lpost+len,rpost-1);return root;}
void bfs(int x){vector<int>ve;queue<int>q;q.push(x);while(!q.empty()){int w=q.front();q.pop();ve.push_back(w);if(f[w].lson)q.push(f[w].lson);if(f[w].rson)q.push(f[w].rson);}for(int i=0;i<ve.size();i++){if(i==0)cout<<ve[i];else cout<<" "<<ve[i];}
}
int main() {cin>>n;for(int i=1;i<=n;i++)cin>>post[i];for(int i=1;i<=n;i++)cin>>mid[i];int root=creat(1,n,1,n);bfs(root);return 0;
}对于给出后序和中序来重建二叉树, 因为后序的根一定在最后, 我们依次从后往前遍历post(见1处), 对于每一个post[postR], 找出其在in中的位置k, 然后递归重建即可
同理, 如果是给出前序和中序求得后序的话, 仅仅对顺序进行改动即可
#include<bits/stdc++.h>
using namespace std;
//思路：递归求解 分两个部分 恢复二叉树restree和利用队列层次遍历函数leveltra
vector<int> posord;
vector<int> midord;
//定义一个二叉树结构体
typedef struct btnode{int Data;struct btnode *Left,*Right;
}BTnode,*BTree;
//restree函数三个参数分别是后序遍历中的根节点，中序遍历的起点，中序遍历的终点
BTree restree(int root,int begin,int end){if(begin>end) return NULL;//叶子节点无子树int rnt;for(rnt=begin;rnt<end;rnt++)//在中序里找到根节点的位置{if(midord[rnt]==posord[root])break;}BTree Bt=BTree(malloc(sizeof(struct btnode)));Bt->Data=posord[root];Bt->Left=restree(root-1-(end-rnt),begin,rnt-1);Bt->Right=restree(root-1,rnt+1,end);return Bt;
}
void leveltra(BTree bt){queue<BTree> que;int flag=1;BTree temp = NULL;que.push(bt);while(!que.empty()){temp = que.front();if(flag){cout<<temp->Data; flag=0;}elsecout<<" "<<temp->Data;que.pop();if(temp->Left)que.push(temp->Left);if(temp->Right)que.push(temp->Right);}
}
int main(){int n;cin>>n;int m;for(int i=0;i<n;i++){cin>>m;posord.push_back(m);}for(int i=0;i<n;i++){cin>>m;midord.push_back(m);}leveltra(restree(n-1,0,n-1));return 0;
}///第二种
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1<<30;
const LL maxn = 35;struct node{int data;node *l, *r;
};
int N, pre[maxn], in[maxn], post[maxn];
//当前二叉树后序序列区间为[postL, postR], 中序序列区间为[inL, inR]
node* create(int postL, int postR, int inL, int inR){if(postL > postR)return NULL; //后序序列长度<=0node* root = new node;root->data = post[postR];int k;for(k = inL; k <= inR; k++)if(in[k] == post[postR])break;int numLeft = k - inL;  //左子树的节点个数root->l = create(postL, postL+numLeft-1, inL, k-1); //重建左子树root->r = create(postL+numLeft, postR-1, k+1, inR); //重建右子树 1处return root;
}
int indx = 1;
void Bfs(node* root){queue<node*> q;q.push(root);while(!q.empty()){node* cur = q.front();q.pop();if(indx++ != 1) cout << ' ' << cur->data;else cout << cur->data;if(cur->l != NULL) q.push(cur->l);if(cur->r != NULL) q.push(cur->r);}
}
int main()
{cin >> N;for(int i = 0; i < N; i++)cin >> post[i];for(int i = 0; i < N; i++)cin >> in[i];node* root = create(0, N-1, 0, N-1);//建树Bfs(root);                          //层序遍历return 0;
}

L2-011 玩转二叉树 (25 分)

镜像反转只需将层次遍历中先遍历右边的即可 ，其他就是建树的操作了～～
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 50
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int mid[N],pre[N];
struct node{int lson,rson;
}f[N];
int creat(int lmid, int rmid , int lpre ,int rpre){if(lmid >rmid || lpre>rpre){return 0;}int root=pre[lpre];int fa=lmid;while(mid[fa]!=root)fa++;//len是表示左子树的结点个数数量。int len=fa-lmid;f[root].lson=creat(lmid,fa-1,lpre+1,lpre+len);f[root].rson=creat(fa+1,rmid,lpre+len+1,rpre);return root;
}
void bfs(int x){vector<int>ve;queue<int>q;q.push(x);while(!q.empty()){int w=q.front();q.pop();ve.push_back(w);if(f[w].rson)q.push(f[w].rson);if(f[w].lson)q.push(f[w].lson);}for(int i=0;i<ve.size();i++){if(i==0)cout<<ve[i];else cout<<" "<<ve[i];}
}
int main() {cin>>n;for(int i=1;i<=n;i++)cin>>mid[i];for(int i=1;i<=n;i++)cin>>pre[i];int root=creat(1,n,1,n);bfs(root);return 0;
}

L2-035 完全二叉树的层序遍历 (25 分)

#include <iostream>
using namespace std;int n, tree[31];
//创建
void create(int i) {if (i > n)return;create(2 * i);create(2 * i + 1);cin >> tree[i];
}int main() {cin >> n;create(1);for (int i = 1; i <= n; i++) {if (i > 1)cout << " ";cout << tree[i];}return 0;
}

二叉搜索树的相关模拟：

普通+完全：模板

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int pre[N];
int ism=0;
vector<int>anspre,ansmid,anspost;
void f(int l , int r){if(l>r)return;int tl=l+1;//左孩子的区间的尽头。int tr=r; // 右孩子的区间的尽头。if(!ism){//正常while(tl<=r&&pre[tl]<pre[l])tl++;while(tr>=l+1&&pre[tr]>=pre[l])tr--;}else{while(tl<=r&&pre[tl]>=pre[l])tl++;while(tr>=l+1&&pre[tr]<pre[l])tr--;}if(tl-tr!=1)return;///如果不是二叉搜索树//类似输出前序遍历，中序遍历，后序遍历的写法//如果 要求输出中序遍历，则push_back()操作放在中间anspre.push_back(pre[l]);f(l+1,tr); //左,注意区间要去掉根ansmid.push_back(pre[l]);f(tl,r);//右anspost.push_back(pre[l]);//根，注意为pre[l];
}struct node{int lson,rson;
}f[N];
int post[N],mid[N];
int creat(int lmid , int rmid ,int lpost ,int rpost){if(lmid>rmid || lpost >rpost){return 0;}int root=post[rpost];int fa=lmid;while(mid[fa]!=root)fa++;int len=fa-lmid;f[root].lson=creat(lmid,fa-1,lpost,lpost+len-1);f[root].rson=creat(fa+1,rmid,lpost+len,rpost-1);return root;
}int main() {cin>>n;for(int i=1;i<=n;i++)cin>>pre[i];f(1,n);

L2-004 这是二叉搜索树吗？ (25 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int pre[N];
int ism=0;
vector<int>ans;
void f(int l , int r){if(l>r)return;int tl=l+1;//左孩子的区间的尽头。int tr=r; // 右孩子的区间的尽头。if(!ism){//正常while(tl<=r&&pre[tl]<pre[l])tl++;while(tr>=l+1&&pre[tr]>=pre[l])tr--;}else{while(tl<=r&&pre[tl]>=pre[l])tl++;while(tr>=l+1&&pre[tr]<pre[l])tr--;}if(tl-tr!=1)return;///如果不是二叉搜索树//类似输出前序遍历，中序遍历，后序遍历的写法//如果 要求输出中序遍历，则push_back()操作放在中间f(l+1,tr); //左,注意区间要去掉根f(tl,r);//右ans.push_back(pre[l]);//根，注意为pre[l];
}
int main() {cin>>n;for(int i=1;i<=n;i++)cin>>pre[i];f(1,n);///第一次不成功可能因为是镜像if(ans.size()!=n){ans.clear();ism=1;f(1,n);}///镜像还不成功就说明不是搜索二叉树if(ans.size()!=n){cout<<"NO"<<endl;}else{cout<<"YES"<<endl;for(int i=0;i<ans.size();i++){if(i==0)cout<<ans[i];else cout<<" "<<ans[i];}}return 0;
}

L3-010 是否完全二叉搜索树 (30 分)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;int Tree[maxn];//因为二叉树是直接给一堆数，让你创建，所以如果是完全的话，反正位置就是2*i 和 2*i+1
void update(int root, int val){if(Tree[root]==0) // 第一个根节点是没有的一开始就像ok那样的；；具体到每一个小树都是这样的。Tree[root] = val;else if(val > Tree[root])update(root*2, val);else update(root*2+1,val);
}int main(){int n;  cin>>n;for(int i = 1; i <= n; i++){int x;  cin>>x;  update(1,x);}int ok = 0, cnt = 0;for(int i = 1; i < maxn; i++){if(Tree[i]){if(ok==0){cout<<Tree[i];ok=1;}else{cout<<" "<<Tree[i];}cnt = i;}}if(cnt > n)cout<<"\nNO\n";else cout<<"\nYES\n";return 0;
}

L3-016 二叉搜索树的结构 (30 分)

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 10001
struct node{int l=-1;   //左孩子int r=-1;   //右孩子int fa=-1;  // 父int h;          //深度
};map<int , node> tree;
void Increat(int ro, int h , int v){if(ro==-1) return ;int uu=(v<ro?tree[ro].l : tree[ro].r);if(uu!=-1){Increat(uu , h+1 , v);}else{if(v<ro){tree[ro].l=v;}else{tree[ro].r=v;}tree[v].fa=ro;tree[v].h=h;}
}bool judge(int ro, int a, int b, string lk){if(lk=="root")return ro==a;if(tree.find(a)==tree.end() || tree.find(b)==tree.end())return false;if(lk=="siblings")return tree[a].fa==tree[b].fa;if(lk=="parent")return tree[a].l==b || tree[a].r==b;if(lk=="left")return tree[b].l == a;if(lk=="right")return tree[b].r == a;if(lk=="level")return tree[a].h==tree[b].h;
}int main() {int n;int root;cin>>n;cin>>root;int x,y,z;for(int i=2;i<=n;i++){cin>>x;Increat(root, 1 ,x);}int m, a=0, b=0;cin>>m;for(int i = 1; i <= m; i++){string s, lk;cin>>a>>s;if(s=="and"){cin>>b>>s>>s;if(s=="siblings")lk = s;else cin>>s>>s>>lk;}else{  // 这个就是is了cin>>s>>lk;if(lk=="parent")cin>>s>>b;else if(lk!="root")cin>>s>>s>>b;}if(judge(root,a,b,lk))cout<<"Yes\n";else cout<<"No\n";}return 0;
}

顶堆的模拟模板：

L2-012 关于堆的判断 (25 分)

//下一行给出区间[−10000,10000]内的N个要被插入一个初始为空的小顶堆的整数
//即要根据给的进行建立堆，，
//且根据层序进行创建储存。。
//因为是堆总是一棵完全二叉树。所以可以用 2*i or 2*i+1#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int h[N];
int find(int x){for(int i=1;i<=n;i++){if(h[i]==x){return i;}}return -1;
}
int main() {cin>>n>>m;for(int i=1;i<=n;i++){cin>>h[i];int k=i;while(k>1&&h[k]<h[k/2]){swap(h[k],h[k/2]);k=k/2;}}string s;while(m--){cin>>x;int a=find(x);//根据结点的值找到该节点值的位置；cin>>s;if(s=="and"){cin>>y>>s>>s;int b=find(y);if(a/2==b/2)cout<<"T"<<endl;else cout<<"F"<<endl;}else{cin>>s;if(s=="a"){cin>>s>>s>>y;int b=find(y);if(a/2==b)cout<<"T"<<endl;else cout<<"F"<<endl;}else{cin>>s;if(s=="root"){if(a==1)cout<<"T"<<endl;else cout<<"F"<<endl;}else{cin>>s>>y;int b=find(y);if(a==b/2)cout<<"T"<<endl;else cout<<"F"<<endl;}}}}return 0;
}

栈与队列模板：

L2-037 包装机 (25 分)

//注意：stack的push() top()  pop()  queue 的push()  front()  pop();
//对于N要进行适应性的更改，对于字段错误
//if(sc[x].size()>0){
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1001
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
queue<char>sc[N];int main() {cin>>n>>m>>d;//注意铁轨上的用queue储存。for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>ch;sc[i].push(ch);}}stack<char>s;while(cin>>k){if(k==-1)break;if(k==0){//抓取时，判断是否有if(s.size()>0){cout<<s.top();s.pop();}}else{//从铁轨推东西时看是否还有东西，以及容器里是否满了。if(sc[k].size()>0){if(s.size()==d){cout<<s.top();s.pop();}s.push(sc[k].front());sc[k].pop();}}}return 0;
}

L2-032 彩虹瓶 (25 分)

//记住stack' 没有 s.clear（）
//记住要先判断s的非空才能使用s.top();;
//     while(!s.empty()&&cur==s.top()){
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int x,y,z;
int main(){cin>>n>>m>>k;while(k--){int cur=1;      //用来记录彩虹瓶当前需要填装的货号stack<int>s; //这个stack表示临时货架for(int i=1;i<=n;i++){cin>>x;if(x==cur){cur++;while(!s.empty() &&s.top()==cur){//必须加上判断s非空s.pop();cur++;}}else{if(s.size()<m)s.push(x);}}if(cur==n+1)cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}

L2-033 简单计算器 (25 分)

//这里面是num2 op num1 //对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int main() {stack<int>s1;stack<char>s2;cin>>n;for(int i=0;i<n;i++){cin>>x;s1.push(x);}for(int i=0;i<n-1;i++){cin>>ch;s2.push(ch);}int flag=0;while(!s2.empty()){int num1=s1.top();s1.pop();int num2=s1.top();s1.pop();ch=s2.top();s2.pop();if(ch=='+'){s1.push(num2+num1);}else if(ch=='-'){s1.push(num2-num1);}else if(ch=='*'){s1.push(num2*num1);}else if(ch=='/'){if(num1==0){cout<<"ERROR: "<<num2<<"/0"<<endl;flag=1;break;}else{s1.push(num2/num1);}}}if(flag==0)cout<<s1.top();return 0;
}

L3-002 特殊堆栈 (30 分)

//实现vector 插入时进行排序；；
//核心代码：
cin>>x;
it=lower_bound(v.begin(),v.end(),x);
v.insert(it,x);//“取中值”——即返回所有堆栈中元素键值的中值。 并不进行跳出好像//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int main()
{vector<int> ans;vector<int>order;vector<int>::iterator it;cin>>n;while(n--){cin>>str;if(str[1]=='u'){cin>>x;ans.push_back(x);it=lower_bound(order.begin(),order.end(),x);order.insert(it,x);}else if(str[1]=='e'){if(order.size()>0){int num=order.size();cout<<order[(num-1)/2]<<endl;}else{cout<<"Invalid"<<endl;}}else if(str[1]=='o'){if(order.size()>0){int num=ans[ans.size()-1];cout<<num<<endl;ans.pop_back();it=lower_bound(order.begin(),order.end(),num);order.erase(it);}else{cout<<"Invalid"<<endl;}}}}//超时的
#include <bits/stdc++.h>
using namespace std;
#define N 100100
#define inf 0x3f3f3f3f
int n,m,d,k;
int x,y,z;
string str;
char ch;
vector<int>v[N];int main()
{cin>>n;stack<int>s;vector<int>cur;vector<int>::iterator it;while(n--){cin>>str;if(str=="Pop"){if(s.size()==0){cout<<"Invalid"<<endl;}else{int num=s.top();s.pop();cout<<num<<endl;it=lower_bound(cur.begin(),cur.end(),num);cur.erase(it);}}else if(str=="PeekMedian"){if(cur.size()>0){sort(cur.begin(),cur.end());int num=cur.size();cout<<cur[(num-1)/2]<<endl;}else{cout<<"Invalid"<<endl;}}else if(str=="Push"){cin>>x;cur.push_back(x);s.push(x);}}return 0;
}

简单并查集：

L2-010 排座位 (25 分)

//这题别忘了把初始化给 在主函数进行调用实现。
//int mp[N][N]={0};
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 101
int n,m,k,g,d;
int x,y,z;
vector<int>v[N];
int mp[N][N]={0};
int f[N];
void Init(){for(int i=1;i<=n;i++){f[i]=i;}
}int find( int x){if(x!=f[x]){f[x]=find(f[x]);}return f[x];
}void merge(int x, int y){int fx=find(x);int fy=find(y);if(fx>fy){f[fx]=fy;}else{f[fy]=fx;}
}int main() {cin>>n>>m>>k;Init();for(int i=0;i<m;i++){cin>>x>>y>>z;if(z==-1){mp[x][y]=mp[y][x]=-1;}else{merge(x,y);}}while(k--){cin>>x>>y;int fx=find(x);int fy=find(y);if(fx==fy && mp[x][y]==0){cout<<"No problem"<<endl;}else if(fx!=fy && mp[x][y]==0){cout<<"OK"<<endl;}else if(fx==fy &&mp[x][y]==-1){cout<<"OK but..."<<endl;}else if(fx!=fy &&mp[x][y]==-1){cout<<"No way"<<endl;}}return 0;
}

L2-024 部落 (25 分)

//对于N要进行适应性的更改，对于字段错误
//注意f[i]=i 的时候，范围是N；
//对于N要进行适应性的更改，对于字段错误//    for(auto i:people){book[find(i)]++;}
//
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int f[N]={0};
void Init(){for(int i=0;i<N;i++){f[i]=i;}
}
int find(int x){if(x!=f[x]){f[x]=find(f[x]);}return f[x];
}
void merge(int x, int y){int fx=find(x);int fy=find(y);if(fx>fy){f[fx]=fy;}else{f[fy]=fx;}
}
int main() {Init();cin>>n;set<int>people;for(int i=0;i<n;i++){cin>>k;cin>>x;people.insert(x);for(int j=1;j<k;j++){cin>>y;people.insert(y);merge(x,y);}}int cnt=0;int book[N]={0};//如果每次都用people 应该会很方便：：：：每次都要从people循环开始；；for(auto i:people){book[find(i)]++;}for(auto i:people){if(book[i]>0)cnt++;}cout<<people.size()<<" "<<cnt<<endl;cin>>k;while(k--){cin>>x>>y;if(find(x)==find(y))cout<<"Y"<<endl;else cout<<"N"<<endl;}return 0;
}

L3-003 社交集群 (30 分)

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1001
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int f[N];
void Init( ){for(int i=0;i<=N;i++){f[i]=i;}
}
int find(int x){if(x!=f[x]){f[x]=find(f[x]);}return f[x];
}void merge(int x,int y){int fx=find(x);int fy=find(y);if(fx>fy){f[fx]=fy;}else{f[fy]=fx;}
}
bool cmp(int x,int y){return x>y;
}
int main() {Init();cin>>n;for(int i=1;i<=n;i++){cin>>k>>ch;cin>>x;v[i].push_back(x);for(int j=1;j<k;j++){cin>>y;v[i].push_back(y);merge(x,y);//合并操作}}set<int>sc[N];for(int i=1;i<=n;i++){int num=find(v[i][0]);sc[num].insert(i);}int cnt=0;vector<int>ans;for(int i=1;i<=1000;i++){if(sc[i].size()>0){cnt++;ans.push_back(sc[i].size());}}sort(ans.begin(),ans.end(),cmp);cout<<cnt<<endl;for(int i=0;i<ans.size();i++){if(i==0)cout<<ans[i];else cout<<" "<<ans[i];}return 0;
}

链表模拟模板：

L2-002 链表去重 (25 分)

//这道题要注意的是 可能 b1的数量为0 即没有重复的
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{int data;int next;
}ss[N];
int main() {int firadd,add;cin>>firadd>>n;for(int i=0;i<n;i++){cin>>add>>ss[add].data>>ss[add].next;}int a[N],b[N];int a1=0,b1=0;int book[N]={0};for(int i=firadd;i!=-1;i=ss[i].next){int num=abs(ss[i].data);if(book[num]==0){a[a1++]=i;book[num]=1;}else{b[b1++]=i;}}printf("%05d %d ",a[0],ss[a[0]].data);for(int i=1;i<a1;i++){printf("%05d\n",a[i]);printf("%05d %d ",a[i],ss[a[i]].data);}cout<<"-1"<<endl;if(b1>0){printf("%05d %d ",b[0],ss[b[0]].data);for(int i=1;i<b1;i++){printf("%05d\n",b[i]);printf("%05d %d ",b[i],ss[b[i]].data);}cout<<"-1"<<endl;}return 0;
}

L2-022 重排链表 (25 分)

//对于N要进行适应性的更改，对于字段错误
//struct node{int data;int next;
}ss[N];//#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
struct node{int data;int next;
}ss[N];
int main() {int firadd,add;cin>>firadd>>n;for(int i=0;i<n;i++){cin>>add>>ss[add].data>>ss[add].next;}//a用来存一开始的所有点的顺序地址//b用来存后来按要求需要的地址输出的位置int a[N],b[N];int a1=0,b1=0;for(int i=firadd;i!=-1;i=ss[i].next){a[a1++]=i;}int l=0,r=a1-1;//表示往中间走，l，r表示该存哪个位置的信息了；//该存，表示这个位置还是空的？尝试book？while(l<=r){if(l<=r){b[b1++]=a[r];r--;}if(l<=r){b[b1++]=a[l];l++;}}//输出printf("%05d %d ",b[0],ss[b[0]].data);for(int i=1;i<b1;i++){printf("%05d\n",b[i]);printf("%05d %d ",b[i],ss[b[i]].data);}cout<<"-1"<<endl;return 0;
}

经典DP问题模块模板：

背包问题模板：

最简单的0-1背包问题：
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int v[N];
int w[N];
int f[N][N];int main() {//0-1背包cin>>n>>m;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i]){f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);}}}cout<<f[n][m]<<endl;return 0;
}//变成一位的问题：尽量用这个
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
int v[N];
int w[N];
int f[N];
int main() {//0-1背包cin>>n>>m;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++){for(int j=m;j>=0;j--){if(j<v[i]){f[j]=f[j];}else{f[j]=max(f[j],f[j-v[i]]+w[i]);}}}cout<<f[m]<<endl;return 0;
}//完全背包问题：：
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{int n,m;cin>>n>>m;for(int i = 1 ; i <= n ;i ++){cin>>v[i]>>w[i];}for(int i = 1 ; i<=n ;i++)for(int j = 0 ; j<=m ;j++){for(int k = 0 ; k*v[i]<=j ; k++)f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);}cout<<f[n][m]<<endl;
}//求能够达到最大的价值的方案数量，就是有好多种选择可以使得所选的物品价值最大；；
//背包求方案数：：
路径跟踪 g[i][j]g[i][j]
状态表示g(i,j)g(i,j)—集合： 考虑前 i 个物品，当前已使用体积恰好是 j 的，且 价值 为最大的方案状态表示g(i,j)g(i,j)—属性： 方案的数量 SumSum
状态转移g(i,j)g(i,j)：如果fi,j=fi−1,jfi,j=fi−1,j 且 fi,j=fi−1,j−v+wfi,j=fi−1,j−v+w 则 gi,j=gi−1,j+gi−1,j−vgi,j=gi−1,j+gi−1,j−v
如果fi,j=fi−1,jfi,j=fi−1,j 且 fi,j≠fi−1,j−v+wfi,j≠fi−1,j−v+w 则 gi,j=gi−1,jgi,j=gi−1,j
如果fi,j≠fi−1,jfi,j≠fi−1,j 且 fi,j=fi−1,j−v+wfi,j=fi−1,j−v+w 则 gi,j=gi−1,j−vgi,j=gi−1,j−v
初始状态：g[0][0] = 1#include <iostream>
#include <cstring>using namespace std;const int N = 1010, mod = 1e9 + 7;int n, m;
int w[N], v[N];
int f[N][N], g[N][N];int main()
{cin >> n >> m;for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];for (int i = 1; i <= n; ++ i){for (int j = 0; j <= m; ++ j){f[i][j] = f[i - 1][j];if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);}}g[0][0] = 1;for (int i = 1; i <= n; ++ i){for (int j = 0; j <= m; ++ j){if (f[i][j] == f[i - 1][j])g[i][j] = (g[i][j] + g[i - 1][j]) % mod;if (j >= v[i] && f[i][j] == f[i - 1][j - v[i]] + w[i])g[i][j] = (g[i][j] + g[i - 1][j - v[i]]) % mod;}}int res = 0;for (int j = 0; j <= m; ++ j){if (f[n][j] == f[n][m]){res = (res + g[n][j]) % mod;}}cout << res << endl;return 0;
}//求具体的方案数；
//看凑零钱那个就行了；

L3-001 凑零钱 (30 分)

#include<bits/stdc++.h>
using namespace std;
#define N 10001
int value[N]={0};
int dp[N][N]={0};
int choose[N][N]={0}; //在加之最大未N时候，第N件物品是否选择‘
bool cmp(int x,int y){return x>y;
}
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>value[i];}sort(value+1,value+1+n,cmp);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j]=dp[i-1][j];if(j>=value[i]){dp[i][j]=max(dp[i][j] ,value[i]+ dp[i-1][j-value[i]]);if( dp[i][j]==value[i]+ dp[i-1][j-value[i]]){choose[i][j]=1;}}}}if(dp[n][m]!=m){cout<<"No Solution"<<endl;return 0;}vector<int>ans;for(int i=n,j=m ; i>=1&& j>=0 ; i--){if(choose[i][j]){ans.push_back(value[i]);j=j-value[i];}}for(int i=0;i<ans.size();i++){if(i==0)cout<<ans[i];else cout<<" "<<ans[i];}
return 0;
}

L3-2 拼题A打卡奖励 (30 分)

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,k,g,d;
int x,y,z;
long long m;
char ch;
string str;
int v[N];
int w[N];int main() {//0-1背包cin>>n>>m;int sumtimt=0;int sumvalue=0;for(int i=1;i<=n;i++){cin>>v[i];sumtimt+=v[i];}for(int i=1;i<=n;i++){cin>>w[i];sumvalue+=w[i];}if(sumtimt<=m){cout<<sumvalue<<endl;return 0;}int f[m+1]={0};//适者生存；；；；for(int i=1;i<=n;i++){for(int j=m;j>=0;j--){if(j<v[i]){f[j]=f[j];}else{f[j]=max(f[j], f[j-v[i]]+w[i]);}}}cout<<f[m]<<endl;return 0;
}

L3-020 至多删三个字符 (30 分)

MP[ N ][N】版本Dijs最短路径模板：

第一类：给出路径让判断是否可行：

L2-036 网红点打卡攻略 (25 分)

//注意使用int 而不是 double ，注意出现flag=1的 三 个条件
//对于N要进行适应性的更改，对于字段错误
// //          if(num==inf || vis[ans[i]]==1 ||x!=n ){
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 205
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int mp[N][N];
int vis[N];
int dis[N];int main() {cin>>n>>m;//因为是判断，即只要在main里面搞就行了//初始化；memset(vis,0,sizeof(vis));memset(mp,inf,sizeof(mp));memset(dis,inf,sizeof(dis));for(int i=0;i<=n;i++)mp[i][i]=0;for(int i=0;i<m;i++){cin>>x>>y>>z;mp[x][y]=mp[y][x]=z;}//初始化结束cin>>k;int count=0;int start=0;int minn=inf;for(int i=1;i<=k;i++){cin>>x;vector<int>ans;//用ans来存储路径，方便接下来进行判断//因为要计算别处景点到家(0)的距离，即先把0放入；；ans.push_back(0);for(int i=0;i<x;i++){cin>>y;ans.push_back(y);}ans.push_back(0);int flag=0;int value=0;memset(vis,0,sizeof(vis));for(int j=1;j<ans.size();j++){int num=mp[ans[j]][ans[j-1]];if(num==inf || vis[ans[j]]==1 || x!=n){//判断条件，每个景点都只访问一次；即访问，还只需一次；flag=1;break;}vis[ans[j]]=1;value+=num;}if(flag==1)continue;count++;if(value<minn){minn=value;start=i;}}cout<<count<<endl;cout<<start<<" "<<minn<<endl;return 0;
}

第二类：完全体求各种东西的dijs

L2-001 紧急救援 (25 分)

//这道题给的教训就是：：#define N 要恰到好处不能太大，也不能太小。。切记
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 505
int n,m,k,s,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int mp[N][N];
int dis[N];
int vis[N];
int way[N];
//分割线
int people[N];
int cnt[N];
int num[N];
void dij(int index){//初始化vis，dis，以及main上面的变量；；memset(vis,0,sizeof(vis));memset(dis,inf,sizeof(dis));for(int i=0;i<n;i++)dis[i]=mp[index][i];dis[index]=0;way[index]=index;//初始化的人员，初始化的道路选择；；num[index]=people[index];cnt[index]=1;//找n个最短点，一个for找到一个点，vis【点】=1；//显然，第一个点是自己本身dis【index】=0；//第一部分：找最短的for(int i=0;i<n;i++){int u=-1,minn=inf;for(int j=0;j<n;j++){if(vis[j]==0&&dis[j]<minn){u=j;minn=dis[j];}}if(u==-1)break;vis[u]=1;//第二部分：更新距离for(int j=0;j<n;j++){if(vis[j]==0&&dis[j]>dis[u]+mp[u][j]){dis[j]=dis[u]+mp[u][j];num[j]=num[u]+people[j];way[j]=u;cnt[j]=cnt[u];//c出现下面这个条件啊，就会再出来一个最优判断。}else if(vis[j]==0&&dis[j]==dis[u]+mp[u][j]){cnt[j]=cnt[u]+cnt[j];if(num[j]<num[u]+people[j]){way[j]=u;num[j]=num[u]+people[j];}}}}
}int main() {cin>>n>>m>>s>>d;for(int i=0;i<n;i++)cin>>people[i];//初始化mpmemset(mp,inf,sizeof(mp));for(int i=0;i<n;i++)mp[i][i]=0;for(int i=0;i<m;i++){cin>>x>>y>>z;mp[x][y]=mp[y][x]=z;}//初始化mp结束dij(s);cout<<cnt[d]<<" "<<num[d]<<endl;//输出路径用ans倒着存起来；vector<int>ans;int t=d;while(t!=s){ans.push_back(t);t=way[t];}ans.push_back(s);//存结束//输出,尽量不用ok，这样快，简便int ok=1;for(int i=ans.size()-1;i>=0;i--){if(i!=0)cout<<ans[i]<<" ";else cout<<ans[i];}return 0;
}

L3-005 垃圾箱分布 (30 分)

//这个注意点时最短距离最远加上平均距离，这两个；；
//但是最后4分不知道为啥怎么办？好像是精度的问题：
//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1020
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int dis[N]={0};
int vis[N]={0};
int mp[N][N]={0};void dij(int index ){memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));dis[index]=0;for(int i=0;i<n+m;i++){int u=-1,minn=inf;for(int j=1;j<=n+m;j++){if(vis[j]==0&& dis[j]<minn){u=j;minn=dis[j];}}if(u==-1){break;}vis[u]=1;for(int j=1;j<=n+m;j++){if(vis[j]==0 &&dis[j]>dis[u]+mp[u][j]){dis[j]=dis[u]+mp[u][j];}}}
}
int main() {cin>>n>>m>>k>>d;memset(mp,inf,sizeof(mp));for(int i=1;i<N;i++)mp[i][i]=0;string a,b;while(k--){cin>>a>>b>>z;if(a[0]=='G'){x=n+a[1]-'0';}else{x=a[0]-'0';}if(b[0]=='G'){y=n+b[1]-'0';}else{y=b[0]-'0';}mp[x][y]=mp[y][x]=z;}double avedis=0;int start=0;double premindis=0;for(int i=n+1;i<=n+m;i++){double sum=0;int flag=0;int mindis=inf;dij(i);for(int j=1;j<=n;j++){if(dis[j]>d){flag=1;break;}sum=sum+dis[j];if(dis[j]<mindis)mindis=dis[j];}if(flag==1){continue;}if(mindis>premindis){start=i;premindis=mindis;avedis=sum;}else if(mindis==premindis){if(sum<avedis){start=i;premindis=mindis;avedis=sum;}}}if(start==0){cout<<"No Solution"<<endl;}else{cout<<"G"<<start-n<<endl;printf("%.1f",premindis);printf(" %.1f",(double)avedis/n);}return 0;
}

L3-007 天梯地图 (30 分)

//对于N要进行适应性的更改，对于字段错误
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 505
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];int dislen[N];
int distime[N];
int vis[N];
int mpT[N][N];
int mpL[N][N];
int wayT[N];
int wayL[N];
void dijLen(int index){memset(vis,0,sizeof(vis));memset(dislen,inf,sizeof(dislen));for(int i=0;i<n;i++)dislen[i]=mpL[index][i];dislen[index]=0;int jiedian[N]={0};for(int i=0;i<n;i++){int u=-1,minn=inf;for(int j=0;j<n;j++){if(vis[j]==0&&dislen[j]<minn){u=j;minn=dislen[j];}}if(u==-1)break;vis[u]=1;for(int j=0;j<n;j++){if(vis[j]==0&&dislen[j]>dislen[u]+mpL[u][j]){dislen[j]=dislen[u]+mpL[u][j];wayL[j]=u;jiedian[j]=jiedian[u]+1;}else if(vis[j]==0 && dislen[j]==dislen[u]+mpL[u][j]){if(jiedian[j]>jiedian[u]+1){jiedian[j]=jiedian[u]+1;wayL[j]=u;}}}}}
void dijTime(int index){memset(vis,0,sizeof(vis));memset(distime,inf,sizeof(distime));//如果少了下面这一行的代码，则会输出多个开头for(int i=0;i<n;i++)distime[i]=mpT[index][i];int dis[N];//复制一份最短，memset(dis,inf,sizeof(dis));for(int i=0;i<n;i++)dis[i]=dislen[i];dis[index]=distime[index]=0;for(int i=0;i<n;i++){int u=-1,minn=inf;for(int j=0;j<n;j++){if(vis[j]==0 && distime[j]<minn){u=j;minn=distime[j];}}if(u==-1)break;vis[u]=1;for(int j=0;j<n;j++){if(vis[j]==0 && distime[j]>distime[u]+mpT[u][j]){wayT[j]=u;distime[j]=distime[u]+mpT[u][j];dis[j]=dis[u]+mpL[u][j];}else if(vis[j]==0 && distime[j]==distime[u]+mpT[u][j]){if(dis[j]>dis[u]+mpL[u][j]){wayT[j]=u;dis[j]=dis[u]+mpL[u][j];}}}}
}
int main() {cin>>n>>m;memset(mpT,inf,sizeof(mpT));memset(mpL,inf,sizeof(mpL));memset(wayL,-1,sizeof(wayL));memset(wayT,-1,sizeof(wayT));int time,len;while(m--){cin>>x>>y>>z>>time>>len;if(z==1){mpT[x][y]=time;mpL[x][y]=len;}else{mpT[x][y]=mpT[y][x]=time;mpL[x][y]=mpL[y][x]=len;}}int start,end;cin>>start>>end;dijLen(start);dijTime(start);vector<int>ansl;vector<int>anst;int mid=end;while(mid!=-1){ansl.push_back(mid);mid=wayL[mid];}ansl.push_back(start);mid=end;while(mid!=-1){anst.push_back(mid);mid=wayT[mid];}anst.push_back(start);if(ansl==anst){cout << "Time = " <<dislen[end]<<"; Distance = "<<distime[end]<<": ";for(int i=ansl.size()-1;i>=0;i--){if(i==0)cout<<ansl[i];else cout<<ansl[i]<<" => ";}}else{cout<< "Time = " <<dislen[end]<<": ";for(int i=ansl.size()-1;i>=0;i--){if(i==0)cout<<ansl[i];else cout<<ansl[i]<<" => ";}cout<<endl;cout<< "Distance = "<<distime[end]<<": ";for(int i=anst.size()-1;i>=0;i--){if(i==0)cout<<anst[i];else cout<<anst[i]<<" => ";}cout<<endl;}return 0;
}///下面是找到的网上的正确的不知道为啥：：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n, m, v1, v2, oneway, length, ti, s, e, tmp, flag;
int disto[510], dis[510][510], timeto[510], tme[510][510], disvis[510], timevis[510], sum[510];
int dispre[510], timepre[510];
int a[510], b[510], ka, kb;
int fdisto[510];
void Dijstrldis() {disto[s] = 0;for(int i = 0; i < n; i++) {int minn = inf, next = -1;for(int j = 0; j < n; j++) {if(disvis[j] == 0 && disto[j] < minn) {minn = disto[j];next = j;}}if(next == -1) break;elsedisvis[next] = 1;for(int j = 0; j < n; j++) {if(disvis[j] == 0 && disto[next] + dis[next][j] < disto[j]) {disto[j] = disto[next] + dis[next][j];dispre[j] = next;sum[j] = sum[next] + 1;} else if(disvis[j] == 0 && disto[next] + dis[next][j] == disto[j]) {if(sum[next] + 1 < sum[j]) {sum[j] = sum[next] + 1;dispre[j] = next;}}}}
}
void Dijstrltime() {timeto[s] = 0;for(int i = 0; i < n; i++) {int minn = inf, next = -1;for(int j = 0; j < n; j++) {if(timevis[j] == 0 && timeto[j] < minn) {minn = timeto[j];next = j;}}if(next == -1) break;elsetimevis[next] = 1;for(int j = 0; j < n; j++) {if(timevis[j] == 0 && timeto[next] + tme[next][j] < timeto[j]) {timeto[j] = timeto[next] + tme[next][j];timepre[j] = next;fdisto[j] = fdisto[next] + dis[next][j];} else if(timevis[j] == 0 && timeto[next] + tme[next][j] == timeto[j]) {if(fdisto[j] > fdisto[next] + dis[next][j]) {timepre[j] = next;fdisto[j] = fdisto[next] + dis[next][j];}}}}
}
int main() {cin>>n>>m;memset(dis,inf,sizeof(dis));memset(tme,inf,sizeof(tme));for(int i = 0; i < n; i++) {sum[i] = 1;disto[i] = inf;timeto[i] = inf;}for(int i = 0; i < m; i++) {scanf("%d%d%d%d%d", &v1, &v2, &oneway, &length, &ti);dis[v1][v2] = length;tme[v1][v2] = ti;if(oneway == 0) {dis[v2][v1] = length;tme[v2][v1] = ti;}}scanf("%d%d", &s, &e);Dijstrldis();tmp = e;ka = 0;a[ka++] = tmp;while(tmp != s) {tmp = dispre[tmp];a[ka++] = tmp;}Dijstrltime();tmp = e;kb = 0;b[kb++] = tmp;while(tmp != s) {tmp = timepre[tmp];b[kb++] = tmp;}flag = 1;if(ka == kb) {for(int i = 0; i < ka; i++) {if(a[i] != b[i]) {flag = 0;break;}}} else {flag = 0;}if(flag) {printf("Time = %d; Distance = %d: ", timeto[e], disto[e]);for(int i = ka-1; i >= 0; i--) printf(i == ka-1 ? "%d" : " => %d", a[i]);printf("\n");} else {printf("Time = %d: ", timeto[e]);for(int i = kb-1; i >= 0; i--) printf(i == kb-1 ? "%d" : " => %d", b[i]);printf("\nDistance = %d: ", disto[e]);for(int i = ka-1; i >= 0; i--) printf(i == ka-1 ? "%d" : " => %d", a[i]);printf("\n");}return 0;
}

L3-011 直捣黄龙 (30 分)

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n, k, len;
int to[210], dis[210][210], sump[210], sum[210], num[210], pre[210], vis[210], sumpath[210];
string s1, s2, s, u, v;
map<string, int> m1;
map<int, string> m2;
void Dijstr(int start) {to[start] = 0;for(int i = 1; i <= n; i++) {int minn = inf, next = -1;for(int j = 1; j <= n; j++) {if(vis[j] == 0 && to[j] < minn) {minn = to[j];next = j;}}if(next == -1) break;elsevis[next] = 1;for(int j = 1; j <= n; j++) {if(vis[j] == 0 && to[next] + dis[next][j] < to[j]) {to[j] = to[next] + dis[next][j];sump[j] = sump[next] + 1;sum[j] = sum[next] + num[j];sumpath[j] = sumpath[next];pre[j] = next;} else if(vis[j] == 0 && to[next] + dis[next][j] == to[j]) {sumpath[j]= sumpath[j] + sumpath[next];if(sump[next] + 1 > sump[j]) {sump[j] = sump[next] + 1;sum[j] = sum[next] + num[j];pre[j] = next;} else if(sump[next] + 1 == sump[j]) {if(sum[j] < sum[next] + num[j]) {sum[j] = sum[next] + num[j];pre[j] = next;}}}}}
}
int main() {cin >> n >> k >> s1 >> s2;for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {dis[i][j] = inf;}}for(int i = 1; i <= n; i++) {sump[i] = 1;sumpath[i] = 1;to[i] = inf;}m1[s1] = 1;m2[1] = s1;for(int i = 2; i <= n; i++) {cin >> s >> num[i];m1[s] = i;m2[i] = s;sum[i] = num[i];}for(int i = 0; i < k; i++) {cin >> u >> v >> len;dis[m1[u]][m1[v]] = len;dis[m1[v]][m1[u]] = len;}Dijstr(1);int t = m1[s2], k = 0, path[210];path[k++] = t;while(t != 1) {t = pre[t];path[k++] = t;} for(int i = k-1; i >= 0; i--) {if(i == k-1) cout << m2[path[i]];elsecout << "->" << m2[path[i]];}printf("\n%d %d %d\n", sumpath[m1[s2]], to[m1[s2]], sum[m1[s2]]);return 0;
}

Edge版本dijs最短路径模板：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oRjCPi71-1679672875240)(C:\Users\86177\AppData\Roaming\Typora\typora-user-images\image-20220502171817759.png)]

1.链式前向星存图：
int head[10000],cnt=0;
struct node{
int y,w,next;
}edge[10000];
void add(int x,int y,int w){edge[++cnt].y=y;edge[cnt].w=w;edge[cnt].next=head[x];head[x]=cnt;
}2.遍历：
for(int i=head[x];i;i=edge[i].next){y=edge[i].y;w=edge[i].w;}#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>using namespace std;typedef pair<int, int> PII; // 第一个存距离，第二个存点的编号const int N = 1000010;
int n, m;
int h[N], w[N], e[N], ne[N], idx; // 使用邻接表存储稀疏图
int dist[N];
bool st[N];void add(int a, int b, int c) {e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}int dijkstra() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;// 定义小根堆//定义：priority_queue<Type, Container, Functional>//Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。		//STL里面默认用的是vector），Functional 就是比较的方式。priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, 1}); // 先将最短的距离添加到小根堆中while (heap.size()) {auto t = heap.top(); // 取出当前已经确定的最短距离的点heap.pop();int ver = t.second;if (st[ver]) continue; // 如果已经被标记过，说明当前的点的边是比较长的重边，直接跳过。st[ver] = true;// 使用当前距离最短的点来更新其出边for (int i = h[ver]; i != -1; i = ne[i]) {int j = e[i]; // j 为 ver 出边所到达的点if (dist[j] > dist[ver] + w[i]) {/* 如果源点直接到 j 点的距离比源点先到 ver 点再从 ver 点到 j 点的距离大，那么就更新 dist[j]，使dist[j] 到源点的距离最短*/dist[j] = dist[ver] + w[i];// 将下一个距离源点最近的点添加到小根堆中heap.push({dist[j], j});}}}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}int main() {scanf("%d%d", &n, &m);memset(h, -1, sizeof h); // 将每一条边的头结点初始化为 -1// 输入 m 条边while (m--) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}cout << dijkstra() << endl;return 0;
}

几何凸包问题模板：

不会：能得分就行，满分要求奇思妙想！！

L3-029 还原文件 (30 分)

//自己的这个思路是循环每一个v[ j ] 记录size 然后从该点开始存到动态数组upda里面存size()个，然后比较两个动态数组是否相等；//26分博主为什么要对输入的每一组标签排序呢 要让最后的纸条最先排队 这是为啥？我感觉没必要啊 可是不加这个样例2就过不了？？
#include<bits/stdc++.h>
using namespace std;
#define N 100100
string str;
char ch;
int n,m,k,d,s;
int x,y,z;
vector<int>v[N];int main(){vector<int>ans;cin>>n;for(int i=0;i<n;i++){cin>>x;ans.push_back(x);}cin>>k;for(int i=1;i<=k;i++){cin>>m;while(m--){cin>>x;v[i].push_back(x);}}vector<int>cur;int vis[N]={0};int len=0;for(int i=0;i<n;i++){//这个还必须是i在这里，因为如果不在这里设置的话，i=n-1；；一直运行；//所以还可以if(i==n-1)break;//95 70 80 97 97 68 58 58 80 72 88 81 81 68 68 60 80//95 70 80for(int j=1;j<=k;j++){if(vis[j]==1)continue;len=v[j].size();vector<int>upda;for(int p=i;p<i+len;p++){upda.push_back(ans[p]);}if(upda==v[j]){cur.push_back(j);vis[j]=1;i=i+len-2;break;}}}for(int i=0;i<cur.size();i++){if(i==0)cout<<cur[i];else cout<<" "<<cur[i];}return 0;
}//30分，真的把循环一倒就30了：
#include<bits/stdc++.h>
using namespace std;
#define N 100100
string str;
char ch;
int n,m,k,d,s;
int x,y,z;
vector<int>v[N];int main(){vector<int>ans;cin>>n;for(int i=0;i<n;i++){cin>>x;ans.push_back(x);}cin>>k;for(int i=1;i<=k;i++){cin>>m;while(m--){cin>>x;v[i].push_back(x);}}vector<int>cur;int vis[N]={0};int len=0;for(int i=0;i<n;i++){//这个还必须是i在这里，因为如果不在这里设置的话，i=n-1；；一直运行；//所以还可以if(i==n-1)break;//95 70 80 97 97 68 58 58 80 72 88 81 81 68 68 60 80//95 70 80for(int j=k;j>=1;j--){if(vis[j]==1)continue;len=v[j].size();vector<int>upda;for(int p=i;p<i+len;p++){upda.push_back(ans[p]);}if(upda==v[j]){cur.push_back(j);vis[j]=1;i=i+len-2;break;}}}for(int i=0;i<cur.size();i++){if(i==0)cout<<cur[i];else cout<<" "<<cur[i];}return 0;
}

No.4 睿抗

初赛：

7-1 懂的都懂 (20 分)【简单 / 暴力 + 哈希表】

7-4 疫情防控 (30 分)【难度: 难 / 并查集 思维】

//超时版本；；#include <bits/stdc++.h>
using namespace std;
#define N 100100
#define inf 0x3f3f3f3f
int x,y,z;
int n,m,s,d,k;
string str;
char ch;
vector<int>v[N];
int flag=0;
int vis[N]={0};
void dfs(int index,int end){vis[index]=1;if(index==end)return;for(int i=0;i<v[index].size();i++){if(vis[v[index][i]]==0){dfs(v[index][i],end);}}
}
int main()
{cin>>n>>m>>d;while(m--){cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}vector<int>lost;int a,b;for(int i=0;i<d;i++){int count=0;cin>>x>>y;lost.push_back(x);while(y--){memset(vis,0,sizeof(vis));for(auto p:lost){vis[p]=1;}cin>>a>>b;//不能到达分两种情况：//第一种就是自己所在或者目的地直接沦陷的if(vis[a]==1 || vis[b]==1){count++;continue;}dfs(a,b);//第二种就是搜索不到的到达不到if(vis[b]==0)count++;}cout<<count<<endl;}return 0;
}

复赛：

7-1 冒险者分队

2022初赛

R5树与二分图

//每条边都是分属于两边；无向图 ； 一个树，求有几个方案 可以变成 二分图 1~N 12 21 一种方案//一开始是没有环的，

//也就是说一开始的树给的初始的是二分图；；

思路：

简单的计数题。注意到一棵树一定是一个二分图，先将其进行黑白染色。则要加入的边连接的两个顶点只能分别属于二分图的左部和右部（即颜色不同）。

在染色时记录颜色为黑色和白色的点的数量，再去掉原有的树边，答案就是（黑点个数*白点个数）-(n–1)。注意答案会超过int的存储范围，需要开long long。

//可以dfs，然后下一个的颜色就是相反的；因为一开始的树是二分树，而深度搜索的话是一个接着一个；
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vector<int>v[N];
int vis[N];
int dist[N];
int cnt1=0,cnt2=0;
void dfs(int index,int color){if(color==1)cnt1++;else cnt2++;vis[index]=1;for(int i=0;i<v[index].size();i++){if(vis[v[index][i]]==0){dfs(v[index][i],-color);}}
}
int main() {cin>>n;//每条边都是分属于两边；无向图  ；  一个树，求有几个方案 可以变成 二分图  1~N  12  21 一种方案//一开始是没有环的，//也就是说一开始的树给的初始的是二分图；；for(int i=1;i<n;i++){cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}dfs(1,1);cout<<cnt1*cnt2-n+1<<endl;return 0;
}//官方结果：
#include <iostream>  using namespace std;  int n;  int head[1000005], nxt[2000005], to[2000005], cnt;  int d[1000005];  int c[1000005];  int sum[2];  void add(int x, int y) {  nxt[++cnt] = head[x];  to[cnt] = y;  head[x] = cnt;  }  void dfs(int cur, int color) {  sum[max(0, c[cur] = color)]++;  for (int i = head[cur]; i != 0; i = nxt[i])  if (c[to[i]] == 0)  dfs(to[i], -color);  }  int main() {  cin >> n;  for (int i = 1; i < n; i++) {  int x, y;  cin >> x >> y;  add(x, y);  add(y, x);  d[x]++;  d[y]++;  }  dfs(1, 1);  cout << 1LL * sum[0] * sum[1] - n + 1 << endl;  return 0;  }  

RC-u3 跑团机器人

思路：

通过字符串处理，计算得到每种面数骰子被加多少个，减多少个，同时将常数项求和。对于求最大最小值，可以通过贪心选择骰子的结果为1或最大值（即为面数）得到。

本文标签： PTA