2021牛客OI赛前集训营-提高组（第二场）
链接
vp 的，赛时 \(80+0+100+0\)
T1 不会，写了个分块+ST 表，发现常数还比暴力大。
T2 不会，看题解才会了，想到了经典套路之固定端点瞎选。
T3 萌萌数据结构，提示性挺强的，发现每个点都可以将 2 段序列合并成一段新的，考虑贪心即可，每次合并 2 段最大的序列，考虑 multiset+启发式合并，优秀的 \(O(n\log^2n)\)。
T4 弃了。
赛后：
T1 发现交换没影响，因为如果 2 个位，考虑交换。
若原来贡献为 1，交换后也显然贡献为 1。
若原来贡献为 2，交换后贡献为 0。
若原来贡献为 0，交换后贡献为 2。
发现都对奇偶性没影响，考虑记录下区间 1 的数量即可。
T2
我们可以考虑固定一条线段看看能不能乱选。
考虑 2 个点 \(A(x,y),B(xx,yy)\)。
如何求出线段 \(AB\) 上的整点数量。
记 \(a=|x-xx|,b=|y-yy|\)，答案显然是 \(\gcd(a,b)\)，参考什么莫反的题。
把整一段拍扁到序列上，发现 \(D\) 的限制并不是很好做，但是考虑单位相隔长度一样，即每个点和它的横坐标加 1 的那个点的距离都是一样的。
令 \(dis=dist((0,0),(\dfrac{a}{\gcd(a,b)},\dfrac{b}{\gcd(a,b)}))\)
那么假如选了 0 和第 \(qwq\) 个点，合法当且仅当
\[qwq*dis\ge D,qwq\ge\dfrac{D}{dis} \]令 \(qwq=\lceil\dfrac{D}{dis}\rceil\)
考虑只需要选 \(N-2\) 个点了，因为左右端点都选了。
那么答案为
\[C(gcd(a,b)-1-(qwq-1)*(N-1),N-2) \]\(-(qwq-1)*(N-1)\) 选 \(N\) 个点，间隔 \(N-1\)，每个间隔至少 \(qwq-1\)。
最后考虑乘上答案系数，注意假如是不是水平/竖直线需要 \(\times2\)，因为有序点对。
T1
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int rd() {
char ch=getchar(); int sum=0,f=1;
while(ch>'9'||ch<'0') {
if(ch=='-') f=-1; ch=getchar();
}
while(ch<='9'&&ch>='0') sum=sum*10+ch-'0',ch=getchar();
return sum*f;
}
#define N (int)(2e5+3)
#define M 402
int n,m,Q;
bool gt() {
char ch=getchar();
while(ch!='0'&&ch!='1') ch=getchar();
return ch-'0';
}
struct BBB {
bitsetB[20][M];
int len,bl,id[N],L[M],R[M]; bool a[N];
void init(int lenn) {
len=lenn; bl=min(len,500);
for(int i=1;i<=len;i++) {
a[i]=gt(); id[i]=(i-1)/bl+1;
B[0][id[i]][i]=a[i];
}
for(int i=1;i<=id[len];i++) L[i]=(i-1)*bl+1,R[i]=i*bl; R[id[len]]=len;
for(int i=1;(1ll<&BT) {
// cout<y) return ;
int qwq=log2(y-x+1);
BT|=(B[qwq][x]>>(l-1)); BT|=(B[qwq][y-(1ll<>(l-1));
}
}
}P1,P2;
bitsetr1,r2;
namespace xgf{
int a[N],b[N];
void solve() {
for(int i=1;i<=n;i++) a[i]=gt();
for(int i=1;i<=m;i++) b[i]=gt();
Q=rd();
int l,r,ll,rr;
while(Q--) {
l=rd(); r=rd(); ll=rd(); rr=rd(); int qwq=0;
for(int i=0;i T2
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define mod (int)(1e9+7)
using namespace std;
int rd() {
char ch=getchar(); int sum=0,f=1;
while(ch>'9'||ch<'0') {
if(ch=='-') f=-1; ch=getchar();
}
while(ch<='9'&&ch>='0') sum=sum*10+ch-'0',ch=getchar();
return sum*f;
}
ll lrd() {
char ch=getchar(); ll sum=0,f=1;
while(ch>'9'||ch<'0') {
if(ch=='-') f=-1; ch=getchar();
}
while(ch<='9'&&ch>='0') sum=sum*10+ch-'0',ch=getchar();
return sum*f;
}
ll C[2003][2003];
ll N,W,H,D;
ll fpow(ll x,ll y) {
ll res=1; x%=mod;
while(y) {
if(y&1) res=res*x%mod; y>>=1; x=x*x%mod;
}
return res;
}
ll gcd(ll x,ll y) {
return !y?x:gcd(y,x%y);
}
double dis(ll x,ll y,ll xx,ll yy) {
return sqrt(1.0*(x-xx)*(x-xx)+1.0*(y-yy)*(y-yy));
}
ll CC(ll x,ll y) {
if(x T3
#include
#include
#include
#include
#include
#include
using namespace std;
int rd() {
char ch=getchar(); int sum=0,f=1;
while(ch>'9'||ch<'0') {
if(ch=='-') f=-1; ch=getchar();
}
while(ch<='9'&&ch>='0') sum=sum*10+ch-'0',ch=getchar();
return sum*f;
}
#define N (int)(1e5+5)
struct edge {
int nex,to;
}e[N<<1];
multiset >s[N];
multiset::iterator it;
int head[N],cnt,id[N],n;
void add_edge(int x,int y) {
e[++cnt].nex=head[x]; e[cnt].to=y; head[x]=cnt;
}
void dfs1(int x,int ff) {
for(int i=head[x];i;i=e[i].nex) {
int y=e[i].to; if(y==ff) continue;
dfs1(y,x);
if(s[id[y]].size()>s[id[x]].size()) swap(id[x],id[y]);
for(it=s[id[y]].begin();it!=s[id[y]].end();it++) s[id[x]].insert(*it);
s[id[y]].clear();
}
if(!s[id[x]].size()) s[id[x]].insert(1);
else if(s[id[x]].size()==1) {
it=s[id[x]].begin(); s[id[x]].insert(*it+1); s[id[x]].erase(it);
} else {
int qwq=1; it=s[id[x]].begin(); qwq+=*it; s[id[x]].erase(it); it=s[id[x]].begin(); qwq+=*it; s[id[x]].erase(it);
s[id[x]].insert(qwq);
}
}
void solve() {
n=rd(); cnt=0; memset(head,0,sizeof(head));
for(int i=1;i<=n;i++) {
id[i]=i; s[i].clear();
}
int x,y;
for(int i=1;i