CF1710 题解
A
看图写话。
想象一个格子以及周围同色格的颜色必须呈一个三叉的形状：
# # #
## ## ### ###
# # #
这些三叉拼起来最小的形状，就是两个以上的整行，或整列。所以遍历每一种颜色，通过整除观察它最多能填几列，如果 \(1\) 列就不能放，如果奇数列就要看是否一个数可以取到奇数；再对行做一遍即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
ll a[N],n,m,k;
inline bool try_line()
{
ll tmp = 0; int can_be_odd = 0;
for(int i = 1;i <= k;i++)
{
if(a[i] / m <= 1) continue;
if(a[i] / m > 2) can_be_odd = 1;
tmp += a[i] / m;
}
return tmp >= n && ((n & 1) ? can_be_odd : 1);
}
inline bool try_column()
{
ll tmp = 0; int can_be_odd = 0;
for(int i = 1;i <= k;i++)
{
if(a[i] / n <= 1) continue;
if(a[i] / n > 2) can_be_odd = 1;
tmp += a[i] / n;
}
return tmp >= m && ((m & 1) ? can_be_odd : 1);
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>m>>k;
for(int i = 1;i <= k;i++) cin>>a[i];
if(try_line()) puts("Yes");
else if(try_column()) puts("Yes");
else puts("No");
}
return 0;
}
B
Rairn 没来qwq。
场上没切这题，耻辱。
考虑答案要算总共贡献减去一个凸函数的值是否超过 \(m\) 。考虑最后结果是很多的 “山峰”，只有这些 “峰顶” 有可能成为删掉过后的最大值，然而这些 “山峰”有斜率转折且是邻域内的极大值，所以一定是凸函数顶点 \(x_i\) 。
所以我们只需要计算所有降雨时这 \(n\) 个顶点的函数值，直接动态开点线段树将 \(k,b\) 塞进去即可（可以离散化）。算出来后挑出那些大于 \(m\) 的函数值，扫描每个 \(i\) ：
如果对于一个大于 \(m\) 的 \(j\) ，\(i\) 没有包含 \(j\) ，那么 \(j\) 一定会成为剩下大于 \(m\) 的那一个，不合法，不然减去 \(i\) 的贡献后 ，\(j\) 处的值（称作 \(v_j\)），需要小于 \(m\) ，列出式子：
\[v_j - (p_i - |x_i - x_j|) \leq m \]拆为：
\[v_j - (p_i - x_i + x_j) \leq m\\ v_j - (p_i + x_i - x_j) \leq m \]移项：
\[v_j - x_j \leq m + x_i - p_i\\ v_j + x_j \leq m - p_i - x_i \]所以要满足对于所有 \(j\) ，都有这个式子，直接将最大的 \(v_j - x_j,v_j + x_j\) 求出来 \(\Theta(1)\) 判断即可，复杂度 \(\Theta (n \log n)\) 。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5,TOP = 1e9;
typedef long long ll;
bool st;
ll q[N];
int cnt = 0,n,m,x[N],p[N],ans[N];
struct SegTree{
ll k[N * 50],b[N * 50];
int lc[N * 50],rc[N * 50],tot;
inline int nn()
{
++tot;
k[tot] = 0; b[tot] = 0; lc[tot] = 0; rc[tot] = 0;
return tot;
}
inline void modify(ll l,ll r,ll L,ll R,ll nk,ll nb,int pos)
{
if(L <= l && r <= R) {k[pos] += nk; b[pos] += nb; return;}
ll mid = (l + r) >> 1;
if(L <= mid) {if(!lc[pos]) lc[pos] = nn(); modify(l,mid,L,R,nk,nb,lc[pos]);}
if(R > mid) {if(!rc[pos]) rc[pos] = nn(); modify(mid + 1,r,L,R,nk,nb,rc[pos]);}
}
inline ll query(ll l,ll r,ll x,ll nk,ll nb,int pos)
{
nk += k[pos]; nb += b[pos];
if(l == r) {return nk * x + nb;}
ll mid = (l + r) >> 1;
if(x <= mid) return query(l,mid,x,nk,nb,lc[pos]);
else return query(mid + 1,r,x,nk,nb,rc[pos]);
}
}t;
bool ed;
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
t.tot = 0; cnt = 0; t.nn();
for(int i = 1;i <= n;i++)
{
cin>>x[i]>>p[i];
t.modify(-TOP,TOP,x[i] - p[i],x[i],1,p[i] - x[i],1);
t.modify(-TOP,TOP,x[i] + 1,x[i] + p[i],-1,x[i] + p[i],1);
}
for(int i = 1;i <= n;i++) q[i] = t.query(-TOP,TOP,x[i],0,0,1);
ll maxid = -1e18,maxia = -1e18;
for(int i = 1;i <= n;i++) if(q[i] > m) maxia = max(maxia,q[i] + x[i]),maxid = max(maxid,q[i] - x[i]);
for(int i = 1;i <= n;i++)
{
if(1ll * p[i] - x[i] + m >= maxid && 1ll * p[i] + x[i] + m >= maxia) ans[i] = 1;
else ans[i] = 0;
}
for(int i = 1;i <= n;i++) cout<<ans[i];
cout<< '\n';
}
return 0;
}
C
考虑每一位去做，就是数位 dp。本来想枚举 \(a \oplus b\) 和 \(a \oplus c\) 的值，但是考虑不好算 \(a,b,c \leq n\) 的范围，所以转而枚举 \(a,b,c\) 的值。
钦定 \(a \oplus b,b \oplus c \leq a \oplus c\)，将当前位选择列出可得：
| value | a | b | c |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 0 |
| 3 | 0 | 1 | 1 |
| 4 | 1 | 0 | 0 |
| 5 | 1 | 0 | 1 |
| 6 | 1 | 1 | 0 |
| 7 | 1 | 1 | 1 |
由于前两个异或小于等于第三个，所以容易想到设两个状态 \(ls1,ls2\) 表示根据前 \(siz\) 位后是否已经有 \(a \oplus b \leq a \oplus c\) ， \(b \oplus c \leq a \oplus c\) 。容易发现如果没有则不能选 \(2,5\) 状态。
我们知道两个异或值相加一定大于等于另外一个异或值（因为两个异或值异或起来等于第三个，而且 \(x \oplus y \leq x + y\)），不取等的条件是两个要有交，所以再记一个状态 \(eq\) 表示是否存在一个位 \(i\) ，使得 \((a \oplus b)_i = (b \oplus c)_i\) 。
最后记三个 \(li1,li2,li3\) 代表 \(a,b,c\) 是否顶上限即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5,MOD = 998244353;
int a[N],n;
typedef long long ll;
ll f[N][8][8];
inline int zip(int x,int y,int z) {return x | (y << 1) | (z << 2);}
inline ll dfs(int siz,bool ls1,bool ls2,bool eq,bool li1,bool li2,bool li3)
{
if(siz == n + 1) {return eq;}
if(f[siz][zip(ls1,ls2,eq)][zip(li1,li2,li3)] != -1) return f[siz][zip(ls1,ls2,eq)][zip(li1,li2,li3)];
int top1 = (li1 ? a[siz] : 1),top2 = (li2 ? a[siz] : 1),top3 = (li3 ? a[siz] : 1);
ll res = 0;
for(int i = 0;i <= top1;i++)
for(int j = 0;j <= top2;j++)
for(int k = 0;k <= top3;k++)
{
if(!ls1 && (i ^ j) > (i ^ k)) continue;
if(!ls2 && (j ^ k) > (i ^ k)) continue;
res += dfs(siz + 1,ls1 | ((i ^ j) < (i ^ k)),ls2 | ((j ^ k) < (i ^ k)),eq | (((i ^ j) == 1) && ((j ^ k) == 1)),li1 & (i == a[siz]),li2 && (j == a[siz]),li3 && (k == a[siz]));
res %= MOD;
}
return f[siz][zip(ls1,ls2,eq)][zip(li1,li2,li3)] = res;
}
char s[N];
int main()
{
memset(f,-1,sizeof(f));
scanf("%s",s + 1);
n = strlen(s + 1);
for(int i = 1;i <= n;i++) a[i] = s[i] - '0';
cout<<dfs(1,0,0,0,1,1,1) * 3 % MOD;
return 0;
}