模拟赛
T1
枚举每个点
直接对每个ai%r
再考虑区间减
判断是否有剩余即可
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<bits/stdc++.h>
#define int long long
#define jiaa(a,b) {a+=b;if(a>=MOD) a-=MOD;}
#define jian(a,b) {a-=b;if(a<0) a+=MOD;}
#define lson x<<1
#define rson x<<1|1
using namespace std;
int ksm(int a,int b,int p){if(b==0) return 1;if(b==1) return a%p;int c=ksm(a,b/2,p);c=c*c%p;if(b%2==1) c=c*a%p;return c%p;
}
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
#define lowbit(x) x&(-x)
int a[100005];
const int MAXN=1e5+5;
void modify(int l,int r,int c){for(int i=l;i<=MAXN;i+=lowbit(i)) a[i]+=c;for(int i=r+1;i<=MAXN;i+=lowbit(i)) a[i]-=c;
}
int query(int x){int ans=0;for(int i=x;i;i-=lowbit(i)) ans+=a[i];return ans;
}
signed main()
{freopen("dskfj.in", "r", stdin);freopen("dskfj.out", "w", stdout);int n=read(),k=read(),r=read();for(int i=1;i<=n;i++){int x=read();modify(i,i,x);}for(int i=1;i<=n-k+1;i++){int zh=query(i)%r;if(!zh) continue;int l=i,r=i+k-1;modify(l,r,-zh);}for(int i=1;i<=n;i++){int zh=query(i);if(zh%r!=0){cout<<"No"<<'\n';return 0;}}cout<<"Yes"<<'\n';return 0;
}
T2
树形dp
一棵子树内共四种情况
空、一条链、两条链、一个倒Y
记录倒Y的数量（a）及链的数量（b）
发现3个链自己可以组成三叉
一个倒Y也可组成三叉
一个链和一个倒Y也可组成三叉
先三个链自己配
再配倒Y
于是记录min(a,2)和b%3的值
发现可能会对父亲贡献链和倒Y
因此倒Y要记录min(a,3)
链记录0~4,注意0,3 、1,4不同，区别在于能否对父亲贡献2条链
然后树上背包就行
T3
T4
预处理极小mex区间
变成三维偏序
观察性质
变成二位偏序
贪心模拟二分
1.https://www.luogu.com.cn/problem/AT_kupc2018_k
容易发现不好点一定是独立集（否则有边一定有一个点是好点）
发现K没用，直接变成K=2即可
然后将平均值拆开
check(m)是否可行
等价于b1-m + b2-m + …… + bq-m >=0
变成求权值和最大的点覆盖
（点覆盖就是独立集的补集）
转化成求独立集的最小值
可以dp
dpr表示右边选r这个点的最小独立集
枚举上一个选的点l，计算区间贡献K_l,r
每次从r到r+1时，对1~l-1的区间的K_p,r+1进行一个w_l,r的区间加，同时修改dp_r+1
需要线段树维护区间加，全局min,单点修
2.https://www.luogu.com.cn/problem/P9695
对每个x二分一个左端点l右端点r
数据结构check是否可行（s_a1+s_a2+……+s_ak是否=r-l+1）
3.
考虑贪心
让每个ai尽量大，此基础上让bi尽量大
但不一定优
考虑对ai做前缀减（相当于区间减）
假设减去h
于是我们就有了h次区间加的操作
贪心加区间长的即可
4.https://www.luogu.com.cn/problem/CF405E
对于一棵树从下往上贪心
找到一个父亲节点，使得所有儿子都是叶子
若儿子为偶数，配对消除
否则，剩下的一条边与fa-fa[fa]这条边配对，消除一棵子树
可以自然转化成图
5.https://www.luogu.com.cn/problem/P11189
先进行操作2
最后一定使得ap<=0且ap<=afa才能通过操作1满足要求
于是每个叶子节点的操作次数区间[li,ri]易求
考虑如何快速求父亲的[li,ri]
li就是所有儿子的li的max
ri发现满足单调性，二分check
6.https://www.luogu.com.cn/problem/P13552
容易发现最后进行加操作一定是优的
问题转化成将一堆数划分成k个集合，使得每个集合按位与结果最大
假设有m个数最高位=1
首先有一些性质
二进制下A 1 B 0 C 0
则 (a&b)+c<a+(b&c)
于是，若k>=m+1,则每个高位1单独一个集合，剩余的0划分成k-m个集合
否则，将所有的0按位与进行合并，递归考虑次高位的情况