Educational Codeforces Round 104 (Rated for Div. 2)

A. Arena

\quad原題鏈接

http://codeforces.com/contest/1487/problem/A

\quad解題思路

首先，我們看戰(zhàn)斗次數(shù)是無(wú)限的，任意非最小值的英雄都有贏得次數(shù)，既然有場(chǎng)次可以贏，那么我們就可以給他安排連勝的序列，是可以成為最后的 winnner 的。因此最終結(jié)果為 $n?cnt(min)$總英雄數(shù)量減去最小值的次數(shù)。

\quadAC代碼

#include <bits/stdc++.h> using namespace std;const int N = 1010, INF = 0x3f3f3f3f; int a[N], n;int main() {int t; cin >> t;while (t -- ){cin >> n;int minblood = INF, cnt = 0;for (int i = 1; i <= n; i ++ )scanf("%d", &a[i]), minblood = min(minblood, a[i]);for (int i = 1; i <= n; i ++ )if (a[i] == minblood)cnt ++;cout << n - cnt << endl;}return 0; }

B.Cat Cycle

\quad原題鏈接

http://codeforces.com/contest/1487/problem/B

\quad解題思路

一種很簡(jiǎn)單的思路

• 當(dāng) n 為偶數(shù)時(shí)，是不會(huì)相撞的，結(jié)果很好求

• 那么當(dāng)$n=2?i+1$為奇數(shù)的時(shí)候，剛剛開(kāi)始$B=1,A=2?i+1$，經(jīng)過(guò)$i$步驟達(dá)到$B=i+1,A=i+1?B=i+2,A=i+1$，也就是說(shuō)會(huì) 經(jīng)過(guò)$i$布相撞，而且相撞后之后兩者是剛好錯(cuò)開(kāi)，距離仍舊是$?\frac{n?1}{2}?$，下面我們給出證明：
  假設(shè)$A=cur,B=cur+1$，即$B、A$剛好發(fā)生沖突，那么我們證明下一次相撞會(huì)在什么時(shí)刻。
  若首先，倘若兩者會(huì)相撞，那么要么A減到0，轉(zhuǎn)變成n，要么B增加到了n + 1，變成了1，這樣才會(huì)有相碰的機(jī)會(huì)。我們首先計(jì)算出 A循環(huán)需要的次數(shù)為cur - x = 0, x = cur次，B需要的次數(shù)為 cur + 1 + x = n + 1, x = n - cur 次。
  若$cur\le n?cur$，那么是 A 會(huì)由0轉(zhuǎn)換成 n，然后有一次沖突，設(shè)沖突在 t 次，那么有
  $cur?t+n=cur+1+t?t=\frac{n?1}{2}$
  若$cur>n?cur$，，那么是 B由n+1向轉(zhuǎn)換成 1，然后有一次沖突，設(shè)沖突在 t 次，那么有
  $cur?t=cur+1+t?n?t=\frac{n?1}{2}$
  綜上，沖突每$\frac{n?1}{2}$會(huì)發(fā)生一次！！

• 因此， 直接沖突就會(huì) + 1，

很狗的模擬簡(jiǎn)化復(fù)雜度思路

• 當(dāng) n 為偶數(shù)時(shí)，是不會(huì)相撞的，結(jié)果很好求
• 那么當(dāng)$n=2?i+1$為奇數(shù)的時(shí)候，不難發(fā)現(xiàn)，每經(jīng)過(guò)$n$次，那么B的原始位置會(huì) + 2，即序列為$1,3,5,???$，最后到達(dá) $n$，起始點(diǎn)發(fā)生沖突，重回$(1,n)$起點(diǎn)，也就是說(shuō)循環(huán)為$n?(n?1)/2$，那么循環(huán)內(nèi)部以 $n$ 為大步長(zhǎng)，會(huì)沖突兩次，那么大步長(zhǎng)內(nèi)部，也會(huì)有沖突，下面的沖突就需要列式子計(jì)算了。
• 這個(gè)方法又麻煩，bug還多，坑慘我了

\quadAC代碼

思路一代碼

#include <bits/stdc++.h> using namespace std;typedef long long LL; const int N = 1010, INF = 0x3f3f3f3f; int n, k;int main() {int t; cin >> t;while (t -- ){cin >> n >> k;k --; // 這樣的話，起點(diǎn)就是 (1, n)if (n % 2 == 1) // 奇數(shù)沖突會(huì) + 1{k = k + k / (n / 2);}int idx = (1 + k) % n;if (idx == 0) idx = n;printf("%d\n", idx);}return 0; }

思路二代碼

#include <bits/stdc++.h> using namespace std;typedef long long LL; const int N = 1010, INF = 0x3f3f3f3f; LL a[N], n, K;void sol(LL n, LL k) {if (n % 2 == 0) // 偶數(shù){if (k % n == 0)printf("%d\n", n);elseprintf("%d\n", k % n);}else // 奇數(shù){k -= 1; // 因?yàn)橐诔跏紶顟B(tài)LL mod = LL(n) * (n / 2); // 循環(huán)k %= mod;if (k == 0) printf("1\n");else{LL cnt = k / n; // 小循環(huán)k %= n;LL cur = (1 + cnt * 2); // B編號(hào)if (cur > n)cur -= n;if (k == 0) // 次數(shù)耗盡printf("%lld\n", cur);else{LL nxt = (n - cur) / 2; // 下一次相碰需要的步數(shù)if (k < nxt) // 下一次不會(huì)碰了{cur += k;if (cur > n)cur -= n;printf("%lld\n", cur);}else{k -= nxt;cur = cur + nxt + 1;if (cur > n)cur -= n;// 當(dāng)前的位置是 cur, n - nxt, 還剩下 k 步驟LL A = n - nxt;LL B = cur;if (k == 0){printf("%lld\n", B);return;}A = A - k;B = B + k;if (B <= n) // 還沒(méi)走出去{printf("%lld\n", B);}else{B -= n;if (B >= A){B ++;}if (B > n) B -= n;printf("%lld\n", B);}}}}} } int main() {int t; cin >> t;while (t -- ){cin >> n >> K;// printf("ans=\n\t");sol(n, K);}return 0; }

C.Minimum Ties

\quad原題鏈接

http://codeforces.com/contest/1487/problem/C

\quad解題思路

本題就是一個(gè)比較簡(jiǎn)單的模擬題，倘若 $n$ 為奇數(shù)，那么他對(duì)戰(zhàn)的球隊(duì)數(shù)量 $n?1$為偶數(shù)，那么是可以一半輸，一半贏的，關(guān)鍵是如何找到這種方案。首先要想找的話，利用所有球隊(duì)共有的性質(zhì)，就可以完成每個(gè)隊(duì)伍的輸贏一半。
我們假設(shè)球隊(duì)的數(shù)量為$n$，編號(hào)為$1,2,3,???,n$，那么我們可以讓他們圍成一個(gè)圈，如下圖所示。

讓當(dāng)前編號(hào)i,輸給比他編號(hào)大的，贏編號(hào)比他小的，那么這樣就完成了無(wú)矛盾的輪轉(zhuǎn)對(duì)稱。
同理，奇數(shù)的時(shí)候，也是這樣，不過(guò)中位數(shù)那個(gè)編號(hào)是平局。

\quadAC代碼

#include <bits/stdc++.h> using namespace std;typedef long long LL; const int N = 1010, INF = 0x3f3f3f3f; int n, a[N][N];int main() {int t; cin >> t;while (t -- ){cin >> n;static int cnt = 0;cnt = n - 1; // 每支隊(duì)伍比賽次數(shù)for (int i = 1; i < n; i ++ ) // 遍歷隊(duì)伍{if (cnt % 2 == 0) // 一般贏，一半輸{for (int j = 1; j <= n - i; j ++ ){if (j <= cnt / 2){printf("%d ", 1);}else{printf("%d ", -1);}}}else{int tie = (cnt + 1) / 2;for (int j = 1; j <= n - i; j ++ ){if (j < tie){printf("%d ", 1);}else if (j == tie){printf("%d ", 0);}else{printf("%d ", -1);}}}}cout << endl;}return 0; }

D.Pythagorean Triples

\quad原題鏈接

http://codeforces.com/contest/1487/problem/D

\quad解題思路

就是一個(gè)簡(jiǎn)單的公式推導(dǎo)，最后可以使用二分log(n)，也可以直接O(1)來(lái)寫(xiě)sqrt

\quadAC代碼

#include <bits/stdc++.h> using namespace std;typedef long long LL; const int N = 1010, INF = 0x3f3f3f3f; int n, a[N][N];int main() {int t; cin >> t;while (t -- ){static int tmp;cin >> n;// printf("Floor:");tmp = floor(sqrt(2 * n - 1));if (tmp % 2 == 0) tmp -= 1;tmp = tmp / 2;cout << tmp << endl;}return 0; }

E.Cheap Dinner

\quad原題鏈接

http://codeforces.com/contest/1487/problem/E

\quad解題思路

分層圖 + 貪心進(jìn)行求解。
對(duì)于a, b, c, d四個(gè)數(shù)組，首先我們用a數(shù)組更新b數(shù)組，再拿更新之后的b數(shù)組更新c數(shù)組，一定到d數(shù)組，進(jìn)行結(jié)果輸出。
關(guān)鍵在于如何進(jìn)行相鄰數(shù)組的更新，下面我們以a數(shù)組更新b數(shù)組為例進(jìn)行敘述：
利用堆的性質(zhì)進(jìn)行貪心更新，首先將 a 的數(shù)值存入堆中，假設(shè)如今待更新的集合組為 set，那么我們將set中與當(dāng)前下標(biāo)沖突的取出，然后更新集合中的剩余數(shù)，并將集合清空，再講原本沖突未更新的點(diǎn)放入，直到堆為空或者是b數(shù)組所有元素貪心更新完畢。
關(guān)鍵點(diǎn)是使用STL中的set來(lái)降低復(fù)雜度

\quadAC代碼

#include <bits/stdc++.h> using namespace std;typedef pair<int, int> PII; const int INF = 0x3f3f3f3f; const int N = 150010, M = 200010; int a[N], b[N], c[N], d[N]; int n1, n2, n3, n4; bool st[N]; int h[N], ne[M], e[M], idx;void add(int x, int y) {e[idx] = y, ne[idx] = h[x], h[x] = idx ++; }// 處理當(dāng)前這一層 void deal(int a[], int b[], int n1, int n2) {// initialpriority_queue<PII, vector<PII>, greater<PII> > pque;for (int i = 1; i <= n1; i ++ )if (st[i])pque.push(PII(a[i], i));// inputint m; cin >> m;memset(h, -1, sizeof h); idx = 0;for (int i = 1, x, y; i <= m; i ++ ){scanf("%d%d", &x, &y);add(x, y);}//memset(st, false, sizeof st);int surp = n2;PII cur; int val, idx, u;set<int> s1; set<int>::iterator it;for (int i = 1; i <= n2; i ++ )s1.insert(i);while (surp != 0 && pque.size()){cur = pque.top(); pque.pop();val = cur.first, idx = cur.second;for (int i = h[idx]; ~i; i = ne[i]){u = e[i];if (!st[u])s1.erase(u);}for (it = s1.begin(); it != s1.end(); it ++ ) // 主要是利用集合來(lái)去掉不合適的部分{static int v; v = * it;b[v] = a[idx] + b[v];st[v] = true;surp --;}s1.clear();for (int i = h[idx]; ~i; i = ne[i]){u = e[i];if (!st[u])s1.insert(u);}} }int main() {// inputcin >> n1 >> n2 >> n3 >> n4;for (int i = 1; i <= n1; i ++ )scanf("%d", &a[i]);for (int i = 1; i <= n2; i ++ )scanf("%d", &b[i]);for (int i = 1; i <= n3; i ++ )scanf("%d", &c[i]);for (int i = 1; i <= n4; i ++ )scanf("%d", &d[i]);// 分層圖按層次進(jìn)行for (int i = 1; i <= n1; i ++ )st[i] = true;deal(a, b, n1, n2);deal(b, c, n2, n3);deal(c, d, n3, n4);// 結(jié)果輸出int res = INF;for (int i = 1; i <= n4; i ++ )if (st[i])res = min(res, d[i]);if (res == INF) res = -1;cout << res << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的Educational Codeforces Round 104 (Rated for Div. 2)A~E解题报告的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。