Codeforces Round 810 div.1 ABC
本文最后更新于:2 年前
A. Color the Picture
观察发现同一个颜色必须呈整行或整列才能满足条件,且至少需要连续两行,计算一下每个颜色最多可以涂几行/列即可,特判奇数行/列时,所有颜色都仅能涂2行/列的情况。
ll n, m, k;
ll a[maxn];
void solve(){
cin >> n >> m >> k;
for(ll i=1;i<=k;i++) cin >> a[i];
ll s = 0;
bool fg = 0;
for(ll i=1;i<=k;i++){
ll d = a[i] / n;
if(d > 1) s += d;
if(d > 2) fg = true;
}
if((fg || m % 2 == 0) && s >= m){
cout << "Yes\n";
return;
}
s = 0;
fg = 0;
for(ll i=1;i<=k;i++){
ll d = a[i] / m;
if(d > 1) s += d;
if(d > 2) fg = true;
}
if((fg || n % 2 == 0) && s >= n){
cout << "Yes\n";
return;
}
cout << "No\n";
}
B. Rain
首先预处理出每个位置上降水量的总值(离散化差分或数据结构),然后将所有降水按照左端点排序,枚举每个位置 $x$,二分找出第一个 删除之后,不能使得 $x$ 处降水量少于m的位置,显然这个点右侧的全都不合法。
同理再按照右端点排序搞一次,就把所有不合法的点筛去了。
struct node{
ll x, p;
ll id;
ll sum;
}a[maxn], b[maxn];
ll n, m;
map<ll, ll> d2;
void solve(){
cin >> n >> m;
d2.clear();
for(ll i=1;i<=n;i++){
a[i].id = i;
cin >> a[i].x >> a[i].p;
d2[a[i].x-a[i].p+1] += 1;
d2[a[i].x+1] -= 2;
d2[a[i].x+a[i].p+1] += 1;
}
ll sum = 0;
vector<pair<ll, ll>> d11;
for(auto [p, c]: d2){
sum += c;
d11.emplace_back(p, sum);
}
sum = 0;
sort(a+1, a+n+1, [](node x, node y){
return x.x < y.x;
});
for(ll i=0, j=1;i<d11.size();i++){
while(j <= n && d11[i].first > a[j].x){
a[j].sum = sum + d11[i-1].second * (a[j].x - d11[i-1].first);
j++;
}
sum += d11[i].second;
if(i > 0) sum += d11[i-1].second * (d11[i].first - d11[i-1].first - 1);
while(j <= n && d11[i].first == a[j].x){
a[j].sum = sum;
j++;
}
}
sort(a+1, a+n+1, [](node x, node y){
return x.x - x.p + 1 < y.x - y.p + 1;
});
for(ll i=1;i<=n;i++) b[i] = a[i];
sort(b+1, b+n+1, [](node x, node y){
return x.x + x.p - 1 < y.x + y.p - 1;
});
vector<ll> ans(n+1, 1);
ll midel = 1e9;
for(ll i=1;i<=n;i++){
if(a[i].sum <= m) continue;
ll d = a[i].sum - m;
ll p = lower_bound(a+1, a+n+1, a[i].x - d + 1, [&](node a, ll pos){
return a.x - a.p + 1 <= pos;
}) - a;
midel = min(midel, p);
}
for(ll i=midel;i<=n;i++) ans[a[i].id] = 0;
ll mxdel = 0;
for(ll i=1;i<=n;i++){
if(b[i].sum <= m) continue;
ll d = b[i].sum - m;
ll p = lower_bound(b+1, b+n+1, b[i].x+d-1, [&](node a, ll pos){
return a.x + a.p - 1 < pos;
}) - b;
mxdel = max(mxdel, p-1);
}
for(ll i=1;i<=mxdel;i++) ans[b[i].id] = 0;
for(ll i=1;i<=n;i++) cout << ans[i];
cout << '\n';
}
C. XOR Triangle
新的一种bitmask技巧:
设 $cnt_{i,j,k}$,定义是这样的:
当 $a,b,c$ 的第 $x$ 位分别为 $i,j,k$ 时,$cnt_{i,j,k}$ 就在 $x$ 位上为1,否则为0
例如对于下面的 $a,b,c$,有如下 $cnt$:
$$
cnt[011]:&10000001\
a&01010010\
b&10010101\
c&10111001
$$
即仅有 $abc=011$ 的位置,$cnt_{011}$ 才为1
有了这种 $cnt$ 数组,就可以推断出一些东西:
$a=\sum\sum cnt_{1jk}$($a$ 中所有的 $1$ 不重复不遗漏的加起来)
$b=\sum\sum cnt_{i1k}$
$a\bigoplus b=\sum cnt_{01k}+\sum cnt_{10k}$
简单推断可得,题目的条件等价于:$cnt_{001}+cnt_{110}>0$,$cnt_{011}+cnt_{100}>0$,$cnt_{010}+cnt_{101}>0$
设 $dp[i][j][k]$ 为前 $i$ 位,上限状态为 $j$,$cnt$ 状态为 $k$ 的方案数
$j$ 用三位表示 $a,b,c$ 三个数是否达到了上限,$k$ 用三位表示上述三组 $cnt$ 是否已经大于0,转移复杂度为 $O(8^3n)$
vector<int> subset(int x){
int k = x;
vector<int> r;
while(k > 0){
r.push_back(k);
k = (k - 1) & x;
}
r.push_back(0);
return r;
}
void solve() {
string s;
cin >> s;
vector f(8, vector<ll>(8, 0));
f[0][0] = 1;
for(char c: s){
int curlim = (c == '0' ? 0 : 7);
vector g(8, vector<ll>(8, 0));
for(int lim = 0; lim < 8; lim++){
for(int frm = 0; frm < 8; frm++){
for(int st: subset(lim | curlim)){
int nt = frm;
if(st == 1 || st == 6){
nt |= 1;
}
if(st == 2 || st == 5){
nt |= 2;
}
if(st == 3 || st == 4){
nt |= 4;
}
(g[lim | (st ^ curlim)][nt] += f[lim][frm]) %= mode;
}
}
}
f = g;
}
ll ans = 0;
for(int i = 0; i < 8; i++) (ans += f[i][7]) %= mode;
cout << ans << '\n';
}