pat1121-1131-白红宇

pat1121-1131

阅读量：5295 次

发布时间：2019-06-14

本文共 16869 字，大约阅读时间需要 56 分钟。

1121

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;typedef long long ll;const int N = 1e6+5;const int INF = 0x3f3f3f3f;#define MP(x, y) make_pair(x, y)int pai[N];int a[N];int has[N];int ord[N];int main() { int n; while(~scanf("%d", &n)) { memset(pai, -1, sizeof(pai)); for(int i = 0; i < n; ++i) { int a, b; scanf("%d%d", &a, &b); pai[a] = b; pai[b] = a; } int m; scanf("%d", &m); for(int i = 0; i < m; ++i) { scanf("%d", &a[i]); has[a[i]] ++; if(pai[a[i]] != -1) has[pai[a[i]]] ++; } int tot = 0; for(int i = 0; i < m; ++i) { if(has[a[i]] == 1) { ord[tot ++] = a[i]; } } sort(ord, ord + tot); printf("%d\n", tot); for(int i = 0; i < tot; ++i) { if(i) printf(" "); printf("%05d", ord[i]); } if(tot) printf("\n"); } return 0;}

1122 我把爆搜都写完了，才发现这题的圈顺序是给定的，我爆搜就不删了

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;typedef long long ll;const int N = 205;const int INF = 0x3f3f3f3f;#define MP(x, y) make_pair(x, y)struct Node{ int to, nx;}E[N*N*2];int mp[N][N];int head[N], tot;void add(int fr, int to) { E[tot].to = to; E[tot].nx = head[fr]; head[fr] = tot ++;}set
               
                 st;int suc;void dfs(int l, int r) { printf("%d %d\n", l, r); if(suc) return; if(st.size() == 0) { if(mp[l][r]) suc = 1; return; } if(st.size() == 1) { int tt = *st.begin(); if(mp[l][tt] && mp[r][tt]) { suc = 1; } return; } vector
                
                  ch1; vector
                 
                   ch2; for(int i = head[l]; ~i; i = E[i].nx) { if(st.find(E[i].to) != st.end()) { ch1.push_back(E[i].to); } } if(l == r) { for(int i = 0; i < ch1.size() && !suc; ++i) { for(int j = i+1; j < ch1.size() && !suc; ++j) { st.erase(ch1[i]); st.erase(ch1[j]); dfs(ch1[i], ch1[j]); st.insert(ch1[i]); st.insert(ch1[j]); } } return; } for(int i = head[r]; ~i; i = E[i].nx) { if(st.find(E[i].to) != st.end()) { ch2.push_back(E[i].to); } } for(int i = 0; i < ch1.size() && !suc; ++i) { for(int j = 0; j < ch2.size() && !suc; ++j) { if(ch1[i] != ch2[j]) { st.erase(ch1[i]); st.erase(ch2[j]); dfs(ch1[i], ch2[j]); st.insert(ch1[i]); st.insert(ch2[j]); } } }}int main() { int n,m; while(~scanf("%d %d", &n, &m)) { memset(head, -1, sizeof(head)); tot = 0; for(int i = 0; i < m; ++i) { int a, b; scanf("%d %d", &a, &b); add(a, b); add(b, a); mp[a][b] = mp[b][a] = 1; } int k; scanf("%d", &k); while(k --) { int a; scanf("%d", &a); int fl = 1; st.clear(); int pre = -1; int St = -1; for(int i = 0; i < a; ++i) { int b; scanf("%d", &b); if(St == -1) St = b; if(st.find(b) != st.end() && i != a-1) fl = 0; if(i == a-1 && St != b) fl = 0; if(~pre && !mp[b][pre]) fl = 0; pre = b; st.insert(b); } // int tt = *st.begin(); st.erase(tt); // suc = 0; // dfs(tt, tt); if(fl && a > 4) printf("YES\n"); else printf("NO\n"); } } return 0;}

1123 和之前一道avl类似

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef long long ll;const int N = 25;const int INF = 0x3f3f3f3f;#define MP(x, y) make_pair(x, y)int root;int num[N];int L[N], R[N], fa[N];int n;void insert(int x, int tag) { // printf("tag: %d\n", x); if(!root) { root = tag; fa[tag] = tag; return; } if(num[x] > num[tag]) { if(!L[x]) L[x] = tag, fa[tag] = x; else insert(L[x], tag); }else { if(!R[x]) R[x] = tag, fa[tag] = x; else insert(R[x], tag); }}struct Node{ int po, val; Node(int a=0, int b=0):po(a), val(b){}}E[10];int cmp(Node a,Node b) { return a.val < b.val;}void LL(int x) { // printf("LL\n"); int fart = fa[fa[x]]; int t1 = x; int t2 = R[x]; int t3 = fa[x]; fa[t1] = 0; fa[t2] = 0; fa[t3] = 0; R[t1] = t3; fa[t3] = t1; L[t3] = t2; fa[t2] = t3; if(t3 == root) { root = t1; fa[t1] = t1; }else if(L[fart] == t3) { L[fart] = t1; fa[t1] = fart; }else R[fart] = t1, fa[t1] = fart;}void RR(int x) { // printf("RR\n"); int fart = fa[fa[x]]; int t1 = x; int t2 = L[x]; int t3 = fa[x]; fa[t1] = 0; fa[t2] = 0; fa[t3] = 0; L[t1] = t3; fa[t3] = t1; R[t3] = t2; fa[t2] = t3; if(t3 == root) { root = t1; fa[t1] = t1; }else if(L[fart] == t3) { L[fart] = t1; fa[t1] = fart; }else R[fart] = t1, fa[t1] = fart;}void LR(int x, int tag) { // printf("LR\n"); int fart = fa[fa[x]]; int t1 = x; int t2 = R[x]; int t3 = fa[x]; int a1 = L[t2]; int a2 = R[t2]; fa[t1] = 0; fa[t2] = 0; fa[t3] = 0; R[t1] = 0; L[t3] = 0; L[t2] = t1; fa[t1] = t2; R[t2] = t3; fa[t3] = t2; if(t3 == root) { root = t2; fa[t2] = t2; }else if(L[fart] == t3) { L[fart] = t2; fa[t2] = fart; }else { R[fart] = t2; fa[t2] = fart; } if(a1) insert(root, a1); if(a2) insert(root, a2);}void RL(int x, int tag) { // printf("RL\n"); int fart = fa[fa[x]]; int t1 = x; int t2 = L[x]; int t3 = fa[x]; int a1 = L[t2]; int a2 = R[t2]; L[t1] = 0; R[t3] = 0; fa[t1] = 0; fa[t2] = 0; fa[t3] = 0; L[t2] = t3; fa[t3] = t2; R[t2] = t1; fa[t1] = t2; // printf("hh %d %d %d\n", num[t1], num[t2], num[t3]); if(t3 == root) { root = t2; fa[t2] = t2; }else if(L[fart] == t3) { L[fart] = t2; fa[t2] = fart; }else { R[fart] = t2; fa[t2] = fart; } // printf("hh %d %d", fart, R[fart]); if(a1) insert(root, a1); if(a2) insert(root, a2);}void fix(int x) { int rt = fa[fa[x]]; int fart = fa[rt]; if( (L[rt]==0) + (R[rt]==0) == 1) { int tot = 0; for(int i = 0, tt = x; i < 3; ++i) { E[tot++] = Node(tt, num[tt]); tt = fa[tt]; } sort(E, E+tot, cmp); L[E[1].po] = E[0].po; fa[E[0].po] = E[1].po; R[E[1].po] = E[2].po; fa[E[2].po] = E[1].po; L[E[0].po] = 0; R[E[0].po] = 0; L[E[2].po] = 0; R[E[2].po] = 0; if(root == rt) { root = E[1].po; fa[root] = root; }else if(L[fart] == rt) { L[fart] = E[1].po; fa[E[1].po] = fart; }else { R[fart] = E[1].po; fa[E[1].po] = fart; } }else { // printf("%d %d %d\n", x, rt, fa[rt]); if (L[fa[rt]] == rt && L[rt] == fa[x] ) LL(rt); else if(R[fa[rt]] == rt && R[rt] == fa[x] ) RR(rt); else if(L[fa[rt]] == rt && R[rt] == fa[x] ) LR(rt, x); else if(R[fa[rt]] == rt && L[rt] == fa[x] ) RL(rt, x); }}void test(int x, int pre) { printf("%d from %d\n", x, pre); if(L[x]) test(L[x], x); if(R[x]) test(R[x], x);}int height[N]; int tag;void dfs(int x) { int t1 = 0, t2 = 0; if(L[x]) dfs(L[x]), t1 = height[L[x]]; if(R[x]) dfs(R[x]), t2 = height[R[x]]; height[x] = max(t1, t2)+1; if( abs(t1- t2) > 1 && !tag) tag = x;}void solve(int x) { // printf("do %d\n", x); memset(height, 0, sizeof(height)); tag = 0; dfs(root); if(tag) { int t1 = tag; if(height[L[t1]] > height[R[t1]]) t1 = L[t1]; else t1 = R[t1]; if(height[L[t1]] > height[R[t1]]) t1 = L[t1]; else t1 = R[t1]; if(height[L[t1]] > height[R[t1]]) t1 = L[t1]; else if(height[L[t1]] < height[R[t1]]) t1 = R[t1]; // printf("%d %d\n", tag, t1); fix(t1); } // test(root, root); // printf("\n");}void bfs(int x) { int all = 0; queue
              
                Q; Q.push(x); while(Q.front() != 0) { int po = Q.front(); Q.pop(); all ++; Q.push(L[po]); Q.push(R[po]); } while(!Q.empty()) Q.pop(); Q.push(x); int nn = 0; while(!Q.empty()) { int po = Q.front(); Q.pop(); if(!nn) nn = 1; else printf(" "); printf("%d", num[po]); if(L[po]) Q.push(L[po]); if(R[po]) Q.push(R[po]); } printf("\n"); if(all == n) printf("YES\n"); else printf("NO\n");}int main() { while(~scanf("%d", &n)) { root = 0; memset(fa, 0, sizeof(fa)); memset(L, 0, sizeof(L)); memset(R, 0, sizeof(R)); for(int i = 1; i <= n; ++i) { scanf("%d", &num[i]); insert(root, i); solve(i); // fa[root] = root; // check(root); } // printf("hh\n"); bfs(root); // printf("%d\n", num[root]); } return 0;}

1124

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef long long ll;const int N = 25;const int INF = 0x3f3f3f3f;#define MP(x, y) make_pair(x, y)map
              
                mp;int main() { int m, n, s; while(~scanf("%d %d %d", &m, &n, &s)) { int won = s; int all = 0; mp.clear(); for(int i = 1, j = 1; i <= m; ++i) { char s[10]; scanf("%s", s); if(j == won) { if(mp.find(s) == mp.end()) printf("%s\n", s), won += n, all ++; else j --; mp[s] = 1; } j++; } if(!all) printf("Keep going...\n"); } return 0;}

1125 讲道理我没有读懂题之前 = =我以为在你们选几个组成不就行了，直接选两个最大的

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef long long ll;const int N = 1e4+5;const int INF = 0x3f3f3f3f;#define MP(x, y) make_pair(x, y)int a[N];int main() { int n; while(~scanf("%d", &n)) { for(int i = 0; i < n; ++i) scanf("%d", &a[i]); sort(a, a + n); int ans = a[0]; for(int i = 1; i < n; ++i) { ans = (ans + a[i]) / 2; } printf("%d\n", ans); } return 0;}

1126需先判断下图的连通性

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef long long ll;const int N = 505;const int INF = 0x3f3f3f3f;#define MP(x, y) make_pair(x, y)struct Node{ int to, nx;}E[N*N*2];int head[N], tot;int vis[N];void add(int fr, int to) { E[tot].to = to; E[tot].nx = head[fr]; head[fr] = tot ++;}void dfs(int x) { for(int i = head[x]; ~i; i = E[i].nx) { int to = E[i].to; if(!vis[to]) { vis[to] = 1; dfs(to); } }}int in[N];int main() { int n, m; while(~scanf("%d %d", &n, &m)) { memset(in, 0, sizeof(in)); memset(vis, 0, sizeof(vis)); memset(head, -1, sizeof(head)); tot = 0; for(int i = 0; i < m; ++i) { int a, b; scanf("%d %d", &a, &b); add(a, b); add(b, a); in[a] ++; in[b] ++; } vis[1] = 1; dfs(1); int fl = 1; for(int i = 1; i <= n; ++i) { if(!vis[i]) { fl = 0; break; } } int odd = 0; int even = 0; for(int i = 1; i <= n; ++i) { if(in[i] % 2 == 0) even ++; else odd ++; } for(int i = 1; i <= n; ++i) { if(i != 1) printf(" "); printf("%d", in[i]); } printf("\n"); if(odd == 0 && fl) printf("Eulerian\n"); else if(odd == 2 && fl) printf("Semi-Eulerian\n"); else printf("Non-Eulerian\n"); } return 0;}

1127

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef long long ll;const int N = 35;const int INF = 0x3f3f3f3f;#define MP(x, y) make_pair(x, y)int in[N];int post[N];map
              
                L;map
               
                 R;int solve(int LL, int RR, int l, int r) { if(l > r) return 0; else if(l == r) return post[l]; int tag = post[r]; int po = 0; for(int i = LL; i <= RR; ++i) { if(in[i] == tag) { po = i; break; } } int _po = l + (po-1-LL); L[tag] = solve(LL, po-1, l, _po); R[tag] = solve(po+1, RR, _po+1, r-1); return tag;}void bfs(int x) { queue
                
                  Q; Q.push(x); int fl = 1; while(!Q.empty()) { vector
                 
                   vc; int ed = Q.size(); for(int i = 0; i < ed; ++i) { int po = Q.front(); Q.pop(); vc.push_back(po); if(L[po]) Q.push(L[po]); if(R[po]) Q.push(R[po]); } if(fl) for(int i = vc.size()-1; i >= 0; --i) { if(vc[i] != x) printf(" "); printf("%d", vc[i]); }else for(int i = 0; i < vc.size(); ++i) { if(vc[i] != x) printf(" "); printf("%d", vc[i]); } fl ^= 1; } printf("\n");}int main() { int n; while(~scanf("%d", &n)) { for(int i = 1; i <= n; ++i) { scanf("%d", &in[i]); } for(int i = 1; i <= n; ++i) scanf("%d", &post[i]); int root = solve(1, n, 1, n); bfs(root); } return 0;}

1128

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef long long ll;const int N = 1005;const int INF = 0x3f3f3f3f;#define MP(x, y) make_pair(x, y)int dia1[N*2];int row[N];int dia2[N*2];int main() { int k; while(~scanf("%d", &k)) { for(int i = 1; i <= k; ++i) { int a; scanf("%d", &a); int fl = 1; for(int j = 1; j <= a; ++j) { int b; scanf("%d", &b); int t1 = b; int t2 = b-j + a; int t3 = b+j; if(row[t1] == i|| dia1[t2] == i || dia2[t3] == i ) fl = 0; row[t1] = i; dia1[t2] = i; dia2[t3] = i; } if(fl) printf("YES\n"); else printf("NO\n"); } } return 0;}

1129

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef long long ll;const int N = 5e4+5;const int INF = 0x3f3f3f3f;#define MP(x, y) make_pair(x, y)int has[N];int a[N];struct Node{ int nu, po; Node(int a=0, int b=0):nu(a), po(b) {} bool operator <(const Node &T) const { if(nu != T.nu) return nu > T.nu; else return po < T.po; }};set
              
                st;set
               
                 ::iterator it;int main() { int n, k; while(~scanf("%d %d", &n, &k)) { st.clear(); memset(has, 0, sizeof(has)); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); has[a[1]] ++; st.insert(Node(has[a[1]], a[1])); for(int i = 2; i <= n; ++i) { printf("%d: ", a[i]); int cnt = 0; for(it = st.begin(); it != st.end(); ++it) { if(it != st.begin()) printf(" "); printf("%d", (*it).po); cnt ++; if(cnt >= k) break; } printf("\n"); has[a[i]] ++; it = st.find(Node(has[a[i]]-1, a[i]) ); if( it != st.end() ) st.erase(it), st.insert(Node(has[a[i]], a[i])); else { st.insert(Node(has[a[i]], a[i])); if(st.size() > k) st.erase(--st.end()); } } } return 0;}

1030

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef long long ll;const int N = 25;const int INF = 0x3f3f3f3f;#define MP(x, y) make_pair(x, y)char num[N][15];int dep[N];int root;int L[N], R[N];void dfs(int x) { if(x != root && L[x] + R[x]) printf("("); if(L[x]) dfs(L[x]); printf("%s", num[x]); if(R[x]) dfs(R[x]); if(x != root && L[x] + R[x]) printf(")");}int main() { int n; while(~scanf("%d", &n)) { for(int i = 1; i <= n; ++i) { char b[10], c[10]; scanf("%s %s %s", num[i], b, c); int tt; if(b[0] != '-') { sscanf(b, "%d", &tt); L[i] = tt, dep[tt] ++; } if(c[0] != '-') { sscanf(c, "%d", &tt); R[i] = tt; dep[tt] ++; } } for(int i = 1; i <= n; ++i) { if(!dep[i]) { root = i; dfs(i); break; } } printf("\n"); } return 0;}

1031 最后一题还是花了一点时间，简单来说就是最短路即可，但是中间处理还是有点难的

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef long long ll;const int N = 105;const int M = 1e5+5;const int INF = 0x3f3f3f3f;#define MP(x, y) make_pair(x, y)map
              
                nam;map
               
                 ::iterator it;int _nam[M];vector
                
                  input[N];int n; int tol;struct Node{ int nx, to, ty;}E[M*10];int head[M], tot;void add(int fr, int to, int ty) { E[tot].to = to; E[tot].nx = head[fr]; E[tot].ty = ty; head[fr] = tot++;}struct Hode{ int po, di, ti, ty; Hode(int a=0, int b=0, int c=0, int d=0):po(a), di(b), ti(c), ty(d) {} bool operator < (const Hode & T) const{ if(di != T.di) return di > T.di; else return ti > T.ti; }};pair
                 
                   pre[M]; int vis[M];int dis[M], tim[M];vector
                  
                   
                     > ans;void dfs(int x, int s) {// printf("%d %d\n", x, _nam[x]); if(x == s) { return ; } dfs(pre[x].first, s); ans.push_back(MP(x, pre[x].second));}void dij(int s, int t) {// printf("%d %d\n", s, t); for(int i = 1; i <= tol; ++i) { vis[i] = 0; dis[i] = INF; tim[i] = INF; } dis[s] = 0; tim[s] = 0; priority_queue
                    
                      Q; Q.push(Hode(s, dis[s], tim[s], INF)); while(!Q.empty()) { int po = Q.top().po; int ty = Q.top().ty; Q.pop(); if(vis[po]) continue; vis[po] = 1; for(int i = head[po]; ~i; i = E[i].nx) { int to = E[i].to; int tt = ty != E[i].ty; if(dis[to] > dis[po] + 1) { dis[to] = dis[po] + 1; tim[to] = tim[po] + tt; pre[to] = MP(po, E[i].ty); Q.push(Hode(to, dis[to], tim[to], E[i].ty)); }else if(dis[to] == dis[po] + 1 && tim[to] > tim[po] + tt ) { tim[to] = tim[po] + tt; pre[to] = MP(po, E[i].ty); Q.push(Hode(to, dis[to], tim[to], E[i].ty)); } } } ans.clear(); dfs(t, s); printf("%d\n", dis[t]); int fr = s; ans.push_back(MP(INF, INF)); for(int i = 1; i < ans.size(); ++i) { if(ans[i].second != ans[i-1].second) { printf("Take Line#%d from %04d to %04d.\n", ans[i-1].second, _nam[fr], _nam[ans[i-1].first]); fr = ans[i-1].first; } }}int main() { while(~scanf("%d", &n)) { memset(head, -1, sizeof(head)); tot = 0; for(int i = 1; i <= n; ++i) { int m; scanf("%d", &m); input[i].push_back(m); for(int j = 0; j < m; ++j) { int b; scanf("%d", &b); input[i].push_back(b); nam[b] ++; } } tol = 0; for(it = nam.begin(); it != nam.end(); ++it) { nam[it->first] = ++tol; _nam[tol] = it->first; } // for(int i = 1; i <= tol; ++i) printf("%d:%d ", _nam[i], nam[_nam[i]]); printf("\n"); for(int i = 1; i <= n; ++i) { for(int j = 2; j < input[i].size(); ++j) { add(nam[input[i][j]], nam[input[i][j-1]], i); add(nam[input[i][j-1]], nam[input[i][j]], i); } } int m; scanf("%d", &m); while(m --) { int a, b; scanf("%d %d", &a, &b); dij(nam[a], nam[b]); } } return 0;}