NOIP 提高组模拟赛5
math
emmmmmm，这题我跑了个奇奇怪怪的背包，然后用奇奇怪怪的优化，然后奇奇怪怪的AC了
先说我奇奇怪怪的想法，发现本题式子可以理解为每个数可以取任意个，能够凑出的数有哪些，貌似可以完全背包
然鹅，因为存在模k这个操作，直接跑完全背包显然是错的，跑多些容量应该是可行的，但是跑多少是难以预估的，(MLETLE警告)，然后我们考虑最多取多少个物品，之后再取都没有意义，显然，让物品大小\(j\)不停的加\(a[i]\)模\(k\)，等到再次等于\(a[i]\)即可停止
然鹅，这样会喜提TLE，考虑继续优化，发现其实我们会多次取到同一个容量，造成了许多无意义的判断，如何简化？首先对原数组取模后排序，然后每次判断一下1单位的新的容量是否已经存在，如果存在，那说明有步长比当前容量小的已经更新过了，那么当前容量没有必要更新，这样能大大降低复杂度。最终复杂度\(O(能过)\)
再说一下题解做法，其他大佬也都是这个思路，以下内容照抄题解
\(ax + by = z\)存在整数解，当且仅当\(gcd(a, b)∣z\)。
那么，若\(z\)可以被凑出，即 \(\sum_{i=1}^{n} x_{i}a_{i} = z\)，当且仅当\(gcd(a_{1} , a_{2} , ? , a_{n} )∣z\)。因此，答案只能是\(gcd\)的整数
倍。但是，这样考虑$x \(有可能是负数，但是在\)mod k\(的条
件下，我们可以把\)x \(调为非负整数。
时间复杂度\)O((n + k)logv)$
奇奇怪怪的背包代码
#include
#include
#include
using namespace std;
const int maxn=1000005;
int a[maxn];
bool vis[maxn];
int main(){
int n,k;scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)a[i]=a[i]%k;
vis[0]=1;
sort(a+1,a+n+1);
for(int i=1;i<=n;++i){
if(vis[a[i]])continue;
bool flag=1;
for(int j=a[i];flag||j!=a[i];j=(j+a[i])%k){
flag=0;if(vis[j])continue;
for(int x=j;x B. biology
首先走的点越多越好，对于a相同的点，一定由a小于他们的最大的转移，可以列出DP式子\(f[i]=max(f[k]+b[i]+|x[i]-x[k]|+|y[i]-y[k]|)\)，然后我们发现该式子转移最坏情况达到了\(O(N^2M^2)\)，考虑如何优化
式子中最讨厌的就是绝对值，那么我们考虑拆掉，分四种情况讨论，然后可以开四个二维树状数组维护范围最大值转移，这样复杂度可以降到\(O(NMlogNlogM)\)，可是貌似还会TLE，如何继续优化？
其实可以发现，假如我们不考虑状态是否合法，就是那个绝对值符号是否正确，因为不合法的相当于减去了一个数，合法状态加上了一个数，最终取的\(max\)一定是合法的状态，所以我们没有必要查询范围最值，直接使用全局最值是没有问题的，直接取最值即可
#include
#include
#include
#include
using namespace std;
const int maxn=2005;
struct node{
int x,y,a,b;
}c[maxn*maxn];
int tot,n,m;
bool cmp(node x,node y){
return x.a C. english
这题好难啊，用到了可持久化Tire树，启发式合并等我没学过的算法，对着题解一行行敲的，先简单理解一下，等学完了那些知识再看看有没有坑填
首先暴力代码+特殊性质特判可以搞到30-50pts
然后再说正解，用单调栈处理出每个数\(x\)作为最大值的区间，用\(l[x]\)和\(r[x]\)记录区间左右端点，然后对以每个x单独处理
首先说对ans1的计算，假设确定了区间一侧端点，怎么快速求出所有从该端点出发的区间的贡献？因为异或运算的存在，考虑按位处理，如果端点的值该位为1，那么另一端为0才有贡献，反之亦然。预处理出前缀和数组\(sum[i][j]\)表示前i个数，第j位为1的个数，对于区间查询\(l-x-r\)为了降低循环次数，我们用x左右两端较小的来枚举，查询另一端与该位不同的的个数\(s\)，对答案有\(s*(1<
然后对于ans2我还没理解
对每个以x为最大值的区间，同样确定了一段，查找有多少有贡献的另一端，就是查找\(a[x]\)和某段区间中几个数异或值大于\(a[x]\)，用类似前缀和的方式维护可持久化Tire树，每个数都是一个新的版本，我们只需要建一条链，剩下的查询历史版本即可。处理每个前缀的数的个数，即每个节点向下有几个有效信息。查找过程从高位向低位，如果\(a[x]\)此位为1，那\(a[i]\)与此位必须异或为1才可能贡献，如果\(a[x]\)此位为0，那么此位为异或为1的（前面与y相同）的数的个数就是贡献，然后还要继续向下累计异或为0的情况。最后用类似前缀和的方式减一下，防止负数加一个mod再计算即可。
#include
#include
using namespace std;
const int mod=1e9+7;
const int maxn=2e5+25;
int max(int x,int y){return x>y?x:y;}
int a[maxn],n,opt;
int l[maxn],r[maxn],sta[maxn],top;
int sum[maxn][25],root[maxn];
long long ans1,ans2;
struct tire{
int siz[maxn*30];//当前节点子树，有多少个信息（数）
int son[maxn*30][2];//son[x][0/1] x 的两个子节点，0/1为边上维护的信息
int cnt;
void insert(int prt,int &rt,int x,int dep){//可持久化Tire树 prt历史版本根节点，rt当前状态根节点（未确定，需要传参），x插入的新信息（值），dep还需处理的深度
rt=++cnt;siz[rt]=siz[prt];//开新点，个数记录历史版本
if(dep<0){//处理完毕，加上本次贡献返回
++siz[rt];
return;
}
int tmp=(x>>dep)&1;
son[rt][tmp^1]=son[prt][tmp^1];//当前没有的点，继承历史版本
insert(son[prt][tmp],son[rt][tmp],x,dep-1);//向下
siz[rt]=siz[son[rt][0]]+siz[son[rt][1]];//统计个数
return;
}
int query(int x,int y,int pos){//查询在1-pos区间内有多少数异或x大于y，即有贡献的个数
int u=root[pos],ret=0;//ret统计答案，u为当前点
for(int i=20;i>=0;--i){//从高位向低位找
int a=(x>>i)&1;
int b=(y>>i)&1;
if(b==0){//如果y此位为0，那么此位为异或为1的（前面与y相同）的数的个数就是贡献
ret+=siz[son[u][a^1]];//记录当前贡献
u=son[u][a];//继续查找与y此位也相同，大于y的个数
}
else u=son[u][a^1];//如果y此位为1，那此位必须异或为1才可能贡献，向下求解
if(!u)break;
}
return ret;
}
}t;
void solve(int x,int l,int r){
if(x-l=0;--j){
if((a[i]>>j)&1)ans1=(ans1+1ll*(1<=0;--j){
if((a[i]>>j)&1)ans1=(ans1+1ll*(1<=a[sta[top]]&&top)r[sta[top]]=i-1,--top;
l[i]=sta[top]+1;
sta[++top]=i;
}
while(top)r[sta[top]]=n,--top;
//sum前缀和，sum[i][j]前i个数 从低向位第j位为1的有几个
for(int i=1;i<=n;++i){
for(int j=0;j<=20;++j){
if(1&(a[i]>>j))sum[i][j]=sum[i-1][j]+1;
else sum[i][j]=sum[i-1][j];
}
}
for(int i=1;i<=n;++i)solve(i,l[i],r[i]);
if(opt&1)printf("%lld\n",ans1);
if(opt&2)printf("%lld\n",ans2);
return 0;
}