结合最近十年L2，发现了一些考察规律。
考点方面
-
基础数据结构：链表模拟，树的构造，树的遍历（前中后序层序遍历），图的遍历，并查集的应用，堆栈，手写小根堆
-
标准模板库（STL)的灵活使用：map,set,vector的嵌套，特殊键值，重写排序规则，大小比较等
-
结构体的应用：排序规则的写法
-
基础算法：DFS,LIS(diworth定理和二分优化）
-
细节比较多有一定思维量的模拟
数据，输出方面
-
天坑数据，极限数据较多
-
输出对格式有特殊要求
L2-001 紧急救援 (25 分)
考察内容：图论最短路问题，基于迪杰斯特拉算法的修改
算法之迪杰斯特拉（dijkstra）非常详细介绍_PRML_MAN的博客-CSDN博客_迪杰斯特拉算法
Dijkstra算法-(迪杰斯特拉)算法的迭代实现与优先队列实现 图解算法过程_冰冻火山的博客-CSDN博客_dijkstra算法优先队列
代码采用了队列优化和邻接表，细节较多，但时间复杂度低
本题要求，“你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。”
就是说，是最短路就两者都要更新，等于最短路，取能召集更多救援队的那一条即可。
和传统最短路问题不同，本题我们如果发现了通往pos点更短的路径 ，在修改最短路的同时，还应该对pos点进行状态转移，最短路径条数直接更新为连接它的点的最短路径条数，能召集最多的救援队再加上pos点即可
例如，红色点发现了比两个黄色点更优的最短路，也就是绿色点时，需要继承这一路全部信息。
if(dis[now.id]+s[x].w<dis[j])
{
dis[j]=dis[now.id]+s[x].w;
maxval[j]=maxval[now.id]+val[j];
pre[j]=now.id;
cnt[j]=cnt[now.id];
struct node tail;
tail.id=j;
tail.dis=dis[j];
q.push(tail);
}如果等于最短路，pos还应该加上最短路条数，然后对最短路进行选择，可以选择包含本点也可以不选择，取最大值即可。
如下图，通往红色点的最短路有三条等价时，需要加上这三条的最短路条数，在这三条中选取救援队最多的即可
else if(dis[now.id]+s[x].w==dis[j])
{
cnt[j]+=cnt[now.id];
if(maxval[j]<maxval[now.id]+val[j])
{
maxval[j]=maxval[now.id]+val[j];
pre[j]=now.id;
}
}然后就是答案的输出，我们设置pre数组，代表每个点之前的点的标号，修正pre数组时 ，在以上两种情况更新时，随之更新即可
# include<iostream>
# include<cstring>
# include<queue>
using namespace std;
int dis[550];
struct node
{
int dis,id;
friend bool operator<(node a,node b)
{
return a.dis>b.dis;
}
};
bool book[550];
typedef struct
{
int b,e,w;
}xinxi;
xinxi s[1000000];
int f[1000000];
int nex[1000000];
int len;
priority_queue<node>q;
void add(int x,int y,int z)
{
s[len].b=x;
s[len].e=y;
s[len].w=z;
nex[len]=f[x];
f[x]=len;
len++;
}
int val[550];
int maxval[550];
int pre[550];
int cnt[550];
int ans[550];
int main ()
{
memset(f,-1,sizeof(f));
int n,m,st,d;
cin>>n>>m>>st>>d;
for(int i=0;i<n;i++)
{
cin>>val[i];
}
while(m--)
{
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
for(int i=0;i<n;i++)
{
dis[i]=0x3f3f3f;
}
dis[st]=0;
struct node head;
head.dis=0;
cnt[st]=1;
pre[st]=-1;
maxval[st]=val[st];
head.id=st;
q.push(head);
while(!q.empty())
{
struct node now;
now=q.top();
q.pop();
if(book[now.id])
continue;
book[now.id]=1;
int x=f[now.id];
while(x!=-1)
{
int j=s[x].e;
if(dis[now.id]+s[x].w<dis[j])
{
dis[j]=dis[now.id]+s[x].w;
maxval[j]=maxval[now.id]+val[j];
pre[j]=now.id;
cnt[j]=cnt[now.id];
struct node tail;
tail.id=j;
tail.dis=dis[j];
q.push(tail);
}
else if(dis[now.id]+s[x].w==dis[j])
{
cnt[j]+=cnt[now.id];
if(maxval[j]<maxval[now.id]+val[j])
{
maxval[j]=maxval[now.id]+val[j];
pre[j]=now.id;
}
}
x=nex[x];
}
}
cout<<cnt[d]<<" ";
cout<<maxval[d]<<endl;
int len1=0;
while(d!=-1)
{
ans[len1]=d;
len1++;
d=pre[d];
}
for(int i=len1-1;i>=0;i--)
{
if(i)
cout<<ans[i]<<" ";
else
cout<<ans[i];
}
return 0;
}
L2-002 链表去重 (25 分)
本题无需严格模拟链表各项操作，注意到我们将原始链表重新存入一个结构体数组中，编号变成其遍历顺序。一旦出现了重复情况，我们把重复的元素放到>n的位置，这样我们就把链表分成了两部分，1-n是去重后的，>n是重复的
细节较多，比如可能全是重复的情况，也可能没有重复情况；
还有就是，本题的所谓五位数字编号，并不是字符串，就是普通的数字编号，00001与1是等价的。这一特殊要求仅仅体现在答案的输出。
链表遍历操作
for(int i=1; i<=n; i++)
{
int id,val,nex;
cin>>id>>val>>nex;
s[id].val=val;
s[id].id=id;
s[id].nex=nex;
}
int nowid=st,cnt1=1,cnt2=1;
while(nowid!=-1)
{
int val=abs(s[nowid].val);
if(book[val])
{
t[cnt2+n]=s[nowid];
cnt2++;
nowid=s[nowid].nex;
continue;
}
book[val]=1;
t[cnt1]=s[nowid];
cnt1++;
nowid=s[nowid].nex;
}
剩下的平移操作，我写的比较复杂，建议自己模拟
# include<iostream>
# include<cstring>
# include<queue>
# include<iomanip>
using namespace std;
# define maxn 100000*2
typedef struct
{
int id;
int nex;
int val;
}link;
link s[maxn], t[maxn];
int n,st;
bool book[maxn];
int main ()
{
cin>>st>>n;
for(int i=1; i<maxn; i++)
{
t[i].id=-1;
}
for(int i=1; i<=n; i++)
{
int id,val,nex;
cin>>id>>val>>nex;
s[id].val=val;
s[id].id=id;
s[id].nex=nex;
}
int nowid=st,cnt1=1,cnt2=1;
while(nowid!=-1)
{
int val=abs(s[nowid].val);
if(book[val])
{
t[cnt2+n]=s[nowid];
cnt2++;
nowid=s[nowid].nex;
continue;
}
book[val]=1;
t[cnt1]=s[nowid];
cnt1++;
nowid=s[nowid].nex;
}
int nowcnt=1;
cnt1--;
cnt2--;
for(int i=1; i<=n; i++)
{
if(t[i].id!=-1)
{
if(nowcnt==1&&nowcnt<cnt1)
{
cout<<setw(5)<<setfill('0')<<t[i].id<<" "<<t[i].val<<" ";
nowcnt++;
}
else if(nowcnt<=cnt1)
{
if(cnt1!=1)
cout<<setw(5)<<setfill('0')<<t[i].id<<endl;
cout<<setw(5)<<setfill('0')<<t[i].id<<" "<<t[i].val<<" ";
if(nowcnt==cnt1)
{
cout<<-1<<endl;
}
nowcnt++;
}
}
}
nowcnt=1;
for(int i=n+1; i<=2*n; i++)
{
if(t[i].id!=-1)
{
if(nowcnt==1&&nowcnt<cnt2)
{
cout<<setw(5)<<setfill('0')<<t[i].id<<" "<<t[i].val<<" ";
nowcnt++;
}
else if(nowcnt<=cnt2)
{
if(cnt2!=1)
cout<<setw(5)<<setfill('0')<<t[i].id<<endl;
cout<<setw(5)<<setfill('0')<<t[i].id<<" "<<t[i].val<<" ";
if(nowcnt==cnt2)
{
cout<<-1<<endl;
}
nowcnt++;
}
}
}
return 0;
}
L2-003 月饼 (25 分)
贪心 ，性价比排序，没有太多好说的
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
typedef struct
{
double v,p,c;
} yue;
yue s[maxn];
bool cmp(yue a,yue b)
{
return a.c>b.c;
}
int main ()
{
int n;
double sum;
cin>>n>>sum;
for(int i=1; i<=n; i++)
{
cin>>s[i].v;
}
for(int i=1; i<=n; i++)
{
cin>>s[i].p;
s[i].c=s[i].p/s[i].v;
}
sort(s+1,s+1+n,cmp);
double ans=0,nowsum=0;
for(int i=1;i<=n;i++)
{
if(nowsum+s[i].v<=sum)
{
nowsum+=s[i].v;
ans+=s[i].p;
}
else
{
double cha=sum-nowsum;
nowsum+=cha;
ans+=s[i].c*cha;
break;
}
}
cout<<fixed<<setprecision(2)<<ans;
return 0;
}
L2-004 这是二叉搜索树吗？ (25 分)
考察内容 前中后序遍历
二叉树前序遍历、中序遍历、后序遍历、层序遍历的直观理解_白夜行的狼的博客-CSDN博客_中序遍历
在已知中序的情况下，知前可推后，知后可推前
已知前序遍历和中序遍历求二叉树_SEVENY_的博客-CSDN博客_已知前序遍历中序遍历求二叉树
本题，我们在找到前序遍历的根节点时，向右寻找其左子树和右子树，对于原二叉搜索树，按照以下规则，也就是把连续小于根节点的作为左子树，否则是右子树，如果分界点满足要求，就说明可以继续往下递归。
其镜像，只需要把规则反过来即可，本代码放在了同一个dfs里，用flag决定操作内容
int mid1=left+1,mid2=right;
while(mid1<=right&&tree[left]>tree[mid1])
mid1++;
while(mid2>=left+1&&tree[left]<=tree[mid2])
mid2--;
if(mid1==mid2+1)
{
dfs(left+1,mid1-1);
dfs(mid1,right);
root.push_back(tree[left]);
}然后就是答案的输出了，要求后序遍历，我们可以假设原序列满足要求，根节点找到之后，先遍历左子树，在遍历右子树，最后把本次根节点放入vector容器，这样就顺便模拟了后序遍历，最后检查一下这一容器是否装下来全部节点，否则对其镜像进行判断，再否则，就不满足条件了
while循环建议单开程序调试，下标比较易错
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
int tree[1010],flag,check;
vector<int>root;
void dfs(int left,int right)
{
if(left>right)
return ;
if(flag==0)
{
int mid1=left+1,mid2=right;
while(mid1<=right&&tree[left]>tree[mid1])
mid1++;
while(mid2>=left+1&&tree[left]<=tree[mid2])
mid2--;
if(mid1==mid2+1)
{
dfs(left+1,mid1-1);
dfs(mid1,right);
root.push_back(tree[left]);
}
else
{
check=1;
return ;
}
}
else
{
int mid1=left+1,mid2=right;
while(mid1<=right&&tree[left]<=tree[mid1])
mid1++;
while(mid2>=left+1&&tree[left]>tree[mid2])
mid2--;
if(mid1==mid2+1)
{
dfs(left+1,mid1-1);
dfs(mid1,right);
root.push_back(tree[left]);
}
else
{
check=1;
return ;
}
}
}
int main ()
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>tree[i];
}
dfs(1,n);
if(!check)
{
cout<<"YES"<<endl;
int sizecnt=0;
for(auto it:root)
{
sizecnt++;
if(sizecnt<root.size())
cout<<it<<" ";
else
cout<<it;
}
return 0;
}
else
{
root.clear();
flag=1;
check=0;
dfs(1,n);
if(!check)
{
cout<<"YES"<<endl;
int sizecnt=0;
for(auto it:root)
{
sizecnt++;
if(sizecnt<root.size())
cout<<it<<" ";
else
cout<<it;
}
return 0;
}
}
cout<<"NO";
return 0;
}
L2-005 集合相似度 (25 分)
Set的应用，查找共同元素，两个集合大小相加减去共同元素就是不相同元素。
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
set<int>s[55];
int main ()
{
int n,size;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>size;
while(size--)
{
int x;
cin>>x;
s[i].insert(x);
}
}
int t;
cin>>t;
while(t--)
{
int x,y;
cin>>x>>y;
double sum=s[x].size()+s[y].size(),cnt=0;
for(auto it:s[x])
{
if(s[y].find(it)!=s[y].end())
{
cnt++;
}
}
cout<<fixed<<setprecision(2)<<cnt/(sum-cnt)*100<<'%'<<endl;
}
return 0;
}
L2-006 树的遍历 (25 分)
考察内容，已知后序中序求层序，写的代码比较繁琐，不建议参考，网上有更简洁的
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
typedef struct
{
int id,l=0,r=0;
} s;
s tree[100000];
int mid[1000000],bac[1000000];
int n;
void dfs(int left1,int right1,int left2,int right2,bool check,int father)
{
if(left1>right1)
return ;
if(check==0)
tree[father].l=bac[right1];
else
tree[father].r=bac[right1];
if(left1==right1)
{
return ;
}
int nowmid=left2;
for(int i=left2; i<=right2; i++)
{
if(mid[i]==bac[right1])
{
nowmid=i;
break;
}
}
dfs(left1,left1+nowmid-left2-1,left2,nowmid-1,0,bac[right1]);
dfs(left1+nowmid-left2,right1-1,nowmid+1,right2,1,bac[right1]);
}
queue<s>q;
vector<int>ans;
vector<int> vec;
queue<int> que;
int main ()
{
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>bac[i];
}
for(int i=1; i<=n; i++)
{
cin>>mid[i];
}
dfs(1,n,1,n,0,0);
for(int i=1; i<=100000; i++)
{
tree[i].id=i;
// cout<<tree[i].l<<" "<<tree[i].r<<endl;
}
//pre(bac[n]);
s head;
head=tree[bac[n]];
q.push(head);
while(!q.empty())
{
s now=q.front();
q.pop();
if(now.id==0)
break;
ans.push_back(now.id);
if(now.l)
q.push(tree[now.l]);
if(now.r)
q.push(tree[now.r]);
}
for(int i=0; i<ans.size(); i++)
{
if(i!=ans.size()-1)
cout<<ans[i]<<" ";
else
cout<<ans[i];
}
return 0;
}
L2-007 家庭房产 (25 分)
考察知识点：并查集
【算法与数据结构】—— 并查集_酱懵静的博客-CSDN博客_并查集
总结来，就是合并操作，查询操作，用f[x]代表了X所在集合的名称。用size代表了该集合元素个数
输出这样要求我们
首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：
家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积意思就是说，对于一个集合整体，我们把其中最小元素作为该集合名称，这样就要求我们在集合合并时，把更小的当成父亲即可。 然后，对于家庭人口数，就是size大小，合并之后，把保持的各套房餐分别加入集合进行计算即可，
被注释掉的内容更好理解，本代码把对房产的分配也加入到合并操作，可忽略
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
int f[100000];
int son[10];
double cnt[100000],s[100000];
int getf(int x)
{
if(x==f[x])
return x;
else
{
f[x]=getf(f[x]);
return f[x];
}
}
map<int,int>m;
double siz[100000];
typedef struct
{
double pcnt,ps;
int size, id;
}t;
t ans[100000];
bool cmp(t a, t b)
{
if(a.ps!=b.ps)
return a.ps>b.ps;
return a.id<b.id;
}
double tempcnt[1010],temps[1010];
int num[1010];
int main ()
{
int n;
cin>>n;
for(int i=0;i<100000;i++)
{
f[i]=i;
siz[i]=1;
}
for(int i=1;i<=n;i++)
{
int x,y,z;
cin>>x>>y>>z;
num[i]=x;
m[x]=1;
m[y]=1;
m[z]=1;
int k=0;
cin>>k;
memset(son,0,sizeof(son));
for(int i=1;i<=k;i++)
{
cin>>son[i];
m[son[i]]=1;
}
cin>>tempcnt[i]>>temps[i];
if(x!=-1)
{
k++;
son[k]=x;
}
if(y!=-1)
{
k++;
son[k]=y;
}
if(z!=-1)
{
k++;
son[k]=z;
}
for(int i=1;i<k;i++)
{
int t1=getf(son[i]);
int t2=getf(son[i+1]);
if(t1!=t2)
{
f[max(t1,t2)]=min(t1,t2);
siz[min(t1,t2)]+=siz[max(t1,t2)];
s[min(t1,t2)]+=s[max(t1,t2)];
cnt[min(t1,t2)]+=cnt[max(t1,t2)];
}
}
int t=getf(son[k]);
s[t]+=temps[i];
cnt[t]+=tempcnt[i];
}
/* for(int i=1;i<=n;i++)
{
int fa=getf(num[i]);
cnt[fa]+=tempcnt[i];
s[fa]+=temps[i];
}
*/
int len=1;
for(int i=0;i<=100000;i++)
{
if(f[i]==i&&m[i])
{
ans[len].id=i;
ans[len].pcnt=double(cnt[i]/siz[i]);
ans[len].ps=double(s[i]/siz[i]);
ans[len].size=siz[i];
len++;
}
}
sort(ans+1,ans+len,cmp);
cout<<len-1<<endl;
for(int i=1;i<len;i++)
{
cout<<setw(4)<<setfill('0')<<ans[i].id<<" "<<ans[i].size<<" "<<fixed<<setprecision(3)<<ans[i].pcnt<<" "<<fixed<<setprecision(3)<<ans[i].ps<<endl;
}
return 0;
}
L2-008 最长对称子串 (25 分)
子串与子序列的区别
举例说明子串和子序列的区别 ！！！_帅帅邬同学的博客-CSDN博客_子序列和子串的区别
本题是子串，对于一个对称子串，无非两种情况，偶数串奇数串，奇数串除了中间位置特殊，其余两两相等，也就是我们可以枚举中间位置，向两边扩展即可，也叫双指针
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
string s;
int main ()
{
getline(cin,s);
int ans=0;
for(int i=0;i<s.length();i++)
{
int len=1;
int left=i-1,right=i+1;
while(left>=0&&right<s.length()&&s[left]==s[right])
{
len+=2;
left--;
right++;
}
ans=max(ans,len);
if(s[i]==s[i+1])
{
len=2;
left=i-1;
right=i+2;
while(left>=0&&right<s.length()&&s[left]==s[right])
{
len+=2;
left--;
right++;
}
ans=max(ans,len);
}
}
cout<<ans;
return 0;
}
L2-009 抢红包 (25 分)
按照题目要求，结构体模拟即可
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
typedef struct
{
double sum;
int cnt;
int id;
}people;
people s[10010];
bool cmp(people a,people b)
{
if(a.sum!=b.sum)
return a.sum>b.sum;
if(a.cnt!=b.cnt)
return a.cnt>b.cnt;
return a.id<b.id;
}
int main ()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int k;
cin>>k;
s[i].id=i;
double sum=0;
for(int i=1;i<=k;i++)
{
int id;
double sum1;
cin>>id>>sum1;
s[id].cnt++;
s[id].sum+=sum1;
sum+=sum1;
}
s[i].sum-=sum;
}
sort(s+1,s+1+n,cmp);
for(int i=1;i<=n;i++)
{
cout<<s[i].id<<" "<<fixed<<setprecision(2)<<s[i].sum/100<<endl;
}
return 0;
}
L2-010 排座位 (25 分)
并查集与set的应用，我们把朋友保留在一起，敌对关系用set存,便于快速查找，find!=s.end()
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
set<int>s[110];
int f[110];
int getf(int x)
{
if(x==f[x])
return x;
else
{
f[x]=getf(f[x]);
return f[x];
}
}
int main ()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
f[i]=i;
}
while(m--)
{
int x,y,z;
cin>>y>>z>>x;
if(x==1)
{
int t1=getf(y);
int t2=getf(z);
f[t2]=t1;
}
else
{
s[y].insert(z);
s[z].insert(y);
}
}
while(k--)
{
int x,y;
cin>>x>>y;
int t1=getf(x),t2=getf(y);
if(t1==t2&&s[x].find(y)==s[x].end())
{
cout<<"No problem"<<endl;
}
else if(t1!=t2&&s[x].find(y)==s[x].end())
{
cout<<"OK"<<endl;
}
else if(t1==t2&&s[x].find(y)!=s[x].end())
{
cout<<"OK but..."<<endl;
}
else
{
cout<<"No way"<<endl;
}
}
return 0;
}
L2-011 玩转二叉树 (25 分)
猜想规律，在层序遍历求解时，交换左右子树加入队列的次数，得出答案
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
int mid[500000],pre[500000];
typedef struct
{
int id,l,r;
}s;
s tree[500000];
int dfs(int l1,int r1,int l2,int r2)
{
if(l1>r1)
return -1;
int nowf=pre[l2];
int nowmid;
for(int i=l1;i<=r1;i++)
{
if(nowf==mid[i])
{
nowmid=i;
}
}
tree[nowf].l=dfs(l1,nowmid-1,l2+1,l2+nowmid-l1);
tree[nowf].r=dfs(nowmid+1,r1,l2+nowmid-l1+1,r2);
return nowf;
}
queue<s>q;
vector<int>ans;
int main ()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>mid[i];
}
for(int i=1;i<=n;i++)
{
cin>>pre[i];
}
for(int i=0;i<500000;i++)
{
tree[i].id=i;
tree[i].l=-1;
tree[i].r=-1;
}
dfs(1,n,1,n);
q.push(tree[pre[1]]);
while(!q.empty())
{
s now=q.front();
q.pop();
if(now.id==-1)
break;
ans.push_back(now.id);
if(now.r!=-1)
q.push(tree[now.r]);
if(now.l!=-1)
q.push(tree[now.l]);
}
for(int i=0;i<ans.size();i++)
{
if(i!=ans.size()-1)
cout<<ans[i]<<" ";
else
cout<<ans[i];
}
return 0;
}
L2-012 关于堆的判断 (25 分)
C++手写堆的实现（LuoguP3378模板）_MerakAngel的博客-CSDN博客_c++手写堆
本题考察堆的手写，由于是一定范围内的负数，我们可以采用数组平移，构建好堆之后，我们离散化求出每个元素的下标，便于答案的判断
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
int heap[10000];
int heap_size;
void put(int d)
{
int now,next;
heap_size++;
heap[heap_size]=d;
now=heap_size;
while(now>1)
{
next=now>>1;
if(heap[now]>=heap[next])
return ;
swap(heap[now],heap[next]);
now=next;
}
}
int pos[1000000];
int get()
{
int now,next,res;
res=heap[1];
heap[1]=heap[heap_size];
heap_size--;
now=1;
while(now*2<=heap_size)
{
next=now<<1;
if(next<heap_size&&heap[next+1]<heap[next])
next++;
if(heap[now]<=heap[next])
return res;
swap(heap[now],heap[next]);
now=next;
}
}
int main ()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
put(x);
}
for(int i=1;i<=n;i++)
{
pos[heap[i]+10005]=i;
}
while(m--)
{
int x,y;
cin>>x;
string s;
cin>>s;
if(s=="is")
{
cin>>s;
if(s=="the")
{
cin>>s;
if(s=="root")
{
if(pos[x+10005]==1)
cout<<'T'<<endl;
else
cout<<'F'<<endl;
}
else
{
cin>>s>>y;
if(pos[y+10005]>>1==pos[x+10005])
cout<<'T'<<endl;
else
cout<<'F'<<endl;
}
}
else if(s=="a")
{
cin>>s>>s>>y;
if(pos[x+10005]>>1==pos[y+10005])
cout<<'T'<<endl;
else
cout<<'F'<<endl;
}
}
else if(s=="and")
{
cin>>y>>s>>s;
if(pos[y+10005]>>1==pos[x+10005]>>1)
cout<<'T'<<endl;
else
cout<<'F'<<endl;
}
}
return 0;
}
L2-013 红色警报 (25 分)
考察内容，强连通分量，图的遍历。
关于题意“当失去一个城市导致国家被分裂为多个无法连通的区域时”，说的很不清晰，意思是失去一个城市，导致了除了本城市与本城市所在整体的联通性改变外，还有部分城市被迫脱离了整体，也就是形成了新的强连通分量。我们对于已经破坏的城市不再搜索，算成一个强连通，其余再计算即可，当比之前多出来2个以上时，说明红色警报
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
typedef struct
{
int b,e;
}xinxi;
xinxi s[100000];
int f[100000];
int nex[100000];
int len;
void add(int x,int y)
{
s[len].b=x;
s[len].e=y;
nex[len]=f[x];
f[x]=len;
len++;
}
bool broken[550];
bool col[550];
int n,m;
void dfs(int now)
{
col[now]=1;
//cout<<now;
int x=f[now];
while(x!=-1)
{
int j=s[x].e;
if(!broken[j]&&!col[j])
{
dfs(j);
}
x=nex[x];
}
}
int getcnt()
{
memset(col,0,sizeof(col));
int temp=0;
for(int i=0;i<n;i++)
{
if(!col[i]&&!broken[i])
{
dfs(i);
temp++;
}
else if(broken[i])
temp++;
}
return temp;
}
int cnt;
int main ()
{
cin>>n>>m;
memset(f,-1,sizeof(f));
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
int k;
cin>>k;
int precnt=getcnt();
// cout<<precnt<<endl;
for(int i=1;i<=k;i++)
{
int x;
cin>>x;
broken[x]=1;
int nowcnt=getcnt();
if(nowcnt>precnt+1)
{
cout<<"Red Alert: City "<<x<<" is lost!"<<endl;
}
else
{
cout<<"City "<<x<<" is lost."<<endl;
}
if(i==n)
{
cout<<"Game Over."<<endl;
}
precnt=nowcnt;
}
return 0;
}
L2-014 列车调度 (25 分)
考察内容，思维，diworth定理，LIS的二分优化
Diworth定理_dcaqnjmx39255的博客-CSDN博客
[NOIP2010 普及组] 导弹拦截 – 洛谷
（题解区有详解二分）
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
int a[100000+10];
int q[100000+10];
int main ()
{
//求最长下降子序列个数
//求最长上升子序列长度
int n;
cin>>n;
cin>>a[1];
int len=1;
q[len]=a[1];
for(int i=2;i<=n;i++)
{
cin>>a[i];
if(a[i]>q[len])
{
len++;
q[len]=a[i];
}
else
{
int pos=lower_bound(q+1,q+1+len,a[i])-q;
q[pos]=a[i];
}
}
cout<<len;
return 0;
}
L2-015 互评成绩 (25 分)
结构体模拟排序即可
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
typedef struct
{
double a;
}student;
student s[100000];
bool cmp(student a,student b)
{
return a.a>b.a;
}
int main ()
{
int n,k,m;
cin>>n>>k>>m;
for(int i=1;i<=n;i++)
{
double sum=0;
double max1=-1;
double min1=999999;
double now;
for(int i=1;i<=k;i++)
{
cin>>now;
sum+=now;
max1=max(max1,now);
min1=min(min1,now);
}
sum-=(max1+min1);
sum/=(k-2);
s[i].a=sum;
}
sort(s+1,s+1+n,cmp);
for(int i=m;i>=1;i--)
{
if(i!=1)
cout<<fixed<<setprecision(3)<<s[i].a<<" ";
else
cout<<fixed<<setprecision(3)<<s[i].a;
}
return 0;
}
L2-016 愿天下有情人都是失散多年的兄妹 (25 分)
考察内容，Dfs,结构体，我们只需要对一个人上溯五代并标记祖先，对另一个人上溯五代查看是否重复即可，另外注意性别问题
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
typedef struct
{
int f,m,id;
int xing;
}people;
people s[100000+10];
set<int>book1;
void dfs1(int step,int now)
{
if(step==6)
return ;
book1.insert(now);
if(s[now].f!=-1)
dfs1(step+1,s[now].f);
if(s[now].m!=-1)
dfs1(step+1,s[now].m);
}
int flag;
void dfs2(int step,int now)
{
if(step==6)
return ;
if(flag)
return ;
if(book1.find(now)!=book1.end())
{
flag=1;
return ;
}
if(s[now].f!=-1)
dfs2(step+1,s[now].f);
if(s[now].m!=-1)
dfs2(step+1,s[now].m);
}
int main ()
{
for(int i=0;i<=100000;i++)
{
s[i].id=i;
s[i].f=-1;
s[i].m=-1;
}
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int id;
char ch;
int f,m;
cin>>id>>ch>>f>>m;
s[id].f=f;
s[id].m=m;
if(ch=='M')
s[id].xing=1;
else
s[id].xing=2;
if(f!=-1)
s[f].xing=1;
if(m!=-1)
s[m].xing=2;
}
int k;
cin>>k;
while(k--)
{
int x,y;
cin>>x>>y;
if(s[x].xing==s[y].xing)
{
cout<<"Never Mind"<<endl;
}
else
{
book1.clear();
flag=0;
dfs1(1,x);
dfs2(1,y);
if(flag)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
}
return 0;
}
L2-017 人以群分 (25 分)
贪心，奇数时，n/2+1个最多的分配，否则各分配n/2
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
typedef long long int ll;
ll a[100000];
bool cmp(ll a,ll b)
{
return a>b;
}
int main ()
{
int n;
cin>>n;
ll sum1=0,sum=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
}
int mid=n>>1;
if(n&1)
mid++;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=mid;i++)
{
sum1+=a[i];
}
cout<<"Outgoing #: "<<mid<<endl;
cout<<"Introverted #: "<<n/2<<endl;
cout<<"Diff = "<<abs(sum-sum1*2)<<endl;
return 0;
}
L2-018 多项式A除以B (25 分)
知识点比较独立，没有备考价值，略
L2-019 悄悄关注 (25 分)
仍然是结构体模拟，注意细节即可
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
typedef long long int ll;
typedef struct
{
string s;
int cnt;
bool book;
}people;
people s[100000];
map<string,int>m;
bool cmp(people a,people b)
{
if(a.book!=b.book)
return a.book>b.book;
else
return a.s<b.s;
}
int main ()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
m[s]=1;
}
int t;
cin>>t;
double sum=0;
for(int i=1;i<=t;i++)
{
cin>>s[i].s>>s[i].cnt;
sum+=s[i].cnt;
}
sum/=t;
int cnt=0;
for(int i=1;i<=t;i++)
{
if(m[s[i].s]==0&&s[i].cnt>sum)
{
s[i].book=1;
cnt++;
}
}
if(!cnt)
{
cout<<"Bing Mei You";
return 0;
}
else
{
sort(s+1,s+1+t,cmp);
for(int i=1;i<=t;i++)
{
if(s[i].book)
{
cout<<s[i].s<<endl;
}
}
}
return 0;
}
L2-020 功夫传人 (25 分)
dfs，注意即使遇见得到弟子，仅仅增加本弟子功力，再继续传的话，仍然递减
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
typedef long long int ll;
typedef struct
{
int b,e;
}xinxi;
xinxi s[2*100000+10];
int f[2*100000+10],nex[2*100000+10];
int len;
void add(int x,int y)
{
s[len].b=x;
s[len].e=y;
nex[len]=f[x];
f[x]=len;
len++;
}
map<int,int>m;
double ans[100000+10];
int n;
double r;
void dfs(int now,double sum)
{
ans[now]=sum;
if(m[now])
{
ans[now]*=m[now];
}
int x=f[now];
while(x!=-1)
{
int j=s[x].e;
dfs(j,sum*r);
x=nex[x];
}
}
int main ()
{
memset(f,-1,sizeof(f));
cin>>n;
double sum;
cin>>sum;
cin>>r;
r=(1-r/100);
for(int i=0;i<n;i++)
{
int k;
cin>>k;
if(!k)
cin>>m[i];
else
{
while(k--)
{
int x;
cin>>x;
add(i,x);
}
}
}
dfs(0,sum);
double answer=0;
for(int i=0;i<n;i++)
{
if(m[i])
answer+=ans[i];
}
cout<<(int)answer;
return 0;
}
L2-021 点赞狂魔 (25 分)
还是结构体，细节是不够三人的情况
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
typedef long long int ll;
typedef struct
{
int cnt;
double p;
string name;
}biao;
biao s[1010];
set<int>cnt;
bool cmp(biao a,biao b)
{
if(a.cnt!=b.cnt)
return a.cnt>b.cnt;
return a.p<b.p;
}
int main ()
{
int n;
cin>>n;
for(int i=1;i<=100;i++)
{
s[i].name='-';
}
for(int i=1;i<=n;i++)
{
cin>>s[i].name;
int k;
cin>>k;
cnt.clear();
for(int i=1;i<=k;i++)
{
int id;
cin>>id;
cnt.insert(id);
}
s[i].cnt=cnt.size();
s[i].p=double(k)/double(s[i].cnt);
}
sort(s+1,s+1+n,cmp);
for(int i=1;i<3;i++)
{
cout<<s[i].name<<" ";
}
cout<<s[3].name;
return 0;
}
L2-022 重排链表 (25 分)
类似于上一个链表题目，我们按照遍历顺序重新存储链表，再分奇偶双指针扩展即可
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 100000*2
# include<vector>
# include<set>
# include<map>
typedef long long int ll;
typedef struct
{
int id;
int nex;
int val;
} link;
link s[100000+10];
link t[100000+10];
int main ()
{
int st,n;
cin>>st>>n;
for(int i=0; i<=100000; i++)
{
s[i].id=i;
s[i].nex=-1;
}
for(int i=1; i<=n; i++)
{
int id,nex,val;
cin>>id>>val>>nex;
s[id].nex=nex;
s[id].val=val;
}
int len=1;
int now=st;
while(now!=-1)
{
t[len]=s[now];
now=s[now].nex;
len++;
}
len--;
n=len;
if(n%2==0)
{
int left=1;
int right=n;
while(left<=n/2&&right>=n/2+1)
{
cout<<setw(5)<<setfill('0')<<t[right].id<<" "<<t[right].val<<" "<<setw(5)<<setfill('0')<<t[left].id<<endl;
if(right-1!=left)
cout<<setw(5)<<setfill('0')<<t[left].id<<" "<<t[left].val<<" "<<setw(5)<<setfill('0')<<t[right-1].id<<endl;
else
cout<<setw(5)<<setfill('0')<<t[left].id<<" "<<t[left].val<<" "<<-1<<endl;
left++;
right--;
}
}
else
{
int left=1;
int right=n;
while(left<=n/2&&right>=n/2+2)
{
cout<<setw(5)<<setfill('0')<<t[right].id<<" "<<t[right].val<<" "<<setw(5)<<setfill('0')<<t[left].id<<endl;
if(right-1!=left)
cout<<setw(5)<<setfill('0')<<t[left].id<<" "<<t[left].val<<" "<<setw(5)<<setfill('0')<<t[right-1].id<<endl;
left++;
right--;
}
cout<<setw(5)<<setfill('0')<<t[n>>1|1].id<<" "<<t[n>>1|1].val<<" "<<-1<<endl;
}
return 0;
}
L2-023 图着色问题 (25 分)
不需要dfs染色，只需要对边进行判断即可，边两段不能颜色相同
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
typedef long long int ll;
typedef struct
{
int b,e;
}xinxi;
xinxi s[maxn];
int f[maxn],nex[maxn],c,len;
void add(int x,int y)
{
s[len].b=x;
s[len].e=y;
nex[len]=f[x];
f[x]=len;
len++;
}
set<int>cnt;
int col[550];
int main ()
{
memset(f,-1,sizeof(f));
int n,m;
cin>>n>>m>>c;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
int t;
cin>>t;
while(t--)
{
cnt.clear();
for(int i=1;i<=n;i++)
{
cin>>col[i];
cnt.insert(col[i]);
}
int flag=0;
for(int i=1;i<=n;i++)
{
int x=f[i];
while(x!=-1)
{
int j=s[x].e;
if(col[j]==col[i])
{
flag=1;
break;
}
x=nex[x];
}
}
if(cnt.size()!=c)
flag=1;
if(flag)
{
cout<<"No"<<endl;
}
else
cout<<"Yes"<<endl;
}
return 0;
}
L2-024 部落 (25 分)
考察并查集，set容器
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
typedef long long int ll;
int f[100000];
int getf(int x)
{
if(f[x]==x)
return f[x];
else
{
f[x]=getf(f[x]);
return f[x];
}
}
void hebing(int x,int y)
{
int t1=getf(x);
int t2=getf(y);
if(t2!=t1)
{
f[t2]=t1;
}
}
set<int>s;
set<int>cnt;
int main ()
{
int n;
cin>>n;
for(int i=1;i<=100000;i++)
{
f[i]=i;
}
for(int i=1;i<=n;i++)
{
int k;
cin>>k;
int prex;
cin>>prex;
s.insert(prex);
for(int j=1;j<k;j++)
{
int x;
cin>>x;
s.insert(x);
hebing(x,prex);
prex=x;
}
}
for(int i=1;i<=10000;i++)
{
if(s.find(i)!=s.end())
{
cnt.insert(getf(i));
}
}
cout<<s.size()<<" "<<cnt.size()<<endl;
int t;
cin>>t;
while(t--)
{
int x,y;
cin>>x>>y;
if(getf(x)!=getf(y))
{
cout<<'N'<<endl;
}
else
cout<<'Y'<<endl;
}
return 0;
}L2-025 分而治之 (25 分)
所谓”孤立无援“，就是说没有任何其他节点与之相连，转化成求解强连通分量个数
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
typedef long long int ll;
typedef struct
{
int b,e;
}xinxi;
xinxi s[maxn];
int f[maxn],nex[maxn],len;
void add(int x,int y)
{
s[len].b=x;
s[len].e=y;
nex[len]=f[x];
f[x]=len;
len++;
}
int broken[100000],book[100000],cnt;
void dfs(int now)
{
if(broken[now])
return ;
book[now]=cnt;
int x=f[now];
while(x!=-1)
{
int j=s[x].e;
if(!book[j])
dfs(j);
x=nex[x];
}
}
set<int>ans;
int main ()
{
memset(f,-1,sizeof(f));
int n,m;
cin>>n>>m;
while(m--)
{
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
int k;
cin>>k;
for(int i=1;i<=k;i++)
{
for(int i=1;i<=n;i++)
{
broken[i]=0;
book[i]=0;
}
cnt=1;
int t;
cin>>t;
for(int i=1;i<=t;i++)
{
int x;
cin>>x;
broken[x]=1;
}
for(int i=1;i<=n;i++)
{
if(!book[i])
{
dfs(i);
cnt++;
}
}
ans.clear();
for(int i=1;i<=n;i++)
{
if(book[i]&&!broken[i])
{
ans.insert(book[i]);
}
}
if(ans.size()+t==n)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return 0;
}
L2-026 小字辈 (25 分)
类似于树形结构的遍历，求最深的节点即可
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
typedef long long int ll;
typedef struct
{
int e,b;
}xinxi;
xinxi s[1000000];
int len;
int f[1000000],nex[1000000];
void add(int x,int y)
{
s[len].b=x;
s[len].e=y;
nex[len]=f[x];
f[x]=len;
len++;
}
int id[1000000];
int maxid;
void dfs(int now,int level)
{
int x=f[now];
id[now]=level;
maxid=max(maxid,level);
while(x!=-1)
{
int j=s[x].e;
dfs(j,level+1);
x=nex[x];
}
}
vector<int>ans;
int main ()
{
memset(f,-1,sizeof(f));
int n;
cin>>n;
int root;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(x!=-1)
{
add(x,i);
}
else
{
root=i;
}
}
dfs(root,1);
cout<<maxid<<endl;
for(int i=1;i<=n;i++)
{
if(id[i]==maxid)
{
ans.push_back(i);
}
}
for(int i=0;i<ans.size();i++)
{
if(i!=ans.size()-1)
cout<<ans[i]<<" ";
else
cout<<ans[i];
}
return 0;
}
L2-027 名人堂与代金券 (25 分)
仍然是结构体模拟
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
typedef long long int ll;
typedef struct
{
string id;
int zhi;
int cnt;
}xue;
xue s[100000];
bool cmp(xue a,xue b)
{
if(a.zhi!=b.zhi)
return a.zhi>b.zhi;
return a.id<b.id;
}
int main ()
{
int n,g,k;
cin>>n>>g>>k;
int sum=0;
for(int i=1;i<=n;i++)
{
cin>>s[i].id>>s[i].zhi;
if(s[i].zhi>=g)
sum+=50;
else if(60<=s[i].zhi&&s[i].zhi<g)
sum+=20;
}
sort(s+1,s+1+n,cmp);
s[1].cnt=1;
cout<<sum<<endl;
for(int i=1;i<=n;i++)
{
if(s[i].zhi==s[i-1].zhi&&s[i-1].cnt<=k)
{
cout<<s[i-1].cnt<<" "<<s[i].id<<" "<<s[i].zhi<<endl;
s[i].cnt=s[i-1].cnt;
}
else
{
if(i<=k)
cout<<i<<" "<<s[i].id<<" "<<s[i].zhi<<endl;
s[i].cnt=i;
}
}
return 0;
}L2-028 秀恩爱分得快 (25 分)
坑点！！-0和0截然相反，故用字符串存储名字，转成数字求出下标！
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
typedef long long int ll;
double qin[1010][1010];
int id[1010][550];
bool flag;
int zhuan(string s)
{
int ans=0;
if(s[0]=='-')
{
flag=1;
for(int i=1; i<=s.length()-1; i++)
{
ans=ans*10+(s[i]-'0');
}
}
else
{
for(int i=0; i<=s.length()-1; i++)
{
ans=ans*10+(s[i]-'0');
}
}
return ans;
}
string name[1010];
int xing[1010];
int main ()
{
int n,m;
cin>>n>>m;
for(int i=1; i<=m; i++)
{
cin>>id[i][0];
for(int j=1; j<=id[i][0]; j++)
{
string s;
cin>>s;
flag=0;
id[i][j]=zhuan(s);
name[id[i][j]]=s;
if(flag)
xing[id[i][j]]=1;
}
for(int j=1;j<=id[i][0];j++)
{
for(int k=1;k<=id[i][0];k++)
{
if(xing[id[i][j]]!=xing[id[i][k]])
{
qin[id[i][j]][id[i][k]]+=1/(double(id[i][0]));
}
}
}
}
string a,b;
cin>>a>>b;
int aa=zhuan(a);
int bb=zhuan(b);
double max1=0,max2=0;
for(int i=0;i<n;i++)
{
if(xing[aa]!=xing[i])
{
max1=max(max1,qin[aa][i]);
}
if(xing[bb]!=xing[i])
{
max2=max(max2,qin[bb][i]);
}
}
if(max1==qin[aa][bb]&&max2==qin[bb][aa])
{
cout<<a<<" "<<b;
return 0;
}
for(int i=0;i<n;i++)
{
if(max1==qin[aa][i])
{
cout<<a<<" "<<name[i]<<endl;
}
}
for(int i=0;i<n;i++)
{
if(max2==qin[bb][i])
{
cout<<b<<" "<<name[i]<<endl;
}
}
return 0;
}
L2-029 特立独行的幸福 (25 分)
欧拉筛，筛出素数。然后对于区间内数进行判断即可，死循环的判断用set，一旦出现重复元素，也就代表即将陷入死循环，值得注意的是，每次转化成的1，也要依附于最初元素
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
typedef long long int ll;
set<int>v[10000+10];
bool prim[10000+10];
bool book[10000+10];
set<int>temp;
vector<int>tem;
int zhuan(int x)
{
int ans=0;
while(x)
{
ans+=(x%10)*(x%10);
x/=10;
}
return ans;
}
int main ()
{
//过程中经过的数字都是幸福数
//
memset(prim,1,sizeof(prim));
prim[1]=0;
prim[0]=0;
for(int i=2; i*i<=10000; i++)
{
if(prim[i])
{
for(int j=i*i; j<=10000; j+=i)
{
prim[j]=0;
}
}
}
int left,right;
cin>>left>>right;
for(int i=left; i<=right; i++)
{
temp.clear();
int x=i;
tem.clear();
int flag=0;
tem.push_back(x);
while(x!=1)
{
x=zhuan(x);
tem.push_back(x);
if(temp.find(x)==temp.end())
{
temp.insert(x);
}
else
{
flag=1;
break;
}
}
// cout<<endl;
if(!flag)
{
for(auto it:temp)
{
if(it!=i)
{
book[it]=1;
v[i].insert(it);
}
}
}
}
int flag=0;
for(int i=left;i<=right;i++)
{
if(!book[i]&&v[i].size())
{
if(!prim[i])
{
cout<<i<<" "<<v[i].size()<<endl;
}
else
{
cout<<i<<" "<<v[i].size()*2<<endl;
}
flag=1;
}
}
if(!flag)
{
cout<<"SAD";
return 0;
}
return 0;
}
L2-030 冰岛人 (25 分)
坑点：m,f结尾的人，并没有父亲没有母亲，是石头缝里蹦出来的；技巧是，对于一个字符串名字，我们用map来映射到它对应的结构体，从而可以根据姓名找到祖先
坑点：“五代以内无公共祖先”，如果有公共祖先，必须全部大于等于五代，否则只要有一代在五代之内，就不满足
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
typedef long long int ll;
struct node
{
string id;
string father;
char sex;
};
map<string,node>m;
int n,flag;
void check(string a,string b)
{
int cnt1=1,cnt2=1;
for(string i=a;!i.empty();i=m[i].father,cnt1++)
{
cnt2=1;
// cout<<i<<" ";
for(string j=b;!j.empty();j=m[j].father,cnt2++)
{
// cout<<j<<endl;
if(cnt1>=5&&cnt2>=5)
break;
if(i==j&&(cnt1<5||cnt2<5))
{
flag=1;
return ;
}
}
}
}
int main ()
{
cin>>n;
for(int i=1;i<=n;i++)
{
string a,b;
cin>>a>>b;
int len2=b.length();
if(b[len2-1]=='m'||b[len2-1]=='f')
{
// m[a].father=b.substr(0,len2-1);
m[a].sex=b[len2-1];
m[a].id=a;
}
else
{
if(b[len2-1]=='r')
{
m[a].father=b.substr(0,len2-7);
m[a].sex='f';
}
else
{
m[a].father=b.substr(0,len2-4);
m[a].sex='m';
}
m[a].id=a;
}
//cout<<a<<" "<<m[a].father<<endl;
}
int t;
cin>>t;
while(t--)
{
string a,b,c,d;
cin>>a>>b>>c>>d;
if(m.find(a)==m.end()||m.find(c)==m.end())
{
cout<<"NA"<<'\n';
continue;
}
else if(m[a].sex==m[c].sex)
{
cout<<"Whatever"<<'\n';
continue;
}
flag=0;
check(a,c);
if(flag)
cout<<"No"<<'\n';
else
cout<<"Yes"<<'\n';
}
return 0;
}
L2-031 深入虎穴 (25 分)
坑点，入口不是0,图遍历求最大深度就行
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
typedef long long int ll;
typedef struct
{
int b,e;
}xinxi;
xinxi s[1000000];
int len;
int f[1000000];
int nex[1000000];
void add(int x,int y)
{
s[len].b=x;
s[len].e=y;
nex[len]=f[x];
f[x]=len;
len++;
}
int ans=0,id;
void dfs(int now,int dep)
{
if(ans<=dep)
{
ans=dep;
id=now;
}
int x=f[now];
while(x!=-1)
{
int j=s[x].e;
dfs(j,dep+1);
x=nex[x];
}
}
int book[100000+10];
int main ()
{
memset(f,-1,sizeof(f));
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int k;
cin>>k;
for(int j=1;j<=k;j++)
{
int y;
cin>>y;
book[y]=1;
add(i,y);
}
}
int root;
for(int i=1;i<=n;i++)
{
if(book[i]==0)
{
root=i;
}
}
dfs(root,0);
cout<<id;
return 0;
}
L2-032 彩虹瓶 (25 分)
栈的应用，注意，当货架顶部满足条件时，我们取货架顶部之后，不要着急把当前不能发货的压入栈，交给下一次循环，可能存在取完栈顶又满足的情况
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
# include<stack>
typedef long long int ll;
stack<int>s;
int a[10000];
int main ()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=k;i++)
{
while(s.size())
{
s.pop();
}
for(int j=1;j<=n;j++)
{
cin>>a[j];
}
int flag=0;
int now=1;
int pos=1;
while(pos<=n)
{
if(now==a[pos])
{
now++;
pos++;
}
else if(!s.empty()&&s.top()==now)
{
s.pop();
now++;
}
else
{
s.push(a[pos]);
pos++;
if(s.size()>m)
{
flag=1;
break;
}
}
}
if(flag)
{
cout<<"NO"<<endl;
}
else
{
if(s.size()<=1)
{
cout<<"YES"<<endl;
}
else
{
int pre=s.top();
s.pop();
flag=0;
while(!s.empty())
{
if(s.top()==pre+1)
{
pre=s.top();
s.pop();
}
else
{
flag=1;
break;
}
}
if(flag)
{
cout<<"NO"<<endl;
}
else
{
cout<<"YES"<<endl;
}
}
}
}
return 0;
}
L2-033 简单计算器 (25 分)
栈的应用，注意0的处理，当数字栈还剩一个元素时，即使输出答案
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
# include<stack>
typedef long long int ll;
stack<int>s;
stack<char>t;
int a[10000];
int main ()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
s.push(x);
}
for(int i=1;i<n;i++)
{
char ch;
cin>>ch;
t.push(ch);
}
while(1)
{
if(s.size()==1)
{
cout<<s.top();
return 0;
}
int n1,n2;
if(!s.empty())
n1=s.top();
s.pop();
if(!s.empty())
n2=s.top();
s.pop();
char ch;
if(!t.empty())
{
ch=t.top();
t.pop();
if(ch=='+')
{
int n3=n1+n2;
s.push(n3);
}
else if(ch=='-')
{
int n3=n2-n1;
s.push(n3);
}
else if(ch=='*')
{
int n3=n1*n2;
s.push(n3);
}
else
{
if(n1==0)
{
cout<<"ERROR: ";
cout<<n2<<'/'<<n1;
return 0;
}
else
{
int n3=n2/n1;
s.push(n3);
}
}
}
if(s.size()==1)
{
cout<<s.top();
return 0;
}
}
return 0;
}
L2-034 口罩发放 (25 分)
细节巨多，坑点如下，一天一人会购买多次，一天存在一个人也不买的情况，身份证号码不全是数字！ 不建议参考代码，混乱无比。对于购买时间问题，采用map标记，一旦购买成功，刷新购买时间
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
# include<stack>
typedef long long int ll;
map<string,int>pre;
typedef struct
{
string id;
string name;
int cnt;
bool check;
int t;
} ren;
ren s[100000];
bool cmp(ren a,ren b)
{
if(a.t!=b.t)
return a.t<b.t;
return a.cnt<b.cnt;
}
ren ans[100000];
int lenans=1;
map<string,int>book1;
map<string,int>book2;
bool pan(string s)
{
for(int i=0;i<s.length();i++)
{
if(!isdigit(s[i]))
return 1;
}
return 0;
}
int main ()
{
int d,p;
cin>>d>>p;
for(int i=1; i<=d; i++)
{
int n,m;
cin>>n>>m;
int len=1;
book2.clear();
for(int j=1; j<=n; j++)
{
string id,name;
bool check;
cin>>name>>id>>check;
int h,m;
char ch;
cin>>h>>ch>>m;
if(id.length()!=18)
continue;
if(pan(id))
continue;
if(check)
{
ans[lenans].name=name;
ans[lenans].id=id;
ans[lenans].check=check;
ans[lenans].t=h*60+m;
ans[lenans].cnt=j;
lenans++;
}
if(pre[id]+p+1>i&&pre[id]!=0)
continue;
s[len].name=name;
s[len].id=id;
s[len].check=check;
s[len].t=h*60+m;
s[len].cnt=j;
len++;
}
sort(s+1,s+len,cmp);
int cnt=0;
for(int j=1; j<len; j++)
{
if(cnt== m)
break;
if(!book2[s[j].id])
{
cout<<s[j].name<<" "<<s[j].id<<endl;
pre[s[j].id]=i;
book2[s[j].id]=1;
cnt++;
}
if(cnt==m)
break;
}
}
for(int i=1; i<lenans; i++)
{
if(book1[ans[i].id]==0)
{
book1[ans[i].id]=1;
cout<<ans[i].name<<" "<<ans[i].id<<endl;
}
}
return 0;
}L2-035 完全二叉树的层序遍历 (25 分)
把建树过程融入输入
根据n，我们先处理出来完全二叉树每个编号的左右儿子，从一节点开始，模拟后序遍历即可
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
# include<stack>
typedef long long int ll;
int n;
int a[50];
struct node
{
int l,r,id;
}s[10000];
void dfs(int now)
{
if(s[now].l)
dfs(s[now].l);
if(s[now].r)
dfs(s[now].r);
cin>>s[now].id;
}
queue<node>q;
vector<int>ans;
int main ()
{
cin>>n;
for(int i=1;i<=n;i++)
{
if(i*2<=n)
s[i].l=i*2;
if(i*2+1<=n)
s[i].r=i*2+1;
}
dfs(1);
q.push(s[1]);
while(!q.empty())
{
struct node now=q.front();
q.pop();
ans.push_back(now.id);
if(now.l)
q.push(s[now.l]);
if(now.r)
q.push(s[now.r]);
}
for(int i=0;i<ans.size();i++)
{
if(i!=ans.size()-1)
cout<<ans[i]<<" ";
else
cout<<ans[i];
}
return 0;
}L2-036 网红点打卡攻略 (25 分)
邻接矩阵，注意，网红店必须是n个都包含才行。只要满足这个条件，就应该计入答案数
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
# include<stack>
typedef long long int ll;
ll dis[210][210];
int min1=0;
set<int>s;
int temp[500];
int coun[500];
int main ()
{
int n,m;
cin>>n>>m;
fill(dis[0],dis[0]+210*210,-1);
for(int i=1;i<=m;i++)
{
int x,y;
ll z;
cin>>x>>y>>z;
dis[x][y]=z;
dis[y][x]=z;
}
int t;
cin>>t;
min1=0x3f3f3f3f3f3f;
int cnt=0,ans;
for(int j=1;j<=t;j++)
{
int k;
cin>>k;
temp[0]=0;
s.clear();
memset(coun,0,sizeof(coun));
for(int i=1;i<=k;i++)
{
cin>>temp[i];
coun[temp[i]]++;
s.insert(temp[i]);
}
int flag=0;
/* for(int i=1;i<=n;i++)
{
if(coun[i]!=1)
flag=1;
}
*/
if(s.size()==n)
flag=0;
else
flag=1;
if(flag)
continue;
temp[k+1]=0;
ll tempsum=0;
for(int i=0;i<=k;i++)
{
if(dis[temp[i]][temp[i+1]]==-1)
{
flag=1;
break;
}
tempsum+=dis[temp[i]][temp[i+1]];
}
if(flag)
continue;
cnt++;
if(tempsum<min1)
{
min1=tempsum;
ans=j;
}
}
cout<<cnt<<endl;
cout<<ans<<" "<<min1;
return 0;
}
L2-037 包装机 (25 分)
栈队列，不再详述
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
# include<stack>
typedef long long int ll;
stack<char>st[200];
queue<char>d;
int main ()
{
int n,m,v;
cin>>n>>m>>v;
string s;
for(int i=1;i<=n;i++)
{
cin>>s;
for(int j=s.length()-1;j>=0;j--)
{
st[i].push(s[j]);
}
}
int x;
while(cin>>x&&x!=-1)
{
if(x&&!st[x].empty())
{
char ch=st[x].top();
st[x].pop();
if(st[0].size()==v)
{
char ch=st[0].top();
st[0].pop();
d.push(ch);
}
st[0].push(ch);
}
else if(x==0&&!st[0].empty())
{
char ch=st[0].top();
st[0].pop();
d.push(ch);
}
}
while(!d.empty())
{
cout<<d.front();
d.pop();
}
return 0;
}
L2-038 病毒溯源 (25 分)
vector的天然可比较性（按照字典序可以直接比较】可以加入元素，Dfs之后，立刻删除该位置也是可以的，使得代码量大大减少
void dfs(int now)
{
if(ans.size()<temp.size())
{
ans=temp;
}
else if(ans.size()==temp.size())
{
ans=min(ans,temp);
}
int x=f[now];
while(x!=-1)
{
int j=s[x].e;
temp.push_back(j);
dfs(j);
temp.pop_back();
x=nex[x];
}
}# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
# include<stack>
typedef long long int ll;
typedef struct
{
int b,e;
}xinxi;
xinxi s[100000];
int len;
int f[100000];
int nex[100000];
void add(int x,int y)
{
s[len].b=x;
s[len].e=y;
nex[len]=f[x];
f[x]=len;
len++;
}
bool book[100000];
vector<int>ans,temp;
void dfs(int now)
{
if(ans.size()<temp.size())
{
ans=temp;
}
else if(ans.size()==temp.size())
{
ans=min(ans,temp);
}
int x=f[now];
while(x!=-1)
{
int j=s[x].e;
temp.push_back(j);
dfs(j);
temp.pop_back();
x=nex[x];
}
}
int main ()
{
int n;
cin>>n;
memset(f,-1,sizeof(f));
for(int i=0;i<n;i++)
{
int k;
cin>>k;
while(k--)
{
int x;
cin>>x;
book[x]=1;
add(i,x);
}
}
int root;
for(int i=0;i<n;i++)
{
if(!book[i])
{
root=i;
break;
}
}
temp.push_back(root);
dfs(root);
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++)
{
if(i!=ans.size()-1)
{
cout<<ans[i]<<" ";
}
else
cout<<ans[i];
}
return 0;
}L2-039 清点代码库 (25 分)
map无法用sort排序，但因为map本质是pair，我们可以把map转存到vector,重写vector的排序规则，利用vector天然可比较性，把vector当成键值
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
# include<stack>
typedef long long int ll;
vector<int>v;
map<vector<int>,int>mm;
int temp[1000];
bool cmp(pair<vector<int>,int>& a, pair<vector<int>,int>& b)
{
if(a.second!=b.second)
{
return a.second>b.second;
}
return a.first<b.first;
}
int main()
{
int n;
cin>>n;
int m;
cin>>m;
for(int i=1;i<=n;i++)
{
v.clear();
for(int j=1;j<=m;j++)
{
cin>>temp[j];
v.push_back(temp[j]);
}
mm[v]++;
}
vector<pair<vector<int>,int>>vv(mm.begin(),mm.end());
sort(vv.begin(),vv.end(),cmp);
cout<<vv.size()<<endl;
for(auto it:vv)
{
cout<<it.second<<" ";
for(int i=0;i<it.first.size();i++)
{
if(i!=it.first.size()-1)
cout<<it.first[i]<<" ";
else
cout<<it.first[i];
}
cout<<endl;
}
return 0;
}L2-040 哲哲打游戏 (25 分)
纯模拟，注意读取存档后，当前节点也会发生变化
# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<iomanip>
using namespace std;
# define maxn 1000000*2
# include<vector>
# include<set>
# include<map>
# include<stack>
typedef long long int ll;
vector<int>v[100000+10];
int dang[1010];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int k;
cin>>k;
while(k--)
{
int x;
cin>>x;
v[i].push_back(x);
}
}
int now=1;
while(m--)
{
int x;
cin>>x;
if(x==1)
{
int y;
cin>>y;
cout<<now<<endl;
dang[y]=now;
}
else if(x==0)
{
int y;
cin>>y;
now=v[now][y-1];
}
else
{
int y;
cin>>y;
now=dang[y];
}
}
cout<<now;
return 0;
}
版权声明：本文为jisuanji2606414原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。