当前位置：网站首页>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）
边栏推荐
猜你喜欢
随机推荐
Shengxin weekly issue 33
JQ user defined attribute value
--都市修炼手册之SQL-- 第一章 基础复习
Quickly generate 1~20 natural numbers and easily copy
Install tensorflow GPU miscellaneous
Is it safe to log in the stock account on the flush? How to open a stock account in the flush
27. template match
浅谈接口测试（二）
微信朋友圈测试点
Forgotten Jieba participle
Talking about interface test (I)
GUN make (1) 简介
Oracle数据库开启备份准备工作
正则表达式
Fasttext knowledge points summary
leetcode 300. Longest Increasing Subsequence 最长递增子序列 (中等)
Textcnn paper Interpretation -- revolutionary neural networks for sense classification
完整复习(包含语法)--MYSQL正则表达式
二造实务案例答题技巧和举例汇总，满满都是精髓
GUN make (2) 总述