PAT甲级题解1121-1155
1121
样例
输入:
3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333输出:
5
10000 23333 44444 55555 88888思路和坑点
思路：
建立伴侣关系表，然后对每一个出席的人进行统计和标记，然后根据要求记录并输出单身人士即可。这里需要注意，根据样例可以直到，如果是有伴侣但是伴侣未到场的情况下也属于单身人士，也要参与统计。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main() {
int n,m,a,b;
scanf("%d",&n);
vector<int> couple(100000,-1); //记录伴侣编号
for(int i=0;i<n;i++){ //读入并标记伴侣编号
scanf("%d %d",&a,&b);
couple[a]=b;
couple[b]=a;
}
scanf("%d",&m);
vector<int> guest(m),at(100000,0); //出场的宾客和在场标记
for(int i=0;i<m;i++){
scanf("%d",&guest[i]);
at[guest[i]]=1;
}
set<int> ans;
for(int i=0;i<m;i++){ //如果存在伴侣且伴侣在场的不算单身人士，否则计入答案集合
int tmp=guest[i];
if(couple[tmp]!=-1&&at[couple[tmp]]) continue;
else ans.insert(tmp);
}
printf("%d\n",ans.size()); //按照要求输出结果
for(auto it=ans.begin();it!=ans.end();it++){
if(it!=ans.begin()) putchar(' ');
printf("%05d",*it);
}
return 0;
}1122
样例
输入:
6 10
6 2
3 4
1 5
2 5
3 1
4 1
1 6
6 3
1 2
4 5
6
7 5 1 4 3 6 2 5
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 3 4 5 2 6
7 6 1 2 5 4 3 1输出:
YES
NO
NO
NO
YES
NO思路和坑点
思路：
判断是否存在哈密顿回路，即一条包含了所有结点的回路。由此可以确定一下的情况下不是哈密顿图，如果包含的节点数不等于n+1（因为回路头尾都是同一个结点，因此总共为n+1个），则不是哈密顿图；如果给定的路径不相连也不是哈密顿回路；由于题目中保证结点不重复，所以需要判定是否每个结点都出现并且都出现一次，如果不满足也不是哈密顿图。
按照上述逻辑进行判定即可，其中判定结点出现并且都只出现一次，可以直接使用map去重，如果总共节点数为n+1，但是map去重后的节点数不为n，说明没有包含所有结点。
AC代码
#include<bits/stdc++.h>
using namespace std;
int G[205][205]={0}; //存放图的数据
int n,m,k;
void judge();
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){ //读入数据，用邻接矩阵记录图
int a,b;
scanf("%d%d",&a,&b);
G[a][b]=G[b][a]=1;
}
scanf("%d",&k);
for(int i=0;i<k;i++) //判断k组需要查验的路径
judge();
return 0;
}
void judge() //判断一组序列能不能够成一组哈密顿回路
{
int num,temp,pre,first; //pre记录前一个位置的结点值,first记录第一个位置的值
bool flag=true;
scanf("%d",&num);
if(num!=n+1){ //如果元素个数不等于节点数+1，一定构不成哈密顿回路
flag=false;
for(int i=0;i<num;i++) //过滤本组数据
scanf("%d",&temp);
}
else{
unordered_map<int,bool> mp; //结点去重
scanf("%d",&pre);
first=pre;
mp[first]=true; //读入、保存并标记第一个结点
for(int i=1;i<num;i++){ //后序读入结点，判断和前一个结点是否有路径，如果存在断链，则不是哈密顿回路
scanf("%d",&temp);
if(G[pre][temp]==0) flag=false;
pre=temp;
mp[temp]=true;
}
if(pre!=first||mp.size()!=n)//如果首尾不同或者不包含所有结点，则不是哈密顿回路
flag=false;
}
puts(flag?"YES":"NO");
}1123
样例
样例1
输入:
5
88 70 61 63 65输出:
70 63 88 61 65
YES样例2
输入:
8
88 70 61 96 120 90 65 68输出:
88 65 96 61 70 90 120 68
NO思路和坑点
思路：
先根据AVL树的规则进行建树，建树后进行判定。AVL树的相关操作可以参考算法笔记中的介绍，这里不做详细讲解，或者去看二叉树总结那篇文章中的讲解；完全二叉树的判定使用层序遍历的方法，所以层序序列的遍历输出也可以同时进行。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
int data,high;
struct node *lchild,*rchild;
}Node,*Tree;
//结点相关的函数
Node * newnode (int x); //新建结点
int gethigh(Node *root); //获取树的高度
int getbf(Node *root); //获取平衡因子
void updatahigh(Node *root); //更新树的高度
//旋转调整和插入
void L(Node *&root); //左旋
void R(Node *&root); //右旋
void Insert(Node *&root,int x); //插入函数
void Judge(Node *root); //判断函数，判断树是不是完全二叉树
void layorder(Tree root); //层序遍历
int main(){
int n;
scanf("%d",&n);
Tree root=NULL; //一定要初始化，不然野指针有可能导致段错误
for(int i=0;i<n;i++){ //进行插入建AVL树
int temp;
scanf("%d",&temp);
Insert(root,temp);
}
Judge(root); //判定函数
return 0;
}
Node * newnode (int x)
{
Node * root=new node;
root->data=x;
root->high=1;
root->lchild=root->rchild=NULL;
return root;
}
int gethigh(Node *root){
if(root==NULL) return 0;
else return root->high;
}
int getbf(Node *root){
return gethigh(root->lchild)-gethigh(root->rchild);
}
void updatahigh(Node *root){
root->high=max(gethigh(root->lchild),gethigh(root->rchild))+1;
}
void L(Node *&root){
Node *temp=root->rchild;
root->rchild=temp->lchild;
temp->lchild=root;
updatahigh(root);
updatahigh(temp);
root=temp;
}
void R(Node *&root){
Node *temp=root->lchild;
root->lchild=temp->rchild;
temp->rchild=root;
updatahigh(root);
updatahigh(temp);
root=temp;
}
void Insert(Node *&root,int x){
if(root==NULL){
root=newnode(x);
return ;
}
if(x<root->data){
Insert(root->lchild,x);
updatahigh(root);
if(getbf(root)==2){
if(getbf(root->lchild)==1){
R(root);
}
else if(getbf(root->lchild)==-1){
L(root->lchild);
R(root);
}
}
}
else{
Insert(root->rchild,x);
updatahigh(root);
if(getbf(root)==-2){
if(getbf(root->rchild)==-1){
L(root);
}
else if(getbf(root->rchild)==1){
R(root->rchild);
L(root);
}
}
}
}
void Judge(Node *root){ //判断和层序遍历一起进行，因为完全二叉树的判定本来就通过层序进行的
int cnt=0;
bool flag=true; //输出格式计数器，falg为判定标记
queue<Node *> q;
q.push(root);
while(!q.empty()){
Node* now=q.front();
q.pop();
if(now!=NULL){ //如果结点不空，输出并入队
if(cnt++) putchar(' ');
printf("%d",now->data);
q.push(now->lchild);
q.push(now->rchild);
}
else{
while(!q.empty()){ //如果遇到一个空结点，则如果后序还有非空结点则不是完全二叉树
now=q.front();
q.pop();
if(now!=NULL){ //如果后序有非空结点则输出，并修改标记，将其孩子入队
flag=false;
if(cnt++) putchar(' ');
printf("%d",now->data);
q.push(now->lchild);
q.push(now->rchild);
}
}
}
}
putchar('\n');
puts(flag?"YES":"NO");
}1124
样例
样例1
输入:
9 3 2
Imgonnawin!
PickMe
PickMeMeMeee
LookHere
Imgonnawin!
TryAgainAgain
TryAgainAgain
Imgonnawin!
TryAgainAgain输出:
PickMe
Imgonnawin!
TryAgainAgain样例2
输入:
2 3 5
Imgonnawin!
PickMe输出:
Keep going...思路和坑点
思路：
直接模拟整个过程就行，每次确定下一个领奖人的编号，做好判断和领奖标记即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int M,N,S;
scanf("%d%d%d",&M,&N,&S);
string temp; //用于存放每个人的名字信息
map<string,int> mp; //标记某人是否领过奖了
bool flag=false; //用于标记是否有发过奖
for(int i=1;i<=M;i++){ //读入每一个人的名字
cin>>temp;
if(mp[temp]==1) S+=1; //如果此人已经领过奖则跳过
if(i==S&&mp[temp]==0){ //如果轮到此人且未领过奖品则领奖并修改个人标记和发奖标记
mp[temp]=1;
cout<<temp<<endl;
flag=true;
S+=N; //更新到下一个发奖人的编号
}
}
if(flag==false) cout<<"Keep going..."; //如果未发过奖则输出keep going
return 0;
}1125
样例
输入:
8
10 15 12 3 4 13 1 15输出:
14思路和坑点
思路:
有点像创建哈夫曼树的操作,每次找出两个最短的结成绳子,然后放回,再从中挑出两个最短的结成绳子.此处直接使用stl中的优先级队列实现自动排序,保证头部永远都有两个最短的,每次按照题目要求进行结绳计算即可
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d",&n);
//创建优先级队列,底层使用vector实现,greater表示数字越小,权值越大排在最前边
priority_queue<double,vector<double>,greater<double> > q;
for(int i=0;i<n;i++){ //每一个元素入队
double temp;
scanf("%lf",&temp);
q.push(temp);
}
while(q.size()>1){ //如果队列长度大于2
double a,b;
a=q.top(); q.pop(); //取出队头的两个元素,然后按照题目给的方式模拟结绳
b=q.top(); q.pop();
a/=2;
a+=b/2;
q.push(a); //获得的绳子重新放入队列
}
printf("%d",(int)q.top()); //当队列只剩一个元素时便是最后的结果,转化成int型输出即可
return 0;
}1126
样例
样例1
输入:
7 12
5 7
1 2
1 3
2 3
2 4
3 4
5 2
7 6
6 3
4 5
6 4
5 6输出:
2 4 4 4 4 4 2
Eulerian样例2
输入:
6 10
1 2
1 3
2 3
2 4
3 4
5 2
6 3
4 5
6 4
5 6输出:
2 4 4 4 3 3
Semi-Eulerian思路和坑点
思路:
首先需要明确题目所给出的概念:1.欧拉路径:经过图中所有边仅仅一次的路径称为欧拉路径;2.欧拉回路，经过图中所有边仅仅一次的回路称为欧拉回路;3.已经证明，对于连通图，如果所有的结点度数都为偶数，一定存在欧拉回路;如果只有两个结点的度为奇数，则所有的欧拉路径必然以他们其中一个为头，另一个为尾。
同时题目也说明了，拥有欧拉回路的称为欧拉图，有欧拉路径但是没有欧拉回路的称为半欧拉图。
我们只需要保证图连通，然后根据给定的结论判断图的类型即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int G[501][501]={0}; //图的邻接矩阵
int degree[501]={0}; //记录每一个结点的度
bool vis[501]={false}; //用于标记是否被访问过
void dfs(int u); //深度优先遍历函数
int DFSTrave(); //DFS的驱动函数,以遍历每一个连通分量,返回连通分量的个数
int main(){
int a,b,cnt=0;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){ //读入图并统计每个结点的度
scanf("%d%d",&a,&b);
G[a][b]=G[b][a]=1;
degree[a]++;
degree[b]++;
}
for(int i=1;i<=n;i++){
if(i!=1) putchar(' ');
printf("%d",degree[i]); //输出每一个结点的度
if(degree[i]%2==1){ //如果度时奇数则进行统计
cnt++;
if(cnt==1) a=i; //记录唯二的奇数度结点的编号
else if(cnt==2) b=i;
}
}
putchar('\n');
int num=DFSTrave(); //计算连通分量
if(num==1){ //如果图时连通图,继续判定
if(cnt==0) puts("Eulerian");//如果全部都是偶数度的结点,则一定是欧拉图
else if(cnt==2&&G[a][b]==1) puts("Semi-Eulerian");
else puts("Non-Eulerian");//如果有唯二奇数度的结点,且两个结点不连通,则存在欧拉路径但是不存在欧拉回路,是Semi-Eulerian,否则什么都不是
}
else
puts("Non-Eulerian"); //不连通一定不是欧拉图
return 0;
}
void dfs(int u) //对一个连通分量进行dfs
{
vis[u]=true;
for(int i=1;i<=n;i++){
if(vis[i]==false&&G[u][i]==1){
dfs(i);
}
}
}
int DFSTrave(){ //dfs驱动函数,返回连通分量个数
int ret=0;
for(int i=1;i<=n;i++){
if(vis[i]==false){
dfs(i);
ret++;
}
}
return ret;
}1127
样例
输入:
8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1输出:
1 11 5 8 17 12 20 15思路和坑点
思路：
先使用中序和后序序列递归建树，然后对建成的树进行层序遍历并保存层序遍历的结果，统计每一层的节点数量，然后对偶数层的节点序列进行逆转，就是最后需要的输出序列。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{ //二叉树的结点定义
int data;
struct node *left,*right;
}Node,*Tree;
int n;
int post[31]; //后序遍历序列
int in[31]; //中序遍历序列
int layercnt[31]={0}; //统计每层的元素个数
vector<int> layer; //存放层序遍历序列
Node *creat(int pl,int pr,int il,int ir);//由中序和后序建树的函数
int layorder(Tree root); //层序遍历
int main(){
scanf("%d",&n); //读入序列
for(int i=0;i<n;i++)
scanf("%d",&in[i]);
for(int i=0;i<n;i++)
scanf("%d",&post[i]);
Tree root=creat(0,n-1,0,n-1); //建树
int layern=layorder(root); //层序遍历，并返回最大的层数
int sum=1; //已经处理过的结点个数，根不需要处理，直接跳过，所以初始化为1
for(int i=1;i<=layern;i++){ //偶数层进行反转
if(i%2==0)
reverse(layer.begin()+sum,layer.begin()+sum+layercnt[i]);
sum+=layercnt[i]; //累加处理过的结点个数
}
for(int i=0;i<layer.size();i++){//输出最终的序列
if(i) putchar(' ');
printf("%d",layer[i]);
}
return 0;
}
Node *creat(int pl,int pr,int il,int ir)
{
if(pl>pr) return NULL;
Node *root=new node;
root->data=post[pr];
int k;
for(k=il;k<=ir;k++){
if(in[k]==post[pr]) break;
}
int leftnum=k-il;
root->left=creat(pl,pl+leftnum-1,il,k-1);
root->right=creat(pl+leftnum,pr-1,k+1,ir);
return root;
}
int layorder(Tree root)
{
int maxlayer=0,cnt=0; //maxlayer记录层数，cnt记录每一个层的元素个数
queue<Node*> q;
Node * last=root,*tail=root; //last记录当前层的最后一个，tial记录下一层的最后一个位置
q.push(root);
while(!q.empty()){
Node * now=q.front();
q.pop();
layer.push_back(now->data); //加入层序遍历序列
cnt++;
if(now->left) q.push(tail=now->left); //孩子入队并更新tail
if(now->right) q.push(tail=now->right);
if(now==last){ //如果当前层已经处理完毕
layercnt[maxlayer++]=cnt; //统计当前层节点数量，并重置计数器
cnt=0;
last=tail; //更新last
}
}
return maxlayer; //返回树的最大层数
}1128
样例
输入:
4
8 4 6 8 2 7 1 3 5
9 4 6 7 2 8 1 9 5 3
6 1 5 2 6 4 3
5 1 3 5 2 4输出:
YES
NO
NO
YES思路和坑点
思路：
根据题目的描述，判定是否同一行、同一列或者对角线（行列坐标差值相等），由于题目按照每列的顺序给出，所以已经满足不同列的要求，只需判断另外两个条件即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{ //表示每个棋子的坐标
int x,y;
}Node;
void Judge();
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) //依次判断n个序列
Judge();
return 0;
}
void Judge()
{
int n;
scanf("%d",&n);
vector<Node> v;
for(int i=1;i<=n;i++){
Node temp;
temp.y=i; //表示列
scanf("%d",&temp.x); //表示行
v.push_back(temp); //读入节点
}
bool flag=true;
for(int i=0;i<n;i++){ //两两进行判定
for(int j=i+1;j<n;j++){
if(v[i].x==v[j].x||v[i].x-v[j].x==v[i].y-v[j].y){
flag=false; break; //因为已知不再同一列，所以只需要判断是否再同一列或者是否对角线（横竖坐标差值相同）
} //如果同行或者同对角线，则判定为否
}
if(flag==false) //判断标记，可以提前退出双重循环
break;
}
puts(flag?"YES":"NO");
}1129
样例
输入:
12 3
3 5 7 5 5 3 2 1 8 3 8 12输出:
5: 3
7: 3 5
5: 3 5 7
5: 5 3 7
3: 5 3 7
2: 5 3 7
1: 5 3 2
8: 5 3 1
3: 5 3 1
8: 3 5 1
12: 3 5 8思路和坑点
思路：
使用有序容器存储每个商品结构体，然后根据其排序规则重载比较符号，是的容器内部的排序按照我们需要的方式进行，然后根据频率和id排序存入即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{ //定义结构体，并重载比较函数
int id;
int freq;
node(int _id,int _freq):id(_id),freq(_freq){} //构造函数初始化结构体
friend bool operator < (node a,node b){
if(a.freq!=b.freq) return a.freq>b.freq; //重载小于的比较函数，因为set默认从小到大，所以把小于重载成我们需要的比较类型
else return a.id<b.id; //如果请求频率高为第一排序参数，从大到小，否则按照id从大到小排列
}
}Node;
int cnt[50001]={0}; //记录查询频率
int main(){
int n,k,num;
scanf("%d%d",&n,&k);
set<Node> s; //使用set存放结点
for(int i=0;i<n;i++){
scanf("%d",&num);
if(i){ //从第二个读入开始输出
printf("%d:",num); //输出头部
int tempcnt=0; //用于计数
for(auto it=s.begin();tempcnt<k&&it!=s.end();it++){
printf(" %d",it->id); //依次输出最多k个数据
tempcnt++;
}
putchar('\n');
}
auto it=s.find(node(num,cnt[num])); //在set中查找是否有当前元素
if(it!=s.end()) s.erase(it); //如果有则删除，更新频率后再插入，保证其排序正确
cnt[num]++;
s.insert(node(num,cnt[num]));
}
return 0;
}1130
样例
样例1
输入:
8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
- -1 6
c -1 -1输出:
(a+b)*(c*(-d))样例2
输入:
8
2.35 -1 -1
* 6 1
- -1 4
% 7 8
+ 2 3
a -1 -1
str -1 -1
871 -1 -1输出:
(a*2.35)+(-(str%871))思路和坑点
思路：
根据数据构建二叉树，然后对二叉树使用中序遍历获取中缀表达式，注意括号的处理。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{ //二叉树结点定义，使用静态数组存储，所以指针为int
string data;
int left=-1,right=-1;
}Node;
Node T[25]; //存储树的数据
string inorder(int root); //中序遍历获取中缀表达式
int main(){
int n;
scanf("%d",&n);
if(n==1) { //特判
string temp;
cin>>temp;
cout<<temp;
return 0;
}
bool isroot[25]={0}; //标记根，如果不是根则标记为1，最后剩余的0便是根
for(int i=1;i<=n;i++){ //读入数据并修改标记
cin>>T[i].data;
scanf("%d%d",&T[i].left,&T[i].right);
if(T[i].left!=-1) isroot[T[i].left]=1;
if(T[i].right!=-1) isroot[T[i].right]=1;
}
int root; //查找根
for(int i=1;i<=n;i++){
if(isroot[i]==0){
root=i;break;
}
}
string out=inorder(root); //遍历获得结果
cout<<out.substr(1,out.size()-2); //去最外层括号
return 0;
}
string inorder(int root)
{
if(T[root].left==-1&&T[root].right==-1) return T[root].data; //单个结点返回数据即可
else{
string temp="("; //添加左括号
if(T[root].left!=-1) temp+=inorder(T[root].left); //获取左子树的表达式
temp+=T[root].data; //加上当前结点的值
if(T[root].right!=-1) temp+=inorder(T[root].right); //追加右子树的表达式
temp+=")"; //添加右括号
return temp; //返回整个表达式
}
} 1131
样例
输入:
4
7 1001 3212 1003 1204 1005 1306 7797
9 9988 2333 1204 2006 2005 2004 2003 2302 2001
13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011
4 6666 8432 4011 1306
3
3011 3013
6666 2001
2004 3001输出:
2
Take Line#3 from 3011 to 3013.
10
Take Line#4 from 6666 to 1306.
Take Line#3 from 1306 to 2302.
Take Line#2 from 2302 to 2001.
6
Take Line#2 from 2004 to 1204.
Take Line#1 from 1204 to 1306.
Take Line#3 from 1306 to 3001.思路和坑点
代码年代久远了，我记得是参考了柳神的代码，这题挺难了，看懂了自己也不一定能独立写得出来。
AC代码
#include<bits/stdc++.h>
using namespace std;
vector<int> v[10000];
bool vis[10000]={false}; //占用标记
int mincnt,minTrans,st,ed;
unordered_map<int,int> line;
vector<int> path,temppath;
int transfercnt(vector<int> &a){ //换乘统计
int cnt=-1,preline=0; //cnt计数，preline前一段的路线编号
for(int i=1;i<a.size();i++){ //遍历得到的路径
if(line[a[i-1]*10000+a[i]]!=preline) cnt++; //如果当前的线路于上一段不同，说明换乘，计数加一
preline= line[a[i-1]*10000+a[i]];
}
return cnt;
}
void dfs(int node,int cnt){ //dfs
if(node==ed){ //如果到大终点
if(cnt<mincnt){ //如果路径更短。更新
mincnt=cnt;
minTrans=transfercnt(temppath);
path=temppath;
}
else if(cnt==mincnt&&transfercnt(temppath)<minTrans){//如果长度相同，但是换乘更少，也更新
mincnt=cnt;
minTrans=transfercnt(temppath);
path=temppath;
}
return;
}
for(int i=0;i<v[node].size();i++){ //递归的dfs搜索node相邻接的顶点
int k=v[node][i];
if(vis[k]==false){
vis[k]=true; //计入路径，并修改标记
temppath.push_back(k);
dfs(k,cnt+1);
vis[k]=false; //解除占用
temppath.pop_back(); //回上一层
}
}
}
int main(){
int n,m,k,pre,temp;
scanf("%d",&n);
for(int i=1;i<=n;i++){ //读入数据
scanf("%d%d",&m,&pre); //第一个结点提前读入
for(int j=1;j<m;j++){
scanf("%d",&temp);
v[pre].push_back(temp);
v[temp].push_back(pre);
line[pre*10000+temp]=line[temp*10000+pre]=i;
pre=temp;
}
}
scanf("%d",&k);
for(int i=0;i<k;i++){
scanf("%d%d",&st,&ed);
mincnt=99999,minTrans=99999; //初始化统计变量
temppath.clear(); //其实顶点放入路径
vis[st]=true; //修改标记
temppath.push_back(st);
dfs(st,0);
vis[st]=false; //解除占用，还原状态
printf("%d\n",mincnt);
int preline=0,pretrans=st;
for(int j=1;j<path.size();j++){
if(line[path[j-1]*10000+path[j]]!=preline){
if(preline!=0) printf("Take Line#%d from %04d to %04d.\n",preline,pretrans,path[j-1]);
preline=line[path[j-1]*10000+path[j]];
pretrans=path[j-1];
}
}
printf("Take Line#%d from %04d to %04d.\n",preline,pretrans,ed);
}
return 0;
}1132
样例
输入:
3
167334
2333
12345678输出:
Yes
No
No思路和坑点
思路：
讲给定的字符串分割成两部分，然后进行计算判定即可，使用stl或者一些库函数能够快速处理。
AC代码
#include<bits/stdc++.h>
using namespace std;
void Judge(){
string str; //读入字符串
cin>>str;
long long a,b,c; //使用longlong方式int型溢出
int k=str.size()/2; //取字符串一半的长度
sscanf(str.substr(0,k).c_str(),"%lld",&a); //将两部分从字符串转化为数字
sscanf(str.substr(k,k).c_str(),"%lld",&b);
sscanf(str.c_str(),"%lld",&c);
if(b!=0&&c%(a*b)==0) puts("Yes"); //计算结果是否相等，进行判定，此处因为要进行除法计算所以必须判断除数是否为0，因为数字没有前置0，所以不用判断a
else puts("No");
}
int main(){
int n;
scanf("%d",&n); //依次读入数据，并进行判断
for(int i=0;i<n;i++)
Judge();
return 0;
}1133
样例
输入:
00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218输出:
33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1思路和坑点
思路：
使用数组来处理链表的题目一般思路都比较简单，这里要对链表根据结点值x的大小依次按照x小于零、x大于等于0且小于等于k、x大于k的顺序排序好，所以直接遍历三次，每次将一类数据放入数组中，最后输出整个数组。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct{
int id,data,next;
}NODE;
NODE in[100000]; //输入的链表
NODE out[100000]; //输出的数组
int main(void)
{
int head,n,k;
scanf("%d %d %d",&head,&n,&k);
for(int i=0;i<n;i++){ //读入数据，给每一个结点赋值，包含了自己的id
int temp;
scanf("%d",&temp);
in[temp].id=temp;
scanf("%d %d",&in[temp].data,&in[temp].next);
}
int cnt=0;
for(int i=head;i!=-1;i=in[i].next) //遍历三次链表，依次将<0、0<x<k、x>k的结点存放在数组中
if(in[i].data<0) out[cnt++]=in[i];
for(int i=head;i!=-1;i=in[i].next)
if(in[i].data>=0&&in[i].data<=k) out[cnt++]=in[i];
for(int i=head;i!=-1;i=in[i].next)
if(in[i].data>k) out[cnt++]=in[i];
int i;
for(i=0;i<cnt-1;i++) //从数组中输出链表
printf("%05d %d %05d\n",out[i].id,out[i].data,out[i+1].id);
printf("%05d %d -1",out[i].id,out[i].data); //最后一个单独处理
return 0;
}1134
样例
输入:
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
5
4 0 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2输出:
No
Yes
Yes
No
No思路和坑点
思路：
vertex cover的概念：图结点的某一个集合，图中每一条边至少涉及集合中一个点。
所以，将点集中点涉及到的所有边都进行标记，然后如果图的边未被全部标记，则不是vertex cover，否则是。
AC代码
#include<bits/stdc++.h>
#define MAXN 10004
using namespace std;
vector<int> v[MAXN]; //二维数组，每一个一维数组存放每一个顶点链接的边的编号
int n,m; //顶点数n和边数m
bool vis[MAXN]={false}; //边的访问标记
void Judge();
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){ //读入数据
int a,b;
scanf("%d%d",&a,&b);
v[a].push_back(i);
v[b].push_back(i);
}
int k;
scanf("%d",&k);
for(int i=0;i<k;i++) //依次判断每一组数据
Judge();
return 0;
}
void Judge()
{
int num,temp;
fill(vis,vis+m,false); //初始化vis数组
bool flag=true;
scanf("%d",&num);
for(int i=0;i<num;i++){ //依次读入num个顶点
scanf("%d",&temp);
for(int j=0;j<v[temp].size();j++){
vis[v[temp][j]]=true; //将每一个点所联系的边进行标记
}
}
for(int i=0;i<m;i++){ //遍历标记数组
if(vis[i]==false){
flag=false; break; //如果某条边未被访问过，则不构成vertex vocer
}
}
puts(flag?"Yes":"No"); //输出判定结果
}1135
样例
输入:
3
9
7 -2 1 5 -4 -11 8 14 -15
9
11 -2 1 -7 5 -4 8 14 -15
8
10 -7 5 -6 8 15 -11 17输出:
Yes
No
No思路和坑点
柳神赛高！我只能看懂并理解柳神的代码，自己暂时还写不出来，具体可以看看注释。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
int data;
struct node *left,*right;
}Node,*Tree;
void Insert(Node *&root,int x){ //插入建树
if(root==NULL){
root=new Node;
root->data=x;
root->right=root->left=NULL;
}
else if(abs(x)<=abs(root->data)) //插入左子树
Insert(root->left,x);
else Insert(root->right,x); //插入右子树
}
bool JudgeRB(Tree root ){ //判断是否符合红黑结点要求
if(root==NULL) return true;
if(root->data<0){ //如果是红结点，判断孩子
if(root->left&&root->left->data<0) return false;
if(root->right&&root->right->data<0) return false;
}
return JudgeRB(root->left)&&JudgeRB(root->right); //判断左右子树是否都符合红黑标准
}
int getBnum(Tree root){
if(root==NULL) return 0;
int l=getBnum(root->left);
int r=getBnum(root->right);
if(root->data>0)
return max(l,r)+1; //如果当前结点是黑色，返回左右子树最大值+1
else
return max(l,r); //如果是红色，返回左右子树的最大值
}
bool JudgeBnum(Tree root){ //判断左右子树一直到叶子结点路径上黑色结点的个数是否相同
if(root==NULL) return true;
int l=getBnum(root->left);
int r=getBnum(root->right);
if(l!=r) return false;
return JudgeBnum(root->left)&&JudgeBnum(root->right);
}
int main(){
int k,n;
scanf("%d",&k);
for(int i=0;i<k;i++){
scanf("%d",&n);
vector<int> a(n);
Tree root=NULL;
for(int j=0;j<n;j++){
scanf("%d",&a[j]);
Insert(root,a[j]);
}
if(a[0]<0||JudgeBnum(root)==false||JudgeRB(root)==false)
puts("No");
else
puts("Yes");
}
return 0;
}1136
样例
样例1
输入:
97152输出:
97152 + 25179 = 122331
122331 + 133221 = 255552
255552 is a palindromic number.样例2
输入:
196输出:
196 + 691 = 887
887 + 788 = 1675
1675 + 5761 = 7436
7436 + 6347 = 13783
13783 + 38731 = 52514
52514 + 41525 = 94039
94039 + 93049 = 187088
187088 + 880781 = 1067869
1067869 + 9687601 = 10755470
10755470 + 07455701 = 18211171
Not found in 10 iterations.思路和坑点
思路：
第一个是需要判定是不是回文数，判断字符串对称即可，另一个是要做字符串的相加处理，都属于常规操作。
坑点：
要注意对输入的数字进行判定，如果一开始就是回文数，则直接输出。
AC代码
#include<bits/stdc++.h>
using namespace std;
bool ishw(string &s); //判定是不是回文数
void add(string &s); //两个数字相加
int main(){
string s;
cin>>s;
if(s.size()==1||ishw(s)) { //如果只有一个字符，或者本身已经是回文数，直接输出
cout<<s<<" is a palindromic number.";
}
else{
int cnt=10;
while(cnt--){ //在规定次数内进行判定
add(s); //做一次相加处理
if(ishw(s)){
cout<<s<<" is a palindromic number.";
return 0;
}
}
puts("Not found in 10 iterations."); //如果在有限次数内没有产生回文数，则按照要求输出对应信息
}
return 0;
}
bool ishw(string &s) //判断回文
{
int i=0,j=s.size()-1;
while(i<j){
if(s[i]!=s[j])
return false;
i++,j--;
}
return true;
}
void add(string &s) //字符串相加
{
string temp=s;
reverse(temp.begin(),temp.end()); //逆转字符串
cout<<s<<" + "<<temp<<" = "; //输出相加的两个字符串
int flag=0; //进位
for(int i=0;i<s.size();i++){
int num=s[i]-'0'+temp[i]-'0'+flag;
s[i]='0'+num%10;
flag=num/10;
}
if(flag) s.push_back('0'+flag); //如果最高位仍然有进位
reverse(s.begin(),s.end()); //将最后形成的字符串按照正确的顺序返回
cout<<s<<'\n';
}1137
样例
输入:
6 6 7
01234 880
a1903 199
ydjh2 200
wehu8 300
dx86w 220
missing 400
ydhfu77 99
wehu8 55
ydjh2 98
dx86w 88
a1903 86
01234 39
ydhfu77 88
a1903 66
01234 58
wehu8 84
ydjh2 82
missing 99
dx86w 81输出:
missing 400 -1 99 99
ydjh2 200 98 82 88
dx86w 220 88 81 84
wehu8 300 55 84 84思路和坑点
思路:
按照题目的要求，对学生进行过滤，筛选掉一定不合格的，然后计算总评成绩，并按照要求排序并输出结果。过滤数据有助于提高程序运行速度。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct{
string id; //学生名字
int pscore,gmid,gfin,g; //pscore为编程成绩，gmid表示期中成绩，gfin表示期末称其，g表示最终成绩
bool is; //合格标记
}ST;
ST s[10000];
bool cmp(ST a,ST b){
if(a.g!=b.g) return a.g>b.g; //按照总成绩从高到底
else return a.id<b.id; //成绩相同时候按照名字字典序排序
}
int main(void)
{
int p,m,n,score;
string name;
map<string,int> mp; //每个人在数组中的下标
scanf("%d %d %d",&p,&m,&n);
for(int i=1;i<=p;i++){ //读入编程成绩并初始化其他成员变量
cin>>name>>score;
if(score<200) continue; //编程成绩低于200分的一定不合格，直接过滤掉
mp[name]=i;
s[i].id=name;
s[i].pscore=score; //记录名字和编程成绩
s[i].gmid=-1; //期中成绩初始化为-1
s[i].is=false; //默认标记为不合格
}
for(int i=0;i<m;i++){
cin>>name>>score; //读入其中成绩
if(mp[name]!=0) //如果编程成绩合格，记录期中成绩
s[mp[name]].gmid=score;
}
for(int i=0;i<n;i++){
cin>>name>>score;
if(mp[name]==0) continue; //如果不在统计范围内，则跳过步处理，过滤一定不合格的学生
int mid=s[mp[name]].gmid; //获取期中成绩
s[mp[name]].gfin=score; //记录期末成绩
if(mid<=score) //如果期中成绩小于期末成绩，总成绩为期末成绩
s[mp[name]].g=score;
else //否则按照要求进行计算
s[mp[name]].g=(0.5+0.4*mid+0.6*score);
if(s[mp[name]].g>=60) //如果总成绩也达标
s[mp[name]].is=true; //标记为合格
}
sort(s+1,s+p+1,cmp); //排序并输出合格学生的信息
for(int i=1;i<=p;i++){
if(s[i].is)
cout<<s[i].id<<' '<<s[i].pscore<<' '<<s[i].gmid<<' '<<s[i].gfin<<' '<<s[i].g<<'\n';
}
return 0;
}1138
样例
输入:
7
1 2 3 4 5 6 7
2 3 1 5 4 7 6输出:
3思路和坑点
思路:
我们可以根据一棵树的先序和中序唯一确定一棵树，所以我们使用递归的方式来构建树形，但是我们只需要找到第一个后序的结点就可以了，那么我们可以考虑，如果这棵树有左子树则，后序第一个结点一定在左子树中，如果没有左子树但是有右子树，则后序第一个结点一定在右子树中，否则这棵树没有左子树和右子树，根便是后序序列中的第一个元素。由此逻辑，我们可以得到以下递归代码，实现找到第一个后序结点。
AC代码
#include<bits/stdc++.h>
using namespace std;
bool flag=false;
int ans; //返回后序的第一个元素
vector<int> pre,in;
void postorder(int pl,int pr,int il,int ir); //先序和中序确定树形
int main(){
int n;
scanf("%d",&n);
pre.resize(n); in.resize(n); //初始化先序和中序的序列大小
for(int i=0;i<n;i++) //读入两个序列
scanf("%d",&pre[i]);
for(int i=0;i<n;i++)
scanf("%d",&in[i]);
postorder(0,n-1,0,n-1,n-1);
cout<<ans;
return 0;
}
void postorder(int pl,int pr,int il,int ir){ //递归确定树形
if(pl>pr||flag) return; //如果当前序列为空或者已经找到答案，直接返回上一层
if(pl==pr){ //如果只有一个元素，说明没有左右子树，当前值就是答案
ans=pre[pl];
flag=true;
return ;
}
int lnum=0,rnum=0,k; //找到当前子树根在中序的位置，左右则为子树
for(k=il;k<=ir;k++){
if(in[k]==pre[pl])
break;
}
lnum=k-il;rnum=ir-k; //计算左右子树个数
if(lnum) postorder(pl+1,pl+lnum,il,k-1); //如果有左子树，则后序第一个元素一定在左子树中
else if(rnum) postorder(pl+lnum+1,pr,k+1,ir); //如果没有左子树，则后序第一个元素一定在右子树中
}1139
样例
输入:
10 18
-2001 1001
-2002 -2001
1004 1001
-2004 -2001
-2003 1005
1005 -2001
1001 -2003
1002 1001
1002 -2004
-2004 1001
1003 -2002
-2003 1003
1004 -2002
-2001 -2003
1001 1003
1003 -2001
1002 -2001
-2002 -2003
5
1001 -2001
-2003 1001
1005 -2001
-2002 -2004
1111 -2003输出:
4
1002 2004
1003 2002
1003 2003
1004 2002
4
2001 1002
2001 1003
2002 1003
2002 1004
0
1
2003 2001
0思路和坑点
自己的代码有bug，考虑不周全，暂时还是放以下柳神的代码吧，柳神对于此题数据的处理方法非常有趣，值得借鉴。
AC代码
#include<bits/stdc++.h>
using namespace std;
unordered_map<int, bool> arr;
struct node {
int a, b;
};
bool cmp(node x, node y) {
return x.a != y.a ? x.a < y.a : x.b < y.b;
}
int main() {
int n, m, k;
scanf("%d%d", &n, &m);
vector<int> v[10000];
for (int i = 0; i < m; i++) {
string a, b;
cin >> a >> b;
if (a.length() == b.length()) {
v[abs(stoi(a))].push_back(abs(stoi(b)));
v[abs(stoi(b))].push_back(abs(stoi(a)));
}
arr[abs(stoi(a)) * 10000 + abs(stoi(b))] = arr[abs(stoi(b)) * 10000 + abs(stoi(a))] = true;
}
scanf("%d", &k);
for (int i = 0; i < k; i++) {
int c, d;
cin >> c >> d;
vector<node> ans;
for (int j = 0; j < v[abs(c)].size(); j++) {
for (int k = 0; k < v[abs(d)].size(); k++) {
if (v[abs(c)][j] == abs(d) || abs(c) == v[abs(d)][k]) continue;
if (arr[v[abs(c)][j] * 10000 + v[abs(d)][k]] == true)
ans.push_back(node{v[abs(c)][j], v[abs(d)][k]});
}
}
sort(ans.begin(), ans.end(), cmp);
printf("%d\n", int(ans.size()));
for(int j = 0; j < ans.size(); j++)
printf("%04d %04d\n", ans[j].a, ans[j].b);
}
return 0;
}1140
样例
输入:
1 8输出:
1123123111思路和坑点
思路:
需要理解题目的意思，后一串字符是对前一串字符的解读，例子如下：
1
11 //上一行的1有1个
12 //上一行的1有2个
1121 //上一行的1有1个，2有1个
122111 //上一行的1有两个，2有1个，1有一个
112213 //上一行的1有一个，2有两个，1有三个
以此类推所以只要会统计每一个连续的字符个数，重新组成新的字符串，然后迭代即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
void readans(string &s);
string to_str(int n);
int main(){
string s;
int n;
cin>>s>>n;
for(int i=0;i<n-1;i++)
readans(s);
cout<<s;
return 0;
}
void readans(string &s){ //通过传进来的字符串获取下一串字符串的长度
string temp="";
char pre=s[0]; //从第一个开始处理
int cnt=1; //计数器
for(int i=1;i<s.size();i++){
if(s[i]==pre) cnt++; //如果是相同字符，累加个数
else{
temp.push_back(pre); //如果和前边不同，则处理连续的数字
temp+=to_str(cnt); //加入字符和字符个数
cnt=1; //重置计数器
}
pre=s[i]; //更新pre
}
temp.push_back(pre); //处理最后一段
temp+=to_str(cnt);
s=temp; //更细s为新的一串字符
}
string to_str(int n){ //整数转为字符串
string ret="";
while(n){
ret.push_back('0'+n%10);
n/=10;
}
return ret;
}1141
样例
输入:
10
A57908 85 Au
B57908 54 LanX
A37487 60 au
T28374 67 CMU
T32486 24 hypu
A66734 92 cmu
B76378 71 AU
A47780 45 lanx
A72809 100 pku
A03274 45 hypu输出:
5
1 cmu 192 2
1 au 192 3
3 pku 100 1
4 hypu 81 2
4 lanx 81 2思路和坑点
思路：
正常的统计并排序思路，但是可以通过下标排序的方法减少时间消耗，具体操作方法和原理可以参考PAT总结文章中的笔记。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct node{
string id;
int ta,tb,tt,total;
int num;
node(){
ta=0;tb=0;tt=0;num=0;
}
}Node;
vector<Node> v; //存数据
unordered_map<string,int> mp; //下标映射
vector<int> sindex; //下标排序用，能够加速排序，空间换时间
void to_low(string &s){ //将字符串全部置为小写
for(int i=0;i<s.size();i++){
s[i]=tolower(s[i]);
}
}
bool cmp(int a,int b){ //排序的比较函数
if(v[a].total!=v[b].total) return v[a].total>v[b].total;
else if(v[a].num!=v[b].num) return v[a].num<v[b].num;
else return v[a].id<v[b].id;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){ //读入数据
string id,sch;
int score;
cin>>id>>score>>sch;
to_low(sch);
if(mp.find(sch)==mp.end()){ //如果是新的数据
mp[sch]=v.size(); //分配下标
Node temp;
temp.id=sch; //存入数据
v.push_back(temp);
}
int k=mp[sch]; //根据成绩的等级累加到对应学校的总分上
if(id[0]=='A')
v[k].ta+=score;
else if(id[0]=='B')
v[k].tb+=score;
else
v[k].tt+=score;
v[k].num++; //人数统计
}
for(int i=0;i<v.size();i++){ //初始化排序下标数组，顺带计算每个学校的加权分数
sindex.push_back(i);
v[i].total=(int) (1.0*v[i].tb/1.5+v[i].ta+v[i].tt*1.5);
}
sort(sindex.begin(),sindex.end(),cmp);//排序
int rank=1,pre; //排名
printf("%d\n",v.size());
for(int i=0;i<sindex.size();i++){
int k=sindex[i];
if(i&&v[k].total!=v[pre].total){//如果和前一个排名不同则排名+1
rank=i+1;
}
printf("%d %s %d %d\n",rank,v[k].id.c_str(),v[k].total,v[k].num);
pre=k; //更新前一个元素的位置
}
return 0;
}1142
样例
输入:
8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
3 4 3 6
3 3 2 1输出:
Yes
Yes
Yes
Yes
Not Maximal
Not a Clique思路和坑点
思路:
首先明确概念：clique指的是图的某一个顶点的子集中，任意两个顶点之间都相互邻接。maximal clique指的是clique的最大集合，不能再找到一个顶点加入maximal clique以满足clique
由此，可以得到思路，默认是clique，当发现有不邻接的定点对儿时，则不是一个clique，然后再判断是不是maxiaml，判断是否存在一个不在集合中的点，满足和当前集合中所有顶点都邻接，如果能找到则不是maximal
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 205
int G[MAXN][MAXN]={0};
int n,m;
void Judge();
int main(){
int a,b,k;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
G[a][b]=G[b][a]=1;
}
scanf("%d",&k);
for(int i=0;i<k;i++)
Judge();
return 0;
}
void Judge()
{
int flag=0; //0表示yes，1表示not max，2表示not clique
vector<bool> vis(n);
fill(vis.begin(),vis.end(),false);//所有的顶点的访问标记
int num;
scanf("%d",&num);
vector<int> vn(num); //读入一组结点
for(int i=0;i<num;i++){
scanf("%d",&vn[i]);
vis[vn[i]]=true;
}
for(int i=0;i<num;i++){ //如果出现两个顶点之间不连通便是2
for(int j=i+1;j<num;j++){
if(G[vn[i]][vn[j]]==0){
flag=2;
break;
}
}
if(flag==2) break;
}
if(flag==0){ //如果不是2，则继续判别
for(int i=1;i<=n;i++){
int cnt=0; //计数器
if(vis[i]==false){ //检测不在当前集合中的的顶点
for(int j=0;j<vn.size();j++)
if(G[i][vn[j]]==1) cnt++; //统计结点i和当前集合中的链接个数
if(cnt==vn.size()){ //如果结点i能够和当前集合中所有结点想邻接，则说明当前集合可以扩充，不是max，标记为1
flag=1; break;
}
}
}
}
switch(flag){ //根据标记输出类型
case 0:puts("Yes");break;
case 1:puts("Not Maximal");break;
case 2:puts("Not a Clique");break;
default: break;
}
}1143
样例
输入:
6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99输出:
LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.思路和坑点
思路:
题目给出的是二叉搜索树的先序遍历，可以根据二叉搜索树的特性来查找，具体原理参见代码注释，要留意题目给出的数据结构的特性，并加以利用。
AC代码
#include<bits/stdc++.h>
using namespace std;
unordered_map<int, bool> mp; //标记是否出现过
int main() {
int m, n, u, v, a;
scanf("%d %d", &m, &n);
vector<int> pre(n);
for (int i = 0; i < n; i++) { //读取先序序列，先序序列的顺序为根、左、右，且左子树小于根，右子树大于根
scanf("%d", &pre[i]);
mp[pre[i]] = true;
}
for (int i = 0; i < m; i++) {
scanf("%d %d", &u, &v); //读取两个结点
for(int j = 0; j < n; j++) {
a = pre[j]; //判断每一个结点和uv的关系
if ((a >= u && a <= v) || (a >= v && a <= u)) break;//根据先序的顺序规律，当U和V出现在a的左右两侧或者某个在a的位置上时，a是公共祖先
}
if (mp[u] == false && mp[v] == false) //根据是否存在的情况分类输出结果
printf("ERROR: %d and %d are not found.\n", u, v);
else if (mp[u] == false || mp[v] == false)
printf("ERROR: %d is not found.\n", mp[u] == false ? u : v);
else if (a == u || a == v)
printf("%d is an ancestor of %d.\n", a, a == u ? v : u);
else
printf("LCA of %d and %d is %d.\n", u, v, a);
}
return 0;
}1144
样例
输入:
10
5 -25 9 6 1 3 4 2 5 17输出:
7思路和坑点
思路:
把出现的数字都进行标记，然后根据标记数组找到题目要求的那个正整数。
AC代码
#include<bits/stdc++.h>
using namespace std;
bool a[100005]={false}; //标记是否出现过
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){ //读取每一个数字，然后把出现过的数字进行标记
int temp;
scanf("%d",&temp);
if(temp<=100000&&temp>0)
a[temp]=true;
}
n=1;
while(1){
if(a[n]==false){ //遍历标记数组，找到那个符合要求的数字
printf("%d",n);
break;
}
n++;
}
return 0;
}1145
样例
输入:
4 5 4
10 6 4 15 11
11 4 15 2输出:
15 cannot be inserted.
2.8思路和坑点
思路:
首先，要进行哈希表的构建，哈希的长度为不小于tsize的一个素数。构建哈希表的时候，使用正的平方探测法解决冲突问题。
然后，根据构建好的哈希表进行查找，查找结束的标志为，查找到或者查找到空位、或者回到原位。
AC代码
#include<bits/stdc++.h>
using namespace std;
bool isprime(int n){ //判断是不是素数
for(int i=2;i*i<=n;i++)
if(n%i==0) return false;
return true;
}
int main(){
int tsize,n,m,a;
scanf("%d%d%d",&tsize,&n,&m);
while(!isprime(tsize)) tsize++; //找到不小于tsize的素数作为哈希表的长度
vector<int> v(tsize,0); //全部初始化为0 ，表示为空位（因为插入的数字都是正数），哈希表
for(int i=0;i<n;i++){
scanf("%d",&a); //读入一个数字
int flag=0; //标记是否放入，1为放入，0为未放入
for(int j=0;j<tsize;j++){ //j为0时表示第一次散列，之后表示二次探测
int pos=(a+j*j)%tsize;
if(v[pos]==0){ //如果找到空位，则插入a并修改标记
v[pos]=a;
flag=1;
break;
}
}
if(flag==0) printf("%d cannot be inserted.\n",a); //输出不能插入的数字
}
int ans=0;
for(int i=0;i<m;i++){
scanf("%d",&a);
for(int j=0;j<=tsize;j++){
ans++; //比较次数加一
int pos=(a+j*j)%tsize;
if(v[pos]==a||v[pos]==0) break;//找到或到达空位，或者j增量取到tsize时回到第一次散列的位置时，结束查找
}
}
printf("%.1lf\n",ans*1.0/m); //输出平均查找次数
return 0;
}1146
样例
输入:
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
6
5 2 3 6 4 1
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6输出:
0 4 5思路和坑点
思路:
按照拓扑排序的思路执行每一个串判别的序列，如果中间出现某个顶点的入度不为0，则说明此序列不是拓扑排序的序列。
AC代码
#include<bits/stdc++.h>
using namespace std;
int indegree[1003]={0}; //记录每一个结点的入度
vector<int> G[1003]; //二维数组记录图
int n,m;
int cnt=0; //计数器控制输出格式
void Judge(int q);
int main(){
int a,b,k;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
G[a].push_back(b); //邻接表表示图
indegree[b]++; //b的入度增加
}
scanf("%d",&k);
for(int i=0;i<k;i++) //判断k个序列是不是拓扑排序
Judge(i);
return 0;
}
void Judge(int q)
{
int flag=true; //判断标记
vector<int> ind(n+1); //初始化临时的入度数组
for(int i=1;i<=n;i++)
ind[i]=indegree[i];
for(int i=0;i<n;i++){ //读入序列
int temp;
scanf("%d",&temp);
if(ind[temp]!=0){ //如果按照拓扑排序的方式处理发现某一个顶点的入度不为0则不能构成拓扑排序
flag=false;
while(getchar()!='\n') //后序序列不用再判定了，直接吸收过滤后边多余字符
continue;
break;
}
else //否则把当前结点后继的所有顶点的度减一，继续循环
for(int j=0;j<G[temp].size();j++)
ind[G[temp][j]]--;
}
if(flag==false){ //根据标记判断是否输出
if(cnt++) putchar(' ');
printf("%d",q);
}
}1147
样例
输入:
3 8
98 72 86 60 65 12 23 50
8 38 25 58 52 82 70 60
10 28 15 12 34 9 8 56输出:
Max Heap
50 60 65 72 12 23 86 98
Min Heap
60 58 52 38 82 70 25 8
Not Heap
56 12 34 28 9 8 15 10思路和坑点
思路：
可以偷懒借助现成的库函数进行判定是不是堆，然后获取后序序列，也可以再获取后序序列的同时进行判定是否满足堆的要求。
AC代码
#include<bits/stdc++.h>
using namespace std;
int n,m; //m组数据，n个数值
int cnt=0; //格式控制计数器
vector<int> v; //存放序列
void Judge(); //判断堆
void getpos(int root); //后序序列
int main(){
scanf("%d%d",&m,&n);
v.resize(n);
for(int i=0;i<m;i++) //依次判断每组数据
Judge();
return 0;
}
void Judge(){
cnt=0;
for(int i=0;i<n;i++)
scanf("%d",&v[i]); //创建序列，并使用库函数直接判断是不是堆，需要C++11及以上标准支持
if(is_heap(v.begin(),v.end(),less<int>()))
puts("Max Heap");
else if(is_heap(v.begin(),v.end(),greater<int>()))
puts("Min Heap");
else
puts("Not Heap");
getpos(0); //后序序列
putchar('\n');
}
void getpos(int root){ //递归后序遍历
if(root>=n) return; //遇到空结点这返回
getpos(root*2+1); //下标从0开始则2n+1为左子树，2n+2为右子树
getpos(root*2+2);
if(cnt) putchar(' ');
printf("%d",v[root]); //输出当前结点
cnt++;
}1148
样例
样例1
输入:
5
-2
+3
-4
+5
+4输出:
1 4样例2
输入:
6
+6
+3
+1
-5
-2
+4输出:
1 5样例3
输入:
5
-2
-3
-4
-5
-1输出:
No Solution思路和坑点
思路：
我们假定两个人是狼人，然后由此判定其他人的说法，如果发现刚好满足题设条件，则说明当前假设成立，否则没有满足条件的输出，则认为无解。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
vector<int> v(N+1);
for(int i=1;i<=N;i++) //用于存放每一个玩家说的数字
cin>>v[i];
for(int i=1;i<=N;i++){ //双重循环，这样可以得到题目所说的最小序列
for(int j=i+1;j<=N;j++){
vector<int> lie,a(N+1,1); //记录说谎者和假定的身份（1表示好人，-1表示狼人，初始化为1）
a[i]=a[j]=-1; //假定i和j都是狼人
for(int k=1;k<=N;k++){ //遍历每个人说的话
if(v[k]*a[abs(v[k])]<0) //v表示第k个玩家说的话，与相对应的描述的另一位玩家abs[v[k]]的身份进行比对，如果符号（身份）不同，乘积小于0，即说明此人说谎
lie.push_back(k); //保存说谎玩家的序号
}
if(lie.size()==2&&a[lie[0]]+a[lie[1]]==0){ //如果说谎玩家刚好有两个，而且一个狼人一个好人（题目要求只有两个狼人，有狼人说谎且不是所有狼人都说谎）
cout<<i<<' '<<j; //如果满足题目条件，说明当前的假设成立，也就是i和j都是狼人，输出即可
return 0;
}
}
}
cout<<"No Solution"; //如果没有满足条件的输出，则无解
return 0;
}1149
样例
输入:
6 3
20001 20002
20003 20004
20005 20006
20003 20001
20005 20004
20004 20006
4 00001 20004 00002 20003
5 98823 20002 20003 20006 10010
3 12345 67890 23333输出:
No
Yes
Yes思路和坑点
思路：
标记两种反应物的关系，然后根据每一个货物清单，查找相关反应物是否出现在清单中。
坑点:
一个物品的反应物可能不止一种，所以要选用合适的方式存储这种关系。
AC代码
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,string> mp; //记录反应物对应关系
bool check(){
int n;
cin>>n;
unordered_map<string,int> m; //记录某个物品是否出现过
vector<string> v(n);
for(int i=0;i<n;i++){ //读取每一种货物
cin>>v[i];
m[v[i]]=1;
}
for(int i=0;i<n;i++)
if(mp[v[i]]!=""){ //如果当前物品有反应物
for(int j=0;j<mp[v[i]].size();j+=5){
string temp=mp[v[i]].substr(j,5); //每次提取从j开始的五位进行核查
if(m[temp]==1) return false; //如果与之反应的物品也出现在清单里，则不能安全运输
}
}
return true;
}
int main(){
int n,m;
string a,b;
cin>>n>>m;
for(int i=0;i<n;i++){ //采用衔接的方式构建一个类似于二维矩阵的map，
cin>>a>>b; //把每一个物品对应的反应物品string类变量直接加在value值的后边，构成一个长串
mp[a]+=b; //检查时每次取出5位进行对比核查
mp[b]+=a;
}
for(int i=0;i<m;i++) //判定m箱货物清单
puts(check()?"Yes":"No");
return 0;
}1150
样例
输入:
6 10
6 2 1
3 4 1
1 5 1
2 5 1
3 1 8
4 1 6
1 6 1
6 3 1
1 2 1
4 5 1
7
7 5 1 4 3 6 2 5
7 6 1 3 4 5 2 6
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 2 5 4 3 1
7 6 3 2 5 4 1 6输出:
Path 1: 11 (TS simple cycle)
Path 2: 13 (TS simple cycle)
Path 3: 10 (Not a TS cycle)
Path 4: 8 (TS cycle)
Path 5: 3 (Not a TS cycle)
Path 6: 13 (Not a TS cycle)
Path 7: NA (Not a TS cycle)
Shortest Dist(4) = 8思路和坑点
思路:
明确概念：1.TS cycle表示经过每一个顶点的回路。2.TS simple cycle表示简单TS cycle。3.其他的都不是TS。
因此，我们可以简单氛围TS cycle和非TS cycle，然后再对TS cycle进行判定是不是简单类型。可以使用map容器判定是否是简单回路并且能够去重判定是否经过了所有的顶点。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define INF 30000
int n,m;
int G[205][205]; //邻接矩阵存储图
int minid,mins=INF; //mins和minid存储最短的TS距离和ID
void Judge(int num);
int main(){
fill(G[0],G[0]+205*205,INF); //初始化图中的距离为最大值
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int a,b,dis;
scanf("%d%d%d",&a,&b,&dis);//读入图的数据
G[a][b]=G[b][a]=dis;
}
int k;
scanf("%d",&k);
for(int i=1;i<=k;i++) //k组路径进行判定
Judge(i);
printf("Shortest Dist(%d) = %d",minid,mins);
return 0;
}
void Judge(int num)
{
map<int,int> mp; //记录每一个顶点的出现次数
int tag=1,flag=1; //1表示TS路径，0表示不是TS,flag为标记，1表示是简单TS，0表示非简单TS
int dis=0; //计算距离
int k,first,pre,temp;
scanf("%d%d",&k,&first);
pre=first; //读入并初始化第一个结点
for(int i=1;i<k;i++){
scanf("%d",&temp);
dis+=G[pre][temp]; //统计路径长度
mp[temp]++; //统计结点次数次数
if(mp[temp]>1) flag=0; //出现重复结点则不是一定不是简单TS
pre=temp;
}
if(mp.size()!=n||dis>INF) tag=0;//如果不包含所有的顶点或者不连通则一定不是TS
printf("Path %d: ",num); //输出路径编号
if(temp==first&&tag){ //如果是回路，且满足TS的要求
printf("%d ",dis);
if(flag) puts("(TS simple cycle)"); //没有重复结点，是简单TSTS
else puts("(TS cycle)") ; //是TS
if(dis<mins){ //更新最短TS路径
mins=dis,minid=num;
}
}
else{ //如果不是回路一定不是TS
if(dis>INF) printf("NA "); //不连通的类型
else printf("%d ",dis); //连通，但仍然不是TS
puts("(Not a TS cycle)");
}
}1151
样例
输入:
6 8
7 2 3 4 6 5 1 8
5 3 7 2 6 4 8 1
2 6
8 1
7 9
12 -3
0 8
99 99输出:
LCA of 2 and 6 is 3.
8 is an ancestor of 1.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.思路和坑点
思路:
根据先序和中序的关系，可以直到在中序中，LCA一定在U和V结点的中间，或者是其中一个，但是要找到最底层的LCA则需要递归到最底层的子树上去查找，具体实现见代码及注释。
AC代码
#include<bits/stdc++.h>
using namespace std;
vector<int> pre,in; //先序顺序为根、左、右 中序序列为左、根、右
unordered_map<int,int> pos; //记录结点再中序序列中的位置
void lca(int prroot,int inl,int inr,int a,int b){
if(inl>inr) return; //当序列长度为0时返回
int inroot=pos[pre[prroot]],ain=pos[a],bin=pos[b]; //确定先序的根，a,b在中序序列的位置
if(ain<inroot&&bin<inroot) //如果a，b都在根的左子树上，则递归向左子树查询
lca(prroot+1,inl,inroot-1,a,b);
else if((ain<inroot&&bin>inroot)||(ain>inroot&&bin<inroot))//如果a，b在根的左右两侧，说明根为LCA
printf("LCA of %d and %d is %d.\n",a,b,in[inroot]);
else if(ain>inroot&&bin>inroot) //如果都在右子树，则递归向右子树查询
lca(prroot+1+inroot-inl,inroot+1,inr,a,b);
else if(ain==inroot) //如果其中有一个在根的位置上，则输出对应信息
printf("%d is an ancestor of %d.\n",a,b);
else if(bin==inroot)
printf("%d is an ancestor of %d.\n",b,a);
}
int main(){
int m,n,a,b;
scanf("%d%d",&m,&n);
in.resize(n+1),pre.resize(n+1);
for(int i=1;i<=n;i++){
scanf("%d",&in[i]);
pos[in[i]]=i;
}
for(int i=1;i<=n;i++) scanf("%d",&pre[i]); //读入序列并记录每个结点在中序序列的位置
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
if(pos.find(a)==pos.end()&&pos.find(b)==pos.end()) //如果两者都不存在
printf("ERROR: %d and %d are not found.\n", a, b);
else if(pos.find(a)==pos.end()||pos.find(b)==pos.end())//如果有一个不存在
printf("ERROR: %d is not found.\n", pos.find(a)==pos.end()?a:b);
else
lca(1,1,n,a,b); //如果凑存在则查找LCA
}
return 0;
}1152
样例
样例1
输入:
20 5
23654987725541023819输出:
49877样例2
输入:
10 3
2468024680输出:
404思路和坑点
每次截取字符串中规定位数的字符转化为数字之后判定是不是素数。
AC代码
#include<bits/stdc++.h>
using namespace std;
bool IsPrime(int x){
if(x==0||x==1) return false;
for(int i=2;i<sqrt(1.0*x);i++)
if(x%i==0) return false;
return true;
}
int main(){
string str;
int len,k;
scanf("%d %d\n",&len,&k);
cin>>str;
for(int i=0;i+k<=len;i++){ //注意循环边界
string num=str.substr(i,k); //去除当前位置开始向后的k个字符
if(IsPrime(stoi(num))){ //转化成数字并验证是不是素数，如果是则输出并返回
cout<<num; return 0;
}
}
cout<<"404"; //如果找不到符合条件的素数，则输出404
return 0;
}1153
样例
输入:
8 4
B123180908127 99
B102180908003 86
A112180318002 98
T107150310127 62
A107180908108 100
T123180908010 78
B112160918035 88
A107180908021 98
1 A
2 107
3 180908
2 999输出:
Case 1: 1 A
A107180908108 100
A107180908021 98
A112180318002 98
Case 2: 2 107
3 260
Case 3: 3 180908
107 2
123 2
102 1
Case 4: 2 999
NA思路和坑点
思路:
排序并按照查询类型遍历整个数据，然后将需要的数据输出。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct{ //学生结构体
string id;
int score;
}ST;
bool cmp(ST a,ST b){ //排序规则
if(a.score!=b.score) return a.score>b.score;
else return a.id<b.id;
}
int main(void){
int n,m,case_tp; //case_tp表示查验类型
string temp,day,room; //临时变量，时间，考场
cin>>n>>m;
vector<ST> v(n),ans; //v用于存储数据，ans用于存放答案
for(int i=0;i<n;i++)
cin>>v[i].id>>v[i].score; //读入原始数据
for(int i=1;i<=m;i++){ //进行查验
int cnt=0; //用于输出个数
cin>>case_tp>>temp; //读入查验类型和查验参数
cout<<"Case "<<i<<": "<<case_tp<<' '<<temp<<'\n';
ans.clear(); //初始化ans数组
if(case_tp==1){ //第一种类型
for(int j=0;j<n;j++) //找到同一个级别的考生放入输出的数组中
if(v[j].id[0]==temp[0]) ans.push_back(v[j]);
sort(ans.begin(),ans.end(),cmp); //按照要求排序并输出
for(int j=0;j<ans.size();j++){
cout<<ans[j].id<<' '<<ans[j].score<<'\n';
cnt++;
}
}
else if(case_tp==2){ //第二种类型
int sum=0,num=0; //用于统计总人数和总分分数
for(int j=0;j<n;j++){
room=v[j].id.substr(1,3); //遍历原始数据获取每个考生的考场号
if(room==temp){ //如果和查验的考场号相同，则累计人数和总分
num++;
sum+=v[j].score;
}
}
if(num) {printf("%d %d\n",num,sum);cnt++;} //当人数不为0时，输出并把标记cnt+1
}
else{
unordered_map<string,int> mp; //创建考场和人数的对应关系
for(int j=0;j<n;j++){ //遍历数据，获取考试日期和考场号
day=v[j].id.substr(4,6);
room=v[j].id.substr(1,3);
if(day==temp) //对应考场的人数统计+1
mp[room]++;
}
ST t; //这里发现如果把人数放在学生分数位置，考场号放在准考证号位置，两者排序规则相同，所以用于借用
for(auto it=mp.begin();it!=mp.end();it++){ //把考场号和人数组成结构体放入输出的数组中
t.id=it->first; t.score=it->second;
ans.push_back(t);
}
sort(ans.begin(),ans.end(),cmp); //按照要求排序后输出
for(int j=0;j<ans.size();j++){
cout<<ans[j].id<<' '<<ans[j].score<<'\n';
cnt++;
}
}
if(cnt==0) puts("NA"); //如果当前类型没有输出，则查询结果为空，输出NA
}
return 0;
}1154
样例
输入:
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
4
0 1 0 1 4 1 0 1 3 0
0 1 0 1 4 1 0 1 0 0
8 1 0 1 4 1 0 5 3 0
1 2 3 4 5 6 7 8 8 9输出:
4-coloring
No
6-coloring
No思路和坑点
思路：
记录每个结点的颜色，然后遍历所有的边表，如果发现有两个相邻顶点的颜色一样则不满足要求，否则按照要求输出k-coloring。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef struct edg{ //边结点定义
int a,b;
}Edg;
int n,m;
vector<Edg> v;
void Judge();
int main(){
scanf("%d%d",&n,&m);
v.resize(m);
for(int i=0;i<m;i++) //读取一个边
scanf("%d%d",&v[i].a,&v[i].b);
int k;
scanf("%d",&k);
for(int i=0;i<k;i++) //何查每一组数据
Judge();
return 0;
}
void Judge(){
map<int,int> color; //统计颜色种类
bool flag=true;
vector<int> inc(n); //读入序列
for(int i=0;i<n;i++){
scanf("%d",&inc[i]);
color[inc[i]]++;
}
for(int i=0;i<m;i++){ //遍历所有的边
int a=v[i].a,b=v[i].b;
if(inc[a]==inc[b]){ //如果边的两个顶点颜色相同
flag=false; //则不符合要求
break;
}
}
if(flag) //输出结果
printf("%d-coloring\n",color.size());
else
puts("No");
}1155
样例
样例1
输入:
8
98 72 86 60 65 12 23 50输出:
98 86 23
98 86 12
98 72 65
98 72 60 50
Max Heap样例2
输入:
8
8 38 25 58 52 82 70 60输出:
8 25 70
8 25 82
8 38 52
8 38 58 60
Min Heap样例3
输入:
8
10 28 15 12 34 9 8 56输出:
10 15 8
10 15 9
10 28 34
10 28 12 56
Not Heap思路和坑点
思路：
使用库函数判断是不是堆，然后dfs获取路径，这里注意题目要求先右节点再左节点路径。
AC代码
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> v; //存放堆的各个顶点
vector<int> path; //存放路径
void getpath(int i);
int main(){
scanf("%d",&n);
v.resize(n);
for(int i=0;i<n;i++) //读入堆的结点
scanf("%d",&v[i]);
getpath(0);
if(is_heap(v.begin(),v.end(),less<int>())) //使用stl中的函数判断堆
puts("Max Heap");
else if(is_heap(v.begin(),v.end(),greater<int>()))
puts("Min Heap");
else
puts("Not Heap");
return 0;
}
void getpath(int i){ //获取根到结点的路径
if(i*2+1>=n&&i<n){ //如果已经到了最后一层
path.push_back(v[i]); //加入最后一个叶子结点
for(int j=0;j<path.size();j++){ //输出路径
if(j) putchar(' ');
printf("%d",path[j]);
}
putchar('\n');
path.pop_back(); //回退一个元素返回到上一层
return;
}
else if(i>=n) return; //如果当前结点为空直接返回上一层
path.push_back(v[i]); //放入当前结点
getpath(i*2+2); //获取右子树叶子结点路径
getpath(i*2+1); //获取左子树叶子结点路径
path.pop_back(); //回退一个元素返回到上一层
}
Comments | NOTHING