SDOI2016 Round 1解题报告
2017-02-18 10:09:00         来源：morestep的专栏

SDOI2016 Round 1解题报告：已知n,m,k，求∑n?1i=0∑m?1j=0max((ixorj)?k,0)。

Ps.对于取模中的除法运算，如x=(a/2)modP可以转化成x=((amod(2?P))/2)modP

Code:

``````#include
#include
#include
#include
#include
#include
using namespace std;
#define N 70
#define LL long long
LL n,m,K,P,ans,mi[N];
inline int in(){
int x=0; char ch=getchar(); bool f=1;
while (ch<'0'||ch>'9'){
if (ch=='-') f=0;
ch=getchar();
}while (ch>='0'&&ch<='9')
x=x*10+ch-'0',ch=getchar();
if (!f) x=-x; return x;
}
inline LL Lin(){
LL x=0; char ch=getchar(); bool f=1;
while (ch<'0'||ch>'9'){
if (ch=='-') f=0;
ch=getchar();
}while (ch>='0'&&ch<='9')
x=x*10ll+(LL)(ch-'0'),ch=getchar();
if (!f) x=-x; return x;
}
inline LL calc(LL x,LL y){
LL s=(((x+y)%(P*2ll))*((y-x+1)%(P*2ll)))%(P*2ll);
s/=2ll,s%=P; return s;
}
inline LL work(LL x,LL y,int xx,int yy){
LL s=0,z; if (xxK) s=calc(z-K,z+mi[xx]-K-1);
else if ((z+mi[xx])>K) s=calc(0,z+mi[xx]-K-1);
s=(s*(mi[yy]%P))%P; return s;
}
int main(){
int T=in(),i,j,tt; LL x,y;
mi[0]=1ll;
for (i=1; i<=62; i++) mi[i]=mi[i-1]<<1;
for (tt=1; tt<=T; tt++){
n=Lin(),m=Lin(),K=Lin();
P=Lin(),x=0ll,ans=0ll;
for (i=62; i>=0; i--){
if (n&mi[i]){
y=0ll;
for (j=62; j>=0; j--){
if (m&mi[j]){
ans=(ans+work(x,y,i,j))%P,y|=mi[j];
}
}x|=mi[i];
}
}printf("%I64d\n",ans);
}return 0;
}``````

T2

S?>每个奇数个质因子的数，流量为bi，费用为0

Code:

``````#include
#include
#include
#include
#include
#include
using namespace std;
#define N 610
#define M 600010
#define P 2000000
#define inf 1000000000
#define limit -100000000000000ll
#define LL long long
struct A{
int x,y,k; LL z;
}a[N];
struct e{
int u,v,cap,next; LL cost;
}e[M*2];
bool vis[N]; LL dis[N],sum=0;
inline int in(){
int x=0; char ch=getchar(); bool f=1;
while (ch<'0'||ch>'9'){
if (ch=='-') f=0;
ch=getchar();
}while (ch>='0'&&ch<='9')
x=x*10+ch-'0',ch=getchar();
if (!f) x=-x; return x;
}
inline LL Lin(){
LL x=0; char ch=getchar(); bool f=1;
while (ch<'0'||ch>'9'){
if (ch=='-') f=0;
ch=getchar();
}while (ch>='0'&&ch<='9')
x=x*10ll+(LL)(ch-'0'),ch=getchar();
if (!f) x=-x; return x;
}
inline void add(int u,int v,int cap,LL cost){
e[++num].u=u,e[num].v=v,e[num].cap=cap;
e[++num].u=v,e[num].v=u,e[num].cap=0;
}
inline void pide(int xu){
int i,x=a[xu].x,y;
a[xu].k=0,y=sqrt(x);
for (i=2; i<=sqrt(x); i++){
while (!(x%i)) x/=i,a[xu].k++;
}if (x>1) a[xu].k++;
}
inline bool spfa(){
int i,u,v,h=0,t=1;
for (i=S; i<=T; i++)
vis[i]=0,dis[i]=limit;
LL minn=dis[0];
q[h]=S,dis[S]=0ll,flow[S]=inf,vis[S]=1;
while (h0&&dis[v]minn) return true;
else return false;
}
int main(){
int i,j; n=in(),S=0,T=n+1;
for (i=1; i<=n; i++) a[i].x=in();
for (i=1; i<=n; i++) a[i].y=in();
for (i=1; i<=n; i++) a[i].z=Lin();
for (i=1; i<=n; i++){
pide(i);
}for (i=1; i<=n; i++){
if (a[i].k&1){
for (j=1; j<=n; j++){
if (i==j) continue;
if (!(a[j].k&1)){
if (!(a[i].x%a[j].x)&&a[i].k==a[j].k+1)
if (!(a[j].x%a[i].x)&&a[j].k==a[i].k+1)
}
}
}
}while (spfa()){
if ((sum+dis[T]*flow[T])<0){
ans+=(int)(sum/(-dis[T])); break;
}else {
for (i=T; i!=S; i=e[pre[i]].u){
e[pre[i]].cap-=flow[T];
e[pre[i]^1].cap+=flow[T];
}ans+=flow[T],sum+=dis[T]*flow[T];
}
}printf("%d\n",ans);
return 0;
}``````

T3

Code:

``````#include
#include
#include
#include
#include
#include
using namespace std;
#define N 100010
#define inf 123456789123456789ll
#define LL long long
#define root 1,1,n
#define lch rt<<1,l,mid
#define rch rt<<1|1,mid+1,r
struct E{
int v,next; LL k;
}e[N<<1];
struct Line{
LL k,b;
inline LL F(LL x){
return k*x+b;
}
};
struct Tr{
Line x; LL minn; bool f;
}tr[N<<2];
inline int in(){
int x=0; char ch=getchar(); bool f=1;
while (ch<'0'||ch>'9'){
if (ch=='-') f=0;
ch=getchar();
}while (ch>='0'&&ch<='9')
x=x*10+ch-'0',ch=getchar();
if (!f) x=-x; return x;
}
inline LL Lin(){
LL x=0ll; char ch=getchar(); bool f=1;
while (ch<'0'||ch>'9'){
if (ch=='-') f=0;
ch=getchar();
}while (ch>='0'&&ch<='9')
x=x*10ll+(LL)(ch-'0'),ch=getchar();
if (!f) x=-x; return x;
}
inline void add(int u,int v,LL k){
e[++num].v=v,e[num].k=k;
}
inline void BFS(){
int i,j,u,v,h=0,t=1; q[h]=1,dis[1]=0;
while (h=0; i--){
u=q[i],sz[u]=1,son[u]=0;
v=e[j].v; if (v==fa[u][0]) continue;
sz[u]+=sz[v]; if (sz[son[u]]=0; i--)
if (k&(1<=0; i--)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
if (x==y) return x;
return fa[x][0];
}
inline void push_up(int rt){
tr[rt].minn=min(tr[rt].minn,min(tr[rt<<1].minn,tr[rt<<1|1].minn));
}
inline void build(int rt,int l,int r){
tr[rt].minn=inf,tr[rt].f=0;
if (l==r) return;
int mid=(l+r)>>1;
build(lch),build(rch);
push_up(rt);
}
inline void change(int rt,int l,int r,int ll,int rr,Line x){
if (ll<=l&&r<=rr){
tr[rt].minn=min(tr[rt].minn,min(x.F(Dis[l]),x.F(Dis[r])));
if (!tr[rt].f){
tr[rt].f=1,tr[rt].x=x;
return;
}if (l==r){
if (x.F(Dis[l])>1;
LL k1=x.F(Dis[l]),k2=tr[rt].x.F(Dis[l]);
LL kk1=x.F(Dis[mid]),kk2=tr[rt].x.F(Dis[mid]);
LL kkk1=x.F(Dis[r]),kkk2=tr[rt].x.F(Dis[r]);
if (k1>k2&&kkk1>kkk2) return;
if (k1>1;
if (ll<=mid) change(lch,ll,rr,x);
if (rr>mid) change(rch,ll,rr,x);
push_up(rt);
}
inline LL query(int rt,int l,int r,int ll,int rr){
if (ll<=l&&r<=rr) return tr[rt].minn;
int mid=(l+r)>>1; LL k=inf;
if (tr[rt].f) k=min(k,min(tr[rt].x.F(Dis[max(ll,l)]),tr[rt].x.F(Dis[min(rr,r)])));
if (ll<=mid) k=min(k,query(lch,ll,rr));
if (rr>mid) k=min(k,query(rch,ll,rr));
return k;
}
inline void work_change(int x,int y,LL z,LL zz){
int f=lca(x,y); LL k1,b1,k2,b2;
k1=-z,b1=z*dis[x]+zz;
k2=z,b2=z*(-2*dis[f]+dis[x])+zz;
while (de[top[x]]>de[f]){
change(root,w[top[x]],w[x],(Line){k1,b1});
x=fa[top[x]][0];
}while (de[top[y]]>de[f]){
change(root,w[top[y]],w[y],(Line){k2,b2});
y=fa[top[y]][0];
}if (x!=f) change(root,w[f],w[x],(Line){k1,b1});
else if (y!=f) change(root,w[f],w[y],(Line){k2,b2});
else change(root,w[f],w[f],(Line){k1,b1});
}
inline void work_query(int x,int y){
ans=inf;
while (top[x]!=top[y]){
if (de[top[x]]``````

```Day2 T1 题目大意： 开始有一个空串，n次操作，每次在串的最后新添一个字符，每次操作完后求此时串中不同字串的个数。```

```题解： SA+线段树。对原串建前缀数组，然后问题转变成了每次加入i个前缀，求有多少之前没出现过的。那就可以用线段树维护一下当前rank的前驱和后继，查一下他们之间的lcp，加加减减就好了（zkw好写好调啊）。 Ps.据说是SAM裸题，然而我并不会啊。```

`Code:`

``````#include
#include
#include
#include
#include
#include
using namespace std;
#define N 200010
#define LL long long
int n,m,tot,a[N],sa[N],rank[N],cc[N],h[N],tt[N],height[N<<2],tr[N<<2]; LL ans=0;
inline int in(){
int x=0; char ch=getchar(); bool f=1;
while (ch<'0'||ch>'9'){
if (ch=='-') f=0;
ch=getchar();
}while (ch>='0'&&ch<='9')
x=x*10+ch-'0',ch=getchar();
if (!f) x=-x; return x;
}
inline bool cmp(int x,int y){
return a[x]=1; i--) sa[cc[rank[tt[i]]]--]=tt[i];
for (i=1,m=0; i<=n; i++){
m++,tt[sa[i]]=m;
while (i=1; i--) height[i]=min(height[i<<1],height[i<<1|1]);
}
for (x=x+tot; x; x>>=1) tr[x]=1;
}
inline int Last(int x){
for (x=x+tot; x; x>>=1)
if ((x&1)&&tr[x^1]) break;
for (x=x^1; x>=1)
if ((!(x&1))&&tr[x^1]) break;
for (x=x^1; x>=1,r>>=1){
if (!(l&1)) s=min(s,height[l^1]);
if (r&1) s=min(s,height[r^1]);
}return s;
}
int main(){
n=in(); int i,x,l,r;
for (i=n; i>=1; i--) a[i]=in();
for (i=n; i>=1; i--){
ans+=(LL)(n-i+1),x=rank[i];
if (1<=l&&r<=n) ans+=(LL)query(l,r);
if (1<=l) ans-=(LL)query(l,x);
if (r<=n) ans-=(LL)query(x,r);
printf("%I64d\n",ans);
}return 0;
}``````

```T2 题目大意： 求长度为n的排列中恰好有k个第i位是i的方案数。```

```题解： 考虑f[m]表示一个长度为m排列中m个数全都不在原位的方案数，那一个长度为n(n>m)的排列中恰好有n?m个数在原位的方案是Cmn×f[m]，显然f[m]=(m?1)(f[m?1]+f[m?2])，因为有取模，所以可以预处理出f[n]、1?n的阶乘和1!?n!的逆元，O(n)预处理，O(1)询问。```

`Code:`

``````#include
#include
#include
#include
#include
#include
using namespace std;
#define N 1000000
#define P 1000000007ll
#define LL long long
int n,m; LL fac[N+10],inv[N+10],f[N+10];
inline int in(){
int x=0; char ch=getchar(); bool f=1;
while (ch<'0'||ch>'9'){
if (ch=='-') f=0;
ch=getchar();
}while (ch>='0'&&ch<='9')
x=x*10+ch-'0',ch=getchar();
if (!f) x=-x; return x;
}
inline LL C(int x,int y){
return (((fac[x]*inv[y])%P)*inv[x-y])%P;
}
inline LL qp(LL x,LL y){
LL z=1;
while (y){
if (y&1) z=(z*x)%P;
x=(x*x)%P,y>>=1;
}return z;
}
int main(){
int T=in(),tt,i;
fac[0]=1ll,f[0]=1,f[1]=0,f[2]=1;
for (i=1; i<=N; i++)
fac[i]=fac[i-1]*(LL)i%P;
inv[N]=qp(fac[N],P-2);
for (i=N-1; i>=0; i--)
inv[i]=inv[i+1]*(LL)(i+1)%P;
for (i=3; i<=N; i++)
f[i]=(LL)(i-1)*(f[i-1]+f[i-2])%P;
for (tt=1; tt<=T; tt++){
n=in(),m=in();
printf("%I64d\n",C(n,m)*f[n-m]%P);
}return 0;
}``````

```T3 题目大意： 给出n个数，划分成m块，每块的权值为块内所有数的和，设最小的方差为Ans，求Ans?m2。```

```题解： DP+斜率优化。化式子： 令xx为平均数，s[i]为前i个数的和。 Ans=1m∑mi=1(xi?xx)2 =1m∑mi=1(x2i?2×xi×xx+xx2) =1m∑mi=1(x2i)?1m∑mi=1(2×xi×xx)+xx2 =1m∑mi=1(x2i)?1m×2×s[m]×xx+xx2 =1m∑mi=1(x2i)?2×s[m]2m2+s[m]2m2 =1m∑mi=1(x2i)?s[m]2m2 Ans×m2=m∑mi=1x2i?s[m]2 就是求最小平方和，直接搞斜率优化就好了。```

`Code:`

``````#include
#include
#include
#include
#include
#include
using namespace std;
#define N 3010
#define LL long long
struct Q{
LL x,y;
}q[N<<1];
int n,m,a[N],s[N]; LL f[N][N],ans;
inline int in(){
int x=0; char ch=getchar(); bool f=1;
while (ch<'0'||ch>'9'){
if (ch=='-') f=0;
ch=getchar();
}while (ch>='0'&&ch<='9')
x=x*10+ch-'0',ch=getchar();
if (!f) x=-x; return x;
}
inline void dp(int xu){
int i,h=1,t=1; LL x,y,x1,y1,x2,y2;
q[h].x=(LL)s[xu-1]*2;
q[h].y=f[xu-1][xu-1]+(LL)s[xu-1]*s[xu-1];
for (i=xu; i<=n; i++){
while (h=y) h++;
else break;
}f[xu][i]=q[h].y-q[h].x*(LL)s[i]+(LL)s[i]*(LL)s[i];
x=(LL)s[i]*2,y=f[xu-1][i]+(LL)s[i]*(LL)s[i];
while (h``````