D1T1 P10217 季风
题意有点抽象，大概就是要求我们对两个有若干次重复的序列进行操作，每次可以将这两个序列都向上或向下调整一个值，但是调整的绝对值的总和有限制，问能否最终将总和调整至固定值。
由于 \(m\) 不一定是 \(n\) 的倍数，因此序列在重复若干次之后可能会遗留一些散块，这是不好处理的，我们考虑枚举这个散快的大小，这样就只用考虑整块的加减。
简化条件之后就可以开始求解了，先考虑其中一个序列，设散块的和为 \(suma\)，大小为 \(l\)，整块的和为 \(Asum\)，则如果我们要选择 \(k\) 个散块，则我们需要调整的大小就是 \(|suma+k \cdot Asum -x|\)，另一个序列同理，当二者和不超过 \(k \cdot n + l\) 时有解。
我们将两个绝对值函数求和并减去右边的一次函数，那我们要求的即为最小零点，注意到相加后的函数也是凸函数，直接两次二分的复杂度是 \(O(n\log n)\) 的，直接对折点分讨就可以做到线性，这里给个我的考场 90 分代码（赛时因为 abs 惨遭 CE）。
#include<bits/stdc++.h>
#define ll __int128
#define N 1000005
#define inf 0x7f7f7f7f7f7f7f7f
using namespace std;
ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
void write(ll x){
if(x<0)x=-x,putchar('-');
if(x/10)write(x/10);
putchar(x%10+'0');
}
ll a[N],b[N];
ll n,k,x,y,Asum,Bsum,suma=0,sumb;
ll labs(ll x){
return (x<0?-x:x);
}
ll f(ll pos,ll ty){
if(ty==1)return labs(suma+pos*Asum-x);
else return labs(sumb+pos*Bsum-y);
}
bool check(ll mid){
ll vala=(f(mid+1,1)-f(mid,1));
ll valb=(f(mid+1,2)-f(mid,2));
return vala+valb-n*k>0;
}
void solve(){
n=read(),k=read(),x=read(),y=read();Asum=0,Bsum=0;ll ans=inf;
for(ll i=1;i<=n;i++){
a[i]=read();b[i]=read();
Asum+=a[i];Bsum+=b[i];
}
if(x==0 && y==0){write(0);putchar('\n');return;}
suma=0,sumb=0;
for(ll i=1;i<=n;i++){
suma+=a[i];sumb+=b[i];
ll l=1,r=500000000000000ll;
while(l<r){
ll mid=(l+r)>>1;
if(check(mid)>0)r=mid;
else l=mid+1;
}
r=l;l=0;
while(l<r){
ll mid=(l+r)>>1;
if(f(mid,1)+f(mid,2)<=(mid*n+i)*k)r=mid;
else l=mid+1;
}
if(f(l,1)+f(l,2)<=(l*n+i)*k)ans=min(ans,l*n+i);
if(i%10000==0)write(i);
}
if(ans==inf)write(-1),putchar('\n');
else write(ans),putchar('\n');
}
int main(){
ll T=read();while(T--)solve();
return 0;
}
D1T2 P10218 魔法手杖
我们先考虑只有异或该怎么做，这类问题的一个传统套路是从高位到低位贪心检验前面确定的为加上这位为 1 是否有解，有解就将答案这位设成 1，否则不变并向下继续考虑，因此我们只用关心怎样解决如何判定答案的问题。
由于这个问题有良好的贪心性质，我们也从上往下依次进行判定，类似数位 dp 的操作，我们只考虑到当前位都贴紧答案上界的数，这样如果有些数已经在比较高的某些位置（我们已经考虑过的位置）大于答案，那我们就不用再在下面处理。这样说可能有些抽象，更具体地，若是关注判定过程中的其中一层，我们可以将其分为以下几种情况：
-
若答案这位为 0，那么如果我们不在这位进行异或操作，这位为 1 的数字就可以不用考虑，直接递归处理这位为 0 的数字，进行操作的情况同理。
-
若答案这位为 1，如果这位既有 0 又有 1 那肯定无解，因为我们没办法只通过异或让所有数这位都是 1，否则操作唯一，递归处理即可。
这样我们就解决了全是异或操作的情况，而由于加法操作也有能够贪心的良好性质，我们尝试能不能不做大的改动，只在原本求解的框架上进行小的修改。
D2T1 P10220 迷宫守卫
#include<bits/stdc++.h>
#define N 200005
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9')f=(ch=='-'?-1:1),ch=getchar();
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
void write(ll x){
if(x<0)x=-x,putchar('-');
if(x/10)write(x/10);
putchar(x%10+'0');
}
ll n,k,tot;
ll ans[N],c[N],q[N],le[N],mar[N];
struct Node{
ll c,w;
Node(ll c=0,ll w=0):c(c),w(w){}
};
vector<Node> t[N];
map<ll,pair<ll,ll> > T[N];
void dfs(ll x){
if(x>=(1<<n))return t[x].push_back(Node(0,q[x])),void();
ll ls=(x<<1),rs=(x<<1)|1;dfs(ls);dfs(rs);
ll lasls=inf,lasrs=inf,lpos=0,rpos=0,bel=0;Node val;
for(ll i=1,lim=t[ls].size()+t[rs].size();i<=lim;i++){
if(rpos==t[rs].size() || (lpos!=t[ls].size() && t[ls][lpos].w>t[rs][rpos].w))val=t[ls][lpos++],bel=0;
else val=t[rs][rpos++],bel=1;
if(bel==0){
ll cos=inf;
if(t[rs].size()!=0 && t[rs][t[rs].size()-1].w>val.w){
t[x].push_back(Node(val.c,val.w));
}
else if(lasrs!=inf){
if(lasrs<=c[x])t[x].push_back(Node(val.c+lasrs,val.w)),T[x][val.w]=make_pair(0,-lasrs);
else t[x].push_back(Node(val.c+c[x],val.w)),T[x][val.w]=make_pair(lasrs-c[x],-c[x]);
}
else t[x].push_back(Node(val.c+c[x],val.w));
}
else{
if(t[ls].size()!=0 && t[ls][t[ls].size()-1].w>val.w){
t[x].push_back(Node(val.c,val.w));
}
else if(lasls!=inf){
t[x].push_back(Node(val.c+lasls,val.w));T[x][val.w]=make_pair(0,-lasls);
}
}
if(bel==0)lasls=min(lasls,val.c);
else lasrs=min(lasrs,val.c);
}
}
ll ide(ll val,ll d){
return (le[val]&(1<<(n-d-1)))?1:0;
}
void solve2(ll x,ll opt){
if(x>=(1<<n))return ans[++tot]=q[x],void();
if(opt==-1){
for(auto val:t[x]){
if(val.c>k)continue;
ll d=__lg(x);ll id=ide(val.w,d);k-=val.c;
solve2((x<<1)+id,val.w);
if(k>=T[x][val.w].first)k-=T[x][val.w].second;
solve2((x<<1)+(id^1),-1);
break;
}
}
else{
ll d=__lg(x),id=ide(opt,d);
solve2((x<<1)+id,opt);if(k>=T[x][opt].first)k-=T[x][opt].second;
solve2((x<<1)+(id^1),-1);
}
}
void solve(){
n=read(),k=read();
for(ll i=1;i<(1<<n);i++)c[i]=read();
for(ll i=(1<<n);i<(1<<(n+1));i++)q[i]=read(),le[q[i]]=i;
dfs(1);solve2(1,-1);tot=0;
for(ll i=1;i<=(1<<n);i++)write(ans[i]),putchar(' ');
for(ll i=1;i<=(1<<(n+1));i++)t[i].clear(),mar[i]=0,T[i].clear();putchar('\n');
}
int main(){
ll T=read();while(T--)solve();
return 0;
}