Codeforces Round #654 (Div. 2)
A.Magical Sticks
题意:
给个长度为的木棒,木棒可以拼接在一起。问最多可以拼接出多少根长度相等的木棒。
题解:
最终都拼成长度为的,和组合,和组合...最终答案为
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { ll n; scanf("%lld", &n); printf("%lld\n", (n - 1) / 2 + 1); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
B.
题意:
规定每个周期为天,你可以从任意一天开始连续涂色天,询问可以形成多少种不同的形状
题解:
可以分成和两种情况。
当时,都只有一种形状,而,有个形状,因此答案为
当时,都有个形状,因此答案为
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { ll n, r; scanf("%lld%lld", &n, &r); if (n <= r) printf("%lld\n", n * (n - 1) / 2 + 1); else printf("%lld\n", r * (r + 1) / 2); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
C.A Cookie for You
题意:
有个食物和个食物,有个客人和个客人,客人每人会吃一个当前数量较多的那个食物,客人每人会吃一个当前数量较少的那个食物,判断是否存在一种排列方式使得每个客人都能吃到食物
题解:
可以知道至多有个客人可以吃到食物,且客人全吃数量较少的那种食物才能取到最大值,因此将客人排在最前面,客人全排在后面,如果则每个客人都能吃到
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { ll a, b, n, m; scanf("%lld%lld%lld%lld", &a, &b, &n, &m); if (min(a, b) >= m && a + b >= n + m) puts("Yes"); else puts("No"); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
D.Grid-00100
题意:
给定一个的全矩阵,现在要将个位置填为。定义矩阵的,其中为第行中的数量,为第列中的数量,现在要求最小,输出最小的方案
题解:
可以发现在一个位置放,对该行和该列的贡献都为,为了使贡献最小,那么应该尽量放到不同行和不同列,所以每次可以在不同行不同列放,同时可以发现,当时,否则为。
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { int n, k; scanf("%d%d", &n, &k); printf("%d\n", k % n ? 2 : 0); for (int i = n - 1; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) printf("%d", (i + j) % n * n + i < k); puts(""); } } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
E1. Asterism (Easy Version)
题意:
给定个怪兽,每个怪兽有个糖果,一开始有个糖果,现在依次和怪兽比糖果数,如果,则获胜,糖果数。为初始有个糖果,对怪兽的出场顺序进行排序,能全胜的排序数。同时给定一个质数,如果则输出这个,其中。
题解:
对进行排序,首先可以确定时均不行,因为此时,而,因此一定包含。
那么由于不妨枚举,对于每个,可以确定在位置的值为,那么二分可得的数记为,那么该位置可以放置的数为个,那么,因此只要对每个位置判断一下是否为即可。
#include <bits/stdc++.h> using namespace std; int a[2005]; vector<int> ans; int main() { int n, p; scanf("%d%d", &n, &p); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a + 1, a + n + 1); for (int x = 1; x < a[n]; x++) { int flag = 1; for (int i = 1; i <= n; i++) { int pos = upper_bound(a + 1, a + n + 1, x + i - 1) - a - 1; if ((pos - i + 1) % p == 0) { flag = 0; break; } } if (flag) ans.push_back(x); } printf("%d\n", ans.size()); for (auto i : ans) printf("%d ", i); puts(""); return 0; }
E2.Asterism (Hard Version)
题意:
E2和E1的题意相同,。
题解:
因为,所以不可能再去枚举了,其实从E1的结果可以发现答案都为连续的数,最开始的那个数也很好确定就为,那么只要确定最大的数即可。想到如果很大,答案就是,那么如果,那么至少前个数可以随意取,因此答案一定包含,由此可以想到上界就是最多前个数可以自由移动,但是第个数要固定,那么想想什么时候第个数固定,就是时,,因此答案为
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll a[100005]; int main() { ll n, p, ans1 = 0, ans2 = 2e9; scanf("%lld%lld", &n, &p); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); sort(a + 1, a + n + 1); for (int i = 1; i <= n; i++) { ans1 = max(ans1, a[i] - i + 1); if (i >= p) ans2 = min(ans2, a[i] - i + p); } printf("%lld\n",max(ans2 - ans1, 0ll)); for (int i = ans1; i < ans2; i++) printf("%lld ", i); return 0; }