Educational Codeforces Round 104 Div. 2 A~E

A-Arena

輸 出 n ? 最 小 數 的 個 數 ， 輸出n-最小數的個數， 輸出n?最小數的個數，

Code

#include "bits/stdc++.h"

using namespace std;

void solve() {
    int _; cin >> _;
    while(_--) {
        int n; cin >> n;
        map<int, int> mp;
        int mx = 1e9;
        for(int i = 1;i <= n; i++) {
            int x; cin >> x;
            mp[x]++;
            mx = min(mx, x);
        }
        cout << n - mp[mx] << endl;
    }
}

signed main() {
    solve();
}

B - Cat Cycle

因 為 貓 B 首 先 呆 在 1 的 位 置 ， 所 以 k 要 減 1 ， 最 后 位 置 加 1 即 可 ， 因為貓B首先呆在1的位置，所以k要減1，最后位置加1即可， 因為貓B首先呆在1的位置，所以k要減1，最后位置加1即可，

當 n 為 奇 數 時 ， 直 接 輸 出 ( k ? 1 ) % n + 1 當n為奇數時，直接輸出(k-1)\%n+1 當n為奇數時，直接輸出(k?1)%n+1
當 n 為 偶 數 時 ， 因 為 會 有 相 遇 問 題 ， 當n為偶數時，因為會有相遇問題， 當n為偶數時，因為會有相遇問題，
而 相 遇 時 間 為 ( n ? 1 ) / 2 ， 總 相 遇 次 數 為 ( k ? 1 ) ( n ? 1 ) / 2 ， 而相遇時間為(n-1)/2，總相遇次數為\frac{(k-1)}{(n-1)/2}， 而相遇時間為(n?1)/2，總相遇次數為(n?1)/2(k?1)?，
最 后 位 置 為 ( k ? 1 + ( k ? 1 ) ( n ? 1 ) / 2 ) % n + 1 ， 最后位置為(k-1+\frac{(k-1)}{(n-1)/2})\%n+1， 最后位置為(k?1+(n?1)/2(k?1)?)%n+1，

Code

#include "bits/stdc++.h"

using namespace std;

void solve() {
    int _; cin >> _;
    while(_--) {
        int n, k; cin >> n >> k;
        k -= 1;
        if(n & 1) {
            cout << (k + k / ((n - 1) / 2)) % n + 1 << endl;
        }
        else cout << k % n + 1 << endl;
    }
}

signed main() {
    solve();
}

C - Minimum Ties

當 n 為 奇 數 時 ， 那 么 每 個 隊 都 是 n 2 的 贏 和 輸 ， 所 以 輸 出 1 、 ? 1 、 1... 即 可 ， 當n為奇數時，那么每個隊都是\frac{n}{2}的贏和輸，所以輸出1、-1、1...即可， 當n為奇數時，那么每個隊都是2n?的贏和輸，所以輸出1、?1、1...即可，

當 n 為 偶 數 時 ， 那 么 每 個 隊 都 是 n 2 ? 1 的 贏 和 輸 還 有 一 場 平 局 ， 當n為偶數時，那么每個隊都是\frac{n}{2}-1的贏和輸還有一場平局， 當n為偶數時，那么每個隊都是2n??1的贏和輸還有一場平局，

平 局 場 就 是 1 和 2 ， 3 和 4 ， 5 和 6 等 等 ， 剩 下 場 都 是 一 半 贏 一 半 輸 ， 平局場就是1和2，3和4，5和6等等，剩下場都是一半贏一半輸， 平局場就是1和2，3和4，5和6等等，剩下場都是一半贏一半輸，

Code

#include "bits/stdc++.h"

using namespace std;

void solve() {
    int _; cin >> _;
    while(_--) {
        int n; cin >> n;
        if(n & 1) {
            for(int i = 1;i <= (n - 1) * n / 2; i++) {
                if(i & 1) cout << 1 << " ";
                else cout << -1 << " ";
            }
        }
        else {
            int t = 0;
            while(n--) {
                t++;
                for(int i = 1;i <= n; i++){
                    if(i == 1 && (t & 1)) cout << 0 << " ";
                    else {
                        if(!(i & 1)) cout << 1 << " ";
                        else cout << -1 << " ";
                    }
                }
            }
        }
        cout << endl;
    }
}

signed main() {
    solve();
}

D - Pythagorean Triples

三 個 條 件 ： 三個條件： 三個條件：

• c = a 2 ? b c=a^2-b c=a2?b
• c 2 = a 2 + b 2 c^2=a^2+b^2 c2=a2+b2
• 1 ≤ a , b , c ≤ n 1\leq a,b,c\leq n 1≤a,b,c≤n

問 這 樣 ( a , b , c ) 的 組 數 有 多 少 ？ 問這樣(a,b,c)的組數有多少？ 問這樣(a,b,c)的組數有多少？

來 化 簡 一 下 ， 二 式 ? 一 式 得 c 2 ? c = b 2 + b ?????????? ( c + b ) ( c ? b ) = b + c 來化簡一下，二式-一式得c^2-c=b^2+b\;\;\;\;\;(c+b)(c-b)=b+c 來化簡一下，二式?一式得c2?c=b2+b(c+b)(c?b)=b+c
繼 續 化 簡 c ? b = 1 ???? b = c ? 1 ， 帶 入 一 式 得 2 c = a 2 + 1 ， 繼續化簡c-b=1\;\;b=c-1，帶入一式得2c=a^2+1， 繼續化簡c?b=1b=c?1，帶入一式得2c=a2+1，

所 以 整 個 條 件 就 變 為 ， a 一 定 要 是 奇 數 ， 并 且 a ≤ n ， 得 ： 所以整個條件就變為，a一定要是奇數，并且a\leq n，得： 所以整個條件就變為，a一定要是奇數，并且a≤n，得：

a n s = ? 2 ? n ? 1 2 ? ? 1 ans=\left \lceil \frac{\sqrt{2*n-1}}{2} \right \rceil-1 ans=?22?n?1 ????1

這 個 減 1 是 因 為 c = 1 時 ， b = 0 ， 錯 誤 組 ， 這個減1是因為c=1時，b=0，錯誤組， 這個減1是因為c=1時，b=0，錯誤組，

Code

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

void solve() {
    int _; cin >> _;
    while(_--) {
        ll n; cin >> n;
        ll a = sqrt(2 * n - 1);
        cout << a / 2 + (a % 2 == 1) - 1 << endl;
    }
}

signed main() {
    solve();
}

E - Cheap Dinner

裸裸地貪心，待補

Code

#include "bits/stdc++.h"

using namespace std;

#define endl "\n"
#define pb push_back

vector<int> a[5], n(5);
vector<pair<int, int>> que, tt;
map<int, set<int>> mp[5];

void solve() {
    for (int i = 1; i <= 4; i++) cin >> n[i], a[i].pb(0);
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= n[i]; j++) {
            int x;
            cin >> x;
            a[i].pb(x);
        }
    }
    for (int i = 1; i <= 3; i++) {
        int m;
        cin >> m;
        for (int j = 1; j <= m; j++) {
            int x, y;
            cin >> x >> y;
            mp[i][x].insert(y);
        }
    }
    for (int i = 1; i <= n[1]; i++) que.pb({a[1][i], i});
    for (int k = 2; k <= 4; k++) {
        sort(que.begin(), que.end());
        for (int i = 1; i <= n[k]; i++) {
            for (auto j : que) {
                int x = j.first, y = j.second;
                if (mp[k - 1][y].find(i) == mp[k - 1][y].end()) {
                    tt.pb({a[k][i] + x, i});
                    break;
                }
            }
        }
        que = tt;
        tt.clear();
    }
    sort(que.begin(), que.end());
    if (que.empty())
        cout << -1 << endl;
    else
        cout << que[0].first << endl;
}

signed main() {
    solve();
}