当前位置：网站首页>[PTA] group programming ladder competition - Summary of exercises L3 (incomplete)
[PTA] group programming ladder competition - Summary of exercises L3 (incomplete)
2022-07-24 07:13:00 【karshey】
Simulation question
STL topic
L3-002 Special stack （ Two vector）
L3-002 Special stack
Reference resources
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e5+10;
int n;
vector<int>v,v1;//v Orderly
int main()
{
cin>>n;
while(n--)
{
string a;cin>>a;
if(a=="Pop")
{
if(v1.empty()) puts("Invalid");
else
{
int t=v1.back();
auto it=lower_bound(v.begin(),v.end(),t);
v.erase(it);
cout<<t<<endl;
v1.pop_back();
}
}
else if(a=="PeekMedian")
{
if(v1.empty()) puts("Invalid");
else cout<<v[(v.size()+1)/2-1]<<endl;
}
else
{
int t;cin>>t;
v1.pb(t);
auto it=lower_bound(v.begin(),v.end(),t);
v.insert(it,t);
}
}
return 0;
}
dp topic
Search questions
L3-001 Collect change （dfs）
dfs： From smallest to largest , The first answer found is the answer with the smallest sequence . If it is arranged from large to small, it will TLE Two points .
It's fine too dp（01 knapsack ）.
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e4+10;
int n,m,a[N],sum,fl;
vector<int>ans,anss;
void dfs(int u,int sum)
{
if(fl) return;
if(sum>m) return;
if(sum==m)
{
fl=1;
anss=ans;
return;
}
for(int i=u;i<=n;i++)
{
ans.pb(a[i]);
dfs(i+1,sum+a[i]);
ans.pop_back();
}
}
int main()
{
cin>>n>>m;
fir(i,1,n)
{
cin>>a[i];sum+=a[i];
}
if(sum<m)
{
cout<<"No Solution";return 0;
}
sort(a+1,a+1+n);
dfs(1,0);
if(fl)
{
int f=0;
for(auto x:anss)
{
if(f) cout<<" ";
cout<<x;f++;
}
}
else cout<<"No Solution";
return 0;
}
L3-004 Tumor diagnosis （bfs）
The three dimensional bfs.
dfs There will be some mistakes , It is estimated that there are too many recursions .
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1500+10;
int g[1300][130][80],v[1300][130][80];
int n,m,l,t;
int ans,temp;
int dx[6]={
0,0,0,0,1,-1};
int dy[6]={
0,0,1,-1,0,0};
int dz[6]={
1,-1,0,0,0,0};
struct node
{
int x,y,z;
};
void bfs(int x,int y,int z)
{
queue<node>q;
q.push({
x,y,z});
while(q.size())
{
node t=q.front();q.pop();
for(int i=0;i<6;i++)
{
int xx=t.x+dx[i];
int yy=t.y+dy[i];
int zz=t.z+dz[i];
if(xx>=1&&xx<=m&&yy>=1&&yy<=n&&zz>=1&&zz<=l)
{
if(!v[xx][yy][zz]&&g[xx][yy][zz])
{
v[xx][yy][zz]=1;
temp++;
q.push({
xx,yy,zz});
}
}
}
}
}
int main()
{
cin>>m>>n>>l>>t;
fir(i,1,l)
fir(j,1,m)
fir(k,1,n)
cin>>g[j][k][i];
fir(i,1,l)
fir(j,1,m)
fir(k,1,n)
{
if(!v[j][k][i]&&g[j][k][i])
{
temp=1;
v[j][k][i]=1;
bfs(j,k,i);
if(temp>=t) ans+=temp;
}
}
cout<<ans;
return 0;
}
L3-008 Shoushan （bfs）
Did not understand “ Let's say that there are at most two near the top of each mountain ” It means , Direct template bfs once .
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e4+10;
int n,m,k;
vector<int>g[N];
struct node
{
int a,ans;
};
int id,maxn;
int v[N];
int bfs(int x)
{
memset(v,0,sizeof(v));
queue<node>q;
q.push({
x,0});
v[x]=1;
id=-1,maxn=-1;
while(q.size())
{
node t=q.front();q.pop();
for(auto u:g[t.a])
{
if(v[u]) continue;
v[u]=1;
node temp={
u,t.ans+1};
if(t.ans+1>maxn)
{
maxn=t.ans+1;
id=u;
}
else if(t.ans+1==maxn&&u<id)
{
id=u;
}
q.push(temp);
}
}
return id;
}
int main()
{
cin>>n>>m>>k;
fir(i,1,m)
{
int a,b;cin>>a>>b;
g[a].pb(b);g[b].pb(a);
}
while(k--)
{
int kk;cin>>kk;
int ans=bfs(kk);
if(ans==-1) puts("0");
else cout<<ans<<endl;
}
return 0;
}
Graph theory
L3-011 press forward to the enemy's capital （dij+dfs+map）
L3-011 press forward to the enemy's capital
A hodgepodge of too many elements belongs to .
I hear it's direct dfs You can also get full marks , The data is a little bit watery .
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define ll long long
#define pb push_back
const int N=200+10;
int n,m;
string start,endd;
map<string,int>mp;
map<int,string>mpp;
int idx=1;
void add(string a)
{
mp[a]=idx;
mpp[idx]=a;
idx++;
}
int p[N];//people
int g[N][N];
int ss,ee;//start end
int dist[N],st[N];
int dij()
{
memset(dist,0x3f,sizeof(dist));
dist[ss]=0;
for(int i=1;i<=n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]&&(t==-1||dist[j]<dist[t]))
{
t=j;
}
}
st[t]=1;
for(int j=1;j<=n;j++)
{
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
return dist[ee];
}
int minn,all,killl;
vector<int>ans,temp;
int v[N];
void dfs(int u,int kill)
{
if(u==ee)
{
all++;
if(temp.size()>ans.size())
{
ans=temp;killl=kill;
}
else if(temp.size()==ans.size()&&kill>killl)
{
killl=max(killl,kill);ans=temp;
}
return;
}
for(int i=1;i<=n;i++)
{
if(!v[i]&&dist[i]==dist[u]+g[u][i])
{
v[i]=1;
temp.pb(i);
dfs(i,kill+p[i]);
temp.pop_back();
v[i]=0;
}
}
}
int main()
{
cin>>n>>m>>start>>endd;
add(start);add(endd);
fir(i,1,n-1)
{
string a;int b;cin>>a>>b;
if(mp.find(a)==mp.end())
{
add(a);
}
int t=mp[a];p[t]=b;
}
memset(g,0x3f,sizeof(g));
fir(i,1,m)
{
string a,b;int c;cin>>a>>b>>c;
int t1=mp[a],t2=mp[b];
g[t1][t2]=g[t2][t1]=c;
}
ss=mp[start],ee=mp[endd];
// The shortest length
minn=dij();
all=0;ans.clear();
killl=0;
v[ss]=1;
temp.pb(ss);
dfs(ss,0);
int f=0;
for(auto x:ans)
{
if(f) cout<<"->";
cout<<mpp[x];f++;
}
cout<<endl;
cout<<all<<" "<<minn<<" "<<killl;
return 0;
}
L3-005 Dustbin distribution （dij）
For every trash can dij.
Be careful ： Final output to lf, If it's just f It will not pass the last point .
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e3+30;
int n,m,k,ds;
int toint(string a)
{
int anss=0;
for(int i=0;a[i];i++)
{
if(a[i]>='0'&&a[i]<='9') anss=anss*10+a[i]-'0';
}
return anss;
}
int g[N][N];
int dist[N],st[N];
void dij(int s)// Calculate all points to s One of the most short circuit
{
memset(dist,0x3f,sizeof(dist));
memset(st,0,sizeof(st));
dist[s]=0;//s Point as the starting point
for(int i=1;i<=n+m;i++)
{
int t=-1;
for(int j=1;j<=n+m;j++)
if(!st[j]&&(t==-1||dist[j]<dist[t]))
t=j;
st[t]=1;
for(int j=1;j<=n+m;j++)
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
}
int ansid;double ans1,ans2;
int main()
{
cin>>n>>m>>k>>ds;
memset(g,0x3f,sizeof(g));
fir(i,1,k)
{
string a,b;int c;cin>>a>>b>>c;
int aa=toint(a),bb=toint(b);
if(a[0]=='G') aa+=n;
if(b[0]=='G') bb+=n;
g[aa][bb]=g[bb][aa]=c;
}
ansid=11;ans1=-1,ans2=0x3f3f3f3f;
for(int i=1;i<=m;i++)
{
int t=i+n;
dij(t);
int minn=0x3f3f3f3f;double pj=0;int f=0;
for(int j=1;j<=n;j++)
{
if(dist[j]>ds)
{
f=1;break;
}
minn=min(dist[j],minn);
pj+=dist[j];
}
pj/=n;
if(!f)
{
int flag=0;
if(minn>ans1) flag++;
else if(ans1==minn&&pj<ans2) flag++;
else if(ans1==minn&&ans2==pj&&i<ansid) flag++;
if(flag)
{
ansid=i;ans1=minn;ans2=pj;
}
}
}
if(ansid==11) puts("No Solution");
else
{
printf("G%d\n",ansid);
printf("%.1lf %.1lf",(double)ans1,ans2);// No lf The last point will not pass buckle 4 branch
}
return 0;
}
Binary tree problem
L3-010 Complete binary search tree
L3-010 Complete binary search tree
Be careful ： If it's not a completely binary tree , Then it is possible that the subscript of the node is very large , May explode int or LL, So want to use map.
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=20+10;
map<int,int>mp;
int n;
void in(int x)
{
int xx=1;
while(mp.find(xx)!=mp.end())
{
if(x>mp[xx]) xx*=2;
else xx=xx*2+1;
}
mp[xx]=x;
}
int main()
{
cin>>n;
cin>>mp[1];
fir(i,2,n)
{
int t;cin>>t;
in(t);
}
vector<int>temp;
int f=0,ff=0;
for(auto x:mp)
{
if(f) cout<<" ";
f++;cout<<x.second;
temp.pb(x.first);
}
for(int i=0;i<temp.size()-1;i++)
{
if(temp[i]+1!=temp[i+1]) ff=1;
}
cout<<endl;
if(ff) cout<<"NO";
else cout<<"YES";
return 0;
}
L3-016 The structure of binary search tree （ Binary tree construction +map+ simulation ）
L3-016 The structure of binary search tree
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e5+10;
int n,m;
map<int,int>mp,ans;
void ins(int x)
{
int xx=1;
while(mp.find(xx)!=mp.end())
{
if(x>mp[xx]) xx=xx*2+1;
else xx*=2;
}
mp[xx]=x;ans[x]=xx;
}
int main()
{
cin>>n;
cin>>mp[1];ans[mp[1]]=1;
fir(i,2,n)
{
int t;cin>>t;
ins(t);
}
cin>>m;
while(m--)
{
int a;cin>>a;string s1;cin>>s1;
if(s1=="is")
{
string s2;cin>>s2>>s2;
//the root
if(s2=="root")
{
if(ans.find(a)!=ans.end()&&ans[a]==1) puts("Yes");
else puts("No");
}
//the parent of B
else if(s2=="parent")
{
cin>>s2;int b;cin>>b;
if(ans.find(a)!=ans.end()&&ans.find(b)!=ans.end())
{
int aa=ans[a],bb=ans[b];
if(bb/2==aa) puts("Yes");
else puts("No");
}
else puts("No");
}
//the left child of B
else if(s2=="left")
{
cin>>s2>>s2;int b;cin>>b;
if(ans.find(a)!=ans.end()&&ans.find(b)!=ans.end())
{
int aa=ans[a],bb=ans[b];
if(aa==bb*2) puts("Yes");
else puts("No");
}
else puts("No");
}
//the right child of B
else if(s2=="right")
{
cin>>s2>>s2;int b;cin>>b;
if(ans.find(a)!=ans.end()&&ans.find(b)!=ans.end())
{
int aa=ans[a],bb=ans[b];
if(aa==bb*2+1) puts("Yes");
else puts("No");
}
else puts("No");
}
}
else
{
int b;string s2;
cin>>b>>s2>>s2;
//and B are siblings
if(s2=="siblings")
{
int aa=-1,bb=-1;
if(ans.find(a)!=ans.end()) aa=ans[a];
if(ans.find(b)!=ans.end()) bb=ans[b];
if(aa==bb+1||bb==aa+1) puts("Yes");
else puts("No");
}
//and B are on the same level
else
{
int aa=0,bb=0,f=0;
if(ans.find(a)!=ans.end()) a=ans[a];
else f++;
if(ans.find(b)!=ans.end()) b=ans[b];
else f++;
while(a)
{
a/=2;aa++;
}
while(b)
{
b/=2;bb++;
}
if(aa==bb&&!f) puts("Yes");
else puts("No");
string temp;
fir(i,1,3) cin>>temp;
}
}
}
return 0;
}
Check the set of questions
L3-003 Social cluster
Be careful , Here is the number of people in each parallel search set , Therefore, we should use everyone's first hobby to represent this person .
#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e3+10;
int n,p[N];
void ini()
{
for(int i=1;i<=1000;i++) p[i]=i;
}
int find(int x)
{
while(x!=p[x]) x=p[x];
return p[x];
}
void merge(int a,int b)
{
int aa=find(a),bb=find(b);
if(aa!=bb) p[bb]=aa;
}
int v[N],a[N];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
ini();
cin>>n;
fir(i,1,n)
{
int t;cin>>t;char op;cin>>op;
cin>>a[i];t--;
while(t--)
{
int temp;cin>>temp;
merge(a[i],temp);
}
}
map<int,int>mp;
fir(i,1,n)
{
int fa=find(a[i]);
mp[fa]++;
}
cout<<mp.size()<<endl;
vector<int>ans;
for(auto x:mp) ans.pb(x.second);
sort(ans.begin(),ans.end(),cmp);
int f=0;
for(auto x:ans)
{
if(f) cout<<" ";
f++;cout<<x;
}
return 0;
}
边栏推荐
- xavier_ normal_ Initialization test
- Vs debugging
- STM32 ADC based on Hal library uses DMA multi-channel sampling and solves the problems encountered
- Redis 主从机制
- Hackingtool of security tools
- Use the root user to create a new user and set the password for
- Mongodb application scenario and model selection (massive data storage model selection)
- 编译与调试（gcc,g++,gdb）
- 【行测】图形找规律类题目
- Upload pictures Base64
猜你喜欢
第二部分—C语言提高篇_4. 二级指针
OWASP TOP10 penetration test
Variables and data types (04) end
Ue4/5 cannot open the file "xxx.generated.h" (cannot open file xxx.generated.h) solution summary
C language from entry to soil (III)
【LeetCode】11. 盛最多水的容器 - Go 语言题解
Introduction to pyqt5 - student management system
（笔记整理未完成）【图论：求单源最短路径】
Redis persistence
sojson jsjiami.com. V6 crawler JS reverse
随机推荐
Redis 分片集群
17. What is the situation of using ArrayList or LinkedList?
Use dichotomy to find specific values from the array
AMD64(x86_64)架构abi文档：上
安全工具之hackingtool
电子商务时代，企业社交电商转型要做什么？
Redis 持久化
Ue4/5 cannot open the file "xxx.generated.h" (cannot open file xxx.generated.h) solution summary
Redis master-slave mechanism
2022-07-22 mysql/stonedb并行hashJoin内存占用分析
一个怎样的模式能让平台用户发生自助裂变？-链动2+1
【Tips】创建版本控制项目的简单方法
第二部分—C语言提高篇_3. 指针强化
B. Also Try Minecraft
Accumulation of project problems
单点登录的三种实现方式
17. 什么情况用ArrayList or LinkedList呢?
Redis 主从机制
MongoDB应用场景及选型（海量数据存储选型）
【LeetCode】11. 盛最多水的容器 - Go 语言题解