【ABC 313】A~E題解
好久沒打過比賽了，也好久沒寫過題解。cf時(shí)間有點(diǎn)陰間，來做下ABC
這次做出了A~D，rk900+，E感覺賽時(shí)過的和D人數(shù)差不多，但我不是很會(huì)數(shù)數(shù)（哭
A
題意：給你 \(n\) 個(gè)數(shù) \(P_i\)，找到最小的非負(fù)整數(shù) \(x\) 使得 \(P_1+x>P_i\)
做法：$$x = max(x, P_i - P_1 + 1)$$ 循環(huán)一遍即可。
點(diǎn)擊查看代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100 + 10, M = 2e6 + 10, mod = 100003;
int n, a[N];
int main(){
ios::sync_with_stdio(false);
cin >> n;
int x = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(i > 1) {
x = max(x, a[i] - a[1] + 1);
}
}
cout << x << endl;
return 0;
}
B
題意：有 \(n(n <= 50)\) 個(gè)人，\(m\) 對關(guān)系，每對關(guān)系 \((x,y)\) 表示 \(x\) 能力強(qiáng)于 \(y\)，這種關(guān)系具有傳遞性。問誰是最強(qiáng)的，如果不能唯一確定，輸出-1
做法：
- 有點(diǎn)復(fù)雜，我的做法是floyd，求出每兩個(gè)人之間的關(guān)系
點(diǎn)擊查看代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100 + 10, M = 2e6 + 10, mod = 100003;
int n, m, a[N];
int g[N][N];
int floyd() {
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(g[i][k] && g[k][j]) {
g[i][j] = 1;
}
}
}
}
// for(int i = 1; i <= n; i++) {
// for(int j = 1; j <= n; j++) {
// if(i == j)continue;
// if(g[i][j] && g[j][i]) return -1;
// }
// }
for(int k = 1; k <= n; k++) {
bool f = 1;
for(int i = 1; i <= n; i++) {
if(g[k][i] || i == k) continue;
else {f = 0; break;}
}
if(f) return k;
}
return -1;
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1, x, y; i <= m; i++) {
cin >> x >> y;
g[x][y] = 1;
}
cout << floyd() << endl;
return 0;
}
- 把 \(x\) 強(qiáng)于 \(y\) 抽象成 \(x\) 到 \(y\) 有一條有向邊，這樣可以知道，最強(qiáng)的人就是度數(shù)為0的點(diǎn)，假設(shè)這樣的點(diǎn)只有一個(gè)，那么就是答案
點(diǎn)擊查看代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100 + 10, M = 2e6 + 10, mod = 100003;
int n, m, a[N];
int rd[N];
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1, x, y; i <= m; i++) {
cin >> x >> y;
rd[y]++;
}
int cnt = 0, ans;
for(int i = 1; i <= n; i++) {
if(!rd[i]) cnt++, ans = i;
}
if(cnt != 1) ans = -1;
cout << ans << endl;
return 0;
}
C
C - Approximate Equalization 2
題意：給你 \(n(n <= 2*10^5)\) 個(gè)數(shù)，定義一次操作為一個(gè)數(shù)+=1，一個(gè)數(shù)-=1，問你最少需要多少次操作，能把整個(gè)數(shù)列變成最大值與最小值的差不超過1
做法：可以求出 $ave = \frac{\sum{a_i}}{n} $，改變后值為 \(ave + 1\) 的有 \(more = \sum{a_i} - ave * n\) 個(gè)，值為 \(ave\) 的有 \(n - more\) 個(gè)。將 \(a_i\) 排序，最后肯定是前 \(n - more\) 個(gè)值為 \(ave\)， 后 \(more\) 個(gè)值為 \(ave + 1\)。因?yàn)樾蛄性黾拥闹档暮团c減小的值的和相等，讓我們只看應(yīng)該增大值的 \(a_i\)，如果 \(a_i\) 小于它應(yīng)該成為的值，就把 \(supposed(a_i) - a_i\) 加進(jìn)答案。
點(diǎn)擊查看代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
ll n, m, a[N];
int main(){
ios::sync_with_stdio(false);
cin >> n;
ll tot = 0;
for(int i = 1, x, y; i <= n; i++) {
cin >> a[i];
tot += a[i];
}
sort(a + 1, a + n + 1);
ll ave = tot / n;
ll ans = 0, more = tot - ave * n;
if(more == 0) {
for(int i = 1, x, y; i <= n; i++) {
if(a[i] < ave) ans += ave - a[i];
}
}
else {
// more 個(gè) ave+1， n-more 個(gè) ave
for(int i = 1; i <= n - more; i++) {
if(a[i] < ave) ans += ave - a[i];
else break;
}
for(int i = n - more + 1; i <= n; i++) {
if(a[i] < ave + 1) ans += ave + 1 - a[i];
}
}
cout << ans << endl;
return 0;
}
D
題意：交互題。有 \(n(n <= 1000)\) 個(gè)數(shù)，它們的值是0或者1，每次可以詢問 \(k(k < n, k為奇數(shù))\) 個(gè)數(shù)的和是奇數(shù)還是偶數(shù)， 最多問 \(n\) 次。求這 \(n\) 個(gè)數(shù)的值。
做法：
首先問 base = 【1,2,3,...,k-1,k】
然后依次問 tem =【1,2,3,...,k-1,i】 ... (i的值從k+1取到n)，共 \(n - k + 1\) 次?？梢灾纊+1 到 n 這些數(shù)和 \(a_k\) 的值相同或不同。
之后，問【1,2,3,...,k+1,k】、【1,2,3,...,k+1,k-1,k】...(把k+1插入k-1、k-2、... 1的位置，其他數(shù)和base保持一致)，共 \(k-1\) 次，可以知道 1 到 k-1 這些數(shù)和 \(a_{k+1}\) 的值相同或不同。
總共就問了 \(n\) 次。
這樣就把所有數(shù)劃分為兩個(gè)陣營，一個(gè)陣營的數(shù)值全為0，另一個(gè)全為1。
然后根據(jù)base的值，它由 \(k\) 個(gè)數(shù)的和組成，而 \(k\) 為奇數(shù)，所以根據(jù)這k個(gè)數(shù)包含奇數(shù)個(gè)1，偶數(shù)個(gè)0（和為奇數(shù)），或者偶數(shù)個(gè)1、奇數(shù)個(gè)0（和為偶數(shù)）的關(guān)系，就可以知道每個(gè)陣營的數(shù)的值。
點(diǎn)擊查看代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1005 + 10;
int n, k;
int ans[N], result[N];
int base, tem, rec;
set<int> st[2];
inline int ask() {
int res;
cout << '?';
for(int i = 1; i <= k; i++) {
cout << ' ' << ans[i];
}cout << endl;
cin >> res;
return res;
}
void solve() {
for(int i = 1; i <= k; i++) ans[i] = i;
base = ask(); // 1 to k
st[0].insert(k);
for(int i = k + 1; i <= n; i++) {
ans[k] = i;
tem = ask();
if(tem == base) {
st[0].insert(i);
if(i == k + 1) rec = 0;
}
else {
st[1].insert(i);
if(i == k + 1) rec = 1;
}
}
ans[k] = k;
for(int i = k - 1; i >= 1; i--) {
ans[i] = k + 1;
tem = ask();
if(tem == base) st[rec].insert(i);
else st[1 - rec].insert(i);
ans[i] = i;
}
int cnt = 0;
for(int i = 1; i <= k; i++) {
if(st[0].count(i) == 1) cnt++;
}
cnt %= 2;
if(cnt == base) {
//k=1
for(auto x : st[0]) result[x] = 1;
}
else {
//k=0
for(auto x : st[1]) result[x] = 1;
}
cout << '!';
for(int i = 1; i <= n; i++) cout << ' ' << result[i];
cout << endl;
}
int main(){
cin >> n >> k;
solve();
return 0;
}
E
這題是賽后補(bǔ)的
給你一個(gè)數(shù)字串s（包含1到9），一次操作可以讓 \(s_i\) 變成 \(s_{i+1}\) 個(gè) \(s_i\)，最后一個(gè)字符去掉。問多少次操作可以讓s變成長度為1，如果不可能，輸出-1
做法：容易發(fā)現(xiàn)如果出現(xiàn)兩個(gè)連續(xù)的非1數(shù)字，答案為-1
我們要求的是操作的次數(shù)，記為ans。
如果最后一個(gè)數(shù)是1，那么$$ans += 1$$
否則，$$ans += 1 + (s[i]-'1')*(ans+1)$$
理解：ans += 1，是刪掉當(dāng)前這個(gè)數(shù)的操作次數(shù)；非1的數(shù)x每次操作會(huì)增長x-1個(gè)1，此前已經(jīng)操作了ans次，那么一個(gè)非1的數(shù)y總共增加 (x-1)(ans)次，又因?yàn)閯h掉當(dāng)前這個(gè)數(shù)又會(huì)導(dǎo)致一次1數(shù)量的增長，所以ans+=(x-1)(ans+1)
點(diǎn)擊查看代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1005 + 10;
int n;
string s;
int main(){
cin >> n >> s;
for(int i = 0; i < s.length(); i++) {
if(i && s[i] != '1' && s[i - 1] != '1') {
cout << -1 << endl;
return 0;
}
}
ll ans = 0;
while(1) {
while(s.length() > 1 && s.back() == '1') s.pop_back(), ans++;
if(s.length() == 1) {cout << ans << endl; return 0;}
int tem = s.back() - '0'; s.pop_back();
ans += 1 + (tem - 1) * (ans + 1) % 998244353;
ans %= 998244353;
}
cout << ans << endl;
return 0;
}
浙公網(wǎng)安備 33010602011771號