Codeforces Round 1013 (Div. 3)

Codeforces Round 1013 (Div. 3)

A. Olympiad Date

题意：

给出n个数字，按顺序取到第几个可以组成"01032025"，若不能组成输出0

思路：

map记录一下"01032025"，啥时候全取过一遍直接输出当前位置

AC code:

void solve() {   int n; cin >> n;int a[n];for (int i = 0; i < n; i ++) {cin >> a[i];}string ca = "01032025";map<int, int> mp;for (int i = 0; i < ca.size(); i ++) {mp[ca[i] - '0'] ++;}int pos = 0;for (int i = 0; i < n; i ++) {if (mp[a[i]]) mp[a[i]] --;bool flag = true;for (auto [x, y] : mp) {if (y >0) flag = false;}if (flag) {cout << i + 1 << endl;return;}}cout << 0 << endl;
} 

B. Team Training

题意：

n名学生，每名学生有一个能力值$a_i$，学生之间可以任意组成团队，团队的实力为团队数量*团队最小能力者

当一个团队能力值达到x时成为强大团队，最少可以组成多少强大团队

思路：

逆序排序后，记录当前团队人数*当前人的能力值，大于x则直接组队并归零新团队人数

AC code:

void solve() {   int n,x; cin >>n >>x;vector<int> v(n);for (int i = 0; i < n; i ++) cin >> v[i];sort(v.begin(), v.end(), greater<int>());int ans = 0;int sz = 0;vector<int> ca;for (int i = 0; i < n; i ++) {sz ++;if (v[i]*sz >= x) ans ++, sz = 0;} cout << ans << endl;} 

C. Combination Lock

题意：

构造一个排列n，这个排列前移任意单位都存在一个元素值等于当前位置

思路：

偶数无法构成，奇数均可构成

因为奇数始终存在一个中心点，所以从1开始顺序输出(i*2)%n即可

AC code：

void solve() {   int n; cin >> n;if (n % 2 == 0) {cout << -1 << endl;return;}for (int i = 1; i < n; i ++) {cout << (i * 2) % n << ' ';} cout << n<< endl;
} 

D. Place of the Olympiad

题意：

n*m个桌子，k名参与者每个人可以选择一个桌子，使得每行最大的连续的桌子数量最小

思路：

二分

AC code:

bool check(int x) {if (x >= m) return n*m;int ca = (m + 1) / (x + 1);int cnt1 = min({m - ca + 1, ca * x});int cnt2 = 0;if ((m + 1) / (x + 1) + 1 <= m+1) {cnt2 = min({(ca+1)*x, m - ca});}return max(cnt1, cnt2) *n >= k;
}void solve() {   cin >> n >> m >> k;int l = 1, r = m;while (l < r) {int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}cout << r << endl;
} 

E. Interesting Ratio

题意：

略

思路：

打表我们可以发现规律

1 2 
1 3
1 5
1 7
++++
2 4 
2 6
2 10
2 14
+++
3 6
3 9
....

实际上就是小于n的素数被除数的数量

AC code: （含打表）

bool prime(int x) {if (x == 1) return false;for (int i = 2; i <= x / i; i ++) {if (x % i == 0) return false;} return true;
}int gcd(int a, int b) {if (b) while ((a%=b) && (b%=a)); return a+b;
}int lcm(int a, int b) {return a*b/gcd(a, b);
}vector<int> pr;void solve() {   int n; cin >> n;int ans = 0;for (auto x : pr) {if (x > n) break;ans += n / x;}// for (int i = 1; i < n; i ++) {//     for (int j = i + 1; j <= n; j ++) {//         int a = lcm(i, j);//         int b = gcd(i, j);//         if (a % b == 0 && prime(a / b)) {//             ans ++;//             cout << i << ' ' << j << endl;//         }//     }// }cout << ans << endl;
} 

F. Igor and Mountain

题意：

存在一个n*m的垂直的山，每层可以看做一个格子，每格中X为可以攀爬的点

从一个格子到另一格子的距离小于d时可以直接进行移动，移动不能向下，只能在同层及上层

现在需要从第n层任意可以攀爬的格子开始最终到达第1层，有多少种方案

思路：

首先是最开始的第n层，我们从每个可以攀爬的格子都可以视为一条路，我们把方案定为1

之后定义一个前后缀和，对于初始层我们可以左右各拓展d个格子

使用前后缀和来更新我们当前层可以走的方案数量

最后再使用当前层的方案来更新前后缀和去更新下一层

直到递归到第一层所有可以攀爬的格子的方案数的和即为答案

AC code:

void solve() {   int n, m, d; cin >> n >> m >> d;vector<vector<char>> g(n + 1, vector<char>(m + 1));for (int i = 1; i <= n; i ++) {for (int j = 1; j <= m; j ++) {cin >> g[i][j];}}vector<int> v(m+10);vector<int> per(m+10, 0);vector<int> suf(m+10, 0);for (int i = n; i >= 1; i --) {for (int j = 1; j <= m; j ++) {if (g[i][j] == 'X') {if (i == n) {v[j] = 1;}else {int l = max(0LL, j - d), r = min(m+1, j + d);v[j] = (((per[j] - per[l] + MOD)%MOD + (suf[j] - suf[r]+MOD)%MOD - v[j])+MOD) % MOD;}} else {v[j] = 0;} }for (int j = 1; j <= m; j ++) per[j] = (per[j - 1] + v[j] + MOD) % MOD;for (int j = m; j >= 1; j --) suf[j] = (suf[j + 1] + v[j] + MOD) % MOD;for (int j = 1; j <= m; j ++) {if (g[i][j] == '#') continue;int l = max(0LL, j - d - 1), r = min(m+1, j + d + 1);int t = v[j];v[j] += (per[j] - per[l] + MOD)%MOD + (suf[j] - suf[r] + MOD)%MOD - 2*t;v[j] %= MOD;}for (int j = 1; j <= m; j ++) per[j] = (per[j - 1] + v[j] + MOD) % MOD;for (int j = m; j >= 1; j --) suf[j] = (suf[j + 1] + v[j] + MOD) % MOD;}cout << per[m]%MOD << endl;
}