2024 6 月 杂题
鹅同节快乐。
AT_dwacon5th_prelims_d Square Rotation
题意
- 在无限大的二维平面中有 $N$ 个黑点：$(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)$，剩余的点均为白点，你可以按以下规则进行无限次操作：
- 选择一个边长为 $D$ 的正方形，并将其四个角上的点进行旋转，具体来说选择了一个左下角 $(x,y)$ 的正方形，会按以下顺序旋转：$(x,y)\rightarrow(x+D,y)\rightarrow(x+D,y+D)\rightarrow(x,y+D)\rightarrow(x,y)$
- 你需要通过任意次操作使得平面上切比雪夫距离最远的两黑点的距离最小，并输出这一最小距离。
- $2\le N\le 10^5,1\le D\le 1000$
题解
妙妙题。
乍一看一点思路都没有，考虑手模一下。
容易发现，这个修改方式只限制了每个点 $(x,y)$ 只能移动到 $(x',y')$ 满足 $x'\equiv x\pmod D,y'\equiv y\pmod D$，在满足这个条件的情况下是可以随便动的。具体构造考虑先把点移到充分远的地方，然后一个一个挪过来。
那么我们就只关心每个同余类有多少个黑点了。
容易发现这是一个最小化最大值的问题，考虑二分答案。那么思考如何 check。
首先切比雪夫距离最小可以认为是用一个正方形把所有点框住，考虑枚举正方形的左下角。
容易发现，同一个同余类在正方形中的出现次数只有三种（设正方形边长为 $L$，那么分别是 $\left\lfloor\frac{(L+1)}{D}\right\rfloor^2,(\left\lfloor\frac{(L+1)}{D}\right\rfloor+1)^2,\left\lfloor\frac{(L+1)}{D}\right\rfloor\times (\left\lfloor\frac{(L+1)}{D}\right\rfloor+1)$），并且三种分别是四个连续的矩形。于是容易想到用前缀和维护矩形内满足条件的同余类个数。
于是做完了，复杂度 $O(N+D^2\log V)$，其中 $V$ 是值域。这个已经能过了。
有没有更强力的做法？
考虑 $(\left\lfloor\frac{(L+1)}{D}\right\rfloor+1)^2$ 必须大于等于出现最多的同余类出现次数，而 $\left\lfloor\frac{(L+1)}{D}\right\rfloor^2$ 必定能小于等于出现最多的同余类出现次数，那么不妨设正方形边长为 $aD+b$，其中 $0\le b< D,a=\left\lceil\sqrt{mx}\right\rceil-1$，其中 $mx$ 是出现次数最多的同余类出现次数。
然后容易发现那个前缀和就不会变了，只是每次找的四个矩形会变。于是可以考虑先把 $b$ 赋为 $D-1$，枚举左下角然后每次尝试缩小 $b$，复杂度就缩到了 $O(N+D^2)$（注意到 $b$ 只会缩 $D$ 次，小于 $O(D^2)$）。
参考代码
$O(N+D^2\log V)$
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1005,inf=0x3f3f3f3f;
int n,d,cnt[N<<1][N<<1];
int sum[3][N<<1][N<<1];
int calc(int x1,int y1,int x2,int y2,int p){
if(x2<x1||y2<y1) return 0;
return sum[p][x2][y2]-(x1?sum[p][x1-1][y2]:0)-(y1?sum[p][x2][y1-1]:0)+(x1&&y1?sum[p][x1-1][y1-1]:0);
}
bool chk(int mm){
int p=(mm+1)/d;
forup(i,0,d*2-1){
forup(j,0,d*2-1){
sum[0][i][j]=(1ll*(p+1)*(p+1)>=cnt[i][j]);
sum[1][i][j]=(1ll*p*(p+1)>=cnt[i][j]);
sum[2][i][j]=(1ll*p*p>=cnt[i][j]);
forup(k,0,2){
if(i) sum[k][i][j]+=sum[k][i-1][j];
if(j) sum[k][i][j]+=sum[k][i][j-1];
if(i&&j) sum[k][i][j]-=sum[k][i-1][j-1];
}
}
}
forup(i,0,d*2-1){
forup(j,0,d*2-1){
msg("%d ",sum[2][i][j]);
}msg("|\n");
}
int t=(mm+1)%d;
msg("%d %d||\n",t,d);
forup(x,0,d-1){
forup(y,0,d-1){
msg("%d %d %d||\n",x,y,calc(x,y,x+t-1,y+t-1,0)+calc(x+t,y,x+d-1,y+t-1,1)+calc(x,y+t,x+t-1,y+d-1,1)+calc(x+t,y+t,x+d-1,y+d-1,2));
if(calc(x,y,x+t-1,y+t-1,0)+calc(x+t,y,x+d-1,y+t-1,1)+calc(x,y+t,x+t-1,y+d-1,1)+calc(x+t,y+t,x+d-1,y+d-1,2)==d*d) return true;
}
}
return false;
}
signed main(){
n=read();d=read();
forup(i,1,n){
int x=read(),y=read();
++cnt[x%d][y%d];
}
forup(i,0,d-1){
forup(j,0,d-1){
cnt[i+d][j]=cnt[i][j+d]=cnt[i+d][j+d]=cnt[i][j];
}
}
int ll=1,rr=1e9,mm;
while(ll<rr){
msg("%d %d====\n",ll,rr);
mm=(ll+rr)>>1;
if(chk(mm)) rr=mm;
else ll=mm+1;
}
printf("%d\n",ll);
}
$O(N+D^2)$
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1005,inf=0x3f3f3f3f;
int n,d,cnt[N<<1][N<<1];
int sum[3][N<<1][N<<1];
int calc(int x1,int y1,int x2,int y2,int p){
if(x2<x1||y2<y1) return 0;
return sum[p][x2][y2]-(x1?sum[p][x1-1][y2]:0)-(y1?sum[p][x2][y1-1]:0)+(x1&&y1?sum[p][x1-1][y1-1]:0);
}
bool chk(int x,int y,int t){
return calc(x,y,x+t-1,y+t-1,0)+calc(x+t,y,x+d-1,y+t-1,1)+calc(x,y+t,x+t-1,y+d-1,1)+calc(x+t,y+t,x+d-1,y+d-1,2)==d*d;
}
signed main(){
n=read();d=read();
forup(i,1,n){
int x=read(),y=read();
++cnt[x%d][y%d];
}
int mx=0;
forup(i,0,d-1){
forup(j,0,d-1){
mx=max(mx,cnt[i][j]);
cnt[i+d][j]=cnt[i][j+d]=cnt[i+d][j+d]=cnt[i][j];
}
}
int a=ceil(sqrt(mx))-1,b=d-1;
forup(i,0,d*2-1){
forup(j,0,d*2-1){
sum[0][i][j]=(1ll*(a+1)*(a+1)>=cnt[i][j]);
sum[1][i][j]=(1ll*a*(a+1)>=cnt[i][j]);
sum[2][i][j]=(1ll*a*a>=cnt[i][j]);
forup(k,0,2){
if(i) sum[k][i][j]+=sum[k][i-1][j];
if(j) sum[k][i][j]+=sum[k][i][j-1];
if(i&&j) sum[k][i][j]-=sum[k][i-1][j-1];
}
}
}
forup(x,0,d-1){
forup(y,0,d-1){
while(b>0&&chk(x,y,b)) --b;
}
}
printf("%d\n",a*d+b);
}
AT_dwacon6th_prelims_e Span Covering
图源模拟赛题解。
题意
- 你有一个区间 $[0,X)$，还有 $n$ 个黑色纸条，第 $i$ 个纸条长度为 $l_i$。
- 一张纸条可以覆盖一段 $[j,j+l_i)$ 的区间，纸条间可以重合。问有多少把所有纸条放完的方案能覆盖整个区间。
- $1\le n\le 100,1\le X\le 500$，对 $10^9+7$ 取模。
题解
貌似是套路题啊，赛时好多人都切了。
首先这种放若干个区间的可以考虑从长的开始放。这样就不会有后面的把前面的完全覆盖掉（恰好等长不算）的情况了。
那么任意一个时刻，显然纸条都会连成若干个连续块。
因为最后一定是连成一坨的，我们其实可以不关心每个纸条在序列上的具体位置，只用关心每个连续块内纸条的相对位置以及连续块的顺序。
那么容易想到一个 DP，设 $f_{i,j,k}$ 表示考虑前 $i$ 个（从大到小排序）纸条，形成了 $j$ 个连续块，总长度为 $k$ 的方案数。
然后分四种情况转移：
- 完全放在之前一块内：每一块都有 $l_i-1$ 个位置不能放，于是 $f_{i,j,k}\gets f_{i-1,j,k}\times (k-j(l_i-1))$。
- 与之前任何一块都不相交（挨着也算相交）：有 $j$ 个空格可以塞，于是 $f_{i,j,k}\gets f_{i-1,j-1,k-l_i}\times j$
- 与之前某一块相交：先枚举将那个块延长了多少，每一块可以向左或向右延长，于是 $f_{i,j,k}\gets \sum_{t=1}^{l_i}f_{i-1,j,k-t}\times 2(j-1)$。
- 将两块连在一起：还是枚举连起来两个块的距离，然后容易发现对于距离为 $t$，有 $l_i-t+1$ 种不同的放法，于是 $f_{i,j,k}\gets \sum_{t=1}^{l_i}f_{i-1,j+1,k-t}\times (j-1)(l_i-t+1)$。
然后容易发现对于 $l_i$，最多有 $\left\lfloor\frac{x}{l_i}\right\rfloor$ 段，原因是之前每一段长度都大于等于 $l_i$，DP 第一维有 $n$ 种，第二维有 $\left\lfloor\frac{x}{l_i}\right\rfloor$ 种，第三维有 $x$ 种，转移复杂度为 $l_i$，于是总复杂度 $O(nX^2)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=505,inf=0x3f3f3f3f,mod=1e9+7;
int n,m,l[N],dp[2][N][N];
signed main(){
n=read();m=read();
forup(i,1,n){
l[i]=read();
}
sort(l+1,l+n+1,greater<int>());
dp[1][1][l[1]]=1;
forup(i,2,n){
int p=i&1,q=p^1;
forup(j,1,m/l[i-1]+1){
forup(k,1,m){
(dp[p][j][k]+=1ll*dp[q][j][k]*(k-(l[i]-1)*j)%mod)%=mod;
if(k+l[i]<=m) (dp[p][j+1][k+l[i]]+=1ll*dp[q][j][k]*(j+1)%mod)%=mod;
forup(t,1,l[i]){
if(k+t>m) break;
(dp[p][j][k+t]+=2ll*dp[q][j][k]*j%mod)%=mod;
(dp[p][j-1][k+t]+=1ll*dp[q][j][k]*(j-1)%mod*(l[i]-t+1)%mod)%=mod;
}
dp[q][j][k]=0;
}
}
}
printf("%d\n",dp[n&1][1][m]);
}
模拟赛神秘题目 1
题意
- 有一个机器人，要执行 $n$ 条指令，每条指令形如向左/右拐弯后，前进若干步。
- 现在给你每条指令的限制，每个限制形如 $(D,L,R)$，其中 $D$ 是一个字符表示拐弯的方向（'L' 表示左拐，'R' 表示右拐，'?' 表示没有限制），$[L,R]$ 为这一步长度的范围。
- 初始在 $(0,0)$ 问能否在 $n$ 步后恰好走到 $(X,Y)$。
- $1\le n\le 50$，保证无论怎么走坐标都不会超过 $32$ 位整数范围，$|X|,|Y|\le 10^9$
题解
这种题也能做的？（小豆泥大小眼 .png）。
观察数据范围，容易想到大概是 $O(n^5)$ 附近复杂度的暴力算法或者 $O(2^{\frac{n}{2}})$ meet-in-middle。
$O(n^5)$ 不是容易想的，考虑 meet-in-middle。
容易发现，在确定每个操作的方向后，终点横坐标只和下标为偶数的操作有关，纵坐标只和下标为奇数的操作有关。考虑能不能把这两部分分开考虑。因为确定下标的奇偶就能确定横纵方向，所以下文讨论方向只讨论正负。
在确定每个操作的方向后，容易得到终点的横坐标是一段区间，纵坐标也是一段区间。两边分别找这段区间里面有没有 $(X,Y)$ 即可。考虑如何确定每个 ? 的方向。
容易发现，若一个 ? 后面也是 ?，那么无论它把方向变成正的还是负的并不影响下一步方向的正负。但是若一个 ? 后面是一个字母，这个 ? 就会影响后面连续一块字符的正负了。容易想到把这两种分开。第一种 ? 里面奇偶下标是完全独立的，奇下标只会影响纵坐标，偶下标只会影响横坐标。第二种相当于一个 ? 既影响了横坐标，又影响了纵坐标。设第二种问号有 $a$ 个，第一种里面的奇下标有 $b$ 个，偶下标有 $c$ 个。
那么先 $2^a$ 枚举第二种 ?，显然有 $a\le \frac{n}{2}$，然后再分别 $2^b,2^c$ 枚举终点横纵坐标区间（可以先预处理每一个 bitmask 能得到的最大值和最小值，因为剩下的横纵坐标是互不干扰的所以可以分开枚举），如果包含 $(X,Y)$ 就输出答案。复杂度 $O(2^a(2^b+2^c))$。
因为 $\max(b,c)\le n-2a$，于是这个复杂度是 $O(2^{\frac{n}{2}})$ 的。注意预处理复杂度不要写假了。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=55,inf=0x3f3f3f3f;
int n,X,Y;
struct ope{
int dir,l,r;
}s[N];
struct blk{
int st,len,x1,x2,y1,y2;
};
vector<blk> seq;
vector<int> pp[2];
int oL[1<<25],oR[1<<25],eL[1<<25],eR[1<<25];
int sxL[1<<25],sxR[1<<25],syL[1<<25],syR[1<<25];
bool dd[N];
void gans(int m1,int mo,int me,int x,int y){
int sz=seq.size(),so=pp[1].size(),se=pp[0].size();
printf("%d\n",n);
forup(i,0,sz-1){
dd[seq[i].st]=((m1>>i)&1);
if(!dd[seq[i].st]){
forup(j,seq[i].st+1,seq[i].st+seq[i].len-1){
dd[j]^=1;
}
}
}
forup(i,0,so-1){
dd[pp[1][i]]=((mo>>i)&1);
}
forup(i,0,se-1){
dd[pp[0][i]]=((me>>i)&1);
}
forup(i,1,n){
// msg("%d ",dd[i]);
if(!(i&1)){
if(dd[i]^dd[i-1]){
printf("L ");
}else{
printf("R ");
}
if(x!=X){
if(s[i].r-s[i].l<=X-x){
if(dd[i]) printf("%d\n",s[i].r);
else printf("%d\n",s[i].l);
x+=s[i].r-s[i].l;
}else{
if(dd[i]) printf("%d\n",s[i].l+X-x);
else printf("%d\n",s[i].r-X+x);
x=X;
}
}else{
if(dd[i]) printf("%d\n",s[i].l);
else printf("%d\n",s[i].r);
}
}else{
if(dd[i]^dd[i-1]){
printf("R ");
}else{
printf("L ");
}
if(y!=Y){
if(s[i].r-s[i].l<=Y-y){
if(dd[i]) printf("%d\n",s[i].r);
else printf("%d\n",s[i].l);
y+=s[i].r-s[i].l;
}else{
if(dd[i]) printf("%d\n",s[i].l+Y-y);
else printf("%d\n",s[i].r-Y+y);
y=Y;
}
}else{
if(dd[i]) printf("%d\n",s[i].l);
else printf("%d\n",s[i].r);
}
}
}
}
int sx1,sx2,sy1,sy2;
signed main(){
n=read();X=read();Y=read();
dd[0]=1;
forup(i,1,n){
char a;scanf(" %1c",&a);
if(a=='L') s[i].dir=1;
else if(a=='R') s[i].dir=-1;
else s[i].dir=0;
s[i].l=read();s[i].r=read();
}
int i=1;
if(s[1].dir!=0){
int dir=1;
while(s[i].dir){
if(s[i].dir==1){
if(!(i&1)){
dir^=1;
}
}else if(s[i].dir==-1){
if(i&1){
dir^=1;
}
}
dd[i]=dir;
if(!(i&1)){
if(dir){
sx1+=s[i].l;
sx2+=s[i].r;
}else{
sx1-=s[i].r;
sx2-=s[i].l;
}
}else{
if(dir){
sy1+=s[i].l;
sy2+=s[i].r;
}else{
sy1-=s[i].r;
sy2-=s[i].l;
}
}
++i;
}
}
while(i<=n){
if(s[i].dir==0&&s[i+1].dir==0){
pp[i&1].push_back(i);
++i;
}else{
blk nw;
nw.st=i;
nw.x1=nw.y1=nw.x2=nw.y2=0;
int dir=1;
do{
if(s[i].dir==1){
if(!(i&1)){
dir^=1;
}
}else if(s[i].dir==-1){
if(i&1){
dir^=1;
}
}
dd[i]=dir;
if(!(i&1)){
if(dir){
nw.x1+=s[i].l;
nw.x2+=s[i].r;
}else{
nw.x1-=s[i].r;
nw.x2-=s[i].l;
}
}else{
if(dir){
nw.y1+=s[i].l;
nw.y2+=s[i].r;
}else{
nw.y1-=s[i].r;
nw.y2-=s[i].l;
}
}
++i;
}while(s[i].dir!=0);
nw.len=i-nw.st;
seq.push_back(nw);
}
}
int sz=seq.size(),so=pp[1].size(),se=pp[0].size();
forup(i,0,so-1){
oL[0]-=s[pp[1][i]].r;
oR[0]-=s[pp[1][i]].l;
}
forup(i,1,(1<<so)-1){
int lb=(i&-i),t=31^__builtin_clz(lb);
oL[i]=oL[i-lb]+s[pp[1][t]].l+s[pp[1][t]].r;
oR[i]=oR[i-lb]+s[pp[1][t]].l+s[pp[1][t]].r;
}
forup(i,0,se-1){
eL[0]-=s[pp[0][i]].r;
eR[0]-=s[pp[0][i]].l;
}
forup(i,1,(1<<se)-1){
int lb=(i&-i),t=31^__builtin_clz(lb);
eL[i]=eL[i-lb]+s[pp[0][t]].l+s[pp[0][t]].r;
eR[i]=eR[i-lb]+s[pp[0][t]].l+s[pp[0][t]].r;
}
forup(i,0,sz-1){
sxL[0]-=seq[i].x2;
sxR[0]-=seq[i].x1;
syL[0]-=seq[i].y2;
syR[0]-=seq[i].y1;
}
forup(i,1,(1<<sz)-1){
int lb=(i&-i),t=31^__builtin_clz(lb);
sxL[i]=sxL[i-lb]+seq[t].x1+seq[t].x2;
sxR[i]=sxR[i-lb]+seq[t].x1+seq[t].x2;
syL[i]=syL[i-lb]+seq[t].y1+seq[t].y2;
syR[i]=syR[i-lb]+seq[t].y1+seq[t].y2;
}
forup(i,0,(1<<sz)-1){
int msko=-1,mske=-1;
int xl=sx1+sxL[i],xr=sx2+sxR[i],yl=sy1+syL[i],yr=sy2+syR[i];
forup(j,0,(1<<se)-1){
if(xl+eL[j]<=X&&X<=xr+eR[j]){
mske=j;
xl+=eL[j];
break;
}
}
if(mske==-1) continue;
forup(j,0,(1<<so)-1){
if(yl+oL[j]<=Y&&Y<=yr+oR[j]){
msko=j;
yl+=oL[j];
break;
}
}
if(msko==-1) continue;
gans(i,msko,mske,xl,yl);
return 0;
}
puts("-1");
}
骰子（模拟赛题目）
以后还是把标题打出来方便找。
题意
- 用一个长度为 $n$ 的正整数序列 $D$ 代表一个 $n$ 面骰，即其中每个数等概率投出。
- 现在有一种游戏，双方各投一次骰子，若数字不同则更大者获得 $1$ 分，否则两边各获得 $0.5$ 分。
- 令 $S(D_1,D_2)$ 表示用 $D_1$ 和 $D_2$ 比赛时，$D_1$ 的期望得分。若 $S(D_1,D_2)\ge 0.5$ 则称 $D_1$ 对 $D_2$ 有优势。
- 现在给你两个骰子 $A,B$，面数分别为 $n,m$，你需要先找出其中有优势的那个（保证 $S(A,B)\ne 0.5$）。钦定 $A$ 表示其中有优势的那个。找到满足 $S(D_3,A)\ge 0.5$ 的 $D_3$ 中 $S(D_3,B)$ 的最小值。以及满足 $S(D_4,A)\le 0.5$ 的 $D_4$ 中 $S(D_4,B)$ 最大的。
- $1\le n,m\le 10^5$，所有数据在 $32$ 位整数内。
题解
神秘趣味题。
首先比较两个骰子是简单的，就不多赘述了。
考虑平局要算分，赢了要算分，输了不算分是不符合直觉的。为了更符合直觉不妨进行一些转化：把分数减去 $0.5$ 再乘二。就变成了赢了记 $1$ 分输了扣一分平局不算分。最后输出答案的时候变换一下就行了。
只考虑第一问（第二问同理），容易想到二分答案。那么考虑如何判断答案能否小于等于 $mid$。
首先显然的，可以对骰面进行离散化（注意可能选到原有的数 $\pm 1$），那么考虑每个数的贡献。
考虑 $x$ 对 $S(D_3,A)$ 的贡献。容易发现就是 $A$ 中严格小于 $x$ 的数量减去严格大于 $x$ 的数量。设这个数为 $a_x$。同理有 $b_x$。
设 $D_3$ 有 $p$ 面。容易发现 $S(D_3,A)=\frac{\sum a_x}{p\cdot n}\ge 0$，$S(D_3,B)=\frac{\sum b_x}{p\cdot m}\le mid$，考虑 $01$ 分数规划套路，易得 $\sum b_x-mid\cdot m\le 0$，且 $\sum a_x\ge 0$。
首先若存在 $a_x\ge 0,b_x-mid\cdot m\le 0$，那么直接选它就可以了。
但对于其它情况要 DP 吗？并不需要，因为你可以选无限个，所以考虑选两个最优的把它们拼起来即可。容易想到选 $a_x>0,b_x-m\cdot mid>0$ 的里面 $\frac{b_x-m\cdot mid}{a_x}$ 最小的以及负的里面最大的。由于 $a$ 是整数直接取到两个 $a$ 的 $\mathrm{lcm}$ 显然不劣。
然后就做完了，复杂度 $O(n\log V)$（假设 $n,m$ 同阶），其中 $V=eps^{-1}$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using ld=long double;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f;
const ld eps=1e-9;
int n,m,V;
vector<int> a,b;
vector<int> lsh;
int suma[N*3],sumb[N*3];
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
bool chk1(ld mm){
pair<int,ld> am=mkp(0,0),bm=mkp(0,0);
bool f1=false,f2=false;
forup(i,1,V){
int aa=suma[i-1]-n+suma[i];
ld bb=-mm*m+sumb[i-1]-m+sumb[i];
if(aa>=0&&bb<=0) return true;
if(aa==0||(aa<0&&bb>0)) continue;
if(aa>0){
if(!f1||bb*am.fi<am.se*aa) am=mkp(aa,bb),f1=true;
}else{
if(!f2||-bb*bm.fi>bm.se*-aa) bm=mkp(-aa,-bb),f2=true;
}
}
if(!f1||!f2) return false;
int gg=gcd(am.fi,bm.fi);
ld res=am.se*(bm.fi/gg)-bm.se*(am.fi/gg);
return res<=0;
}
bool chk2(ld mm){
pair<int,ld> am=mkp(0,0),bm=mkp(0,0);
bool f1=false,f2=false;
forup(i,1,V){
int bb=sumb[i-1]-m+sumb[i];
ld aa=-mm*n+suma[i-1]-n+suma[i];
if(aa>=0&&bb<=0) return true;
if(bb==0||(aa<0&&bb>0)) continue;
if(bb>=0){
if(!f1||aa*am.fi>am.se*bb) am=mkp(bb,aa),f1=true;
}else{
if(!f2||-aa*bm.fi<bm.se*-bb) bm=mkp(-bb,-aa),f2=true;
}
}
if(!f1||!f2) return false;
int gg=gcd(am.fi,bm.fi);
ld res=am.se*(bm.fi/gg)-bm.se*(am.fi/gg);
return res>=0;
}
signed main(){
n=read();
a.resize(n);
forup(i,0,n-1){
a[i]=read();
lsh.push_back(a[i]);
if(a[i]>1) lsh.push_back(a[i]-1);
lsh.push_back(a[i]+1);
}
m=read();
b.resize(m);
forup(i,0,m-1){
b[i]=read();
lsh.push_back(b[i]);
if(b[i]>1) lsh.push_back(b[i]-1);
lsh.push_back(b[i]+1);
}
sort(lsh.begin(),lsh.end());
lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
V=lsh.size();
sort(a.begin(),a.end());sort(b.begin(),b.end());
int pb=0,c1=0,c2=0;
i64 sum=0;
forup(i,0,n-1){
if(i&&a[i]!=a[i-1]){
c1+=c2;c2=0;
}
while(pb<m&&b[pb]<a[i]){
++c1;++pb;
}
while(pb<m&&b[pb]==a[i]){
++c2;++pb;
}
sum+=2*c1+c2;
}
if(sum<1ll*n*m) swap(a,b),swap(n,m);
for(auto &i:a){
i=lower_bound(lsh.begin(),lsh.end(),i)-lsh.begin()+1;
++suma[i];
}
for(auto &i:b){
i=lower_bound(lsh.begin(),lsh.end(),i)-lsh.begin()+1;
++sumb[i];
}
forup(i,1,V){
suma[i]+=suma[i-1];sumb[i]+=sumb[i-1];
}
ld ll=-1,rr=1,mm;
forup(i,1,25){
mm=(ll+rr)/2;
if(chk1(mm)) rr=mm;
else ll=mm;
}
printf("%.9Lf ",ll/2+0.5);
ll=-1,rr=1;
forup(i,1,25){
mm=(ll+rr)/2;
if(chk2(mm)) ll=mm;
else rr=mm;
}
printf("%.9Lf",ll/2+0.5);
}
CF1693E Outermost Maximums
题意
- 你有一个长度为 $n+2$ 的序列 $a$，其中 $a_1=a_{n+1}=0$，其余元素均给定。
- 你可以按任何顺序进行以下操作任意次：
- 找到序列中的第一个最大值，把它变成它之前的前缀最大值。
- 找到序列中的最后一个最大值，把它变成它之后的后缀最大值。
- 问把 $a$ 变成全 $0$ 序列最少需要操作多少次。
题解
水黑。
考虑计算每个点需要操作多少次，容易想到一个贪心：每一次对 $a_i$ 的操作都尽可能把 $a_i$ 变得更小。显然正确，因为将同一个位置的一个更小的数变成 $0$ 需要的次数显然不多于一个更大的数。
考虑怎么做，一个简单做法是从大到小扫值域，然后用线段树维护前缀/后缀最大值再操作，也是能对的。复杂度 $O(n\log n)$。
但是有一个更好写的做法。
仍然考虑从大到小扫，显然刚碰到某个数 $x$ 的时候是不知道它要取操作 $1$ 还是 $2$，那么把它标记为待定。容易发现，当扫第一次到一个更小的数 $y$ 时，若它最左边的点为 $L$，最右边为 $R$，$R$ 右边的的全取操作 $2$（右边的比 $y$ 还小），$L$ 左边的全取操作 $1$（同理），中间的取操作 $1,2$ 都会变成 $y$，那么它们又变成待定的了。容易发现任意时刻被标记为操作 $1$，操作 $2$ 的待定的必然是三段连续的区间。考虑维护中间待定的区间，用树状数组维护每次把多少个数变成 $y$ 了即可（分两种情况，待定区间和 $[L,R]$ 有/无交）。注意变成 $y$ 的数全都会变成待定的，实现时需注意。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=2e5+5,inf=0x3f3f3f3f;
i64 n,a[N],res;
struct BIT{
i64 c[N];
void upd(i64 x,i64 k){for(;x<=n;x+=x&-x)c[x]+=k;}
i64 sum(i64 x){i64 res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
i64 qurey(i64 l,i64 r){return sum(r)-sum(l-1);}
}mt;
vector<i64> seq[N];
signed main(){
n=read();
res=0;
forup(i,1,n){
a[i]=read();
if(a[i]) ++res;
seq[a[i]].push_back(i);
}
i64 l=0,r=0;
fordown(i,n,1){
if(seq[i].empty()) continue;
i64 L=seq[i][0],R=seq[i].back();
res+=mt.qurey(L+1,R-1);
if(L>r){
res+=mt.qurey(r+1,L-1);
l=r+1;r=R;
}else if(R<l){
res+=mt.qurey(R+1,l-1);
r=l-1;l=L;
}else{
l=L;r=R;
}
for(auto j:seq[i]) mt.upd(j,1);
}
printf("%lld\n",res);
}
P4899 [IOI2018] werewolf 狼人
题意
- 有一张 $n$ 个点 $m$ 条边的无向连通图，其中每个点的序号就是它的权值。
- 有 $q$ 个询问，每个询问问你从 $E$ 出发只走权值小于等于 $R$ 的点和从 $S$ 出发只走权值大于等于 $L$ 的点（保证 $E\le R,L\le S,L\le R$）所得到的两点集是否有交。
- $1\le n\le 2\times 10^5,n-1\le m\le 4\times 10^5$，注意数据下标从 $0$ 开始（我代码里全部 $+1$ 了）。
题解
唐，写了 90min，其中想了 1h，其中有 50min 在思考怎么写码量最小（简而言之就是目光呆滞，玩维玩的）。
首先容易发现能试做每个时间加入一个点，然后看从小到大加入的 $R$ 时刻 $E$ 所在连通块与从大到小加入 $L$ 时刻 $S$ 所在连通块是否有交。
容易想到广义 Kruskal 重构树（从小到大得到 $T_1$，从大到小得到 $T_2$），对 $T_2$ 求 dfs 序，每次询问就是先倍增跳到最高的能到的位置，然后查 $T_1$ 的对应子树有没有 $T_2$ 的一个 dfn 区间中的任意点。
然后方法就多了，在线可以主席树或者线段树的可持久化合并，离线可以 DSU on tree 或者启发式合并或者线段树合并或者扫描线。我写的线段树合并。
复杂度 $O(n\log n)$（容易发现线段树合并总复杂度 $O(n\log n)$，然后每次查询是倍增跳 $+$ 线段树区间查，为 $O(\log n)$）。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,m,q,ans[N];
vector<int> e[N];
struct query{
int s,e,l,r;
}s[N];
vector<int> qu[N];
vector<int> son[2][N];
int fa[N],rt[2];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
void Merge(int u,int v,int type){
u=getfa(u);v=getfa(v);
if(u==v) return;
son[type][v].push_back(u);
fa[u]=v;
}
int f[19][N];
void dfs1(int x){
forup(i,1,18){
f[i][x]=f[i-1][f[i-1][x]];
}
for(auto i:son[0][x]){
f[0][i]=x;
dfs1(i);
}
}
int dfn[N],Tm,sz[N];
int f2[19][N];
void dfs2(int x){
dfn[x]=++Tm;sz[x]=1;
forup(i,1,18){
f2[i][x]=f2[i-1][f2[i-1][x]];
}
for(auto i:son[1][x]){
f2[0][i]=x;
dfs2(i);
sz[x]+=sz[i];
}
}
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,ls[id]
#define rson mid+1,r,rs[id]
int ls[N<<5],rs[N<<5],cnt[N<<5],cntn,root[N];
void Update(int P,int l,int r,int &id){
if(!id) id=++cntn;
++cnt[id];
if(l==r) return;
if(P<=mid) Update(P,lson);
else Update(P,rson);
}
void Merge(int l,int r,int &id,int v){
if(!id||!v) return id|=v,void();
cnt[id]+=cnt[v];
if(l==r) return;
Merge(lson,ls[v]);Merge(rson,rs[v]);
}
int Query(int L,int R,int l,int r,int id){
if(!id) return 0;
if(L<=l&&r<=R){
return cnt[id];
}
int res=0;
if(L<=mid) res+=Query(L,R,lson);
if(mid< R) res+=Query(L,R,rson);
return res;
}
}mt;
void dfs3(int x){
mt.Update(dfn[x],1,n,mt.root[x]);
for(auto i:son[0][x]){
dfs3(i);
mt.Merge(1,n,mt.root[x],mt.root[i]);
}
for(auto i:qu[x]){
ans[i]=bool(mt.Query(dfn[s[i].e],dfn[s[i].e]+sz[s[i].e]-1,1,n,mt.root[x]));
}
}
signed main(){
n=read();m=read();q=read();
forup(i,1,m){
int u=read()+1,v=read()+1;
e[u].push_back(v);
e[v].push_back(u);
}
forup(i,1,n) fa[i]=i;
forup(i,1,n){
for(auto j:e[i]){
if(j<i){
Merge(j,i,0);
}
}
}
rt[0]=getfa(1);
dfs1(rt[0]);
forup(i,1,n) fa[i]=i;
fordown(i,n,1){
for(auto j:e[i]){
if(j>i){
Merge(j,i,1);
}
}
}
rt[1]=getfa(1);
dfs2(rt[1]);
forup(i,1,q){
s[i].e=read();s[i].s=read();s[i].l=read();s[i].r=read();
++s[i].e;++s[i].s;++s[i].l;++s[i].r;
int x=s[i].s;
fordown(j,18,0){
if(f[j][x]&&f[j][x]<=s[i].r) x=f[j][x];
}
qu[x].push_back(i);
x=s[i].e;
fordown(j,18,0){
if(f2[j][x]&&f2[j][x]>=s[i].l) x=f2[j][x];
}
s[i].e=x;
}
dfs3(rt[0]);
forup(i,1,q){
printf("%d\n",ans[i]);
}
}
模拟赛神秘题目【0622A组】数据结构
赛时糖丸了。
题意
- 有一张坐标轴，上面有 $n$ 红点与 $n$ 个蓝点，其中红点横坐标均严格小于 $0$，蓝点横坐标均严格大于 $0$。每个点有点权 $w_i$
- 有 $m$ 个询问，每个询问形如 $L,R$，求一个点对 $i,j$ 其中 $i$ 是红点，$j$ 是蓝点，满足：
- $y_i<y_j$
- $(x_i > L\land x_j < R)\lor(x_i < L\land x_j > R)$
- 求 $w_i+w_j$ 的最大值。
- $1\le n\le 10^5,1\le q \le 5\times 10^5$，其余数据在 $[-10^9,10^9]$ 之内，保证所有横坐标与 $L,R$ 两两不同，所有纵坐标两两不同
题解
显然可以先离散化。
首先有两个限制就很不好搞，考虑消去一个。可以将 $y_i<y_j$ 这个限制对纵坐标分治消去。
那么每层就是把左边的红点和右边的蓝点取出来配至多 $n^2$ 对，这样第二个限制就能简单二维数点做了。
容易发现分治的每一层中每一对可能成为答案的要么左边是对应的最大值，要么右边是对应的最大值。
首先对于一个询问，钦定答案在这一层分治中产生。那么根据 $L$ 把左边的红点分成两个集合 $L_1,L_2$，表示横坐标小于 $L$ 的点集和大于 $L$ 的。同理有 $R_1,R_2$。
容易发现答案要么是 $L_1,R_2$ 中各选一个，要么是 $L_2,R_1$ 中各选一个。假如都在 $1$（或者都在 $2$）里面显然两种都能取到其中一边的最大值。假如一个在 $1$ 里一个在 $2$ 里那么取两个最大值的显然比另一个优。
因此我们就只需要保留 $O(n\log n)$ 个点对了。加上二维数点复杂度 $O(n\log^2 n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,M=5e5+5,inf=0x3f3f3f3f;
int n,m,ans[M];
struct Node{
int x,y,w;
}s[N],seq[N];
vector<int> lshx,lshy;
struct query{
int l,r,pos,val;
}q[N*20+M];
int cntq=0;
void solve(int l,int r){
if(l==r) return;
int mid=(l+r)>>1;
solve(l,mid);solve(mid+1,r);
int mx=-1;
forup(i,l,mid) if(seq[i].x&&(mx==-1||seq[i].w>seq[mx].w)) mx=i;
if(~mx) forup(i,mid+1,r) if(!seq[i].x) q[++cntq]=query{seq[mx].y,seq[i].y,0,seq[mx].w+seq[i].w};
mx=-1;
forup(i,mid+1,r) if(!seq[i].x&&(mx==-1||seq[i].w>seq[mx].w)) mx=i;
if(~mx) forup(i,l,mid) if(seq[i].x) q[++cntq]=query{seq[i].y,seq[mx].y,0,seq[mx].w+seq[i].w};
}
struct BIT{
int c[N<<1];
void init(){mem(c,0);}
void upd(int x,int k){for(;x<=n*2;x+=x&-x)c[x]=max(c[x],k);}
int sum(int x){int res=0;for(;x>0;x-=x&-x)res=max(res,c[x]);return res;}
}mt;
signed main(){
n=read();
forup(i,1,n){
s[i].x=read();s[i].y=read();s[i].w=read();
lshx.push_back(s[i].x);
lshy.push_back(s[i].y);
}
forup(i,n+1,n*2){
s[i].x=read();s[i].y=read();s[i].w=read();
lshx.push_back(s[i].x);
lshy.push_back(s[i].y);
}
sort(lshx.begin(),lshx.end());
sort(lshy.begin(),lshy.end());
lshx.erase(unique(lshx.begin(),lshx.end()),lshx.end());
lshy.erase(unique(lshy.begin(),lshy.end()),lshy.end());
forup(i,1,n*2){
int x=lower_bound(lshx.begin(),lshx.end(),s[i].x)-lshx.begin()+1,
y=lower_bound(lshy.begin(),lshy.end(),s[i].y)-lshy.begin()+1;
seq[y]=Node{(i<=n),x,s[i].w};
}
solve(1,n*2);
m=read();
forup(i,1,m){
int l=read(),r=read();
l=lower_bound(lshx.begin(),lshx.end(),l)-lshx.begin()+1;
r=upper_bound(lshx.begin(),lshx.end(),r)-lshx.begin();
q[++cntq]=query{l,r,i,0};
}
sort(q+1,q+cntq+1,[&](query a,query b){
if(a.l!=b.l) return a.l<b.l;
return a.r<b.r;
});
mt.init();
forup(i,1,cntq){
if(q[i].val){
mt.upd(n*2-q[i].r+1,q[i].val);
}else{
ans[q[i].pos]=max(ans[q[i].pos],mt.sum(n*2-q[i].r));
}
}
sort(q+1,q+cntq+1,[&](query a,query b){
if(a.l!=b.l) return a.l>b.l;
return a.r<b.r;
});
mt.init();
forup(i,1,cntq){
if(q[i].val){
mt.upd(q[i].r,q[i].val);
}else{
ans[q[i].pos]=max(ans[q[i].pos],mt.sum(q[i].r));
}
}
forup(i,1,m){
printf("%d\n",ans[i]-(!ans[i]));
}
}
P10217 [省选联考 2024] 季风
题意
- 给定两个环状数组 $x_i,y_i$，和两个整数 $X,Y$，以及一个限制 $k$。
- 求出最小的 $m$，满足存在两数组 $x_i',y_i'$（这个就不是环状的了），使得 $\forall i\in[0,m),|x_i'|+|y_i'|\le k$，且 $\sum_{i=0}^{m-1} x_i+x_i'=X,\sum_{i=0}^{m-1} y_i+y_i'=Y$，无解输出 $-1$。
- 有多测，$\sum n\le 10^6$，其余数据均小于等于 $10^8$。
题解
傻逼 C++ 整数除法向 $0$ 取整。
首先容易发现这个限制等价于：
$$ |X-\sum_{i=0}^{m-1}x_i|+|Y-\sum_{i=0}^{m-1}y_i|\le mk $$
考虑拆绝对值。看到有个 $\le$ 符号那么考虑拆成 $\max$ 的形式，于是：
$$ \max(X-\sum_{i=0}^{m-1}x_i,-X+\sum_{i=0}^{m-1}x_i)+\max(Y-\sum_{i=0}^{m-1}y_i,-Y+\sum_{i=0}^{m-1}y_i)\le mk $$
也就是说四种搭配方式的最大值小于等于 $mk$。那么显然四个都要小于等于 $mk$。
化一下式子，可以得到：
$$ \begin{aligned} \sum_{i=0}^{m-1}(-x_i-y_i-k)&\le -X-Y\\ \sum_{i=0}^{m-1}(x_i-y_i-k)&\le X-Y\\ \sum_{i=0}^{m-1}(-x_i+y_i-k)&\le -X+Y\\ \sum_{i=0}^{m-1}(x_i+y_i-k)&\le X+Y\\ \end{aligned} $$
这样四个不等关系。
下面讨论最后一种 $\sum_{i=0}^{m-1}(x_i+y_i-k)\le X+Y$，设 $s_j=\sum_{i=0}^{j}(x_i+y_i-k)$（这里钦定 $j<n$）。
容易想到 $\sum_{i=0}^{m-1}$ 相当于在环状数组上绕了完整的若干圈再走了最后一圈的一部分。那么不妨枚举最后一圈走了多少，这样答案就是一个 $s_i+t\times s_{n-1}$ 的形式。带入上面的不等式易得到 $t$ 的上界（或者下界，当 $s_n<0$ 时）。四个合起来就能得到 $t$ 的取值区间。那么假如区间非空就能得到 $t$ 的最小值。对每个 $i$ 求出这个最小值再汇总即可。
注意 C++ 整数除法向 $0$ 取整，考虑用浮点除法算出来再用 floor/ceil 做上下取整。
复杂度 $O(n)$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=2e5+5,inf=1e18;
i64 n,k,x,y,a[N],b[N];
i64 ans=inf;
void solve(){
n=read();k=read();x=read();y=read();
ans=inf;
forup(i,0,n-1){
a[i]=read();b[i]=read();
if(x<0) a[i]*=-1;
if(y<0) b[i]*=-1;
if(i) a[i]+=a[i-1],b[i]+=b[i-1];
}
x=abs(x);y=abs(y);
if(!x&&!y){
puts("0");
return;
}
forup(i,0,n-1){
i64 tl=0,tr=inf;
i64 si=a[i]+b[i]-k*(i+1),sn=a[n-1]+b[n-1]-k*n;
if(sn>0) tr=min(tr,(i64)floor(1.0*(x+y-si)/sn));
else if(sn<0) tl=max(tl,(i64)ceil(1.0*(x+y-si)/sn));
else if(si>x+y) continue;
si=a[i]-b[i]-k*(i+1);sn=a[n-1]-b[n-1]-k*n;
if(sn>0) tr=min(tr,(i64)floor(1.0*(x-y-si)/sn));
else if(sn<0) tl=max(tl,(i64)ceil(1.0*(x-y-si)/sn));
else if(si>x-y) continue;
si=-a[i]+b[i]-k*(i+1);sn=-a[n-1]+b[n-1]-k*n;
if(sn>0) tr=min(tr,(i64)floor(1.0*(-x+y-si)/sn));
else if(sn<0) tl=max(tl,(i64)ceil(1.0*(-x+y-si)/sn));
else if(si>-x+y) continue;
si=-a[i]-b[i]-k*(i+1);sn=-a[n-1]-b[n-1]-k*n;
if(sn>0) tr=min(tr,(i64)floor(1.0*(-x-y-si)/sn));
else if(sn<0) tl=max(tl,(i64)ceil(1.0*(-x-y-si)/sn));
else if(si>-x-y) continue;
if(tl<=tr){
ans=min(ans,tl*n+i+1);
}
}
if(ans==inf){
puts("-1");
}else{
printf("%lld\n",ans);
}
}
signed main(){
i64 t=read();
while(t--){
solve();
}
}
P2391 白雪皑皑
题意
- 有一个长度为 $n$ 的区间，初始为颜色 $0$。有 $m$ 个染色操作，每次操作的区间随机给出（这个相当于随机吧），第 $i$ 次将一个区间染成颜色 $i$。
- 问最终的序列颜色。
- $1\le n\le 10^6,1\le m\le 10^7$
题解
套路地，考虑将操作序列倒过来，这样每个点就只会被染一遍了。那么可以考虑用并查集维护连续的被染过的区间，每次就能 $O(\alpha(n))$ 地跳到下一个没染过地位置。于是做完了，复杂度 $O(m\alpha(n))$（其中 $\alpha$ 是反阿克曼函数，就是并查集的复杂度）。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;i++)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;i--)
using namespace std;
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e6+5,inf=0x3f3f3f3f;
int fa[N],co[N],n,m,p,q;
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
void merge(int u,int v){
u=getfa(u);v=getfa(v);
if(u==v) return;
fa[u]=v;
}
signed main(){
n=read();m=read();p=read();q=read();
forup(i,1,n) fa[i]=i;
fordown(i,m,1){
int l=(p*i+q)%n+1,r=(q*i+p)%n+1;
if(l>r) swap(l,r);
for(int p=l;p<=r;++p){
if(p>l||co[p-1]){
merge(p-1,p);
}
if(co[p]){
p=getfa(p)+1;
if(p<=r){
merge(p-1,p);
}
}
if(p>r) break;
co[p]=i;
}
if(r<n&&co[r+1]) merge(r,r+1);
}
forup(i,1,n){
printf("%d\n",co[i]);
}
}
P2221 [HAOI2012] 高速公路
题意
- 你有一个初始权威 $0$ 的序列 $a_i$，长度为 $n$。有两个操作共 $m$ 次：
- 给 $[l,r)$ 区间内所有点加 $v$。
- 查询在 $[l,r]$ 内等概率随机选两个点 $u,v$（你可以认为 $u<v$），计算从 $u$ 到 $v$ 费用的期望，以最简分数形式输出。
- 其中，从 $i$ 走到 $i+1$ 的费用为 $a_i$，从 $u$ 到 $v$ 的费用即中间每一步的费用之和。
- $1\le n,m\le 10^5$，其余数据在合理范围内，任意时刻有 $0\ge a_i\le 10^4$。
题解
首先期望可以用总费用除以方案数算出，这个就简单 $\gcd$ 即可。
考虑如何计算总费用，即总共的 $\binom{r-l+1}{2}$ 种方案的费用和。
考虑拆分贡献，即计算每个 $a_i$ 会贡献多少次。容易发现对于一个 $i\in[l,r]$，它会在 $(i-l+1)\times (r-i)$ 个区间中产生贡献。
那么这个东西怎么维护呢？考虑线段树。
首先假设两个子结点都做完了，考虑应该怎么合并。
容易发现答案就是两子结点的答案加上横跨两区间的路径的贡献。对于所有左儿子区间内的点，容易发现新路径的终点数量是相同的（即右区间的长度），那么考虑维护每个点的点权乘以它左边（$\le i$）的起点数的总和，同理对于右区间应维护它右边（$ > i$）的终点数的总和（注意一个是小于等于一个是严格大于）。
然后在合并时还要维护这两个东西。只说点权乘以左侧点数的（另一个同理）。容易发现对于左区间是没有变化的。右区间除去原有贡献以外，每个点的“左边的点”数量都增加了左区间长度，那么加上左区间长度乘以总和即可。
这样就处理完每个区间的贡献了，考虑怎么维护跨区间的贡献（妈的写蠢了，其实可以直接把上面这个东西封装一下直接用，但是无所谓了）。
对于一个线段树结点（被查询区间严格包含，即会完全产生贡献），内部的点除去原有贡献以外，还有区间外路径的贡献。容易发现确定 $L,R$ 后，起点终点都不在区间内的路径会使区间内每个点都产生一次贡献，而其中有一个在区间内的贡献做法和刚才类似，于是做完了，复杂度 $O(n\log n)$。
/// ddetails | 参考代码 open: False type: success
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s),E123123=(e);i<=E123123;i++)
#define fordown(i,s,e) for(i64 i=(s),E123123=(e);i>=E123123;i--)
using namespace std;
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e5+5,inf=1e18;
i64 n,m,a[N],ans[N];
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
i64 sum[N<<2],ans[N<<2],lans[N<<2],rans[N<<2],mark[N<<2];
void PushUp(i64 id,i64 l,i64 r){
sum[id]=sum[id<<1]+sum[id<<1|1];
ans[id]=ans[id<<1]+ans[id<<1|1]+(mid-l+1)*rans[id<<1|1]+(r-mid)*lans[id<<1];
rans[id]=rans[id<<1|1]+rans[id<<1]+sum[id<<1]*(r-mid);
lans[id]=lans[id<<1]+lans[id<<1|1]+sum[id<<1|1]*(mid-l+1);
}
void modi(i64 id,i64 val,i64 len){
sum[id]+=val*len;
lans[id]+=val*len*(len+1)/2;
rans[id]+=val*len*(len-1)/2;
ans[id]+=val*(len*len*(len-1)/2-(len-1)*len*(2*len-1)/6);
mark[id]+=val;
}
void PushDown(i64 id,i64 l,i64 r){
modi(id<<1,mark[id],mid-l+1);
modi(id<<1|1,mark[id],r-mid);
mark[id]=0;
}
void Update(i64 L,i64 R,i64 X,i64 l=1,i64 r=n,i64 id=1){
if(L<=l&&r<=R){
modi(id,X,r-l+1);
return;
}
if(mark[id]) PushDown(id,l,r);
if(L<=mid) Update(L,R,X,lson);
if(mid< R) Update(L,R,X,rson);
PushUp(id,l,r);
}
i64 Query(i64 L,i64 R,i64 l=1,i64 r=n,i64 id=1){
if(L<=l&&r<=R){
return ans[id]+rans[id]*(l-L)+lans[id]*(R-r)+sum[id]*(l-L)*(R-r);
}
if(mark[id]) PushDown(id,l,r);
i64 res=0;
if(L<=mid) res+=Query(L,R,lson);
if(mid< R) res+=Query(L,R,rson);
return res;
}
#undef mid
#undef lson
#undef rson
}mt;
i64 gcd(i64 a,i64 b){return b?gcd(b,a%b):a;}
signed main(){
n=read();m=read();
forup(i,1,m){
char op;scanf(" %1c",&op);
if(op=='C'){
i64 l=read(),r=read(),v=read();
mt.Update(l,r-1,v);
}else{
i64 l=read(),r=read();
i64 res=mt.Query(l,r),q=(r-l+1)*(r-l)/2,gg=gcd(res,q);
if(res){
printf("%lld/%lld\n",res/gg,q/gg);
}else{
puts("0/1");
}
}
}
}
///
CF446C DZY Loves Fibonacci Numbers
题意
- 有一个长度为 $n$ 的序列，有 $m$ 个操作，操作有两种区间加斐波拉契数列（从 $1$ 开始），区间求和。
- $1\le n,m\le 3\times 10^5$，对 $10^9+9$ 取模。
题解
斐波拉契数列的通项公式为：
$$ f_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right) $$
那么就转化成两个区间加等比数列（并且公比分别固定）了。
注意到要求 $5$ 的二次剩余，这个可以直接暴力枚举打表，很快就能跑出来，其中一个是 $383008016$。
容易发现对于一个完整区间，我们只需要维护它的首项就能得到整个区间的和，所以懒标记只需记录首项就能正常下传了。
复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;i++)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;i--)
using namespace std;
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=3e5+5,inf=0x3f3f3f3f,mod=1e9+9;
const int s5=383008016,is5=276601605,inv2=5e8+5,q[2]={691504013,308495997};
int pq[2][N];
int ksm(int a,int b){
int c=1;
while(b){
if(b&1) c=1ll*a*c%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
int n,m,a[N];
int calc(int st,int len,int s){
return 1ll*st*(pq[s][len]-1)%mod*q[s]%mod;
//黄金分割比的特性，倒数等于它减一，所以它减一的倒数等于它自己
}
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
int sum[N<<2],mark1[N<<2],mark2[N<<2];
void PushUp(int id){
sum[id]=(sum[id<<1]+sum[id<<1|1])%mod;
}
void Build(int l=1,int r=n,int id=1){
if(l==r){
sum[id]=a[l];
return;
}
Build(lson);Build(rson);
PushUp(id);
}
void modi(int id,int len,int v1,int v2){
msg("%d %d|%d %d|\n",v1,v2,calc(v1,len,0),calc(v2,len,1));
(sum[id]+=(calc(v1,len,0)-calc(v2,len,1)+mod)%mod)%=mod;
(mark1[id]+=v1)%=mod;(mark2[id]+=v2)%=mod;
}
void PushDown(int id,int l,int r){
msg("%d %d|",l,mid);
modi(id<<1,mid-l+1,mark1[id],mark2[id]);
msg("%d %d|=%d %d=",mid+1,r,mid-l+1,mark1[id]-mark2[id]);
modi(id<<1|1,r-mid,1ll*mark1[id]*pq[0][mid-l+1]%mod,1ll*mark2[id]*pq[1][mid-l+1]%mod);
mark1[id]=mark2[id]=0;
}
void Update(int L,int R,int l=1,int r=n,int id=1){
if(L<=l&&r<=R){
msg("%d %d|",l,r);
modi(id,r-l+1,1ll*is5*pq[0][l-L+1]%mod,1ll*is5*pq[1][l-L+1]%mod);
return;
}
if(mark1[id]) PushDown(id,l,r);
if(L<=mid) Update(L,R,lson);
if(mid< R) Update(L,R,rson);
PushUp(id);
}
int Query(int L,int R,int l=1,int r=n,int id=1){
if(L<=l&&r<=R){
return sum[id];
}
if(mark1[id]) PushDown(id,l,r);
int res=0;
if(L<=mid) (res+=Query(L,R,lson))%=mod;
if(mid< R) (res+=Query(L,R,rson))%=mod;
return res;
}
}mt;
signed main(){
n=read();m=read();
pq[0][0]=pq[1][0]=1;
forup(i,1,n){
pq[0][i]=1ll*pq[0][i-1]*q[0]%mod;
pq[1][i]=1ll*pq[1][i-1]*q[1]%mod;
}
forup(i,1,n){
a[i]=read();
}
mt.Build();
forup(i,1,m){
int op=read(),l=read(),r=read();
if(op==1){
mt.Update(l,r);
}else{
printf("%d\n",mt.Query(l,r));
}
}
}
P2757 [国家集训队] 等差子序列
神秘技巧题。
题意
- 给定一个长度为 $n$ 的排列，求其中是否有长度大于等于三的子序列是等差数列。
- $1\le n\le 5\times 10^5$
题解
首先这个条件等价于找有没有长度恰好等于三的子序列是等差数列。
容易想到找中间项 $a_i$，看存不存在一个 $k$，使得 $a_i+k,a_i-k$ 分别在 $i$ 的两边。
发现“存在一对分别在 $i$ 的两边”是不好维护的。正难则反，考虑反过来能不能维护，即维护“全都在 $i$ 的同一边”。
我们可以从小到大遍历序列（注意遍历序列而非数轴），容易发现不存在这样的 $k$ 当且仅当从 $a_i$ 处对折所有被遍历过的点都能对上另一个遍历过的点（或者超出数轴）。考虑哈希维护，做区间哈希可以线段树。复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;i++)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;i--)
using namespace std;
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1<<19,inf=0x3f3f3f3f,P=131,M=1e9+9;
int n,a[N],p[N],pw[N];
struct SegTree{
#define mid ((l+r)>>1)
int hs[2][N<<1];
void clear(){
mem(hs,0);
}
void Update(int P){
hs[0][P+N]=hs[1][P+N]=1;
for(int i=P+N;i;i>>=1){
int len=1<<(19-(31^__builtin_clz(i)));
if(i!=P+N){
hs[0][i]=(hs[0][i<<1]+1ll*hs[0][i<<1|1]*pw[len>>1]%M)%M;
hs[1][i]=(1ll*hs[1][i<<1]*pw[len>>1]%M+hs[1][i<<1|1])%M;
}
}
}
int Query(int P,int l,int r){
if(l>r) return 0;
int res=0,len=0;
stack<int> stk;
for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1){
if(!(l&1)){
if(P==0){
res=(res+1ll*hs[0][l^1]*pw[len]%M)%M;
len+=1<<(19-(31^__builtin_clz(l)));
}else{
stk.push(l^1);
}
}
if(r&1){
if(P==1){
res=(res+1ll*hs[1][r^1]*pw[len]%M)%M;
len+=1<<(19-(31^__builtin_clz(r)));
}else{
stk.push(r^1);
}
}
}
while(stk.size()){
int l=stk.top();stk.pop();
if(P==1){
res=(res+1ll*hs[1][l]*pw[len]%M)%M;
len+=1<<(19-(31^__builtin_clz(l)));
}else{
res=(res+1ll*hs[0][l]*pw[len]%M)%M;
len+=1<<(19-(31^__builtin_clz(l)));
}
}
return res;
}
#undef mid
}mt;
void solve(){
n=read();
mt.clear();
forup(i,1,n){
a[i]=read();
p[a[i]]=i;
}
forup(i,1,n){
int len=min(a[i]-1,n-a[i]);
if(mt.Query(1,a[i]-len,a[i]-1)!=mt.Query(0,a[i]+1,a[i]+len)){
puts("Y");
return;
}
mt.Update(a[i]);
}
puts("N");
}
signed main(){
int t=read();
pw[0]=1;
forup(i,1,5e5){
pw[i]=1ll*pw[i-1]*P%M;
}
while(t--){
solve();
}
}
P3293 [SCOI2016] 美味
题意
- 给定一个长度为 $n$ 的序列 $a_i$，有 $m$ 次查询，每次查询有四个参数 $b,x,l,r$，表示你需要输出 $\max_{i=l}^r\begin{Bmatrix}b\oplus(a_i+x)\end{Bmatrix}$，其中 $\oplus$ 表示按位异或。
- $1\le n \le 2\times 10^5,1\le a_i,b,x\le10^5,1\le l\le r\le n,1\le m\le 10^5$
题解
比较套路，不要想复杂了。
首先这种最大化异或和的题根据套路，从大到小看每一位能不能为 $1$。
如果没有 $+x$ 的影响。相当于每次查询值域上一个长度为 $2^w$ 的区间 $[l,r]$ 内有没有值（就是这一位尽量和 $b$ 不同）。
有了 $+x$ 的影响就转化为查询区间 $[l-x,r-x]$ 了。
对于查询序列上一段区间内有没有某个值，可以用主席树实现。
于是做完了，复杂度 $O(n\log^2 n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;i++)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;i--)
using namespace std;
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1<<18,inf=0x3f3f3f3f;
int n,m,a[N];
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,ls[id]
#define rson mid+1,r,rs[id]
int ls[N*25],rs[N*25],root[N],cnt[N*25],cntn;
void Build(int l,int r,int &id){
id=++cntn;
if(l==r) return;
Build(lson);Build(rson);
}
void Update(int P,int l,int r,int &id,int v){
id=++cntn;
cnt[id]=cnt[v]+1;
if(l==r) return;
ls[id]=ls[v];rs[id]=rs[v];
if(P<=mid) Update(P,lson,ls[v]);
else Update(P,rson,rs[v]);
}
int Query(int L,int R,int l,int r,int id,int v){
if(L>R) return 0;
if(L<=l&&r<=R){
return cnt[id]-cnt[v];
}
int res=0;
if(L<=mid) res+=Query(L,R,lson,ls[v]);
if(mid< R) res+=Query(L,R,rson,rs[v]);
return res;
}
};
SegTree mt;
signed main(){
n=read();m=read();
mt.Build(0,N-1,mt.root[0]);
forup(i,1,n){
a[i]=read();
mt.Update(a[i],0,N-1,mt.root[i],mt.root[i-1]);
}
forup(i,1,m){
int b=read(),x=read(),l=read(),r=read();
int val=0;
fordown(i,17,0){
int w=(1<<i);
if((b>>i)&1){
if(!mt.Query(max(val-x,0),min(val+w-1-x,N-1),0,N-1,mt.root[r],mt.root[l-1])){
val+=w;
}
}else{
if(mt.Query(max(val+w-x,0),min(val+(w<<1)-1-x,N-1),0,N-1,mt.root[r],mt.root[l-1])){
val+=w;
}
}
}
printf("%d\n",b^val);
}
}
P3826 [NOI2017] 蔬菜
唉，贪心算法。
题意
- 你是一个蔬菜商，有 $n$ 种蔬菜，第 $i$ 种蔬菜初始有 $c_i$ 个，单价 $a_i$，假如你卖出至少一个就会额外获得 $s_i$ 的收益。每天有 $x_i$ 个蔬菜会腐烂（你可以先把会烂的卖了，剩下的这一天就不会烂了），烂了就不能卖了。你一天最多卖 $m$ 个蔬菜。
- $k$ 次询问，问你前 $p$ 天最多能赚多少钱。
- $1\le n,k\le 10^5,1\le m\le 10,1\le p\le 10^5$，其余数据在 $32$ 位整数范围内。
题解
首先每天菜会腐烂是不好做的。不妨倒过来变成每天会“长出”菜。这样菜就不会腐烂了。那显然每一天都卖最贵的 $m$ 个是不劣的，因为假如你今天没卖后面任意时刻都能卖。
这样就能 $O(p\log n)$ 地做一个询问了。具体来说对于每种菜先存维护它在什么时候长出第一个（如果 $x_i=0$ 就认为是在最终时刻长出来的），然后用一个堆维护最贵的菜，每次取出最贵的 $m$ 个计入答案。计算完一天后如果还有剩（就是 $c_i$ 个没用完）就压回去。这样就能很简单地维护出每个菜卖了几个了。
但是多组询问。怎么办呢？
容易想到 $p+1$ 的答案和 $p$ 的答案有很大的相关性。容易发现 $p$ 时刻的蔬菜集合严格包含 $p+1$ 的蔬菜集合。也就是说 $p+1$ 决策集合中的所有菜都能存在于 $p$ 的决策集合中。那么显然直接用 $p+1$ 的决策集合删除最便宜的 $m$ 个菜是不劣的（有一些边界情况，实现时注意）。
复杂度 $O(n\log n)$（毕竟那几个数同阶懒得细分了）。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e5+5,inf=0x3f3f3f3f;
i64 n,m,k,a[N],s[N],c[N],x[N],ans[N];
priority_queue<pii> q;
i64 cnt[N],M=1e5;
priority_queue<pii,vector<pii>,greater<pii> > q2;
vector<i64> vec[N];
signed main(){
n=read();m=read();k=read();
forup(i,1,n){
a[i]=read();s[i]=read();c[i]=read();x[i]=read();
if(!x[i]){
vec[M].push_back(i);
}else{
i64 tm=(c[i]+x[i]-1)/x[i];
vec[min(M,tm)].push_back(i);
}
}
fordown(i,M,1){
for(auto j:vec[i]){
q.push(mkp(a[j]+s[j],j));
}
i64 lim=m;
stack<i64> stk;
while(q.size()&&lim>0){
i64 p=q.top().se;q.pop();
if(!cnt[p]){
lim--;
ans[M]+=a[p]+s[p];
++cnt[p];
if(c[p]-(i-1)*x[p]-cnt[p]>0) q.push(mkp(a[p],p));
else stk.push(p);
}else{
i64 num=min(lim,c[p]-(i-1)*x[p]-cnt[p]);
cnt[p]+=num;ans[M]+=num*a[p];
lim-=num;
stk.push(p);
}
}
while(stk.size()){
i64 p=stk.top();stk.pop();
if(cnt[p]<c[p]){
q.push(mkp(a[p],p));
}
}
}
i64 C=0;
forup(i,1,n){
if(cnt[i]){
q2.push(mkp(a[i]+s[i],1));
if(cnt[i]>1){
q2.push(mkp(a[i],cnt[i]-1));
}
C+=cnt[i];
}
}
fordown(i,M-1,1){
i64 t=max(0ll,C-i*m);
C-=t;
ans[i]=ans[i+1];
while(t>0){
pii p=q2.top();q2.pop();
i64 num=min(p.se,t);
t-=num;p.se-=num;
ans[i]-=num*p.fi;
if(p.se){
q2.push(p);
}
}
}
forup(i,1,k){
i64 t=read();
printf("%lld\n",ans[t]);
}
}
P10060 [SNOI2024] 树 V 图
有点神秘的。
题意
- 给定一棵 $n$ 个点的树，其上有 $k$ 个关键点，每个关键点有颜色（即原题意中 $a_i$ 的下标 $i$）。
- 现给定与每个点相距最近的关键点的颜色 $f_u$（若有多个距离相同，则取其中最小的 $i$），问有多少种不同的关键点方案（称两个方案不同当且仅当某个点在两方案中涂色情况不同）。
- $1\le k\le n\le 3000$，有多测。
题解
首先容易发现关键点的 $f_u$ 肯定是它自己的颜色，并且同一个颜色的所有点必定是一个连通块（考虑假设某颜色分成了两个连通块，其中一个连通块肯定离另一种颜色更近），这就能判掉一些不好搞的无解情况了。
然后考虑刻画两颜色连通块的边界。容易发现对应颜色的关键点离边界的距离必定相等（或者相差 $1$，但这个属于细节问题）。
也就是说，我们假设确定了某个连通块内的关键点，我们就能得到其周围所有关键点的合法点集。
那么考虑一个 DP，设 $dp_i$ 表示 $i$ 所在连通块的关键点为 $i$ 的方案数。这玩意显然不能做，因为所有状态都是对全图定义的。考虑能不能把它变成一个类似于树形 DP，每个状态只概括一部分点。
容易想到，由于每种颜色都是一个连通块，而连通块之间也是一个树形结构！所以可以把 $dp_i$ 的定义改成“考虑 $i$ 所在连通块及其在连通块树上的子树，$i$ 所在连通块关键点为 $i$ 的方案数”，这样就能很简单地 $O(n^2)$ 做了。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=3005,mod=998244353;
int n,k,c[N];
vector<int> e[N];
int vis[N],visc[N];
void dfs1(int x,int co){
vis[x]=1;
for(auto i:e[x]){
if(vis[i]||c[i]!=co) continue;
dfs1(i,co);
}
}
int fc[N];
int dp[N],sum;
void dfs3(int x,int fa,int dis,int rt){
if(dis==0){
(sum+=dp[x])%=mod;
if(c[x]>c[rt]) return;
}
if(c[x]<c[rt]&&dis==-1){
(sum+=dp[x])%=mod;
return;
}
if(c[x]>c[rt]&&dis==1){
(sum+=dp[x])%=mod;
}
for(auto i:e[x]){
if(i==fa||c[i]!=c[x]) continue;
dfs3(i,x,dis-1,rt);
}
}
void dfs2(int w,int fa){
for(auto i:e[w]){
if(i==fa) continue;
if(c[i]!=c[w]) fc[c[i]]=c[w];
dfs2(i,w);
}
if(c[fa]!=c[w]){
forup(x,1,n){
if(c[x]==c[w]){
dp[x]=1;
forup(i,1,n) vis[i]=0;
queue<pii> q;
q.push(mkp(x,0));
while(q.size()){
int u=q.front().fi,d=q.front().se;q.pop();
vis[u]=1;
for(auto i:e[u]){
if(c[i]==c[x]){
if(!vis[i]){
q.push(mkp(i,d+1));
}
}else if(c[i]!=fc[c[x]]){
sum=0;
dfs3(i,u,d,x);
dp[x]=1ll*dp[x]*sum%mod;
}
}
}
}
}
}
}
void solve(){
n=read();k=read();
forup(i,1,n) e[i].clear(),vis[i]=visc[i]=fc[i]=dp[i]=0;
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
forup(i,1,n){
c[i]=read();
}
forup(i,1,n){
if(!vis[i]){
if(visc[c[i]]){
puts("0");
return;
}
visc[c[i]]=1;
dfs1(i,c[i]);
}
}
dfs2(1,0);
int ans=0;
forup(i,1,n){
if(c[i]==c[1]){
(ans+=dp[i])%=mod;
}
}
printf("%d\n",ans);
}
signed main(){
int t=read();
while(t--){
solve();
}
}
P8292 [省选联考 2022] 卡牌
题意
- 给定 $n$ 个数 $s_i$，有 $m$ 次询问。第 $i$ 次询问给定 $c_i$ 个质数 $p_{i,j}$，问有多少种选择 $s_i$ 的方法，使得你选出来的数乘积是那几个质数的公倍数。
- $1\le s_i,p_{i,j}\le 2000,1\le c_i,\sum c_i\le 18000,1\le n\le 10^6,1\le m\le 1500$，$p_{i,j}$ 均为质数。
题解
充分利用质数的性质。
首先这道题就相当于让你的在每个质数的倍数中至少选一个数。那么容易想到 $2^{c_i}$ 容斥，具体式子略。
但是 $2000$ 以内有 $303$ 个质数，显然要爆啊。考虑一些更神秘的性质。根据经典性质，一个 $2000$ 以内的数至多只有一个大于 $\sqrt{2000}$ 的质因子。打表可以发现小于等于 $\sqrt{2000}$ 的质数只有 $14$ 个（但是注意到 $43\times 47=2021>2000$，所以其实也可以把 $43$ 归为大于 $\sqrt{2000}$ 的那一类，就只有 $13$ 个了）。这个是支持指数复杂度的。
那么把全集按大于等于 $43$ 的质因子划分为若干个不交的集合 $B_i$。对询问中小于 $43$ 的质数暴力容斥，那么可以维护每个 $B_i$ 中不含某 $msk$（小于 $43$ 的质数的某集合）的数有多少个。如果询问中有 $B_i$ 那么这些中至少要选一个，方案就是 $2^k-1$，否则就是 $2^k$。为了防止复杂度爆炸，可以遍历询问中有的 $B_i$ 把 $2^K-1$ 乘进去，再数出有多少个可选可不选的数，一次性乘 $2^k$ 即可。具体细节见代码。
复杂度 $O(2^{13}(m+\sum c))$。
参考代码
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void();
#endif
using namespace std;
using i64=long long;
#define gc getchar()
int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2005,inf=0x3f3f3f3f,mod=998244353;
int n,m,p2[1000005],num[N];
int siz[350][1<<13];//siz[0][msk] 中存的是对应 msk 的总数
int vv[N],mp[N],cnts;
vector<int> pri;
void init(int n=2000){
mp[1]=0;
forup(i,2,n){
if(!vv[i]){
pri.push_back(i);
mp[i]=++cnts;
}
for(auto j:pri){
if(i*j>n) break;
vv[i*j]=1;
if(i%j==0) break;
}
}
}
signed main(){
init();
n=read();
p2[0]=1;
forup(i,1,n){
p2[i]=2ll*p2[i-1]%mod;
}
forup(i,1,n){
int a=read();
++num[a];
}
forup(aa,1,2000){
if(!num[aa]) continue;
int a=aa,al=0;
if(a==43*43){
forup(i,0,(1<<13)-1){
siz[mp[43]][i]+=num[aa];
siz[0][i]+=num[aa];
}
continue;
}
for(int j=2;j*j<=a;++j){
if(!(a%j)){
if(j<43){
al|=(1<<(mp[j]-1));
}
while(!(a%j)) a/=j;
}
}
if(a!=1&&a<43){
al|=(1<<(mp[a]-1));
a=1;
}
// msg("%d %d||\n",aa,al);
a=mp[a];
forup(msk,0,(1<<13)-1){
if(!(msk&al)){
siz[a][msk]+=num[aa];
if(a) siz[0][msk]+=num[aa];
}
}
}
m=read();
forup(i,1,m){
int c=read();
vector<int> vec;
int al=0,res=0;
forup(i,1,c){
int a=read();
if(a<43){
al|=(1<<(mp[a]-1));
}else{
vec.push_back(a);
}
}
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
for(int msk=al;msk;msk=(msk-1)&al){
int p=__builtin_popcount(msk),val=1,cnt=siz[0][msk];
for(auto i:vec){
val=1ll*val*(p2[siz[mp[i]][msk]]-1)%mod;
cnt-=siz[mp[i]][msk];
}
val=1ll*val*p2[cnt]%mod;
(res+=1ll*(p&1?mod-1:1)*val%mod)%=mod;
}
int val=1,cnt=siz[0][0];
for(auto i:vec){
val=1ll*val*(p2[siz[mp[i]][0]]-1)%mod;
cnt-=siz[mp[i]][0];
}
val=1ll*val*p2[cnt]%mod;
(res+=val)%=mod;
printf("%d\n",res);
}
}
/*
10
23 26 26 25 23 2 7 7 11 20
1
6 13 5 11 7 2 23
*/