T1
题意
在 \(n\) 瓶水中有1瓶毒药，\(m\)次实验，每次选择 \(k\) 瓶水测试其中是否有毒药，给出实验结果，试判断能否辨别出毒药，若能则给出最早得出结论的实验批次，否则求出可能成为毒药的编号。
分析
提前一天就被告知是道构造，考场上还是没写出题解的线性解法，写了个维护 \(set\) 以为会 \(TLE\)，期望得分 \(75pt\)，结果是 \(WA\)，喜提 \(40pt\)，目前还没订正。
T2
题意
有 \(n\) 个权值 \(a_i\) 的人解决 \(m\) 个事件，每个事件必须至少由指定两人之一参与，定义一个合法方案的权值是参与方案的人权值之积，求所有合法方案的权值和。
分析
这道题 \(m\) 最大可达 \(800\)，而 \(n\) 最大只有 \(36\)，故考虑对 \(n\) 进行状态枚举，不过仍然开不了 \(2^{36}\) 大小的数组，考场上就写了个 \(n=20\) 的部分分，期望得分 \(20pt\)，实际得分 \(0pt\)，题解让人眼前一亮，使用折半状压，对当前枚举到的状态 \(now\) 直接匹配另一半状态，把复杂度降低到了 \(O(2^{\frac{n}{2}} \times n)\)。
Code
#include<iostream>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=18;
int n,m,MOD,a[N<<1],ltl[N],ltr[N],rtr[N],sum[1<<N],lft,rgt,res;
int main()
{freopen("planet.in","r",stdin);freopen("planet.out","w",stdout);IOS;cin>>n>>m>>MOD;lft=(n+1)/2,rgt=n-lft;for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<m;i++){int u,v;cin>>u>>v;u--,v--;if(u>v) swap(u,v);if(u<lft){if(v<lft) ltl[u]|=(1<<v);else ltr[u]|=(1<<(v-lft));}else rtr[u-lft]|=(1<<(v-lft));}for(int sta=0;sta<(1<<rgt);sta++){int tmp=1;for(int i=0;i<rgt;i++){if((sta>>i)&1)tmp=1ll*tmp*a[i+lft]%MOD;else if((sta|rtr[i])!=sta){tmp=0;break;}}sum[sta]=tmp;}for(int i=0;i<rgt;i++)for(int sta=0;sta<(1<<rgt);sta++)if(!((sta>>i)&1)) sum[sta]=(sum[sta]+sum[sta|(1<<i)])%MOD; for(int sta=0;sta<(1<<lft);sta++){int tmp=1,need=0;for(int i=0;i<lft;i++){if((sta>>i)&1)tmp=1ll*tmp*a[i]%MOD;else {if((sta|ltl[i])!=sta){tmp=0;break;}elseneed|=ltr[i];}}res=(res+1ll*tmp*sum[need]%MOD)%MOD;}cout<<res<<'\n';return 0;
}
T3
题意
对一个排列 \(a\) 进行冒泡排序，共 \(n-1\) 趟，\(q\) 次询问数字 \(x\) 在 \(k\) 趟排序后的下标。
分析
考场上写的暴力，离线询问之后直接模拟，期望得分 \(20pt\)，实际得分 \(20pt\)，题解写的线段树，目前还没订正。
T4
题意
维护长度为 \(n\) 的序列 \(a\)，支持修改操作 \((x,y,k)\)，对所有满足 \((i-1) \pmod{x} \leq y\) 的 \(a_i\) 加上 \(k\)，查询操作 \((l,r)\)，求 \(\Sigma_{i=l}^r a_i\)。
分析
注意到这道题可以用根号分治。
对于 \(x \leq \sqrt{n}\) 的部分维护 \(f_{i,j}\) 表示 \(\Sigma a_t,(t-1) \equiv j \pmod{i}\)，每次修改 \(O(\sqrt{n})\) 暴力更新，维护 \(f_{i,j}\) 的前缀和就可以 \(O(1)\) 查询。
对于 \(x > \sqrt{n}\) 的部分，需要修改的区间数量不超过 \(\sqrt{n}\) 个，考虑通过线段树维护修改和查询，不过 \(O(m \sqrt{n} \log n)\) 的时间复杂度会 \(TLE\)，注意到每次修改的区间数是 \(\sqrt{n}\)，而查询操作只涉及 \(1\) 个区间，考虑使用 \(diff_i\) 表示 \(\Delta a_i\) 的差分，这样就有了 \(\Sigma_{i=l}^r a_i = \Sigma_{i=l}^r \Sigma_{j=1}^i diff_j = (r-l+1) \Sigma_{i=1}^{l-1} diff_i + \Sigma_{i=l}^r diff_i (r-i+1)\)，我们只需要通过分块维护 \(diff_i\) 和 \(i \times diff_i\) 就可以了。本题是这次唯一在考场上 \(AC\) 的题，期望得分 \(100pt\)，实际得分 \(100pt\)。
值得一提的是，由于代码中对于 \(x \leq \sqrt{n}\) 部分的处理常数更小，故可以调小决策点，分为 \(x \leq \frac{\sqrt{n}}{2}\) 和 \(x > \frac{\sqrt{n}}{2}\) 两部分。
Code
#include<iostream>
#include<cmath>
#define bl(i) ((i-1)/blo+1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=2e5+5;
const int M=1005;
int n,m,blo;
long long val[N],pre[N],delta[M][M],pre_delta[M][M],add_tag[N][2],sum[M][2];
inline int read()
{int t=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9'){t=t*10+ch-'0';ch=getchar();}return t;
}
long long Query(int l,int r,int opt)
{long long res=0;for(int i=l;i<=min(r,bl(l)*blo);i++) res+=add_tag[i][opt];if(bl(l)!=bl(r))for(int i=(bl(r)-1)*blo+1;i<=r;i++) res+=add_tag[i][opt];for(int i=bl(l)+1;i<=bl(r)-1;i++) res+=sum[i][opt];return res;
}
int main()
{freopen("four.in","r",stdin);freopen("four.out","w",stdout);IOS;n=read();m=read();blo=sqrt(n);if(n>=100) blo/=2;for(int i=1;i<=n;i++)val[i]=read();for(int i=1;i<=n;i++)pre[i]=pre[i-1]+val[i];for(int i=1;i<=m;i++){int op=read();if(op==1){int x=read(),y=read(),k=read();y=min(y,x-1);if(x<=blo){for(int j=0;j<=y;j++) delta[x][j]+=k;pre_delta[x][0]=delta[x][0];for(int j=1;j<x;j++)pre_delta[x][j]=pre_delta[x][j-1]+delta[x][j];}else{for(int l=1;l<=n;l+=x){add_tag[l][0]+=k,sum[bl(l)][0]+=k;add_tag[l][1]+=1ll*l*k,sum[bl(l)][1]+=1ll*l*k;if(l+y+1>n) continue;add_tag[l+y+1][0]-=k,sum[bl(l+y+1)][0]-=k;add_tag[l+y+1][1]-=1ll*(l+y+1)*k,sum[bl(l+y+1)][1]-=1ll*(l+y+1)*k;}}}else{int l=read(),r=read();long long ans=pre[r]-pre[l-1];for(int x=1;x<=blo;x++)ans=ans+pre_delta[x][(r-1)%x]+((r-1)/x-(l-1)/x)*pre_delta[x][x-1]-((l-1)%x<1?0:pre_delta[x][(l-1)%x-1]);ans+=(r-l+1)*Query(1,l-1,0)+(r+1)*Query(l,r,0)-Query(l,r,1);cout<<ans<<'\n';}}return 0;
}