1. 知识点总结
90/100
这次卡在第一题,主要是考察思维(如何遍历确定边界来减少时间复杂度)
题目 | 难度 | 知识点 |
---|---|---|
Forever | 🎯🎯 | 时间复杂度+数组 |
Merging Linked Lists | 🎯 | 链表 |
Postfix Expression | 🎯 | 二叉树后序遍历 |
Dijkstra Sequence | 🎯 | Dij算法 |
2. 分题题解
2.1 Forever
第一版,只过了一个测试点,估计是只过了样例,思路如代码,自认为注释还是很容易看懂的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll A;
ll m,n;
int K;
int N;
//最大公因数
ll gcd(ll a,ll b){
ll temp;
while(a){
temp=a;
a=b%a;
b=temp;
}
return b;
}
bool flag=false;
int tail;
void dfs(ll num,int len,ll sum,int tlen,ll tsum){
//num是当前的数字,len是当前数字长度,sum是当前数字各位之和
//printf("当前数字:%lld 长度:%d 和:%lld 目标长度:%d 目标和:%lld\n",num,len,sum,tlen,tsum);
if(len>tlen||sum>tsum){
return;
}
if(sum<tsum&&len>=tlen){
return;
}
if(sum==tsum&&len==tlen){
printf("%lld %lld",n,num);
for(int i=0;i<tail;i++){
printf("9");
}
printf("\n");
}else{
for(int i=0;i<=9;i++){
//剪枝
if((tlen-len-1)*9+sum+i<tsum)continue;
if(sum+i<=tsum){
dfs(num*10+i,len+1,sum+i,tlen,tsum);
}
}
}
return ;
}
int main(){
scanf("%d",&N);
for(int i=1;i<=N;i++){
flag=false;
scanf("%d%lld",&K,&m);
printf("Case %d\n",i);
//枚举可以末尾放9的个数
for(int tail_9=K;tail_9>=1;tail_9--){
//首先判断能否构成一个数字
int head=K-tail_9;
tail=tail_9;
if((head&&m-tail_9*9>=1&&(m-tail_9*9)/head<=9)||(head==0&&m-tail_9*9==0)){
//如果能构成一个数字的话
n=m+1-tail_9*9;
ll sum=m-tail_9*9;
if(gcd(n,m)>2){
//输出答案
if(head){
for(ll j=1;j<=9;j++){
if(j<=sum){
dfs(j,1,j,head,sum);
}
}
}else{
printf("%lld ",n);
for(int c=0;c<tail;c++){
printf("9");
}
printf("\n");
}
flag=true;
}
}
}
if(!flag){
printf("No Solution\n");
}
}
return 0;
}
第二版
怀疑是直接输出的时候没有考虑重复输出的情况,所以加上了限制,即用set过滤重复的样本,结果还是10/20;
稍微复习了一下结构体重载运算符的写法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll A;
ll m,n;
int K;
int N;
//答案
struct Ans{
int n;
string str;
//重写结构体==
bool operator ==(const Ans a)const{
return this->n==a.n&&this->str==a.str;
}
bool operator <(const Ans a)const{
if(this->n!=a.n){
return this->n<a.n;
}else{
return this->str<a.str;
}
}
};
set<Ans>ans;
//最大公因数
ll gcd(ll a,ll b){
ll temp;
while(a){
temp=a;
a=b%a;
b=temp;
}
return b;
}
bool flag=false;
int tail;
void dfs(ll num,int len,ll sum,int tlen,ll tsum){
//num是当前的数字,len是当前数字长度,sum是当前数字各位之和
//printf("当前数字:%lld 长度:%d 和:%lld 目标长度:%d 目标和:%lld\n",num,len,sum,tlen,tsum);
if(len>tlen||sum>tsum){
return;
}
if(sum<tsum&&len>=tlen){
return;
}
if(sum==tsum&&len==tlen){
//存储答案
Ans temp;
temp.n=n;
temp.str=to_string(num);
for(int i=0;i<tail;i++){
temp.str+="9";
}
ans.insert(temp);
}else{
for(int i=0;i<=9;i++){
//剪枝
if((tlen-len-1)*9+sum+i<tsum)continue;
if(sum+i<=tsum){
dfs(num*10+i,len+1,sum+i,tlen,tsum);
}
}
}
return ;
}
int main(){
scanf("%d",&N);
for(int i=1;i<=N;i++){
flag=false;
scanf("%d%lld",&K,&m);
printf("Case %d\n",i);
//枚举可以末尾放9的个数
for(int tail_9=K;tail_9>=1;tail_9--){
//首先判断能否构成一个数字
int head=K-tail_9;
tail=tail_9;
if((head&&m-tail_9*9>=1&&(m-tail_9*9)/head<=9)||(head==0&&m-tail_9*9==0)){
//如果能构成一个数字的话
n=m+1-tail_9*9;
ll sum=m-tail_9*9;
if(gcd(n,m)>2){
//输出答案
if(head){
for(ll j=1;j<=9;j++){
if(j<=sum){
dfs(j,1,j,head,sum);
}
}
}else{
Ans temp;
temp.str="";
temp.n=n;
for(int c=0;c<tail;c++){
temp.str+="9";
}
ans.insert(temp);
}
flag=true;
}
}
}
if(!flag){
printf("No Solution\n");
}else{
//输出答案
//printf("答案个数%d\n",ans.size());
for(set<Ans>::iterator it=ans.begin();it!=ans.end();it++){
printf("%d %s\n",(*it).n,(*it).str.c_str());
}
}
}
return 0;
}
2.2 Merging Linked Lists
PAT和力扣最大的区别在于,输出正确即可,其实不必将链表结构实现,只需要数组替代一下,注意输出的时候对应的逻辑关系即可。
#include<bits/stdc++.h>
using namespace std;
//排序
struct Node{
int val;
int addr;
int nxt;
};
map<int,Node>nodes;
vector<Node>list1,list2,list3;
int head1,head2,n;
int addr,val,nxt;
void Merge(vector<Node>list1,vector<Node>list2){
int len1=list1.size();
int len2=list2.size();
int p1=0;
int p2=len2-1;
while(1){
if(p1<len1){
list3.push_back(list1[p1]);
}
if(p1+1<len1){
list3.push_back(list1[p1+1]);
}
if(p2>=0){
list3.push_back(list2[p2]);
}
p1+=2;
p2-=1;
if(p1>=len1&&p2<0){
break;
}
}
}
int main(){
scanf("%d%d%d",&head1,&head2,&n);
for(int i=0;i<n;i++){
scanf("%d%d%d",&addr,&val,&nxt);
nodes[addr].addr=addr;
nodes[addr].val=val;
nodes[addr].nxt=nxt;
}
//遍历,得到链表
int p=head1;
while(p!=-1){
// printf("1:%d\n",nodes[p].val);
list1.push_back(nodes[p]);
p=nodes[p].nxt;
}
p=head2;
while(p!=-1){
// printf("2:%d\n",nodes[p].val);
list2.push_back(nodes[p]);
p=nodes[p].nxt;
}
//输出结果
if(list1.size()>=2*list2.size()){
Merge(list1,list2);
}else{
Merge(list2,list1);
}
//输出答案
for(int i=0;i<list3.size();i++){
if(i){
printf("%05d\n",list3[i].addr);
}
printf("%05d %d ",list3[i].addr,list3[i].val);
}
printf("-1");
return 0;
}
2.3 Postfix Expression
这题的难点在于,对于某一个结点,如果它的值为“+”或者“-”且左节点为空,输出的时候需要特殊考虑,也就是需要将后序遍历改成前序遍历,样例中只给了“-”,所以“+”容易被忘掉(最后两个测试点)
#include<bits/stdc++.h>
using namespace std;
struct Node{
char data[12];
int left;
int right;
};
vector<Node>nodes;
vector<bool>isChild;
int n;
void postTravel(int root){
if(root==-1){
return ;
}else if((nodes[root].data[0]=='-'||nodes[root].data[0]=='+')&&strlen(nodes[root].data)==1&&nodes[root].left==-1){
printf("(");
printf("%s",nodes[root].data);
postTravel(nodes[root].left);
postTravel(nodes[root].right);
printf(")");
}else{
printf("(");
postTravel(nodes[root].left);
postTravel(nodes[root].right);
printf("%s",nodes[root].data);
printf(")");
}
}
int main(){
scanf("%d",&n);
nodes.resize(n+1);
isChild.resize(n+1);
fill(isChild.begin(),isChild.end(),false);
for(int i=1;i<=n;i++){
scanf("%s %d %d",nodes[i].data,&nodes[i].left,&nodes[i].right);
if(nodes[i].left!=-1){
isChild[nodes[i].left]=true;
}
if(nodes[i].right!=-1){
isChild[nodes[i].right]=true;
}
}
//找到根节点
int root=-1;
for(int i=1;i<=n;i++){
if(!isChild[i]){
root=i;
break;
}
}
//后序遍历
postTravel(root);
return 0;
}
2.4 Dijkstra Sequence
这题就是DIj的板子变式,对时间复杂度抓得不是很狠,需要利用给的seq去判断,四舍五入算是做了简单的剪枝,不合法的时候直接返回false
#include<bits/stdc++.h>
using namespace std;
//Dij路径
const int inf=INT_MAX;
int Nv,Ne;
vector<vector<int>>graph;
vector<int>seq;
int u,v,d;
bool isDijSeq(int st,int ed){
vector<int>dis(Nv+1,inf);
vector<bool>vis(Nv+1,false);
dis[st]=0;
int index=0;
while(1){
//printf("当前:%d 距离:%d\n",seq[index],dis[seq[index]]);
if(index>=Nv){
//printf("gameover\n");
break;
}
int u=seq[index],min_dis=dis[u];
for(int i=1;i<=Nv;i++){
if(dis[i]<min_dis&&!vis[i]){
min_dis=dis[i];
u=i;
}
}
if(u!=seq[index]){
//printf("应该是:%d\n",u);
return false;
}else{
index++;
}
vis[u]=true;
//更新
for(int v=1;v<=Nv;v++){
if(graph[u][v]!=inf&&dis[v]>=dis[u]+graph[u][v]){
dis[v]=dis[u]+graph[u][v];
}
}
}
return true;
}
int main(){
scanf("%d%d",&Nv,&Ne);
//初始化
graph.resize(Nv+1);
seq.resize(Nv);
for(int i=1;i<=Nv;i++){
graph[i].resize(Nv+1);
fill(graph[i].begin(),graph[i].end(),inf);
}
for(int i=0;i<Ne;i++){
scanf("%d%d%d",&u,&v,&d);
graph[u][v]=d;
graph[v][u]=d;
}
int q;
scanf("%d",&q);
while(q--){
for(int i=0;i<Nv;i++){
scanf("%d",&seq[i]);
}
if(isDijSeq(seq[0],seq[Nv-1])){
printf("Yes\n");
}else{
printf("No\n");
}
}
return 0;
}
3. 参考资料
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4+10;
vector<pair<int, int> > res;
int needlen, n, num9;
int now;
void dfs(int len, int sum)
{
if (len*9 < sum) return; //剪枝,加不加无所谓
if (len == 0)
{
if (sum == 0)
{
int temp = now;
for (int i = 0; i < num9; i++) temp = temp*10+9;
res.push_back(make_pair(n, temp));
}
return ;
}
if (sum < 0 || len <= 0) return ; //剪枝,加不加无所谓
for (int i = 0; i <= 9; i++)
{
if (i == 0 && len == needlen || i == 9 && len == 1) continue;
now = now*10+i;
dfs(len-1, sum-i);
now = now/10;
}
}
int main(void)
{
int i, j, temp;
int q; scanf("%d", &q);
for (j = 1; j <= q; j++)
{
printf("Case %d\n", j);
int k, m; scanf("%d%d", &k, &m);
set<int> se;
temp = m;
for (i = 2; i <= temp; i++)
{
if (temp % i == 0)
{
se.insert(i);
temp /= i;
i--;
}
}
if (*se.rbegin() <= 2)
{
printf("No Solution");
continue;
}
res.clear();
for (auto it = se.begin(); it != se.end(); ++it)
{
if (*it > 2)
{
int prime = *it;
for (i = 1; ; i++)
{
n = i*prime; if (n >= m) break;
if ((m-n-8)%9 != 0) continue;
num9 = (m-n-8)/9+1;
int len = k-num9, sum = m-num9*9; //将问题转换为长度为len, 数字和为sum的问题
needlen = len;
dfs(len, sum);
}
}
}
sort(res.begin(), res.end());
if (res.size() == 0) printf("No Solution\n");
else
{
for (i = 0; i < res.size(); i++)
{
printf("%d %d\n", res[i].first, res[i].second);
}
}
}
}