预计分数:30+30+0=60
实际分数:30+20+0=50
题解部分全部来自http://www.cnblogs.com/TheRoadToTheGold/p/7723564.html
T1https://www.luogu.org/problem/show?pid=T14734
不会。。打30分暴力走人
对于60%的分数
通过观察可知设当前坐标为x，则通过坐标为a的圆环可移动到2a-x处。连续通过两个圆环(a,b)可以移动到x+(2b-2a)处。
先以移动步数为偶数情况考虑简化版问题：设圆环坐标为a[1]~a[n]，对于任意两个圆环，可由坐标x变为x+2(a[j]-a[i])，题目转化为对于N^2个数其中b[i,j]=2(a[j]-a[i])，通过有限次加减运算能否由x=0变化至目标。
根据广义裴蜀定理以及扩展欧几里得相关原理可知，当且仅当目标为gcd的倍数时有解。故预处理出全部可能的2(a[j]-a[i])，求出其最大公约数，在判断目标是否为gcd的倍数即可。
对于奇数的情况，可以通过枚举第一步的方案转化为偶数的情况，即维护一个set表示0步或1步可达点集(mod gcd意义下)，再查询目标点在mod gcd下是否属于这个集合即可。复杂度瓶颈在于N^2个数求gcd。
对于100%的分数
通过欧几里得算法的性质与更相减损术可知gcd(a,b)=gcd(a-b,b)。设p1={2*(a[i]-a[1])|i>1}的最大公约数，设p2={2*(a[i]-a[j])}的最大公约数，易知p1>=p2（因为p1比p2约束宽松）。而对于任意i,j由于p1同时是2*(a[i]-a[1])、2*(a[j]-a[1])的约束，那么p1也一定是任意2*(a[i]-a[1])-2*(a[j]-a[1])=2*(a[i]-a[j])的约数，故p1<=p2。综上所述p1=p2，这样就不需要N^2个数同时求gcd了，只求p1即可，可获得满分。
#include<set>
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; typedef long long LL; #define N 100001 LL a[N]; set<LL>S; void read(LL &x)
{
x=; int f=; char c=getchar();
while(!isdigit(c)) { if(c=='-') f=-; c=getchar(); }
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
x*=f;
} LL getgcd(LL i,LL j) { return !j ? i : getgcd(j,i%j); } int main()
{
freopen("ninja.in","r",stdin);
freopen("ninja.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) read(a[i]);
LL gcd=;
for(int i=;i<=n;i++) gcd=getgcd(abs(a[i]-a[]<<),gcd);
LL x;
if(gcd)
{
S.insert();
for(int i=;i<=n;i++) S.insert((*a[i]%gcd+gcd)%gcd);
while(m--)
{
read(x);
puts(S.find((x%gcd+gcd)%gcd)!=S.end() ? "Yes" : "No");
}
}
else
{
while(m--)
{
read(x);
puts(x==a[]* ? "Yes" : "No");
}
}
}
T2https://www.luogu.org/problem/show?pid=T14735
有20分裸地暴力
还有10分裸的线段树
其他的不会做，，后来线段树写炸了QWQ、、、
线段树
先下放取反标记，在下方加标记
下放取反标记时，若存在加标记，加标记也取反
关键是如何处理加标记的影响
设当前线段树区间有4个数x1，x2，x3，x4
sum[i] 表示 选出i个数的乘积 的和
sum[1]=x1+x2+x3+x4
sum[2]=x1x2+x1x3+x1x4+x2x3+x2x4+x3x4
sum[3]=x1x2x3+x1x2x4+x1x3x4+x2x3x4
sum[4]=x1x2x3x4
操作：区间加a
以sum[3]为例
新的sum[3]=
(x1+a)(x2+a)(x3+a) +
(x1+a)(x2+a)(x4+a) +
(x1+a)(x3+a)(x4+a) +
(x2+a)(x3+a)(x4+a)
=x1x2x3+a(x1x2+x1x3+x2x3)+a^2(x1+x2+x3)+a^3 +
x1x2x4+a(x1x2+x1x4+x2x4)+a^2(x1+x2+x4)+a^3 +
x1x3x4+a(x1x3+x1x4+x3x4)+a^2(x1+x3+x4)+a^3 +
x2x3x4+a(x2x3+x2x4+x3x4)+a^2(x2+x3+x4)+a^3
=sum[3] + a*sum[2]*2 + a^2*sum[1]*3 + a^4
所以 对有siz个元素的区间执行区间加a操作
那么sum[]的更新：
for i： 10 ——> 1
for j：i-1——>1
sum[i]+=a^(i-j)*sum[j]*C(siz-j,i-j)
解释：
有i个（xi+a）相乘
从里面选出j个xi，那就只能选i-j个a
后面那个组合数？
一共有siz个（xi+a） ，已经确定了有j个（xi+a）选择xi
一共要选i个（xi+a），那就要从剩下的siz-j个（xi+a）里选出 i-j个（xi+a）来用他们的a
所以是C（siz-j，i-j）
区间的合并
枚举左边选j个，那右边就选i-j个，乘起来就行了
例：
假设当前要选3个数
左边有2个数x1，x2 选1个，
右边有3个数x3，x4，x5 选2个
那就是 x1*x3*x4+x1*x3*x5+x1*x4*x5+x2*x3*x4+x2*x3*x5+x2*x4*x5
=x1*右边的sum[2]+x2*右边的sum[2]
=左边的sum[1] * 右边的sum[2]
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 50001 const int mod=1e9+; typedef long long LL; int n; int C[N][]; int f[N<<];
int siz[N<<],mid[N<<];
bool rev[N<<]; struct node { int sum[]; }ans[N<<]; void read(int &x)
{
x=; int ff=; char c=getchar();
while(!isdigit(c)) { if(c=='-') ff=-; c=getchar(); }
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
x*=ff;
} int tot=; void MOD(int &a,int b)
{
a+=b;
a-= a>=mod ? mod : ;
} void pre(int n)
{
C[][]=;
for(int i=;i<=n;i++)
{
C[i][]=;
for(int j=;j<=min(i,);j++) C[i][j]=(C[i-][j]+C[i-][j-])%mod;
}
} void update(int k)
{
for(int i=;i<=;i++)
{
ans[k].sum[i]=;
for(int j=;j<i;j++) MOD(ans[k].sum[i],1ll*ans[k<<].sum[j]*ans[k<<|].sum[i-j]%mod);
MOD(ans[k].sum[i],ans[k<<].sum[i]); MOD(ans[k].sum[i],ans[k<<|].sum[i]);
}
} void build(int k,int l,int r)
{
siz[k]=r-l+;
if(l==r) { read(ans[k].sum[]); MOD(ans[k].sum[],); return; }
mid[k]=l+r>>;
build(k<<,l,mid[k]); build(k<<|,mid[k]+,r);
update(k);
} void insert(int k,int w)
{
MOD(f[k],w);
for(int i=;i;i--)
{
int x=w;
for(int j=i-;j;j--,x=1ll*x*w%mod)
MOD(ans[k].sum[i],1ll*x*ans[k].sum[j]%mod*C[siz[k]-j][i-j]%mod);
MOD(ans[k].sum[i],1ll*x*C[siz[k]][i]%mod);
}
} void turn(int k)
{
rev[k]^=;
if(f[k]) f[k]=mod-f[k];
for(int i=;i>;i-=)
if(ans[k].sum[i]) ans[k].sum[i]=mod-ans[k].sum[i];
} void down(int k)
{
if(rev[k]) turn(k<<),turn(k<<|),rev[k]=;
if(f[k]) insert(k<<,f[k]),insert(k<<|,f[k]),f[k]=;
} void add(int k,int l,int r,int opl,int opr,int w)
{
if(l>=opl && r<=opr) { insert(k,w); return; }
down(k);
if(opl<=mid[k]) add(k<<,l,mid[k],opl,opr,w);
if(opr>mid[k]) add(k<<|,mid[k]+,r,opl,opr,w);
update(k);
} void reverse(int k,int l,int r,int opl,int opr)
{
if(l>=opl && r<=opr) { turn(k); return; }
down(k);
if(opl<=mid[k]) reverse(k<<,l,mid[k],opl,opr);
if(opr>mid[k]) reverse(k<<|,mid[k]+,r,opl,opr);
update(k);
} node query(int k,int l,int r,int opl,int opr,int w)
{
if(l>=opl && r<=opr) return ans[k];
down(k);
if(opr<=mid[k]) return query(k<<,l,mid[k],opl,opr,w);
else if(opl>mid[k]) return query(k<<|,mid[k]+,r,opl,opr,w);
else
{
node L=query(k<<,l,mid[k],opl,opr,w),R=query(k<<|,mid[k]+,r,opl,opr,w);
node tmp;
for(int i=;i<=w;i++)
{
tmp.sum[i]=(L.sum[i]+R.sum[i])%mod;
for(int j=;j<i;j++) MOD(tmp.sum[i],1ll*L.sum[j]*R.sum[i-j]%mod);
}
return tmp;
}
} int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int n,m;
read(n); read(m);
pre(n);
build(,,n);
int ty,l,r,w;
while(m--)
{
read(ty); read(l); read(r);
if(ty==)
{
read(w); w%=mod;
w+= w< ? mod : ;
add(,,n,l,r,w);
}
else if(ty==) reverse(,,n,l,r);
else
{
read(w);
node p=query(,,n,l,r,w);
printf("%d\n",query(,,n,l,r,w).sum[w]);
}
}
}
T3https://www.luogu.org/problem/show?pid=T14737
没看懂题目。。。。
总结
、。、、今天的考试确实没有昨天那么水了，，，，
不过，，我好菜啊。。。。。。