开始准备cccc(cry)天梯赛了,第一周训练题,把官网挂出的训练题刷完了,对pat有了一点点的熟悉感。
L1-1 就不说了。。。
L1-2打印沙漏
一个变量保存空格数,一个变量保存沙漏符号数,打印就行了,但这题话说wrong好几次啊,坑点是沙漏符号后面不打印空格,orz。。。
<span style="font-size:14px;">#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<vector>#include<list>#include<algorithm>using namespace std;int main(){int n;char c;scanf("%d %c",&n,&c);int a[1010];a[0] = 0;a[1] = 1;for(int i=2;i<1010;i++){a[i] = a[i-1] + (2*i - 1)*2;}int t = 0;for(;t<1010;t++){<span style="white-space:pre"></span>//找到最大一层if(n<a[t])break;}t--;int z = 0;for(int i=t;i>=1;i--){<span style="white-space:pre"></span>//打印上一半for(int j=0;j<z;j++){printf(" ");}for(int j = 0;j<(i*2-1);j++){printf("%c",c);}z++;printf("\n");}z-=2;<span style="white-space:pre"></span>//中间只有一个for(int i=2;i<=t;i++){<span style="white-space:pre"></span>//打印下一半for(int j=0;j<z;j++){printf(" ");}for(int j = 0;j<(i*2-1);j++){printf("%c",c);}z--;printf("\n");}printf("%d\n",n-a[t]);return 0;}</span>
L1-3个位数统计 取余一下就行
<span style="font-size:14px;">#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<vector>#include<list>#include<algorithm>using namespace std;int main(){int a[11];memset(a,0,sizeof(a));char n[1010];scanf("%s",n);int len = strlen(n);if(len==1&&n[0]=='0')a[0]++;while(len){a[n[--len]-'0']++;}for(int i=0;i<10;i++){if(a[i]){printf("%d:%d\n",i,a[i]);}}return 0;}</span>
L1-4计算摄氏温度
怎么感觉在凑字数。。。
<span style="font-size:14px;">#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<vector>#include<list>#include<algorithm>using namespace std;int main(){int n;scanf("%d",&n);printf("Celsius = %d\n",5*(n-32)/9);return 0;}</span>
L1-5考试座位号
hash,用了map,对应一下就行
<span style="font-size:14px;">#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<vector>#include<list>#include<algorithm>#include<map>#include<string>using namespace std;int main(){int N;scanf("%d",&N);map<int ,string>m;int c[1010];for(int i=0;i<N;i++){string n;int a,b;cin>>n>>a>>b;m[a] = n;c[a] = b;}int n;scanf("%d",&n);while(n--){int temp;scanf("%d",&temp);cout<<m[temp]<<' '<<c[temp]<<endl;}return 0;}</span>
L1-6连续因子
暴力的解法,从改数的平方根开始先前查找,当该次查找结束且长度比之前长则更新,因为从后往前扫,保证更新的数为最小
<span style="font-size:14px;">#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<vector>#include<list>#include<algorithm>using namespace std;int main(){int N;scanf("%d",&N);int n = 0;char a[1010];char temp[1010];int tn = 0;int status = 1;for(int i = (int)sqrt(N)+1;i>=2&&status;i--){tn = 0;if(N%i==0){temp[tn++] = i;int t = N/i;for(int j = i-1;j>=2;j--){if(t%j==0){temp[tn++] = j;t/=j;if(j==2){status = 0;}}else{temp[tn] = 0;break;}}if(tn>=n){strcpy(a,temp);n = tn;}}}if(n==0){printf("%d\n%d\n",n+1,N);}else{printf("%d\n",n);for(int j=n-1;j>=0;j--){printf("%d",a[j]);if(j!=0){printf("*");} else{printf("\n");}}}return 0;}</span>
L1-7念数字
字符串存储,对应即可
<span style="font-size:18px;">#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<vector>#include<list>#include<algorithm>#include<string>using namespace std;char a[10][10] = {"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};int main(){string s;cin>>s;int len = s.size();int i=0;if(s[i]=='-'){printf("fu ");i++;}for(;i<len;i++){printf("%s",a[s[i]-'0']);if(i!=len-1){printf(" ");}else{printf("\n");}}return 0;}</span><span style="font-size:24px;"></span>
L1-8求整数段和
打印数字一个变量记行,一个变量计数
求和 要考虑正数和负数
#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<vector>#include<list>#include<algorithm>using namespace std;int main(){int a,b;scanf("%d%d",&a,&b);int n = b-a+1;for(int i=0;i<n;i++){int temp = a+i;int time = 5;if(temp<=0){time--;} while(temp){time--;temp/=10;}for(int i=0;i<time;i++){printf(" ");}printf("%d",a+i);if((i+1)%5==0){printf("\n");}}if(n%5!=0){printf("\n");}if(a>=0||b<=0){printf("Sum = %d\n",(b-a+1)*(b+a)/2);}else{printf("Sum = %d\n",(b-0+1)*(b+0)/2 + (0-a+1)*(0+a)/2);}return 0;}
L2-1 紧急救援
求最短路径,使用广度优先搜索,要求输出最短路径的条数和路径。
最短路并且要求救援队的数量最多,那么使用优先队列,按照步数来进行排序,相同步数则救援队数量最多,则当广度优先搜索搜索到目的地时,求得的步数为结果,当步数大于已求得的结果,则搜索结束。
路径使用数组保存,每搜索一个点,与当前已标记的点去比较,步数最小且救援队数量最多则更新路径数组,路径输出则从D查找到S即可。
#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<vector>#include<list>#include<algorithm>#include<queue>using namespace std;int c[510];//每个城市的救援队数量int a[510][510];//存储步数int book[510];//记录路径int cunt;int step;int ttime;struct node{int c;//救援队int s;//步数int n;//当前节点int o;//前一个节点bool operator <(const node& x) const{//优先级:先排列步数,再排列救援队数目if(s==x.s){return c<x.c;}else{return s>x.s;}} };int N,M,S,D;void serach(int t);void fin();int main(){scanf("%d%d%d%d",&N,&M,&S,&D);for(int i=0;i<N;i++){scanf("%d",&c[i]);book[i] = -1;}for(int i=0;i<N;i++){for(int j=0;j<N;j++){a[i][j] = -1;//没有联通 为-1}}while(M--){int x,y,z;scanf("%d%d%d",&x,&y,&z);a[x][y] = a[y][x] = z;}step = 11111111;//最后步数结果cunt = 11111111;//最后救援队数量结果ttime = 0;//最短路径数量fin();//广搜printf("%d %d\n",ttime,cunt);serach(D);//输出路径printf("\n");return 0;}//输出路径(递归)void serach(int t){if(t==S){printf("%d",S);return ;}serach(book[t]);printf(" %d",t);}void fin(){node p;//起始点p.o = S;p.n = S;p.c = c[S];p.s = 0;priority_queue<node> q;//优先队列q.push(p);while(!q.empty()){node t = q.top();q.pop();if(book[t.n]<0){//记录路径book[t.n] = t.o;}if(t.s>step){//已求得结果,退出return ;}else if(t.n==D&&t.s==step){//最短路径计数ttime++;}else if(t.n==D){//最优路径step = t.s;ttime++;cunt = t.c;}node temp;temp.o = t.n;for(int i=0;i<N;i++){//广搜if(book[i]<0&&a[t.n][i]>=0){//未广搜且联通temp.n = i;temp.c = t.c+c[i];temp.s = t.s + a[t.n][i];q.push(temp);}}}}
L2-2 链表去重
本体借鉴feng同学思路,感谢^_^
把所有点保存,设一个标记数组,从头结点开始,若当前点值未存在,存进一个数组,否则存进另一个,最后顺序输出即可。注意输出,从第二个节点开始要输出两遍自身地址,因为前后有可能地址并不对应。
输出技巧:%05d 即可输出5位,前面补0
#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<vector>#include<list>#include<map>#include<algorithm>using namespace std;struct node{int key;int next;}a[100005];char book[10005];int o[100005];int s[100005];int on,sn;int main(){int S,N;scanf("%d%d",&S,&N);for(int i=0;i<N;i++){int p;scanf("%d",&p);scanf("%d%d",&a[p].key,&a[p].next);}sn = 0,on = 0;memset(book,0,sizeof(book));for(int i=0;i<N&&S!=-1;i++){if(!book[abs(a[S].key)]){o[on++] = S;book[abs(a[S].key)] = 1;S = a[S].next;}else{s[sn++] = S;S = a[S].next;}}if(on){for(int i=0;i<on;i++){if(i==0){printf("%05d %d",o[i],a[o[i]].key);}else{printf(" %05d\n%05d %d",o[i],o[i],a[o[i]].key);}}printf(" -1\n");}if(sn){for(int i=0;i<sn;i++){if(i==0){printf("%05d %d",s[i],a[s[i]].key);}else{printf(" %05d\n%05d %d",s[i],s[i],a[s[i]].key);}}printf(" -1\n");}return 0;}
L2-3 月饼
排下序,计算就可以了,注意精度
#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<vector>#include<list>#include<algorithm>using namespace std;struct node{double num;double mon;bool operator <(const node& x)const{return mon*x.num>num*x.mon?1:0;<span style="white-space:pre"></span>//没有用除法,把分数化成同分母比较,会减少误差}};int main(){int n;double m;node a[1010];scanf("%d%lf",&n,&m);for(int i=0;i<n;i++){scanf("%lf",&a[i].num);}for(int i=0;i<n;i++){scanf("%lf",&a[i].mon);}sort(a,a+n);double sum = 0;for(int i=0;i<n;i++){if(m==0)break;if(m>=a[i].num){//最后的错误点 ’= ’ 精度要求很高! sum += a[i].mon;m-=a[i].num;}else if(m>0&&m<a[i].num){sum += (a[i].mon*m/a[i].num);break;}}printf("%.2lf\n",sum);return 0;}
L2-4 这是二叉搜索树吗?
建树了,建一颗正常搜索树,再建一颗镜像搜索树,分别比较是否符合即可
#include<stdio.h>#include<iostream>#include<algorithm>#include<stdlib.h>using namespace std;struct node{int k;struct node* left;struct node* right;};int N;int a[1010];int tt[1010];struct node* tree1;struct node* tree2;void pos(struct node* t);void pre(struct node* t,int& x);struct node* init1(struct node* t,int v);//正常struct node* init2(struct node* t,int v);//镜像int main(){scanf("%d",&N);tree1 = tree2 = NULL;for(int i=0;i<N;i++){scanf("%d",&a[i]);tree1 = init1(tree1,a[i]);tree2 = init2(tree2,a[i]);}int x = 0;pre(tree1,x);<span style="white-space:pre"></span>//前序int status = 0;for(int i=0;i<N;i++){//比较if(tt[i]!=a[i]){status = 1;break;}}if(status){x = 0;pre(tree2,x);//后序status = 0;for(int i=0;i<N;i++){if(tt[i]!=a[i]){status = 1;break;}}if(status==0){printf("YES\n");pos(tree2);}else{printf("NO\n");}}else{printf("YES\n");pos(tree1);}return 0;}//输出路径void pos(struct node* t){if(t==NULL) return ;pos(t->left);pos(t->right);if(t==tree1||t==tree2){printf("%d\n",t->k);}else{printf("%d ",t->k);}}//前序void pre(struct node* t,int& x){if(t!=NULL&&x<N){tt[x] = t->k;x++;pre(t->left,x);pre(t->right,x);}}struct node* init1(struct node* t,int v){if(t==NULL){t = (struct node*)malloc(sizeof(struct node));t->k = v;t->left = t->right = NULL;return t;}if(v<t->k){t->left = init1(t->left,v);}else{t->right = init1(t->right,v);}return t;}struct node* init2(struct node* t,int v){if(t==NULL){t = (struct node*)malloc(sizeof(struct node));t->k = v;t->left = t->right = NULL;return t;}if(v>=t->k){t->left = init2(t->left,v);}else{t->right = init2(t->right,v);}return t;}
L3-1 凑零钱
普通01背包,装满背包,dp[]中保存用的零钱个数,零钱用的越多,肯定数最小,我排了下序,好像不排序也可以
dfs强剪枝也可以
#include<stdio.h>#include<iostream>#include<algorithm>#include<string.h>using namespace std;int book[110];<span style="white-space:pre"></span>//路径int v[110];<span style="white-space:pre"></span>//用于路径中比较值void input(int x);//输出,我起错名了。。。int main(){int N,M;int a[10010];scanf("%d%d",&N,&M);for(int i=0;i<N;i++){scanf("%d",&a[i]);}int dp[110];sort(a,a+N);for(int i=0;i<=M;i++){dp[i] = -0x3f3f3f3f;<span style="white-space:pre"></span>//注意装满应该为无穷小book[i] = -1;}dp[0] = 0;for(int i=0;i<N;i++){for(int j=M;j>=a[i];j--){if(dp[j]<=dp[j-a[i]]+1){dp[j] = dp[j-a[i]]+1;book[j] = j-a[i];v[j] = a[i];}}}if(dp[M]>0){input(M);printf("\n");}else{printf("No Solution\n");}return 0;}void input(int x){if(book[x]==0){printf("%d",v[x]);return ;}input(book[x]);printf(" %d",v[x]);}
L3-2 堆栈
单点更新查询,用线段树,保存本区间内的点数
#include<stdio.h>#include<iostream>#include<algorithm>#include<string.h>#include<stack>#define lson l,m,level*2#define rson m+1,r,level*2+1using namespace std;int a[100010];int tree[100010*5];void init(int l,int r,int level);void find(int l,int r,int level,int x);void update(int l,int r,int level,int x,int s);int main(){int N;scanf("%d",&N);stack<int>s;getchar();int mmax = 100002;memset(a,0,sizeof(a));memset(tree,0,sizeof(tree));//init(1,100000,1);while(N--){char c[30];int num;scanf("%s",c);if(!strcmp(c,"Pop")){if(!s.empty()){printf("%d\n",s.top());update(1,mmax,1,s.top(),0);a[s.top()]--;s.pop();}else{printf("Invalid\n");}}else if(!strcmp(c,"PeekMedian")){int n = s.size();if(n>0){if(n%2==1){<span style="white-space:pre"></span>//注意奇偶数n++;}find(1,mmax,1,n/2);}else{printf("Invalid\n");}}else if(!strcmp(c,"Push")){scanf("%d",&num);s.push(num);a[num]++;if(mmax<num){//这里mmax会出错(应该是线段树的N是确定的,而不是不确定的,memory) mmax = num;}update(1,mmax,1,num,1);}}}void update(int l,int r,int level,int x,int b){if(l==r&&x==l){if(b==0)tree[level]--;elsetree[level]++;return ;}int m = (l+r)>>1;if(x<=m){update(lson,x,b);}else{update(rson,x,b);}tree[level] = tree[level*2+1] + tree[level*2];}void find(int l,int r,int level,int x){if(l==r&&(x<=tree[level])){printf("%d\n",l);return ;}int m = (l+r)>>1;if(tree[level*2]>=x){find(lson,x);}else{find(rson,(x-tree[level*2]));}}void init(int l,int r,int level){if(l==r){tree[level] = a[l];return ;}int m = (l+r)>>1;init(lson);init(rson);tree[level] = tree[level*2] + tree[level*2+1];}
L3-3 社交集群
vector数组为活动号,保存选择该活动的人员编号。从第一个人i开始查找,所有和本人在同一活动中的人全部入队,并标记上i,并对队的每个人进行相同查找,直到队空。i++,在进行下一个没有查找过的人的查找到结束。
最后计算标记数组中共出现的标号和数量,排序输出。
#include<iostream>#include<stdio.h>#include<math.h>#include<string.h>#include<vector>#include<queue>#include<algorithm>using namespace std;vector <int >a[1010];int main(){int N;scanf("%d",&N);int mmax = 0;for(int i=1;i<=N;i++){int n;scanf("%d:",&n);for(int j=0;j<n;j++){int num;scanf("%d",&num);if(mmax<num){mmax = num;}a[num].push_back(i); }}int x[1010],y[1010];//x:person y:problemmemset(x,0,sizeof(x));memset(y,0,sizeof(y));for(int i=1;i<=N;i++){//renif(!x[i]){x[i] = i;queue<int>q;q.push(i);while(!q.empty()){int p = q.front();q.pop();for(int j=0;j<=mmax;j++){if(a[j].size()!=0&&!y[j]&&find(a[j].begin(),a[j].end(),p)!=a[j].end()){y[j] = 1;for(int k=0;k<a[j].size();k++){if(!x[a[j][k]]){x[a[j][k]] = i;q.push(a[j][k]);}}}}}}}int c[1100];memset(c,0,sizeof(c));for(int i=1;i<=N;i++){c[x[i]]++;}sort(c,c+N+10,greater<int>());int time = 0;for(int i=0;c[i];i++){time++;}printf("%d\n",time);if(time){printf("%d",c[0]);for(int i=1;c[i];i++){printf(" %d",c[i]);}printf("\n");}return 0;}