Codeforces 1281 #Codeforces

1281A.py

import sys
class IoTool:  # a tool for input redirection 
    DEBUG = 0
    def _reader_dbg():
        with open('./input.txt', 'r') as f:
            lines = f.readlines()
        for l in lines: yield l.strip() 
    def _reader_oj():  
        return iter(sys.stdin.read().split('\n'))
    reader = _reader_dbg() if DEBUG else _reader_oj()
    def read(): return next(IoTool.reader)

input = IoTool.read

def main():
    s = input()
    if s.endswith('po'):
        print('FILIPINO')
    elif s.endswith('desu') or s.endswith('masu'):
        print('JAPANESE')
    else:
        print('KOREAN')


if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        main()

1281B.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)

using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 5e3 + 100;
char s[maxn], c[maxn];
vector<int> alpha[27];

void solve() {
    cin >> s >> c;
    bool end = false;
    int len = strlen(s);
    F(i, 26) alpha[i].clear();
    F(i, len) alpha[s[i]-'A'].push_back(i);
    F(i, len){
        F(j, s[i]-'A'){
            if(!alpha[j].empty() && alpha[j].back() > i){
                swap(s[i], s[alpha[j].back()]);
                end = true;
                break;
            }
        }
        if(end) break;
    }
    if(strcmp(s, c) >= 0){
        cout << "---\n"; 
    }else{
        cout << s << '\n';
    }
}

signed main() {
    Android;
    int t;
    cin >> t;
    while(t--)
    solve();
}

1281C.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)

using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const int inf = 0x3f3f3f3f;
const int maxn = 600;
const int max_hack = 1e6 + 100;
const ll mod = 1e9 + 7;

char buffer[maxn];
int rec[max_hack], t[max_hack] = {0}; // 终极偷鸡
vector<int> range;
int x, slen, test_case;

int seek(int pos){
    if(pos < slen) return buffer[pos] - '0';
    if(t[pos] == test_case) return rec[pos]; // 记忆化偷鸡
    auto ptr = upper_bound(range.begin(), range.end(), pos);
    t[pos] = test_case;
    return rec[pos] = seek(pos - (*ptr - *(ptr-1)));
}

void solve() {
    ll ans;
    range.clear();
    bool exceed = false;
    cin >> x >> buffer;
    ans = slen = strlen(buffer);
    range.push_back(slen);
    for(int i=0; i<x; i++){
        int repeat = seek(i) - 1;
        ll paste_len = (ans - i - 1 + mod) % mod;
        for(int j = 0; j<repeat; j++){
            ans = ans + paste_len;
            if(!exceed) range.push_back(ans);
            if(ans > x) exceed = true;
            ans = ans % mod;
        }
    }
    cout << ans << '\n';
}

signed main() {
    Android;
    int t;
    cin >> t;
    for(test_case = 1; test_case <= t; test_case++) 
        solve();
}

1281D.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)

using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const int inf = 0x3f3f3f3f;
const int maxn = 60 + 10;
const ll mod = 1e9 + 7;

char buffer[maxn][maxn];
int sum[maxn][maxn];

int solve() {
    int r, c;
    cin >> r >> c;
    for(int i=1; i<=r; i++) cin >> buffer[i] + 1;
    F(i, r + 1) F(j, c + 1) sum[i][j] = 0;
    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++){
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + (buffer[i][j] == 'A');
        }
    }
    // 全为A
        if(sum[r][c] == r * c) return 0;
    // 如果列/行全为A
        // 边缘/中间
        int all_a = 0;
        for(int i=1; i<=r && all_a != 2; i++) if(sum[i][c] - sum[i-1][c] == c) {
            all_a = max(all_a, (i==1||i==r)?2:1);
        }
        for(int i=1; i<=c && all_a != 2; i++) if(sum[r][i] - sum[r][i-1] == r) {
            all_a = max(all_a, (i==1||i==c)?2:1);
        }
        if(all_a == 2) return 1;
        if(all_a == 1) return 2;

    // 如果有A
        int has_a = 0;
        // 角落有A
        if(buffer[1][1] == 'A' || buffer[1][c] == 'A') return 2;
        if(buffer[r][1] == 'A' || buffer[r][c] == 'A') return 2;
        // 边缘有A
        if(sum[1][c] >= 1 || sum[r][c] - sum[r-1][c] >= 1) return 3;
        if(sum[r][1] >= 1 || sum[r][c] - sum[r][c-1] >= 1) return 3;
        // 边缘无A
        if(sum[r][c] >= 1) return 4;
        return -1;
}

signed main() {
    Android;
    int t;
    cin >> t;
    while(t--){
        int ans = solve();
        if(ans == -1){
            cout << "MORTAL\n"; 
        }else{
            cout << ans << '\n';
        }
    }
}

1281E.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)

using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 100;

int e[maxn], from[2 * maxn], to[2 * maxn], nxt[2 * maxn];
ll weight[2 * maxn];
int edge_cnt;
ll sz[maxn];

void add_edge(int u, int v, ll w){
    from[edge_cnt] = u, to[edge_cnt] = v, weight[edge_cnt] = w;
    nxt[edge_cnt] = e[u];
    e[u] = edge_cnt++;
}

int dfs(int u, int fa){
    sz[u] = 1;
    for(int edge=e[u]; edge!=-1; edge=nxt[edge]){
        int v = to[edge];
        if(v == fa) continue;
        sz[u] += dfs(v, u);
    }
    return sz[u];
}

void solve() {
    ll k, u, v, w;
    ll ans_mx = 0, ans_mn = 0;
    cin >> k;
    k = 2 * k;
    edge_cnt = 0;
    F(i, k+1) e[i] = -1;
    F(i, k-1){
        cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    dfs(1, 0);
    F(i, edge_cnt){
        int u = from[i], v = to[i], w = weight[i];
        if(sz[u] < sz[v]) swap(u, v);
        // 一条边应当被通过max(sz[v], k-sz[v])次
        ans_mx += min(k-sz[v], sz[v]) * w;
        // 一条边最多被通过1次
        ans_mn += w * (sz[v] & 1);
    }
    ans_mn /= 2;
    ans_mx /= 2;
    cout << ans_mn << " " << ans_mx << '\n';
}

signed main() {
    Android;
    int t;
    cin >> t;
    while(t--)
        solve();
}