Educational Codeforces Round 80 (Rated for Div. 2) A. Deadline B. Yet Another Meme Problem C. Two Arrays D. Minimax Problem E. Messenger Simulator
题目链接：https://codeforces.com/contest/1288/problem/A
题意：
给你一个 N 和 D，问是否存在一个 X ， 使得 $x+lceil dfrac {x}{d+1} ceil leq n$
分析：
可以将式子变为
$egin{aligned}left( x+1 ight) +lceil dfrac {d}{x+1} ceil leq n+1\ Rightarrow 2sqrt {d}leq n+1end{aligned}$
然后判断一下即可
#include<bits/stdc++.h> using namespace std; #define ll long long const int N = 2e5 + 10; int main() { int t; cin >> t; while(t --) { double n , d; cin >> n >> d; if(2 * sqrt(d) <= n + 1) cout << "YES" << ' '; else cout << "NO" << ' '; } return 0; }
B. Yet Another Meme Problem
题目链接：https://codeforces.com/contest/1288/problem/B
题意：
给你一个 A 和 B，你可以从1 - A 中任选一个 a ，1 - B 中任选一个 b，使得 a + b + a * b = conc(a , b) // conc(12 , 23) = 1223
问你最多可以从两个集合中找出几对满足上述关系的a ，b
分析：
设 k 为 B 的位数，则 conc(a , b) = a * 10 ^ k + b , 即
$egin{aligned}a imes b+a+b=a imes 10^{k}+b\ Rightarrow aleft( b+1 ight) =a imes 10^{k}end{aligned}$
所以当b = 10^x-1时则任意a都可以与b组成一对,所以ans = A * (1 - B 中 9,99,999...的个数)
#include<bits/stdc++.h> using namespace std; #define ll long long const int N = 2e5 + 10; int main() { int t; cin >> t; while(t --) { ll a , b; cin >> a >> b; int now = 9 , cnt = 0; while(now <= b) now = now * 10 + 9 , cnt ++; cout << a * cnt << ' '; } return 0; }
C. Two Arrays
题目链接：https://codeforces.com/contest/1288/problem/C
题意：
给你一个 N 和 M（1 <= N <= 1000 , 1 <= M <= 10 ），M表示数组的长度，N表示你可以任意使用[1 , N]内的数字（可重复使用）
问你有多少种方法构造两个数组 A , B 使得 A 数组不降序 , B数组不升序且对于数组中的任一位置 i 都有ai < bi
分析：
①dp
因为数据范围不大 ，所以比赛时很快想到了O(n * n * m)的做法
定义dp1[i][j] 表示 A数组第 i 项为 j 有多少种方案，定义dp2[i][j]表示 B数组第 i 项为 j 有多少种方案
则 $ans=sum ^{n}_{i=1}sum ^{n}_{i=i}dp_{1}left[ m ight] left[ i ight] imes dp_{2}left[ m ight] left[ j ight] $
#include<bits/stdc++.h> using namespace std; #define ll long long const int MOD = 1e9 + 7; const int N = 1e3 + 10; ll dp1[15][N] , dp2[15][N]; int main() { int n , m; cin >> n >> m; for(int i = 1 ; i <= n ; i ++) dp1[1][i] = dp2[1][i] = 1; for(int i = 2 ; i <= m ; i ++) for(int j = 1 ; j <= n ; j ++) for(int k = 1 ; k <= j ; k ++) dp1[i][j] += dp1[i - 1][k] , dp1[i][j] %= MOD; for(int i = 2 ; i <= m ; i ++) for(int j = 1 ; j <= n ; j ++) for(int k = j ; k <= n ; k ++) dp2[i][j] += dp2[i - 1][k] , dp2[i][j] %= MOD; ll ans = 0; for(int i = 1 ; i <= n ; i ++) for(int j = i ; j <= n ; j ++) ans += dp1[m][i] * dp2[m][j] , ans %= MOD; cout << ans << ' '; return 0; }
②组合数学
由题可得 a1 <= a2 <= a3 ... <= am，b1 >= b2 >= b3 ... >= bm，又因为bm >= am
所以a1,a2,a3...am,bm,...b3,b2,b1就是一长度为2 * m且不降序的数组
我们设 xi 为第 i 个数被选中的次数，那么 x1 + x2 + x3 + ... + xn = 2 * m
于是我们可以把数组中的每一个位置看成一个小球，把n个数中的每一个数看成一个盒子
那么就有 2 * m个小球，n个盒子。题目就可以转换为我们要将2 * m个小球放在n个盒子里（盒子可以为空）
这样就成了隔板法的经典例题
卢卡斯随便一搞就完事了
/*这句话写给我自己看⊙︿⊙*/
/*(先通过这个方法计算总方案数,每个方案选择出来的数都可以从小到大插到2 * m个位置上,所以每个方案必定合法,对答案必定有贡献)*/
#include<bits/stdc++.h> using namespace std; #define ll long long const int MOD = 1e9 + 7; const int N = 2e5 + 10; ll F[N]; void init(ll p) { F[0] = 1; for(int i = 1;i <= p;i++) F[i] = F[i-1]*i % MOD; } ll inv(ll a,ll m) { if(a == 1)return 1; return inv(m%a,m)*(m-m/a)%m; } ll Lucas(ll m,ll n,ll p) { ll ans = 1; while(n && m) { ll a = n % p; ll b = m % p; if(a < b)return 0; ans = ans * F[a] % p * inv(F[b] * F[a - b] % p , p) % p; n /= p; m /= p; } return ans; } int main() { init(N); int n , m; cin >> n >> m; cout << Lucas(n - 1 , 2 * m + n - 1 , MOD) << ' '; return 0; }
D. Minimax Problem
题目链接：https://codeforces.com/contest/1288/problem/D
题意：
给你 n <= 3e5 个长度为 m <= 8 的数组，你需要选出两个数组a , b使他们的每一位结合（留下max(ai , bi)），结合后数组中的最小值必须尽可能的大
分析：
首先我们肯定需要一个数作为最小值来进行筛选，但是题目最多可能有 n * m 种数，枚举每个数再操作肯定是不可能的，所以比赛时一眼就想到二分
先将 n 个数组看成是 n * m 的矩阵，那么矩阵的第i行就代表第i个数组
可以先二分一个最小值 mid ，然后遍历矩阵，将小于mid的元素标记为0，大于等于mid的标记为1，于是就可以得到一个01矩阵，并且我们把每行都看成一个二进制数
那么这时候如果有任意两行对应的二进制数进行或运算得到 (1 << m) - 1 , 即两行 | 完之后若得到全1的一行(结合之后每个数都 >= mid)，那么说明这个mid是可行的,更新ans1,ans2
然而这步如果我们暴力一对一的做法来查找这两行则复杂度为O( n^2)肯定是不行的,但是题目给的 m 最大值只有8，也就是说01矩阵的每一行转二进制后对应的值肯定是小于256
所以我们只要在对这256个数进行暴力一对一同时判断是否有两行能与之对应即可
比赛时候用了部分以前写状压dp的优化，虽然运行起来会快一点点，但是其实关了同步流就没什么卵用，反而还丑的不像话（貌似不关同步流会TLE）
赛后给 Vv 讲了做法，发现她居然用同样的思路写出比我好看的代码？excuse me？？
于是我赶紧写了一个比她好看的（虽然还是有点丑）
#include<bits/stdc++.h> using namespace std; #define rep(i , a , b) for(int i = a ; i <= b ; i ++) #define ll long long const int N = 3e5 + 10; int a[N][10] , b[N][10]; int n , m ; int id[1010]; int tot; int ans1 , ans2; bool check(int mid) { memset(id , 0 , sizeof(id)); rep(i , 1 , n) { rep(j , 1 , m) if(a[i][j] >= mid) b[i][j] = 1; else b[i][j] = 0; } rep(i , 1 , n) { int temp = 0; rep(j , 1 , m) temp += b[i][j] << (j - 1); id[temp] = i; } rep(i , 0 , 256) { rep(j , 0 , 256) { if((i | j) == tot && id[i] && id[j]) {ans1 = id[i] , ans2 = id[j] ; return true;} } } return false; } int main() { ios::sync_with_stdio(false); cin >> n >> m; tot = (1 << m) - 1; rep(i , 1 , n) rep(j , 1 , m) cin >> a[i][j]; int l = 0 , r = 1000000010 , mid; while(l <= r) { mid = l + r >> 1; if(check(mid)) l = mid + 1; else r = mid - 1; } cout << ans1 << " " << ans2 << ' '; return 0; }
E. Messenger Simulator
题目链接：https://codeforces.com/contest/1288/problem/E
题意：
给你一个长度为n的序列，初始化为1,2,3...n，现在进行m次操作，每次操作有一个数 x，你需要将 x 提至数组的首位，问1~m次操作中每个数在序列中的最左端和最右端分别是多少
分析：
对于第 i 个数，如果它被操作过，则它的最左端为1，否则为 i （它前面的数被操作不影响它当前位置，后面的数被操作只会使它位置增大）
如果没被操作过，则最右端为操作结束之后的位置（同上），但是若它被操作过，则它的位置会减小（若为1则不变），而之后别的数被操作，它的位置又会增大
所以若它被操作过，它的位置即可能增加，也可能减少。而当它刚被操作结束，别的数被操作时，它的位置必定增加，一直到所有操作都结束或者它又一次被操作。
所以它的最右端需要在每次被操作时更新。
我们可以先在序列前空下m个空位，并初始化第i个数在操作前的坐标pos[i]为 i + m ， 并将该坐标标记为1，代表这坐标上存在着一个数。若某坐标上不存在数则标记为0
当第 j 次操作时，我们在更新被操作数X的最右端的同时将被操作数X坐标改为m + 1 - j，并把原来的坐标标记去掉，并在新坐标m + 1 - j做标记。
而对于某个数 i ，它当前的相对位置为1 ~ pos[i]有标记的坐标的个数，即1 ~ pos[i]的区间和，所以我们可以想到用树状数组来维护这些操作
当所有操作结束之后我们再去更新每个数的最大值即可
（通宵写博客，脑子有点不好使，感觉自己没有表述清楚，不过代码还是很好理解的）
ps：比赛的时候其实还留有半小时的时间可以去思考E，但是因为D写得太丑太乱搞得自己有点自闭 + 为人太懒了于是就放弃了，现在想来有点可惜，喜欢以后不会再这样了！
#include<bits/stdc++.h> using namespace std; #define rep(i , a , b) for(int i = a ; i <= b ; i ++) #define ll long long const int N = 3e5 + 10; int pos[N << 1]; struct node{ int mi , ma; }ha[N << 1]; int tree[N << 4] , a[N]; int n , m ; int lowbit(int x) { return x & (-x); } void update(int pos , int x) { while(pos <= N * 2) { tree[pos] += x; pos += lowbit(pos); } } int query(int x) { int res = 0; while(x) { res += tree[x]; x -= lowbit(x); } return res; } int main() { cin >> n >> m; rep(i , 1 , n) ha[i].mi = ha[i].ma = i , pos[i] = N + i , update(N + i , 1); rep(i , 1 , m) cin >> a[i]; rep(i , 1 , m) { ha[a[i]].mi = 1; ha[a[i]].ma = max(ha[a[i]].ma , query(pos[a[i]])); update(pos[a[i]] , -1); update(N + 1 - i , 1); pos[a[i]] = N + 1 - i; } rep(i , 1 , n) ha[i].ma = max(ha[i].ma , query(pos[i])); rep(i , 1 , n) cout << ha[i].mi << " " << ha[i].ma << ' '; return 0; }