# 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(){
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;
}
}

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";
}

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));
}

string judge(string a,string b,string 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(){
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;
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(){
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 main(){
node a[100010];

for(int i = 0;i<n;i++){
}

vector <vector<int>> seq;
for(int i = 0;i<n && p!=-1 ;i++){   // 注意会有无效节点！
vector <int> temp(2);
seq.push_back(temp);
seq[i][0] = a[p].key;
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;
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<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;
if (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);
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;
}

for(int i = 0;i<n;i++){
}

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){};
};

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;
if (vis[v] == false && 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';
}
}
}

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 main(){
node a[100010];
int hashtable[10001] = {};

for(int i = 0;i<n;i++){
}

vector <vector<int>> seq1;
vector <vector<int>> seq2;

for(int i = 0;i<n && p!=-1 ;i++){
vector <int> temp(2);
temp[0] = a[p].key;
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){
for(int i = 0;i<size;i++){
p = new node;
p->data = array[i];
p->next = NULL;
pre->next = p;
pre = p;
}
}

int count = 0;
while (p!= NULL){
if (p->data == x) count ++;
p = p->next;
}
return count;   // 链表中 x 的个数
}

while(pos-- > 0){q = q->next;}  // 找到 pos-1 位置
node *p = new node;
p->next = q->next;
q->next = p;
p->data = x;
}

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;
}
}