知识框架
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在这循环为0
count=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==length
if(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;
else
x++;//不是同一个学校的，连续编排
pos[i][j][k]=x;//特别有意思的循环，i学校j队伍中k队员的编号就是x
pre=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]<<" ";
else
cout<<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表示已经累积了多少个6
if(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];
}
//初始化mp
memset(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;
}
else
cout<<" "<<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; //后序序列长度<=0
node* 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);
}
else
sc.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 0x3f3f3f3f
int 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;
//这个一定要赋予初值0
int 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、需要判断的发货顺序的数量K
cin >> 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==length
if(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;
else
x++;//不是同一个学校的，连续编排
pos[i][j][k]=x;//特别有意思的循环，i学校j队伍中k队员的编号就是x
pre=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]<<" ";
else
cout<<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内的必须在判断是否为数字之后，只有在是
//数字的情况下才能使用stoi
if(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表示已经累积了多少个6
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 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 0x3f3f3f3f
int 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;
//这个一定要赋予初值0
int 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;
}
else
cout<<" "<<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; //后序序列长度<=0
node* 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];
//初始化mp
memset(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;
else
disvis[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;
else
timevis[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;
else
vis[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]];
else
cout << "->" << 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 80
for(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 80
for(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 跑团机器人
思路：文章来源：https://www.toymoban.com/news/detail-722387.html
通过字符串处理，计算得到每种面数骰子被加多少个，减多少个，同时将常数项求和。对于求最大最小值，可以通过贪心选择骰子的结果为1或最大值（即为面数）得到。文章来源地址https://www.toymoban.com/news/detail-722387.html
到了这里，关于【PTA】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![【基础算法】[PTA]-找出不是两个数组共有的元素](https://imgs.yssmx.com/Uploads/2024/02/757956-1.gif)
