如何制作PTA刷题的详细记录表？
- 内容介绍
- 文章标签
- 相关推荐
本文共计9820个文字，预计阅读时间需要40分钟。
PTA刷题笔记+资源地址：https://github.com/Haorical/Code/tree/master/PTA/GPLT涵盖两周内刷完GPLT L2和L3的题目，持续更新，包括代码、解析和少量评论。一周内完成L2的40道题，附刷题笔记+dj+vis数据配置。
PTA刷题记录仓库地址: github.com/Haorical/Code/tree/master/PTA/GPLT
两周之内刷完GPLT L2和L3的题，持续更新，包括AK代码，坑点，和少量评论
用一周刷完了l2的40道题
刷题笔记
- dj vis数组置为真
- 链表判空不用数量，判断结尾
- 注意数据类型比较，段错误可能int double比较/无限循环/数组给小了
- 指针定义时赋空
- 镜像树left right互换就行
- union()时间过长 建议不用
- bfs入队判空
- 并查集有时不用路径压缩 Union
- make_heap()
- 并查集查连通块很简单
- lower_bound查找>=目标第一个元素 upper_bound >
- set判断有无重复
- sort() begin end
- py sort()容易超时
- 注意yes no大小写
- 数组建树时注意递归结束条件
- dj最短路
- 模拟链表
- 简单贪心
- 二叉搜索树实现
- set操作 set_intersection() set_union()使用
- 给两个遍历序列建树 再层序遍历
- 并查集+结构体排序 码量大
- 暴力模拟 动态规划(过不了)
- 结构体排序
- 并查集
- 给两个遍历序列镜像建树
- 堆实现(小/大)
- 并查集/搜索 求连通块
- 思维题 upper_bound()使用 容器操作
- 简单模拟
- 搜索求连通块
- 思维题 sort()使用
- 多项式除法
- 模拟 map vector set使用
- 记忆化搜索
- 结构体排序
- 模拟链表
- 图邻接表存储
- 并查集
- 并查集/搜索求连通块
- 记忆化搜索
- 结构体排序
- 模拟
- 数学+模拟
- map使用
- 记忆化搜索
- 栈使用
- 基础栈
- 恶心模拟
- 完全二叉树数组存储
- 模拟
- 栈+队列
- 记忆化搜索 vector排序
- map+vector
- 简单模拟
简单的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;){ //巨坑 不要判断节点个数 判断链表下一个地址是不是-1
if(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(); //一定clear
s2.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.0
printf("%.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-1
root->right=create(postL+numLeft,postR-1,k+1,R);//建立右子树 更新中序L=k+1
return 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){ //标准bfs
queue<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();// 记得clear
int 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(){
//input
int 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 Photo
double love[1010] = {0};
for(int c = 1; c <= 2; c++){
for(int i = 0; i < m; i++){
//Find CP
int ok = 0;
for(int j = 0; j < photo[i].size(); j++){
if(photo[i][j]==cp[c]){
ok = 1;
break;
}
}
//Add Love
if(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 maxlove
double 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;
//output
if(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*2
maxn=max(now->left->nid,maxn);
}
if(now->right!=nullptr){
q.push(now->right);
now->right->nid=now->nid*2+1; //nid*2+1
maxn=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 可怜的简单题
本文共计9820个文字，预计阅读时间需要40分钟。
PTA刷题笔记+资源地址：https://github.com/Haorical/Code/tree/master/PTA/GPLT涵盖两周内刷完GPLT L2和L3的题目，持续更新，包括代码、解析和少量评论。一周内完成L2的40道题，附刷题笔记+dj+vis数据配置。
PTA刷题记录仓库地址: github.com/Haorical/Code/tree/master/PTA/GPLT
两周之内刷完GPLT L2和L3的题，持续更新，包括AK代码，坑点，和少量评论
用一周刷完了l2的40道题
刷题笔记
- dj vis数组置为真
- 链表判空不用数量，判断结尾
- 注意数据类型比较，段错误可能int double比较/无限循环/数组给小了
- 指针定义时赋空
- 镜像树left right互换就行
- union()时间过长 建议不用
- bfs入队判空
- 并查集有时不用路径压缩 Union
- make_heap()
- 并查集查连通块很简单
- lower_bound查找>=目标第一个元素 upper_bound >
- set判断有无重复
- sort() begin end
- py sort()容易超时
- 注意yes no大小写
- 数组建树时注意递归结束条件
- dj最短路
- 模拟链表
- 简单贪心
- 二叉搜索树实现
- set操作 set_intersection() set_union()使用
- 给两个遍历序列建树 再层序遍历
- 并查集+结构体排序 码量大
- 暴力模拟 动态规划(过不了)
- 结构体排序
- 并查集
- 给两个遍历序列镜像建树
- 堆实现(小/大)
- 并查集/搜索 求连通块
- 思维题 upper_bound()使用 容器操作
- 简单模拟
- 搜索求连通块
- 思维题 sort()使用
- 多项式除法
- 模拟 map vector set使用
- 记忆化搜索
- 结构体排序
- 模拟链表
- 图邻接表存储
- 并查集
- 并查集/搜索求连通块
- 记忆化搜索
- 结构体排序
- 模拟
- 数学+模拟
- map使用
- 记忆化搜索
- 栈使用
- 基础栈
- 恶心模拟
- 完全二叉树数组存储
- 模拟
- 栈+队列
- 记忆化搜索 vector排序
- map+vector
- 简单模拟
简单的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;){ //巨坑 不要判断节点个数 判断链表下一个地址是不是-1
if(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(); //一定clear
s2.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.0
printf("%.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-1
root->right=create(postL+numLeft,postR-1,k+1,R);//建立右子树 更新中序L=k+1
return 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){ //标准bfs
queue<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();// 记得clear
int 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(){
//input
int 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 Photo
double love[1010] = {0};
for(int c = 1; c <= 2; c++){
for(int i = 0; i < m; i++){
//Find CP
int ok = 0;
for(int j = 0; j < photo[i].size(); j++){
if(photo[i][j]==cp[c]){
ok = 1;
break;
}
}
//Add Love
if(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 maxlove
double 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;
//output
if(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*2
maxn=max(now->left->nid,maxn);
}
if(now->right!=nullptr){
q.push(now->right);
now->right->nid=now->nid*2+1; //nid*2+1
maxn=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 可怜的简单题