当前位置：网站首页>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）
边栏推荐
- Is it safe to open a securities account online
- Shengxin weekly issue 33
- recvmsg ＆ sendmsg
- What is the process of opening a mobile card account? Is it safe to open an account online?
- 清甜女孩李斯霞 受邀担任第六季完美童模全球总决赛小主持人
- Talking about interface test (I)
- Summary of knowledge points of catboost
- readv ＆ writev
- Textcnn paper Interpretation -- revolutionary neural networks for sense classification
- 完整复习(包含语法)--MYSQL正则表达式
猜你喜欢
biggan:large scale gan training for high fidelity natural image synthesis
通过电脑获取WIFI密码（只能连接过的WiFi）
王老吉药业“关爱烈日下最可爱的人”公益活动在杭启动
GUN make (2) 总述
Interpretation of script corresponding to postman assertion
MySQL book borrowing system project database creation TABLE statement (combined primary key and foreign key settings)
甜酷少女金书伊 受邀担任第六季完美童模全球总决赛代言人
Can bus transceiver principle
Abnova丨抗GBA单克隆抗体解决方案
浅谈接口测试（二）
随机推荐
俏皮少女王艺璇 受邀担任第六季完美童模全球总决赛推广大使
Loss function of depth model
**MySQL例题一（根据不同问题，多条件查询）**
Focal loss
2022 explosion proof electrical operation certificate examination question bank and simulation examination
胰蛋白酶的化学性质及应用
快速生成1~20自然数，并轻松复制
Abnova丨ACTN4 DNA 探针解决方案
CYCA少儿形体礼仪 乐清市培训成果考核圆满落幕
cyclegan:unpaired image-to-image translation using cycle-consistent adversarial network
2021-1-15 摸魚做的筆記Ctrl+c /v來的
Common basic Oracle commands
NLP enhanced technology
Summary of informer's paper
GUN make (5) makefile中的变量
弹性蛋白酶的用途和化学性质
Common deep learning optimizers
2021-1-15 fishing notes ctrl+c /v
Model integration and cascading
27. template match