PAT 甲级真题题解（63-120）

1063 Set Similarity 

n个序列分别先放进集合里去重。在询问的时候，遍历A集合中每个数，判断下该数在B集合中是否存在，统计存在个数（分子），分母就是两个集合大小减去分子。

 // 1063 Set Similarity
 #include <set>
 #include <map>
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 set <int> se[];

 int main() {
     int n, k, m;
     scanf("%d", &n);
     for(int i = ; i <= n; i++) {
         scanf("%d", &m);
         while(m--) {
             scanf("%d", &k);
             se[i].insert(k);
         }
     }
     scanf("%d", &k);
     while(k--) {
         int id1, id2;
         double cnt = , total = ;
         scanf("%d %d", &id1, &id2);
         for(int i : se[id1]) {
             if(se[id2].find(i) != se[id2].end()) cnt++;
         }
         total = se[id1].size() + se[id2].size() - cnt;
         printf("%.1f%\n", cnt *  / total);
     }
     return ;
 }

1064 Complete Binary Search Tree 

按照中序遍历建树。对应根节点依次填入排序好的数即可。

 // 1064 Complete Binary Search Tree
 #include <queue>
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = ;
 int a[N], level[N], n, cnt = ;

 void solve(int root) {
     if(root > n) return ;
     solve( * root);
     level[root] = a[++cnt];
     solve( * root + );
 }

 int main() {
     scanf("%d", &n);
     for(int i = ; i <= n; i++) scanf("%d", &a[i]);
     sort(a + , a +  + n);
     solve();
     for(int i = ; i <= n; i++) {
         if(i != ) printf(" ");
         printf("%d", level[i]);
     }
     return ;
 }

1065 A+B and C (64bit)

对溢出的情况特判一下。

 // 1065 A+B and C (64bit)
 #include <iostream>
 using namespace std;

 typedef long long ll;

 int main() {
     int t;
     scanf("%d", &t);
     for(int i = ; i <= t; i++) {
         ll a, b, c, sum = ;
         scanf("%lld %lld %lld", &a, &b, &c);
         sum = a + b;
         if(a >  && b >  && sum <= ) {
             printf("Case #%d: true\n", i);
         } else if(a <  && b <  && sum >= ) {
             printf("Case #%d: false\n", i);
         } else if(sum > c) {
             printf("Case #%d: true\n", i);
         } else {
             printf("Case #%d: false\n", i);
         }
     }
     return ;
 }

1066 Root of AVL Tree 

AVL模板题

 #include <bits/stdc++.h>
 using namespace std;

 typedef struct node;
 typedef node * tree;

 struct node{
     int v, heigh;
     tree L,R;
 };

 int getheigh(tree root){
     if(root==NULL) return ;
     return root->heigh;
 }

 void updataheigh(tree root){
     root->heigh=max(getheigh(root->L),getheigh(root->R))+;
 }

 int getBalance(tree root){
     return getheigh(root->L)-getheigh(root->R);
 }

 void L(tree &root){
     tree temp;
     temp=root->R;
     root->R=temp->L;
     temp->L=root;
     updataheigh(root);
     updataheigh(temp);
     root=temp;
 }

 void R(tree &root){
     tree temp;
     temp=root->L;
     root->L=temp->R;
     temp->R=root;
     updataheigh(root);
     updataheigh(temp);
     root=temp;
 }

 void insertt(tree &root,int v){
     if(root==NULL){
         root=new node;
         root->v=v;
         root->heigh=;
         root->L=root->R=NULL;
         return;
     }
     if(v<root->v){
         insertt(root->L,v);
         updataheigh(root);
         if(getBalance(root)==){
             if(getBalance(root->L)==){
                 R(root);
             }
             else if(getBalance(root->L)==-){
                 L(root->L);
                 R(root);
             }
         }
     }
     else{
         insertt(root->R,v);
         updataheigh(root);
         if(getBalance(root)==-){
             if(getBalance(root->R)==-){
                 L(root);
             }
             else if(getBalance(root->R)==){
                 R(root->R);
                 L(root);
             }
         }
     }

 }

 int main(){
     int n;
     scanf("%d",&n);
     int x;
     tree root;
     root=NULL;
     for(int i=;i<n;i++){
         scanf("%d",&x);
         insertt(root,x);
     }
     printf("%d\n",root->v);
     return ;
 }

1067 Sort with Swap(0, i)

看到表排序的知识，摘录下。

表排序思想：N个数字的排列由若干个独立的环组成

分成以下三种环：

1. 环内只有一个元素，即该数已经在正确的位置上，不需要交换。
2. 环内有 n 个元素，含 0，需要交换次数是：n-1 （每一个非 0 元素都要和 0 换一下）
3. 环内有 n 个元素，不含 0，需要交换的次数是：n+1（把 0 换入换出 + 其余 n-1 个非 0 元素和 0 换一下）

 // 1067 Sort with Swap(0, i)
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = 1e5 + ;
 bool vis[N];
 int pos[N];

 int main() {
     int n, u, ans = ;
     scanf("%d", &n);
     for(int i = ; i < n; i++) {
         scanf("%d", &u);
         pos[u] = i;
     }
     for(int i = ; i < n; i++) {
         if(pos[i] != i && !vis[i]) {
             int cnt = , j = i;
             do {
                 cnt++;
                 vis[j] = true;
                 if(j == ) cnt -= ;
                 j = pos[j];
             }while(j != i);
             cnt++;
             ans += cnt;
         }
     }
     printf("%d\n", ans);
     return ;
 }

1068 Find More Coins

因题目特殊的输出要求，用01背包的时候需要先用大的数填，不然如果先用小的数填，小的数会影响后面的数，最后从小的往大的拿出去即可。

 // 1068 Find More Coins
 #include <vector>
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = 1e4 + ;
 int n, m;
 int a[N], dp[N];
 vector <int> ans;
 bool check[N][];

 int main() {
     scanf("%d %d", &n, &m);
     for(int i = ; i <= n; i++) scanf("%d", &a[i]);
     sort(a + , a +  + n);
     for(int i = n; i >= ; i--) {
         for(int j = m; j >= a[i]; j--) {
             if(dp[j - a[i]] + a[i] >= dp[j]) {
                 dp[j] = dp[j - a[i]] + a[i];
                 check[i][j] = ;
             }
         }
     }
     if(dp[m] != m) {
         printf("No Solution\n");
         return ;
     }
     int id = ;
     while(m > ) {
         if(check[id][m]) {
             ans.push_back(a[id]);
             m -= a[id];
         }
         id++;
     }
     for(int i = ; i < ans.size(); i++) {
         if(i != ) printf(" ", ans[i]);
         printf("%d", ans[i]);
     }
     return ;
 }

1069 The Black Hole of Numbers

按题目模拟即可。

 // 1069 The Black Hole of Numbers
 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 int a[];
 bool cmp(int a, int b) {return a > b;}

 int cal1(int n) {
     memset(a, , sizeof(a));
     int cnt = , res = ;
     while(n) {
         a[++cnt] = n % ;
         n /= ;
     }
     sort(a + , a +  + );
     for(int i = ; i >= ; i--) {
         res = res *  + a[i];
     }
     return res;
 }

 int cal2() {
     int res = ;
     sort(a + , a +  + );
     for(int i = ; i <= ; i++) {
         res = res *  + a[i];
     }
     return res;

 }

 int main() {
     int n;
     scanf("%d", &n);
     while() {
         int p1 = cal1(n);
         int p2 = cal2();
         n = p1 - p2;
         printf("%04d - %04d = %04d\n", p1, p2, n);
         if(n ==  || n == ) return ;
     }
     return ;
 }

1070 Mooncake

按每吨多少钱从大到小排序下，再取即可。

 // 1070 Mooncake
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = ;

 struct node{
     double storage, price;
 }moon[N];

 bool cmp(node x, node y) {
     return x.price * y.storage  > y.price * x.storage;
 }

 int main() {
     int n;
     double d, ans = ;
     scanf("%d %lf", &n, &d);
     for(int i = ; i <= n; i++) scanf("%lf", &moon[i].storage);
     for(int i = ; i <= n; i++) scanf("%lf", &moon[i].price);
     sort(moon + , moon +  + n, cmp);
     for(int i = ; i <= n; i++) {
         if(d >= moon[i].storage) {
             ans += moon[i].price;
             d -= moon[i].storage;
         } else {
             ans += moon[i].price * (1.0 * d / moon[i].storage);
             break;
         }
     }
     printf("%.2f\n", ans);
     return ;
 }

1071 Speech Patterns

用map存下。更新答案即可。

 // 1071 Speech Patterns
 #include <map>
 #include <string>
 #include <iostream>
 using namespace std;

 string in, tmp, ans1;
 map<string, int> mp;
 map<string, int>::iterator it;

 int main(){
     int ans2 = ;
     getline(cin, in);
     for(int i =  ; i < in.size(); i++) {
         if(isalnum(in[i])) {
             tmp += tolower(in[i]);
             if(i == in.size() - ) mp[tmp]++;
         } else {
             if(tmp.size()) mp[tmp]++;
             tmp.clear();
         }
     }
     for(it = mp.begin(); it!=mp.end(); it++){
         if(ans2 < it->second){
             ans2 = it -> second;
             ans1 = it -> first;
         }else if(ans2 == it -> second && ans1 > it -> first){
             ans1 = it -> first;
         }
     }
     cout << ans1 << " " << ans2 << endl;
 }

1072 Gas Station

以加油站为起点，跑最短路即可。

 //1072 Gas Station
 #include <queue>
 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N=1e3+;
 const int INF=0x3f3f3f3f;;
 int n,m,k,ds,mp[N][N],dis[N],vis[N];

 int toint(char s[]){
     int sum=;
     int len=strlen(s);
     for(int i=;i<len;i++){
         if(s[i]=='G') continue;
         sum=sum*+s[i]-'';
     }
     if(s[]=='G') return sum+n;
     return sum;
 }

 void Dijkstra(int v){
     fill(vis,vis+N,false);
     fill(dis,dis+N,INF);
     for(int i=;i<=n+m;i++) dis[i]=mp[v][i];
     dis[v]=;
     for(int i=;i<n+m;i++){
         int u=-,minn=INF;
         for(int j=;j<=n+m;j++){
             if(!vis[j]&&minn>dis[j]){
                 u=j;minn=dis[j];
             }
         }
         vis[u]=true;
         for(int j=;j<=n+m;j++){
             if(!vis[j]&&dis[j]>mp[u][j]+dis[u]){
                 dis[j]=mp[u][j]+dis[u];
             }
         }
     }
 }
 int main(){
     int num,a,b;
     char s1[],s2[];
     scanf("%d %d %d %d",&n,&m,&k,&ds);
     fill(mp[],mp[]+N*N,INF);
     for(int i=;i<k;i++){
         scanf("%s %s %d",s1,s2,&num);
         a=toint(s1),b=toint(s2);
         mp[a][b]=mp[b][a]=num;
     }
     int id=-;
     double maxDis=-,minAvg=INF;
     for(int i=n+;i<=n+m;i++){
         Dijkstra(i);
         double avg=;
         double Min=INF;
         bool flag=false;
         for(int j=;j<=n;j++){
             if(dis[j]>ds){
                 flag=true;
                 break;
             }
             if(Min>dis[j]){
                 Min=dis[j];
             }
             avg+=1.0*dis[j]/n;
         }
         if(flag) continue;
         if(maxDis<Min){
             maxDis=Min;
             id=i;
             minAvg=avg;
         }
         else if(maxDis==Min&&minAvg>avg){
             id=i;
             minAvg=avg;
         }

     }
     if(id==-) printf("No Solution\n");
     else{
         printf("G%d\n",id-n);
         printf("%.1f %.1f\n",maxDis,minAvg);
     }
     return ;
 }

1073 Scientific Notation

按题意模拟即可。

 // 1073 Scientific Notation
 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = 1e4 + ;
 char s[N];

 int main() {
     int n, i = ;
     scanf("%s", s);
     n = strlen(s);
     while(s[i] != 'E') {
         i++;
     }
     i++;
     if(s[] != '+') printf("%c", s[]);
     int m = ;
     for(int j = i + ; j < n; j++) m =  * m + (s[j] - '');
     if(s[i] == '+') {
         m+=;
         for(int j = ; j < i - ; j++) {
             m--;
             if(m == -) printf(".");
             if(s[j] != '.') printf("%c", s[j]);
         }
         while(m > ) {
             printf("");
             m--;
         }
     } else {
         m--;
         printf("0.");
         while(m > ) {
             printf("");
             m--;
         }
         for(int j = ; j < i - ; j++) {
             if(s[j] != '.') printf("%c", s[j]);
         }
     }
     return ;
 }

1074 Reversing Linked List

每k个长度翻转一次。$j$位置对应交换的位置为$(2 * i + k - j - 1)$，这个只使用前半和后半交换，注意特判跳出。

 //1074 Reversing Linked List
 #include <cstdio>
 #include <vector>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = 1e5 + ;
 int nxt[N], val[N], res[N];

 int main() {
     int root, n, k, cnt = ;
     scanf("%d%d%d", &root, &n, &k);
     for(int i = ; i <= n; i++) {
         int u, v, w;
         scanf("%d%d%d", &u, &v, &w);
         val[u] = v; nxt[u] = w;
     }
     while(root != -) {
         res[cnt++] = root;
         root = nxt[root];
     }
     for(int i = ; i + k <= cnt; i += k) {
         for(int j = i; j < (i + k); j++) {
             if(j >= ( * i + k - j - )) break;
             swap(res[( * i + k - j - )], res[j]);
         }
     }
     for(int i = ; i < cnt - ; i++) {
         printf("%05d %d %05d\n", res[i], val[res[i]], res[i + ]);
     }
     printf("%05d %d -1\n", res[cnt - ], val[res[cnt - ]]);
     return ;
 }

1075 PAT Judge

结构体排序，注意一下区别提交得0分和提交没有通过编译。

 // 1075 PAT Judge
 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = 1e5 + ;
 int v[];
 int n, k, m;
 struct node{
     int q[], id, sum, ok, perfect;
 }p[N];

 void init() {
     for(int i = ; i <= n; i++)
     for(int j = ; j <= k; j++)
     p[i].q[j] = -, p[i].id = i;
 }

 bool cmp(node x, node y) {
     if(x.sum == y.sum) {
         if(x.perfect == y.perfect) return x.id < y.id;
         return x.perfect > y.perfect;
     }
     return x.sum > y.sum;
 }

 int main() {
     int r = ;
     scanf("%d %d %d", &n, &k, &m);
     for(int i = ; i <= k; i++) scanf("%d", &v[i]);
     init();
     for(int i = ; i <= m; i++) {
         int uid, pid, val;
         scanf("%d %d", &uid, &pid);
         scanf("%d", &val);
         p[uid].q[pid] = max(p[uid].q[pid], val);
     }
     for(int i = ; i <= n; i++) {
         int cnt = , perfect = ;
         bool ok = ;
         for(int j = ; j <= k; j++) {
             if(p[i].q[j] != - && p[i].q[j] != -) cnt += p[i].q[j], ok = ;
             if(p[i].q[j] == v[j]) perfect++;
         }
         if(ok) p[i].ok = ;
         else p[i].ok = ;
         p[i].sum = cnt;
         p[i].perfect = perfect;
     }
     sort(p + , p +  + n, cmp);
     for(int i = ; i <= n; i++) {
         if(p[i].ok == ) continue;
         if(p[i].sum != p[i - ].sum) r = i;
         printf("%d %05d %d", r, p[i].id, p[i].sum);
         for(int j = ; j <= k; j++) {
             if(p[i].q[j] == -) printf(" -");
             else if(p[i].q[j] == -) printf("");
             else printf(" %d",p[i].q[j]);
         }
         printf("\n");
     }
     return ;
 }

1076 Forwards on Weibo

DFS或BFS，DFS的时候注意剪枝。

DFS版本

 //1076 Forwards on Weibo
 #include <vector>
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = ;
 vector <int> E[N];
 bool vis[N];
 int layer[N];
 int n, m, k, u, sz, ans;

 void dfs(int u, int l) {
     vis[u] = ;
     layer[u] = l;
     if(l <= k) {
         for(int i = ; i < E[u].size(); i++) {
             int v = E[u][i];
             if(!vis[v] || layer[v] > l + ) {
                 dfs(v, l + );
             }
         }
     }
 }

 int main() {
     scanf("%d %d", &n, &k);
     for(int i = ; i <= n; i++) {
         scanf("%d", &sz);
         while(sz) {
             sz--;
             scanf("%d", &u);
             E[u].push_back(i);
         }
     }
     scanf("%d", &m);
     while(m--) {
         for(int i = ; i <= n; i++) vis[i] = , layer[i] = ;
         scanf("%d", &u);
         ans = ;
         dfs(u, );
         for(int i = ; i <= n; i++) if(layer[i] > ) ans++;
         printf("%d\n", ans - );
     }
     return ;
 }

BFS版本

 //1076 Forwards on Weibo
 #include <queue>
 #include <vector>
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = ;
 vector <int> E[N];
 bool vis[N];
 int n, m, k, u, sz;

 void bfs() {
     int ans = ;
     for(int i = ; i <= n; i++) vis[i] = ;
     queue < pair<int,int> > Q;
     Q.push(make_pair(u, ));
     vis[u] = ;
     while(!Q.empty()) {
         int cur = Q.front().first;
         int layer = Q.front().second;
         Q.pop();
         if(layer >= k) continue;
         for(int i = ; i < E[cur].size(); i++) {
             int v = E[cur][i];
             if(!vis[v]) {
                 ans++;
                 vis[v] = ;
                 Q.push(make_pair(v, layer + ));
             }
         }
     }
     printf("%d\n", ans);
 }

 int main() {
     scanf("%d %d", &n, &k);
     for(int i = ; i <= n; i++) {
         scanf("%d", &sz);
         while(sz) {
             sz--;
             scanf("%d", &u);
             E[u].push_back(i);
         }
     }
     scanf("%d", &m);
     while(m--) {
         scanf("%d", &u);
         bfs();
     }
     return ;
 }

1077 Kuchiguse

模拟

 //1077 Kuchiguse
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 int id[];
 char s[][];

 int main() {
     int n, cnt = ;
     scanf("%d", &n);
     getchar();
     for(int i = ; i <= n; i++) {
         char c;
         while(scanf("%c", &c) != EOF && c != '\n') {
             s[i][id[i]++] = c;
         }
     }
     while() {
         for(int i = ; i <= n; i++) {
             if( ((id[i] - cnt) < )  || (s[i][id[i] - cnt] != s[][id[] - cnt]) ) {
                 cnt--;
                 if(cnt == ) printf("nai");
                 else {
                     for(int i = id[] - cnt; i < id[] ; i++) {
                         printf("%c", s[][i]);
                     }
                 }
                 return ;
             }
         }
         cnt++;
     }
     return ;
 }

1078 Hashing

Hash二次探测。0^2，1^2，2^2...。

 //1078 Hashing
 #include <iostream>
 using namespace std;

 const int N = 1e4 + ;
 bool vis[N];

 bool check(int x) {
     if(x < ) return false;
     for(int i = ; i * i <= x; i++) {
         if(x % i == ) return false;
     }
     return true;
 }

 int main() {
     int n, m, p;
     cin >> m >> n;
     while(!check(m)) {m++;}
     for(int i = ; i <= n; i++) {
         bool f = ;
         cin >> p;
         if(i != ) printf(" ");
         for(int i = ; i < m; i++) {
             int tmp = (p + i * i) % m;
             if(!vis[tmp]) {
                 f = ;
                 printf("%d", tmp);
                 vis[tmp] = ;
                 break;
             }
         }
         if(!f) printf("-");
     }
     return ;
 }

1079 Total Sales of Supply Chain

从根跑一遍DFS到叶子节点。统计每个叶子节点的能够产生的销售额。

 //1079 Total Sales of Supply Chain
 #include <vector>
 #include <cstdio>
 using namespace std;

 const int N = 1e5 + ;
 int cnt[N];
 bool vis[N];
 double p, r;
 double price[N];
 vector <int> E[N];

 void dfs(int u, double val) {
     vis[u] = ; price[u] = val;
     for(int i = ; i < E[u].size(); i++) {
         int v = E[u][i];
         if(!vis[v]) dfs(v, val * ( + r / ));
     }
 }

 int main() {
     int n, k, u;
     scanf("%d %lf %lf", &n, &p, &r);
     for(int i = ; i < n; i++) {
         scanf("%d", &k);
         if(k == ){
              scanf("%d", &cnt[i]);
         } else {
             while(k--) {
                 scanf("%d", &u);
                 E[i].push_back(u);
             }
         }
     }
     double ans = ;
     dfs(, p);
     for(int i = ; i < n; i++) {
         ans += price[i] * cnt[i];
     }
     printf("%.1f\n", ans);
     return ;
 }

1080 Graduate Admission

按照题意模拟，用set从小到大排序特性会方便很多。

 // 1080 Graduate Admission
 #include <set>
 #include <cstdio>
 #include <vector>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = 4e4 + ;
 struct Stu{
   int Id, Ge, Gi, Gh, Rank;
   int choices[];
 };

 struct Sch{
   int maxn, lastRank;
   set<int> admit;
 };

 bool cmp(Stu x, Stu y){
     if(x.Gh == y.Gh) return x.Ge > y.Ge;
     return x.Gh > y.Gh;
 }

 set<int>::iterator it;

 int main(){
     int n, m, k;
     scanf("%d%d%d", &n, &m, &k);
     vector<Sch> sch(m);
     vector<Stu> stu(n);
     for(int i = ; i < m; i++) scanf("%d", &sch[i].maxn);
     for(int i = ; i < n; i++){
         scanf("%d%d", &stu[i].Ge, &stu[i].Gi);
         stu[i].Id=i; stu[i].Gh = stu[i].Ge + stu[i].Gi;
         for(int j = ; j < k; j++) scanf("%d", &stu[i].choices[j]);
     }
     sort(stu.begin(), stu.end(), cmp);
     int Rank = ;
     for(int i = ; i < n; i++){
         if(i== || (stu[i].Gh == stu[i-].Gh && stu[i].Gi == stu[i-].Gi)) stu[i].Rank = Rank;
         else{
             Rank = i + ;
             stu[i].Rank = Rank;
         }
     }
     for(int i = ; i < n; i++){
         bool f=;
         for(int j = ; j < k; j++){
             int schid = stu[i].choices[j];
             if(sch[schid].maxn > ){
                 sch[schid].admit.insert(stu[i].Id);
                 sch[schid].maxn--;
                 sch[schid].lastRank = stu[i].Rank;
                 f = true;
             }else if(sch[schid].lastRank == stu[i].Rank) {
                 sch[schid].admit.insert(stu[i].Id);
                 f = true;
             }
             if(f) break;
         }
     }
     for(int i = ; i < m; i++){
         for(it = sch[i].admit.begin(); it!=sch[i].admit.end(); it++){
           if(it == sch[i].admit.begin()) printf("%d", *it);
           else printf(" %d", *it);
         }
         printf("\n");
     }
     return ;
 }

1081 Rational Sum

通分，注意最后若答案为0的时的格式输出。

 // 1081 Rational Sum
 #include <cstdio>
 #include <algorithm>
 using namespace std;

 typedef long long ll;
 ll a[], b[];

 int main() {
     ll n, nr = , dm = ;
     scanf("%lld", &n);
     for(ll i = ; i <= n; i++) {
         scanf("%lld/%lld", &a[i], &b[i]);
         dm = b[i] / __gcd(b[i], dm) * dm;
     }
     for(ll i = ; i<= n; i++) {
         nr = nr + (dm / b[i]) * a[i];
     }
     ll g = __gcd(nr, dm);
     if(g != ) nr /= g, dm /= g;
     if(nr / dm) {
         printf("%lld", nr / dm);
         nr = nr - (nr / dm) * dm;
         if(nr != ) printf(" %lld/%lld", nr, dm);
         return ;
     }
     nr = nr - (nr / dm) * dm;
     if(nr != ) printf("%lld/%lld", nr, dm);
     else printf("");
     return ;
 }

1082 Read Number in Chinese

模拟，注意细节即可。

 // 1082 Read Number in Chinese
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 string a[] = {"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
 string b[] = {"","Shi","Bai","Qian","Wan","Shi","Bai","Qian","Yi"};

 int main() {
     int n, f = ;
     string s;
     cin >> s;
     if(s[] == '-') {
         cout << "Fu" << " ";
         s = s.substr();
     }
     n = s.size();
     reverse(s.begin(), s.end());
     for(int i = n - ; i >= ; i--) {
         if(i == n - ) {
             cout << a[s[i] - ''] << " " << b[i];
         } else {
             if(s[i] != '') {
                 if(f) {
                     cout << " " << a[];
                     f = ;
                 }
                 cout << " " << a[s[i] - ''] << " " << b[i];
             } else {
                 f = ;
                 if(i == ) cout << " " << b[];
             }
         }
     }
     if(f && s[] != '') {
         cout << " " << a[];
     }
     if(s.size() == ) {
         cout << a[s[] - ''];
     }
     else if(s.size() >  && s[] != ''){
         cout << " " << a[s[] - ''];
     }
     return ;
 }

1083 List Grades

结构体排序

 // 1083 List Grades
 #include <cstdio>
 #include <algorithm>
 using namespace std;

 const int N = 2e5 + ;
 struct node {
     char name[], id[];
     int grade;
 }recoder[N];

 bool cmp(node x, node y) {
     return x.grade > y.grade;
 }

 int main() {
     bool f = ;
     int n;
     scanf("%d", &n);
     for(int i = ; i <= n; i++) {
         scanf("%s %s %d", recoder[i].name, recoder[i].id, &recoder[i].grade);
     }
     int g1, g2;
     scanf("%d%d", &g1, &g2);
     sort(recoder + , recoder +  + n, cmp);
     for(int i = ; i <= n; i++) {
         if(recoder[i].grade <= g2 && recoder[i].grade >= g1) {
             printf("%s %s\n", recoder[i].name, recoder[i].id);
             f = ;
         }
     }
     if(!f) printf("NONE\n");
     return ;
 }

map标记一下。

 // 1084 Broken Keyboard
 #include <map>
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 map <char, int> m;

 int main() {
     char c;
     string s1, s2;
     cin >> s1 >> s2;
     for(int i = ; i < s2.size(); i++) {
         m[s2[i]] = ;
         if(s2[i] >= 'a' && s2[i] <= 'z') {
             c = s2[i] - ;
             m[c] = ;
         }
         else if(s2[i] >= 'A' && s2[i] <= 'Z') {
             c = s2[i] + ;
             m[c] = ;
         }
     }
     for(int i = ; i < s1.size(); i++) {
         if(!m[s1[i]]) {
             m[s1[i]] = ;
             if(s1[i] >= 'a' && s1[i] <= 'z') {
                 c = s1[i] - ;
                 m[c] = ;
                 cout << c;
             }
             else if(s1[i] >= 'A' && s1[i] <= 'Z') {
                 c = s1[i] + ;
                 m[c] = ;
                 cout << s1[i];
             } else {
                 cout << s1[i];
             }
         }
     }
     return ;
 }

1085 Perfect Sequence

二分搜索

 // 1085 Perfect Sequence
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 typedef long long ll;
 const int N = 1e5 + ;
 ll a[N];

 int main() {
     int ans = ;
     ll n, p;
     scanf("%lld %lld", &n, &p);
     for(int i = ; i < n; i++) scanf("%lld", &a[i]);
     sort(a, a + n);
     for(int i = ; i < n; i++) {
         int pos1 = lower_bound(a, a + n, a[i]) - a;
         int pos2 = lower_bound(a, a + n, a[i] * p + ) - a;
         pos2--;
         ans = max(ans, pos2 - pos1 + );
     }
     printf("%d\n", ans);
     return ;
 }

1086 Tree Traversals Again

由题目可以得知push的时候为往下找，分情况讨论存左孩子还是右孩子，pop的时候表示往右走，下一次push存右孩子，最后后序遍历一下即可。

 // 1086 Tree Traversals Again
 #include <stack>
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 char s[];
 struct node{
     int lch, rch;
 }tree[];
 stack <int> sta;
 int n, u, fa, root = -, child = ;

 void postorder(int u) {
     if(tree[u].lch != ) postorder(tree[u].lch);
     if(tree[u].rch != ) postorder(tree[u].rch);
     if(u == root) printf("%d", u);
     else printf("%d ", u);
 }

 int main() {
     scanf("%d", &n);
     n *= ;
     while(n--) {
         scanf("%s", s);
         if(s[] == 'u') {
             scanf("%d", &u);
             sta.push(u);
             if(root == -) {
                 root = u;
             } else {
                 if(child == ) tree[fa].lch = u;
                 else tree[fa].rch = u;
             }
             fa = u;
             child = ;
         } else {
             if(sta.size())
             fa = sta.top();
             sta.pop();
             child = ;
         }
     }
     postorder(root);
     return ;
 }

1087 All Roads Lead to Rome

先Floyd得到最短路，再DFS搜，搜的过程中更新答案。

 // 1087 All Roads Lead to Rome
 #include <bits/stdc++.h>
 using namespace std;

 const int N = ;
 int n, m, cost, cnt = , maxhappy = ;
 int happy[N], d[N][N];
 string s[N], s1, s2;
 map<string, int> mp;
 vector<int> E[N], res, ans;
 bool vis[N];

 void dfs(int u, int en, int co) {
     if(u == en && co == cost) {
         int sum = ;
         for(int i = ; i < res.size(); i++) {
             sum += happy[res[i]];
         }
         if(sum > maxhappy) {
             maxhappy = sum;
             ans.clear();
             for(int i = ; i < res.size(); i++) ans.push_back(res[i]);
         }
         else if(sum == maxhappy && res.size() < ans.size()) {
             ans.clear();
             for(int i = ; i < res.size(); i++) ans.push_back(res[i]);
         }
         cnt++;
         return ;
     }
     for(int k = ; k < E[u].size(); k++) {
         int v = E[u][k];
         if(vis[v]) continue;
         res.push_back(v);
         vis[v] = ;
         dfs(v, en, co + d[u][v]);
         vis[v] = ;
         res.pop_back();
     }
 }

 int main() {
     cin >> n >> m >> s[];
     mp[s[]] = ;
     memset(d, 0x3f, sizeof(d));
     for(int i = ; i <= n; i++) d[i][i] = ;
     for(int i = ; i <= n; i++) {
         cin >> s[i] >> happy[i];
         mp[s[i]] = i;
     }
     for(int i = ; i <= m; i++) {
         cin >> s1 >> s2 >> cost;
         d[mp[s1]][mp[s2]] = cost;
         d[mp[s2]][mp[s1]] = cost;
         E[mp[s2]].push_back(mp[s1]);
         E[mp[s1]].push_back(mp[s2]);
     }

     for(int k = ; k <= n; k++)
     for(int i = ; i <= n; i++)
     for(int j = ; j <= n; j++)
     d[i][j] = min(d[i][j] ,d[i][k] + d[k][j]);

     cost = d[mp[s[]]][mp["ROM"]];
     vis[mp[s[]]] = ;
     dfs(mp[s[]], mp["ROM"], );

     cout << cnt << " " << cost << " " << maxhappy << " " << maxhappy / ans.size() << endl;
     cout << s[];
     for(int i = ; i < ans.size(); i++) cout << "->" << s[ans[i]];
     return ;
 }

1088 Rational Arithmetic

注意相乘会爆long long，判断负可以分别判断x 和 y

 // 1088 Rational Arithmetic
 #include <bits/stdc++.h>
 using namespace std;

 typedef long long ll;
 ll gcd(ll a, ll b) {
     return b ==  ? a : gcd(b, a % b);
 }

 void func(ll x, ll y) {
     bool f = ;
     if(x * y == ) {
         if(y == ) printf("Inf");
         else if(x == ) printf("");
         return ;
     }
     if((x >  && y < ) || (x <  && y > )) f = ;
     x = abs(x); y = abs(y);
     ll val = x / y;
     ll res = x - val * y;
     if(f) printf("(-");
     if(val != ) printf("%lld", val);
     if(res == ) {
         if(f) printf(")");
         return ;
     }
     if(val != ) printf(" ");
     ll g = gcd(res, y);
     res /= g; y /= g;
     printf("%lld/%lld", res, y);
     if(f) printf(")");
 }

 int main() {
     ll a, b, c, d;
     scanf("%lld/%lld %lld/%lld", &a, &b, &c, &d);
     func(a, b);printf(" + ");func(c, d);printf(" = ");func(a * d + b * c, b * d);printf("\n");
     func(a, b);printf(" - ");func(c, d);printf(" = ");func(a * d - b * c, b * d);printf("\n");
     func(a, b);printf(" * ");func(c, d);printf(" = ");func(a * c, b * d);printf("\n");
     func(a, b);printf(" / ");func(c, d);printf(" = ");func(a * d, b * c);
     return ;
 }

1089 Insert or Merge

先判断是否为插入排序，不是的话，跑一遍归并，直到a数组和b数组一样，再进行一次归并操作。

 // 1089 Insert or Merge
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = ;
 int a[N], b[N];

 int main() {
     int n, i, j;
     cin >> n;
     for (i = ; i < n; i++) cin >> a[i];
     for (i = ; i < n; i++) cin >> b[i];
     for (i = ; i < n -  && b[i] <= b[i + ]; i++);
     for (j = i + ; a[j] == b[j] && j < n; j++);
     if (j == n) {
         cout << "Insertion Sort" << endl;
         sort(a, a + i + );
     } else {
         cout << "Merge Sort" << endl;
         int k = , f = ;
         while(f) {
             f = ;
             for (i = ; i < n; i++) {
                 if (a[i] != b[i]) f = ;
             }
             k = k * ;
             for (i = ; i < n / k; i++)
             sort(a + i * k, a + (i + ) * k);
             sort(a + n / k * k, a + n);
         }
     }
     for(j = ; j < n; j++) {
         if (j != )  cout << " ";
         cout << a[j];
     }
     return ;
 }

1090 Highest Price in Supply Chain

DFS跑一遍树即可。

 // 1090 Highest Price in Supply Chain
 #include <cstdio>
 #include <vector>
 using namespace std;

 const int N = 1e5 + ;
 int n, u, cnt, root;
 double p, r, maxp = , sellp[N];
 vector <int> E[N];

 void dfs(int a, double price) {
     sellp[a] = price;
     maxp = max(maxp, price);
     for(int i = ; i < E[a].size(); i++) {
         int b = E[a][i];
         dfs(b, price * (1.0 + r / ));
     }
 }

 int main() {
     scanf("%d %lf %lf", &n, &p, &r);
     for(int i = ; i < n; i++) {
         scanf("%d", &u);
         if(u == -) root = i;
         else E[u].push_back(i);
     }
     dfs(root, p);
     for(int i = ; i < n; i++) {
         if(sellp[i] == maxp) cnt++;
     }
     printf("%.2f %d\n", maxp, cnt);
     return ;
 }

1091 Acute Stroke

3维BFS裸题。

 // 1091 Acute Stroke
 #include <queue>
 #include <cstdio>
 using namespace std;

 int n, m, l, t, ans = ;
 int mp[][][];
 bool vis[][][];
 struct node{
     int z, x, y;
 };
 int dx[] = {, , , , -, };
 int dy[] = {, , -, , , };
 int dz[] = {-, , , , , };

 bool check(int z, int x, int y) {
     if(z >=  && z <= l && x >=  && x <= n && y >=  && y <= m) return true;
     return false;
 }

 int bfs(int z, int x, int y) {
     queue <node> q;
     node tmp;
     int res = ;
     q.push(node{z, x, y});
     vis[z][x][y] = ;
     while(!q.empty()) {
         res++;
         tmp = q.front();
         q.pop();
         for(int i = ; i < ; i++) {
             int nz = tmp.z + dz[i];
             int nx = tmp.x + dx[i];
             int ny = tmp.y + dy[i];
             if(check(nz, nx, ny) && !vis[nz][nx][ny] && mp[nz][nx][ny]) {
                 vis[nz][nx][ny] = ;
                 q.push(node{nz, nx, ny});
             }
         }

     }
     if(res >= t) return res;
     else return ;
 }

 int main() {
     scanf("%d%d%d%d", &n, &m, &l, &t);
     for(int z = ; z <= l; z++)
     for(int x = ; x <= n; x++)
     for(int y = ; y <= m; y++)
     scanf("%d", &mp[z][x][y]);

     for(int z = ; z <= l; z++)
     for(int x = ; x <= n; x++)
     for(int y = ; y <= m; y++)
     if(mp[z][x][y] && !vis[z][x][y]) ans += bfs(z, x, y);

     printf("%d\n", ans);
     return ;
 }

1092 To Buy or Not to Buy

用数组标记一下即可。

 // 1092 To Buy or Not to Buy
 #include <iostream>
 using namespace std;

 int a[];
 string s1, s2;

 int main(){
     cin >> s1 >> s2;
     int c1 = , c2 = ;
     for(int i = ; i < s1.size(); i++) a[s1[i]]++;
     for(int i = ; i < s2.size(); i++) a[s2[i]]--;
     for(int i = ; i < ; i++) {
         if(a[i] < ) c1+=a[i];
         else c2+=a[i];
     }
     if(c1 < ) cout << "No " << -c1 << endl;
     else cout << "Yes " << c2 << endl;
     return ;
 }

1093 Count PAT's

统计一下P,A,T。在A位置计算前面有几个P，后面有几个T。

 // 1093 Count PAT's
 #include <cstdio>
 #include <cstring>
 using namespace std;

 typedef long long ll;
 const int N =  1e5 + ;
 const ll mod = ;
 char s[N];
 ll sum[N][];

 int main() {
     int n;
     ll ans = ;
     scanf("%s", s + );
     n = strlen(s + );
     for(int i = ; i <= n; i++) {
         for(int j = ; j <= ; j++) sum[i][j] = sum[i - ][j];
         if(s[i] == 'P') sum[i][]++;
         else if(s[i] == 'A') sum[i][]++;
         else sum[i][]++;
     }
     for(int i = ; i <= n; i++) {
         if(s[i] == 'A') {
             ans = (ans + (sum[i][] * (sum[n][] - sum[i][])) % mod) % mod;
         }
     }
     printf("%lld\n", ans);
     return ;
 }

1094 The Largest Generation

DFS跑下树，记录下即可。

 // 1094 The Largest Generation
 #include <vector>
 #include <cstdio>
 using namespace std;

 const int N = ;
 int n, m, cnt[N];
 vector <int> children[N];

 void dfs(int u, int level) {
     for(int i = ; i < children[u].size(); i++) {
         dfs(children[u][i], level + );
     }
     cnt[level]++;
 }

 int main() {
     scanf("%d%d", &n, &m);
     while(m--) {
         int r, k, c;
         scanf("%d%d", &r, &k);
         while(k--) {
             scanf("%d", &c);
             children[r].push_back(c);
         }
     }
     dfs(, );
     int mx = , id;
     for(int i = ; i <= n; i++) {
         if(cnt[i] > mx) {
             mx = cnt[i];
             id = i;
         }
     }
     printf("%d %d\n", mx, id);
     return ;
 }

1095 Cars on Campus

按同个车牌号并以时间排序，模拟过去即可。

 // 1095 Cars on Campus
 #include <map>
 #include <vector>
 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = 1e4 + ;
 char s[N][], op[];
 int t[N], f[N], id[N];
 int cnt[ *  + ], maxtime;
 map<string, int> m;
 vector <string> ans;

 bool cmp(int x, int y) {
     if(!strcmp(s[x], s[y])) {
         return t[x] < t[y];
     } else {
         return strcmp(s[x], s[y]) < ;
     }
 }

 int main() {
     int n, k, hh, mm, ss;
     scanf("%d%d", &n, &k);
     for(int i = ; i < n; i++) {
         id[i] = i;
         scanf("%s %d:%d:%d %s", s[i], &hh, &mm, &ss, op);
         t[i] =  * hh +  * mm + ss;
         if(op[] == 'i') f[i] = ;
         else f[i] = ;
     }
     sort(id, id + n, cmp);
     for(int i = ; i < n; i++) {
         if(!strcmp(s[id[i]], s[id[i - ]])) {
             if(f[id[i - ]] ==  && f[id[i]] == ) {
                 cnt[t[id[i - ]]]++;
                 cnt[t[id[i]]]--;
                 m[s[id[i]]] = m[s[id[i]]] + t[id[i]] - t[id[i - ]];
                 maxtime = max(maxtime, m[s[id[i]]]);
             }
         }
     }
     for(int i = ; i <=  * ; i++) cnt[i] += cnt[i - ];
     while(k--) {
         scanf("%d:%d:%d", &hh, &mm, &ss);
         hh =  * hh +  * mm + ss;
         printf("%d\n", cnt[hh]);
     }
     for(int i = ; i < n; i++) {
         if(m[s[i]] == maxtime) {
             ans.push_back(s[i]);
             m[s[i]] = ;
         }
     }
     sort(ans.begin(), ans.end());
     for(int i = ; i < ans.size(); i++) cout << ans[i] << " ";
     hh = maxtime / ; maxtime -=  * hh;
     mm = maxtime / ; maxtime -=  * mm;
     ss = maxtime;
     printf("%02d:%02d:%02d\n", hh, mm, ss);
     return ;
 }

1096 Consecutive Factors

暴力找起点，然后找可以被整除的数。

 // 1096 Consecutive Factors
 #include <iostream>
 #include <algorithm>
 using namespace std;

 typedef long long ll;

 int main() {
     ll n, f = , maxlen = ;
     cin >> n;
     for(ll i = ; i * i <= n; i++){
         ll m = , j = i;
         for(; j * j <= n; j++) {
             m *= j;
             if(n % m != ) break;
         }
         if(j - i > maxlen) {
             maxlen = j - i;
             f = i;
         }
     }
     if(f == ) {
         cout <<  << endl << n << endl;
         return ;
     }
     cout << maxlen << endl;
     ll tmp = ;
     cout << f;
     for(ll i = f + ; tmp < n && (i - f) < maxlen; i++) {
         tmp *= i;
         cout << "*" << i;
     }
     return ;
 }

1097 Deduplication on a Linked List

从根跑下树，把仍然保留的移除的都存起来。最后输出即可。

 #include <map>
 #include <vector>
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = 1e5 + ;
 int nxt[N], val[N];
 map<int, int> m;

 struct node{
     int u, w, v;
 };

 vector <node> Remain, Remove;

 int main() {
     int root, cur, n;
     scanf("%d %d", &root, &n);
     for(int i = ; i <= n; i++) {
         int u, v, w;
         scanf("%d %d %d", &u, &w, &v);
         nxt[u] = v;
         val[u] = w;
     }
     cur = root;
     while(cur != -) {
         if(!m[abs(val[cur])]) {
             Remain.push_back({cur, val[cur], nxt[cur]});
             m[abs(val[cur])] = ;
         } else {
             Remove.push_back({cur, val[cur], nxt[cur]});
         }
         cur = nxt[cur];
     }
     for(int i = ; i < Remain.size(); i++) {
         if(i != Remain.size() - ) printf("%05d %d %05d\n", Remain[i].u, Remain[i].w, Remain[i + ].u);
         else printf("%05d %d -1\n", Remain[i].u, Remain[i].w);
     }
     for(int i = ; i < Remove.size(); i++) {
         if(i != Remove.size() - ) printf("%05d %d %05d\n", Remove[i].u, Remove[i].w, Remove[i + ].u);
         else printf("%05d %d -1\n", Remove[i].u, Remove[i].w);
     }
     return ;
 }

1098 Insertion or Heap Sort

判断下排序类型，插入排序很容易解决，再扔个堆排序上去即可。

 // 1098 Insertion or Heap Sort
 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = ;
 int a[N], b[N];

 void solve(int l, int r) {
     int i = , j = ;
     while(j <= r) {
         if(j +  <= r && b[j] < b[j + ]) j++;
         if(b[j] > b[i]) {
             swap(b[j], b[i]);
             i = j;
             j =  * (i + ) -;
         } else {
             break;
         }
     }
 }

 int main() {
     int n, k, f = ;
     scanf("%d", &n);
     for(int i = ; i < n; i++) scanf("%d", &a[i]);
     for(int i = ; i < n; i++) scanf("%d", &b[i]);
     for(k = ; k < n -  && b[k] <= b[k + ]; k++) ;
     for(int i = k + ; i < n; i++) {
         if(a[i] != b[i]) {f = ; break;}
     }
     if(f) {
         printf("Insertion Sort\n");
         sort(b, b + k + );
         for(int i = ; i < n; i++){
             printf("%d", b[i]);
             if(i != n - ) printf(" ");
         }
     } else {
         printf("Heap Sort\n");
         int p = n - ;
         while(p >  && b[p - ] <= b[p]) {
             p--;
         }
         swap(b[], b[p]);
         solve(, p - );
         for(int i = ; i < n; i++){
             printf("%d", b[i]);
             if(i != n - ) printf(" ");
         }
     }
     return ;
 }

1099 Build A Binary Search Tree

先排序，中序遍历即为填数的顺序。最后再层次遍历输出。

 // 1099 Build A Binary Search Tree
 #include <queue>
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 queue <int> q;
 const int N = ;
 int lch[N], rch[N], val[N], a[N], cnt = ;

 void dfs(int u) {
     if(lch[u] != -) dfs(lch[u]);
     val[u] = a[cnt++];
     if(rch[u] != -) dfs(rch[u]);
 }

 int main() {
     int n, f = ;
     scanf("%d", &n);
     for(int i = ; i < n; i++) {
         int l, r;
         scanf("%d %d", &l, &r);
         lch[i] = l; rch[i] = r;
     }
     for(int i = ; i < n; i++) scanf("%d", &a[i]);
     sort(a, a + n);
     dfs();
     q.push();
     while(!q.empty()) {
         int cur = q.front();
         q.pop();
         if(!f) f = ;
         else printf(" ");
         printf("%d", val[cur]);
         if(lch[cur] != -) q.push(lch[cur]);
         if(rch[cur] != -) q.push(rch[cur]);
     }
     return ;
 }

1100 Mars Numbers

模拟。

 // 1100 Mars Numbers
 #include <iostream>
 using namespace std;

 string s;
 string str[] = {
     "tret", "jan", "feb", "mar", "apr", "may", "jun",
     "jly", "aug", "sep", "oct", "nov", "dec", "tam", "hel",
     "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok",
     "mer", "jou"
 };

 void cal1() {
     if(s[] == '') {
         cout << "tret" << endl;
         return ;
     }
     int num = ;
     for(int i = ; i < s.size(); i++) num =  * num + (s[i] - '');
     if(num / ) cout << str[num /  + ];
     if((num / ) && (num % )) cout << " ";
     if(num % ) cout << str[num % ];
     cout << endl;
 }

 void cal2() {
     int t1 = , t2 = ;
     string s1 = s.substr(, ), s2 = "";
     if(s.size() > ) s2 = s.substr(, );
     for(int i = ; i <= ; i++) {
         if(str[i] == s1) t1 = i;
         if(str[i] == s2) t2 = i;
     }
     if(t1 > ) cout << (t1 - ) *  + t2 << endl;
     else cout << t1 + t2 << endl;
 }

 int main() {
     int n;
     cin >> n;
     getchar();
     for(int i = ; i <= n; i++) {
         getline(cin, s);
         if(s[] >= '' && s[] <= '') cal1();
         else cal2();
     }
     return ;
 }

1101 Quick Sort

用个数组记录下从前往后，对于当前位置的最大值；从后往前，对于当前位置的最小值。最后再遍历一遍数组即可。

 // 1101 Quick Sort
 #include <vector>
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 vector <int> ans;
 const int N = 1e5 + ;
 int a[N], pre[N], nxt[N];

 int main() {
     int n;
     scanf("%d", &n);
     for(int i = ; i <= n; i++) scanf("%d", &a[i]);
     for(int i = ; i <= n; i++) {
         pre[i] = max(pre[i - ], a[i]);
     }
     nxt[n + ] = 1e9 + ;
     for(int i = n; i >= ; i--) {
         nxt[i] = min(nxt[i + ], a[i]);
     }
     for(int i = ; i <= n; i++) {
         if(pre[i] <= a[i] && nxt[i] >= a[i]) {
             ans.push_back(a[i]);
         }
     }
     printf("%d\n", ans.size());
     sort(ans.begin(), ans.end());
     for(int i = ; i < ans.size(); i++) {
         if(i == ) printf("%d", ans[i]);
         else printf(" %d", ans[i]);
     }
     printf("\n");
     return ;
 }

1102 Invert a Binary Tree

先找下根，中序和层序，把先左后右的顺序调换下。

 // 1102 Invert a Binary Tree
 #include <queue>
 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = ;
 int n, root, f;
 int lch[N], rch[N], fa[N];

 void level_order() {
     queue <int> q;
     q.push(root);
     while(!q.empty()) {
         int u = q.front();
         if(!f) f = ;
         else printf(" ");
         printf("%d", u);
         q.pop();
         if(rch[u] != -) q.push(rch[u]);
         if(lch[u] != -) q.push(lch[u]);
     }
     printf("\n");
 }

 void in_order(int u) {
     if(rch[u] != -) in_order(rch[u]);
     if(!f) f = ;
     else printf(" ");
     printf("%d", u);
     if(lch[u] != -) in_order(lch[u]);
 }

 int main() {
     cin >> n;
     memset(fa, -, sizeof(fa));
     memset(lch, -, sizeof(lch));
     memset(rch, -, sizeof(rch));
     for(int i = ; i < n; i++) {
         char c1, c2;
         cin >> c1 >> c2;
         if(c1 != '-') {
             lch[i] = (c1 - '');
             fa[(c1 - '')] = i;
         }
         if(c2 != '-') {
             rch[i] = (c2 - '');
             fa[(c2 - '')] = i;
         }
     }
     for(int i = ; i < n; i++){
         if(fa[i] == -) root = i;
     }
     f = ;
     level_order();
     f = ;
     in_order(root);
     printf("\n");
     return ;
 }

1103 Integer Factorization

预处理下，再DFS+剪枝。更新下答案。

 // 1103 Integer Factorization
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 int a[], b[], ans[];
 int n, m, k, c;

 void dfs(int id, int cnt, int val) {
     b[cnt] = id;
     if(cnt > m || val > n) return ;
     if(val == n && cnt == m) {
         bool f = ;
         for(int i = ; i <= m; i++) {
             if(ans[i] != b[i]) {
                 if(b[i] > ans[i]) f = ;
                 break;
             }
         }
         for(int i = ; i <= m; i++) ans[i] = b[i];
         return ;
     }
     for(int i = id; i <= c && val + a[i] <= n; i++) {
         dfs(i, cnt + , val + a[i]);
     }
 }

 int POW(int u, int v) {
     int res = ;
     for(int i = ; i <= v; i++) res *= u;
     return res;
 }

 int main() {
     scanf("%d%d%d", &n, &m, &k);
     for(int i = ; POW(i, k) <= n; i++) {
         a[i] = POW(i, k);
         c = i;
     }
     for(int i = ; i <= c; i++) dfs(i, , a[i]);
     int res = ;
     for(int i = ; i <= m; i++) res += a[ans[i]];
     if(res == n) {
         printf("%d = %d^%d", n, ans[m], k);
         for(int i = m - ; i >= ; i--) {
             printf(" + %d^%d", ans[i], k);
         }
         printf("\n");
     } else {
         printf("Impossible\n");
     }
     return ;
 }

1104 Sum of Number Segments

每个位置会算到的次数为$i * (n - i + 1)$。

 #include <cstdio>
 using namespace std;

 const int N = 1e5 + ;
 double a[N];

 int main() {
     int n;
     double ans = ;
     scanf("%d", &n);
     for(int i = ; i <= n; i++) scanf("%lf", &a[i]);
     for(int i = ; i <= n; i++) {
         ans += a[i] * i * (n - i + );
     }
     printf("%.2f\n", ans);
     return ;
 }

1105 Spiral Matrix

蛇形填数，注意下细节。

 // 1105 Spiral Matrix
 #include <cmath>
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = 1e4 + ;
 int a[N];
 int ans[N][N];

 int main() {
     int n, k;
     scanf("%d", &n);
     for(int i = ; i <= n; i++) scanf("%d", &a[i]);
     if(n == ) {
         printf("%d", a[]);
         return ;
     }
     sort(a + , a +  + n);
     int m = sqrt(1.0 * n);
     while(n % m != ) m++;
     if((n / m) > m) m = n/ m;
     //m n/m
     k = n; n = n / m;
     int i = , j = ;
     int U = , D = m, L = , R = n;
     while(k > ) {
         while(k >  && j < R) {
             ans[i][j] = a[k--];
             j++;
         }
         while(k >  && i < D) {
             ans[i][j] = a[k--];
             i++;
         }
         while(k >  && j > U) {
             ans[i][j] = a[k--];
             j--;
         }
         while(k >  && i > L) {
             ans[i][j] = a[k--];
             i--;
         }
         U++; D--; L++; R--;
         i++; j++;
         if(k == ) {
             ans[i][j] = a[k--];
         }
     }
     for(int i = ; i <= m; i++) {
         for(int j = ; j <= n; j++) {
             printf("%d%c", ans[i][j], (j == n) ? '\n' : ' ');
         }
     }
     return ;
 }

1106 Lowest Price in Supply Chain

跑下树。在叶子节点更新下最小值，最后再遍历下叶子节点即可。

 // 1106 Lowest Price in Supply Chain
 #include <cstdio>
 #include <vector>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = 1e5 + ;
 int n, k, id;
 double p, r, val[N], mi = 1e12;
 vector <int> E[N];

 void dfs(int u) {
     if(E[u].size() == ) mi = min(mi, val[u]);
     for(int j = ; j < E[u].size(); j++) {
         int v = E[u][j];
         val[v] = val[u] * (1.0 + r / 100.0);
         dfs(v);
     }
 }

 int main() {
     scanf("%d %lf %lf", &n, &p, &r);
     for(int i = ; i < n; i++) {
         scanf("%d", &k);
         for(int j = ; j <= k; j++) {
             scanf("%d", &id);
             E[i].push_back(id);
         }
     }
     val[] = p;
     dfs();
     int cnt = ;
     for(int i = ; i < n; i++) if(val[i] == mi && E[i].size() == ) cnt++;
     printf("%.4f %d\n", mi, cnt);
     return ;
 }

1107 Social Clusters

并查集搞搞。

 // 1107 Social Clusters
 #include <cstdio>
 #include <vector>
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = 1e3 + ;
 vector <int> E[N], ans;
 int fa[N], C[N];

 int fi(int x) {
     return x == fa[x] ? x : fa[x] = fi(fa[x]);
 }

 void Union(int x, int y) {
     int fx = fi(x), fy = fi(y);
     if(fx != fy) {
         fa[fy] = fx;
     }
 }

 int main() {
     bool f = ;
     int n, k, u, cnt = ;
     scanf("%d", &n);
     for(int i = ; i <= n; i++) {
         fa[i] = i;
         scanf("%d:", &k);
         while(k--) {
             scanf("%d", &u);
             E[u].push_back(i);
         }
     }
     for(int i = ; i < N; i++) {
         for(int j = ; j < E[i].size(); j++) {
             u = E[i][j];
             Union(u, E[i][]);
         }
     }
     for(int i = ; i <= n; i++) {
         C[fi(i)]++;
         if(i == fa[i]) cnt++;
     }
     printf("%d\n", cnt);
     for(int i = ; i <= n; i++) {
         if(C[i] != ) ans.push_back(C[i]);
     }
     sort(ans.begin(), ans.end());
     for(int i = ans.size() - ; i >= ; i--) {
         if(i != ans.size() - ) printf(" ");
         printf("%d", ans[i]);
     }
     return ;
 }

1108 Finding Average

注意 一个合法数字 的输出格式。

 // 1108 Finding Average
 #include <cstdio>
 #include <cstring>
 using namespace std;

 char str[];

 double check() {
     int i = , f = , cnt = ;
     if(str[] == '-') i = , f = -;
     int m = strlen(str);
     for(; i < m; i++) {
         if(str[i] >= '' && str[i] <= '') continue;
         if(str[i] == '.') {
             cnt++;
             if(cnt >= ) return ;
         }
         else return ;
     }
     double res = ;
     i = ;
     if(str[] == '-') i = , f = -;
     for(; i < m; i++) {
         if(str[i] == '.') {
             if(i +  < m) return ;
             if(i +  < m) res += (str[i + ] - '') / 100.0;
             if(i +  < m) res += (str[i + ] - '') / 10.0;
             return f * res;
         }
         res =  * res + 1.0 * (str[i] - '');
     }
     return f * res;
 }

 int main() {
     double average = ;
     int n, c = ;
     scanf("%d", &n);
     while(n--) {
         scanf("%s", str);
         double val = check();
         if(val >= - && val <= ) average += check(), c++;
         else{
             printf("ERROR: %s is not a legal number\n", str);
         }
     }
     if(c == ) printf("The average of %d number is %.2f\n", c, average / c);
     else if(c > ) printf("The average of %d numbers is %.2f\n", c, average / c);
     else printf("The average of 0 numbers is Undefined\n");
     return ;
 }

1109 Group Photo

模拟。

 // 1109 Group Photo
 #include <vector>
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 struct node {
     int h;
     string name;
 } tmp;

 bool cmp(node x, node y) {
     if(x.h == y.h) return x.name < y.name;
     return x.h > y.h;
 }

 vector<node> p;

 int main() {
     int n, k, per, last, id = ;
     cin >> n >> k;
     per = n / k;
     last = per + (n % k);
     for (int i = ; i <= n; i++) {
         cin >> tmp.name >> tmp.h;
         p.push_back(tmp);
     }
     sort(p.begin(), p.end(), cmp);
     for (int i = ; i < k; i++) {
         int now = per, f = -;
         if(i == ) now = last;
         int pos = now / ;
         vector<string> ans(n);
         while(pos >=  && pos < now) {
             ans[pos] = p[id++].name;
             pos += f;
             if(f < ) {
                 f *= -;
                 f++;
             } else {
                 f *= -;
                 f--;
             }
         }
         for (int j = ; j < now; j++) {
             cout << ans[j];
             if(j != now - ) cout << " ";
             else cout << endl;
         }
         ans.clear();
     }
     return ;
 }

1110 Complete Binary Tree

完全二叉树递归出的最大下标值一定等于总节点数。

 // 1110 Complete Binary Tree
 #include <queue>
 #include <iostream>
 using namespace std;

 int fa[], lch[], rch[];
 int n, root, last, maxindex = ;

 void dfs(int u, int index) {
     if(u == -) return ;
     if(index > maxindex) {
         maxindex = index;
         last = u;
     }
     dfs(lch[u],  * index);
     dfs(rch[u],  * index + );
 }

 int main() {
     cin >> n;
     for(int i = ; i < n; i++) fa[i] = lch[i] = rch[i] = -;
     for(int i = ; i < n; i++) {
         string s1, s2;
         cin >> s1 >> s2;
         if(s1 != "-") {
             fa[atoi(s1.c_str())] = i;
             lch[i] = atoi(s1.c_str());
         }
         if(s2 != "-") {
             fa[atoi(s2.c_str())] = i;
             rch[i] = atoi(s2.c_str());
         }
     }
     for(int i = ; i < n; i++) {
         if(fa[i] == -) root = i;
     }
     dfs(root, );
     if(maxindex == n) {
         cout << "YES " << last << endl;
     } else {
         cout << "NO " << root << endl;
     }
     return ;
 }

1112 Stucked Keyboard

模拟。

 // 1112 Stucked Keyboard
 #include <map>
 #include <iostream>
 using namespace std;

 string str;
 map<char, int> ok;

 int main() {
     int n, k, c = ;
     cin >> k >> str;
     n = str.size();
     for (int i = ; i < n; i++) {
         if(str[i] == str[i - ]) {
             c++;
         } else {
             if(c % k != ) ok[str[i - ]] = ;
             c = ;
         }
     }
     if(c >  && c % k != ) ok[str[n - ]] = ;
     for (int i = ; i < n; i++) {
         if(ok[str[i]] == ) {
             cout << str[i];
             ok[str[i]] = -;
         }
     }
     cout << endl;
     c = ;
     for (int i = ; i < n; i++) {
         if(str[i] == str[i - ]) {
             c++;
         } else {
             if(c % k == ) {
                 if(ok[str[i - ]] != ) for (int j = ; j <= c / k; j++) cout << str[i - ];
                 else  for (int j = ; j <= c; j++) cout << str[i - ];
             }
             else {
                 for (int j = ; j <= c; j++) cout << str[i - ];
             }
             c = ;
         }
     }
     if(c >  && c % k == ) {
         if(ok[str[n - ]] != ) for (int j = ; j <= c / k; j++) cout << str[n - ];
         else  for (int j = ; j <= c; j++) cout << str[n - ];
     }
     else {
         for (int j = ; j <= c; j++) cout << str[n - ];
     }
     return ;
 }

1113 Integer Set Partition

先排序，再前面加一加，后面加一加。

 // 1113 Integer Set Partition
 #include <iostream>
 #include <algorithm>
 using namespace std;

 typedef long long ll;
 const int N = 1e5 + ;
 ll a[N];

 int main() {
     int n, m;
     ll s1 = , s2 = ;
     cin >> n;
     for (int i = ; i <= n; i++) cin >> a[i];
     sort(a + , a +  + n);
     for (int i = n /  + ; i <= n; i++) s1 += a[i];
     for (int i = ; i < n /  + ; i++) s2 += a[i];
     cout << (n % ) << " ";
     cout << abs(s1 - s2) << endl;
     return ;
 }

1114 Family Property

暴力模拟即可。

 // 1114 Family Property
 #include <map>
 #include <vector>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N =  + ;
 int fa[N], M[N], A[N];
 int fi(int x) {
     return fa[x] == x ? x : fa[x] = fi(fa[x]);
 }

 void Union(int x, int y) {
     if(x == - || y == -) return ;
     int fx = fi(x), fy = fi(y);
     if(fx != fy) {
         fa[fx] = fy;
     }
 }

 void init() {
     for(int i = ; i < N; i++) fa[i] = i;
 }

 int cnt = ;
 vector<int> V, E[N];
 map<int, int> mp;

 struct node {
     int ansID, ansM;
     double avg1, avg2;
 }ans[N];

 map<int, int> vis;

 bool cmp(node x, node y) {
     if(x.avg2 == y.avg2) return x.ansID < y.ansID;
     return x.avg2 > y.avg2;
 }

 int main() {
     init();
     int n;
     cin >> n;
     for (int i = ; i <= n; i++) {
         int id, father, mother, child, k;
         cin >> id >> father >> mother >> k;
         Union(id, father);
         if(father != -) V.push_back(father);
         Union(id, mother);
         if(mother != -) V.push_back(mother);
         while (k--) {
             cin >> child;
             if(child != -) V.push_back(child);
             Union(id, child);
         }
         V.push_back(id);
         cin >> M[id] >> A[id];
     }
     for (int i = ; i < V.size(); i++) {
         int u = V[i];
         if(fa[u] == u && !mp[u]) {
             cnt++;
             mp[u] = cnt;
         }
     }
     for (int i = ; i < V.size(); i++) {
         int u = V[i];
         if(!vis[u]) E[mp[fi(u)]].push_back(u), vis[u] = ;
     }
     for (int i = ; i <= cnt; i++) {
         int minid = ;
         double sum1 = ;
         double sum2 = ;
         for(int j = ; j < E[i].size(); j++) {
             int v = E[i][j];
             minid = min(minid, v);
             sum1 += M[v];
             sum2 += A[v];
         }
         ans[i].ansID = minid;
         ans[i].ansM = E[i].size();
         ans[i].avg1 = sum1 / E[i].size();
         ans[i].avg2 = sum2 / E[i].size();
     }
     sort(ans + , ans +  + n, cmp);
     cout << cnt << endl;
     for (int i = ; i <= cnt; i++) {
         printf("%04d %d %.3f %.3f\n", ans[i].ansID, ans[i].ansM, ans[i].avg1, ans[i].avg2);
     }
     return ;
 }

1115 Counting Nodes in a BST

用链表实现二叉搜索树的插入。构建完树后，DFS一遍，在对应深度更新节点数。

 // 1115 Counting Nodes in a BST
 #include <iostream>
 using namespace std;

 struct node {
     int val;
     struct node *left, *right;
 };

 const int N =  + ;
 int num[N], maxd = -;

 node *build(node *root, int v) {
     if(root == NULL) {
         root = new node();
         root -> val = v;
         root -> left = root -> right = NULL;
     } else if(v > root->val) {
         root->right = build(root->right, v);
     } else {
         root->left = build(root->left, v);
     }
     return root;
 }

 void dfs(node *root, int dp) {
     if(root == NULL) {
         maxd = max(maxd, dp);
         return ;
     }
     num[dp]++;
     dfs(root->left, dp + );
     dfs(root->right, dp + );
 }

 int main() {
     int n, k;
     node *root = NULL;
     cin >> n;
     while(n--) {
         cin >> k;
         root = build(root, k);
     }
     dfs(root, );
     cout << num[maxd - ] << " + " << num[maxd - ] << " = " << num[maxd - ] + num[maxd - ] << endl;
     return ;
 }

1116 Come on! Let's C

模拟。

 // 1116 Come on! Let's C
 #include <map>
 #include <iostream>
 using namespace std;

 map<int, int> Rank;

 bool check(int x) {
     if(x < ) return false;
     for(int i = ; i * i <= x; i++) {
         if(x % i == ) return false;
     }
     return true;
 }

 int main() {
     int n, k;
     cin >> n;
     for (int i = ; i <= n; i++) {
         cin >> k;
         Rank[k] = i;
     }
     cin >> n;
     while (n--) {
         cin >> k;
         printf("%04d: ", k);
         if(Rank[k] == -) cout << "Checked" << endl;
         else if(Rank[k] == ) cout << "Are you kidding?" << endl;
         else if(Rank[k] == ) cout << "Mystery Award" << endl, Rank[k] = -;
         else if(check(Rank[k])) cout << "Minion" << endl, Rank[k] = -;
         else cout << "Chocolate" << endl, Rank[k] = -;
     }
     return ;
 }

1117 Eddington Number

前缀和

 // 1117 Eddington Number
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = 1e6 + ;
 int d[N];

 int main() {
     int n, k, ans = ;
     cin >> n;
     for(int i = ; i <= n; i++) {
         cin >> k;
         d[k]++;
     }
     for(int i = ; i < N; i++) d[i] += d[i - ];
     for(int i = ; i < N; i++) {
         if((n - d[i]) >= i) ans = max(ans, i);
     }
     cout << ans << endl;
     return ;
 }

1118 Birds in Forest

并查集

 // 1118 Birds in Forest
 #include <cstdio>
 #include <vector>
 using namespace std;

 const int N = 1e4 + ;
 bool vis[N];
 int fa[N], cnt = ;
 vector <int> birds;

 int fi(int x) {
     return x == fa[x] ? x : fa[x] = fi(fa[x]);
 }

 void Union(int x, int y) {
     int fx = fi(x), fy = fi(y);
     if(fx != fy) {
         fa[fx] = fy;
     }
 }

 void init() {
     for (int i = ; i < N; i++) fa[i] = i;
 }

 int main() {
     init();
     int m, n, k, u, v;
     scanf("%d", &n);
     while (n--) {
         scanf("%d", &k);
         for (int i = ; i <= k; i++) {
             scanf("%d", &v);
             if(!vis[v]) vis[v] = , birds.push_back(v);
             if(i == ) u = v;
             else Union(u, v);
         }
     }
     for (int i = ; i < birds.size(); i++) {
         u = birds[i];
         if(fa[u] == u) cnt++;
     }
     printf("%d %d\n", cnt, birds.size());
     scanf("%d", &m);
     while (m--) {
         scanf("%d %d", &u, &v);
         if(fi(u) == fi(v)) printf("Yes\n");
         else printf("No\n");
     }
     return ;
 }

1119 Pre- and Post-order Traversals 

通过前序和后序先建棵树。（题目中说明可以随意建棵符合的树）再中序遍历即可。

 #include <bits/stdc++.h>
 using namespace std;

 const int maxn=;
 int preOrder[maxn], postOrder[maxn];
 bool isUnique=true;

 struct Node{
     int left=-,right=-;
 }node[maxn];

 void build(int preL,int preR,int postL,int postR){
     if(preL>=preR){
         return;
     }
     int fa=preL;
     int val=preOrder[preL+];
     int postIdx;
     for(int i=postL;i<postR;i++){
         if(val==postOrder[i]){
             postIdx=i;
             break;
         }
     }
     int num=postIdx-postL;
     if(preR-preL-==num){
         isUnique=false;
     }
     node[fa].left=preL+;
     build(preL+,preL+num+,postL,postIdx);
     if(preR-preL->num){
         node[fa].right=preL+num+;
         build(preL+num+,preR,postIdx+,postR-);
     }
 }

 bool first=true;

 void inOrder(int root){
     if(root==-){
         return;
     }
     inOrder(node[root].left);
     if(first){
         first=false;
         printf("%d",preOrder[root]);
     }
     else
         printf(" %d",preOrder[root]);
     inOrder(node[root].right);
 }

 int main(){
     int n;
     scanf("%d",&n);
     for(int i=;i<=n;i++) scanf("%d",&preOrder[i]);
     for(int i=;i<=n;i++) scanf("%d",&postOrder[i]);
     build(,n,,n);
     if(isUnique) printf("Yes\n");
     else printf("No\n");
     inOrder();
     printf("\n");
     return ;
 }

1120 Friend Numbers

模拟

 // 1120 Friend Numbers
 #include <set>
 #include <cstdio>
 #include <iostream>
 using namespace std;

 const int N = 1e4 + ;
 int a[N], b[N];

 int cal(int x) {
     int sum1 = ;
     while (x) {
         sum1 += x % ;
         x /= ;
     }
     return sum1;
 }

 int check(int x, int y) {
     if (x == y) return x;
     return ;
 }

 set<int> ans;

 int main() {
     int n;
     bool f = ;
     scanf("%d", &n);
     for (int i = ; i <= n; i++) scanf("%d", &a[i]), b[i] = cal(a[i]);
     for (int i = ; i <= n; i++) {
         for (int j = i; j <= n; j++) {
             int val = check(b[i], b[j]);
             if (val) ans.insert(val);
         }
     }
     printf("%d\n", ans.size());
     for (auto x : ans) {
         if (!f) f = ;
         else printf(" ");
         printf("%d", x);
     }
     return ;
 }

1121 Damn Single

模拟

 // 1121 Damn Single
 #include <map>
 #include <vector>
 #include <cstdio>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 map<int, int> m, vis;
 vector<int> p;
 const int N = 1e4 + ;
 int a[N];

 int main() {
     int n, x, y;
     scanf("%d", &n);
     while (n--) {
         scanf("%d %d", &x, &y);
         x++; y++;
         m[x] = y;
         m[y] = x;
     }
     scanf("%d", &n);
     for (int i = ; i <= n; i++) {
         scanf("%d", &a[i]);
         a[i]++;
         vis[a[i]] = ;
     }
     for (int i = ; i <= n; i++) {
         if (vis[ m[a[i]] ]) continue;
         p.push_back(a[i]);
     }
     sort(p.begin(), p.end());
     printf("%d\n", p.size());
     for (int i = ; i < p.size(); i++) {
         if (i != ) printf(" ");
         printf("%05d", p[i] - );
     }
     return ;
 }

1122 Hamiltonian Cycle

模拟

 // 1122 Hamiltonian Cycle
 #include <set>
 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 using namespace std;

 const int N = ;
 int MAP[N][N];
 set<int> s;

 int main() {
     memset(MAP, -, sizeof(MAP));
     int n, m, k;
     scanf("%d %d", &n, &m);
     for (int i = ; i <= m; i++) {
         int u, v;
         scanf("%d %d", &u, &v);
         MAP[u][v] = ; MAP[v][u] = ;
     }
     scanf("%d", &k);
     while (k--) {
         bool f = ;
         int u, v, root;
         scanf("%d", &m);
         scanf("%d", &root);
         s.insert(root);
         u = root;
         for (int i = ; i < m; i++) {
             scanf("%d", &v);
             s.insert(v);
             if (MAP[u][v] == -) f = ;
             u = v;
         }
         if (root != u || s.size() != n || m != n + ) f = ;
         if (!f) printf("NO\n");
         else printf("YES\n");
         s.clear();
     }
     return ;
 }