Codeforces Round #654 E. Asterism (思维+二分)

Codeforces Round #654 E. Asterism

题目地址：

http://codeforces.com/contest/1371/problem/E2

E1基本思路：

对于E1我们考虑去枚举$x$，每次独立判断$x$是否符合$f(x)$不被$p$整除;

根据题目条件，我们容易知道在$x$确定的情况下，Yuzu在每个位置 $i$ 的糖果数就也确定了是$x+i-1$;

那么我们要不败的话，当前位置敌人的糖果一定要小于Yuzu在这个位置的糖果数，那么我们进行一个二分就能找到可供放置的敌人的数量设为$po{s}_i$，再减去之前已经确定的$(i-1)$个敌人，我们就能知道每个位置还能供我们选择的敌人就有$po{s}_i-i+1$个;

所以此时的全排列数量也就是$f(x)$应该是${\prod }_{i=1}^n(po{s}_i-i+1)$，要不被素因子$p$整除，只要对于每个项判断是否能被整除就行了。

E1参考代码：

#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false) #define int long long #define rep(i, l, r) for (int i = l; i <= r; i++) #define per(i, l, r) for (int i = l; i >= r; i--) #define mset(s, _) memset(s, _, sizeof(s)) #define pb push_back #define pii pair <int, int> #define mp(a, b) make_pair(a, b) #define INF (int)1e18 inline int read() { int x = 0, neg = 1; char op = getchar(); while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); } while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); } return neg * x; } inline void print(int x) { if (x < 0) { putchar('-'); x = -x; } if (x >= 10) print(x / 10); putchar(x % 10 + '0'); } const int maxn = 2010; int n,p,a[maxn]; signed main() { IO; cin >> n >> p; rep(i,1,n) cin >> a[i]; sort(a + 1 , a + 1 + n); vector<int > ans; for(int x = 1 ; x <= 2000 ; x++){ bool v = true; for(int i = 1 ; i <= n ; i++){ int pos = upper_bound(a + 1, a + 1 + n,x + i - 1) - a - 1; if((pos - i + 1) % p == 0) { v = false; break; } } if(v) ans.push_back(x); } cout << ans.size() << '\n'; for(auto it : ans) cout << it << ' '; cout << '\n'; return 0; }

E2基本思路：

对于E2肯定我们不能枚举$x$，那么通过E1的代码我们容易发现答案都是连续的，所以我们可以思考$f(x)$%$p==0$是否具有单调关系，如果有单调关系，那么很明显我们就能二分$x$降低复杂度了。

那么我们如何证明$f(x)$对$p$取模一定的单调的，或者说证明对于某一$x_i$出现了$f(x_i)$能被$p$整除，那么之后更大$x>x_i$的$f(x)$一定也会被$p$整除。

对于$x$的增大，我们发现对于每个位置的$po{s}_i-i+1$一定的单调不减的，而且这部分是以一种阶乘的方式，从大的数往下依次递减，然后再回到一个大数的(打表可以发现，应该也可以证明，太菜了证明不来)，所以就是说只要最大的$po{s}_i-i+1$它大于等于$p$，那么对于随着$x$的增大，单调不减的最大$po{s}_i-i+1$也会增大，而由于这部分具有类似阶乘的递减关系，就一定也会存在一个位置会被$p$整除。

因此，二分是成立的，而最小的x也就是二分的左边界就应该是敌人按顺序排列的情况，能够直接算到这个最小x，然后我们二分找到最大x，这之间的就是所有符合条件的答案了。

E2参考代码：

#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false) #define int long long #define rep(i, l, r) for (int i = l; i <= r; i++) #define per(i, l, r) for (int i = l; i >= r; i--) #define mset(s, _) memset(s, _, sizeof(s)) #define pb push_back #define pii pair <int, int> #define mp(a, b) make_pair(a, b) #define INF (int)1e18 inline int read() { int x = 0, neg = 1; char op = getchar(); while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); } while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); } return neg * x; } inline void print(int x) { if (x < 0) { putchar('-'); x = -x; } if (x >= 10) print(x / 10); putchar(x % 10 + '0'); } const int maxn = 1e5 + 10; int n,p,a[maxn]; bool check(int x) { for (int i = 1; i <= n; i++) { int pos = upper_bound(a + 1, a + 1 + n, x + i - 1) - a - 1; if ((pos - i + 1) % p == 0) return false; } return true; } signed main() { IO; cin >> n >> p; rep(i, 1, n) cin >> a[i]; sort(a + 1, a + 1 + n); int mn = 1; for(int i = 1 ; i <= n ; i++) mn = max(mn,a[i] - i + 1); int l = mn,r = INF,ans = -1; while (l <= r) { int mid = (l + r) / 2; if (check(mid)) ans = mid, l = mid + 1; else r = mid - 1; } if(ans == -1){ cout << 0 << '\n'; return 0; } cout << ans - mn + 1 << '\n'; for(int i = mn ; i <= ans ; i++) cout << i << ' '; cout << '\n'; return 0; }