PAT 刷题代码

patcodes.md
//B1001 #include <iostream> using namespace std; int main(){ int n; cin>>n; for (int i = 0; i<1000000000; i++){ if (n == 1){ cout<<'0'<<endl; return 0; } else{ if(n%2 == 0){ n = n * 0.5; } else{ n = (3 * n+1)*0.5; }; if (n==1){ cout<<i+1<<endl; return 0; } } } }
//B1002 # include <stdio.h> # include <iostream> # include <string> using namespace std; int main(){ string n; cin>>n; int sum = 0; for (int i=0;i<int(n.size());i++){ sum += n[i] - '0'; } // cout<<sum; string sum1 = to_string(sum); for (int i = 0; i< int(sum1.size());i++){ if (sum1[i] == '0') cout<<"ling"; if (sum1[i] == '1') cout<<"yi"; if (sum1[i] == '2') cout<<"er"; if (sum1[i] == '3') cout<<"san"; if (sum1[i] == '4') cout<<"si"; if (sum1[i] == '5') cout<<"wu"; if (sum1[i] == '6') cout<<"liu"; if (sum1[i] == '7') cout<<"qi"; if (sum1[i] == '8') cout<<"ba"; if (sum1[i] == '9') cout<<"jiu"; if (i != int(sum1.size())-1) cout<<" "; } return 0; }
//B1003 # include <stdio.h> # include <iostream> # include <string> using namespace std; int substr(string a){ int pexist = 0,ppos = 0; for (int i = 0;i<a.size();i++){ if (a[i] == 'P'){ pexist = 1; ppos = i; } if (pexist == 1 && a[i] == 'T' && i > ppos+1){ for (int j = 0;j<a.size();j++){ if (a[j]!= 'P' && a[j]!= 'A' && a[j]!= 'T'){ return 0; } } return 1; } } return 0; } int judge(string n){ if (substr(n) == 1){ int ppos = n.find('P'); int tpos = n.find('T'); // cout<<ppos<<' '<<tpos-ppos-1<<' '<<n.size()-tpos-1<<' '; if (ppos*(tpos-ppos-1)==n.size()-tpos-1){ cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } } else{ cout<<"NO"<<endl; } return 0; } int main(){ int num; cin>>num; string n[num]; for (int i = 0;i<num;i++){ cin>>n[i]; } for (int i = 0;i<num;i++){ judge(n[i]); } }
//B1003 # include <stdio.h> # include <iostream> # include <string> using namespace std; int main(){ int num; cin>>num; string n[num*2]; int score[num]; int count = 0; for (int i = 0;i<num*3;i++){ if (i%3 == 2){ cin>>score[(i-2)/3]; } else{ cin>>n[count++]; } } int max,min,maxpos,minpos; max = min = score[0]; maxpos = minpos = 0; for (int i = 0;i<num;i++){ if (score[i]>max){ max = score[i]; maxpos = i; } if (score[i]<min){ min = score[i]; minpos = i; } } cout<<n[maxpos * 2]<<' '<<n[maxpos * 2+1]<<endl; cout<<n[minpos * 2]<<' '<<n[minpos * 2+1]<<endl; }
//B1005 #include <iostream> #include <algorithm> using namespace std; int findanddel(int num[], int j,int n){ for (int i = 0;i<n;i++){ if (num[i] == j){ num[i] = 1; } } return 0; } int main(){ int n; cin>>n; int num[n]; for (int i = 0;i<n;i++){ cin>>num[i]; } for (int i = 0;i<n;i++){ int k = num[i]; while(k!=1){ if (k%2 == 0){ k = k/2; findanddel(num,k,n); } else{ k = (k*3+1)/2; findanddel(num,k,n); } } } sort(num,num + n); for (int i = n-1;i>=0;i--){ if (num[i] == 1) break; else if (i!=n-1) cout<<' '; cout<<num[i]; } return 0; }
//B1006 #include <iostream> #include <algorithm> using namespace std; int main(){ int n; cin>>n; int a[3]; for(int i = 0;i<3;i++){ a[i] = n%10; n = n/10; } for (int i = 0; i<a[2]; i++){ cout<<'B'; } for (int i = 0; i<a[1]; i++){ cout<<'S'; } int count = 0; for (int i = 0; i<a[0]; i++){ cout<<++count; } return 0; }
//B1007 #include <iostream> #include <algorithm> #include <vector> #include <math.h> using namespace std; int min(int a,int b){ if(a<b)return a; else return b; } int main(){ int n; cin>>n; vector <int> su; su.push_back(2); for (int i = 2;i<n+1;i++){ int judge = 1; for (int j = 0; j<su.size();j++){ if (i%su[j] == 0){ judge = 0; } if (su[j] > sqrt(n)) break; } if (judge == 1){ su.push_back(i); } } // for (int i = 0;i<su.size();i++){ // cout<<su[i]<<' '; // } int count = 0; for (int i = 1;i<su.size();i++){ if(su[i]>n)break; if(su[i]-su[i-1]==2){ count++; } } cout<<count; return 0; }
//B1008 我觉得题解的做法就是有病…… #include <iostream> #include <algorithm> #include <vector> #include <math.h> using namespace std; int main(){ int n,m; cin>>n>>m; int num[n]; for (int i = 0;i<n;i++){ cin>>num[i]; } for (int i = 0;i<n;i++){ cout<<num[(i-m+n*100)%n]; if (i!=n-1) cout<<' '; } return 0; }
//B1009 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <sstream> using namespace std; int main(){ string str; getline(cin,str); // cout<<str; str = str+" "; vector<string> strSplit; vector<char>s; for (int i = 0;i<str.size()+1;i++){ // for (int j = 0;j<s.size();j++){ // cout<<s[j]; // } if (str[i]!=' '&&i!=str.size()) s.push_back(str[i]); else { string a; for (int j = 0;j<s.size();j++){ a = a+s[j]; // cout<<s[j]; } s.clear(); strSplit.push_back(a); } } for (int i = 1;i<strSplit.size();i++){ if(i!=strSplit.size()-1) cout<<strSplit[strSplit.size()-i-1]<<" "; else cout<<strSplit[strSplit.size()-i-1]; } return 0; }
//B1010 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> using namespace std; int main(){ // cout<<"Enter Please"<<endl; int tmp; vector<int>num; vector<int>num2; while(cin>>tmp){ if(tmp == 0) { cout<<"0 0"; return 0; } num.push_back(tmp); cin>>tmp; num2.push_back(tmp); if(tmp == 0) break; } // cout<<num2.size()<<endl; // for(int i = 0;i<num.size();i++){ // cout<<num[i]; // } // cout<<'\n'; for(int i = 0;i<int(num2.size());i++){ if (num2[i] == 0 && i == 0) { cout<<"0 0"; break; } if (num2[i]>0) cout<<num2[i]*num[i]<<' '<<num2[i]-1; if (i!=int(num2.size()-1) && num2[i+1]!=0) cout<<' '; // cout<<'E'<<num2[i]; } return 0; }
//B1011 大数相加u模板 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> using namespace std; int cmp(string a, string b){ if(a.size()>b.size()) return 1; else if(a.size()<b.size()) return -1; else { for (int i = 0;i<a.size();i++){ if (a[i]!=b[i]){ if (a[i]>b[i]) return 1; if (a[i]<b[i]) return -1; } } return 0; } } string add2(string a,string b){ if (a == "0") return b; if (b == "0") return a; string c; reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); string a1(32-a.size(),'0'); string b1(32-b.size(),'0'); a = a + a1; b = b + b1; int jinwei = 0; for (int i = 0;i<32;i++){ char tmp; tmp = a[i]+b[i]-48+jinwei; if (tmp>'9'){ tmp -= 10; jinwei = 1; } else jinwei = 0; c += tmp; } reverse(c.begin(), c.end()); int j = 0; string d; for(int i = 0;i<c.size();i++){ if (c[i]!='0') j=1; if (j==1) d += c[i]; } return d; } string abs(string a){ if (a[0] != '-') return a; else { string b; for (int i = 1;i<a.size();i++){ b += a[i]; } return b; } } string sub2(string a,string b){ string c; reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); string a1(32-a.size(),'0'); string b1(32-b.size(),'0'); a = a + a1; b = b + b1; // cout<<a<<' '<<b<<endl; int jinwei = 0; for (int i = 0;i<32;i++){ char tmp; tmp = a[i]-b[i]+48-jinwei; if (tmp<'0'){ tmp += 10; jinwei = 1; } else jinwei = 0; c += tmp; } reverse(c.begin(), c.end()); int j = 0; string d; for(int i = 0;i<c.size();i++){ if (c[i]!='0') j=1; if (j==1) d += c[i]; } return d; } string sub(string a,string b){ if (a== "0") { if (abs(b) == b) return "-"+abs(b); else return abs(b); } if (b == "0") return a; int big = cmp(abs(a), abs(b)); if (big == 0) return "0"; else if (big == 1){ if (abs(a)==a && abs(b)==b) return sub2(a,b); else if (abs(a)!=a && abs(b)==b) return "-"+add2(abs(a),b); else if (abs(a)==a && abs(b)!=b) return add2(a,abs(b)); else return "-"+sub2(abs(a),abs(b)); } else { if (abs(a)==a && abs(b)==b) return "-"+sub2(b,a); else if (abs(a)!=a && abs(b)==b) return sub2(b,abs(a)); else if (abs(a)==a && abs(b)!=b) return sub2(abs(b),a); else return sub2(abs(b),abs(a)); } return "0"; } string add(string a,string b){ if (a[0] == '-' && b[0] == '-') return "-"+add2(abs(a), abs(b)); else if (a[0] != '-' && b[0] == '-') return sub(a,abs(b)); else if (a[0] == '-' && b[0] != '-') return sub(b,abs(a)); else return add2(abs(a), abs(b)); } string judge(string a,string b,string c){ // cout<<add(a,b)<<endl; string result = sub(add(a,b),c); // cout<<result<<" "; if (result[0] == '-' || result == "0" ) return "false"; else return "true"; // return result; } string output(string a,string b,string c,int num){ return "Case #" + to_string(num) + ": "+judge(a,b,c); } int main(){ // cout<<"Enter Please"<<endl; int n; cin>>n; string a[n],b[n],c[n]; if (n!=0){ for (int i=0;i<n;i++){ cin>>a[i]>>b[i]>>c[i]; } for (int i=0;i<n;i++){ cout<<output(a[i],b[i],c[i],i+1)<<endl; } } return 0; } int main1(){ string a,b,c; cin>>a>>b>>c; string result = sub(add(a,b),c); cout<<result<<" "<<output(a,b,c,1)<<endl; return 0; }
//B1012 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ cout<<"Enter Please"<<endl; int n; cin>>n; int num[n]; for (int i = 0;i<n;i++){ cin>>num[i]; } int a1,a2,a3,a5; float a4 = 0.0; a1 = a2 = a3 = a5 =0; int count4 = 0; int count2 = 1; int judge2 = 0; for (int i = 0;i<n;i++){ if (num[i] % 10 == 0) a1 += num[i]; if (num[i] % 5 == 1) { judge2 = 1; a2 += count2 * num[i]; count2 = count2 * (-1); } if (num[i] % 5 == 2) a3 += 1; if (num[i] % 5 == 3) { a4 += num[i]; count4 +=1; } if (num[i] % 5 == 4) { if (a5<num[i]) a5 = num[i]; } } a4 = a4/count4; string a11=a1>0?to_string(a1):"N"; string a21=judge2 == 1?to_string(a2):"N"; string a31=a3>0?to_string(a3):"N"; string a51=a5>0?to_string(a5):"N"; // int a11 = a1; // int a21 = a2; // int a31 = a3; // int a51 = a5; if (a4 >0){ cout<<a11<<' '<<a21<<' '<<a31<<' '<<fixed<<setprecision(1)<<a4<<' '<<a51; } else{ cout<<a11<<' '<<a21<<' '<<a31<<' '<<'N'<<' '<<a51; } return 0; }
//B1013 朴素方法 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int m,n; cin>>m>>n; vector <int> su; su.push_back(2); int i = 1; while(su.size()<n+1){ i++; int judge = 1; for (int j = 0; j<su.size();j++){ if (i%su[j] == 0){ judge = 0; } if (su[j] > sqrt(i)) break; } if (judge == 1){ su.push_back(i); } } for (int i = m-1;i<su.size()-1;i++){ cout<<su[i]; if ((i-m+2)%10 == 0 && i != su.size()-2)cout<<endl; else if (i != su.size()-2) cout<<' '; else break; } return 0; }
//B1013 $ 1/7 格式! #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; const int MAXN=10000000; int prime[MAXN];//保存素数 bool vis[MAXN] = {0};//初始化 int Prime(int n,int m) { int cnt=0; for(int i=2;i<n;i++) { if(!vis[i]) prime[cnt++]=i; for(int j=0;j<cnt&&i*prime[j]<n;j++) { vis[i*prime[j]]=1; if(i%prime[j]==0)//关键 break; } if (cnt>m)break; } return cnt;//返回小于n的素数的个数 } int main(){ int m,n,count = 0; cin>>m>>n; Prime(10000000,n+5); for(int i = 0;count<n+2;i++){ if(vis[i] == 0){ if (count>m) { printf("%d",i); if ((count-m)%10 == 0)printf("\n"); else if (count!=n+1)printf(" "); } count++; } } return 0; }
//B1014/A1061 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; unsigned long int cmp(string a,string b){ if (a.size()>b.size()) return b.size(); else return a.size(); } int main(){ string a,b,c,d; cin>>a>>b>>c>>d; char day,hour; int minute = 0; int count = 0; for (int i = 0;i<cmp(a,b);i++){ if (a[i] == b[i] && a[i]>='A' && a[i]<='G' && count == 0) { day = a[i]; count++; continue; } if (a[i] == b[i] && a[i]>='A' && a[i]<='N' && count == 1) { hour = a[i]; count++; break; } if (a[i] == b[i] && a[i]>='0' && a[i]<='9' && count == 1) { hour = a[i]; count++; break; } } for (int i = 0;i<cmp(c,d);i++){ if (c[i] == d[i] && c[i]>='A' && c[i]<='Z') { minute = i; break; } if (c[i] == d[i] && c[i]>='a' && c[i]<='z') { minute = i; break; } } // cout<<day<<hour<<minute<<endl; if (day == 'A') cout<<"MON "; if (day == 'B') cout<<"TUE "; if (day == 'C') cout<<"WED "; if (day == 'D') cout<<"THU "; if (day == 'E') cout<<"FRI "; if (day == 'F') cout<<"SAT "; if (day == 'G') cout<<"SUN "; if (hour >='A') cout<<hour-'A'+10<<':'<<setfill('0')<<setw(2)<<minute; else cout<<setfill('0')<<setw(2)<<hour<<':'<<setfill('0')<<setw(2)<<minute; return 0; }
//B1015/A1062 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; typedef struct{ int id,d,c,sgn,total; } student; bool cmp(student a,student b) { //'>'降序排序 //'<'升序排序 if(a.sgn!=b.sgn)return a.sgn<b.sgn; else if(a.total!=b.total)return a.total>b.total; else if(a.d!=b.d)return a.d>b.d; else return a.id<b.id; // 这里的if-else太妙了 //NOTE3 } int main(){ int num,l,h; cin>>num>>l>>h; student students[num]; for (int i = 0;i<num;i++){ cin>>students[i].id>>students[i].d>>students[i].c; } int failcount = 0; for (int i = 0;i<num;i++){ students[i].total = students[i].d + students[i].c; if (students[i].d>=h && students[i].c>=h) students[i].sgn = 0; else if (students[i].d>=h && students[i].c<h && students[i].c>=l) { students[i].sgn = 1;} else if (students[i].c>=l && students[i].d>=l && students[i].d>=students[i].c) students[i].sgn = 2; else if (students[i].c>=l && students[i].d>=l) students[i].sgn = 3; else { students[i].sgn = 4; failcount ++; } } sort(students, students+num, cmp); student tmp; for (int j = 0;j<num;j++) { if (students[j].c == students[j+1].c && students[j].d == students[j+1].d && students[j].id > students[j+1].id ){ tmp = students[j]; students[j] = students[j+1]; students[j+1] = tmp; } } cout<<num-failcount<<endl; for (int j = 0;j<num-failcount;j++) { // cout<<students[j].id<<" "<<students[j].d<<" "<<students[j].c<<" "<<students[j].sgn<<" "<<students[j].total<<endl;; cout<<students[j].id<<" "<<students[j].d<<" "<<students[j].c<<endl;; } return 0; }
//B1017 $ 编译错误 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <cstring> #include <sstream> #include <iomanip> #include <stdio.h> #include <stdlib.h> using namespace std; struct bign{ int len; int d[1000]; bign(){ len = 0; memset(d,0,sizeof(d)); } }; bign convert1(string n){ bign a; for(int i = 0;i<n.size();i++){ a.d[a.len++] = (int)(n[n.size()-1-i]-'0'); } return a; } bign devide(bign a,int b,int &r){ bign q; r = 0; q.len = a.len; for(int i = a.len-1;i>=0;i--){ r = 10 * r + a.d[i]; if (r<b) q.d[i] = 0; else { q.d[i] = r/b; r = r%b; } } while (q.len >= 2 && q.d[q.len-1] == 0){q.len--;} return q; } int main(){ string n; cin>>n; int b,r=0; scanf("%d",&b); bign q = devide(convert1(n),b,r); // printf("%d\n",q.len); for(int i = 0;i<q.len;i++){ printf("%d",q.d[q.len-1-i]); } printf(" %d",r); return 0; }
//B1019/A1069 $6/7 直接输入6174的忘记考虑了 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int n; scanf("%d",&n); int a[4]; int a1,a2,judge = 0; while((n!=6174 && n!= 0) || (n==6174 && judge == 0)){ judge = 1; a[0] = n/1000; a[1] = (n-a[0]*1000)/100; a[2] = (n-a[0]*1000-a[1]*100)/10; a[3] = n%10; sort(a,a+4); a1 = a[3] + a[2] * 10 + a[1] * 100 + a[0] * 1000; a2 = a[0] + a[1] * 10 + a[2] * 100 + a[3] * 1000; n = a2-a1; printf("%04d - %04d = %04d\n",a2,a1,n); } return 0; }
//B1020 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; typedef struct{ double amount,totalprice; } moon; bool cmp(moon a,moon b){ return (a.totalprice/a.amount)>(b.totalprice/b.amount); } int main(){ int n; double d,money; cin>>n>>d; vector<moon>mooncake; mooncake.resize(n); for(int i = 0;i<n;i++){scanf("%lf",&mooncake[i].amount);} for(int i = 0;i<n;i++){scanf("%lf",&mooncake[i].totalprice);} sort(mooncake.begin(),mooncake.end(),cmp); for(int i = 0;i<n;i++){ if (d>mooncake[i].amount){d -=mooncake[i].amount;money+=mooncake[i].totalprice;} else{ money+=mooncake[i].totalprice/mooncake[i].amount * d; break; } } printf("%.2lf",money); return 0; }
//B1021 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ string k; cin>>k; int rst[10] = {}; for(int i = 0;i<k.size();i++){ rst[int(k[i]-'0')]++; } for(int i = 0;i<10;i++){ if (rst[i]>0)cout<<i<<":"<<rst[i]<<endl; } return 0; }
//B1022 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int a,b,c,d; vector<int>result; cin>>a>>b>>d; c = a + b; while (c/d > 0){ result.push_back(c-d*(c/d)); c = (c-c%d)/d; } result.push_back(c); for (int i = result.size()-1;i>-1;i--){ cout<<result[i]; } return 0; }
//B1023 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int num[10]; for(int i = 0;i<10;i++){scanf("%d",&num[i]);} for(int i = 1;i<10;i++){ if (num[i]>0){cout<<i;num[i]-=1;break;} } for(int i = 0;i<10;i++){ while(num[i]>0){cout<<i;num[i]-=1;} } return 0; }
//B1024/A1073 这个是计算出来的,大数便不行了 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ double num[2]; string input; cin>>input; int pose = 0; for(int i = 1;i<input.size();i++){ if(input[i]=='E') { pose = i; break; } } num[0] = 10*(input[1]-'0'); for(int i = 3;i<pose;i++){ num[0]+=input[i]-'0'; num[0] = num[0]*10; } long long a = (long long)num[0]/10; //main part for(int i = pose+2;i<input.size();i++){ num[1]+=input[i]-'0'; num[1] = num[1]*10; } int b = (int)num[1]/10; //^b // cout<<a<<' '<<b<<endl; if (input[0] == '-') cout<<'-'; if (input[pose+1] == '-'){ cout<<"0."; for(int i = 0;i<b-1;i++){cout<<'0';} cout<<a;} else{ if (b>=(to_string(a).size())-1) cout<<fixed<<setprecision(0)<<a*pow(10, b-(to_string(a).size())+1); else{ for(int i = 0;i<b+1;i++){ cout<<to_string(a)[i]; } cout<<'.'; for(int i = b+1;i<to_string(a).size();i++){ cout<<to_string(a)[i]; } } } return 0; }
//B1024/A1073 这个是字符串折腾出来的 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ double num[2]; string input; cin>>input; int pose = 0; for(int i = 1;i<input.size();i++){ if(input[i]=='E') { pose = i; break; } } vector<char>nums; nums.push_back(input[1]); for(int i = 3;i<pose;i++){ nums.push_back(input[i]); } for(int i = pose+2;i<input.size();i++){ num[1]+=input[i]-'0'; num[1] = num[1]*10; } int b = (int)num[1]/10; //^b if (input[0] == '-') cout<<'-'; if (input[pose+1]=='+'){ if (nums.size()<=b+1){ //这里“=”是大坑,否则会输出“35.” for(int i = 0;i<nums.size();i++){ cout<<nums[i]; } for(int i = 0;i<b+1-nums.size();i++){ cout<<0; } } else{ for(int i = 0;i<b+1;i++){ cout<<nums[i]; } cout<<'.'; for(int i = b+1;i<nums.size();i++){ cout<<nums[i]; } } } else{ cout<<"0."; for(int i = 0;i<b-1;i++){ cout<<0; } for(int i = 0;i<nums.size();i++){ cout<<nums[i]; } } return 0; }
//B1025/A1074 $ 4/7 #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <vector> using namespace std; struct node{ int key; int next,add; }; int main(){ int head,n,k; scanf("%d %d %d",&head,&n,&k); int key,add,next; node a[100010]; for(int i = 0;i<n;i++){ scanf("%d %d %d",&add,&key,&next); a[add].key = key; a[add].add = add; a[add].next = next; } vector <vector<int>> seq; int p = head; for(int i = 0;i<n && p!=-1 ;i++){ // 注意会有无效节点! vector <int> temp(2); seq.push_back(temp); seq[i][0] = a[p].key; seq[i][1] = a[p].add; p = a[p].next; } for (int i = 0;i<seq.size()-k+1;i+=k){ // 这个+1 影响了测试点1&2 reverse(seq.begin()+i, seq.begin()+i+k); } for(int i = 0;i<seq.size()-1;i++){ printf("%05d %d %05d\n",seq[i][1],seq[i][0],seq[i+1][1]); } int m = (int)seq.size(); printf("%05d %d %d\n",seq[m-1][1],seq[m-1][0],-1); return 0; } //00100 6 5 //00000 4 99999 //00100 1 12309 //68237 6 -1 //33218 3 00000 //99999 5 68237 //12309 2 33218 //00000 6 3 //00000 1 11111 //11111 2 22222 //22222 3 -1 //33333 4 44444 //44444 5 55555 //55555 6 -1
//B1027 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int n; char a; cin>>n>>a; if (n == 1){ cout<<a<<endl<<0; return 0; } int m = sqrt((n+1)/2); int left = n+1-2*m*m; for (int i = m;i>1;i--){ for (int j = 0;j<m-i;j++){ cout<<' '; } for (int j =0;j<2*i-1;j++){ cout<<a; } cout<<endl;; } for (int j = 0;j<m-1;j++){ cout<<' '; } cout<<a<<endl; for (int i = 2;i<m+1;i++){ for (int j = 0;j<m-i;j++){ cout<<' '; } for (int j =0;j<2*i-1;j++){ cout<<a; } cout<<endl;; } cout<<left; return 0; }
//B1028 TODO 4/5 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; typedef struct{ char name[20]; int date; } man; bool cmp(man a,man b) { return a.date<b.date; } int main(){ int n; cin>>n; man people[n]; int a,b,c; for (int i = 0;i<n;i++){ scanf("%s %d/%d/%d" ,people[i].name,&a,&b,&c); people[i].date = a*10000+b*100+c; } sort(people, people+n,cmp); // for (int i = 0;i<n;i++){ // cout<<people[i].name<<' '<<people[i].date<<endl; // } int max = 0,min = n-1; for(int i = 0;i<n;i++){ if (i == 0) { if (people[0].date>18140905) max = 0;} else{ if (people[i].date>18140905 && people[i-1].date<=18140905) max = i; //测试点2 if (people[i-1].date<=20140906 && people[i].date>20140906) min = i-1; //测试点1 } } cout<<min-max+1<<' '<<people[max].name<<' '<<people[min].name; return 0; }
//B1029/A1084 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> //strlen #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ char a[1000],b[1000]; int hashtable[128] = {}; // NOTE9 所有东西的初始化不能忘! scanf("%s %s",b,a); int lena = (int)strlen(a); //NOTE8 取char长度,要#include <cstring> int lenb = (int)strlen(b); for(int i = 0;i<lena;i++){ // if (a[i] == '\0')break; if (a[i]>='A' && a[i]<='Z')hashtable[a[i]-'A']+=1; else if (a[i]>='a' && a[i]<='z')hashtable[a[i]-'a']+=1; else if (a[i]>='0' && a[i]<='9')hashtable[a[i]-'0'+26]+=1; else if (a[i]=='_')hashtable[36]+=1; } for(int i = 0;i<lenb;i++){ // if (b[i] == '\0')break; int t = 0; if (b[i]>='A' && b[i]<='Z')t=b[i]-'A'; else if (b[i]>='a' && b[i]<='z')t=b[i]-'a'; else if (b[i]>='0' && b[i]<='9')t=b[i]-'0'+26; else if (b[i]=='_')t=36; if (hashtable[t]==0) { if (b[i]>='a' && b[i]<='z')cout<<(char)(b[i]-'a'+'A'); else cout<<b[i]; hashtable[t]+=1;} } return 0; }
//B1030/A1085 二分算法 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int n,p,max = 0,tmp = 1; long long maxnum = 0; cin>>n>>p; vector<long long>a; a.resize(n); for(int i = 0;i<n;i++){scanf("%lld",&a[i]);} sort(a.begin(),a.end()); for(int i = 0;i<n;i++){ maxnum = a[i] * p; tmp = (int)(upper_bound(a.begin()+i+1, a.end(), (long long)a[i] * p) - a.begin() - i); if (max < tmp){ max = tmp; } } cout<<max; return 0; }
//B1030/A1085 TwoPointer #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int n,p,max = 1; cin>>n>>p; vector<long long>a; a.resize(n); for(int i = 0;i<n;i++){scanf("%lld",&a[i]);} sort(a.begin(),a.end()); int maxpos = 0; for(int i = 0;i<n;i++){ while(a[maxpos]<=(long long)a[i]*p && maxpos<n){ if(maxpos>=n)break; if(maxpos-i+1>=max)max = maxpos - i+1; maxpos++; } } cout<<max; return 0; }
//B1031 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int n; int judge = 0; cin>>n; const int num = n; int weight[17] = {7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2}; char id[num][19]; //NOTE2 for(int i = 0;i<num;i++){ scanf("%s",id[i]); id[i][18] = '0'; } for(int i = 0;i<n;i++){ int sum = 0; for(int j = 0;j<17;j++){ if (id[i][j]>='0'&& id[i][j]<='9'){ sum += weight[j]*(int)(id[i][j]-'0'); } else { id[i][18] = '1'; break; } } // cout<<i<<"sum="<<sum<<endl; if ( (sum%11 == 0&&id[i][17] == '1' ) || (sum%11 == 1&&id[i][17] == '0' ) || (sum%11 == 2&&id[i][17] == 'X' ) || (sum%11 == 3&&id[i][17] == '9' ) || (sum%11 == 4&&id[i][17] == '8' ) || (sum%11 == 5&&id[i][17] == '7' ) || (sum%11 == 6&&id[i][17] == '6' ) || (sum%11 == 7&&id[i][17] == '5' ) || (sum%11 == 8&&id[i][17] == '4' ) || (sum%11 == 9&&id[i][17] == '3' ) || (sum%11 == 10&&id[i][17] == '2' ) ) { // cout<<sum%11<<' '<<id[i][17]<<endl;; continue;} else { id[i][18] = '1'; } } for(int i = 0;i<num;i++){ if (id[i][18]=='1') { judge = 1; for (int j=0;j<18;j++){ cout<<id[i][j]; } cout<<endl; } else continue; } if (judge == 0) {cout<<"All passed";return 0;} else return 0; }
//B1032 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int n; cin>>n; int a[100000] = {}; int b,c; for (int i = 0;i<n;i++){ cin>>b>>c; a[b]+=c; } int max = 0,pos = 0; for (int i = 0;i<100000;i++){ if(max<a[i]) { max = a[i]; pos = i; } } cout<<pos<<' '<<a[pos]; return 0; }
//B1033 TODO 3/5 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> //strlen #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ char a[1000],b[1000]; bool hashtable[128] = {0}; hashtable[50]=false; scanf("%s %s",a,b); int lena = (int)strlen(a); int lenb = (int)strlen(b); for(int i = 0;i<lena;i++){ if (a[i]>='A' && a[i]<='Z'){ hashtable[a[i]-'A']=true;} else if (a[i]>='a' && a[i]<='z')hashtable[a[i]-'a']=true; else if (a[i]>='0' && a[i]<='9')hashtable[a[i]-'0'+26]=true; else if (a[i]=='_')hashtable[36]=true; else if (a[i]==',')hashtable[37]=true; else if (a[i]=='.')hashtable[38]=true; else if (a[i]=='-')hashtable[39]=true; else if (a[i]=='+')hashtable[40]=true; } for(int i = 0;i<lenb;i++){ int t = 0,shift = 1; if (b[i]>='A' && b[i]<='Z'){t=b[i]-'A';shift = 0;} else if (b[i]>='a' && b[i]<='z')t=b[i]-'a'; else if (b[i]>='0' && b[i]<='9')t=b[i]-'0'+26; else if (b[i]=='_')t=36; else if (b[i]==',')t=37; else if (b[i]=='.')t=38; else if (b[i]=='-')t=39; else if (b[i]=='+')t=40; // cout<<t<<' '<<hashtable[t]<<' '<<shift<<' '<<hashtable[40]<<' '; // cout<<b[i]<<endl; if (hashtable[t]==false) { if (hashtable[40] == true && b[i]>='A' && b[i]<='Z'){ continue; } else cout<<b[i]; } } return 0; }
//B1034/A1088 $ 2/4 分数四则运算模板 // 测试点2 是 long long 的原因 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> typedef long long LL; using namespace std; typedef struct{ LL up,down; } fractionnum; LL maxfactor(LL a,LL b){ a = abs(a); // !! if (b!= 0) return maxfactor(b, a%b); else return a; } fractionnum yue(fractionnum a){ if (a.up == 0){a.down = 1;return a;} if (a.down < 0){a.down = -a.down;a.up = -a.up;} long long max = maxfactor(a.down, a.up); if (max == a.down){ a.up = a.up/a.down; a.down = 1; } else if (max > 1){ a.up = a.up/max; a.down = a.down/max; } return a; } fractionnum pluss(fractionnum a,fractionnum b){ fractionnum temp; temp.down = a.down * b.down; temp.up = a.up * b.down + a.down * b.up; return yue(temp); } fractionnum minuss(fractionnum a,fractionnum b){ b.up = -1 * b.up; return pluss(a,b); } fractionnum multi(fractionnum a,fractionnum b){ fractionnum temp; temp.down = a.down * b.down; temp.up = a.up * b.up; return yue(temp); } fractionnum devide(fractionnum a,fractionnum b){ fractionnum temp; temp.down = a.down * b.up; temp.up = a.up * b.down; return yue(temp); } void printpartition(fractionnum a){ a = yue(a); if (a.up<0)printf("(-"); if (maxfactor(abs(a.down), a.up) == a.down){ printf("%lld",abs(a.up)/a.down); } else{ if (abs(a.up)>a.down){ printf("%lld %lld/%lld",abs(a.up)/a.down,abs(a.up) % a.down,a.down);} else {printf("%lld/%lld",abs(a.up),a.down);} } if (a.up<0)printf(")"); } int main(){ fractionnum a,b; scanf("%lld/%lld",&a.up,&a.down); scanf("%lld/%lld",&b.up,&b.down); printpartition(a);printf(" + "); printpartition(b);printf(" = "); printpartition(pluss(a, b));printf("\n"); printpartition(a);printf(" - "); printpartition(b);printf(" = "); printpartition(minuss(a, b));printf("\n"); printpartition(a);printf(" * "); printpartition(b);printf(" = "); printpartition(multi(a, b));printf("\n"); printpartition(a);printf(" / "); printpartition(b);printf(" = "); if (b.up == 0){printf("Inf\n");} else {printpartition(devide(a, b));printf("\n");}// 这里忘记加大括号!测试点 3 格式错误 return 0; }
//B1035/A1089 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int n; cin>>n; vector<int>a;a.resize(n); vector<int>b;b.resize(n); int bpos = 0,judge = 0; for(int i = 0;i<n;i++){scanf("%d",&a[i]);} for(int i = 0;i<n;i++){ scanf("%d",&b[i]); if(judge == 0 && b[i]<b[i-1]){bpos = i;judge = 1;} } judge = 0; for(int i = bpos+1;i<n;i++){ if(b[i]!=a[i]){judge = 1;break;} } if (judge == 1){ cout<<"Merge Sort\n"; int key = 0; for(int seg = 2;seg<2*n;seg=seg*2){ for(int i = 0;i<n;i+=seg){ if (i+seg<n) sort(a.begin()+i,a.begin()+i+seg); else sort(a.begin()+i,a.end()); } if (key == 1){ for(int i = 0;i<n;i++){ cout<<a[i]; if (i!=n-1)cout<<' '; } break; } judge = 1; for(int i = 0;i<n;i++){if(a[i]!=b[i]){judge = 0;break;}} if (judge == 1)key = 1; } } else { cout<<"Insertion Sort\n"; for(int i = 0;i<bpos;i++){ if (b[i]>b[bpos] && judge == 0){ cout<<b[bpos]<<' '; judge +=1;} cout<<b[i]<<' '; } for(int i = bpos+1;i<n;i++){ cout<<b[i]; if(i!=n-1)cout<<' '; } } return 0; }
//B1036 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int n; char a; cin>>n>>a; for (int i =0;i<n;i++){ cout<<a; } cout<<endl; int t; if (n%2 == 0) t = n/2; else t = n/2+1; for (int i =0;i<t-2;i++){ cout<<a; for (int j =0;j<n-2;j++){ cout<<' '; } cout<<a<<endl;; } for (int i =0;i<n;i++){ cout<<a; } cout<<endl; return 0; }
//B1037 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int g1,s1,k1,g2,s2,k2,g3,s3,k3; scanf("%d.%d.%d %d.%d.%d",&g1,&s1,&k1,&g2,&s2,&k2); int sum1,sum2,diff; sum1 = g1 * 17 * 29 + s1 * 29 + k1; sum2 = g2 * 17 * 29 + s2 * 29 + k2; if (sum1>sum2){ diff = sum1-sum2; g3 = diff/(17*29); s3 = (diff-g3*17*29)/29; k3 = diff - g3 * 17 * 29 - s3 * 29; printf("-%d.%d.%d",g3,s3,k3); } else if (sum1<sum2){ diff = sum2-sum1; g3 = diff/(17*29); s3 = (diff-g3*17*29)/29; k3 = diff - g3 * 17 * 29 - s3 * 29; printf("%d.%d.%d",g3,s3,k3); } else{ cout<<"0.0.0"; return 0; } return 0; }
//B1038 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> //strlen #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ int n,k; int hundred[101] = {}; scanf("%d",&n); int score[n]; for(int i = 0;i<n;i++){ scanf("%d",&score[i]); hundred[score[i]]+=1;} scanf("%d",&k); int query[k]; for(int i = 0;i<k;i++){scanf("%d",&query[i]);} for(int i = 0;i<k;i++){ printf("%d",hundred[query[i]]); if (i<k-1)cout<<' '; } return 0; }
//B1039/A1092 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ char a[1000],b[1000]; scanf("%s %s",a,b); int hash[128] = {}; int lena = (int)strlen(a); int lenb = (int)strlen(b); for(int i = 0;i<lena;i++) hash[(int)a[i]]+=1; int judge = 1,left = 0; for(int i = 0;i<lenb;i++){ hash[(int)b[i]]-=1; if (hash[(int)b[i]]<0) judge = 0; } int num = 0; if (judge == 0){ cout<<"No "; for(int i = 0;i<128;i++){ if(hash[i] < 0)num += hash[i]; } } else{ cout<<"Yes "; for(int i = 0;i<128;i++){ if(hash[i] > 0)num += hash[i]; } } cout<<abs(num); return 0; }
//B1040/A1093 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ string a; cin>>a; vector<int>p;p.resize(a.size()); vector<int>t;t.resize(a.size()); int countp=0,countt = 0; long long count=0;; for(int i = 0;i<a.size();i++){ if(a[i] == 'P')countp+=1; if(a[i] == 'A')p[i] = countp; } for(int i = a.size()-1;i>=0;i--){ if(a[i] == 'T')countt+=1; if(a[i] == 'A')t[i] = countt; } for(int i = 0;i<a.size();i++){ if(a[i] == 'A')count+=(long long)p[i]*t[i]; } cout<<count%1000000007; return 0; }
//B1041 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int n,m; // cout<<123; cin>>n; long long a[n][3]; for (int i = 0;i<n;i++){ cin>>a[i][0]>>a[i][1]>>a[i][2]; } cin>>m; int b[m]; for (int i = 0;i<m;i++){ cin>>b[i]; } for(int i = 0;i<m;i++){ for(int j = 0;j<n;j++){ if (b[i] == a[j][1]){ cout<<a[j][0]<<' '<<a[j][2]<<endl; break; } } } return 0; }
//B1042 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ char a[1000]; cin.getline(a,1000); int hash[27] = {}; int lena = (int)strlen(a); for(int i = 0;i<lena;i++) { if (a[i]>='a'&&a[i]<='z') hash[(int)(a[i]-'a')]+=1; if (a[i]>='A'&&a[i]<='Z') hash[(int)(a[i]-'A')]+=1; } int max = 0; char maxchar; for(int i = 0;i<27;i++){ if(hash[i] > max) {max = hash[i];maxchar = (char)(i+'a');} } cout<<maxchar<<' '; cout<<max; return 0; }
//B1043 4/5错误答案 只需要处理 PATest 6个字母就好了啊!!(其实错误是因为没审题,应该分配10000…) #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ char a[1000]; cin.getline(a,1000); int hash[52] = {}; int lena = (int)strlen(a); for(int i = 0;i<lena;i++) { if (a[i]>='a'&&a[i]<='z') hash[(int)(a[i]-'a')]+=1; if (a[i]>='A'&&a[i]<='Z') hash[(int)(a[i]-'A'+26)]+=1; } for(int i = 0;i<lena;i++) { int judge = 0; if (hash['P'-'A'+26]>0) {cout<<'P';hash['P'-'A'+26]-=1;judge = 1;} if (hash['A'-'A'+26]>0) {cout<<'A';hash['A'-'A'+26]-=1;judge = 1;} if (hash['T'-'A'+26]>0) {cout<<'T';hash['T'-'A'+26]-=1;judge = 1;} if (hash['e'-'a']>0) {cout<<'e';hash['e'-'a']-=1;judge = 1;} if (hash['s'-'a']>0) {cout<<'s';hash['s'-'a']-=1;judge = 1;} if (hash['t'-'a']>0) {cout<<'t';hash['t'-'a']-=1;judge = 1;} if (judge == 0)break; } return 0; }
//B1043 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ char a[50000]; cin.getline(a,50000); int hash[6] = {}; int lena = (int)strlen(a); int sum = 0; for(int i = 0;i<lena;i++) { if (a[i]=='P'){hash[0]++;sum+=1;} else if (a[i]=='A'){hash[1]++;sum+=1;} else if (a[i]=='T'){hash[2]++;sum+=1;} else if (a[i]=='e'){hash[3]++;sum+=1;} else if (a[i]=='s'){hash[4]++;sum+=1;} else if (a[i]=='t'){hash[5]++;sum+=1;} } for(int i = 0;i<lena;i++) { if (hash[0]>0) {cout<<'P';hash[0]-=1;sum-=1;} if (hash[1]>0) {cout<<'A';hash[1]-=1;sum-=1;} if (hash[2]>0) {cout<<'T';hash[2]-=1;sum-=1;} if (hash[3]>0) {cout<<'e';hash[3]-=1;sum-=1;} if (hash[4]>0) {cout<<'s';hash[4]-=1;sum-=1;} if (hash[5]>0) {cout<<'t';hash[5]-=1;sum-=1;} if (sum <= -1)break; } return 0; }
//B1044/A1100 $ 0/5 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> #include <map> #include <string> using namespace std; int toint(string a){ int b = 0; for(int i = 0;i<a.size();i++){ b = b*10 + (int)(a[i] - '0'); } return b; } int main(){ string a[13] = {"tret","jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"}; string b[13] = {"tret","tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"}; map<string,int> str2int; string int2str[169]; // 这个大小开错了,导致两个测试点错误:多了就会有重复! for(int i = 0;i<169;i++){ string temp; if (i/13 != 0 && i%13 != 0) temp = b[i/13]+" "+a[i%13]; else if (i/13 == 0) temp = a[i%13]; else temp = b[i/13]; int2str[i] = temp; str2int[temp] = i; // cout<<i<<' '<<temp<<endl; } // printf("%d",str2int["tam"]); int n; string str; scanf("%d%*c",&n); // 这里一定要接收换行符!! // NOTE 16 scanf 接收换行符 while(n--){ getline(cin,str); if(str[0]>='0'&&str[0]<='9'){ int temp = toint(str); cout<<int2str[temp]<<endl; } else{ cout<<str2int[str]<<endl; } } return 0; }
//B1045/A1101 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ int n; cin>>n; vector<int>a;a.resize(n); for(int i = 0;i<n;i++){scanf("%d",&a[i]);} vector<int>left;left.resize(n); vector<int>right;right.resize(n); vector<int>result;result.resize(n); int max = a[0],min = a[n-1]; left[0] = 1;right[n-1] = 1; for(int i = 0;i<n;i++){ if (a[i]>=max){max = a[i];left[i] = 1;} else {left[i] = 0;} } for(int i = n-1;i>=0;i--){ if (a[i]<=min){min = a[i];right[i] = 1;} else {right[i] = 0;} } int count = 0; for(int i = 0;i<n;i++){ if (left[i] == 1 && right[i] == 1){ // result.push_back(a[i]); result[count++] = a[i];} } printf("%d\n",count); vector<int>finalresult;finalresult.resize(count); for(int i = 0;i<count;i++){finalresult[i] = result[i];} // 说是大小顺序,但其实一定是从小到大的!这一步拷贝排序完全是多余的! // sort(finalresult.begin(),finalresult.end()); for(int i = 0;i<count;i++){ printf("%d",result[i]); if (i<count - 1)printf(" "); } printf("\n"); return 0; }
//B1047 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ int n; cin>>n; vector<int>team; team.resize(1000); for(int i = 0;i<n;i++){ int a,b,c; scanf("%d-%d %d",&a,&b,&c); team[a]+=c; } int max = 0,mteam = 0; for(int i = 0;i<1000;i++){ if (team[i]>max){max = team[i];mteam = i;} } cout<<mteam<<' '<<max; return 0; }
//B1048 TODO 4/6 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int cmp(string a,string b){ if(a.size()>b.size()) return (int)b.size(); else return (int)a.size(); } string max(string a,string b){ if(a.size()<b.size()) return b; else return a; } int main(){ string a,b,c; cin>>a>>b; for(int i = 0;i<cmp(a,b);i++){ if(i%2==0){ int temp = (a[a.size()-i-1]+b[b.size()-i-1]-'0'-'0')%13; // cout<<"ji "<<temp<<endl; if (temp<10) c.push_back((char)(temp+'0')); else if (temp==10) c.push_back('J'); else if (temp==11) c.push_back('Q'); else if (temp==12) c.push_back('K'); } else{ // cout<<"ou "<<(char)((10-a[a.size()-i-1]+b[b.size()-i-1])%10+'0')<<endl; c.push_back((char)((10-a[a.size()-i-1]+b[b.size()-i-1])%10+'0')); } // cout<<c<<endl; } for(int i = cmp(a,b);i<max(a,b).size();i++){ c.push_back(max(a,b)[max(a,b).size()-i-1]); } for(int i = 0;i<c.size();i++){ cout<<c[c.size()-1-i]; } return 0; }
//B1049/A1104 &AC #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ int n; cin>>n; vector<double>a;a.resize(n); for(int i = 0;i<n;i++){ scanf("%lf",&a[i]); } double finalproduct = 0.0; for(int i = 0;i<n;i++){ finalproduct += a[i] * (i+1) * (n-i); } printf("%.02lf",finalproduct); return 0; }
//A1001 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> using namespace std; int main(){ int a,b,result; string op; cin>>a>>b; result = a+b; // cout<<result; op = to_string(result); // cout<<op.size(); int judge = 1; for(int i = 0;i<op.size();i++){ if (i%3 == op.size()%3 && judge == 0){ cout<<','; i-=1; judge = 1; } else { cout<<op[i]; if (op[i] == '-')judge = 1; else judge = 0; } }return 0; }
//A1003 $ 不会 #include <queue> #include <vector> #include <cstdio> using namespace std; const int maxn = 510; const int INF = 0x3fffffff; struct node{ int v,weight; node(int _v,int _w):v(_v),weight(_w){}; }; int n,m,s,u; vector<node>adj[maxn]; int dis[maxn]; //int dis[maxn] = {INF}; // NOTE20 只能0可以简单的初始化,其它的初值需要用 fill 函数 int weight[maxn],pathnum[maxn] = {0},teamnum[maxn] = {0}; bool vis[maxn] = {false}; void Dj(int s){ fill(dis,dis+maxn,INF); dis[s] = 0;pathnum[s] = 1;teamnum[s] = weight[s]; for(int i = 0;i<n;i++){ int MIN = INF,k = -1; for(int j = 0;j<n;j++){ if (dis[j] < MIN && vis[j] == false){ MIN = dis[j]; k = j; } } if (k == -1)return; vis[k] = true; // printf("%d ",k); for(int j = 0;j<adj[k].size();j++){ int v = adj[k][j].v; // printf("--%d--",adj[k][j].v); if (vis[v] == false){ if(dis[v] > dis[k] + adj[k][j].weight) { dis[v] = dis[k] + adj[k][j].weight; pathnum[v] = pathnum[k]; teamnum[v] = teamnum[k] + weight[v]; } else if (dis[v] == dis[k] + adj[k][j].weight) { if (teamnum[v] < teamnum[k] + weight[v]) { teamnum[v] = teamnum[k] + weight[v]; } pathnum[v] += pathnum[k]; } } } // printf("%d %d %d %d ",i,k,pathnum[u],teamnum[u]); // for(int p = 0;p<n;p++){printf(" %d-%d",dis[p],vis[p]);} // printf("\n"); } } int main(){ scanf("%d %d %d %d",&n,&m,&s,&u); for(int i = 0;i<n;i++){scanf("%d",&weight[i]);} for(int i = 0;i<m;i++){ int a,b,c; scanf("%d %d %d",&a,&b,&c); adj[a].push_back(node(b,c)); adj[b].push_back(node(a,c)); } // for(int i = 0;i<n;i++){ // printf("%d ",i); // for(int j = 0;j<adj[i].size();j++) // { // printf("%d-%d ",adj[i][j].v,adj[i][j].weight); // } // printf("\n"); // } Dj(s); printf("%d %d\n",pathnum[u],teamnum[u]); return 0; }
//A1004 6/6 #include <queue> #include <cstdio> #include <vector> #include <math.h> using namespace std; struct Node{ int layer; vector<int>child; }; vector<Node>tree; void inorder(int root){ queue<int>q; q.push(root); tree[root].layer = 1; while(!q.empty()){ int front = q.front(); // printf("%d\n",front); q.pop(); for(int i = 0;i<tree[front].child.size();i++){ q.push(tree[front].child[i]); tree[tree[front].child[i]].layer = tree[front].layer + 1; } } } int main(){ int n,m; scanf("%d %d",&n,&m); tree.resize(n+1); for(int i = 0;i<m;i++){ int childsize,number; scanf("%d %d",&number,&childsize); tree[number].child.resize(childsize); for(int j = 0;j<childsize;j++){ scanf("%d",&tree[number].child[j]); } } // for(int i = 0;i<n;i++){ // printf("%d ",i); // for (int j = 0;j<tree[i].child.size();j++){ // printf(" %d",tree[i].child[j]); // } // printf("\n"); // } inorder(1); // for(int i = 0;i<n;i++){ // printf("%d %d",i,tree[i].layer); // for (int j = 0;j<tree[i].child.size();j++){ // printf(" %d",tree[i].child[j]); // } // printf("\n"); // } vector<int>count(n+1); int maxlayer = 0; for(int i = 0;i<n+1;i++){ if (tree[i].child.size() == 0) count[tree[i].layer]++; if (tree[i].layer > maxlayer) maxlayer = tree[i].layer; } for (int i = 1;i<maxlayer+1;i++){ printf("%d",count[i]); if (i<maxlayer) printf(" "); } return 0; }
//A1005 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> using namespace std; int main(){ string a; int sum = 0; cin>>a; for (int i = 0;i<a.size();i++){ sum += a[i]-'0'; } string result = to_string(sum); for (int i = 0;i<result.size();i++){ switch (result[i]-'0'){ case 0:cout<<"zero";break; case 1:cout<<"one";break; case 2:cout<<"two";break; case 3:cout<<"three";break; case 4:cout<<"four";break; case 5:cout<<"five";break; case 6:cout<<"six";break; case 7:cout<<"seven";break; case 8:cout<<"eight";break; case 9:cout<<"nine";break; } if (i!=result.size()-1)cout<<' '; } return 0; }
//A1006 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; typedef struct{ char name[20]; int date1,date2; } man; bool cmp1(man a,man b) { return a.date1<b.date1; } bool cmp2(man a,man b) { return a.date2>b.date2; } int main(){ int n; cin>>n; man people[n]; int a,b,c,d,e,f; for (int i = 0;i<n;i++){ scanf("%s %d:%d:%d %d:%d:%d" ,people[i].name,&a,&b,&c,&d,&e,&f); people[i].date1 = a*10000+b*100+c; people[i].date2 = d*10000+e*100+f; } sort(people, people+n,cmp1); cout<<people[0].name<<' '; sort(people, people+n,cmp2); cout<<people[0].name<<endl; return 0; }
//A1007 $ 5/25 审题! #include <cstdio> #include <algorithm> using namespace std; int main(){ int n,flag = 0; scanf("%d",&n); int a[n],dp[n],posstart[n]; for(int i = 0;i<n;i++){ scanf("%d",&a[i]); if (a[i]>=0)flag = 1; } if (flag == 0){ printf("0 %d %d",a[0],a[n-1]); return 0; } dp[0] = a[0]; for(int i = 1;i<n;i++){ if (dp[i-1]+a[i] > a[i]){ dp[i] = dp[i-1]+a[i]; posstart[i] = posstart[i-1]; } else{ dp[i] = a[i]; posstart[i] = i; } } int maxendpos = 0; for (int i = 0;i<n;i++){ if (dp[i] > dp[maxendpos]){ maxendpos = i; } } printf("%d %d %d",dp[maxendpos],a[posstart[maxendpos]],a[maxendpos]); return 0; }
//A1008 $AC 虽然没考虑列表相邻相同的情况,但还是AC了 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ int n; cin>>n; vector<int>a;a.resize(n); for(int i = 0;i<n;i++){ scanf("%d",&a[i]); } int finalproduct = 0,now = 0; for(int i = 0;i<n;i++){ if (a[i]>now)finalproduct+= 6 * (a[i]-now) + 5; else finalproduct+= 4 * (-a[i]+now) + 5; now = a[i]; } printf("%d",finalproduct); return 0; }
//A1010 TODO 13/20 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; // string a 转换成 k 进制 longlong long long convert(string a,int k){ long long num = 0; for(int i = (int)a.size()-1;i>=0;i--){ int temp = 0; if (a[i] >= '0' && a[i]<='9')temp = a[i] - '0'; else temp = a[i] - 'a' + 10; if (k<=temp)return 0; num += temp * pow(k, (a.size()-1-i)); } return num; } // 找到最大的进制数 int maxradix(string a){ int radix = 0; for(int i = 0;i<a.size();i++){ if (a[i] >= '0' && a[i]<='9'){ if ((a[i]-'0')>radix) radix = a[i]-'0'; } else { if ((a[i]-'a'+10)>radix) radix = a[i]-'a'+10; } } return radix; } int main(){ int tag,radix; string a,b; cin>>a>>b>>tag>>radix; long long anum; if (tag == 1){ anum = convert (a,radix); } else{ anum = convert (b,radix); b = a; } int left = 0,right = max(maxradix(b),radix)+1,sgn = 0; while(left<=right){ int mid = (left + right)/2; if (anum < convert(b, mid)) right = mid-1; else if (anum > convert(b, mid)) left = mid+1; else {cout<<mid;sgn = 1;break;} // cout<<mid<<endl; } if (sgn == 0)cout<<"Impossible"; return 0; }
//A1011 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int n; double a[3][3]; int pos[3]; for (int i = 0;i<3;i++){ for (int j = 0;j<3;j++){ cin>>a[i][j]; } double max = 0; for (int j = 0;j<3;j++){ if (a[i][j]>max){ max = a[i][j]; pos[i] = j; } } } for (int i = 0;i<3;i++){ if (pos[i] == 0) cout<<"W "; else if (pos[i] == 1) cout<<"T "; else if (pos[i] == 2) cout<<"L "; } cout<<setiosflags(ios::fixed)<<setprecision(2)<<(a[1][pos[1]] * a[0][pos[0]] *a[2][pos[2]] * 0.65 - 1)*2; return 0; }
//A1012 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int now; typedef struct{ int id; int grade[4]; int rank[4]; } student; bool cmp(student a,student b) { return a.grade[now]>b.grade[now]; } int main(){ int n,m; cin>>n>>m; student stu[n],stuchk[m]; for(int i = 0;i<n;i++){ cin>>stu[i].id>>stu[i].grade[0]>>stu[i].grade[1]>>stu[i].grade[2]; stu[i].grade[3] = stu[i].grade[0]+stu[i].grade[1]+stu[i].grade[2]; } for(int i = 0;i<m;i++){ cin>>stuchk[i].id; } for(now = 0;now<4;now++){ sort(stu, stu+n, cmp); for(int i = 0;i<n;i++){ if (i == 0) stu[i].rank[now] = i; if (stu[i].grade[now]!=stu[i-1].grade[now]) stu[i].rank[now] = i; else stu[i].rank[now] = stu[i-1].rank[now]; //这里有并列排名的时候,rank要一样!//NOTE4 } } // for(int i = 0;i<n;i++){ // printf("%d %d %d %d %d %d %d %d %d \n", // stu[i].id,stu[i].grade[0],stu[i].grade[1],stu[i].grade[2],stu[i].grade[3],stu[i].rank[0],stu[i].rank[1],stu[i].rank[2],stu[i].rank[3]); // } int toop[4] = {3,0,1,2}; for(int i = 0;i<m;i++){ // cout<<i<<stuchk[i].id<<' '; int sgn = 0; for(int j = 0;j<n;j++){ if (stuchk[i].id == stu[j].id){ int min = n,minsgn = 5; for(int k = 0;k<4;k++){ if (stu[j].rank[toop[k]]<min) { min = stu[j].rank[toop[k]]; minsgn = toop[k];} } cout<<min+1<<' '; switch (minsgn){ case 0:{cout<<"C"<<endl;break;} case 1:{cout<<"M"<<endl;break;} case 2:{cout<<"E"<<endl;break;} case 3:{cout<<"A"<<endl;break;} default:continue; } sgn = 1; break; } } if (sgn == 0)cout<<"N/A"<<endl; } return 0; }
//A1013 $ 18/25 想复杂了 #include <cstdio> #include <vector> #include <queue> using namespace std; const int maxn = 1010; int n,m,k; vector<int>graph[maxn]; bool BFS(int start,int end,int nopass){ queue<int>q; bool vis[maxn] = {false}; q.push(start);vis[start] = true; while(!q.empty()){ int top = q.front();q.pop(); if (top == end)return true; for(int i = 0;i<graph[top].size();i++){ int temp = graph[top][i]; if (temp != nopass && vis[temp] == false){ q.push(temp); vis[temp] = true; } } } return false; } int getNum(int nopass){ int count = 0; for(int i = 1;i<graph[nopass].size();i++){ // printf("%d %d %d\n",graph[nopass][0],graph[nopass][i],BFS(graph[nopass][0], graph[nopass][i], nopass)); if (!BFS(graph[nopass][0], graph[nopass][i], nopass)){ count ++; int a = graph[nopass][0]; int b = graph[nopass][i]; graph[a].push_back(b); graph[b].push_back(a); } } return count; } int main(){ scanf("%d%d%d",&n,&m,&k); for(int i = 1;i<m+1;i++){ int temp1,temp2; scanf("%d%d",&temp1,&temp2); graph[temp2].push_back(temp1); graph[temp1].push_back(temp2); } // for(int i = 1;i<n+1;i++){ // printf("\n%d",i); // for(int j = 0;j<graph[i].size();j++){ // printf(" %d",graph[i][j]); // } // } int query[k]; for(int i = 0;i<k;i++){scanf("%d",&query[i]);} for(int i = 0;i<k;i++){printf("%d\n",getNum(query[i]));} return 0; }
//A1013 并查集 $ 25/25 #include <cstdio> #include <vector> using namespace std; const int maxn = 1010; int father[maxn]; bool vis[maxn]; vector<int>g[maxn]; void init(int n){ for(int i = 1;i<=n;i++){ father[i] = i; vis[i] = false; } } int findfather(int k){ int a = k; while(father[k]!=k){ k = father[k]; } while(father[a]!=a){ int z = father[a]; father[a] = k; a = z; } return k; } void Union(int a,int b){ int faa = findfather(a); int fab = findfather(b); if (faa != fab) father[a] = b; } int main(){ int n,m,k; scanf("%d %d %d",&n,&m,&k); init(n); for(int i = 1;i<m+1;i++){ int temp1,temp2; scanf("%d%d",&temp1,&temp2); g[temp1].push_back(temp2); g[temp2].push_back(temp1); } int cur; for(int i = 0;i<k;i++){ scanf("%d",&cur); init(n); for(int ii = 1;ii <= n;ii++){ for(int jj = 0;jj<g[ii].size();jj++){ int u = ii,v = g[ii][jj]; if (u!=cur && v != cur){ Union(u, v); } } } int count= 0; for(int i = 1;i<=n;i++){ if (i == cur)continue; int fai = findfather(i); if (vis[fai] == false){ count++; vis[fai] = true; } } printf("%d\n",count-1); } return 0; }
//A1015 $ 1/4 TODO 2/4 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; bool isPrime(int n) { if (n<1)return false; for(int i=2;i<(int)sqrt(1.0*n)+1;i++) { if(n % i == 0)return false; } return true; } // NOTE 11 进制转换模板 // k1 进制 string a 转换成 k2 进制(都<=10) int convert(string a,int k1,int k2){ int num = 0; for(int i = (int)a.size()-1;i>=0;i--){ int temp = 0; if (a[i] >= '0' && a[i]<='9')temp = a[i] - '0'; num += temp * pow(k1, (a.size()-1-i)); } vector<int>tempvec; if (k2 == 10) return num; else{ while(num>=k2){ tempvec.push_back(num % k2); num /= k2; } tempvec.push_back(num); } num = 0; for(int i = 0;i<tempvec.size();i++){ num = num * 10 + tempvec[tempvec.size()-i-1]; } return num; } int main(){ vector<int>n1; vector<int>d; int temp = 1,count = 0; while(temp>0){ scanf("%d",&temp); if (temp<0)break; if (count % 2 == 1) d.push_back(temp); else n1.push_back(temp); count++; } for(int i = 0;i<n1.size();i++){ if (isPrime(n1[i]) == false)printf("No\n"); else{ // cout<<n1[i]<<' '<<d[i]<<' '; // cout<<convert(to_string(n1[i]),10,d[i])<<' '; string str = to_string(convert(to_string(n1[i]),10,d[i])); // cout<<str<<' '; reverse(str.begin(),str.end()); // cout<<str<<' '<<endl; if (isPrime(convert(str,d[i],10))) printf("Yes\n"); else printf("No\n"); } } return 0; }
//A1016 TODO 写了一晚上,一分没有T_T 0/4 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; typedef struct { int time[4]; // int time[4] = {}; //这样就不对了,这是为啥呢TODO bool online = 0; }record; typedef struct { string name; vector<record>records; }client; bool cmp(record a,record b){ if(a.time[0]!=b.time[0])return a.time[0]<b.time[0]; else if(a.time[1]!=b.time[1])return a.time[1]<b.time[1]; else if(a.time[2]!=b.time[2])return a.time[2]<b.time[2]; else return a.time[3]<b.time[3]; } bool cmpname(client a,client b){ return a.name<b.name; } int main(){ int toll[24],n; for(int i = 0;i<24;i++){cin>>toll[i];} cin>>n; vector<client>clients; for(int i = 0;i<n;i++){ string temp; char temp2[100]; record temp1; cin>>temp; int k = 0; int sgn = 0; for(int i = 0;i<clients.size();i++){ if (clients[i].name == temp){k = i;sgn = 1;} } if (sgn == 0){ clients.resize(clients.size()+1); clients[clients.size()-1].name = temp; k = (int)clients.size()-1; } scanf("%d:%d:%d:%d %s",&temp1.time[0],&temp1.time[1],&temp1.time[2],&temp1.time[3],temp2); if (temp2[1] == 'n') temp1.online = 1; //online=1 else temp1.online = 0; clients[k].records.push_back(temp1); } //完成输入,下面开始操作 sort(clients.begin(),clients.end(),cmpname); //排列姓名 for(int i = 0;i<clients.size();i++){ double totalmoney = 0; sort(clients[i].records.begin(),clients[i].records.end(),cmp); //排列记录时间 while(clients[i].records[clients[i].records.size()-1].online == 1){ //删除最后落单的online clients[i].records.pop_back(); } while(clients[i].records[0].online == 1 && clients[i].records[1].online == 1){ //删除最前落单的online clients[i].records.erase(clients[i].records.begin()); } bool k = 1; //用于切换offline和online int printname = 0; for(int j = 0;j<clients[i].records.size();j++){ record temp; if (k==clients[i].records[j].online){ if(printname == 0){ cout<<clients[i].name<<' '<<setw(2)<< setfill('0')<<clients[i].records[0].time[0]<<endl; printname = 1; } cout<<setw(2)<< setfill('0')<<clients[i].records[j].time[1]<<':'<<setw(2)<< setfill('0')<<clients[i].records[j].time[2]<<':'<<setw(2)<< setfill('0')<<clients[i].records[j].time[3]; k = !k; //用于切换offline和online if(clients[i].records[j].online == 1){ temp = clients[i].records[j]; //记录online cout<<' '; } else{ int time = (clients[i].records[j].time[1]*1440+clients[i].records[j].time[2]*60+clients[i].records[j].time[3])-(temp.time[1]*1440+temp.time[2]*60+temp.time[3]); double money = 0; double start,end; for(int day = temp.time[1]; day<clients[i].records[j].time[1]+1;day++){ for(int hour = temp.time[2]; hour < clients[i].records[j].time[2]+1;hour++){ if (temp.time[1]==clients[i].records[j].time[1] && temp.time[2]==clients[i].records[j].time[2]){ //避免临界情况 start = temp.time[3];end = clients[i].records[j].time[3]; } else if (day == temp.time[1] && hour == temp.time[2]){start = temp.time[3];end = 60;} else if (day == clients[i].records[j].time[1] && hour == clients[i].records[j].time[2]){start = 0;end = clients[i].records[j].time[3];} else {start = 0;end = 60;} money = money + (double)toll[hour] * (end-start) / 100; } } cout<<' '<<time<<" $"<<fixed<<setprecision(2)<<money<<endl; totalmoney = totalmoney + money; } } } if (totalmoney > 0){ cout<<"Total amount: $"<<fixed<<setprecision(2)<<totalmoney<<endl; } } return 0; } //// 比较坑的临界数据 10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10 5 a 01:01:01:03 on a 01:02:00:01 once_flag CYLL 01:28:15:41 once_flag a 01:05:02:24 once_flag a 01:02:00:02 off_t
//A1016 第二个改版,1/4了呜呜呜 TODO #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <sstream> #include <iomanip> using namespace std; typedef struct { int time[4]; char name[100]; // int time[4] = {}; //这样就不对了,这是为啥呢TODO bool online = 0; }record; bool cmp(record a,record b){ if(a.time[0]!=b.time[0])return a.time[0]<b.time[0]; else if(a.time[1]!=b.time[1])return a.time[1]<b.time[1]; else if(a.time[2]!=b.time[2])return a.time[2]<b.time[2]; else return a.time[3]<b.time[3]; } bool cmpname(record a,record b){ if (strcmp(a.name,b.name)!=0) return strcmp(a.name,b.name)<0; else if(a.time[0]!=b.time[0])return a.time[0]<b.time[0]; else if(a.time[1]!=b.time[1])return a.time[1]<b.time[1]; else if(a.time[2]!=b.time[2])return a.time[2]<b.time[2]; else return a.time[3]<b.time[3]; } int main(){ int toll[24],n; for(int i = 0;i<24;i++){cin>>toll[i];} cin>>n; vector<record>recs; for(int i = 0;i<n;i++){ string temp; char temp2[100]; record temp1; scanf("%s %d:%d:%d:%d %s",temp1.name,&temp1.time[0],&temp1.time[1],&temp1.time[2],&temp1.time[3],temp2); if (temp2[1] == 'n') temp1.online = 1; //online=1 else temp1.online = 0; recs.push_back(temp1); } //完成输入,下面开始操作 sort(recs.begin(),recs.end(),cmpname); //排列姓名 vector<record>recs4real; for(int i = 0;i<recs.size()-1;i++){ if (strcmp(recs[i].name,recs[i+1].name)==0 && recs[i].online == 1 && recs[i+1].online == 0){ recs4real.push_back(recs[i]); recs4real.push_back(recs[i+1]); i = 1+i; } } // for(int i = 0;i<recs4real.size();i+=2){ // printf("%s %02d:%02d:%02d:%02d %d\n",recs4real[i].name,recs4real[i].time[0],recs4real[i].time[1],recs4real[i].time[2],recs4real[i].time[3],(int)recs4real[i].online); // }cout<<endl; char tempname[20]; int time = 0; double totalmoney = 0; for(int i = 0;i<recs4real.size();i+=2){ if (strcmp(recs4real[i].name,tempname) != 0){ printf("%s %02d\n",recs4real[i].name,recs4real[i].time[0]); sscanf(recs4real[i].name,"%s",tempname); } int passtime = (recs4real[i+1].time[1]*1440+recs4real[i+1].time[2]*60+recs4real[i+1].time[3])-(recs4real[i].time[1]*1440+recs4real[i].time[2]*60+recs4real[i].time[3]); double money = 0; double start,end; for(int day = recs4real[i].time[1]; day<recs4real[i+1].time[1]+1;day++){ for(int hour = recs4real[i].time[2]; hour < recs4real[i+1].time[2]+1;hour++){ if (recs4real[i].time[1]==recs4real[i+1].time[1] && recs4real[i].time[2]==recs4real[i+1].time[2]){ //避免临界情况 start = recs4real[i].time[3];end = recs4real[i+1].time[3]; } else if (day == recs4real[i].time[1] && hour == recs4real[i].time[2]){start = recs4real[i].time[3];end = 60;} else if (day == recs4real[i+1].time[1] && hour == recs4real[i+1].time[2]){start = 0;end = recs4real[i+1].time[3];} else {start = 0;end = 60;} money = money + (double)toll[hour] * (end-start) / 100; } } totalmoney += money; printf("%02d:%02d:%02d %02d:%02d:%02d %d $%.2f\n",recs4real[i].time[1],recs4real[i].time[2],recs4real[i].time[3],recs4real[i+1].time[1],recs4real[i+1].time[2],recs4real[i+1].time[3],passtime,money); if (strcmp(recs4real[i].name,recs4real[i+2].name) != 0){ printf("%s $%.2f\n","Total amount:",totalmoney); totalmoney = 0; } } return 0; }
//A1018 $ 16/30 #include <cstdio> #include <vector> #include <math.h> using namespace std; const int maxn = 510; const int INF = 0x3fffffff; struct edge{ int v,length; edge(int _a,int _b):v(_a),length(_b){}; }; int cmax,n,sp,m; int bikenum[maxn],dis[maxn]; bool vis[maxn] = {}; vector<edge>adj[maxn]; vector<int>pre[maxn],best,tempbest; void Dj(int start){ fill(dis,dis+maxn,INF); dis[start] = 0; for(int ii = 0;ii<n;ii++){ int k = -1,MIN = INF; for(int i = 0;i<n;i++){ if (dis[i]<MIN && vis[i] == false){ MIN = dis[i]; k = i; } } if (k == -1)return; vis[k] = true; for(int i = 0;i<adj[k].size();i++){ int v = adj[k][i].v; if (vis[v] == false && dis[v] > dis[k] + adj[k][i].length){ dis[v] = dis[k] + adj[k][i].length; pre[v].clear(); pre[v].push_back(k); }else if(dis[v] == dis[k] + adj[k][i].length){ pre[v].push_back(k); } } } } // 题意没有读明白!need有正有负!审题!而且途中每个都要调到最优!! int minneed = INF,minremain = INF; void DFS(int now){ if (now == 0){ tempbest.push_back(0); int need = 0,remain = 0; for(int i = (int)tempbest.size()-2;i>=0;i--){ int n = bikenum[tempbest[i]] - cmax/2; // printf("%d ",n); if (n > 0){ remain += n; } else{ if (remain > -n ){ remain = remain + n; } else{ need = need - n - remain; remain = 0; } } // printf(" _%d_%d_ ",need,remain); } if (need < minneed){ minneed = need; minremain = remain; best = tempbest; }else if (need == minneed && remain < minremain){ minneed = need; minremain = remain; best = tempbest; } // printf("__%d__%d__\n",minneed,minremain); tempbest.pop_back(); return; } tempbest.push_back(now); for(int i = 0;i<pre[now].size();i++){ DFS(pre[now][i]); } tempbest.pop_back(); } int main(){ scanf("%d %d %d %d",&cmax,&n,&sp,&m); for(int i = 1;i<=n;i++){scanf("%d",&bikenum[i]);} for(int i = 0;i<m;i++){ int a,b,c; scanf("%d %d %d",&a,&b,&c); adj[a].push_back(edge(b,c)); adj[b].push_back(edge(a,c)); } Dj(0); DFS(sp); printf("%d ",minneed); for(int i = 0;i<best.size();i++){ printf("%d",best[best.size() - 1- i]); if (i<best.size()-1)printf("->"); } printf(" %d",minremain); return 0; }
//A1019 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int c,d; cin>>c>>d; vector<int>result; while (c/d > 0){ result.push_back(c-d*(c/d)); c = (c-c%d)/d; } result.push_back(c); int judge = 1; for(int i = 0;i<(result.size()+1)/2;i++){ if (result[i]!=result[result.size()-1-i]){ cout<<"No"; judge = 0; break; } } if (judge == 1){ cout<<"Yes"; } cout<<endl; for(int i = 0;i<result.size();i++){ cout<<result[result.size()-1-i]; if (i<result.size()-1) cout<<' '; } return 0; }
//A1020 $ 6/6 #include <cstdio> #include <vector> #include <queue> using namespace std; struct node{ int data; node* lchild; node* rchild; }Node; vector<int>layer(0),post(30),in(30); node* create(int postL,int postR,int inL,int inR){ if (postL>postR)return NULL; node* root = new node; root->data = post[postR]; // printf("%d\n",root->data); int k; for(k = inL;k<inR;k++){ if (post[postR] == in[k]){ break; } } int leftnum = k-inL; root->lchild = create(postL, postL+leftnum-1, inL, k-1); root->rchild = create(postL+leftnum,postR-1,k+1,inR); return root; } void layerorder(node* root,vector<int>&layer){ queue<node*>q; q.push(root); node *now = new node; while(!q.empty()){ layer.push_back(q.front()->data); // printf("%d\n",q.front()->data); now = q.front(); q.pop(); if (now->lchild != NULL)q.push(now->lchild); if (now->rchild != NULL)q.push(now->rchild); } } int main(){ int n; scanf("%d",&n); post.resize(n);in.resize(n); for(int i = 0;i<n;i++){scanf("%d",&post[i]);} for(int i = 0;i<n;i++){scanf("%d",&in[i]);} node* root = new node; root = create(0, n-1, 0, n-1); layerorder(root, layer); for(int i = 0;i<n;i++){ printf("%d",layer[i]); if (i<n-1) printf(" "); } return 0; }
//A1021 不会 $ 23/25 #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int maxn = 100000; int n; vector<int>g[maxn]; int father[maxn]; bool vis[maxn] = {false}; bool isfather[maxn] = {false}; void init(int n){ for(int i = 1;i<n+1;i++){ father[i] = i; } } int findfather(int n){ int a = n; while(father[n]!=n){ n = father[n]; } while(a!=father[a]){ int z = father[a]; father[a] = n; a = z; } return n; } void Union(int a,int b){ int faa = findfather(a); int fab = findfather(b); if (faa != fab){father[faa] = fab;} } int countblock(){ for(int i = 1;i<n+1;i++){ isfather[findfather(i)] = true; } int count = 0; for(int i = 1;i<n+1;i++){ if (isfather[i] == true)count++; } return count; } int maxdepth = 0; vector<int>temp,ans; void DFS(int start,int depth,int pre){ if (depth > maxdepth){ temp.clear(); temp.push_back(start); maxdepth = depth; }else if (depth == maxdepth){ temp.push_back(start); } for(int i = 0;i<g[start].size();i++){ if (g[start][i] == pre)continue; DFS(g[start][i], depth+1, start); } } int main(){ scanf("%d",&n); init(n); for(int i = 0;i<n-1;i++){ int a,b; scanf("%d %d",&a,&b); g[a].push_back(b); g[b].push_back(a); Union(a,b); } int blocks = countblock(); if (blocks!=1){ printf("Error: %d components",blocks); } else{ DFS(1, 1, -1); ans = temp; DFS(ans[0], 1, -1); for(int i = 0;i<temp.size();i++){ ans.push_back(temp[i]); } sort(ans.begin(),ans.end()); for(int i = 0;i<ans.size();i++){ if (ans[i]!=ans[i-1])printf("%d\n",ans[i]); } } return 0; }
//A1022 $ 不会 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> #include <set> #include <map> #include <string> using namespace std; int main(){ int n,m; map<string,set<int>>books; int tempid; string temp; scanf("%d",&n); for(int i = 0;i<n;i++){ scanf("%d%*c",&tempid); getline(cin,temp);books[temp].insert(tempid); getline(cin,temp);books[temp].insert(tempid); getline(cin,temp); int start = 0; for(int i = 0;i<temp.size();i++){ if (temp[i] == ' '){ books[temp.substr(start,i-start)].insert(tempid); start = i+1; } } books[temp.substr(start,temp.size()-start)].insert(tempid); getline(cin,temp);books[temp].insert(tempid); getline(cin,temp);books[temp].insert(tempid); } scanf("%d",&m); for(int i = 0;i<m;i++){ scanf("%d: ",&tempid); getline(cin,temp); cout<<tempid<<": "<<temp<<endl; if (books.find(temp) == books.end())printf("Not Found\n"); else{ for(set<int>::iterator it = books[temp].begin();it!=books[temp].end();it++){ printf("%07d\n",*it); } // cout<<1231<<endl; } } }
//A1024 $ 0 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; bool check (string a){ if (a.size() == 1) return true; for (int i = 0;i<a.size()/2+1;i++){ if (a[i]!=a[a.size()-1-i]) return false; } return true; } string plusn (string a){ string b = a; reverse(a.begin(), a.end()); // cout<<a<<' '<<b; string c; c.resize(a.size()+1); int p = 0; for(int i = (int)a.size()-1;i>=0;i--){ int temp = (int)(a[i]+b[i]+p - '0' - '0'); // cout<<temp<<endl; c[i+1] = (char)(temp % 10 +'0'); p = (temp - temp % 10) / 10; } if (p!=0){ c[0] = (char)( p +'0'); return c; } else { string d; d.resize(c.size()-1); for(int i = 0;i<c.size()-1;i++){ d[i] = c[i+1]; } return d; } } int main(){ int k; string a; // scanf("%s%d",&a,&k); cin>>a>>k; int count = 0; while(check(a)!=1 && count<k){ a = plusn(a); count += 1; } cout<<a<<"\n"<<count; // string a; // cin>>a; // cout<<plusn(a); }
//A1025 TODO 1/4 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; typedef struct { int score,localrank,rank,group; string id; }student; // NOTE 19 cmp 写法 bool cmp1(student a,student b){ if (a.group != b.group) return a.group < b.group; else return a.score>b.score; } bool cmp(student a,student b){ return a.score>b.score; } int main(){ int n; cin>>n; vector<student>students; for(int i = 0;i<n;i++){ int temp; cin>>temp; student tempstu; tempstu.id.resize(30); for(int j=0;j<temp;j++){ cin>>tempstu.id>>tempstu.score; tempstu.group = i+1; students.push_back(tempstu); } } sort(students.begin(), students.end(), cmp1); int count = 0; for(int i = 0;i<students.size();i++){ if (i>0){ if (students[i].group == students[i-1].group){ if (students[i].score!=students[i-1].score) students[i].localrank = i-count; else students[i].localrank = students[i-1].localrank; } else{ count = i; students[i].localrank = i-count; } } else{ students[i].localrank = 0; } } // for(int i = 0;i<students.size();i++){ // cout<<students[i].id<<' '<<students[i].score<<' '<<students[i].rank+1<<' '<<students[i].group<<' '<<students[i].localrank+1<<endl; // } sort(students.begin(), students.end(), cmp); for(int i = 0;i<students.size();i++){ if (i == 0) students[i].rank = i; if (students[i].score!=students[i-1].score) students[i].rank = i; else students[i].rank = students[i-1].rank; } cout<<students.size()<<endl; for(int i = 0;i<students.size();i++){ cout<<students[i].id<<' '<<students[i].rank+1<<' '<<students[i].group<<' '<<students[i].localrank+1<<endl; } return 0; }
//A1027 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int a,b,c; cin>>a>>b>>c; cout<<'#'; int result[6]={a/13,a-a/13*13,b/13,b-b/13*13,c/13,c-c/13*13}; for (int i = 0;i<6;i++){ if (result[i]<10) cout<<result[i]; else cout<<(char)(result[i]-10+'A'); } return 0; }
//A1028 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <string.h> #include <sstream> #include <iomanip> using namespace std; typedef struct { int id,score; char name[10]; //分配的太多不行!测试点6会有段错误 }stu; bool cmpid(stu a,stu b){ return a.id<b.id; } bool cmpscore(stu a,stu b){ if (a.score == b.score) return a.id<b.id; else return a.score<b.score; } bool cmpname(stu a,stu b){ if (strcmp(a.name,b.name) == 0) return a.id<b.id; else return strcmp(a.name,b.name)<0; //NOTE7 char数组要这样比大小 } int main(){ int n,k; cin>>n>>k; stu student[n]; for(int i = 0;i<n;i++){ scanf("%d %s %d",&student[i].id,student[i].name,&student[i].score); } switch (k){ case 1:sort(student, student+n, cmpid);break; case 2:sort(student, student+n, cmpname);break; case 3:sort(student, student+n, cmpscore);break; } for(int i = 0;i<n;i++){ cout<<setw(6)<<setfill('0')<<student[i].id<<' '<<student[i].name<<' '<<student[i].score<<endl; } return 0; }
//A1029 直接用long会爆内存…… TODO 8/9 还是有一个内存超限 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int lena,lenb; scanf("%d",&lena); int a[lena+1]; for(int i = 0;i<lena;i++){scanf("%d",&a[i]);} scanf("%d",&lenb); int b[lenb+1]; for(int i = 0;i<lenb;i++){scanf("%d",&b[i]);} // sort (a,a+lena); // sort (b,b+lenb); a[lena] = b[lenb] = 0x7fffffff; int median = (lena + lenb + 1)/2; int pa=0,pb=0,k=2; for(int i = 0;i<median;i++){ if (a[pa]<b[pb]){pa+=1;k=0;} else {pb+=1;k=1;} // if (a[pa]<b[pb]){cout<<a[pa]<<' ';pa+=1;k=0;} // else {cout<<b[pb]<<' ';pb+=1;k=1;} } if (k == 0){cout<<a[pa-1];} else if (k == 1){cout<<b[pb-1];} return 0; }
//A1030 $ 30/30 #include <cstdio> #include <vector> using namespace std; const int maxn = 510; const int INF = 0x3fffffff; struct node { int v,dis,cost; node(int _v,int _dis,int _cost):v(_v),dis(_dis),cost(_cost){}; }; int n,m,s,d; int dis[maxn],cost[maxn][maxn]; bool vis[maxn] = {false}; vector<node>adj[maxn]; vector<int>pre[maxn],best,tempbest; void Dj(int start){ fill(dis,dis+maxn,INF); dis[start] = 0; for(int ii = 0;ii<n;ii++){ int MIN = INF,k = -1; for(int i = 0;i<n;i++){ if (vis[i] == false && dis[i]<MIN){ k = i; MIN = dis[k]; } } if (k == -1)return;vis[k] = true; for(int i = 0;i<adj[k].size();i++){ int v = adj[k][i].v; if (dis[v] > dis[k] + adj[k][i].dis){ dis[v] = dis[k] + adj[k][i].dis; pre[v].clear(); pre[v].push_back(k); }else if (dis[v] == dis[k] + adj[k][i].dis){ pre[v].push_back(k); } } } } int getCost(){ int tempcost = 0; // printf("\n"); for(int i = 1;i<tempbest.size();i++){ tempcost += cost[tempbest[i-1]][tempbest[i]]; // printf("%d ",cost[tempbest[i-1]][tempbest[i]]); } // printf("tempcost=%d\n",tempcost); return tempcost; } int minCost = INF; void DFS(int k){ if (k == s){ tempbest.push_back(k); int temp = getCost(); if(temp<minCost){ minCost = temp; best = tempbest; } tempbest.pop_back(); return; } tempbest.push_back(k); for(int i = 0;i<pre[k].size();i++){ DFS(pre[k][i]); } tempbest.pop_back(); } int main(){ scanf("%d %d %d %d",&n,&m,&s,&d); for(int i = 0;i<m;i++){ int c1,c2,dis,tempcost; scanf("%d %d %d %d",&c1,&c2,&dis,&tempcost); adj[c1].push_back(node(c2,dis,tempcost)); adj[c2].push_back(node(c1,dis,tempcost)); cost[c1][c2] = cost[c2][c1] = tempcost; } Dj(s); // for(int i = 0;i<n;i++){ // printf("%d ",dis[i]); // }printf("\n"); // // for(int i = 0;i<n;i++){ // for(int j = 0;j<pre[i].size();j++){ // printf("%d ",pre[i][j]); // }printf("\n"); // } DFS(d); for(int i = 0;i<best.size();i++){ printf("%d ",best[best.size()-1-i]); } printf("%d %d",dis[d],minCost); }
//A1031 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ string a; cin>>a; int length = a.size(); int lines = (length+2)/3; //total lines(include last) int width = length - lines*2; //width-2 for (int i = 0;i<lines-1;i++){ cout<<a[i]; for(int j = 0;j<width;j++){ cout<<' '; } cout<<a[a.size()-1-i]<<endl; } for (int i = 0;i<width+2;i++){ cout<<a[lines-1+i]; } return 0; }
//A1032 不会 #include <stdio.h> #include <stdlib.h> using namespace std; struct node{ int data; int next; bool flag; }; int main(){ node a[100010]; int s1,s2,n; scanf("%d %d %d",&s1,&s2,&n); for (int i = 0;i<100010;i++){ a[i].flag = 0; } int add,next; for(int i = 0;i<n;i++){ scanf("%d %*c %d",&add,&next); a[add].next = next; } int p = s1; while(p!=-1){a[p].flag = 1;p = a[p].next;} p = s2; while(p!=-1){ if (a[p].flag == 1)break; p = a[p].next; } if (p!=-1)printf("%05d",p); else printf("-1"); return 0; }
//A1033 TODO 4/7 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; typedef struct{ double price,distance; } station; bool cmp(station a,station b){ if (abs(a.distance-b.distance)>0.01)return a.distance<b.distance; else return a.price<b.price; } bool cmp2(station a,station b){ if (abs(a.price-b.price)>0.01)return a.price<b.price; else return a.distance<b.distance; } int main(){ double cmax,distance,davg,n; scanf("%lf%lf%lf%lf",&cmax,&distance,&davg,&n); vector<station>gas; gas.resize(n); for(int i = 0;i<n;i++){scanf("%lf %lf",&gas[i].price,&gas[i].distance);} sort(gas.begin(), gas.end(), cmp); // cout<<endl; // for(int i = 0;i<n;i++){printf("%.2lf %.2lf\n",gas[i].price,gas[i].distance);} // cout<<endl; double maxdistance = 0,k = -1; double totalmoney = 0; int judgeall = 1; double nowleft = 0; for(int i = 0;i<n;i++){ if (i == k){ judgeall = 0; // 如果一开始0处没有,或者中间不够了,则judgeall=1,不输出money // 判断是否为最后一段路 if(distance < (cmax * davg + gas[i].distance)){ totalmoney += gas[i].price * ((distance-gas[i].distance) /davg-nowleft); // cout<<"\n money3+"<< gas[i].price * ((distance-gas[i].distance) /davg-nowleft)<<' '; break;} // 找到可达最便宜的 int judge = 0; double minprice = 100; for(int j = i+1;j<n;j++){ // cout<<" "<<gas[j].distance <<' '<< nowleft * davg<<endl;; if(gas[j].distance <= (nowleft * davg + cmax * davg + gas[i].distance)){ if (gas[j].price < minprice){minprice = gas[j].price;k = j;judge = 1; } } } // cout<<i<<' '<<gas[k].price<<' '<<gas[k].distance<<' '; if (judge == 0){printf("The maximum travel distance = %.2lf",maxdistance+cmax*davg);judgeall = 1;break;} if(minprice<gas[i].price){ // 后面有更便宜的,油加到那里即可 totalmoney += gas[i].price * ((gas[k].distance - gas[i].distance) /davg - nowleft); // cout<<"\n money1+"<< gas[i].price * ((gas[k].distance - gas[i].distance) /davg - nowleft)<<' '; nowleft = 0; } else{ //当前最便宜,加满 totalmoney += gas[i].price * (cmax - nowleft); nowleft = cmax - (gas[k].distance - gas[i].distance)/davg; // cout<<"\n money2+"<< gas[i].price * (cmax - nowleft)<<' '; } maxdistance += gas[k].distance - gas[i].distance; // cout<<totalmoney<<endl; } else if (k<0){ int sgn = 0; for(int j = 0;j<n;j++){if (gas[j].distance<0.00001)sgn = 1;} if (sgn == 1){k = 0;i-=1;} else {cout<<"The maximum travel distance = 0.00";break;} // 测试点2为没有0号加油站 } } if (judgeall == 0)printf("%.2lf",totalmoney); return 0; }
//A1034 $ 25/30 TODO 5/6 #include <cstdio> #include <vector> using namespace std; const int maxn = 50000; struct node { int v,w; node(int _v,int _w):v(_v),w(_w){} }; vector<node>adj[maxn]; int vis[maxn] = {0},nodeWeight[maxn] = {0},gs[maxn] = {0},gcount[maxn] = {0},gleader[maxn] ={-1},gleaderweight[maxn] ={0}; void DFS(int u,int depth,int group){ vis[u] = group; gcount[group]++; for(int i = 0;i<adj[u].size();i++){ gs[group] += adj[u][i].w/2; if (vis[adj[u][i].v] == 0) DFS(adj[u][i].v,depth+1,group); } } int DFSTravel(int n){ int group = 1; for(int i = 0;i<maxn;i++){ if (vis[i]==0 && adj[i].size()>0){ DFS(i,1,group); group +=1; } } return group; } void process(char a[],char b[],int w){ int anum = 0,bnum = 0; for(int i = 0;i<3;i++){ anum = anum*26 + (int)(a[i]-'A'); bnum = bnum*26 + (int)(b[i]-'A'); } // printf("%d,%d,%d\n",anum,bnum,w); adj[anum].push_back(node(bnum,w)); adj[bnum].push_back(node(anum,w)); } void getsum(int k){ int sum = 0; for(int i = 0;i<adj[k].size();i++){ sum += adj[k][i].w; } nodeWeight[k] = sum; } void str(int i,char c[4]){ int count = 2; while(count>=0){ int a = i%26; i = i/26; c[count--] = (char)(a+'A'); } } int main(){ int n,k; scanf("%d %d",&n,&k); for(int i = 0;i<n;i++){ char a[4],b[4]; int w; scanf("%s %s %d",a,b,&w); // printf("--%s,%s\n",a,b); process(a,b,w); } int group = DFSTravel(n); for(int i = 0;i<maxn;i++){ if (adj[i].size()!=0){ getsum(i); if (nodeWeight[i]>gleaderweight[vis[i]]){ gleaderweight[vis[i]] = nodeWeight[i]; gleader[vis[i]] = i; } } } // printf("gid glen id idTimes records"); // for(int i = 0;i<maxn;i++){ // if (adj[i].size()!=0){ // printf("\n%d %4d %6d %4d |%5d %2d ",vis[i],gcount[vis[i]],gleader[vis[i]],gs[vis[i]],i,nodeWeight[i]); // for(int j = 0;j<adj[i].size();j++){ // printf("%5d-%2d ",adj[i][j].v,adj[i][j].w); // } // } // } int countgroup = 0; for(int i = 0;i<group;i++){ if (gcount[i]>2 && gs[i]>k)countgroup++; } printf("%d\n",countgroup); for(int i = 0;i<group;i++){ if (gcount[i]>2 && gs[i]>k){ char c[4]; str(gleader[i],c); printf("%s %d\n",c,gcount[i]); } } return 0; }
//A1035 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> using namespace std; int main(){ int n; cin>>n; string a[n],b[n]; vector<int>c; c.resize(n); int sgn = 0,count = 0; for(int i = 0;i<n;i++){ cin>>a[i]>>b[i]; } for(int i = 0;i<n;i++){ for(int j = 0;j<b[i].size();j++){ if (b[i][j] == 'l') { b[i][j] = 'L'; c[i] = 1; sgn = 1;} if (b[i][j] == '1') { b[i][j] = '@'; c[i] = 1; sgn = 1;} if (b[i][j] == '0') { b[i][j] = '%'; c[i] = 1; sgn = 1;} if (b[i][j] == 'O') { b[i][j] = 'o'; c[i] = 1; sgn = 1;} } if (c[i] == 1) count++; } if (sgn == 0 && n == 1 ) cout<<"There is 1 account and no account is modified"; else if (sgn == 0 && n > 1 ) cout<<"There are "<<n<<" accounts and no account is modified"; else{ cout<<count<<endl; for(int i = 0;i<n;i++){ if (c[i]>0){ cout<<a[i]<<' '<<b[i]<<endl; } } } return 0; }
//A1036 // 一开始零分,是由于输入的问题。string输入需谨慎啊 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; typedef struct{ char name[20],class1[20]; int score; char gender; }man; bool cmp(man a,man b) { //'>'降序排序 //'<'升序排序 if(a.score>b.score) { return true; } return false; } int main(){ int n; cin>>n; man people[n]; for (int i = 0;i<n;i++){ scanf("%s %s %s %d" ,people[i].name,&people[i].gender,people[i].class1,&people[i].score); } sort(people, people+n,cmp); int m = 1,f = 1,k = 0,mi = 0,fi = 0; for(int i = 0;i<n;i++){ if(people[i].gender == 'F'){ cout<<people[i].name<<' '<<people[i].class1<<endl; fi = i; f = 0; break; } } if (f == 1){ cout<<"Absent"<<endl; k = 1; } for(int i = 0;i<n;i++){ if(people[n-1-i].gender == 'M'){ cout<<people[n-1-i].name<<' '<<people[n-1-i].class1<<endl; mi = n-1-i; m = 0; break; } } if (m == 1){ cout<<"Absent"<<endl; k = 1; } if(k == 1) cout<<"NA"; // else cout<<people[fi].score<<' '<<people[mi].score<<abs(people[fi].score-people[mi].score); else cout<<abs(people[fi].score-people[mi].score); return 0; }
//A1036 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; typedef struct{ char name[20],class1[20]; int score; }man; bool cmp(man a,man b) { //'>'降序排序 //'<'升序排序 if(a.score>b.score) { return true; } return false; } int main(){ int n; cin>>n; man tmp,m,f; char gender; m.score = 101; f.score = -1; for (int i = 0;i<n;i++){ scanf("%s %c %s %d" ,tmp.name,&gender,tmp.class1,&tmp.score); //NOTE1 if(gender == 'F' && tmp.score>f.score) f = tmp; else if(gender == 'M' && tmp.score<m.score) m = tmp; } if (f.score == -1) cout<<"Absent"; else cout<<f.name<<' '<<f.class1; cout<<endl; if (m.score == 101) cout<<"Absent"; else cout<<m.name<<' '<<m.class1; cout<<endl; if (m.score == 101 || f.score == -1)cout<<"NA"; else cout<<abs(f.score-m.score); return 0; }
//A1037 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; bool cmpmax(int a,int b){return a>b;} int main(){ int n,m; cin>>n; vector<int>a;a.resize(n); for(int i = 0;i<n;i++){scanf("%d",&a[i]);} cin>>m; vector<int>b;b.resize(m); for(int i = 0;i<m;i++){scanf("%d",&b[i]);} sort(a.begin(),a.end(),cmpmax); sort(b.begin(),b.end(),cmpmax); int length = 0,amount = 0; if (m<n)length = m; else length = n; for(int i = 0;i<length;i++){ if(a[i]>0&&b[i]>0)amount+=a[i]*b[i]; else break; // cout<<amount<<' '; } for(int i = 0;i<length;i++){ if(a[n-i-1]<0&&b[m-i-1]<0)amount+=a[n-i-1]*b[m-i-1]; else break; // cout<<amount<<' '; } cout<<amount; return 0; }
//A1038 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; bool cmp(string a,string b){ return a+b<b+a; // 妙!!! } int main(){ int n; cin>>n; vector<string>a; a.resize(n); for(int i = 0;i<n;i++){ cin>>a[i]; } sort(a.begin(),a.end(),cmp); int judge = 0; for(int i = 0;i<n;i++){ if (judge == 0){ for(int j= 0;j<a[0].size();j++){ if (a[0][j] == '0' && judge == 0)continue; else {judge = 1;printf("%c",a[0][j]);} } } else cout<<a[i]; } if (judge == 0)cout<<0; return 0; }
//A1039 $ 3/6 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; const int maxnum = 26*26*26*10+1; int convert(char temp[]){ int result = 0; for(int i = 0;i<3;i++){ result = result * 26 + (int)(temp[i] - 'A');} result = result * 10 +(int)(temp[3] - '0'); return result; } int main(){ int n,k; scanf("%d%d",&n,&k); vector<int>students[maxnum]; // NOTE 13 vector 数组 for(int i = 0;i<k;i++){ int cnum,cstudents; scanf("%d%d",&cnum,&cstudents); for(int j = 0;j<cstudents;j++){ char n[100]; scanf("%s",n); students[convert(n)].push_back(cnum); } } for(int i = 0;i<n;i++){ char temp[20]; scanf("%s",temp); int id = convert(temp); printf("%s %d",temp,(int)students[id].size()); sort(students[id].begin(),students[id].end()); for(int j = 0;j<students[id].size();j++){ printf(" %d",students[id][j]); } if (i<n-1) printf("\n"); } return 0; }
//A1040 $ 0/25 编译错误 PAT 不能用 gets() #include <cstdio> #include <cstring> #include <iostream> using namespace std; const int maxn = 1010; char S[maxn]; int dp[maxn][maxn] = {}; int main(){ cin.getline(S,maxn); int len = (int)strlen(S),ans = 1; for(int i = 0;i<len;i++){ dp[i][i] = 1; if (i<len-1 && S[i] == S[i+1]){ dp[i][i+1] = 1; ans = 2; } } for (int L = 3;L<=len;L++){ for(int i = 0;i+L-1<len;i++){ int j = i+L-1; if (S[i] == S[j] && dp[i+1][j-1] == 1){ dp[i][j] = 1; ans = L; } } } printf("%d",ans); return 0; }
//A1041 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ int n; cin>>n; int num[100001] = {}; int input[n]; for(int i = 0;i<n;i++){ int a; scanf("%d",&a); input[i] = a; num[a]+=1; } int judge = 0; for(int i = 0;i<n;i++){ if (num[input[i]]==1){cout<<input[i];judge = 1;break;} } if (judge == 0)cout<<"None"; return 0; }
//A1043 $ 不会 #include <cstdio> #include <vector> using namespace std; vector<int>pre,preM,post,postM,origin; int countn,n; struct node{ int data; node* lchild; node* rchild; }*root; void insert(node* &root,int data){ if (root == NULL){ root = new node; root ->data = data; root ->lchild = root->rchild = NULL; return; } if (data >= root->data)insert(root->rchild,data); // 这里必须尽量r放在右,否则出错 else insert(root->lchild, data); } void preOrder(node* root,vector <int>&vi){ if (root == NULL) return; vi.push_back(root->data); preOrder(root->lchild,vi); preOrder(root->rchild,vi); } void preOrderM(node* root,vector <int>&vi){ if (root == NULL) return; vi.push_back(root->data); preOrderM(root->rchild,vi); preOrderM(root->lchild,vi); } void postOrder(node* root,vector <int>&vi){ if (root == NULL) return; postOrder(root->lchild,vi); postOrder(root->rchild,vi); vi.push_back(root->data); } void postOrderM(node* root,vector <int>&vi){ if (root == NULL) return; postOrderM(root->rchild,vi); postOrderM(root->lchild,vi); vi.push_back(root->data); } int main(){ scanf("%d",&n); origin.resize(n); node* root = NULL; for(int i = 0;i<n;i++){ scanf("%d",&origin[i]); insert(root, origin[i]); } preOrder(root,pre); preOrderM(root,preM); postOrder(root,post); postOrderM(root,postM); // for (int i = 0;i<n;i++){printf("%d ",pre[i]);} // printf("\n"); // for (int i = 0;i<n;i++){printf("%d ",preM[i]);} // printf("\n"); // for (int i = 0;i<n;i++){printf("%d ",post[i]);} // printf("\n"); // for (int i = 0;i<n;i++){printf("%d ",postM[i]);} // printf("\n"); if (origin == pre){ printf("YES\n"); for (int i = 0;i<n;i++){ printf("%d",post[i]); if (i<n-1)printf(" "); } printf("\n"); } else if (origin == preM){ printf("YES\n"); for (int i = 0;i<n;i++){ printf("%d",postM[i]); if (i<n-1)printf(" "); } printf("\n"); } else printf("NO"); return 0; }
//A1044 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ int n,m; cin>>n>>m; vector<int>a;a.resize(n); vector<int>b;b.resize(n+1); // 数组长度不足,测试点1会有“运行时错误” vector<int>result;result.resize(n+1); vector<int>resultpos;resultpos.resize(n+1); int temp = 0; // 这里 temp 用来装 b b[0] = 0; for(int i = 0;i<n;i++){ scanf("%d",&a[i]); temp+=a[i]; b[i+1] = temp; } // cout<<endl; // 这里开始 temp 作为最小接近 m 的和 for(int i = 0;i<n;i++){ resultpos[i] = (int)(lower_bound(b.begin()+i, b.end(), (m+b[i])) - b.begin()); result[i] = b[resultpos[i]] - b[i]; if (result[i]<temp && result[i]>=m) temp = result[i]; } for(int i = 0;i<n;i++){ // printf("%d %d %d %d\n",a[i],b[i],result[i],resultpos[i]); if (result[i]==temp) printf("%d-%d\n",i+1,resultpos[i]); } return 0; }
//A1045 $ 24/25 LIS方法 #include <cstdio> #include <algorithm> using namespace std; int main(){ int n,m,l; scanf("%d %d",&n,&m); int hashtable[n+1]; // 颜色序号从1开始!记得是n+1!测试点3错误! fill(hashtable, hashtable+n+1, -1); for(int i = 0;i<m;i++){ int temp; scanf("%d",&temp); hashtable[temp] = i; } scanf("%d",&l); int a[l],dp[l]; int count = 0; for(int i = 0;i<l;i++){ int temp; scanf("%d",&temp); if (hashtable[temp] > -1)a[count++] = hashtable[temp]; } int ans = -1; for(int i = 0;i<count;i++){ dp[i] = 1; for(int j = 0;j<i;j++){ if (a[j] <= a[i] && dp[j] + 1 > dp[i]){ dp[i] = dp[j] + 1; } } ans = max(ans,dp[i]); } printf("%d",ans); return 0; }
//A1045 LCS方法 $ 18/25 #include <cstdio> #include <algorithm> using namespace std; int main(){ int n,m,l; scanf("%d %d",&n,&m); int a[m+1]; for(int i = 1;i<m+1;i++){ scanf("%d",&a[i]); } scanf("%d",&l); int b[l+1]; for(int i = 1;i<l+1;i++){ scanf("%d",&b[i]); } int dp[m+1][l+1]; fill(dp[0]+1, dp[0]+(m+1)*(l+1)+1, 0); for (int i = 1;i<m+1;i++){ for(int j = 1;j<l+1;j++){ int maxk = max(dp[i-1][j],dp[i][j-1]); if (a[i] == b[j]){ dp[i][j] = maxk + 1; }else{ dp[i][j] = maxk; } } } printf("%d",dp[m][l]); return 0; }
//A1047 $ 4/4 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; const int maxnum = 26*26*26*10+1; int convert(char temp[]){ int result = 0; for(int i = 0;i<3;i++){ result = result * 26 + (int)(temp[i] - 'A');} result = result * 10 +(int)(temp[3] - '0'); return result; } void convertchar(int id,char result[]){ result[3] = (char)(id % 10 + '0'); id = id/10; result[2] = (char)(id % 26 + 'A'); id /= 26; result[1] = (char)(id % 26 + 'A'); id /= 26; result[0] = (char)(id + 'A'); // printf("%s",result); } int main(){ int n,k; scanf("%d %d",&n,&k); vector<int>classes[k]; for(int i = 0;i<n;i++){ char temp[20]; int temp2; scanf("%s %d",temp,&temp2); int id = convert(temp); for(int j = 0;j<temp2;j++){ int cid; scanf("%d",&cid); classes[cid-1].push_back(id); } } for(int i = 0;i<k;i++){ printf("%d %d\n",i+1,(int)classes[i].size()); sort(classes[i].begin(),classes[i].end()); for(int j = 0;j<classes[i].size();j++){ // printf("%d ",classes[i][j]); char temp[20]; convertchar(classes[i][j],temp); printf("%s\n",temp); } } return 0; }
//A1048 hash 方法 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ int n,m; cin>>n>>m; int hashtable[1005] = {}; //如果只分配500,m-coin可能就越界了! int coin[n]; int temp; for(int i = 0;i<n;i++){ cin>>temp; coin[i] = temp; hashtable[temp] += 1; } sort(coin,coin+n); for(int i = 0;i<n;i++){ if ((coin[i])>(m/2)) break; if (hashtable[m-coin[i]] >= 1){ if (coin[i] == m-coin[i]){ if (hashtable[coin[i]]>=2){ cout<<coin[i]<<' '<<m-coin[i]; return 0;} else break; } cout<<coin[i]<<' '<<m-coin[i]; return 0; } } cout<<"No Solution"; return 0; }
//A1048 二分查找方法 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ int n,m; cin>>n>>m; int coin[n]; int temp; for(int i = 0;i<n;i++){ cin>>temp; coin[i] = temp; } sort(coin,coin+n); for(int i = 0;i<n;i++){ int pos = (int)(upper_bound(coin+i+1, coin+n, m-coin[i])-coin-1); // cout<<i<<' '<<pos<<' '<<coin [i]<<' '<<coin[pos]<<endl; if (coin[pos]+coin[i]==m && i!=pos){ cout<<coin[i]<<' '<<coin[pos]<<endl; return 0; } } cout<<"No Solution"; return 0; }
//A1048 TwoPointer #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ int n,m; cin>>n>>m; vector<int>coin; coin.resize(n); for(int i = 0;i<n;i++){scanf("%d",&coin[i]);} sort(coin.begin(),coin.end()); // coin.erase(unique(coin.begin(), coin.end()), coin.end());//NOTE 10 数组去重 // for(int i = 0;i<n;i++){printf("%d ",coin[i]);} // cout<<endl; int i=0,j=n-1,judge = 0,k=1; while(i<j){ // cout<<coin[i]<<' '<<coin[j]<<endl; k = 1; if((coin[i]+coin[j])==m){cout<<coin[i]<<' '<<coin[j];return 0;} else if((coin[i]+coin[j])>m){ j-=1; } else{ i+=1; } } cout<<"No Solution"; return 0; }
//A1049 $ 4/7 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ string n; cin>>n; vector<int>a;a.resize(n.size());a[0] = 0; for(int i = 0;i<n.size();i++){a[i] = (int)(n[i]-'0');} int count = 0; for(int i = 0;i<a.size();i++){ int b4 = a[0]; for(int j = 1;j<i;j++){ b4 = b4 * 10 + a[j]; } if (a[i]>1){ if (i == 0){count += pow(10, (a.size()-1-i));} else {count+= pow(10, (a.size()-1-i)) * (b4+1);} } else if (a[i] == 1){ int after = 0; for(int j = i+1;j<a.size();j++){ after = after * 10 + a[j]; } if (i == 0){count += after+1;} else {count+= pow(10, (a.size()-1-i)) * (b4)+ after + 1;} } } cout<<count; return 0; }
//A1049 $ AC 题解的做法 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ int n; cin>>n; int a = 1, ans = 0; int left, right, now; while(n/a!=0){ left = n/(a*10); now = n/a % 10; right = n % a; if (now == 0)ans += left *a; else if (now == 1)ans += left * a + right + 1; else ans += (left + 1) *a; a*= 10; } cout<<ans; return 0; }
//A1050 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> using namespace std; int main(){ int hashtable[128] = {}; string a,b; getline(cin,a); //NOTE10 输入整行文字 getline(cin,b); for(int i = 0;i<b.size();i++){hashtable[(int)b[i]] = 1;} // 这里若是写成 i<strlen(b),将是O(n^2)复杂度! for(int i = 0;i<a.size();i++){ if (hashtable[(int)a[i]] == 0)cout<<a[i]; } return 0; }
//A1051 $ 4/6 #include <stack> #include <cstdio> #include <vector> using namespace std; int main(){ int m,n,k; scanf("%d %d %d",&m,&n,&k); for (int i = 0;i<k;i++){ bool flag = true; stack<int>st; while(!st.empty()){st.pop();} int temp = 0; vector<int>a(n); // 这个直接写成7了!粗心! for(int k = 0;k<n;k++){scanf("%d",&a[k]);} for(int j = 1;j<n+1;){ st.push(j++); if (st.size()>m){flag = false;} while (!st.empty() && st.top() == a[temp] && st.size()<=m){ st.pop(); temp++; } } if ((!st.empty()) || flag == false)printf("NO\n"); else printf("YES\n"); } }
//A1052 $ 2/5 #include <stdio.h> #include <stdlib.h> #include <algorithm> using namespace std; struct node{ int key = 1000000; int next,add; int judge = 0; }; bool cmp(node a,node b){ if (a.judge == 0 || b.judge == 0)return a.judge>b.judge; else return a.key<b.key; } int main(){ node a[100010]; int n,head; scanf("%d %d",&n,&head); int key,add,next; // for (int i = 0;i<100010;i++){ // a[i].key = 1000000; // a[i].judge = 0; // } for(int i = 0;i<n;i++){ scanf("%d %d %d",&add,&key,&next); a[add].key = key; a[add].add = add; a[add].next = next; } int p = head,count = 0; // 有可能有无效结点! while(p!=-1){ a[p].judge = 1; p = a[p].next; count ++; } if (count == 0){printf("0 -1");return 0;} // 测试点5 sort(a,a+100010,cmp); printf("%d %05d\n",count,a[0].add); for(int i = 0;i<count;i++){ // 因此这里是count if (i<count-1){ printf("%05d %d %05d\n",a[i].add,a[i].key,a[i+1].add);} else printf("%05d %d -1\n",a[i].add,a[i].key); } return 0; }
//A1053 $ 3/6 #include <vector> #include <cstdio> #include <algorithm> using namespace std; int n,m,s; struct Node { int weight; vector<int>child; }; vector<Node>tree; vector<int>temp; vector<vector<int>>ans; void DFS(int &root,int &sum){ // printf("%d %d\n",root,sum); if (tree[root].child.size() == 0 || sum >= s){ if (sum == s && tree[root].child.size() == 0){ ans.push_back(temp); } if(temp.size()>0){ // 这个if为了防止只有一个节点的情况! sum -= tree[temp[temp.size()-1]].weight;} temp.pop_back(); return; } for(int i = 0;i<tree[root].child.size();i++){ temp.push_back(tree[root].child[i]); sum += tree[tree[root].child[i]].weight; DFS(tree[root].child[i],sum); } sum -= tree[root].weight; temp.pop_back(); } bool cmp(vector<int>a,vector<int>b){ int i = 0; while(tree[a[i]].weight == tree[b[i]].weight && i<a.size()-1 && i<b.size()-1){ // 这里要 <size!否则越界 i++; } return tree[a[i]].weight > tree[b[i]].weight; } int main(){ scanf("%d %d %d",&n,&m,&s); tree.resize(n); for(int i = 0;i<n;i++){scanf("%d",&tree[i].weight);} for(int i = 0;i<m;i++){ int num,childsize; scanf("%d %d",&num,&childsize); tree[num].child.resize(childsize); for(int j = 0;j<childsize;j++){ scanf("%d",&tree[num].child[j]); } } // for(int i = 0;i<n;i++){ // printf("%d %d ",i,tree[i].weight); // for(int j = 0;j<tree[i].child.size();j++){ // printf(" %d",tree[i].child[j]); // } // printf("\n"); // } int sum = tree[0].weight; int root = 0; DFS(root, sum); sort(ans.begin(), ans.end(), cmp); for(int i = 0;i<ans.size();i++){ printf("%d",tree[0].weight); for(int j = 0;j<ans[i].size();j++){ printf(" %d",tree[ans[i][j]].weight); } printf("\n"); } return 0; }
//A1054 $ 5/5 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> #include <map> #include <string> using namespace std; int main(){ int m,n; scanf("%d%d",&m,&n); vector<int>screen(n*m); map<int,int>count; for(int i = 0;i<n*m;i++){ scanf("%d",&screen[i]); count[screen[i]] = 0; } for(int i = 0;i<n*m;i++){ count[screen[i]] += 1; } // 我感觉这样要比screen.find()初始化更快 int max = 0,maxpos = 0; for(int i = 0;i<n*m;i++){ if (count[screen[i]] > max){ max = count[screen[i]]; maxpos = screen[i]; } } printf("%d",maxpos); return 0; }
//A1055 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; typedef struct{ string name; int age,money; } bill; bool cmp(bill a,bill b){ if (a.money!=b.money){return a.money>b.money;} else if (a.age!=b.age){return a.age<b.age;} return a.name<b.name; } int main(){ int n,k; cin>>n>>k; vector <bill>people; people.resize(n); int query[k][3]; for(int i = 0;i<n;i++){ people[i].name.resize(20); scanf("%s %d %d",&people[i].name[0],&people[i].age,&people[i].money); } for(int i = 0;i<k;i++){ scanf("%d%d%d",&query[i][0],&query[i][1],&query[i][2]); } sort(people.begin(),people.end(),cmp); // M范围在100以内,因此同一年龄只取财富前100保留 int valid[1000] = {}; vector<bill>peoples; for(int i = 0;i<n;i++){ if (valid[people[i].age]<100) { peoples.push_back(people[i]); valid[people[i].age] += 1;} } for(int i = 0;i<k;i++){ printf("Case #%d:\n",i+1); int judge = 0; for(int j = 0;j<peoples.size();j++){ if (peoples[j].age<=query[i][2] && peoples[j].age>=query[i][1] && judge < query[i][0]){ printf("%s %d %d\n",peoples[j].name.c_str(),peoples[j].age,peoples[j].money); judge++; } if (judge == query[i][0])break; } if (judge == 0){ printf("None"); } } return 0; }
//A1056 $ 2/6 TODO 2/6 //https://pintia.cn/problem-sets/994805342720868352/problems/994805419468242944 //11 3 // 0 1 2 3 4 5 6 7 8 9 10 //25 18 0 46 37 3 19 22 57 56 10 // 6 0 8 7 10 5 9 1 4 2 3 // //19 25 57 22 10 3 56 18 37 0 46 // 57 22 56 46 // 57 46 // // 5 5 5 2 5 5 5 3 1 3 5 #include <cstdio> #include <vector> #include <algorithm> #include <iostream> using namespace std; struct man{ int num = 0,rank; bool win = true; }; int main(){ int np,ng; scanf("%d %d",&np,&ng); vector<man>a(np); // 输入顺序 vector<int>turn(np); // 比赛的输入顺序 vector<int>rturn(np); // hash 从比赛顺序反推学号 for(int i = 0;i<np;i++){scanf("%d",&a[i].num);} for(int i = 0;i<np;i++){ scanf("%d",&turn[i]); rturn[turn[i]] = i; } vector<man>b(np); // 比赛顺序 for(int i = 0;i<np;i+=1){b[i] = a[turn[i]];} vector<man>temp(3); int pos[3]; int sgn = 1; int asd = 10; while (sgn !=0 && asd-- >0){ int count = 0,countall = 0; for(int i = 0;i<np;i++){ // printf("%4d",b[i].num); if (b[i].win == true){ temp[count] = b[i]; pos[count] = i; count++;countall++; } if (count == 3 || i == np-1 ){ count = 0; if (temp[0].num == max(temp[0].num,max(temp[1].num,temp[2].num))){ b[pos[1]].win = 0;b[pos[2]].win = 0; } else if (temp[1].num == max(temp[0].num,max(temp[1].num,temp[2].num))){ b[pos[0]].win = 0;b[pos[2]].win = 0; } else {b[pos[0]].win = 0;b[pos[1]].win = 0;} temp.clear(); temp[0].num = 0; temp[1].num = 0; temp[2].num = 0; } } // cout<<endl; for(int i = 0;i<np;i++){ if(b[i].win == 0 && b[i].rank == 0){ b[i].rank = (countall+2)/3+1; } else if (b[i].win == 1 && b[i].rank == 0 && countall == 1){ sgn = 0; b[i].rank = 1; break; } } // for(int i = 0;i<np;i++){ // printf("%4d",b[i].rank); // } // cout<<endl; // for(int i = 0;i<np;i++){ // printf("%4d",b[i].win); // } // cout<<endl; // for(int i = 0;i<np;i++){ // printf("%4d",b[rturn[i]].rank); // } // cout<<endl; // printf("%d",countall); // cout<<endl; } for(int i = 0;i<np;i++){ printf("%d",b[rturn[i]].rank); if (i<np-1){printf(" ");} } cout<<endl; return 0; } A1057 #include <vector> #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; vector<int>stack; int process(char c[]){ int ans = 0,len = (int)strlen(c); for(int i = 5;i<len;i++){ ans = ans * 10 + c[i]-'0'; } return ans; } int getmedian(int p){ vector<int>a = stack; sort(a.begin(),a.end()); return a[p/2]; } int main(){ int n; scanf("%d%*c",&n); while (n-- >= 0){ int p = (int)stack.size()-1; char c[20]; cin.getline(c,20); if (c[1] == 'o'){ if (p == -1)printf("Invalid\n"); else { printf("%d\n",stack[p]); stack.erase(stack.begin()+p); } } else if (c[1] == 'u'){ int t; t = process(c); stack.push_back(t); } else if (c[1] == 'e'){ if (p == -1)printf("Invalid\n"); else { printf("%d\n",getmedian(p)); } } } return 0; }
//A1058 Notice the realm of int and longlong! #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ long long g1,s1,k1,g2,s2,k2,g3,s3,k3; scanf("%lld.%lld.%lld %lld.%lld.%lld",&g1,&s1,&k1,&g2,&s2,&k2); long long sum1,sum2,diff; sum1 = g1 * 17 * 29 + s1 * 29 + k1; sum2 = g2 * 17 * 29 + s2 * 29 + k2; diff = sum1+sum2; g3 = diff/(17*29); s3 = (diff-g3*17*29)/29; k3 = diff - g3 * 17 * 29 - s3 * 29; printf("%lld.%lld.%lld",g3,s3,k3); return 0; }
//A1059 $ 4/5 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; typedef long long LL; const int maxsize = 10000; vector<bool>hashtable(maxsize,true); vector<LL>prime; // NOTE 12 vector 传参 void getPrime(LL n,vector<LL>&prime){ hashtable[0] = false; hashtable[1] = false; for(int i = 2;i<n;i++){ if (hashtable[i] == true){ for (int j = 2;j<n/i+1 && j<maxsize/i+1;j+=1){ hashtable[j*i] = false;} } } for(int i = 0;i<n;i++){ if (hashtable[i] == true)prime.push_back(i); } } int main(){ LL n; scanf("%lld",&n); if (n>1){ // 测试点3,1要输出“1=1”!! getPrime((LL)sqrt(1.0 * n),prime); vector<int>countprime(prime.size(),0); int judge = 0; LL m=n; for(int i = 0;i<prime.size();i++){ if (n % prime[i] == 0){ n /= prime[i]; countprime[i]++; judge = i; i --; } } if (n!= 1){prime.push_back(n);countprime.push_back(1);} printf("%lld=",m); for(int i = 0;i<prime.size();i++){ if (countprime[i] == 1){ printf("%lld",prime[i]); } else if (countprime[i] > 1){ printf("%lld^%d",prime[i],countprime[i]); } if (countprime[i] > 0 && i!= judge)printf("*"); } } else{printf("1=1");} return 0; }
//A1060 $ 1/7 // 前两个测试点不带小数点 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> #include <set> using namespace std; string convert(string a,int k,int &length){ // 去掉前面的0 int temp = 0,judge1 = 0; for(int i = 0;i<a.size();i++){ if (a[i]!='0'){temp = i;judge1 = 1;break;} } a = a.substr(temp,a.size()-temp); // cout<<a<<endl; // 找到小数点位 int dotpos; if (a.find(".") != string::npos) { dotpos = (int)a.find("."); if (dotpos == 0){ int judge0 = 0; for (int i = 1; i<a.size(); i++) { if (a[i]!='0'){length = 1-i;judge0 = 1;break;} } if (judge0 == 0)length = 0; } else{ length = dotpos; } } else {length = (int)a.size();} if (judge1 == 0){length = 0;} // 最后一个测试点 避免0000的位数出现错误 string result; dotpos = (int)a.find("."); if (dotpos != string::npos) a.erase(a.begin()+dotpos); int start = 0; while(a[start]=='0'){start++;} result = a.substr(start,k); while (result.length()<k) {result = result + "0";} return result; } int main(){ int n,alength,blength; string a,b; scanf("%d",&n); cin>>a>>b; string resa = convert(a, n, alength); string resb = convert(b, n, blength); if (resa == resb && alength == blength) cout<<"YES 0."<<resa<<"*10^"<<alength; else{ cout<<"NO 0."<<resa<<"*10^"<<alength; cout<<" 0."<<resb<<"*10^"<<blength; } return 0; }
//A1063 $ 5/5 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> #include <set> using namespace std; double similarity(set<int>a,set<int>b){ int same = 0; // printf("%d %d",a.size(),b.size()); for(set<int>::iterator it = a.begin();it!=a.end();it++){ if (b.find(*it)!=b.end())same++; // NOTE14 set 判断元素是否存在 } int diff = (int)(a.size()+b.size()) - same; // printf(" %d %d",same,diff); return (double)(same*1.0/diff); } int main(){ int n; scanf("%d",&n); set<int> st[n]; for(int i = 0;i<n;i++){ int temp,temp1; scanf("%d",&temp); for(int j = 0;j<temp;j++){ scanf("%d",&temp1); st[i].insert(temp1); } } scanf("%d",&n); for(int i = 0;i<n;i++){ int temp,temp1; double simi; scanf("%d %d",&temp,&temp1); simi = similarity(st[temp-1], st[temp1-1]); printf("%.01lf%%\n",simi*100); // NOTE15 printf 打印% } return 0; } // A1064 $ 不会 4/6 #include <vector> #include <cstdio> #include <algorithm> using namespace std; int n,countn = 0; vector<int>tree; vector<int>v; void inorder(int root){ if (root>n)return; inorder(2 * root); tree[root] = v[countn++]; inorder(2 * root + 1); } int main(){ scanf("%d",&n); v.resize(n);tree.resize(n+1); // tree.size(n)就会有运行时错误,原来运行时错误和段错误差不多 for (int i = 0;i<n;i++){ scanf("%d",&v[i]); } sort(v.begin(), v.end()); inorder(1); for(int i = 1;i<n+1;i++){ printf("%d",tree[i]); if (i<n)printf(" "); } return 0; }
//A1066 $ 25/25 #include <cstdio> #include <vector> using namespace std; struct node{ int data,height; node *lchild, *rchild; }*root; node* newNode(int v){ node *Node = new node; Node->data = v; Node->height = 1; Node->lchild = Node->rchild = NULL; return Node; } // 获得根结点高度 int getHeight(node* root){ if (root == NULL)return 0; return root-> height; } int getBalanceFactor(node* root){ return getHeight(root->lchild) - getHeight(root->rchild); } // 更新根节点高度 void updateHeight(node* root){ root->height = max(getHeight(root->lchild),getHeight(root->rchild)) + 1; } //左旋 void L(node* &root){ node* temp = root->rchild; root->rchild = temp->lchild; temp->lchild = root; updateHeight(root); updateHeight(temp); root = temp; } //右旋 void R(node* &root){ node* temp = root->lchild; root->lchild = temp->rchild; temp->rchild = root; updateHeight(root); updateHeight(temp); root = temp; } void insert(node* &root,int v){ if (root == NULL){ root = newNode(v); return; } if (v < root->data){ insert(root->lchild,v); updateHeight(root); if (getBalanceFactor(root) == 2){ if (getBalanceFactor(root->lchild) == 1){ R(root); } else if (getBalanceFactor(root->lchild) == -1){ L(root->lchild); R(root); } } } else{ insert(root->rchild,v); updateHeight(root); if (getBalanceFactor(root) == -2){ if (getBalanceFactor(root->rchild) == -1){ L(root); } else if (getBalanceFactor(root->rchild) == 1){ R(root->rchild); L(root); } } } } node* create(int data[],int n){ node* root = NULL; for(int i = 0;i<n;i++){ insert(root,data[i]); } return root; } int main(){ int n,tree[20]; scanf("%d",&n); for(int i = 0;i<n;i++){scanf("%d",&tree[i]);} node* root = create(tree, n); printf("%d",root->data); return 0; }
//A1067 5/6 timeout #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; int main(){ int n,count=0,judge = 0; cin>>n; vector<int>a; vector<int>position; a.resize(n); position.resize(n); for(int i = 0;i<n;i++){scanf("%d",&a[i]);position[a[i]] = i;} for(int i = 0;i<n;i++){ if (a[0] == 0){ judge = 0; for(int j =1;j<n;j++){ if (a[j]!=j){ swap(a[0], a[j]); position[0] = j; position[a[0]] = 0; count+=1; judge = 1;break;} } if (judge == 0)break; } swap(a[position[position[0]]],a[position[0]]); swap(position[position[0]],position[0]); count++; // for(int i = 0;i<n;i++){cout<<a[i]<<' ';} // cout<<endl; // for(int i = 0;i<n;i++){cout<<position[i]<<' ';} // cout<<endl<<endl; } cout<<count; return 0; }
//A1068 $ 不会 TODO #include <cstdio> #include <algorithm> using namespace std; const int maxn = 10010; const int maxv = 110; int w[maxn], dp[maxn] = {}; bool choice[maxn][maxv]; bool cmp(int a,int b){return a>b;} int main(){ int n,m; scanf("%d %d",&n,&m); int a[n]; for(int i = 1;i<=n;i++){ scanf("%d",&a[i]); } sort(w+1,w+n+1,cmp); return 0; }
//A1071 $ 4/5 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <cstring> #include <cstdio> #include <sstream> #include <iomanip> #include <map> #include <string> using namespace std; bool cmp(const pair<string,int>& a,const pair<string,int>& b){ if (a.second != b.second)return a.second > b.second; else return a.first<b.first; } int main(){ string str; getline(cin,str); map<string,int>count; int start = 0,end = (int)str.size()-1,judge = 0; // 初始化 map for(int i = 0;i<str.size();i++){ if ((str[i]>='0'&&str[i]<='9') || (str[i]>='a'&&str[i]<='z') || (str[i]>='A'&&str[i]<='Z')){ if (judge == 0){start = i;judge = 1;} } else{ end = i; string temp = str.substr(start,end-start); transform(temp.begin(), temp.end(), temp.begin(), ::tolower); // NOTE 17 STL string 大小写转换 count[temp] = 0; judge = 0; } } if (judge == 1){ // 最后一段收录!测试点4 “a” end = (int)str.size(); string temp = str.substr(start,end-start); transform(temp.begin(), temp.end(), temp.begin(), ::tolower); count[temp] = 0; } // 遍历填数 for(int i = 0;i<str.size();i++){ if ((str[i]>='0'&&str[i]<='9') || (str[i]>='a'&&str[i]<='z') || (str[i]>='A'&&str[i]<='Z')){ if (judge == 0){start = i;judge = 1;} } else{ end = i; string temp = str.substr(start,end-start); transform(temp.begin(), temp.end(), temp.begin(), ::tolower); count[temp] ++; judge = 0; } } if (judge == 1){ end = (int)str.size(); string temp = str.substr(start,end-start); transform(temp.begin(), temp.end(), temp.begin(), ::tolower); count[temp] ++; } int max = 0; string maxstr; // for(map<string, int>::iterator it = count.begin();it!=count.end();it++){ // if (max<it->second){ // max = it->second; // maxstr = it->first; // } // } // for(map<string,int>::iterator it = count.begin();it!=count.end();it++){ // cout<<it->first<<' '<<it->second<<endl; // } // NOTE 18 map 按照 value 排序: // 将map中的key和value分别存放在一个pair类型的vector中,然后利用vector的sort函数排序: vector<pair<string,int>> count2(count.begin(), count.end()); sort(count2.begin(),count2.end(),cmp); max = count2.begin()->second; maxstr = count2.begin()->first; cout<<maxstr; printf(" %d",max); return 0; }
//A1072 $ 6/30 #include <cstdio> #include <vector> #include <math.h> #include <cstring> using namespace std; const int maxn = 1021; const int INF = 0x3fffffff; struct edge { int v,length; edge(int _a,int _b):v(_a),length(_b){}; }; vector<edge>adj[maxn]; int n,m,k,ds,dis[maxn]; bool vis[maxn]; void DFS(int start,int total){ fill(dis, dis+maxn, INF); fill(vis, vis+maxn, 0); dis[start] = 0; for(int ii = 0;ii<total;ii++){ int k = -1,MIN = INF; for(int i = 1;i<=total;i++){ if (dis[i]<MIN && vis[i] == false){ MIN = dis[i]; k = i; } } if (k == -1)return; vis[k] = true; for(int i = 0;i<adj[k].size();i++){ int v = adj[k][i].v; if (vis[v] == false && dis[v] > dis[k] + adj[k][i].length){ dis[v] = dis[k] + adj[k][i].length; } } } } bool ok(int i,int total){ DFS(i, total); for(int j = 1;j<=n;j++){ if (dis[j] > ds)return false; } return true; } void process(char a[],char b[],int length){ int aa = 0,bb = 0; if (a[0] == 'G'){ if (a[1] == '1' && a[2] == '0')aa = 10+n; else {aa = a[1]-'0'+n;} } else{ int len = (int)strlen(a); for (int i = 0;i<len;i++){ aa = aa * 10 + a[i]-'0'; } } // 这里还搞错了!最后一个测试点就出现了问题 if (b[0] == 'G'){ if (b[1] == '1' && b[2] == '0')bb = 10+n; else {bb = b[1]-'0'+n;} } else{ int len = (int)strlen(b); for (int i = 0;i<len;i++){ bb = bb * 10 + b[i]-'0'; } } adj[aa].push_back(edge(bb,length)); adj[bb].push_back(edge(aa,length)); } int main(){ scanf("%d %d %d %d",&n,&m,&k,&ds); int total = m + n; for(int i = 0;i<k;i++){ char a[5],b[5]; int length; scanf("%s %s %d",a,b,&length); process(a,b,length); } double maxavd = 0,maxd = 0; int k = 0,judge = 0; for (int i = n+1;i<=total;i++){ if (ok(i,total)){ judge = 1; double min = INF,avd = 0; for(int j = 1;j<=n;j++){ avd += dis[j]; // printf("G%d %d %d \n",i-n,j,dis[j]); if (dis[j] < min)min = dis[j]; } avd = avd/n; // printf("%lf",avd); if (min > maxd || (min == maxd && maxavd > avd)){ maxavd = avd; maxd = min; k = i-n; } } } if (judge == 0)printf("No Solution"); else printf("G%d\n%.01lf %.01lf",k,(double)round(maxd*10)/10,(double)round(maxavd*10)/10); return 0; }
//A1075 TODO 4/5 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> #include <iomanip> using namespace std; typedef struct{ int p[6] = {-2,-2,-2,-2,-2,-2}; int dp[6] = {0,0,0,0,0,0}; //提交过,并不是所有的0都不输出 int score = 0,rank,id,pnum; } stu; bool cmp(stu a,stu b){ if (a.score!=b.score) return a.score>b.score; else if(a.pnum!=b.pnum) return a.pnum>b.pnum; else return a.id<b.id; } int main(){ int n,k,m; cin>>n>>k>>m; int pro[k+1]; int sub[m][3]; vector<stu>student; student.resize(n+1); for(int i = 0;i<k;i++){cin>>pro[i];} for(int i = 0;i<m;i++){scanf("%d %d %d",&sub[i][0],&sub[i][1],&sub[i][2]);} for(int i = 0;i<m;i++){ if (student[sub[i][0]].p[sub[i][1]] < sub[i][2]){ student[sub[i][0]].p[sub[i][1]] = sub[i][2]; } student[sub[i][0]].dp[sub[i][1]] = 1; } for(int i = 0;i<n+1;i++){ for(int j = 0;j<6;j++){ if (student[i].p[j]>-1){ student[i].score = student[i].p[j]+student[i].score;} } student[i].id = i; int pn = 0; for(int j = 1;j<k+1;j++){if(student[i].p[j] == pro[j-1]) pn++;} student[i].pnum = pn; } sort(student.begin(),student.end(),cmp); for(int i = 0;i<n+1;i++){ if (i == 0){student[i].rank = 0;} else if (student[i].score != student[i-1].score){student[i].rank = i;} else student[i].rank = student[i-1].rank; int judgeall = 0,judgeall2 = 0; //judgeall不能有编译错误的,judgeall2得有上交的 for(int j = 1;j<k+1;j++){ if (student[i].p[j] == -1) judgeall = 1; if (student[i].p[j] != -2) judgeall2 = 1; } if (student[i].score>0){ cout<<student[i].rank+1<<' '<<setw(5)<<setfill('0')<<student[i].id<<' '<<student[i].score<<' '; for(int j = 1;j<k+1;j++){ // cout<<student[i].p[j]; if (student[i].dp[j] > 0 && student[i].p[j]>0) cout<<student[i].p[j]; else if (student[i].dp[j] > 0)cout<<0; //负分的要输出0 else cout<<'-'; if (j<k)cout<<' '; else cout<<endl; } } else if (judgeall == 0 && judgeall2 == 1){ //全错也要输出 cout<<student[i].rank+1<<' '<<setw(5)<<setfill('0')<<student[i].id<<' '<<student[i].score<<' '; for(int j = 1;j<k+1;j++){ if (student[i].dp[j] > 0)cout<<0; else cout<<'-'; if (j<k)cout<<' '; else cout<<endl; } } } return 0; } //4 3 8 //20 30 40 //1 1 15 //1 3 20 //2 2 0 //2 3 0 //3 1 20 //3 2 15 //4 1 -1 //4 3 -1
//A1076 $30/30 #include <cstdio> #include <vector> #include <queue> using namespace std; const int maxn = 1010; struct node{ int v,layer = 0; node(int _v,int _layer):v(_v),layer(_layer){}; }; vector<node>g[maxn]; bool visit[maxn] = {false}; int n,l; void init(){ for(int i = 0;i<n+1;i++){ visit[i] = false; } } bool in(int frien,int host){ for(int i = 0;i<g[host].size();i++){ if (g[host][i].v == frien)return true; } return false; } int BFS(int start){ int count = -1; node s = node(start, 0); queue<node>q; q.push(s);visit[start] = true; while(!q.empty()){ node front = q.front(); // printf("%d %d\n",start,front.v); int layer = front.layer+1; if (layer > l+1)break; q.pop();count++; int v = front.v; for(int i = 0;i<g[v].size();i++){ if (visit[g[v][i].v] == false){ // node n = node(g[v][i].v,layer); q.push(node(g[v][i].v,layer)); visit[g[v][i].v] = true; } } } return count; } int main(){ scanf("%d%d",&n,&l); for(int i = 1;i<n+1;i++){\ int isize; scanf("%d",&isize); // g[i].resize(isize); for(int j = 0;j<isize;j++){ int temp; scanf("%d",&temp); // g[i].push_back(node(temp,0)); if (!in(i,temp)){ g[temp].push_back(node(i,0)); } } } // for(int i = 1;i<n+1;i++){ // printf("\n%d:",i); // for(int j = 0;j<g[i].size();j++){ // printf(" %d",g[i][j].v); // } // } // printf("\n\n"); int k; scanf("%d",&k); int query[k]; for(int i = 0;i<k;i++){scanf("%d",&query[i]);} for(int i = 0;i<k;i++){ printf("%d\n",BFS(query[i])); init(); } return 0; }
//A1077 TODO 4/5 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> using namespace std; int main(){ int n; cin>>n; vector<string> input; for(int i = 0;i<n+1;i++){ //这里有问题,最后一个输入不进去,暴力+1才解决,其实应该前面加个getchar()接收换行符 string temp; getline(cin,temp); input.push_back(temp); } // cout<<"\n"; // for(int i = 0;i<n+2;i++){ // cout<<input[i]<<endl; // } int issuffix = 1,count = 0; while(issuffix == 1){ for(int i = 1;i<n;i++){ // cout<<input[i][input[i].size()-count-1]<<' '<<input[i+1][input[i+1].size()-count-1]<<endl; if (input[i][input[i].size()-count-1] != input[i+1][input[i+1].size()-count-1]){ issuffix = 0; break; } } if (issuffix == 1) count++; } // cout<<count<<endl; if(count==0)cout<<"nai"; else{ for(int i = 0;i<count;i++){ cout<<input[1][input[1].size()-count+i]; } } return 0; }
//A1078 $ 1/4 TODO 2/4 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> using namespace std; bool isPrime(int n){ if (n <= 1)return false; // 少这句,测试点1错误 for(int i = 2;i<(int)sqrt(1.0*n)+1;i++){ if (n % i == 0)return false; } return true; } int getPrime(int n){ if (isPrime(n))return n; int i = 1; while (isPrime(n+i) == false) { i+=1; } return n+i; } int main(){ int n,size; cin>>n>>size; size = getPrime(size); vector<bool>hash(size,false); int temp; for(int i = 0;i<n;i++){ scanf("%d",&temp); if (hash[temp%size] == false){ hash[temp%size] = true; printf("%d",temp%size); } else{ int j; for(j = 1;j<size;j++){ if (hash[(temp+j*j)%size]==false){ hash[(temp+j*j)%size] = true; printf("%d",(temp+j*j)%size); break; } } if (j >= size)printf("-"); } if (i<n-1) printf(" "); } return 0; }
//A1079 $ 7/7 #include <queue> #include <cstdio> #include <vector> using namespace std; struct Node{ int amount = 0; double price; vector<int>child; }; vector<Node>tree; void inorder(int root,double price,double rate){ queue<int>q; q.push(root); tree[root].price = price; while(!q.empty()){ int front = q.front(); q.pop(); for(int i = 0;i<tree[front].child.size();i++){ q.push(tree[front].child[i]); tree[tree[front].child[i]].price = tree[front].price * (1.0 + rate/100); } } } int main(){ int n; double price,rate; scanf("%d %lf %lf",&n,&price,&rate); tree.resize(n); for(int i = 0;i<n;i++){ int childsize; scanf("%d",&childsize); if (childsize > 0){ tree[i].child.resize(childsize); for(int j = 0;j<childsize;j++){ scanf("%d",&tree[i].child[j]); } } else{ scanf("%d",&tree[i].amount); } } // for(int i = 0;i<n;i++){ // printf("%d %lf\n",i,tree[i].price); // } inorder(0, price, rate); // for(int i = 0;i<n;i++){ // printf("%d %lf\n",i,tree[i].price); // } // double sum = 0; for(int i = 0;i<n;i++){ if (tree[i].amount>0) sum += tree[i].amount * tree[i].price; } printf("%.01lf",sum); return 0; }
//A1080 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> using namespace std; typedef struct{ int ge,gi,admited = 0,id,rank,school; vector<int>app; } stu; bool cmp(stu a,stu b){ if ((a.ge+a.gi)!=(b.ge+b.gi)) return (a.ge+a.gi)>(b.ge+b.gi); else return a.ge>b.ge; } int main(){ int n,m,k; cin>>n>>m>>k; int school[m]; stu student[n]; for(int i = 0;i<m;i++){cin>>school[i];} for(int i = 0;i<n;i++){ student[i].app.resize(k); student[i].id = i; cin>>student[i].ge>>student[i].gi; for(int j = 0;j<k;j++){cin>>student[i].app[j];} } vector<vector<int>>admit; admit.resize(m); sort(student,student+n,cmp); for(int i = 0;i<n;i++){ if(i == 0)student[i].rank = 0; else if ((student[i].gi + student[i].ge) <(student[i-1].gi + student[i-1].ge))student[i].rank = i; else if (student[i].ge<student[i-1].ge)student[i].rank = i; else student[i].rank = student[i-1].rank; // cout<<student[i].rank<<' '<<student[i].id<<' '<<student[i].ge<<' '<<student[i].gi<<' '<<student[i].app[0]<<' '<<student[i].app[1]<<' '<<student[i].app[2]<<endl; } // cout<<endl; for (int j = 0;j<n;j++){ for (int i = 0;i<k;i++){ if (school[student[j].app[i]]>0 && student[j].admited == 0){ school[student[j].app[i]] -=1; admit[student[j].app[i]].push_back(student[j].id); student[j].admited = 1; student[j].school = student[j].app[i]; } if (student[j-1].rank == student[j].rank && student[j].admited == 0 && student[j-1].admited == 1){ admit[student[j-1].school].push_back(student[j].id); student[j].admited = 1; student[j].school = student[j-1].school; } } } for(int i = 0;i<m;i++){ // cout<<admit[i].size()<<" + "; sort(admit[i].begin(),admit[i].end()); for(int j = 0;j<admit[i].size();j++){ cout<<admit[i][j]; if (j<admit[i].size()-1)cout<<' '; } cout<<endl; } return 0; }
//A1081 $ AC #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> using namespace std; typedef struct{ long up,down; } fractionnum; long maxfactor(long a,long b){ a = abs(a); // !! if (b!= 0) return maxfactor(b, a%b); else return a; } fractionnum plus1(fractionnum a,fractionnum b){ if (a.up == 0)return b; if (b.up == 0)return a; fractionnum temp; temp.down = a.down * b.down; temp.up = a.up * b.down + a.down * b.up; if (temp.up == 0) temp.down = 1; long max = maxfactor(temp.up, temp.down); if (max > 1) { temp.up = temp.up / max;temp.down = temp.down/max;} return temp; } void printpartition(fractionnum a){ if (abs(maxfactor(a.down, a.up)) == a.down){ printf("%ld",a.up/a.down); } else{ if (abs(a.up)>a.down){ printf("%ld %ld/%ld",a.up/a.down,a.up%a.down,a.down);} else {printf("%ld/%ld",a.up,a.down);} } } int main(){ int n; cin>>n; vector<fractionnum>a(n); fractionnum result; result.up = 0;result.down = 1; for(int i = 0;i<n;i++){ // printf("%ld/%ld\n",result.up,result.down); scanf("%ld/%ld",&a[i].up,&a[i].down); result = plus1(result,a[i]); } printpartition(result); return 0; }
//A1082 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> using namespace std; int main(){ string num; cin>>num; int sgn = 0,zero = 0,zeropos = 0,wansgn = 0; if(num[0] == '-'){ cout<<"Fu "; sgn = 1; } for(int i = 0+sgn;i<num.size();i++){ // cout<<"-"<<wansgn<<"-"; if (num.size()-i == 5 && num[i] == '0' && num.size()<9) { // 80000 输出ba Wan,解决wan不输出;num.size()<9 防止输出 Yi Wan int k = 0; for(int j = i+1;j<num.size();j++){ if(num[j] !='0') k=1; } if(k == 0){cout<<" Wan";return 0;} } if (num[i]!='0'){ if (zero == 1){ if(zeropos == 4){ cout<<"Wan "; } if(zeropos != 6){ //避免20002000错误 cout<<"ling ";zero = 0; } } switch(num[i]-'0'){ case 1:{cout<<"yi";break;} case 2:{cout<<"er";break;} case 3:{cout<<"san";break;} case 4:{cout<<"si";break;} case 5:{cout<<"wu";break;} case 6:{cout<<"liu";break;} case 7:{cout<<"qi";break;} case 8:{cout<<"ba";break;} case 9:{cout<<"jiu";break;} } if(i < num.size()-1)cout<<' '; switch(num.size()-i-1){ case 0:break; case 1:{cout<<"Shi";break;} case 2:{cout<<"Bai";break;} case 3:{cout<<"Qian";break;} case 4:{cout<<"Wan";break;} case 5:{cout<<"Shi";break;} case 6:{cout<<"Bai";break;} case 7:{cout<<"Qian";break;} case 8:{cout<<"Yi";break;} } int k = 0; // 800 输出ba Bai,解决最后面的空格 for(int j = i+1;j<num.size();j++){ if(num[j]!='0') k=1; } if(i < num.size()-1 && k == 1)cout<<' '; } else{ if (zero == 0) zeropos = num.size()-i-1; zero = 1; if (num.size()-i-1 == 4 && (num.size()<9)){ //防止80008000错误 cout<<"Wan "; } if (num.size() == 1) cout<<"ling";//这防止0错误 } } return 0; }
//A1083 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> using namespace std; typedef struct{ int score; char name[20],id[20]; } stu; bool cmp(stu a,stu b){ return a.score>b.score; } int main(){ int n,a,b,judge = 0; cin>>n; stu student[n]; for(int i = 0;i<n;i++){scanf("%s %s %d",student[i].name,student[i].id,&student[i].score);} cin>>a>>b; sort(student,student+n,cmp); for (int i = 0;i<n;i++){ if(student[i].score >=a && student[i].score <=b){ cout<<student[i].name<<' '<<student[i].id<<endl; judge = 1;} } if (judge == 0){cout<<"NONE";} return 0; } //https://pintia.cn/problem-sets/994805342720868352/problems/994805380754817024 //A1086 TODO 1/5 前中序遍历重构树的方法 #include <cstdio> #include <stdio.h> #include <stack> #include <vector> #include <queue> #include <string> #include <iostream> using namespace std; stack<int>st; // 真实模拟的栈 vector<int>pre,in; // pop的就是in,push的就是pre struct Node{ int data; Node* lchild; Node* rchild; }*root; // 按照当前输入的句子操作st int op(string a){ if (a[1] == 'o'){ int temp = st.top(); st.pop(); in.push_back(temp); // printf("--%d--\n",temp); return temp; } else{ int temp = 0; char tempstr[a.size()+1]; for (int i = 0;i<a.size();i++){ tempstr[i] = a[i]; } sscanf(tempstr,"Push %d",&temp); // printf("--%d--",temp); st.push(temp); pre.push_back(temp); // printf("++%d++\n",temp); return temp; } } // 用pre和in重建二叉树 Node* create(int preL,int preR,int inL,int inR){ if (preL > preR)return NULL; Node* no = new Node; no->data = pre[preL]; int k,leftnum; for(k = inL;k<=inR;k++){ if (pre[preL] == in[k]){ leftnum = k - inL;break; } } no->lchild = create(preL+1, preL+leftnum, inL, k-1); no->rchild = create(preL+leftnum+1, preR, k+1, inR); return no; } // 后序遍历并输出 void postorder(Node* &root,int realroot){ if (root == NULL)return; if (root->lchild != NULL)postorder(root->lchild,realroot); if (root->rchild != NULL)postorder(root->rchild,realroot); printf("%d",root->data); if (root->data != realroot)printf(" "); } int main(){ int n,temp = 0,realroot = 0; string a; scanf("%d%*c",&n); pre.clear(); in.clear(); // 输入 while(temp!=n){ getline(cin,a); temp = op(a); // 如果栈空,说明上一个pop的是root if (st.empty())realroot = temp; } while(!st.empty()){ in.push_back(st.top()); st.pop(); } // printf("realroot:%d\n",realroot); // for(int i = 0;i<n;i++){printf("%d ",pre[i]);} // printf("\n"); // for(int i = 0;i<n;i++){printf("%d ",in[i]);} // printf("\n"); root = create(0,n-1,0,n-1); postorder(root, realroot); return 0; }
//A1086 模拟 TODO #include <cstdio> #include <stdio.h> #include <stack> #include <vector> #include <queue> #include <string> #include <iostream> using namespace std; struct node{ int data,layer,lchild = -1,rchild = -1; }tree[31]; stack<int>st; // 按照当前输入的句子操作st int op(string a,string b,int tempb4){ if (a[1] == 'o'){ int temp = st.top(); st.pop(); // printf("--%d--\n",temp); if (b[1] == 'o'){ tree[temp].lchild = tempb4; } else{ tree[temp].lchild = -1; tree[temp].rchild = -1; } return temp; } else{ int temp = 0; char tempstr[a.size()+1]; for (int i = 0;i<a.size();i++){ tempstr[i] = a[i]; } sscanf(tempstr,"Push %d",&temp); // printf("--%d--",temp); st.push(temp); // tree[temp].layer = (int)st.size(); // printf("++%d++\n",temp); if (b[1] == 'o'){ tree[tempb4].rchild = temp; } else{ tree[tempb4].lchild = temp; } return temp; } } // 后序遍历并输出 void postorder(int &root,int realroot){ if (root == -1) return; if (tree[root].lchild != -1)postorder(tree[root].lchild,realroot); if (tree[root].rchild != -1)postorder(tree[root].rchild,realroot); printf("%d",tree[root].data); if (tree[root].data != realroot)printf(" "); } int main(){ int n,temp = 0,realroot = 0; string a,b; scanf("%d%*c",&n); // 输入 for(int i = 0;i< n*2;i++){ b = a; getline(cin,a); temp = op(a,b,temp); tree[temp].data = temp; // 如果栈空,说明上一个pop的是root if (st.empty())realroot = temp; } for(int i = 1;i<n+1;i++){ printf("%d %d %d %d %d\n",i,tree[i].data,tree[i].layer,tree[i].lchild,tree[i].rchild); } // TODO // 1. 四种情况只能确定辈分大小,不能确定具体辈分,更不能确定左右 // 2. layer 和 st.size() 似乎也没有关系…… int root = 1; // postorder(root, realroot); return 0; }
//A1087 $ 30/30 #include <cstdio> #include <map> #include <vector> #include <string> #include <iostream> #include <algorithm> using namespace std; const int maxn = 210; const int INF = 0x3fffffff; int n,k; map<string,int>citynum; map<int,string>citynum2; int Graph[maxn][maxn],happness[maxn],dis[maxn]; vector<int>pre[maxn],best,tempbest; bool vis[maxn]; void Dj(int start){ fill(vis, vis+maxn, false); fill(dis, dis+maxn, INF); dis[start] = 0; for(int ii = 0;ii<n;ii++){ int k = -1,MIN = INF; for(int i = 0;i<n;i++){ if (vis[i] == false && dis[i] < MIN){ k = i; MIN = dis[i]; } } if (k == -1)return; vis[k] = true; for(int i = 0;i<n;i++){ if (vis[i] == false && Graph[k][i] < INF){ if (dis[i] > dis[k] + Graph[k][i]){ dis[i] = dis[k] + Graph[k][i]; pre[i].clear(); pre[i].push_back(k); }else if (dis[i] == dis[k] + Graph[k][i]){ pre[i].push_back(k); } } } } } void getcost(int &cost,int &hap,int &avhap){ cost = hap = avhap = 0; reverse(tempbest.begin(), tempbest.end()); for(int i = 1;i<(int)tempbest.size();i++){ cost += Graph[tempbest[i]][tempbest[i-1]]; hap += happness[tempbest[i]]; } // printf("\n---"); // for(int i = 0;i<tempbest.size();i++){ // printf("%d ",tempbest[i]); // } // avhap = hap/((int)tempbest.size()-1); // printf(" %d %d %d",cost,hap,avhap); reverse(tempbest.begin(), tempbest.end()); } int mincost = INF,maxhappness = 0,maxavhap = 0,leastnum = 0; void DFS(int start){ // printf("\n}%d}",start); if (start == 0){ tempbest.push_back(start); int cost,hap,avhap; getcost(cost,hap,avhap); // printf(" %d %d %d",cost,hap,avhap); // printf("-%d-",leastnum); if (cost<mincost){ mincost = cost; maxhappness = hap; maxavhap = avhap; best = tempbest; leastnum = 1; } else if (cost == mincost && hap > maxhappness){ maxhappness = hap; maxavhap = avhap; best = tempbest; leastnum +=1; } else if (cost == mincost && hap == maxhappness && avhap > maxavhap){ maxavhap = avhap; best = tempbest; leastnum +=1; } else if (cost == mincost){ leastnum +=1; } tempbest.pop_back(); return; } tempbest.push_back(start); for(int i = 0;i<pre[start].size();i++){ // printf ("%d-%d",start,pre[start][i]); DFS(pre[start][i]); } tempbest.pop_back(); } int main(){ fill(Graph[0], Graph[0] + (maxn * maxn), INF); scanf("%d %d",&n,&k); string temp; char temp1[5]; scanf("%s\n",temp1); temp = temp1; citynum[temp] = 0; citynum2[0] = temp; for (int i = 0;i<n-1;i++){ int a; scanf("%s %d",temp1,&a); // printf("-%s %d\n",temp1,a); temp = temp1; citynum[temp] = i+1; citynum2[i+1] = temp; happness[i+1] = a; } for (int i = 0;i<k;i++){ int a; char temp1[5],temp2[5]; string from,to; scanf("%s %s %d",temp1,temp2,&a); // printf("--%s %s %d\n",temp1,temp2,a); from = temp1; to = temp2; Graph[citynum[from]][citynum[to]] = a; Graph[citynum[to]][citynum[from]] = a; } // for(int i = 0;i<n;i++){ // cout<<citynum2[i]<<' '<<happness[i]; // for (int j = 0;j<maxn;j++){ // if (Graph[i][j]<INF) // cout<<' '<<citynum2[j]<<'-'<<Graph[i][j]; // } // printf("\n"); // } Dj(0); // for(int i = 0;i<n;i++){ // cout<<citynum2[i]; // printf("-%d ",dis[i]); // for(int j = 0;j<pre[i].size();j++){ // printf(" ^%d",pre[i][j]); // } // printf("\n"); // // } DFS(citynum["ROM"]); printf("%d %d %d %d\n",leastnum,mincost,maxhappness,maxavhap); reverse(best.begin(), best.end()); for(int i = 0;i<best.size();i++){ cout<<citynum2[best[i]]; if (i<best.size()-1)printf("->"); } return 0; }
//A1090 $ 6/7 #include <queue> #include <cstdio> #include <vector> #include <math.h> using namespace std; struct Node{ int amount = 0; double price; vector<int>child; }; vector<Node>tree; double inorder(int root,double price,double rate){ double max = 0; queue<int>q; q.push(root); tree[root].price = price; while(!q.empty()){ int front = q.front(); if (tree[front].price>max)max = tree[front].price; // 这句判断位置写错了,导致测试点3错误(测试点3应该就是一个元素) q.pop(); for(int i = 0;i<tree[front].child.size();i++){ q.push(tree[front].child[i]); tree[tree[front].child[i]].price = tree[front].price * (1.0 + rate/100); } } return max; } int main(){ int n,root; double price,rate; scanf("%d %lf %lf",&n,&price,&rate); tree.resize(n); for(int i = 0;i<n;i++){ int fa; scanf("%d",&fa); // printf("-%d-",fa); if (fa != -1)tree[fa].child.push_back(i); else root = i; } // for(int i = 0;i<n;i++){ // printf("%d %lf",i,tree[i].price); // for (int j = 0;j<tree[i].child.size();j++){ // printf(" %d",tree[i].child[j]); // } // printf("\n"); // } double max = inorder(root, price, rate); int count = 0; for(int i = 0;i<n;i++){ if (abs(tree[i].price - max) < 0.01)count ++; } printf("%.02lf %d",max,count); // double sum = 0; // for(int i = 0;i<n;i++){ // if (tree[i].amount>0) // sum += tree[i].amount * tree[i].price; // } // printf("%.01lf",sum); return 0; }
//A1091 $ 6/6 #include <cstdio> #include <vector> #include <queue> #include <math.h> using namespace std; struct Node{ int x,y,z; }no; int pixel[1300][200][100] = {}; bool inq[1300][200][100] = {false}; int m,n,l,t; int X[6] = {0,0,0,0,1,-1}; int Y[6] = {0,0,1,-1,0,0}; int Z[6] = {1,-1,0,0,0,0}; bool judge(int x,int y,int z){ if (x<0 || x>=m ||y<0 || y>=n ||z<0 || z>=l)return false; if (pixel[x][y][z] == 0 || inq[x][y][z] == true)return false; return true; } int BFS(int x,int y,int z){ no.x = x;no.y = y;no.z = z; queue<Node>qu; qu.push(no); inq[x][y][z] = true; int total = 0; while (!qu.empty()){ Node top = qu.front(); qu.pop();total++; for(int i = 0;i<6;i++){ int newx = top.x+X[i]; int newy = top.y+Y[i]; int newz = top.z+Z[i]; if (judge(newx,newy,newz)){ no.x = newx;no.y = newy;no.z = newz; qu.push(no); inq[newx][newy][newz] = true; } } } // printf("%d ",total); if (total >= t)return total; else return 0; } int main(){ scanf("%d%d%d%d",&m,&n,&l,&t); int ans = 0; for(int z = 0;z<l;z++){ for(int x = 0;x<m;x++){ for (int y = 0;y<n;y++){ scanf("%d",&pixel[x][y][z]); } } } for(int z = 0;z<l;z++){ for(int x = 0;x<m;x++){ for (int y = 0;y<n;y++){ if (pixel[x][y][z] == 1 && inq[x][y][z] == false){ ans += BFS(x, y, z); // printf("%d\n",ans); } } } } printf("%d",ans); }
//A1091 标准答案 #include <cstdio> #include <vector> #include <queue> #include <math.h> using namespace std; struct node{ int x,y,z; } Node; int n,m,slice,T; int pixel[1290][130][61]; bool inq[1290][130][61] = {false}; int X[6] = {0,0,0,0,1,-1}; int Y[6] = {0,0,1,-1,0,0}; int Z[6] = {1,-1,0,0,0,0}; bool judge(int x,int y,int z){ if (x >= n|| x<0 || y >= m || y<0 || z>=slice || z<0)return false; if (pixel[x][y][z] == 0 || inq[x][y][z] == true)return false; return true; } int BFS(int x,int y,int z){ int tot = 0; queue<node>Q; Node.x = x;Node.y = y;Node.z = z; Q.push(Node); inq[x][y][z] = true; while(!Q.empty()){ node top = Q.front(); Q.pop(); tot++; for (int i = 0;i<6;i++){ int newX = top.x + X[i]; int newY = top.y + Y[i]; int newZ = top.z + Z[i]; if (judge(newX, newY, newZ)){ Node.x = newX; Node.y = newY; Node.z = newZ; Q.push(Node); inq[newX][newY][newZ] = true; } } } if (tot >= T) return tot; else return 0; } int main(){ scanf("%d%d%d%d",&n,&m,&slice,&T); for(int z = 0;z<slice;z++){ for (int x = 0;x<n;x++){ for(int y = 0;y<m;y++){ scanf("%d",&pixel[x][y][z]); } } } int ans = 0; for(int z = 0;z<slice;z++){ for (int x = 0;x<n;x++){ for(int y = 0;y<m;y++){ if (pixel[x][y][z] == 1 && inq[x][y][z] == false){ ans += BFS(x, y, z); } } } } printf("%d\n",ans); return 0; }
//A1094 $ 1/4 n+1!! #include <queue> #include <cstdio> #include <vector> using namespace std; struct Node{ int layer; vector<int>child; }; vector<Node>tree; void inorder(int root){ queue<int>q; q.push(root); tree[root].layer = 1; while(!q.empty()){ int front = q.front(); // printf("%d\n",front); q.pop(); for(int i = 0;i<tree[front].child.size();i++){ q.push(tree[front].child[i]); tree[tree[front].child[i]].layer = tree[front].layer + 1; } } } int main(){ int n,m; scanf("%d %d",&n,&m); tree.resize(n+1); for(int i = 0;i<m;i++){ int childsize,number; scanf("%d %d",&number,&childsize); tree[number].child.resize(childsize); for(int j = 0;j<childsize;j++){ scanf("%d",&tree[number].child[j]); } } // for(int i = 0;i<n;i++){ // printf("%d ",i); // for (int j = 0;j<tree[i].child.size();j++){ // printf(" %d",tree[i].child[j]); // } // printf("\n"); // } inorder(1); // for(int i = 0;i<n;i++){ // printf("%d %d",i,tree[i].layer); // for (int j = 0;j<tree[i].child.size();j++){ // printf(" %d",tree[i].child[j]); // } // printf("\n"); // } vector<int>count(n+1); for(int i = 0;i<n+1;i++){ count[tree[i].layer]++; } int max = 0,maxpos = 0; for(int i = 0;i<n+1;i++){ if (count[i]>=max) { //这里要有=,输入“1 0”的样例才能对 max = count[i]; maxpos = i; } } printf("%d %d",max,maxpos); return 0; }
//A1095 TODO 0/5 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> using namespace std; typedef struct{ string id; int time,in; }rec; typedef struct{ int time = 0; string id; }car; bool cmptimecar(car a,car b){ if (a.time!=b.time) return a.time<b.time; else return a.id>b.id; } bool cmptime(rec a,rec b){ return a.time<b.time; } bool cmpid(rec a,rec b){ if (a.id!=b.id)return a.id<b.id; else return a.time<b.time; } int main(){ int n,k; cin>>n>>k; vector<rec>records; vector<car>cars; int query[k]; int h,m,s; for(int i = 0;i<n;i++){ rec temp; char temp1[4]; temp.id.resize(10); scanf("%s %d:%d:%d %s",&temp.id[0],&h,&m,&s,temp1); temp.time = h*3600+m*60+s; if(temp1[0] == 'i')temp.in = 1; else temp.in = 0; records.push_back(temp); } for(int i = 0;i<k;i++){ scanf("%d:%d:%d",&h,&m,&s); query[i] = h*3600+m*60+s; } // 删除不匹配的记录 sort(records.begin(),records.end(),cmpid); for(int i = 0;i<records.size();i++){ if (i == 0 && records[0].in == 0){ records.erase(records.begin()+i);i -=1;} else if (records[i].id != records[i-1].id && records[i].in == 0){ records.erase(records.begin()+i);i-=1;} else if (records[i].id == records[i-1].id && records[i].in == records[i-1].in){ if (records[i].in == 1){records.erase(records.begin()+i-1);i-=1;} else {records.erase(records.begin()+i);i-=1;} } } for (int i = 0;i<records.size();i++){ if (i == 0 || records[i].id != records[i-1].id){ car temp; temp.id = records[i].id; temp.time-=records[i].time; cars.push_back(temp); } else { if (records[i].in == 0) cars[cars.size()-1].time += records[i].time; else cars[cars.size()-1].time -= records[i].time;} } sort(cars.begin(),cars.end(),cmptimecar); sort(records.begin(),records.end(),cmptime); // for (int i = 0;i<records.size();i++){ // cout<<records[i].id<<' '<<records[i].time<<' '<<records[i].in<<endl; // }cout<<endl; // // for (int i = 0;i<cars.size();i++){ // cout<<cars[i].id<<' '<<cars[i].time<<endl; // }cout<<endl; // 这里query是按照时间顺序的,故可以这样节省时间 int i = 0,result = 0; for(int j = 0;j<records.size();j++){ if (records[j].time>query[i]) {cout<<result<<endl;i+=1;} if (records[j].in == 1)result += 1; else result -=1; } for (int i = 0;i<cars.size();i++){ cout<<cars[cars.size()-1-i].id<<' '; if(cars[cars.size()-1-i].time != cars[cars.size()-2-i].time)break; } //NOTE6 printf 精度控制 printf("%0*d:%0*d:%0*d",2,cars[cars.size()-1].time/3600,2,(cars[cars.size()-1].time%3600)/60,2,(cars[cars.size()-1].time%60)); return 0; }
//A1096 $ 5/7 TODO 6/7 #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <string> #include <sstream> using namespace std; typedef long long LL; const int maxsize = 1000000; vector<bool>hashtable(maxsize,true); vector<LL>prime; void getPrime(LL n,vector<LL>&prime){ hashtable[0] = false; hashtable[1] = false; for(int i = 2;i<=n;i++){ if (hashtable[i] == true){ for (int j = 2;j<n/i+1 && j<maxsize/i+1;j+=1){ hashtable[j*i] = false;} } } for(int i = 0;i<n;i++){ if (hashtable[i] == true)prime.push_back(i); } } int main(){ LL n; scanf("%lld",&n); LL m = n; getPrime((LL)sqrt(1.0 * n)+1,prime); vector<int>countprime(prime.size(),0); vector<vector<LL>>result; for(int i = 0;i<prime.size();i++){ if (n % prime[i] == 0){ n /= prime[i]; countprime[i]++; i --; } // cout<<prime[i]<<' '<<countprime[i]<<endl; } if (n!= 1){prime.push_back(n);countprime.push_back(1);} int count = 0,max = -1,pos = -1; for(int i = 0;i<prime.size() && prime[i]<=m;i++){ LL mm = m; if (countprime[i] > 0 && prime[i] == mm){ cout<<"1\n"<<prime[i]; return 0; } else if (countprime[i] > 0 && mm % (prime[i]+1) != 0 && mm % (prime[i]-1) != 0){ int judge = 0; for (int j = i+1;j<prime.size() && prime[j]<=m;j++){ judge += countprime[j]; // cout<<prime[j]<<' '<<countprime[j]<<endl; } if (judge == 0 && max == -1){ // 这里要判断诸如32这样的数字! cout<<"1\n"<<prime[i]; return 0; } } else if (countprime[i] > 0 && (mm % (prime[i]+1) == 0 || mm % (prime[i]-1) == 0)){ count+=1; result.resize(count); LL temp = prime[i]; // 第一个不一定是质数!不仅要向后看,还要向前看。 while(mm % (temp) == 0 && temp>=2){ // cout<<temp<<' '<<count-1<<' '<<endl; mm /= temp; result[count-1].push_back(temp--); } reverse(result[count-1].begin(), result[count-1].end()); temp = prime[i]+1; while(mm % (temp) == 0){ // cout<<temp<<' '<<count-1<<' '<<endl; mm /= temp; result[count-1].push_back(temp++); } // printf("%d----",(int)result[count-1].size()); if (max < (int)result[count-1].size()){ max = (int)result[count-1].size(); pos = count-1; } } } printf("%d\n",max); for(int i = 0;i<result[pos].size();i++){ printf("%lld",result[pos][i]); if (i<result[pos].size()-1)printf("*"); } return 0; }
//A1097 $ 4/5 #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <vector> #include <math.h> using namespace std; struct node{ int key; int next,add; }; int main(){ int head,n; scanf("%d %d",&head,&n); int key,add,next; node a[100010]; int hashtable[10001] = {}; for(int i = 0;i<n;i++){ scanf("%d %d %d",&add,&key,&next); a[add].key = key; a[add].add = add; a[add].next = next; } vector <vector<int>> seq1; vector <vector<int>> seq2; int p = head; for(int i = 0;i<n && p!=-1 ;i++){ vector <int> temp(2); temp[0] = a[p].key; temp[1] = a[p].add; if (hashtable[abs(a[p].key)] == 0){ hashtable[abs(a[p].key)] = 1; seq1.push_back(temp); } else{ seq2.push_back(temp); } p = a[p].next; } int m = (int)seq1.size(); for(int i = 0;i<m-1;i++){ printf("%05d %d %05d\n",seq1[i][1],seq1[i][0],seq1[i+1][1]); } // 不加判断,测试点2数组越界! if (m>0)printf("%05d %d %d\n",seq1[m-1][1],seq1[m-1][0],-1); m = (int)seq2.size(); for(int i = 0;i<m-1;i++){ printf("%05d %d %05d\n",seq2[i][1],seq2[i][0],seq2[i+1][1]); } if (m>0)printf("%05d %d %d\n",seq2[m-1][1],seq2[m-1][0],-1); return 0; }
//A1098 $ 23/25 #include <cstdio> #include <algorithm> using namespace std; int n; int init[100],heap[101],insert[100],seq[100]; void print(int a[],int n){ for(int i = 0;i<n;i++){ printf("%d",a[i]); if (i<n-1)printf(" "); } printf("\n"); } void print2(int a[],int n){ for(int i = 0;i<n;i++){ printf("%d",a[i+1]); if (i<n-1)printf(" "); } printf("\n"); } bool cmp(int a[],int b[],int n){ for(int i = 0;i<n;i++){ if (a[i]!=b[i])return false; } return true; } bool cmp2(int a[],int b[],int n){ for(int i = 0;i<n;i++){ if (a[i+1]!=b[i])return false; } return true; } int judgeinsert = 0; bool insertionSort(int insert[],int n){ for(int i = 1;i<n;i++){ // 这里要从1开始!初始序列不参与比较!测试点2 for(int j = 0;j<i;j++){ if (insert[i]<insert[j]) swap(insert[i],insert[j]); } if (judgeinsert == 1){ print(insert,n); return 1; } if (cmp(insert,seq,n)){ printf("Insertion Sort\n"); judgeinsert = 1; } } return 0; } void dj(int low,int high){ int i = low,j = 2*i; while(j<=high){ if (j+1<=high && heap[j+1]>heap[j])j = j+1; if (heap[i]<heap[j]){ swap(heap[i],heap[j]); i = j; j = 2*i; } else break; } } void createHeap(){ for(int i = n/2;i>=1;i--){ dj(i,n); } } int judgeheap = 0; void heapSort(){ createHeap(); for(int i = n;i>1;i--){ swap(heap[i],heap[1]); dj(1, i-1); // print(heap,n); if (judgeheap == 1){ print2(heap,n); return; } if (cmp2(heap,seq,n)){ printf("Heap Sort\n"); judgeheap = 1; } } } int main(){ scanf("%d",&n); for(int i = 0;i<n;i++){ scanf("%d",&init[i]); insert[i] = init[i]; heap[i+1] = init[i]; } for(int i = 0;i<n;i++){ scanf("%d",&seq[i]); } bool isinsert = insertionSort(insert, n); if (!isinsert){ heapSort(); } return 0; }
//A1099 $ 30/30 #include <queue> #include <cstdio> #include <vector> #include <algorithm> using namespace std; int n,countn = 0,countnn = 0; int weight[110],in[110]; struct node{ int data,lchild,rchild; }root,tree[110]; void inorder(int root){ if (root == -1 || root >= n)return; inorder(tree[root].lchild); in[countn++] = root; inorder(tree[root].rchild); } void layerorder(int root){ queue<int>q; q.push(root); while(!q.empty()){ int top = q.front();q.pop(); printf("%d",tree[top].data); countnn++; if (countnn < n)printf(" "); if (tree[top].lchild != -1) q.push(tree[top].lchild); if (tree[top].rchild != -1) q.push(tree[top].rchild); } } int main(){ scanf("%d",&n); for (int i = 0;i<n;i++){ scanf("%d %d",&tree[i].lchild,&tree[i].rchild); // tree[i].data = i; } for (int i = 0;i<n;i++){scanf("%d",&weight[i]);} sort(weight,weight+n); inorder(0); // 中序遍历 // for (int i = 0;i<n;i++){ // printf("%d ",in[i]); // } for(int i = 0;i<n;i++){ tree[in[i]].data = weight[i]; } layerorder(0); // 中序遍历赋值 return 0; }
//A1102 $ 2/4 #include <cstdio> #include <queue> #include <vector> using namespace std; struct node{ int data; int lchild = -1,rchild = -1; int root = 0; // 0是初始状态,1输入时是已经有爸爸,2是爸爸 }; void layerOrder(int root,vector<node>tree,int size){ queue<int>q; q.push(root); int count = 0; while(!q.empty()){ int tmp = q.front(); printf("%d",tmp); q.pop();count++; if (count < size)printf(" "); if (tree[tmp].lchild != -1)q.push(tree[tmp].lchild); if (tree[tmp].rchild != -1)q.push(tree[tmp].rchild); } printf("\n"); } int num = 0; void inOrder(int root,vector<node>tree,int size){ if (tree[root].lchild != -1) inOrder(tree[root].lchild,tree,size); printf("%d",root);num++; if (num<size)printf(" "); if (tree[root].rchild != -1) inOrder(tree[root].rchild,tree,size); } int main(){ int n; scanf("%d%*c",&n); vector<node>tree(n); for(int i = 0;i<n;i++){ char temp1,temp2; scanf("%c %c%*c",&temp1,&temp2); tree[i].data = i; if (tree[i].root == 0)tree[i].root = 2; if (temp2>='0' && temp2 <= '9'){ tree[i].lchild = (int)(temp2 - '0'); tree[tree[i].lchild].root = 1; } if (temp1>='0' && temp1 <= '9'){ tree[i].rchild = (int)(temp1 - '0'); tree[tree[i].rchild].root = 1; } // printf("%c %c ",temp1,temp2); // printf("%d %d ",tree[i].lchild,tree[i].rchild); // for(int i = 0;i<n;i++){ // printf("%d",tree[i].root); // } // printf("\n"); } int root; for(int i = 0;i<n;i++){ if (tree[i].root == 2)root = i; } // for(int i = 0;i<n;i++){ // printf("%d %d %d %d\n",tree[i].data,tree[i].lchild,tree[i].rchild,tree[i].root); // } // printf("\n"); layerOrder(root,tree,n); inOrder(root,tree,n); return 0; }
//A1103 $ 1/8 #include <queue> #include <vector> #include <cstdio> #include <math.h> using namespace std; int n,k,p; vector <int> ans,fac,temp; void init(){ int i = 0; while (pow(i,p)<=n){ fac.push_back(pow(i,p)); i++; } } int maxfacsum = -1; void DFS(int index,int nowk,int facsum,int sum){ if (sum == n && nowk == k){ if (facsum > maxfacsum){ ans = temp;maxfacsum = facsum; } return; } if (sum > n || nowk >k) return; if (index - 1 >= 0){ temp.push_back(index); DFS(index,nowk+1,facsum+index,sum+fac[index]); temp.pop_back(); DFS(index-1,nowk,facsum,sum); } } int main(){ scanf("%d %d %d",&n,&k,&p); init(); DFS((int)fac.size()-1,0,0,0); if (maxfacsum>-1){ printf("%d = %d^%d",n,ans[0],p); for(int i = 1;i<ans.size();i++){ printf(" + %d^%d",ans[i],p); } } else printf("Impossible"); return 0; }
//A1103 标答 #include <cstdio> #include <vector> #include <math.h> using namespace std; int n,k,p,maxsum = -1; vector<int> fac,ans,temp; int power(int x){ int ans = 1; for(int i = 0;i<p;i++){ ans *= x; } return ans; } void init(){ int i = 0,temp = 0; while(temp<=n){ fac.push_back(temp); temp = power(++i); } } void DFS(int index,int nowK,int sum,int facsum){ if (sum == n && nowK == k){ if (facsum > maxsum){ ans = temp; maxsum = facsum; } return; } if (sum > n || nowK > k)return; if (index - 1 >= 0){ temp.push_back(index); DFS(index, nowK+1, sum+fac[index], facsum+index); temp.pop_back(); DFS(index-1,nowK,sum,facsum); } } int main(){ scanf("%d%d%d",&n,&k,&p); init(); DFS((int)fac.size()-1, 0, 0, 0); if (maxsum == -1)printf("Impossible\n"); else{ printf("%d = %d^%d",n,ans[0],p); for(int i = 1;i<ans.size();i++){ printf(" + %d^%d",ans[i],p); } } return 0; }
//A1106 $ 8/8 #include <queue> #include <cstdio> #include <vector> #include <math.h> using namespace std; struct Node{ int amount = 0; double price; vector<int>child; }; vector<Node>tree; void inorder(int root,double price,double rate){ queue<int>q; q.push(root); tree[root].price = price; while(!q.empty()){ int front = q.front(); q.pop(); for(int i = 0;i<tree[front].child.size();i++){ q.push(tree[front].child[i]); tree[tree[front].child[i]].price = tree[front].price * (1.0 + rate/100); } } } int main(){ int n; double price,rate; scanf("%d %lf %lf",&n,&price,&rate); tree.resize(n); for(int i = 0;i<n;i++){ int childsize; scanf("%d",&childsize); if (childsize > 0){ tree[i].child.resize(childsize); for(int j = 0;j<childsize;j++){ scanf("%d",&tree[i].child[j]); } } else{ tree[i].amount = 1; } } // for(int i = 0;i<n;i++){ // printf("%d %lf\n",i,tree[i].price); // } inorder(0, price, rate); // for(int i = 0;i<n;i++){ // printf("%d %lf\n",i,tree[i].price); // } // double sum = 10000000000; for(int i = 0;i<n;i++){ if (tree[i].amount>0 && sum > tree[i].price) sum = tree[i].price; } int count = 0; for(int i = 0;i<n;i++){ if (tree[i].amount>0 && abs(sum - tree[i].price)<0.0001) count++; } printf("%.04lf %d",sum,count); return 0; }
//A1107 $ 16/30 TODO 5/6 #include <cstdio> #include <vector> #include <algorithm> #include <iostream> using namespace std; int father[3000]; void init(int n){ n = n*2; while(n-->=0){father[n] = n;} } int findFather(int a){ while(a!=father[a]){ a = father[a]; } return a; } void Union (int a,int b){ int faa = findFather(a); int fab = findFather(b); if (faa != fab){ if (fab < faa) father[faa] = fab; else father[fab] = faa; } } bool cmp(int a,int b){ return a>b; } int main(){ int n,temp1,temp2; scanf("%d",&n); init(n+1); for(int i = 0;i<n;i++){ cin>>temp1; int k = i + n + 2; char c; cin>>c; // TODO 这里 scanf 不知道为啥会出错 for(int j = 0;j<temp1;j++){ cin>>temp2; Union(k,temp2); } } // for (int i = 1;i<2 * n+2;i++){ // printf("%d %d\n",i,findFather(i)); // } // printf("\n"); int count[3000] = {}; for(int i = n+2;i<2*n+2;i++){ count[findFather(i)]++; } sort(count,count+3000,cmp); int sum = 0; for(int i = 0;i<3000;i++){ if (count[i] == 0){ sum = i;break; } } printf("%d\n",sum); for(int i = 0;i<sum;i++){ printf("%d",count[i]); if (i<sum-1)printf(" "); } return 0; } // TODO 不对 // 队列与栈 算式加减 #include <stack> #include <queue> #include <map> #include <string> #include <iostream> #include <cstdio> using namespace std; struct node{ double num; char op; bool flag; }; string str; stack<node>s; queue<node>q; map<char,int>op; void convert(){ double num; node temp; for(int i = 0;i<str.size();){ if (str[i] >= '0' && str[i]<= '9'){ temp.flag = true; temp.num += (double)(str[i++]-'0'); while(i<str.size() && str[i] >= '0' && str[i]<= '9'){ temp.num = temp.num * 10 + (double)(str[i]-'0'); i++; } q.push(temp); } else{ temp.flag = false; while(!s.empty() && op[str[i]] <= op[s.top().op]){ q.push(s.top()); s.pop(); } temp.op = str[i]; s.push(temp); i++; } } while(!s.empty()){ q.push(s.top()); s.pop(); } } double cal(){ double temp1,temp2; node cur,temp; while(!q.empty()){ cur = q.front(); q.pop(); if (cur.flag == true) s.push(cur); else{ temp2 = s.top().num; s.pop(); temp1 = s.top().num; s.pop(); temp.flag = true; if (cur.op == '+') temp.num = temp1 + temp2; else if (cur.op == '-') temp.num = temp1 - temp2; else if (cur.op == '*') temp.num = temp1 * temp2; else temp.num = temp1 / temp2; s.push(temp); } } return s.top().num; } int main(){ op['+'] = op['-'] = 1; op['*'] = op['/'] = 2; while(getline(cin,str),str !="0"){ for(string::iterator it = str.end(); it!= str.begin();it--){ if (*it == ' ') str.erase(it); } while(!s.empty()) s.pop(); convert(); printf("%.02f",cal()); } } // 动态链表模板 #include <stdio.h> #include <stdlib.h> using namespace std; struct node{ int data; node* next; }; node* create(int array[],int size){ node *p,*pre,*head; head = new node; head -> next = NULL; pre = head; for(int i = 0;i<size;i++){ p = new node; p->data = array[i]; p->next = NULL; pre->next = p; pre = p; } return head; } int search(node* head,int x){ int count = 0; node *p = head->next; while (p!= NULL){ if (p->data == x) count ++; p = p->next; } return count; // 链表中 x 的个数 } void insert(node* head,int pos,int x){ node *q = head; while(pos-- > 0){q = q->next;} // 找到 pos-1 位置 node *p = new node; p->next = q->next; q->next = p; p->data = x; } void del(node* head,int x){ node *p = head->next; node *pre = head; while(p!=NULL){ if (p->data == x){ pre->next = p->next; delete p; p = pre->next; } else{ pre = p; p = p->next; } } } int main(){ int array[5] = {1,2,3,4,5}; node* L = create(array, 5); L = L->next; // 头结点没有数据 while (L!= NULL){ printf("%d ",L->data); L = L->next; } }

发表评论