PTA刷题记录
PTA刷题记录
仓库地址: https://github.com/Haorical/Code/tree/master/PTA/GPLT
两周之内刷完GPLT L2和L3的题，持续更新，包括AK代码，坑点，和少量评论
用一周刷完了l2的40道题
刷题笔记
题目分类
题目
L2-001 紧急救援
简单的dj模板题
#include<bits/stdc++.h> using namespace std; const int N=510; const int INF=0x3fffffff; int n,m,st,ed; int G[N][N]; int d[N],w[N]; bool vis[N]={false}; vector<int> pre[N]; void dj(int s){fill(d,d+N,INF);d[s]=0;for(int i=0;i<n;i++){int u=-1,MIN=INF;for(int j=0;j<n;j++){if(vis[j]==false&&d[j]<MIN){MIN=d[j];u=j;}}if(u==-1) return;vis[u]=true; //又忘了for(int v=0;v<n;v++){if(vis[v]==false){if(d[u]+G[u][v]==d[v]){pre[v].push_back(u);}else if(d[u]+G[u][v]<d[v]){pre[v].clear();pre[v].push_back(u);d[v]=d[u]+G[u][v];}}}} } vector<int> path,tmp; int mv=0,cnt=0; void dfs(int u){if(u==st){cnt++;tmp.push_back(u);int ans=0;for(int i=0;i<tmp.size();i++){ans+=w[tmp[i]];}if(ans>mv){mv=ans;path=tmp;}tmp.pop_back();return;}tmp.push_back(u);for(int i=0;i<pre[u].size();i++){dfs(pre[u][i]);}tmp.pop_back(); }int main(){fill(G[0],G[0]+N*N,INF);cin>>n>>m>>st>>ed;for(int i=0;i<n;i++){cin>>w[i];}int t1,t2,t3;for(int i=0;i<m;i++){cin>>t1>>t2>>t3;G[t1][t2]=G[t2][t1]=t3;}dj(st);dfs(ed);cout<<cnt<<" "<<mv<<endl;for(int i=path.size()-1;i>=0;i--){cout<<path[i];if(i>0) cout<<" ";}system("pause");return 0; }L2-002 链表去重
数组模拟链表，list存储链表
#include<bits/stdc++.h> using namespace std; const int N=100010; struct Node{int cur,next,data; }node[N]; bool flag[N]; vector<Node> l1,l2; int main(){int p,n;cin>>p>>n;int a;for(int i=0;i<n;i++){cin>>a;cin>>node[a].data>>node[a].next;node[a].cur=a;}l1.push_back(node[p]);flag[abs(node[p].data)]=true;p=node[p].next;for(int i=p;i!=-1;){ //巨坑 不要判断节点个数 判断链表下一个地址是不是-1if(flag[abs(node[i].data)]==false){flag[abs(node[i].data)]=true;Node tp=l1.back(); //取最后节点l1.pop_back(); //弹出tp.next=node[i].cur; //更改上个节点的指针l1.push_back(tp);l1.push_back(node[i]);}else{if(!l2.empty()){ //判空Node tp=l2.back();l2.pop_back();tp.next=node[i].cur;l2.push_back(tp);}l2.push_back(node[i]);}i=node[i].next;}for(int i=0;i<l1.size()-1;i++){printf("%05d %d %05d\n",l1[i].cur,l1[i].data,l1[i].next);}Node t1=l1.back();printf("%05d %d %d\n",t1.cur,t1.data,-1);if(!l2.empty()){ //判空for(int i=0;i<l2.size()-1;i++){printf("%05d %d %05d\n",l2[i].cur,l2[i].data,l2[i].next);}t1=l2.back();printf("%05d %d %d",t1.cur,t1.data,-1);}system("pause");return 0; }L2-003 月饼
简单贪心
#include<bits/stdc++.h> using namespace std; const int N=1010; struct Node{double x,y; //测试点3 月饼数量可能为小数double a; }nd[N]; int cmp(Node x,Node y){return x.a>y.a; } int main(){int n;double d; //段错误 int double类型比较造成cin>>n>>d;for(int i=0;i<n;i++){cin>>nd[i].x;}for(int i=0;i<n;i++){cin>>nd[i].y;nd[i].a=1.0*nd[i].y/nd[i].x;}sort(nd,nd+n,cmp);//cout<<nd[0].x;double ans=0;int i=0;while(d>0){if(d>=nd[i].x){n--;d-=nd[i].x;ans+=nd[i].y;}else{ans+=d*nd[i].a;break;d=0;}if(n==0) break;i++;}printf("%.2f",ans);//system("pause");return 0; } //简单贪心L2-004 这是二叉搜索树吗？
// 二叉搜索树 // 代码量比较大 #include<bits/stdc++.h> using namespace std; struct node{int data;node *left,*right; }; void insert(node* &root,int data){if(root==nullptr){root=new node;root->data=data;root->left=root->right=nullptr;return;}if(data<root->data) insert(root->left,data);else insert(root->right,data); } void preOrder(node *root,vector<int> &v){if(root==nullptr) return;v.push_back(root->data);preOrder(root->left,v);preOrder(root->right,v); } void preOrder2(node *root,vector<int> &v){if(root==nullptr) return;v.push_back(root->data);preOrder2(root->right,v);preOrder2(root->left,v); }void postOrder(node *root,vector<int> &v){if(root==nullptr) return;postOrder(root->left,v);postOrder(root->right,v);v.push_back(root->data); }void postOrder2(node *root,vector<int> &v){if(root==nullptr) return;postOrder2(root->right,v);postOrder2(root->left,v);v.push_back(root->data); } int main(){int n;cin>>n;vector<int> v1,v2,v3;node *root=nullptr; //指针定义时一定要赋空指针int data;for(int i=0;i<n;i++){cin>>data;v1.push_back(data);insert(root,data);}preOrder(root,v2);preOrder2(root,v3);if(v1==v2){ //原树的先序遍历cout<<"YES\n";v1.clear();postOrder(root,v1);for(int i=0;i<n;i++){cout<<v1[i];if(i<n-1) cout<<" ";}}else if(v1==v3){ //镜像树的先序遍历cout<<"YES\n";v1.clear();postOrder2(root,v1);//对镜像树后序遍历for(int i=0;i<n;i++){cout<<v1[i];if(i<n-1) cout<<" ";}}else cout<<"NO";system("pause");return 0; }L2-005 集合相似度
// 集合交集 #include<bits/stdc++.h> using namespace std; int main(){int n;cin>>n;vector<set<int>> v(n);for(int i=0;i<n;i++){set<int> s;int t,k;cin>>t;for(int j=0;j<t;j++){cin>>k;s.insert(k);}v[i]=s;}int m;cin>>m;set<int> s1,s2;for(int j=0;j<m;j++){s1.clear(); //一定clears2.clear();int t1,t2;cin>>t1>>t2;t1--,t2--;set_intersection(v[t1].begin(),v[t1].end(),v[t2].begin(),v[t2].end(),inserter(s1,s1.begin())); //集合函数用法// set_union(v[t1].begin(),v[t1].end(),v[t2].begin(),v[t2].end(),inserter(s2,s2.begin())); int nc=s1.size(),nt=v[t1].size()+v[t2].size()-nc; //不用union就不会超时了double ans=1.0*nc/nt*100; //乘1.0printf("%.2f%%\n",ans);}system("pause");return 0; }L2-006 树的遍历
#include<bits/stdc++.h> using namespace std; const int N=50; struct node{int data;node *left,*right; }; int pre[N],in[N],post[N]; int n; node* create(int postL,int postR,int L,int R){ //建立二叉树if(postL>postR) return nullptr;node *root=new node;root->data=post[postR]; //后序数组最后是根节点int k;for(k=L;k<=R;k++){ //在中序遍历中查找根节点if(in[k]==post[postR]){break;}}int numLeft=k-L;//左子树节点个数 //postR 和 k 是根节点， 不包含root->left=create(postL,postL+numLeft-1,L,k-1); //建立左子树 更新中序R=k-1root->right=create(postL+numLeft,postR-1,k+1,R);//建立右子树 更新中序L=k+1return root; } int num=0; void bfs(node *root){queue<node*> q;q.push(root);while(!q.empty()){node* now=q.front();q.pop();num++;cout<<now->data;if(num<n) cout<<" ";if(now->left!=nullptr) q.push(now->left); //注意判空if(now->right!=nullptr) q.push(now->right);} } 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);system("pause");return 0; }L2-007 家庭房产
L2-008 最长对称子串
#include<bits/stdc++.h> using namespace std; const int N=1010; char a[N]; int main(){cin.getline(a,N);int l=strlen(a);int ans=0;for(int i=0;i<l;i++){//奇数for(int j=0;i-j>=0&&i+j<l;j++){if(a[i-j]!=a[i+j]) break;ans=max(ans,2*j+1);}//偶数for(int j=0;i-j>=0&&i+j+1<l;j++){if(a[i-j]!=a[i+j+1]) break;ans=max(ans,2*j+2);}}cout<<ans;system("pause");return 0; }L2-009 抢红包
//简单结构体排序 #include<bits/stdc++.h> using namespace std; const int N=1e4+10; struct node{int id,cnt;int y; }nd[N]; int cmp(node a,node b){if(a.y==b.y){if(a.cnt==b.cnt){return a.id<b.id;}else return a.cnt>b.cnt;}else return a.y>b.y; } int main(){int n;cin>>n;int k;for(int i=1;i<=n;i++){nd[i].id=i;cin>>k;int t1,t2;for(int j=0;j<k;j++){cin>>t1>>t2;nd[t1].id=t1;nd[t1].y+=t2;nd[t1].cnt++;nd[i].y-=t2;}}sort(nd+1,nd+n+1,cmp);for(int i=1;i<=n;i++){printf("%d %.2f",nd[i].id,1.0*nd[i].y/100);if(i<=n-1) cout<<endl;}system("pause");return 0; }L2-010 排座位
//感觉是并查集，就是并查集 #include<bits/stdc++.h> using namespace std; const int N=110; int f[N]; int flag[N][N]; int Find(int x){if(x==f[x]) return x;int a=Find(f[x]);return a; } void Union(int a,int b){a=Find(a); b=Find(b);if(a!=b) f[a]=b; //容易错 } int main(){int n,m,k;cin>>n>>m>>k;for(int i=1;i<=n;i++){f[i]=i;}int t1,t2,t3;for(int i=0;i<m;i++){cin>>t1>>t2>>t3;if(t3==1) Union(t1,t2);else flag[t1][t2]=flag[t2][t1]=1;}for(int i=0;i<k;i++){cin>>t1>>t2;//cout<<Find(t1)<<" "<<Find(t2)<<endl;if(Find(t1)==Find(t2)&&flag[t1][t2]!=1) cout<<"No problem";else if(Find(t1)!=Find(t2)&&flag[t1][t2]!=1) cout<<"OK";else if(Find(t1)==Find(t2)&&flag[t1][t2]==1) cout<<"OK but...";else cout<<"No way";if(i<k-1) cout<<endl;}system("pause");return 0; }L2-011 玩转二叉树
// 也是建树，和6题差不多，一遍过 #include<bits/stdc++.h> using namespace std; const int N=50; struct node {int data;node *left,*right; };int pre[N],in[N],n;node* create(int pl,int pr,int l,int r){if(pl>pr) return nullptr; //return条件node *root=new node;root->data=pre[pl];int k;for(k=l;k<=r;k++){if(in[k]==pre[pl]) break;}int len=k-l;root->right=create(pl+1,pl+len,l,k-1);root->left=create(pl+len+1,pr,k+1,r);return root; } int num=0; void bfs(node* root){queue<node*> q;q.push(root);while(!q.empty()){node *now=q.front();q.pop();cout<<now->data;num++;if(num<n) cout<<" ";if(now->left!=nullptr) q.push(now->left);if(now->right!=nullptr) q.push(now->right);} } int main(){cin>>n;for(int i=0;i<n;i++){cin>>in[i];}for(int i=0;i<n;i++){cin>>pre[i];}node *root=create(0,n-1,0,n-1);bfs(root);system("pause");return 0; }L2-012 关于堆的判断
L2-013 红色警报
并查集实现
// 并查集通过查祖宗节点可以找到有几个集合，用来查连通块数量很好用 // 改成循环还是段错误，数组开小了 // 尝试搜索，csdn都用的dfs,不过bfs不是用来求连通块更好用吗？？？ #include<bits/stdc++.h> using namespace std; const int N=510; int n,m; bool vis[N]={false}; int f[N]; struct node{int x,y; }nd[10*N];//这里开小了，应该按m道路条数最大值开，不用城市数开。 void init(){for(int i=0;i<n;i++){f[i]=i;} } int findf(int x){int t=x;while(t!=f[t]){t=f[t];}int a=x;while(f[a]!=t){int z=a;f[z]=t;a=f[z];}return t;// if(x==f[x]) return x;// f[x]=findf(f[x]);// return f[x]; } void Union(int a,int b){a=findf(a);b=findf(b);if(a!=b) f[a]=b; } int count(){int cnt=0;for(int i=0;i<n;i++){if(f[i]==i&&vis[i]==false){cnt++;}}return cnt; } int main(){cin>>n>>m;init();for(int i=0;i<m;i++){cin>>nd[i].x>>nd[i].y;Union(nd[i].x,nd[i].y);}int cnt1=count(),cnt2=0,cnt3=0;int k,u;cin>>k;while(k--){cin>>u;cnt3++;vis[u]=true;init();//每次都要初始化for(int i=0;i<m;i++){if(!vis[nd[i].x]&&!vis[nd[i].y]) Union(nd[i].x,nd[i].y);}cnt2=count();if(cnt1<cnt2) printf("Red Alert: City %d is lost!",u);else printf("City %d is lost.",u);cnt1=cnt2; //集合个数每次都要更新if(k>0) cout<<'\n';if(cnt3==n) printf("\nGame Over.");}system("pause");return 0; }bfs实现
//尝试bfs搜索实现,我太nb了,一遍过 #include<bits/stdc++.h> using namespace std; const int N=510; vector<int> v[N],lost; bool inq[N]={false}; int n,m,k,u; void bfs(int x){queue<int> q;q.push(x);inq[x]=true; //inq队列，判断是否入过队，约等于有没有访问过while(!q.empty()){int now=q.front();q.pop();for(int i=0;i<v[now].size();i++){if(inq[v[now][i]]==false){q.push(v[now][i]);inq[v[now][i]]=true;}}} } int main(){cin>>n>>m;int t1,t2;for(int i=0;i<m;i++){cin>>t1>>t2;v[t1].push_back(t2);v[t2].push_back(t1);}int sum=0;for(int i=0;i<n;i++){if(inq[i]==false){sum++;bfs(i);}}memset(inq,0,sizeof(inq));cin>>k;int ans,cnt3=0;while(k--){cnt3++;cin>>u;ans=0;memset(inq,0,sizeof(inq));//每次初始化lost.push_back(u);for(int i=0;i<lost.size();i++){inq[lost[i]]=true;//从lost里给inq赋初值}for(int i=0;i<n;i++){if(inq[i]==false){ans++;bfs(i);}}if(sum<ans) printf("Red Alert: City %d is lost!",u);else printf("City %d is lost.",u);sum=ans;if(k>0) cout<<'\n';if(cnt3==n) printf("\nGame Over.");}system("pause");return 0; }L2-014 列车调度
//类似模拟，维护了一个最小值集合的队列 //lower_bound查找>=目标第一个元素 upper_bound > //这里用upper_bound #include<bits/stdc++.h> using namespace std; vector<int> v; int main(){int n;cin>>n;int t,cnt=0;for(int i=0;i<n;i++){cin>>t;// 性质决定肯定是有序的，直接upper_bound看有没有更大中的最小值vector<int>::iterator it=upper_bound(v.begin(),v.end(),t); if(it==v.end()){v.push_back(t);//没有直接插进去cnt++;}else{int j=it-v.begin();//有就替换掉v[j]=t;}}cout<<cnt;system("pause");return 0; }L2-015 互评成绩
// 简单模拟 #include<bits/stdc++.h> using namespace std; const int N=1e4+10; int a[N]; int n,k,m; int main(){cin>>n>>k>>m;for(int i=0;i<n;i++){int t1=100,t2=0,t;for(int j=0;j<k;j++){cin>>t;a[i]+=t;t1=min(t1,t);t2=max(t2,t);}a[i]-=(t1+t2); //天才做法}sort(a,a+n,greater<int>());for(int i=m-1;i>=0;i--){double d=1.0*a[i]/(k-2);printf("%.3f",d);if(i>0) cout<<' ';}system("pause");return 0; }L2-016 愿天下有情人都是失散多年的兄妹
//初看并查集？实际搜索，类似连通块 // 尝试bfs,实际上dfs更简洁 // 用下标表示id的时候，空间尽可能大 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; bool inq[N]={false}; int n,k; vector<int> v1,v2; struct node{int sex;int step;int fid,mid; }nd[N]; vector<int> bfs(int x){ //标准bfsqueue<int> q;vector<int> v;v.push_back(x);q.push(x);nd[x].step=1;while (!q.empty()){int now=q.front();q.pop();if(nd[now].step==5) break;if(inq[nd[now].fid]==false&&nd[now].fid!=-1){q.push(nd[now].fid);inq[nd[now].fid]=true;nd[nd[now].fid].step=nd[now].step+1;v.push_back(nd[now].fid);}if(inq[nd[now].mid]==false&&nd[now].mid!=-1){q.push(nd[now].mid);inq[nd[now].mid]=true;nd[nd[now].mid].step=nd[now].step+1;v.push_back(nd[now].mid);}}return v; } int main(){cin>>n;int t1,t2,t3;char s;for(int i=0;i<N;i++){nd[i].fid=nd[i].mid=-1;//全部初始化为-1}for(int i=0;i<n;i++){cin>>t1>>s>>t2>>t3;nd[t1].sex=(s=='M'?1:0);nd[t1].fid=t2;if(t2!=-1) nd[t2].sex=1; //要标记父母性别nd[t1].mid=t3;if(t3!=-1) nd[t3].sex=0;}cin>>k;while(k--){cin>>t1>>t2;if(nd[t1].sex==nd[t2].sex){cout<<"Never Mind";}else{memset(inq,0,sizeof(inq));v1=bfs(t1); //t1的5代所有人memset(inq,0,sizeof(inq));v2=bfs(t2); //t2 5代所有人set<int> s;int l1=v1.size();int l2=v2.size();for(int i=0;i<l1;i++){s.insert(v1[i]);}for(int i=0;i<l2;i++){s.insert(v2[i]);}if(l1+l2==s.size()) cout<<"Yes"; //有重复的一去重大小会变else cout<<"No";}if(k>0) cout<<'\n';} // system("pause");return 0; }L2-017 人以群分
// 思维题 sort会用就能过 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N]; int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1); //注意是否是0开始for(int i=1;i<=n;i++){a[i]+=a[i-1];}int aa,diff;if(n&1){aa=n/2;diff=a[n]-2*a[aa];}else{aa=n/2;diff=a[n]-2*a[aa];if(a[n]-2*a[aa+1]>diff){diff=a[n]-2*a[aa+1];aa++;}}printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d",n-aa,aa,diff);system("pause");return 0; }L2-018 多项式A除以B
L2-019 悄悄关注
//简单模拟 #include<bits/stdc++.h> using namespace std; const int N=5e3+10; set<string> s; vector<string> v,v1; map<string,int> m; int main(){int n;string t1;cin>>n;for(int i=0;i<n;i++){cin>>t1;s.insert(t1);}int k;cin>>k;int zz=k;int t2,sum=0;while(k--){cin>>t1>>t2;v.push_back(t1);m[t1]=t2;sum+=t2;}for(int i=0;i<zz;i++){int s1=s.size();s.insert(v[i]);int s2=s.size();if(s2>s1&&zz*m[v[i]]>sum){v1.push_back(v[i]);}}if(v1.size()==0) cout<<"Bing Mei You";else{sort(v1.begin(),v1.end());for(int i=0;i<v1.size();i++){cout<<v1[i]<<endl;}}system("pause");return 0; } # 用python很简单，但是最后一个样例超时了，我也不会优化，换成c++ a=input().split() n=int(a[0]) del(a[0]) sum=0 k=int(input()) l1=[] d1={} for i in range(k):t1,t2=input().split()l1.append(t1)d1[t1]=int(t2)sum+=int(t2) sum=sum/k l2=[] for i in l1:if i not in a and d1[i]>sum:l2.append(i) l2.sort() for i in l2:print(i,end=' ')L2-020 功夫传人
// 并查集变形？ #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int s[N]; int height[N]; int finds(int x){if(x==0) return 0;if(height[x]==0) height[x]=finds(s[x])+1; //记忆化搜索，没有的话，最后一个点会超时return height[x]; } int main(){int n;double z,r;cin>>n>>z>>r;int k,t;double ans=0;for(int i=0;i<n;i++){cin>>k;if(k==0){cin>>t;int sh=finds(i);double d=z*pow(1-r/100,sh)*t;ans+=d;} else{for(int j=0;j<k;j++){cin>>t;s[t]=i;}}}cout<<int(ans);system("pause");return 0; }L2-021 点赞狂魔
// 热身赛原题，考试时做出来了，结构体排序 #include<bits/stdc++.h> using namespace std; const int N=110; struct node{string name;int cnt;int avg; }nd[N]; int cmp(node x,node y){if(x.cnt==y.cnt) return x.avg<y.avg; else return x.cnt>y.cnt; } int main(){int n,k,t;set<int> s;cin>>n;for(int i=0;i<n;i++){s.clear();cin>>nd[i].name;cin>>k;for(int j=0;j<k;j++){cin>>t;s.insert(t);}nd[i].cnt=s.size();nd[i].avg=k-nd[i].cnt;}sort(nd,nd+n,cmp);if(n==1) cout<<nd[0].name<<" - -";//容易少写else if(n==2) cout<<nd[0].name<<' '<<nd[1].name<<" -";else cout<<nd[0].name<<' '<<nd[1].name<<' '<<nd[2].name;return 0; }L2-022 重排链表
L2-023 图着色问题
//初看比较唬人，实际考图邻接表存储 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int v,e,k; vector<int> g[N]; set<int> sss; int color[N]; int main(){cin>>v>>e>>k;int t1,t2;for(int i=0;i<e;i++){cin>>t1>>t2;g[t1].push_back(t2);g[t2].push_back(t1);}int n;cin>>n;while(n--){memset(color,0,sizeof(color));sss.clear();// 记得clearint flag=0;for(int j=1;j<=v;j++){cin>>color[j];sss.insert(color[j]);}if(sss.size()!=k) flag=1; // 必须就这几个颜色多了少了都不行if(!flag)for(int j=1;j<=v;j++){if(flag) break;int len=g[j].size();for(int t=0;t<len;t++){if(color[j]==color[g[j][t]]){flag=1;break;}}} if(flag) cout<<"No"; // 注意yes no大小写else cout<<"Yes";if(n>0) cout<<endl;}system("pause");return 0; }L2-024 部落
//基础并查集 #include<bits/stdc++.h> using namespace std; const int N=1e4+10; int f[N],n=0; bool vis[N]={false}; int findf(int x){if(x==f[x]) return x;f[x]=findf(f[x]);return f[x]; } void unionf(int a,int b){a=findf(a);b=findf(b);if(a!=b) f[a]=b; }void init(){for(int i=1;i<N;i++){f[i]=i;} }int cnt(){int count=0;for(int i=1;i<=n;i++){if(f[i]==i&&vis[i]) count++;}return count; } int main(){int k,t1,t2,t3;init();cin>>k;while(k--){cin>>t1>>t2;vis[t2]=true;t1--;n=max(n,t2);while(t1--){cin>>t3;n=max(n,t3); //忘了写1 4测试点没过vis[t3]=true;unionf(t2,t3);}}int sum=0;for(int i=1;i<=n;i++){if(vis[i]) sum++; }cout<<sum<<' '<<cnt()<<endl;cin>>t1;while(t1--){{cin>>t2>>t3;if(findf(t2)==findf(t3)) cout<<'Y';else cout<<'N';if(t1>0) cout<<'\n';}}system("pause");return 0; }L2-025 分而治之
// 和13红色警戒那题差不多，求连通块，并查集，搜索都可以做 // 这里用的并查集码量少 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int f[N],n,m; bool vis[N]={false}; struct node{int x,y; }nd[N]; void init(){for(int i=1;i<=n;i++){f[i]=i;} } int count(){int cnt=0;for(int i=1;i<=n;i++){if(!vis[i]&&f[i]==i) cnt++;}return cnt; } int findf(int x){if(x==f[x]) return x;f[x]=findf(f[x]);return f[x]; } void unionf(int a,int b){a=findf(a);b=findf(b);if(a!=b) f[a]=b; }int main(){cin>>n>>m;int t1,t2;for(int i=0;i<m;i++){cin>>t1>>t2;nd[i].x=t1;nd[i].y=t2;}int k;cin>>k;while(k--){memset(vis,0,sizeof(vis));init();int t3;cin>>t3;for(int i=0;i<t3;i++){cin>>t2;vis[t2]=true;}for(int i=0;i<m;i++){if(!vis[nd[i].x]&&!vis[nd[i].y]) unionf(nd[i].x,nd[i].y);}int sum1=count();//cout<<sum0<<" "<<t3<<" "<<sum1<<endl;if(t3+sum1==n) cout<<"YES"; //这里第一次判断错了else cout<<"NO";if(k>0) cout<<endl;}system("pause");return 0; }L2-026 小字辈
// 记忆化搜索 和20题差不多 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int f[N],c[N]; vector<int> v[N]; int dfs(int s){if(s==-1) return 0;if(c[s]==-1) c[s]=dfs(f[s])+1;return c[s]; } int main(){int n,t;cin>>n;memset(c,-1,sizeof(c));for(int i=1;i<=n;i++){cin>>t;f[i]=t;}int sum=0;for(int i=1;i<=n;i++){if(c[i]==-1){c[i]=dfs(i);sum=max(sum,c[i]);v[c[i]].push_back(i);} }cout<<sum<<endl;int len=v[sum].size();for(int i=0;i<len;i++){cout<<v[sum][i];if(i<len-1) cout<<' ';}system("pause");return 0; }L2-027 名人堂与代金券
// 记忆化搜索 和20题差不多 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int f[N],c[N]; vector<int> v[N]; int dfs(int s){if(s==-1) return 0;if(c[s]==-1) c[s]=dfs(f[s])+1;return c[s]; } int main(){int n,t;cin>>n;memset(c,-1,sizeof(c));for(int i=1;i<=n;i++){cin>>t;f[i]=t;}int sum=0;for(int i=1;i<=n;i++){if(c[i]==-1){c[i]=dfs(i);sum=max(sum,c[i]);v[c[i]].push_back(i);} }cout<<sum<<endl;int len=v[sum].size();for(int i=0;i<len;i++){cout<<v[sum][i];if(i<len-1) cout<<' ';}system("pause");return 0; }L2-028 秀恩爱分得快
// 模拟 太恶心了，挂了几个测试点，考试的时候我绝对不会改的 // 得用字符串存，正确的我放后面了 // #include<bits/stdc++.h> // using namespace std; // const int N=2010; // double a[N][N]; // int tp[N]; // int main(){ // int n,m,k; // cin>>n>>m; // while(m--){ // cin>>k; // memset(tp,0,sizeof(tp)); // for(int i=0;i<k;i++){ // cin>>tp[i]; // } // double tt=1.0/k; // for(int i=0;i<k;i++){ // for(int j=i+1;j<k;j++){ // if(tp[i]*tp[j]<0 || (tp[i]==0&&tp[j]<0) || (tp[i]<0&&tp[j]==0)) { // a[tp[i]+1000][tp[j]+1000]+=tt; // a[tp[j]+1000][tp[i]+1000]+=tt; // } // } // } // } // int t1,t2; // cin>>t1>>t2; // vector<int> v1,v2; // double MAX,MAX1,MAX2; // MAX=MAX1=MAX2=a[t1+1000][t2+1000]; // for(int i=0;i<N;i++){ // if(a[t1+1000][i]>MAX1){ // MAX1=a[t1+1000][i]; // v1.clear(); // v1.push_back(i-1000); // }else if(a[t1+1000][i]==MAX1){ // v1.push_back(i-1000); // } // }// for(int i=0;i<N;i++){ // if(a[t2+1000][i]>MAX2){ // MAX2=a[t2+1000][i]; // v2.clear(); // v2.push_back(i-1000); // }else if(a[t2+1000][i]==MAX2){ // v2.push_back(i-1000); // } // } // if(MAX1==MAX2&&MAX==MAX1) cout<<t1<<' '<<t2; // else{ // if(t1>0) sort(v1.begin(),v1.end(),greater<int>()); // else sort(v1.begin(),v1.end()); // if(t2>0) sort(v2.begin(),v2.end(),greater<int>()); // else sort(v2.begin(),v2.end()); // for(auto i:v1) cout<<t1<<' '<<i<<endl; // for(auto i:v2) cout<<t2<<' '<<i<<endl; // } // system("pause"); // return 0; // }//AC #include<bits/stdc++.h> using namespace std; bool cmp(int a, int b){if(abs(a)==1000)return true;if(abs(b)==1000)return false;return abs(a)<abs(b); } int main(){//inputint n, m, sex[1010]={0};cin>>n>>m;vector<vector<int>>photo(m);for(int i = 0; i < m; i++){int k; cin>>k;for(int j = 0; j < k; j++){string s; cin>>s;if(s=="0")s="1000";if(s=="-0")s="-1000";int tmp = stoi(s);photo[i].push_back(tmp);sex[abs(tmp)] = tmp;}}int cp[3];for(int i = 1; i <= 2; i++){string s; cin>>s;if(s=="0")s="1000";if(s=="-0")s="-1000";cp[i] = stoi(s);}//Search Photodouble love[1010] = {0};for(int c = 1; c <= 2; c++){for(int i = 0; i < m; i++){//Find CPint ok = 0;for(int j = 0; j < photo[i].size(); j++){if(photo[i][j]==cp[c]){ok = 1;break;}}//Add Loveif(ok){for(int j = 0; j < photo[i].size(); j++){if(cp[c]*photo[i][j]<0){love[abs(photo[i][j])] += 1.0/photo[i].size();}}}}}//Count maxlovedouble maxx[3] = {0};vector<vector<int> >ans(3);for(int c = 1; c <= 2; c++){for(int i = 1; i <= 1000; i++){if(cp[c]*sex[i]<0){if(love[i]>maxx[c]){maxx[c] = love[i];ans[c].clear();ans[c].push_back(sex[i]);}else if(love[i]==maxx[c]){ans[c].push_back(sex[i]);}}}}//cout<<ans[1].size()<<" "<<ans[2].size()<<endl;//outputif(maxx[1]==love[abs(cp[2])] && maxx[2]==love[abs(cp[1])]){string s1 = to_string(cp[1]), s2 = to_string(cp[2]);if(cp[1]==1000)s1="0";if(cp[1]==-1000)s1="-0";if(cp[2]==1000)s2="0";if(cp[2]==-1000)s2="-0";cout<<s1<<" "<<s2<<endl;return 0;}for(int c = 1; c <= 2; c++){sort(ans[c].begin(), ans[c].end(),cmp);for(int i = 0; i < ans[c].size(); i++){string s1 = to_string(cp[c]), s2 = to_string(ans[c][i]);if(cp[c]==1000)s1 = "0";if(cp[c]==-1000)s1 = "-0";if(ans[c][i]==1000)s2 = "0";if(ans[c][i]==-1000)s2 = "-0";cout<<s1<<" "<<s2<<endl;}}return 0; }L2-029 特立独行的幸福
#include<bits/stdc++.h> using namespace std; const int N=1e4+10; int l,r; bool vis[N]={false}; bool vis2[N]={false};//设置两个vis数组 vector<int> v[N]; bool isprime(int x){if(x==1) return false;for(int i=2;i<=sqrt(x);i++){if(x%i==0) return false;}return true; } int f(int x){int ans=0;while(x){ans+=((x%10)*(x%10));x/=10;}return ans; } int judge(int x){int t=x;set<int> s;int pre;while(1){pre=s.size();s.insert(x);if(s.size()==pre) return false;if(x==1) return true;x=f(x);v[t].push_back(x);vis[x]=true; //被求出来的一定是不独立的，标记} } int main(){cin>>l>>r;for(int i=l;i<=r;i++){vis2[i]=judge(i); //先全判断一边}int flag=0;for(int i=l;i<=r;i++){if(!vis[i]&&vis2[i]){flag=1;int len=v[i].size();cout<<i<<' '<<(isprime(i)?len*2:len)<<endl;}}if(!flag) cout<<"SAD";system("pause");return 0; }L2-030 冰岛人
#include<bits/stdc++.h> using namespace std; struct people{char sex;string father; }; unordered_map<string,people> p; int judge(string a,string b){int i=1,j;for(string A=a;!A.empty();A=p[A].father,i++){j=1;for(string B=b;!B.empty();B=p[B].father,j++){if(i>=5&&j>=5) return 1;if(A==B&&(i<5||j<5)) return 0;}}return 1; } int main(){int n,m;string str,a,b;cin>>n;for(int i=0;i<n;i++){cin>>a>>b;// 先名后姓// male 男 female 女if(b.back()=='n') p[a]={'m',b.substr(0,b.size()-4)};else if(b.back()=='r') p[a]={'f',b.substr(0,b.size()-7)}; // b.size() b.length not sizeof(b)else p[a].sex=b.back();}cin>>m;for(int i=0;i<m;i++){cin>>a>>str>>b>>str; // 姓没用if(p.find(a)==p.end()||p.find(b)==p.end()) cout<<"NA\n"; //find 约等于map自带else if(p[a].sex==p[b].sex) cout<<"Whatever\n";else cout<<(judge(a,b)?"Yes\n":"No\n");}system("pause");return 0; }// cin >> m;// for (int i = 0; i < m; i++) {// cin >> a >> str >> b >> str; //姓氏没有用// if (people.find(a) == people.end() || people.find(b) == people.end()) printf("NA\n");// else if (people[a].sex == people[b].sex) printf("Whatever\n");// else printf("%s\n", judge(a, b) ? "Yes" : "No");// }L2-031 深入虎穴
// 很直白的搜索 dfs bfs差不多 记忆化搜索。。 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; // vector<int> v[N]; // 貌似一个pre数组就可以 对每个节点遍历深度 int pre[N]; // 先找入口 用pre的话,入口都不用找 int height[N];int geth(int s){if(s==-1) return 0;if(height[s]==0) height[s]=geth(pre[s])+1;return height[s]; }int main(){int n;memset(pre,-1,sizeof(pre));cin>>n;int k,t;for(int i=1;i<=n;i++){cin>>k;while(k--){cin>>t;pre[t]=i;}}int u=-1,MAX=-1;for(int i=1;i<=n;i++){if(geth(i)>MAX){MAX=geth(i);u=i;}}cout<<u;system("pause");return 0; }L2-032 彩虹瓶
// 初看栈使用 数据比较弱 #include<bits/stdc++.h> using namespace std; const int N=1e3+10; int a[N];int main(){int n,m,k;cin>>n>>m>>k;while(k--){stack<int> s; //stack没有clear 直接重新定义int flag=0;memset(a,0,sizeof(a));int t1=1,t2;int cnt1=0;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){t2=a[i];if(t2==t1){t1++;while(!s.empty()&&s.top()==t1){s.pop();t1++;}}else{s.push(t2);if(s.size()>m){ // 把=改成>就过了 下面写的都是对的flag=1;break;}}// int t3=-1;// if(!s.empty()) t3=s.top();// while(t3==t1){// t1++;// s.pop(); // pop之后size要-1// cnt1--;// if(s.empty()) break;// t3=s.top();// }}if(flag){ cout<<"NO"<<endl; continue;}if(t1==n+1) cout<<"YES"<<endl;else cout<<"NO"<<endl;}system("pause");return 0; }L2-033 简单计算器
// 栈基础 #include<bits/stdc++.h> using namespace std; int n; stack<int> s1; stack<char> s2; int main(){cin>>n;int t1,d1,d2;char t2;for(int i=0;i<n;i++){cin>>t1;s1.push(t1);}for(int i=0;i<n-1;i++){cin>>t2;s2.push(t2);}while (!s2.empty()){d1=s1.top();s1.pop();d2=s1.top();s1.pop();t2=s2.top();s2.pop();if(t2=='+') s1.push(d1+d2);if(t2=='-') s1.push(d2-d1);if(t2=='*') s1.push(d1*d2);if(t2=='/') {if(d1==0){printf("ERROR: %d/0",d2); return 0;} s1.push(d2/d1); }}cout<<s1.top();system("pause");return 0; }L2-034 口罩发放
L2-035 完全二叉树的层序遍历
//完全二叉树直接数组存 #include<bits/stdc++.h> using namespace std; int n; int tree[40]; void creat(int root){if(root>n) return; //注意递归结束条件creat(root*2);creat(root*2+1);cin>>tree[root]; } int main(){cin>>n;creat(1);for(int i=1;i<=n;i++){cout<<tree[i];if(i<n) cout<<' ';}system("pause");return 0; }L2-036 网红点打卡攻略
// 模拟 #include<bits/stdc++.h> using namespace std; const int N=210; int cost[N][N],r[N]; int main(){int n,m;cin>>n>>m;int t1,t2,t3;for(int i=0;i<m;i++){cin>>t1>>t2>>t3;cost[t1][t2]=cost[t2][t1]=t3;}int k;cin>>k;int MIN=0x3fffffff,u=-1,cnt=0;for(int i=1;i<=k;i++){set<int> s;int flag=0;cin>>t1;memset(r,-1,sizeof(r));r[0]=0;for(int j=1;j<=t1;j++){cin>>r[j]; //标错下标了}r[t1+1]=0; //这里设置了结束后面就不用判断了int ans=0;for(int j=0;j<=t1;j++){// cout<<r[j]<<' '<<r[j+1]<<endl;if(cost[r[j]][r[j+1]]==0){// cout<<cost[r[j]][r[j+1]]<<endl;flag=1;break;}// cout<<cost[r[j]][r[j+1]]<<endl;ans+=cost[r[j]][r[j+1]];int pre=s.size();s.insert(r[j]);if(s.size()==pre){flag=1;break;}}if(flag||s.size()!=n+1||cost[r[t1]][0]==0) continue;cnt++;if(ans<MIN){MIN=ans;u=i;}}cout<<cnt<<'\n'<<u<<' '<<MIN;system("pause");return 0; }L2-037 包装机
// 栈、队列 #include<bits/stdc++.h> using namespace std; queue<int> q[110]; stack<int> st; map<char,int> mp; vector<int> v; void init(){for(int i=0;i<26;i++){mp[i+'A']=i;} } int main(){int n,m,s;string str;init();cin>>n>>m>>s;for(int i=1;i<=n;i++){cin>>str;for(int j=0;j<m;j++){// cout<<mp[str[j]]<<endl;q[i].push(mp[str[j]]);}}int t,t1,t2;while(cin>>t){if(t==-1) break;if(t==0){if(!st.empty()) // 记得判空即可{t2=st.top();st.pop();v.push_back(t2);}}else{if(!q[t].empty()){ // 判空t1=q[t].front();q[t].pop();if(st.size()==s){t2=st.top();st.pop();v.push_back(t2);}st.push(t1);}}}for(int i=0;i<v.size();i++){cout<<char(v[i]+'A');}system("pause");return 0; }L2-038 病毒溯源
// 一个pre数组的事 记忆化搜索 // vector 重载 < 直接用 #include<bits/stdc++.h> using namespace std; const int N=1e4+10; int pre[N]; int height[N]; int u=-1,MAX=-1; vector<int> vv;int geth(int s){if(s==-1) return 0;if(height[s]==0) height[s]=geth(pre[s])+1;return height[s]; }void dfs(int s,vector<int>& _v){if(s==-1) return;dfs(pre[s],_v);_v.push_back(s); }int main(){int n,t1,t2;memset(pre,-1,sizeof(pre));cin>>n;for(int i=0;i<n;i++){cin>>t1;for(int j=0;j<t1;j++){cin>>t2;pre[t2]=i;}}for(int i=0;i<n;i++){if(geth(i)>MAX){MAX=geth(i);vv.clear();vv.push_back(i);}else if(geth(i)==MAX){vv.push_back(i);}}cout<<MAX<<endl;vector<vector<int>> ans;for(int i=0;i<vv.size();i++){vector<int> v;dfs(vv[i],v);ans.push_back(v);}sort(ans.begin(),ans.end());vector<int> v=ans[0];for(int i=0;i<ans[0].size();i++){cout<<ans[0][i];if(i<ans[0].size()-1) cout<<' ';}system("pause");return 0; }L2-039 清点代码库
// map vector // map pair类型变量 类似结构体 // 用结构题存map 重载<排序 vector自带< #include<bits/stdc++.h> using namespace std; map<vector<int>,int> mp; // 只能用来统计数量，不能重载运算符 // 重新用node来保存 struct node {vector<int> v;int cnt; };vector<int> v;int cmp(node x,node y){if(x.cnt==y.cnt) return x.v<y.v;else return x.cnt>y.cnt; } vector<node> ans; int main(){int n,m,t;cin>>n>>m;for(int i=0;i<n;i++){v.clear();for(int j=0;j<m;j++){cin>>t;v.push_back(t);}mp[v]++;}for(auto i:mp){node tn;tn.v=i.first;tn.cnt=i.second;ans.push_back(tn);}cout<<ans.size()<<endl;sort(ans.begin(),ans.end(),cmp);for(int i=0;i<ans.size();i++){cout<<ans[i].cnt;for(int j=0;j<m;j++){cout<<' '<<ans[i].v[j];}cout<<endl;}system("pause");return 0; }L2-040 哲哲打游戏
// 简单模拟 #include<bits/stdc++.h> using namespace std; const int N=1e5+10; vector<int> v[N]; int ad[N]; int main(){int n,m,k,t;cin>>n>>m;for(int i=1;i<=n;i++){cin>>k;for(int j=0;j<k;j++){cin>>t;v[i].push_back(t);}}int p,q;int now=1;for(int j=0;j<m;j++){cin>>p>>q;if(p==0){now=v[now][q-1];}if(p==1){ad[q]=now;cout<<now<<endl;}if(p==2){now=ad[q];}if(j==m-1) cout<<now;}system("pause");return 0; }L3-001 凑零钱
L3-002 特殊堆栈
L3-003 社交集群
L3-004 肿瘤诊断
L3-005 垃圾箱分布
L3-006 迎风一刀斩
L3-007 天梯地图
L3-008 喊山
L3-009 长城
L3-010 是否完全二叉搜索树
// BST建立并判断完全二叉树 #include<bits/stdc++.h> using namespace std; int n; int maxn=1; struct node{int nid; //用nid来模拟数组存数的下标int data;node *left,*right; }; void insert(node* &root,int data){if(root==nullptr){root=new node;root->data=data;root->left=root->right=nullptr;return; // 记得return}if(data>root->data) insert(root->left,data);else insert(root->right,data); }int ans=0; void bfs(node* root){queue<node*> q;root->nid=1;q.push(root);while (!q.empty()){node *now=q.front();q.pop();cout<<now->data;ans++;if(ans<n) cout<<' ';if(now->left!=nullptr){ q.push(now->left);now->left->nid=now->nid*2; //nid*2maxn=max(now->left->nid,maxn);}if(now->right!=nullptr){q.push(now->right);now->right->nid=now->nid*2+1; //nid*2+1maxn=max(now->right->nid,maxn);}}// 写到这，不会判断是不是完全二叉树了 } int main(){cin>>n;int t;node *root=nullptr;for(int i=0;i<n;i++){cin>>t;insert(root,t);}bfs(root);cout<<endl;if(maxn==n) cout<<"YES"; //用完全二叉树性质判断 最大节点id和个数一样else cout<<"NO";system("pause");return 0; }L3-011 直捣黄龙
L3-012 水果忍者
L3-013 非常弹的球
L3-014 周游世界
L3-015 球队“食物链”
L3-016 二叉搜索树的结构
L3-017 森森快递
L3-018 森森美图
L3-019 代码排版
L3-020 至多删三个字符
L3-021 神坛
L3-022 地铁一日游
L3-023 计算图
L3-024 Oriol和David
L3-025 那就别担心了
L3-026 传送门
L3-027 可怜的复杂
L3-028 森森旅游
L3-029 还原文件
L3-030 可怜的简单题
总结
- 上一篇： The request was reje
- 下一篇： 输入圆半径计算圆周长、圆面积、圆球表面积