当前位置：网站首页>PTA class a simulated seventh bomb: 1160-1163
PTA class a simulated seventh bomb: 1160-1163
2022-06-26 01:43:00 【Republic cake】
1. Summary of knowledge points
Stuck in the first question …… And then there was No
Fortunately, it's not an exam …… Otherwise, the state of mind can be said to have blown up
But other topics are more basic ,Dijkstra Need a good review , I haven't done it for a long time
| Question no | difficulty | Knowledge point |
|---|---|---|
| 1160 | mathematics + Looking for a regular + Search for DFS+ prune （ Personally, I think it needs three brushes ） | |
| 1161 | Linked list | |
| 1162 | Binary tree traversal | |
| 1163 | Dijkstra |
2. Sub topic solution
2.1 The first question is
A question about the state of mind , At first, I noticed that the number at the end can only be 9, Otherwise
n=m+1Is unable to exportn And m The common factor is greater than 2Of , But the first pass of the code doesn't cover this at all …… Because I don't think it's very big ……
for the first time ：2/20
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
int m;
int k;
// Prime judgment
bool isPrime(ll x){
if(x<=2)return false;
if(x==3||x==5||x==7)return true;
for(ll i=2;i*i<=x;i++){
if(x%i==0)return false;
}
return true;
}
// The greatest common factor : division a>b
ll maxDiv(ll a,ll b){
if(a<b){
swap(a,b);
}
ll r=a;
while(r!=0){
r=a%b;
a=b;
b=r;
}
return a;
}
struct Ans{
int n;
ll num;
};
// Calculate the sum of each addition of integers
int CountDigits(string now){
int len=now.size();
int sum=0;
for(int i=0;i<len;i++){
sum+=now[i]-'0';
}
return sum;
}
// Minimum allowable value
int lowest=0;
void CountLowest(int digit_num,int sum,int& lowest){
if(digit_num==1){
lowest=max(lowest,sum);
}
else{
digit_num--;
int temp=sum-9*digit_num;
lowest=max(lowest,temp);
}
//printf("%d A digital , And for %d, minimum value %d\n",digit_num+1,sum,lowest);
}
// Deep search ： Search all the solutions that meet the conditions
vector<Ans>ans;
void dfs(int num,int sum,string now,int digit_num,int mylow){
//printf("digit_num=%d now=%s\n",digit_num,now.c_str());
// The currently traversed number is num, Current sum is sum,now Store all current numbers
now=now+to_string(num);
sum+=num;
digit_num++;
if(sum>m||digit_num>k)return;
// Knowing that the next step is not enough
if(sum+9*(k-digit_num)<m)return;
if(sum==m&&digit_num==k){
//1 0 && 11 10 There can be no greater than 2 The common factor of
ll candidate=stol(now);
string candidate1=to_string(candidate+1);
int dsum=CountDigits(candidate1);
//printf("&&&&&&&&&&&&&&&&&&&dsum=%d m=%d\n",dsum,m);
if(isPrime(maxDiv(dsum,m))){
Ans temp;
temp.n=dsum;
temp.num=candidate;
ans.push_back(temp);
}
return;
}
// Continue to explore
CountLowest(k-digit_num,m-sum,mylow);
for (int i=lowest;i<10;i++){
dfs(i,sum,now,digit_num,mylow);
}
return;
}
int main(){
scanf("%d",&N);
for(int i=1;i<=N;i++){
scanf("%d%d",&k,&m);
// find k An integer consisting of numbers A, Its sum is m
//n=(A+1) and
//m and n The greatest common factor of is greater than 2 The prime
CountLowest(k,m,lowest);
for(int i=lowest;i<10;i++){
if(i==0)continue;
dfs(i,0,"",0,0);
}
printf("Case %d\n",i);
int len=ans.size();
if(len==0){
printf("No Solution\n");
}
for(int i=0;i<len;i++){
printf("%d %lld\n",ans[i].n,ans[i].num);
}
ans.clear();
}
return 0;
}
The second time ： Revision
The first edition ：10 branch
#include<bits/stdc++.h>
using namespace std;
// Yes i individual 9,m-n=8+9*(i-1)
int n;
int k,m;
typedef long long ll;
bool Prime(ll x){
if(x<=2)return false;
for(ll i=2;i*i<=x;i++){
if(x%i==0)return false;
}
return true;
}
ll gcd(ll a,ll b){
if(a<b)swap(a,b);
ll r=b;
while(r!=0){
r=a%b;
a=b;
b=r;
}
return a;
}
struct Ans{
ll num;
int n;
};
vector<Ans>ans;
int target_sum;
int digit_sum;
string nine;
void dfs(int pos,int num,int sum,string now){
//cout<<"now "<<now<<endl;
pos++;
sum+=num;
now+=to_string(num);
if(sum==target_sum&&pos==digit_sum){
//ans.push_back(stol(now+nine));
Ans temp;
temp.n=n;
temp.num=stol(now+nine);
ans.push_back(temp);
return;
}
if(sum>target_sum||pos>digit_sum){
return;
}
for(int i=0;i<=min(9,target_sum-sum);i++){
dfs(pos,i,sum,now);
}
return ;
}
int N;
bool cmp(Ans a,Ans b){
if(a.n!=b.n){
return a.n<b.n;
}else{
return a.num<b.num;
}
}
int main(){
scanf("%d",&N);
for(int l=1;l<=N;l++){
printf("Case %d\n",l);
scanf("%d%d",&k,&m);
bool flag=false;
for(int num9=1;num9<=k;num9++){
// At the end of num9 The number of
n=m-(8+9*(num9-1));
if(n<=1){
break;
}
int div=gcd(m,n);
if(Prime(div)){
// legal
target_sum=m-num9*9;
digit_sum=k-num9;
nine="";
for(int c=0;c<num9;c++){
nine+="9";
}
for(int i=1;i<=min(9,target_sum);i++){
dfs(0,i,0,"");
}
}
}
// Output the answer
int len=ans.size();
if(len!=0){
flag=true;
}
sort(ans.begin(),ans.end(),cmp);
for(int c=0;c<len;c++){
printf("%d %lld\n",ans[c].n,ans[c].num);
}
ans.clear();
if(!flag){
printf("No Solution\n");
}
}
return 0;
}
The second edition ：AC
#include<bits/stdc++.h>
using namespace std;
struct Ans{
int n;
int A;
};
int N;
int k,m;
int n;
bool isPrime(int x){
if(x<=2)return false;
if(x==2||x==3||x==5||x==7)return true;
for(int i=2;i*i<=x;i++){
if(x%i==0)return false;
}
return true;
}
int gcd(int a ,int b){
//a>b
return b==0?a:gcd(b,a%b);
}
int digitSum(int x){
int sum=0;
while(x){
sum+=(x%10);
x/=10;
}
return sum;
}
vector<Ans>ans;
void dfs(int A,int sum,int rest_k){
if(rest_k==0){
if(sum==m){
int n=digitSum(A+1);
if(isPrime(gcd(m,n))){
ans.push_back({
n,A});
}
}
}else if(rest_k>0){
for(int i=0;i<=9;i++){
// prune
if(sum+i<=m&&sum+i+(rest_k-1)*9>=m){
dfs(A*10+i,sum+i,rest_k-1);
}
}
}
}
bool cmp(Ans a,Ans b){
if(a.n!=b.n){
return a.n<b.n;
}else{
return a.A<b.A;
}
}
int main(){
scanf("%d",&N);
for(int times=1;times<=N;times++){
scanf("%d%d",&k,&m);
printf("Case %d\n",times);
//dfs Search for answers
for(int i=1;i<=9;i++){
dfs(i,i,k-1);
}
sort(ans.begin(),ans.end(),cmp);
// Output the answer
int len=ans.size();
for(int i=0;i<len;i++){
printf("%d %d\n",ans[i].n,ans[i].A);
}
ans.clear();
if(len==0){
printf("No Solution\n");
}
}
return 0;
}
2.2 The second question is Merging Linked Lists
Basic problems of linked list （ blend STL）, Pay attention to the output format and -1 The location of
#include<bits/stdc++.h>
using namespace std;
// List operation
struct Node{
int addr;
int val;
int next;
};
int head1;
int head2;
int n;
int addr,val,next_addr;
map<int,Node>nodes;
vector<Node>v1;
vector<Node>v2;
void Change(vector<Node>v1,vector<Node>v2){
int lena=v1.size();
int lenb=v2.size();
int j=lenb-1;
for(int i=0;i<lena;i++){
if(i!=lena-1)
printf("%05d %d %05d\n",v1[i].addr,v1[i].val,v1[i+1].addr);
else
printf("%05d %d -1\n",v1[i].addr,v1[i].val);
if(j>=0){
i++;
// Print
if(1)
printf("%05d %d %05d\n",v1[i].addr,v1[i].val,v2[j].addr);
else
printf("%05d %d -1\n",v1[i].addr,v1[i].val);
// Print
if(i+1!=lena)
printf("%05d %d %05d\n",v2[j].addr,v2[j].val,v1[i+1].addr);
else
printf("%05d %d -1\n",v2[j].addr,v2[j].val);
j--;
}
}
}
int main(){
scanf("%d%d%d",&head1,&head2,&n);
for(int i=0;i<n;i++){
scanf("%d%d%d",&addr,&val,&next_addr);
Node temp;
temp.addr=addr;
temp.val=val;
temp.next=next_addr;
nodes[addr]=temp;
}
int p=head1;
// Traverse v1
while(p!=-1){
Node temp=nodes[p];
v1.push_back(temp);
p=temp.next;
}
// Traverse v2
p=head2;
while(p!=-1){
Node temp=nodes[p];
v2.push_back(temp);
p=temp.next;
}
int len1=v1.size();
int len2=v2.size();
if(len1>=2*len2){
Change(v1,v2);// Big Small
}else {
Change(v2,v1);
}
return 0;
}
2.3 Third question Postfix Expression
This problem examines the traversal of static binary trees , It should be noted that :
- In the normal follow-up traversal, it is necessary to determine whether a node is “+”、“-” And there is no left child （ That is, the non operator , It's a symbol for ）, At this time, the post order traversal is changed to the pre order traversal
- root The search is mainly based on the input , Which node has not been a child
#include<bits/stdc++.h>
using namespace std;
// Static binary tree
struct Node{
char data[15];
int left;
int right;
};
int n;
vector<Node>v;
void postTravel(int root){
if(root==-1){
return;
}
if((v[root].data[0]=='-'||v[root].data[0]=='+')&&strlen(v[root].data)==1&&v[root].left==-1){
printf("(");
printf("%s",v[root].data);
postTravel(v[root].left);
postTravel(v[root].right);
printf(")");
}else{
printf("(");
postTravel(v[root].left);
postTravel(v[root].right);
printf("%s",v[root].data);
printf(")");
}
}
int root;
bool isNotRoot[50]={
false};
int main(){
scanf("%d",&n);
v.resize(n+1);
for(int i=1;i<=n;i++){
scanf("%s%d%d",v[i].data,&v[i].left,&v[i].right);
if(v[i].left!=-1){
isNotRoot[v[i].left]=true;
}
if(v[i].right!=-1){
isNotRoot[v[i].right]=true;
}
}
for(int i=1;i<=n;i++){
if(!isNotRoot[i]){
root=i;
break;
}
}
postTravel(root);
return 0;
}
2.4 Fourth question Dijkstra Sequence
I was wondering if I should search every (st,ed) Corresponding to all possible outputs , and q Comparison of the sequences asked in , But then directly in Dij Function will be u Initialization of q, Compare directly in the algorithm process , Time and space can be saved
#include<bits/stdc++.h>
using namespace std;
const int INF=99999999;
// Check whether a sequence is dijkstra Sequence
int n,m,k;
const int maxn=1009;
int graph[maxn][maxn];
int u,v,d;
vector<int>q;
vector<int>temp;
bool Dij(int st,int ed){
//st To ed The shortest distance
temp.clear();
vector<int>dis(n+1);// The shortest distance from the starting point to each vertex
vector<bool>vis(n+1);
fill(vis.begin(),vis.end(),false);
fill(dis.begin(),dis.end(),INF);
dis[st]=0;// The distance of the starting point itself is 0
int id=0;
for(int i=1;i<=n;i++){
//int u=-1,min_dis=INF;
int u=q[id];
int min_dis=dis[u];
id++;
for(int j=0;j<=n;j++){
if(vis[j]==false&&dis[j]<min_dis){
return false;
}
}
if(u==-1){
break;
}
temp.push_back(u);
vis[u]=true;
for(int v=1;v<=n;v++){
if(!vis[v]&&graph[u][v]!=-1&&dis[v]>graph[u][v]+dis[u]){
dis[v]=graph[u][v]+dis[u];
}
}
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
memset(graph,-1,sizeof(graph));
for(int i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&d);
graph[u][v]=d;
graph[v][u]=d;
}
scanf("%d",&k);
q.resize(n);
for(int i=0;i<k;i++){
// Interrogation sequence
for(int j=0;j<n;j++){
scanf("%d",&q[j]);
}
// Handle
int st=q[0];
int ed=q[n-1];
if(Dij(st,ed)){
printf("Yes\n");
}else{
printf("No\n");
}
}
return 0;
}
3. Reference link
- 1160 Blog ideas
- 1160 Blog explanation （ A simpler version DFS）
边栏推荐
- --SQL of urban cultivation manual -- Chapter 1 basic review
- Reading notes on how to connect the network - hubs, routers and routers (III)
- shell正则表达式
- 快速生成1~20自然数，并轻松复制
- 同花顺上登录股票账户是安全的吗？同花顺上是如何开股票账户的
- 二造实务案例答题技巧和举例汇总，满满都是精髓
- GUN make (1) 简介
- 在FreeBSD中安装MySQL数据库
- Oracle数据库开启备份准备工作
- Have you considered going or staying in graduation season
猜你喜欢
Viwi interface
清甜女孩李斯霞 受邀担任第六季完美童模全球总决赛小主持人
Simple making of master seal
元气少女王钰洁 受邀担任第六季完美童模全球总决赛代言人
RT thread project engineering construction and configuration - (Env kconfig)
热血男孩滕文泽 受邀担任第六季完美童模全球总决赛形象大使
浅谈接口测试（二）
Postman断言对应脚本的解释
Android system startup security
GNN (graph neural network) introduction vernacular
随机推荐
Common deep learning optimizers
User unlock status query
Procédure de désinstallation complète de la base de données Oracle (pas de capture d'écran)
JSON实例（一）
Is it safe to log in the stock account on the flush? How to open a stock account in the flush
Obtain WiFi password through computer (only connected WiFi)
微信朋友圈测试点
【Visual Studio Code】vscode快捷键大全
Postman接口测试之断言
蒟蒻初学单片机的一丢丢笔记
Android system startup security
胰蛋白酶的化学性质及应用
2022 explosion proof electrical operation certificate examination question bank and simulation examination
JSON instance (I)
Reading notes on how to connect the network - hubs, routers and routers (III)
判定积分给业务带来价值的两个指标
王老吉药业“关爱烈日下最可爱的人”公益活动在杭启动
[flower carving experience] 11 start esp32c3
走 迷 宫
Summary of in-depth learning optimization techniques