[*]2020天梯训练赛第七周

7-1 重要的话说三遍

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
constexpr int mod2 = 998244353;
constexpr int MAXNe5 = 1e5 + 7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
int main() {
    cout << "I'm gonna WIN!\nI'm gonna WIN!\nI'm gonna WIN!";
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-2 后天

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
constexpr int mod2 = 998244353;
constexpr int MAXNe5 = 1e5 + 7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
int main() {
    int n = read();
    cout << ((n + 2) % 7 == 0 ? 7 : (n + 2) % 7);
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-3 大笨钟

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 +7;
constexpr int mod2 = 998244353;
constexpr int MAXNe5 = 1e5 +7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
int main() {
    int h = read() - 12, m = read();
    if(h < 0 || (h == 0 && m == 0)) printf("Only %02d:%02d.  Too early to Dang.", h + 12, m);
    else {
        if(m != 0) h ++;
        for(int i = 0; i < h; ++ i) cout << "Dang";
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-4 奇偶分家

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
constexpr int mod2 = 998244353;
constexpr int MAXNe5 = 1e5 + 7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
int main() {
    int n = read(), odd = 0, even = 0;
    while(n --) {
        int input = read();
        if(input & 1) odd ++;
        else even ++;
    }
    cout << odd << ' ' << even;
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-5 到底有多二

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
constexpr int mod2 = 998244353;
constexpr int MAXNe5 = 1e5 + 7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
int main() {
    string input;
    cin >> input;
    double t1 = 1, t2 = 1, even = 0;
    int len = input.length(), i = 0;
    if(input[0] == '-') t1 += 0.5, i = 1;
    if(input[len - 1] % 2 == 0) t2 ++;
    for(; i < len; ++i) {
        if (input[i] == '2') even++;
    }
    if(input[0] == '-') len --;
    printf("%.2f%%", even / len * t1 * t2 * 100);
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-6 谁先倒

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 +7;
constexpr int mod2 = 998244353;
constexpr int MAXNe5 = 1e5 +7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
int main() {
    int a = read(), b = read(), n = read(), c = 0, d = 0;
    while(n --) {
        int a1 = read(), b1 = read(), a2 = read(), b2 = read();
        if(a1 + a2 == b1 && b1 == b2) continue;
        else if(a1 + a2 == b1) c ++;
        else if(a1 + a2 == b2) d ++;
        if(c > a) {
            cout << "A\n" << d;
            break;
        }
        if(d > b) {
            cout << "B\n" << c;
            break;
        }
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-7 帅到没朋友

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
constexpr int mod2 = 998244353;
constexpr int MAXNe5 = 1e5 + 7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
int main() {
    int N = read();
    map<int, bool> mp;
    while(N --) {
        int M = read();
        if(M == 1) {
            int tmp = read();
        } else {
            for(int i = 0; i < M; ++ i) {
                int tmp = read();
                mp[tmp] = 1;
            }
        }
    }
    int M = read();
    vector<int> ans;
    while(M --) {
        int input = read();
        if(mp.find(input) == mp.end()) {
            mp[input] = 1;
            ans.emplace_back(input);
        }
    }
    if(ans.size() == 0) cout << "No one is handsome";
    else
        for(int i = 0; i < ans.size(); ++ i)
            cout << setw(5) << setfill('0') << ans[i] << (i + 1 == ans.size() ? "" : " ");
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-8 输出GPLT

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
constexpr int mod2 = 998244353;
constexpr int MAXNe5 = 1e5 + 7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
int main() {
    string str;
    cin >> str;
    int len = str.length(), G = 0, P = 0, L = 0, T = 0;
    for(int i = 0; i < len; ++ i) {
        char tmp = toupper(str[i]);
        if(tmp == 'G') G ++;
        else if(tmp == 'P') P ++;
        else if(tmp == 'L') L ++;
        else if(tmp == 'T') T ++;
    }
    while(G + P + L + T != 0) {
        if(G) G --, cout << 'G';
        if(P) P --, cout << 'P';
        if(L) L --, cout << 'L';
        if(T) T --, cout << 'T';
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-9 抢红包

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
constexpr int mod2 = 998244353;
constexpr int MAXNe5 = 1e5 + 7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region 
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
int ord[MAXNe5], num[MAXNe5], mon[MAXNe5];
bool cmp(int a, int b) {
    if(num[a] == num[b] && mon[a] == mon[b]) return a < b;
    else if(mon[a] == mon[b]) return num[a] > num[b];
    else return mon[a] > mon[b];
}
int main() {
    int n = read();
    for(int i = 1; i <= n; ++ i) {
        ord[i] = i;
        int k = read(), sum = 0;
        for(int _ = 0; _ < k; ++ _) {
            int tmp1 = read(), tmp2 = read();
            num[tmp1] ++; mon[tmp1] += tmp2; sum += tmp2;
        }
        mon[i] -= sum;
    }
    sort(ord + 1, ord + n + 1, cmp);
    for(int i = 1; i <= n; ++ i) {
        printf("%d %.2f\n", ord[i], mon[ord[i]] / 100.0);
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-10 排座位

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
constexpr int mod2 = 998244353;
constexpr int MAXNe5 = 1e5 + 7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region 
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
int fa[1007], rel[107][107];
void init(int x) {
    for(int i = 0; i <= x; ++ i) fa[i] = i;
}
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main() {
    int n = read(), m = read(), k = read();
    memset(rel, 0, sizeof(rel));
    init(n);
    for(int i = 0; i < m; ++ i) {
        int a = read(), b = read(), relation = read();
        if(relation == 1) {
            int fa1 = find(a), fb1 = find(b);
            if(fa1 != fb1) fa[fa1] = fb1;
        } else {
            rel[min(a, b)][max(a, b)] = 1;
        }
    }
    for(int i = 0; i < k; ++ i) {
        int a = read(), b = read();
        bool res1 = (find(a) == find(b)), res2 = (rel[min(a, b)][max(a, b)]);
        if(res1) {
            if(res2) puts("OK but...");
            else puts("No problem");
        } else {
            if(res2) puts("No way");
            else puts("OK");
        }
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-11 玩转二叉树

#include <bits/stdc++.h>
#define lson (rt->lchild)
#define rson (rt->rchild)
using namespace std;
constexpr int mod = 1e9 + 7;
constexpr int mod2 = 998244353;
constexpr int MAXNe5 = 1e5 + 7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region 
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
typedef struct BiTrNode {
    int data;
    BiTrNode *lchild, *rchild;
} BiTrNode;
int find(int x, int num[], int len) {
    for(int i = 0; i < len; ++ i) 
        if(x == num[i]) return i;
}
BiTrNode *build(int input1[], int input2[], int len) {
    if(len <= 0) return NULL;
    BiTrNode *rt = new BiTrNode;
    rt -> data = input2[0];
    int m = find(input2[0], input1, len);
    lson = build(input1 + m + 1, input2 + m + 1, len - m - 1);
    rson = build(input1, input2 + 1, m);
    return rt;
}
void reverse(BiTrNode *rt) {
    if(rt == NULL) return;
    BiTrNode *tmp = lson;
    lson = rson;
    rson = tmp;
    if(lson) reverse(lson);
    if(rson) reverse(rson);
}
BiTrNode *que[1007];
int ans[1007], Qf = 0, Qr = 0, cnt = 0;
void bfs(BiTrNode *rt) {
    que[Qr ++] = rt;
    while (Qf != Qr) {
        BiTrNode *rt = que[Qf ++];
        ans[cnt ++] = rt->data;
        if(lson) que[Qr ++] = lson;
        if(rson) que[Qr ++] = rson;
    }
    for(int i = 0; i < cnt; ++ i)
        cout << ans[i] << ((i + 1 == cnt) ? "" : " ");
}
int main() {
    int input1[1007], input2[1007], n = read();
    for(int i = 0; i < n; ++ i) input1[i] = read();
    for(int i = 0; i < n; ++ i) input2[i] = read();
    BiTrNode *rt = build(input1, input2, n);
    bfs(rt);
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-12 关于堆的判断

#include <bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9 + 7;
constexpr int mod2 = 998244353;
constexpr int MAXNe5 = 1e5 + 7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region 
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
int H[MAXNe5], cnt = 0;
void insert(int x) {
    H[++ cnt] = x;
    int now = cnt;
    while(now) {
        if(H[now >> 1] > H[now]) swap(H[now >> 1], H[now]);
        else break;
        now >>= 1;
    }
}

int main() {
    int n = read(), m = read();
    memset(H, 0, sizeof(H));
    H[0] = -mod;
    for(int i = 0 ; i < n; ++ i) {
        int tmp = read();
        insert(tmp);
    }
    unordered_map<int, int> ump;
    for(int i = 1; i <= cnt; ++ i) 
        ump[H[i]] = i;
    for(int i = 0; i < m; ++ i) {
        int num1, num2;
        string tmp[10];
        cin >> num1 >> tmp[0];
        if(tmp[0] == "and") {
            cin >> num2 >> tmp[1] >> tmp[2];
            if(ump[num1] / 2 == ump[num2] / 2) puts("T");
            else puts("F");
        } else {
            cin >> tmp[1];
            if(tmp[1] == "the") {
                cin >> tmp[2];
                if(tmp[2] == "root") {
                    if(ump[num1] == 1) puts("T");
                    else puts("F");
                } else {
                    cin >> tmp[3] >> num2;
                    if(ump[num2] / 2 == ump[num1]) puts("T");
                    else puts("F");
                }
            } else {
                cin >> tmp[2] >> tmp[3] >> num2;
                if(ump[num1] / 2 == ump[num2]) puts("T");
                else puts("F");
            }
        }
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-13 天梯地图

最短路，Dijkstra。记录方案可以采用数组记录当前点到上一个点的下标。需要注意边的放缩条件，计算最短路长时，最短路长相等的时候需要更新经过的最小节点个数；计算最短时间时，最短时间相等时更新经过的最短距离。输出答案时，从终点回跳，将答案压入栈依次输出，或顺序记录后倒序输出。
 

7-14 喊山

bfs。
 

7-15 长城

二维凸包。