CF1710A Color the Picture
标签：思维题 \(C^-\)
典型的有图有真相，嘻嘻（抽风了？
显然有一个结论，我们颜色要么一行一行天，要么一列一列填。
并且填进去的颜色必须不少于两行/列
然后就是记一个 ans 和 一个 over 表示如果每个颜色都两行/列填进去能填的最多列数，以及两行/列填进去后还能填多少行/列
最后就按行/列填进去判断一下即可
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 1e5 + 8;
int T;
int n,m,k;
int a[NN];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
ll ans = 0,over = 0;
for(int i = 1; i <= k; ++i){
scanf("%d",&a[i]);
ans += a[i] / n >= 2 ? 2 : 0;
over += a[i] / n >= 2 ? (a[i]/n-2) : 0;
}
if(ans == m){puts("Yes");continue;}
if(ans >= m && ((ans&1) == (m&1))){puts("Yes");continue;}
if(ans + over >= m && over){puts("Yes");continue;}
ans = 0;over = 0;
for(int i = 1; i <= k; ++i){
ans += a[i] / m >= 2 ? 2 : 0;
over += a[i] / m >= 2 ? (a[i]/m-2) : 0;
}
if(ans == n){puts("Yes");continue;}
if(ans >= n && ((ans&1) == (n&1))){puts("Yes");continue;}
if(ans + over >= n && over){puts("Yes");continue;}
puts("No");
}
}
CF1710B Rain
考虑我的方法是预处理 \(O(n\log n)\)，最后求答案 \(O(n)\) 的
考虑我们显然可以先从左到右扫一遍，对于每一个 \(x_i\) 记录它左边的下雨对于它的雨水的深度产生的影响
然后这显然是很好维护的，就是记录当前点的水的深度影响和影响当前点的下雨天的数量，用数学语言表示就是记录当前点的点值和斜率
然后我们需要用一个小根堆记录最近的和 \(x\) 轴的交点，方便将直线退出影响，然后 \(x_i\) 的右边的下雨的影响也可以类比
最后求答案，显然可以找出所有的需要减去的位置和高度，显然我们可以将位置为 \(x\) 高度为 \(h\) 的需求抽象成 \([x-h,x+h]\) 的区间
最后就是判断去掉某一天的下雨的对应的区间能否包含所有区间，这就是维护所有需求区间的最左边和最右边 \(O(n)\) 扫一遍，然后就可以对每个询问 \(O(1)\) 求解了。
考虑代码里面后面的需求区间的最左端点和最右端点的求解有一点麻烦，希望能看懂 QWQ。
code:
#include<bits/stdc++.h>
using namespace std;
const int NN = 2e5 + 8;
typedef long long ll;
int n,m;
struct Rep{
ll x,p;
int num;
bool operator < (const Rep &A)const{
return x < A.x;
}
}a[NN],b[NN];
int top;
priority_queue<ll,vector<ll>,greater<ll> > Q;
priority_queue<ll> R;
bool ans[NN];
bool res[NN];
ll f[NN];
void solve(){
memset(f,0,sizeof(f));top = 0;
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; ++i)
scanf("%lld%lld",&a[i].x,&a[i].p),a[i].num = i,ans[i] = 1;
sort(a+1,a+1+n);
ll now = 0,cnt = 0;
while(!Q.empty())Q.pop();
for(int i = 1; i <= n; ++i){
while(!Q.empty() && Q.top() <= a[i].x){
now -= Q.top() - a[i-1].x;
--cnt;
Q.pop();
}
if(i != 1) now -= (a[i].x - a[i-1].x) * cnt;
++cnt;
now += a[i].p;
Q.push(a[i].x+a[i].p);
f[i] += now;
}
while(!R.empty())R.pop();
now = 0,cnt = 0;
for(int i = n; i >= 1; --i){
while(!R.empty() && R.top() >= a[i].x){
now -= a[i+1].x - R.top();
--cnt;
R.pop();
}
if(i != n) now -= (a[i+1].x - a[i].x) * cnt;
f[i] += now;
++cnt;
now += a[i].p;
R.push(a[i].x-a[i].p);
}
// for(int i = 1; i <= n; ++i){
// printf("%lld:%lld\n",a[i].x,f[i]);
// }
// puts("====================/");
for(int i = 1; i <= n; ++i){
if(f[i] > m){
b[++top] = {a[i].x,f[i]-m};
}
}
ll lmin = 1e18;
for(int i = 1,j = 1; i <= n; ++i){
while(j <= top && b[j].x <= a[i].x) lmin = min(lmin,b[j].x-b[j].p), ++j;
if(lmin < a[i].x - a[i].p) ans[i] = 0;
}
ll rmax = -1e18;
for(int i = n, j = top; i >= 1; --i){
while(j >= 1 && b[j].x >= a[i].x) rmax = max(rmax,b[j].x + b[j].p),--j;
if(rmax > a[i].x + a[i].p) ans[i] = 0;
}
for(int i = 1; i <= n; ++i){
res[a[i].num] = ans[i];
}
for(int i = 1; i <= n; ++i) printf("%d",res[i]);
puts("");
}
int main(){
int T;
scanf("%d",&T);
while(T--){
solve();
}
}
CF1710C XOR Triangle
我们显然可以想到异或的性质：
-
\(a + b \geq a \oplus b\)
-
\(a + b > a \oplus b\) 当且仅当 \(a,b\) 有交集（\(a|b \neq 0\)）
我们应用到这一道题目上就是:
- 若满足 \((a\oplus b) + (b \oplus c) \geq (a \oplus c)\) 当且仅当 \((a\oplus b)\) 与 \((b \oplus c)\) 有交
又因为我们的限制是对 \(a,b,c\) 的，而不是对 \(a\oplus b,b\oplus c,c\oplus a\) 的，所以说我们显然 数位DP 是枚举 \(a,b,c\)
我们设 \(f_{i,j,k}\) 表示前 \(i\) 位，\(j(0\sim 7)\) 表示三种亦或值相互之间有没有交，\(k(0\sim 7)\) 表示有没有顶上限(显然不同于普通的 数位DP 这里要枚举有没有顶上限，不然复杂度是假的)
转移很显然，直接记忆化搜索即可
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 2e5 + 8, MOD = 998244353;
int f[NN][8][8];
string s;
int a[NN];
inline int Calc(int i,int j,int k){
return ((i^j) & (j^k)) + (((i^k) & (j^k)) << 1) + (((i^j) & (i^k)) << 2);
}
inline int Calc2(int x,int i,int j,int k){
return (a[x] == i) + ((a[x] == j) << 1) + ((a[x] == k) << 2);
}
ll dfs(int x,int now,int up){
if(x == s.size()) return now == 7;
if(f[x][now][up] != -1) return f[x][now][up];
int ua = (up&1) ? a[x]:1, ub = (up>>1&1)?a[x]:1, uc = (up>>2&1)?a[x]:1;
ll ans = 0;
for(int i = 0; i <= ua; ++i){
for(int j = 0; j <= ub; ++j){
for(int k = 0; k <= uc; ++k){
ans = (ans + dfs(x+1,now | Calc(i,j,k),up & Calc2(x,i,j,k))) % MOD;
}
}
}
return f[x][now][up] = ans;
}
void solve(){
memset(f,-1,sizeof(f));
s = ' ' + s;
for(int i = 1; i < s.size(); ++i) a[i] = s[i] - '0';
printf("%lld\n",dfs(1,0,7));
}
int main(){
cin >> s;
solve();
}
CF1710D Recover the Tree
一道比较好的构造题目，我们先需要从小到大去对区间排序，然后就是我们会发现
如果对于一个区间 \([l,r]\)，\(l,r\) 分别在两个连通块区间之内，然后中间有 \(k\) 个连通块，我们的构造方案需要满足两个相邻的连通块之间不能直接相连（\(l,r\) 所在连通块可以直接相连，即使相邻）
所以当 \(k = 1\) 时，显然是无解的。
所以我们让 \(l\) 连向 \(r\) 左边的第一个连通块中的任意位置，\(r\) 连向剩下的其他 \(k - 1\) 个连通块即可
至于连通块的维护？？？并查集即可
#include<bits/stdc++.h>
using namespace std;
const int NN = 2e3 + 8;
char s[NN][NN];
int fa[NN];
void solve(){
int n;
scanf("%d",&n);
for(int i = 1; i <= n; ++i) fa[i] = i;
for(int i = 1; i <= n; ++i) scanf("%s",s[i]+i);
for(int i = 1; i <= n; ++i){
for(int j = i-1; j >= 1; --j)if(s[j][i] == '1' && fa[i] > j){
printf("%d %d\n", j, i);
if(fa[fa[i] - 1] > j)
{
printf("%d %d\n", j, fa[i] - 1);
for(int k = fa[fa[i] - 1] - 1; k > j; --k) if(fa[k] == k) printf("%d %d\n",k,i);
}
for(int k = j; k <= i; ++k) fa[k] = fa[j];
}
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
solve();
}
}