PTA程序设计天梯赛 L2题解报告（40/40）
桂志新
L2-001 紧急救援 (25 分)
紧急救援
题目分析：
dijkstra求最短路的同时维护权值，并且输出具体距离，用pre数组存每个点从哪里来的，最后倒叙输出即可
#include <bits/stdc++.h>
using namespace std;
const int N=510;
int g[N][N];
int dist[N];
bool st[N];
int w[N];
int sum_w[N];
int cnt[N];
int pre[N];
int n,m,s,d;
void dijkstra()
{
memset(dist,0x3f,sizeof dist);
sum_w[s]=w[s];
dist[s]=0;
cnt[s]=1;
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=0;j<n;j++)
if(!st[j]&&(t==-1||dist[j]<dist[t]))
t=j;
st[t]=true;
for(int j=0;j<n;j++)
{
if(dist[j]>dist[t]+g[t][j])
{
dist[j]=dist[t]+g[t][j];
cnt[j]=cnt[t];
sum_w[j]=sum_w[t]+w[j];
pre[j]=t;
}
else if(dist[j]==dist[t]+g[t][j])
{
cnt[j]+=cnt[t];
if(sum_w[j]<sum_w[t]+w[j])
{
sum_w[j]=sum_w[t]+w[j];
pre[j]=t;
}
}
}
}
cout<<cnt[d]<<' '<<sum_w[d]<<endl;
stack<int>stk;
int u=d;
while(u!=s)
{
stk.push(u);
u=pre[u];
}
cout<<s;
while(stk.size())
{
cout<<' '<<stk.top();
stk.pop();
}
}
int main()
{
cin>>n>>m>>s>>d;
for(int i=0;i<n;i++)cin>>w[i];
memset(g,0x3f,sizeof g);
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=c;
}
dijkstra();
return 0;
}
L2-002 链表去重 (25 分)
链表去重
用两个数组分别存不重复的，重复的。
用数组模拟单链表
h存头，ne[N]存next结点，空地址设为 -1
则枚举方式为
for(int i=h;~i;i=ne[i])
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h,e[N],ne[N];
bool st[N];
int n;
int main()
{
cin>>h>>n;
for(int i=0;i<n;i++)
{
int idx,data,next;
cin>>idx>>data>>next;
e[idx]=data,ne[idx]=next;
}
vector<int>a,b;//hash
for(int i=h;~i;i=ne[i])
{
int v=abs(e[i]);
if(st[v])b.push_back(i);
else
{
st[v]=true;
a.push_back(i);
}
}
for(int i=0;i<a.size();i++)
{
printf("%05d %d ",a[i],e[a[i]]);
if(i==a.size()-1)puts("-1");
else printf("%05d\n",a[i+1]);
}
for(int i=0;i<b.size();i++)
{
printf("%05d %d ",b[i],e[b[i]]);
if(i==b.size()-1)puts("-1");
else printf("%05d\n",b[i+1]);
}
return 0;
}
L2-003 月饼 (25 分)
月饼
此题是个贪心，要求月饼收益最大，则求单个收益最大进行sort，枚举即可
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
double m;
int n;
struct node
{
double p,w;
bool operator<(const node &t)const
{
return p/w>t.p/t.w;
}
}c[N];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)cin>>c[i].w;
for(int i=0;i<n;i++)cin>>c[i].p;
sort(c,c+n);
double res=0;
for(int i=0;i<n&&m>0;i++)
{
double r=min(m,c[i].w);
m-=r;
res+=c[i].p/c[i].w*r;
}
printf("%.2f\n",res);
return 0;
}
L2-004 这是二叉搜索树吗？
这是二叉搜索树吗？
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，
其左子树中所有结点的键值小于该结点的键值；
其右子树中所有结点的键值大于等于该结点的键值；
其左右子树都是二叉搜索树。
模板题，建树，左右颠倒，
模板题，真没什么好解释的。。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int n;
int p1[N], p2[N];
int cnt1,cnt2;
bool s;
typedef struct node
{
int data;
node* left, * right;
}node,*tree;
tree create1(tree T, int x)
{
if (!T)
{
T = (tree)malloc(sizeof(struct node));
T->left = nullptr, T->right = nullptr;
T->data = x;
}
else
{
if (T->data > x)T->left = create1(T->left, x);
else if (T->data <= x)T->right = create1(T->right, x);
}
return T;
}
tree create2(tree T, int x)
{
if (!T)
{
T = (tree)malloc(sizeof(struct node));
T->left = T->right = nullptr;
T->data = x;
}
else
{
if (T->data <= x)T->left = create2(T->left, x);
else if (T->data > x)T->right = create2(T->right, x);
}
return T;
}
void pre1(tree T)
{
if (!T)return;
p1[cnt1++] = T->data;
pre1(T->left);
pre1(T->right);
}
void post(tree T)
{
if (!T)return;
post(T->left);
post(T->right);
if (s)cout << ' ';
s = true;
cout<< T->data;
}
void pre2(tree T)
{
if (!T)return;
p2[cnt2++] = T->data;
pre2(T->left);
pre2(T->right);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)cin >> a[i];
tree T1 = nullptr;
for (int i = 0; i < n; i++)T1=create1(T1, a[i]);
tree T2 = nullptr;
for (int i = 0; i < n; i++)T2=create2(T2, a[i]);
pre1(T1), pre2(T2);
bool f1 = false;
for (int i = 0; i < n; i++)
if (p1[i] != a[i])f1 = true;
bool f2 = false;
for (int i = 0; i < n; i++)
if (p2[i] != a[i])f2 = true;
if (f1 && f2)
{
puts("NO");
return 0;
}
if (!f1 && f2)puts("YES"),post(T1);
if (f1 && !f2)puts("YES"),post(T2);
if (!f1 && !f2)puts("YES"), post(T1);
return 0;
}
L2-005 集合相似度 (25 分)
集合相似度
unordered_set存集合，按照题意模拟即可
注意输出printf 不然会tle
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int t;
int n, m;
int main()
{
unordered_set<int>s[N];
cin >> t;
for (int i = 1; i <= t; i++)
{
cin >> n;
for (int j = 0; j < n; j++)
{
int x;
cin >> x;
s[i].insert(x);
}
}
cin >> m;
while (m--)
{
int a, b;
cin >> a >> b;
int cnt = 0;
for (auto x : s[a])if (s[b].count(x))cnt++;
printf("%.2f%%\n", cnt * 1.0 / (s[a].size()+s[b].size()-cnt)*100);//容易超时
}
return 0;
}
L2-006 树的遍历 (25 分)
树的遍历
模板题，给两个遍历还原这棵树并输出层序遍历
#include <bits/stdc++.h>
using namespace std;
const int N=35;
int n;
int pos[N],in[N];
typedef struct node
{
int data;
node *left,*right;
}node,*tree;
tree create(int len,int *in,int*pos)
{
if(len<=0)return nullptr;
tree T=(tree)malloc(sizeof (struct node));
T->left=T->right=nullptr;
T->data=pos[len-1];
int i=0;
for(i=0;i<len;i++)
if(T->data==in[i])
break;
T->left=create(i,in,pos);
T->right=create(len-i-1,in+i+1,pos+i);
return T;
}
void bfs(tree T)
{
queue<tree>q;
q.push(T);
bool f=false;
while(q.size())
{
auto t=q.front();
q.pop();
if(f)cout<<' ';
f=true;
cout<<t->data;
if(t->left)q.push(t->left);
if(t->right)q.push(t->right);
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)cin>>pos[i];
for(int i=0;i<n;i++)cin>>in[i];
tree T=nullptr;
T=create(n,in,pos);
bfs(T);
return 0;
}
L2-007 家庭房产 (25 分)
家庭房产
并查集+哈希，难度不大就是比较麻烦
将一个家族的人放到一起，算是个模板提吧，
这里需要注意，当找first_id时一定要初始化为-1，因为0000也是一个人的编号
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=10010;
int f[N];
map<int,bool>st;
int n;
struct people
{
int id;
double cnt,area;
}p[N];
struct family
{
int first_id=-1,num;
double cnt,area,avg_cnt,avg_area;
}fam[N];
void init()
{
for(int i=0;i<N;i++)f[i]=i;
}
int find(int x)
{
if(x!=f[x])f[x]=find(f[x]);
return f[x];
}
void unite(int a,int b)
{
int x=find(a);
int y=find(b);
if(x!=y)f[x]=y;
}
bool cmp(family a,family b)
{
if(a.avg_area!=b.avg_area)
return a.avg_area>b.avg_area;
else return a.first_id<b.first_id;
}
int main()
{
init();
cin>>n;
for(int i=0;i<n;i++)
{
int id,fa,ma;
cin>>id>>fa>>ma;
st[id]=true;
if(~fa)
{
st[fa]=true;
unite(id,fa);
}
if(~ma)
{
st[ma]=true;
unite(id,ma);
}
int k;
cin>>k;
for(int j=0;j<k;j++)
{
int x;
cin>>x;
unite(id,x);
st[x]=true;
}
int cnt,area;
cin>>cnt>>area;
p[id].cnt=cnt,p[id].area=area;
}
for(auto x:st)
{
fam[find(x.x)].cnt+=p[x.x].cnt;
fam[find(x.x)].area+=p[x.x].area;
if(fam[find(x.x)].first_id==-1)fam[find(x.x)].first_id=x.x;
fam[find(x.x)].num++;
}
for(int i=0;i<N;i++)
{
if(!st[i])continue;
fam[find(i)].avg_cnt=fam[find(i)].cnt/fam[find(i)].num;
fam[find(i)].avg_area=fam[find(i)].area/fam[find(i)].num;
}
int sum=0;
for(int i=0;i<N;i++)
if(fam[i].num)sum++;
printf("%d\n",sum);
sort(fam,fam+N,cmp);
for(int i=0;i<sum;i++)
printf("%04d %d %.3f %.3f\n",fam[i].first_id,fam[i].num,fam[i].avg_cnt,fam[i].avg_area);
return 0;
}
L2-008 最长对称子串 (25 分)
最长对称子串
我用的暴力枚举每个区间，因为要求最长，所以倒序
数据比较水，后期更新其他做法
#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
getline(cin,s);
for(int len=s.size();len>0;len--)
{
for(int l=0;l+len-1<s.size();l++)
{
bool f=false;
int r=l+len-1;
int i=l,j=r;
while(i<j)
{
if(s[i]!=s[j])
{
f=true;
break;
}
i++,j--;
}
if(!f)
{
cout<<len<<endl;
return 0;
}
}
}
return 0;
}
L2-009 抢红包 (25 分)
抢红包
模拟题，求个排序就行
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
struct node
{
int qiang_count;
int fa_count;
double qiang_val;
double fa_val;
int id;
double res;
}a[N];
int n;
bool cmp(node a,node b)
{
if(a.res!=b.res)
return a.res>b.res;
else if(a.qiang_count!=b.qiang_count)
return a.qiang_count>b.qiang_count;
else return a.id<b.id;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)a[i].id=i;
for(int i=1;i<=n;i++)
{
int k;
cin>>k;
a[i].fa_count+=k;
for(int j=0;j<k;j++)
{
int id,val;
cin>>id>>val;
a[id].qiang_count++;
a[id].qiang_val+=val;
a[i].fa_count++;
a[i].fa_val+=val;
}
}
for(int i=1;i<=n;i++)a[i].res=a[i].qiang_val-a[i].fa_val;
sort(a+1,a+n+1,cmp);
for (int i = 1; i <= n; i++)
printf("%d %.2f\n", a[i].id, a[i].res*1.0/100);
return 0;
}
L2-010 排座位 (25 分)
排座位
模拟题，稍微用到了矩阵二元关系。。
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int g[N][N];
int n,m,k;
bool check(int a,int b)
{
for(int i=1;i<=n;i++)
if(g[a][i]==1&&g[i][b]!=0)
return true;
return false;
}
int main()
{
cin>>n>>m>>k;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=c;
}
while(k--)
{
int a,b;
cin>>a>>b;
if(g[a][b]==1)puts("No problem");
if(g[a][b]==0)puts("OK");
if(g[a][b]==-1&&check(a,b))puts("OK but...");
else if(g[a][b]==-1)puts("No way");
}
return 0;
}
L2-011 玩转二叉树 (25 分)
玩转二叉树
反向建树即可
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int in[N], p[N];
int n;
typedef struct node
{
int data;
node* left, * right;
}node,*tree;
tree create(int len, int* in, int* p)
{
if (!len)return nullptr;
tree root = nullptr;
root = (tree)malloc(sizeof(struct node));
root->left = root->right = nullptr;
root->data = p[0];
int i = 0;
for (i = 0; i < len; i++)
if (in[i] == root->data)break;
root->right = create(i, in, p + 1);
root->left = create(len - (i + 1), in + i + 1, p + i + 1);
return root;
}
void level(tree T)
{
queue<tree>q;
q.push(T);
bool f = false;
while (q.size())
{
auto t=q.front();
if (f)cout << ' ';
f = true;
q.pop();
if (t->left)q.push(t->left);
if (t->right)q.push(t->right);
cout << t->data;
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)cin >> in[i];
for (int i = 0; i < n; i++)cin >> p[i];
tree T = nullptr;
T = create(n, in, p);
level(T);
return 0;
}
L2-012 关于堆的判断 (25 分)
关于堆的判断
up操作建小顶堆
根据题目要求查询
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e5+10;
int heap[N];
void up(int u)
{
if(heap[u]<heap[u/2]&&u/2>0)
{
swap(heap[u],heap[u/2]);
up(u>>1);
}
}
bool check1(int a,int b)
{
int idxa=0,idxb=0;
for(int i=1;i<=n;i++)
{
if(heap[i]==a)idxa=i;
if(heap[i]==b)idxb=i;
}
if(idxa%2==0&&idxa+1==idxb||idxb%2==0&&idxb+1==idxa)return true;
return false;
}
bool check2(int a,int b)
{
int idxa=0,idxb=0;
for(int i=1;i<=n;i++)
{
if(heap[i]==a)idxa=i;
if(heap[i]==b)idxb=i;
}
if(idxa==idxb*2||idxa==idxb*2+1)return true;
else return false;
}
bool check3(int a)
{
return heap[1]==a;
}
bool check4(int a,int b)
{
int idxa=0,idxb=0;
for(int i=1;i<=n;i++)
{
if(heap[i]==a)idxa=i;
if(heap[i]==b)idxb=i;
}
if(idxb&1&&a==heap[(idxb-1)/2])return true;
if(idxb%2==0&&a==heap[idxb/2])return true;
return false;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>heap[i];
up(i);
}
while(m--)
{
int a;
string b;
cin>>a>>b;
if(b=="and")
{
int b;
cin>>b;
string str1,str2;
cin>>str1>>str2;
if(check1(a,b))puts("T");
else puts("F");
}
else
{
string b;
cin>>b;
if(b=="a")
{
int y;
string str1,str2;
cin>>str1>>str2;
cin>>y;
if(check2(a,y))puts("T");
else puts("F");
}
else
{
string b;
cin>>b;
if(b=="root")
{
if(check3(a))puts("T");
else puts("F");
}
else
{
string str1;
cin>>str1;
int y;
cin>>y;
if(check4(a,y))puts("T");
else puts("F");
}
}
}
}
return 0;
}
L2-013 红色警报 (25 分)
红色警报
并查集
#include <bits/stdc++.h>
using namespace std;
const int N=5010;
int f[N];
int n,m;
bool st[N];
struct node
{
int a,b;
}e[N];
void init()
{
for(int i=0;i<N;i++)f[i]=i;
}
int find(int x)
{
if(x!=f[x])f[x]=find(f[x]);
return f[x];
}
void unite(int a,int b)
{
int x=find(a);
int y=find(b);
if(x!=y)f[x]=y;
}
int main()
{
cin>>n>>m;
init();
for(int i=0;i<m;i++)
{
cin>>e[i].a>>e[i].b;
unite(e[i].a,e[i].b);
}
int cnt=0;
for(int i=0;i<n;i++)
if(f[i]==i)cnt++;
int k;
cin>>k;
int y=k;
while(k--)
{
init();
int x;
cin>>x;
st[x]=true;
for(int i=0;i<m;i++)
{
int a=e[i].a,b=e[i].b;
if(st[a]||st[b])continue;
if(x!=a&&x!=b)
unite(a,b);
}
int res=0;
for(int i=0;i<n;i++)
if(f[i]==i)res++;
if(res>cnt+1)printf("Red Alert: City %d is lost!\n",x);
else printf("City %d is lost.\n",x);
cnt=res;
}
if(y==n)printf("Game Over.\n");
return 0;
}
dfs连通块
#include <bits/stdc++.h>
using namespace std;
const int N=510;
const int M=5010;
int g[N][N];
int n,m;
bool st[N];
void dfs(int u)
{
st[u]=true;
for(int i=0;i<n;i++)
if(!st[i]&&g[u][i])
dfs(i);
}
int calcnt()
{
int cnt=0;
for(int i=0;i<n;i++)
{
if(!st[i])
{
dfs(i);
cnt++;
}
}
return cnt;
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
g[a][b]=g[b][a]=true;
}
int k;
cin>>k;
int y=k;
int cnt=calcnt();
vector<int>v;
while(k--)
{
int x;
cin>>x;
v.push_back(x);
for(int i=0;i<n;i++)g[i][x]=g[x][i]=false;
memset(st,false, sizeof st);
for(auto x:v)st[x]=true;
int res=calcnt();
if(res>cnt) printf("Red Alert: City %d is lost!\n",x);
else printf("City %d is lost.\n",x);
cnt=res;
}
if(y==n)printf("Game Over.\n");
return 0;
}
L2-014 列车调度 (25 分)
列车调度
贪心+二分
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n;
set<int>s;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
auto t=s.lower_bound(x);
if(t!=s.end())
{
s.erase(*t);
s.insert(x);
}
else s.insert(x);
}
cout<<s.size()<<endl;
return 0;
}
L2-015 互评成绩 (25 分)
互评成绩
排序
#include <bits/stdc++.h>
using namespace std;
int n,k,m;
vector<double>res;
int main()
{
cin>>n>>k>>m;
for(int i=0;i<n;i++)
{
vector<int>v;
for(int j=0;j<k;j++)
{
int x;
cin>>x;
v.push_back(x);
}
sort(v.begin(),v.end());
int sum=0;
for(int i=1;i<v.size()-1;i++)sum+=v[i];
res.push_back(sum*1.0/(k-2));
}
sort(res.begin(),res.end(),greater<double>());
bool f=false;
int cnt=0;
vector<double>vv;
for(auto x:res)
{
if(cnt>=m)break;
vv.push_back(x);
cnt++;
}
for(int i=vv.size()-1;i>=0;i--)
{
if(f)cout<<' ';
f=true;
printf("%.3f",vv[i]);
}
return 0;
}
L2-016 愿天下有情人都是失散多年的兄妹 (25 分)
愿天下有情人都是失散多年的兄妹
dfs
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,k;
bool st[N];
vector<int>v[N];
char sex[N];
bool f=false;
void dfs(int u,int depth)
{
if(depth>=5)return;
st[u]=true;
for(int i=0;i<v[u].size();i++)
{
if(st[v[u][i]])f=true;
dfs(v[u][i],depth+1);
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int id;
cin>>id;
char c;
cin>>c;
sex[id]=c;
int fa,ma;
cin>>fa>>ma;
if(~fa)
{
sex[fa]='M';
v[id].push_back(fa);
}
if(~ma)
{
sex[ma]='F';
v[id].push_back(ma);
}
}
cin>>k;
while(k--)
{
int x,y;
cin>>x>>y;
f=false;
memset(st,false, sizeof st);
dfs(x,0);
dfs(y,0);
if(sex[x]==sex[y])puts("Never Mind");
else
{
if(!f) puts("Yes");
else puts("No");
}
}
return 0;
}
L2-017 人以群分 (25 分)
人以群分
排序
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int x, int y)
{
return x > y;
}
int main()
{
int N,i,sum1=0,sum2=0;
int person[100001];
cin >> N;
for (i = 0; i < N; i++)
cin >> person[i];
sort(person, person + N, cmp);
cout << "Outgoing #: " << N - N / 2 << endl;
cout << "Introverted #: " << N / 2 << endl;
for (i = 0; i < N - N / 2; i++)
sum1 += person[i];
for (i = N - N / 2; i < N; i++)
sum2 += person[i];
cout << "Diff = " << sum1 - sum2 << endl;
return 0;
}
L2-018 多项式A除以B (25 分)(未填坑)
没看
L2-019 悄悄关注 (25 分)
哈希
悄悄关注
#include <bits/stdc++.h>
using namespace std;
int main()
{
unordered_map<string,int>mp;
map<string,double>name;
int n;
cin>>n;
for(int i=0;i<n;i++)
{
string s;
cin>>s;
mp[s]=true;
}
int m;
cin>>m;
int sum=0;
for(int i=0;i<m;i++)
{
string s;
int cnt;
cin>>s>>cnt;
name[s]=cnt;
sum+=cnt;
}
double avg=sum*1.0/m;
bool f=false;
for(auto x:name)
{
if(!mp.count(x.first)&&x.second>avg)
{
cout<<x.first<<endl;
f=true;
}
}
if(!f)puts("Bing Mei You");
return 0;
}
L2-020 功夫传人 (25 分)
功夫传人
dfs
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
double z,r;
vector<vector<int>>g;
bool st[N];
double sum;
void dfs(int u,double power)
{
if(st[u])
{
sum+=power*g[u][0];
return;
}
for(int i=0;i<g[u].size();i++)
dfs(g[u][i],power*(1-r/100));
}
int main()
{
scanf("%d%lf%lf",&n,&z,&r);
g.resize(n);
for(int i=0;i<n;i++)
{
int k;
cin>>k;
if(!k)
{
int x;
cin>>x;
st[i]=true;
g[i].push_back(x);
}
else
{
for(int j=0;j<k;j++)
{
int x;
cin>>x;
g[i].push_back(x);
}
}
}
dfs(0,z);
printf("%d\n",(int)sum);
return 0;
}
L2-021 点赞狂魔 (25 分)
点赞狂魔
结构体排序
#include <bits/stdc++.h>
using namespace std;
const int N=110;
struct node
{
string name;
int num;
int sum;
double avg;
}a[N];
int n;
bool cmp(node a,node b)
{
if(a.num!=b.num)return a.num>b.num;
else a.avg<b.avg;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
string name;
cin>>name;
int k;
cin>>k;
a[i].name=name;
a[i].sum=k;
set<int>s;
for(int j=0;j<k;j++)
{
int x;
cin>>x;
s.insert(x);
}
a[i].num=s.size();
a[i].avg=a[i].sum*1.0/a[i].num;
}
sort(a,a+n,cmp);
if(n>=3)
for(int i=0;i<3;i++)
{
cout<<a[i].name;
if(i<2)cout<<" ";
}
else
{
for(int i=0;i<n;i++)
cout<<a[i].name<<" ";
for(int i=0;i<3-n;i++)
{
cout<<"-";
if(i<2-n)cout<<" ";
}
}
return 0;
}
L2-022 重排链表 (25 分)
重组链表
模拟链表
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h,ne[N],e[N],pre[N],idx[N];
int n;
int cnt=1;
int main()
{
cin>>h>>n;
for(int i=0;i<n;i++)
{
int id,data,next;
cin>>id>>data>>next;
e[id]=data;
idx[data]=id;
ne[id]=next;
pre[ne[id]]=id;
}
int i=h,j=h;
while(ne[j]!=-1)
{
j=ne[j];
cnt++;
}
bool f=false;
while(i!=j)
{
printf("%05d %d %05d\n",j,e[j],i);
j=pre[j];
if(i==j)
{
f=true;
break;
}
printf("%05d %d %05d\n",i,e[i],j);
i=ne[i];
}
if(f)
printf("%05d %d -1\n",j,e[j]);
else printf("%05d %d -1\n",i,e[i]);
return 0;
}
L2-023 图着色问题 (25 分)
图着色问题
dfs枚举
#include <bits/stdc++.h>
using namespace std;
const int N=510;
bool g[N][N];
int n,m,k;
int color[N];
bool st[N];
bool dfs(int u)
{
st[u]=true;
for(int i=1;i<=n;i++)
{
if(g[u][i])
{
if(color[u]==color[i])return false;
if(!st[i])if(!dfs(i))return false;
}
}
return true;
}
int main()
{
cin>>n>>m>>k;
for(int i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
g[a][b]=g[b][a]=true;
}
int x;
cin>>x;
while(x--)
{
memset(color,0,sizeof color);
set<int>s;
memset(st,false,sizeof st);
for(int i=1;i<=n;i++)
{
cin>>color[i];
s.insert(color[i]);
}
int i=0;
for( i=1;i<=n&&s.size()==k;i++)
if(dfs(i)==false)break;
if(i==n+1)puts("Yes");
else puts("No");
}
return 0;
}
L2-024 部落 (25 分)
部落
并查集
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n;
int f[N];
int cnt[N];
unordered_map<int,bool>mp;
int find(int x)
{
if(x!=f[x])f[x]=find(f[x]);
return f[x];
}
void unite(int a,int b)
{
int x=find(a);
int y=find(b);
if(x!=y)f[x]=y;
}
int main()
{
cin>>n;
for(int i=0;i<N;i++)f[i]=i;
for(int i=0;i<n;i++)
{
int k;
cin>>k;
int x;
cin>>x;
mp[x]=true;
for(int j=1;j<k;j++)
{
int y;
cin>>y;
unite(x,y);
mp[y]=true;
}
}
int res=0;
for(auto x:mp)
if(f[x.first]==x.first)res++;
cout<<mp.size()<<' '<<res<<endl;
int q;
cin>>q;
while(q--)
{
int a,b;
cin>>a>>b;
if(find(a)==find(b))puts("Y");
else puts("N");
}
return 0;
}
L2-025 分而治之 (25 分)
分而治之
用边存图
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
struct node
{
int a,b;
}e[N];
int n,m;
bool st[2*N];
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)cin>>e[i].a>>e[i].b;
int k;
cin>>k;
while(k--)
{
memset(st,false,sizeof st);
int x;
cin>>x;
for(int i=0;i<x;i++)
{
int y;
cin>>y;
st[y]=true;
}
bool f=false;
for(int i=0;i<m;i++)
{
if(!st[e[i].a]&&!st[e[i].b])
{
puts("NO");
f=true;
break;
}
}
if(f)continue;
else puts("YES");
}
return 0;
}
L2-026 小字辈 (25 分)
小字辈
数组建树，求叶子节点
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>>v;
int h;
vector<vector<int>>leaf;
unordered_map<int,bool>st;
void dfs(int u,int depth)
{
st[u]=true;
if(v[u].size()==0)
{
h=max(h,depth);
leaf[depth].push_back(u);
return;
}
for(int i=0;i<v[u].size();i++)
{
if(st[v[u][i]])continue;
dfs(v[u][i],depth+1);
}
}
int main()
{
cin>>n;
v.resize(n+1);
leaf.resize(n+1);
int root=-1;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(~x)v[x].push_back(i);
else root=i;
}
dfs(root,1);
cout<<h<<endl;
for(int i=0;i<leaf[h].size();i++)
{
cout<<leaf[h][i];
if(i<leaf[h].size()-1)cout<<' ';
}
return 0;
}
L2-027 名人堂与代金券 (25 分)
名人堂与代金券
结构体排序
#include <bits/stdc++.h>
using namespace std;
const int N= 1e4+10;
struct node
{
string name;
int num;
int exm;
int level;
}a[N];
int n,g,k;
int sum;
bool cmp(node a,node b)
{
if(a.exm!=b.exm)return a.exm>b.exm;
return a.name<b.name;
}
int main()
{
cin>>n>>g>>k;
for(int i=0;i<n;i++)
{
cin>>a[i].name>>a[i].exm;
if(a[i].exm>=g&&a[i].exm<=100)a[i].num=50;
else if(a[i].exm>=60&&a[i].exm<g)a[i].num=20;
else if(a[i].exm<60)a[i].num=0;
sum+=a[i].num;
}
cout<<sum<<endl;
sort(a,a+n,cmp);
int cnt=1;
for(int i=0;i<n;i++)
{
if(!i)a[i].level=i+1;
else
{
if(a[i].exm==a[i-1].exm)a[i].level=a[i-1].level;
else a[i].level=i+1;
}
cnt=a[i].level;
if(cnt>k)break;
cout<<a[i].level<<' '<<a[i].name<<' '<<a[i].exm<<endl;
}
return 0;
}
L2-028 秀恩爱分得快 (25 分)（21/25）
秀恩爱分的快
大模拟
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int sex[N];
int n,m;
int judge(string s)
{
int num=0;
int f=-1;
if(s[0]=='-')
{
for(int i=1;i<s.size();i++)num=num*10+s[i]-'0';
sex[num]=-1;
}
else
{
for(int i=0;i<s.size();i++)num=num*10+s[i]-'0';
sex[num]=1;
}
return num;
}
int main()
{
cin>>n>>m;
vector<vector<int>>v(n);
vector<double>pa(n,0.0),pb(n,0.0);
for(int i=0;i<m;i++)
{
int k;
cin>>k;
for(int j=0;j<k;j++)
{
string s;
cin>>s;
int x= judge(s);
v[i].push_back(abs(x));
}
}
int a,b;
cin>>a>>b;
a=abs(a),b=abs(b);
double maxv_A=0.0,maxv_B=0.0;
for(int i=0;i<m;i++)
{
bool is_findA=find(v[i].begin(),v[i].end(),a)!=v[i].end();
bool is_findB=find(v[i].begin(),v[i].end(),b)!=v[i].end();
if(is_findA||is_findB)
{
for(int j=0;j<v[i].size();j++)
{
if(is_findA&&sex[a]!=sex[v[i][j]])
{
pa[v[i][j]]+=(double)1.0/v[i].size();
maxv_A=max(maxv_A,pa[v[i][j]]);
}
else if(is_findB&&sex[b]!=sex[v[i][j]])
{
pb[v[i][j]]+=(double)1.0/v[i].size();
maxv_B=max(maxv_B,pb[v[i][j]]);
}
}
}
}
if(maxv_A==pa[b]&&maxv_B==pb[a])
cout<<sex[a]*a<<' '<<sex[b]*b<<endl;
else
{
for(int i=0;i<n;i++)
if(pa[i]==maxv_A)cout<<sex[a]*a<<' '<<sex[i]*i<<endl;
for(int i=0;i<n;i++)
if(pb[i]==maxv_B)cout<<sex[b]*b<<' '<<sex[i]*i<<endl;
}
return 0;
}
L2-029 特立独行的幸福 (25 分)
特立独行的幸福
大模拟
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
bool st[N];
bool ch[N];
int xx[N];
bool cmp(int x)
{
for(int i=2;i*i<=x;i++)
if(x%i==0)return false;
return true;
}
int main()
{
int l,r;
cin>>l>>r;
for(int i=l;i<=r;i++)
{
if(ch[i])continue;
int k=1;
if(cmp(i))k=2;
memset(st,false,sizeof st);
int cnt=0;
int num=i;
while(1)
{
int m=0;
while(num)
{
m+=(num%10)*(num%10);
num/=10;
}
if(m<=r&&m>=l)ch[m]=true;
if(st[m])
{
ch[m]=true;
break;
}
st[m]=true;
num=m;
cnt++;
if(m==1)
{
xx[i]=k*cnt;
break;
}
}
}
bool f=false;
for(int i=l;i<=r;i++)
{
if(!ch[i]&&xx[i]>0)
{
cout<<i<<' '<<xx[i]<<endl;
f=true;
}
}
if(!f)puts("SAD");
return 0;
}
L2-030 冰岛人 (25 分)
冰岛人
大模拟
#include <bits/stdc++.h>
using namespace std;
typedef pair<char,string>PCS;
unordered_map<string,PCS>p;
int n,m;
bool check(string a,string b)
{
int cnt1=1;
for(string i=a;i.size();i=p[i].second,cnt1++)
{
int cnt2=1;
for( string j=b;j.size();j=p[j].second,cnt2++)
{
if(cnt1>=5&&cnt2>=5)break;
if(i==j)return false;
}
}
return true;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
string a,b;
cin>>a>>b;
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)};
else p[a].first=b.back();
}
cin>>m;
for(int i=0;i<m;i++)
{
string a,b,c,d;
cin>>a>>b>>c>>d;
if(!p.count(a)||!p.count(c))puts("NA");
else if(p[a].first==p[c].first)puts("Whatever");
else if(check(a,c))puts("Yes");
else if(!check(a,c))puts("No");
}
return 0;
}
L2-031 深入虎穴 (25 分)
深入虎穴
树的最深结点
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=2*N;
int h[N],e[M],ne[M],idx;
int n;
int height,id;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int depth)
{
if(h[u]==-1)
{
if(height<depth)
{
height=depth;
id=u;
}
}
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
dfs(j,depth+1);
}
}
int main()
{
cin>>n;
unordered_map<int,int>mp;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
{
int k;
cin>>k;
for(int j=0;j<k;j++)
{
int x;
cin>>x;
add(i,x);
mp[x]=true;
}
}
for(int i=1;i<=n;i++)
{
if(!mp.count(i))
dfs(i,1);
}
cout<<id<<endl;
return 0;
}
L2-032 彩虹瓶 (25 分)
彩虹瓶
模拟栈
#include <bits/stdc++.h>
using namespace std;
int n,m,k;
int main()
{
cin>>n>>m>>k;
while(k--)
{
stack<int>stk;
bool f=false;
int idx=1;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(x!=idx)
{
stk.push(x);
if(stk.size()>m)f=true;
}
else
{
idx++;
while(stk.size()&&stk.top()==idx)stk.pop(),idx++;
}
}
if(!f&&idx>=n)puts("YES");
else puts("NO");
}
return 0;
}
L2-033 简单计算器 (25 分)
简单计算器
模拟栈
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
stack<int>s1;
stack<char>s2;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
s1.push(x);
}
for(int i=0;i<n-1;i++)
{
char x;
cin>>x;
s2.push(x);
}
while(s2.size())
{
int x1=s1.top();
s1.pop();
int x2=s1.top();
s1.pop();
char c=s2.top();
s2.pop();
int res=0;
if(c=='+')res=x1+x2;
if(c=='-')res=x2-x1;
if(c=='*')res=x1*x2;
if(c=='/')
{
if(x1==0)
{
printf("ERROR: %d/0",x2);
return 0;
}
else res=x2/x1;
}
s1.push(res);
}
cout<<s1.top()<<endl;
return 0;
}
L2-034 口罩发放 (25 分)
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
struct node
{
string name;
string id;
int flag;
int hh,mm;
int idx;
int t;
}a[N],s[N];
int cnt;
int d,p;
bool judge(string s)
{
if(s.size()!=18)return false;
for(int i=0;i<s.size();i++)
{
if(s[i]<'0'||s[i]>'9')return false;
}
return true;
}
bool cmp(node a,node b)
{
if(a.t!=b.t)return a.t<b.t;
else return a.idx<b.idx;
}
int main()
{
cin>>d>>p;
map<string,int>m;
map<string,int>st;
for(int i=1;i<=d;i++)
{
int x,y;
cin>>x>>y;
for(int j=1;j<=x;j++)
{
cin>>a[j].name>>a[j].id;
char c;
cin>>a[j].flag>>a[j].hh>>c>>a[j].mm;
a[j].t=a[j].hh*60+a[j].mm;
a[j].idx=j;
if(m.find(a[j].id)==m.end())
m[a[j].id]=0;
if(a[j].flag==1&&judge(a[j].id)&&st.find(a[j].id)==st.end())
{
st[a[j].id]=0;
s[cnt++]=a[j];
}
}
sort(a+1,a+1+x,cmp);
int k=0;
for(int j=1;j<=x&&k<y;j++)
{
if(judge(a[j].id)&&(m[a[j].id]==0||i-m[a[j].id]>p))
{
cout<<a[j].name<<' '<<a[j].id<<endl;
m[a[j].id]=i;
k++;
}
}
}
for(int i=0;i<cnt;i++)cout<<s[i].name<<' '<<s[i].id<<endl;
return 0;
}
L2-035 完全二叉树的层序遍历 (25 分)
完全二叉树的层序遍历
数组还原完全二叉树
#include <bits/stdc++.h>
using namespace std;
const int N=55;
int n;
int tr[N];
int pos[N];
int k;
void dfs(int u)
{
if(u*2<=n)dfs(u*2);
if(u*2+1<=n)dfs(u*2+1);
tr[u]=pos[++k];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>pos[i];
dfs(1);
for(int i=1;i<=n;i++)
{
cout<<tr[i];
if(i<n)cout<<' ';
}
return 0;
}
L2-036 网红点打卡攻略 (25 分)
#include <bits/stdc++.h>
using namespace std;
const int N=210;
int g[N][N];
int n,m,k;
int val=0x3f3f3f3f,idx;
int main()
{
cin>>n>>m;
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=c;
}
cin>>k;
int sum=0;
for(int i=1;i<=k;i++)
{
int cnt;
bool f=false;
cin>>cnt;
int res=0;
set<int>s;
if(cnt!=n)f=true;
int first;
cin>>first;
s.insert(first);
if(!g[0][first])f=true;
else
{
res+=g[0][first];
vector<int>v;
v.push_back(first);
for(int j=1;j<cnt;j++)
{
int x;
cin>>x;
v.push_back(x);
s.insert(x);
}
for(int j=0;j<v.size()-1;j++)
if(g[v[j]][v[j+1]])
res+=g[v[j]][v[j+1]];
else f=true;
if(g[v[v.size()-1]][0])
res+=g[v[v.size()-1]][0];
else f=true;
if(s.size()!=n)f=true;
}
if(!f)
{
sum++;
if(res<val)
{
val=res;
idx=i;
}
}
}
cout<<sum<<endl;
cout<<idx<<' '<<val;
return 0;
}
L2-037 包装机 (25 分)
包装机
模拟栈
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n,m,s;
queue<char>v[N];
vector<int>op;
int main()
{
cin>>n>>m>>s;
for(int i=1;i<=n;i++)
{
for(int j=0;j<m;j++)
{
char x;
cin>>x;
v[i].push(x);
}
}
int x;
while(cin>>x,x!=-1)op.push_back(x);
stack<char>stk;
for(auto x:op)
{
if(x)
{
if(v[x].size())
{
if(stk.size()>=s)
{
cout<<stk.top();
stk.pop();
}
stk.push(v[x].front());
v[x].pop();
}
}
else
{
if(stk.size()>=1)
{
cout<<stk.top();
stk.pop();
}
}
}
return 0;
}
L2-038 病毒溯源 (25 分)
病毒溯源
dfs求字典序最少的最长路
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n;
vector<vector<int>>v;
int height;
bool st[N];
bool vis[N];
vector<int>res;
void dfs(int u,vector<int>&p)
{
vis[u]=true;
p.push_back(u);
if(p.size()>res.size())
{
res.clear();
for(int i=0;i<p.size();i++)res.push_back(p[i]);
}
for(int i=0;i<v[u].size();i++)
{
if(vis[v[u][i]])continue;
dfs(v[u][i],p);
}
p.pop_back();
vis[u]=false;
}
int main()
{
cin>>n;
v.resize(n+1);
for(int i=0;i<n;i++)
{
int k;
cin>>k;
for(int j=0;j<k;j++)
{
int x;
cin>>x;
v[i].push_back(x);
st[x]=true;
}
sort(v[i].begin(),v[i].end());
}
for(int i=0;i<n;i++)
{
if(!st[i])
{
vector<int>p;
dfs(i,p);
}
}
cout<<res.size()<<endl;
for(int i=0;i<res.size();i++)
{
cout<<res[i];
if(i<res.size()-1)cout<<' ';
}
return 0;
}
L2-039 清点代码库 (25 分)
#include <bits/stdc++.h>
using namespace std;
int n,m;
map<vector<int>,int>mp;
set<vector<int>>hs;
struct cmp
{
bool operator()(const pair<vector<int>,int>&a,const pair<vector<int>,int>&b)const
{
if(a.second!=b.second)return a.second>b.second;
else return a.first<b.first;
}
};
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
vector<int>v;
for(int j=1;j<=m;j++)
{
int x;
cin>>x;
v.push_back(x);
}
hs.insert(v);
mp[v]++;
}
set<pair<vector<int>,int>,cmp>s;
cout<<hs.size()<<endl;
for(auto x:hs)s.insert({x,mp[x]});
for(auto x:s)
{
cout<<x.second;
for(int i=0;i<x.first.size();i++)cout<<' '<<x.first[i];
cout<<endl;
}
return 0;
}
L2-040 哲哲打游戏 (25 分)
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e5+10;
int cnt[N];
vector<int>v[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int k;
cin>>k;
for(int j=0;j<k;j++)
{
int x;
cin>>x;
v[i].push_back(x);
}
}
int p=1;
while(m--)
{
int x,y;
cin>>x>>y;
if(x==0) p=v[p][y-1];
else if(x==1)cnt[y]=p,cout<<p<<endl;
else if(x==2)p=cnt[y];
}
cout<<p<<endl;
return 0;
}
类似资料：