[*]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() {
    int n = read();
    cout << ((n + 2) % 7 == 0 ? 7 : (n + 2) % 7);
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-2 重要的话说三遍

# python
print("I'm gonna WIN!\n" *2 + "I'm gonna WIN!")

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 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-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 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-5 到底有多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() {
    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 输出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-8 帅到没朋友

#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-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;
#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, M, input, K, a, b;
    scanf("%d", &N);
    set<int> se[55];
    double mark[55][55];
    memset(mark, -1, sizeof(mark));
    for(register int i = 1; i <= N; ++ i) {
        scanf("%d", &M);
        for(register int j = 0; j < M; ++ j) {
            scanf("%d", &input);
            se[i].insert(input);
        }
    }
    scanf("%d", &K);
    while(K --) {
        scanf("%d %d", &a, &b);
        if(mark[a][b] >= 0.0) {
            printf("%.2f%%\n", mark[a][b]);
        } else {
            set<int> tmp;
            set_intersection(se[a].begin(), se[a].end(), se[b].begin(), se[b].end(), inserter(tmp, tmp.begin()));
            mark[a][b] = 1.0 * tmp.size() / (se[a].size() + se[b].size() - tmp.size()) * 100.0;
            printf("%.2f%%\n", mark[a][b]);
        }
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-10 树的遍历

#include <bits/stdc++.h>
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define met(a,b); memset(a,b,sizeof(a));
typedef long long ll;
using namespace std;
double pai=3.14159265359;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline long long lread() {
    long long tmp=0, fh=1; char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') fh=-1; c=getchar();}
    while (c>='0'&&c<='9') tmp=tmp*10+c-48, c=getchar();
    return tmp*fh;
}
int bak[35],mid[35];
struct nod{
    int weight;
    int left,right;
}tree[35];
int num=1;
void bulid(int now,int len,int *ba,int *mi){
    tree[now].weight=ba[len];
    int fin=1;
    for(int i=1;i<=len;i++){
        if(ba[len]==mi[i]){
            fin=i;break;
        }
    }
    int k=0;
    if(fin!=1){
        num++;
        tree[now].left=num;
        bulid(num,fin-1,ba,mi);
    }
    if(fin!=len){
        num++;
        tree[now].right=num;
        bulid(num,len-fin,ba+fin-1,mi+fin);
    }
}
int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)
        cin>>bak[i];
    for(int i = 1;i <= n;i++)
        cin>>mid[i];
    bulid(1,n,bak,mid);
    queue<int> qu;
    qu.push(1);
    bool sc=0;
    while(!qu.empty()){
        nod temp = tree[qu.front()];
        qu.pop();
        if(sc)cout<<' ';
        cout<<temp.weight;
        sc=1;
        if(temp.left!=0)qu.push(temp.left);
        if(temp.right!=0)qu.push(temp.right);
    }
    #ifndef ONLINE_JUDGE
        system("pause");
    #endif
}

7-11 家庭房产

#include <bits/stdc++.h>
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define met(a,b); memset(a,b,sizeof(a));
typedef long long ll;
using namespace std;
double pai=3.14159265359;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline long long lread() {
    long long tmp=0, fh=1; char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') fh=-1; c=getchar();}
    while (c>='0'&&c<='9') tmp=tmp*10+c-48, c=getchar();
    return tmp*fh;
}
int bin[10000];
bool pc[10000];
int people[10000];
int numt[10000];
int mi[10000];
double sum[10000];
int fin(int n){
    if(bin[n]==n) return n;
    else return bin[n]=fin(bin[n]);
}
struct famy{
    int a;
    int sum;
    double b;
    double c;
}ans[2000];
int sc=0;
bool cmp(famy a,famy b){
    if(a.c==b.c) return a.a<b.a;
    else return a.c>b.c;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<=9999;i++)mi[i]=bin[i]=i;
    for(int i=0;i<n;i++){
        int num,fa,ma,k;
        cin>>num>>fa>>ma>>k;pc[num]=1;
        for(int j=0;j<k;j++){
            int temp;
            cin>>temp;
            pc[temp]=1;
            bin[fin(num)]=fin(temp);
        }
        if(fa!=-1){bin[fin(num)]=fin(fa);pc[fa]=1;}
        if(ma!=-1){bin[fin(num)]=fin(ma);pc[ma]=1;}
        cin>>numt[num]>>sum[num];
    }
    for(int i=0;i<=9999;i++){
        if(!pc[i])continue;
        int u=fin(i);
        mi[u]=min(mi[u],i);
        people[u]++;
        if(u==i)continue;
        numt[u]+=numt[i];
        sum[u]+=sum[i];
    }
    for(int i=0;i<=9999;i++){
        if(people[i]){
            ans[sc].a=mi[i];
            ans[sc].b=numt[i]*1.0/people[i];
            ans[sc].c=sum[i]*1.0/people[i];
            ans[sc].sum=people[i];
            sc++;
        }
    }
    sort(ans,ans+sc,cmp);
    printf("%d\n",sc);
    for(int i=0;i<sc;i++){
        printf("%04d %d %.3lf %.3lf\n",ans[i].a,ans[i].sum,ans[i].b,ans[i].c);
    }
    #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 cnt = 1, p[MAXNe5];
string s1, s2;
void init() {
    int len = s1.length();
    s2 += '!'; s2 += '#';
    for(int i = 0; i < len; ++ i)
        s2 += s1[i], s2 += '#';
}
int manacher() {
    init();
    int mid = 0, r = 0, ans = 0, len = s2.length();
    for(int i = 1; i < len; i++) {
        if(i < r) p[i] = min(p[mid * 2 - i], r - i);
        else p[i] = 1;
        while(s2[i + p[i]] == s2[i - p[i]]) p[i] ++;
        if(r < i + p[i]) r = i + p[i], mid = i;
        ans = max(ans, p[i] - 1);
    }
    return ans;
}
int main() {
    getline(cin, s1);
    cout << manacher();

    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}

7-13 肿瘤诊断

三维坐标系下判断连通性，注意dfs需要特殊技巧，硬搜可能会爆栈，bfs随便搜。

7-14 垃圾箱分布

最短路问题，Dijkstra/spfa。

7-15 迎风一刀斩

思维/模拟。