【解題まとめ】SWERC 2019(Codeforces Gym 102501)

49608 ワード

解題のまとめ

私が解決した:B(1 WA)、I、J、A(3 WA)、D(1 WA、1 TLE).
見ていない:ない.
傍観する:C、F、K、G、H.
見たけどできなかった:E、L.
I Rats
簡単な問題.
B Biodiversity
簡単な問題.
C Ants
簡単な問題.
A Environment-Friendly Travel
最短、略.一度はやったはずのテーマが、いくつも書き間違えて恥ずかしい.
F Icebergs
題意:いくつかの単純な多角形を与え、その面積の和を計算する.
幾何学的テンプレートの問題を計算するのは、私がまだ書けないことです(板も持っていません).
D Gnalcats
标题:スタックに対する操作がいくつかあります.スタック内の要素は2つあります.分割できません.単純タイプ(Simple)と呼ばれ、2つの要素からなる二元グループを複雑タイプと呼ぶ(Complex).2つの操作シーケンスを指定し、単純なタイプの要素のみを含む十分な長さのスタックについて、この2つの操作シーケンスが等価かどうかを尋ねます.等価定義は、2つの操作シーケンスがそれぞれ操作された後、得られた2つの結果が等しいか、または2つの操作シーケンスがスタック上で失敗したかです.
この問題はシミュレーションです.まず長いスタックを構築し、要素ごとに異なる番号を付けてから、2つの操作シーケンスをそれぞれシミュレーションすればいいです.
最後に二元グループが等しいと判断するときはHashを使います.そうしないとTLEになります.
K Birdwatching
題意:1枚の有向図と1つの点T T Tを与えて、どの点がその1本の辺がT T T Tにつながっていることを満たして、しかもそれはこの辺を通ってT T T Tに着くことしかできませんかを聞きます.
まず,T T T Tにエッジが接続されている点をキーと呼ぶ.明らかに答えはそのサブセットです.
その後,キーがT T T Tを指すエッジを捨てて反図を構築する.各キーに対して、別のキーがパスされているかどうかを確認したいと考えています.
このため,各キーu u u uに対して1つの集合S(u)S(u)S(u)を維持することができ,u u uのキーに到達できる集合を表す.この集合の大きさが2を超えないことを保証する.2に達するとu uが答えではないことを示すからだ.
その後、各キーを起点とするDFSでよい.時間の複雑さは、最後のソートを除いて線形です.

#include 
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, T;
int to[100005], nxt[100005], at[100005] = {0}, cnt = 0;
vector<int> keyp, ans;
int S[100005][2] = {0};
void dfs(int cur, int st){
    if (S[cur][1] || S[cur][0] == st || S[cur][1] == st)
        return ;
    if (!S[cur][0]) S[cur][0] = st;
    else S[cur][1] = st;
    for (int i = at[cur]; i; i = nxt[i])
        dfs(to[i], st);
}
int main(){
    n = read(), m = read(), T = read() + 1;
    for (int i = 1; i <= m; ++i){
        int u = read() + 1, v = read() + 1;
        if (v == T) keyp.push_back(u);
        else {
            to[++cnt] = u, nxt[cnt] = at[v], at[v] = cnt;
        } 
    }
    for (int x: keyp) dfs(x, x);
    
    for (int x: keyp){
        if (!S[x][1]) ans.push_back(x);
    }
    printf("%u
", ans.size());
    sort(ans.begin(), ans.end());
    for (int x: ans)
        printf("%d
", x - 1);
    return 0;
}

J Counting Trees
題意:点権に関する二叉木の中序遍歴を与え、各点を満たす点権は父ノードより小さくなく、このような中序遍歴の異なる形態を持つ二叉木が何個あるかを聞く.
サンプル1を見ると、ポイント重みが互いに異なる場合、結果は唯一決定されることがわかる.最小重みの点が見つかるたびに,必ず現在のサブツリーの根であり,その左右に再帰すればよいからである.
では、最小権のノードが複数あるとしたら?明らかに、それらはつながっているはずです.そうしないと、問題の条件を破壊します.これらのノードにt t t個があれば,これらのノードが形成するツリーの数はCatalan⁡toperatorname{Catalan}_である.t Catalant.最小重みノードによって分割された区間については,それらの答えはこれに基づいて乗せればよい.
このような分治のやり方は直観的だが,時間の複雑さは下がりにくい.実際には、各ポイント権を考慮する前に、最も近い、それより大きくないポイント権を考慮するために、いくつかの単調なスタックを使用することができます.次に後者が前者を遮断するかどうかを考える.具体的にはコードを見て理解できます.

#include 
#define MOD 1000000007
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, a[1000005], inv[1000005], catalan[1000005];
int st[1000005], top, lft[1000005], cnt[1000005] = {0};
void init(){
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    inv[1] = 1;
    for (int i = 2; i <= n + 1; ++i)
        inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;
    catalan[0] = catalan[1] = 1;
    for (int i = 2; i <= n; ++i){
        catalan[i] = 1ll * catalan[i - 1] * inv[i] % MOD;
        catalan[i] = 1ll * catalan[i] * (2 * i - 1) % MOD;
        catalan[i] = 1ll * catalan[i] * (2 * i) % MOD;
        catalan[i] = 1ll * catalan[i] * inv[i + 1] % MOD;
    }
}
void solve(){
    a[0] = -1;
    st[top = 1] = 0;
    for (int i = 1; i <= n; ++i){
        while (a[st[top]] > a[i])
            --top;
        lft[i] = st[top];
        st[++top] = i;
    }
    
    //   cnt                  
    int res = 1;
    for (int i = 1; i <= n; ++i){
        if (a[lft[i]] < a[i]){
            res = 1ll * res * catalan[cnt[a[i]]] % MOD;
            cnt[a[i]] = 1;
        }else{
            ++cnt[a[i]];
        }
    }
    for (int i = 0; i <= 1000000; ++i)
        res = 1ll * res * catalan[cnt[i]] % MOD;
    printf("%d
", res);
}
int main(){
    init();
    solve();
    return 0;
}

H Pseudo-Random Number Generator
标题:謎の乱数生成器を与えて、前のN NのNの個数の中でどれだけ偶数なことを求めます.
引き出しの原理から、必然的に1つの循環節が存在する.まずFloyd判輪アルゴリズムを用いて,ループ節に入る前にどれだけの数が必要か,およびループ節がどれだけ長いかを算出することができる.そして1 0 7 10^7 107個ごとに1つの表を打って、暴力で計算すればいいです.
G Swapping Places
标题:S S S種の動物があり、L L種の異なる動物間の友好関係(伝達性なし)がある.長さN N N N Nの動物行列を与え、隣接する動物が友好関係があれば位置を交換できる.得られる辞書順が最も小さい行列を尋ねる.
関係に伝達性がないため、集計メンテナンスは使用できません.
位置i i iとj j jの動物は交換できないことに気づき、i問題は,このような辺の数が多く,O(N 2)O(N^2)O(N 2)であることである.各位置j j j jについて、前に交換できない動物があれば、最も後ろにあるものをj j jにつなげます.すると辺数はO(NS)O(NS)O(NS)に下がり,通過できるようになった.
全時間複雑度はO(N S＋N log⁡N)O(NS＋NlogN)O(NS＋NlogN)であった.

#include 
using namespace std;
int S, L, N;
string s1, s2;
vector<string> vec;
unordered_map<string, int> mp;
bool ok[205][205] = {0};
int que[100005], last_pos[205] = {0};
vector<int> G[100005];
int du[100005] = {0}, ans[100005];
priority_queue<pair<int, int>, vector<pair<int, int> >, 
    greater<pair<int, int> > > pq;
void init(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> S >> L >> N;
    for (int i = 1; i <= S; ++i){
        cin >> s1;
        vec.push_back(s1);
    }
    sort(vec.begin(), vec.end());
    for (int i = 1; i <= S; ++i){
        mp[vec[i - 1]] = i;
    }
    for (int i = 1; i <= L; ++i){
        cin >> s1 >> s2;
        int u = mp[s1], v = mp[s2];
        ok[u][v] = ok[v][u] = true;
    }
    for (int i = 1; i <= N; ++i){
        cin >> s1;
        int id = mp[s1];
        que[i] = id;
        for (int j = 1; j <= S; ++j){
            if (!ok[j][id] && last_pos[j]){
                G[last_pos[j]].push_back(i);
                ++du[i];
            }
        }
        last_pos[id] = i;
        if (!du[i]) pq.push(make_pair(id, i));
    }
}
void solve(){
    int tot = 0;
    while (!pq.empty()){
        int h = pq.top().second;
        pq.pop();
        ans[++tot] = h;
        for (int v: G[h]){
            --du[v];
            if (!du[v]) pq.push(make_pair(que[v], v));
        }
    }
    for (int i = 1; i < N; ++i)
        cout << vec[que[ans[i]] - 1] << ' ';
    cout << vec[que[ans[N]] - 1] << '
';
}
int main(){
    init();
    solve();
    return 0;
}

E Pixels
補充待ち..
L River Game
補充待ち..

Django REST Framework メモ ::ForeignKeyでつながっている別モデルをくっつけてひとつのJSONとしてWebAPI出力する

区間問題貪欲戦略個人分析