A. Deadline
题目链接：https://codeforces.com/contest/1288/problem/A
题意：
给你一个 N 和 D，问是否存在一个 X ， 使得 $x+\lceil \dfrac {x}{d+1}\rceil \leq n$
分析：
可以将式子变为
$\begin{aligned}\left( x+1\right) +\lceil \dfrac {d}{x+1}\rceil \leq n+1\\ \Rightarrow 2\sqrt {d}\leq n+1\end{aligned}$
然后判断一下即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + ;
int main()
{
int t;
cin >> t;
while(t --)
{
double n , d;
cin >> n >> d;
if( * sqrt(d) <= n + )
cout << "YES" << '\n';
else cout << "NO" << '\n';
}
return ;
}
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 , 即
$\begin{aligned}a\times b+a+b=a\times 10^{k}+b\\ \Rightarrow a\left( b+1\right) =a\times 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 + ;
int main()
{
int t;
cin >> t;
while(t --)
{
ll a , b;
cin >> a >> b;
int now = , cnt = ;
while(now <= b) now = now * + , cnt ++;
cout << a * cnt << '\n';
}
return ;
}
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\right] \left[ i\right] \times dp_{2}\left[ m\right] \left[ j\right] $
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 1e9 + ;
const int N = 1e3 + ;
ll dp1[][N] , dp2[][N];
int main()
{
int n , m;
cin >> n >> m;
for(int i = ; i <= n ; i ++)
dp1[][i] = dp2[][i] = ;
for(int i = ; i <= m ; i ++)
for(int j = ; j <= n ; j ++)
for(int k = ; k <= j ; k ++)
dp1[i][j] += dp1[i - ][k] , dp1[i][j] %= MOD;
for(int i = ; i <= m ; i ++)
for(int j = ; j <= n ; j ++)
for(int k = j ; k <= n ; k ++)
dp2[i][j] += dp2[i - ][k] , dp2[i][j] %= MOD;
ll ans = ;
for(int i = ; i <= n ; i ++)
for(int j = i ; j <= n ; j ++)
ans += dp1[m][i] * dp2[m][j] , ans %= MOD;
cout << ans << '\n';
return ;
}
②组合数学
由题可得 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 + ;
const int N = 2e5 + ;
ll F[N];
void init(ll p)
{
F[] = ;
for(int i = ;i <= p;i++)
F[i] = F[i-]*i % MOD;
}
ll inv(ll a,ll m)
{
if(a == )return ;
return inv(m%a,m)*(m-m/a)%m;
}
ll Lucas(ll m,ll n,ll p)
{
ll ans = ;
while(n && m)
{
ll a = n % p;
ll b = m % p;
if(a < b)return ;
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 - , * m + n - , MOD) << '\n';
return ;
}
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 + ;
int a[N][] , b[N][];
int n , m ;
int id[];
int tot;
int ans1 , ans2;
bool check(int mid)
{
memset(id , , sizeof(id));
rep(i , , n)
{
rep(j , , m)
if(a[i][j] >= mid)
b[i][j] = ;
else b[i][j] = ;
}
rep(i , , n)
{
int temp = ;
rep(j , , m)
temp += b[i][j] << (j - );
id[temp] = i;
}
rep(i , , )
{
rep(j , , )
{
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 = ( << m) - ;
rep(i , , n)
rep(j , , m)
cin >> a[i][j];
int l = , r = , mid;
while(l <= r)
{
mid = l + r >> ;
if(check(mid)) l = mid + ;
else r = mid - ;
}
cout << ans1 << " " << ans2 << '\n';
return ;
}
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 + ;
int pos[N << ];
struct node{
int mi , ma;
}ha[N << ];
int tree[N << ] , a[N];
int n , m ;
int lowbit(int x)
{
return x & (-x);
}
void update(int pos , int x)
{
while(pos <= N * )
{
tree[pos] += x;
pos += lowbit(pos);
}
}
int query(int x)
{
int res = ;
while(x)
{
res += tree[x];
x -= lowbit(x);
}
return res;
}
int main()
{
cin >> n >> m;
rep(i , , n)
ha[i].mi = ha[i].ma = i , pos[i] = N + i , update(N + i , );
rep(i , , m)
cin >> a[i];
rep(i , , m)
{
ha[a[i]].mi = ;
ha[a[i]].ma = max(ha[a[i]].ma , query(pos[a[i]]));
update(pos[a[i]] , -);
update(N + - i , );
pos[a[i]] = N + - i;
} rep(i , , n)
ha[i].ma = max(ha[i].ma , query(pos[i]));
rep(i , , n)
cout << ha[i].mi << " " << ha[i].ma << '\n';
return ;
}