首先每个人肯定每次会选择剩下的数中最大的一些数。
因此可以先排序。
考虑到从小到大dp,类似回溯的过程,f[i]代表剩下i个最小的数先手-后手的最大差值。
有dp方程f[i]=max(a[j+1]-f[j])。
然后可以发现求max(a[j+1]-f[j])只需要每次跟新f值后维护一个最大值就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<algorithm>
#include<memory.h>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
#define maxn 1000010
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }
inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll a[maxn],f[maxn],n,cho;
int main(){
n=read();
For(i,1,n) a[i]=read();
sort(a+1,a+n+1);
f[1]=a[1]; cho=a[1];
For(i,1,n){
f[i]=cho;
cho=max(cho,a[i+1]-f[i]);
}
cho=0;
For(i,1,n) cho=max(cho,f[i]);
writeln(cho);
}

首先考虑这个游戏是nim游戏的变形,若只考虑选出m个,则如果异或值为0,则选m个的人必胜,否则选m个的人必失败,且在失败的情况下回合数是偶数次的。
考虑选n个,若能选出若干个异或值为0,先手必胜,否则先手必败。
因为先手第一次可以选出所有异或值为0的,然后在经过奇数次后翻转了先手和后手的关系,使得剩下的无论怎么选都无法选出。
而如果无法选出,则会在经过偶数次后先手将不能取,最终先手失败。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<algorithm>
#include<memory.h>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll int
#define maxn 100010
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }
inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll a[maxn],n;
bool dfs(ll x,ll used,ll now){
if (x==n+1) return(!now&&used);
if (dfs(x+1,used,now)||dfs(x+1,used+1,now^a[x])) return 1;
return 0;
}
int main(){
ll T=10;
while(T--){
n=read();
For(i,1,n) a[i]=read();
puts(dfs(1,0,0)?"NO":"YES");
}
}

题目要求选一个子序列使相邻2个&不为0,因此只需要二进制位有1位不为0即可。
因此对每个数分解做dp,f[i]代表当前第i位为1且以这个数结尾最长子序列,
转移时枚举为1的每一位i,寻找tmp=max(f[i]),然后跟新每一位f[i]的值为tmp+1即可,同时跟新答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<algorithm>
#include<memory.h>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll int
#define maxn 100010
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }
inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll f[maxn],n,cho,bin[32],ans;
int main(){
bin[0]=1; For(i,1,30) bin[i]=bin[i-1]<<1;
n=read();
while(n--){
ll x=read(),tmp=0;
For(i,0,30) if (x&bin[i]) tmp=max(tmp,f[i]+1);
For(i,0,30) if (x&bin[i]) f[i]=tmp;
ans=max(ans,tmp);
}
writeln(ans);
}

这题首先发现可以用floyed实现,f[x][i][j]代表从房间i到房间j且做k次电梯最少上升多少。
然后发现这个可以倍增实现,有f[x]和f[x]合并为f[x*2]。
先预处理出所有2的幂次的答案,然后倍增判断。
发现这是类似矩阵的东西,可以用类似矩阵乘法的方式实现。

#include<algorithm>
#include<memory.h>
#include<cstdio>
#include<cmath>
#define ll long long
#define maxn 110
#define inf 1000000000000000000LL
#define For(i,x,y)    for(ll i=x;i<=y;++i)
#define FOr(i,x,y)    for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){    ll x=0;char ch=getchar();    while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x;    }
inline void write(ll x){    if (x>=10) write(x/10);    putchar(x%10+'0');    }
void writeln(ll x){    write(x);    puts("");    }
struct data{
    ll a[maxn][maxn];
}mp[maxn];
ll n,m,ans,cnt;
data cheng(data a,data b){
    data tmp;
    For(i,1,n)    For(j,1,n){
        tmp.a[i][j]=-inf;
        For(k,1,n)    tmp.a[i][j]=max(tmp.a[i][j],a.a[i][k]+b.a[k][j]);
    }
    return tmp;
}
bool pd(data mp){
    For(i,1,n)    For(j,1,n)    if (mp.a[1][j]>=m)    return 1;
    return 0;
}
int main(){
    ll T=read();
    while(T--){
        n=read();    m=read();    ans=1;
        For(i,1,n)    For(j,1,n){
            mp[1].a[i][j]=read();
            if (!mp[1].a[i][j])    mp[1].a[i][j]=-inf;
        }
        for(cnt=1;;){
            mp[cnt+1]=cheng(mp[cnt],mp[cnt]);
            if (pd(mp[++cnt]))    break;
        }
        data tmp=mp[1];
        FOr(i,cnt-1,1){
            data tt=cheng(mp[i],tmp);
            if (!pd(tt)){
                tmp=tt;
                ans+=1LL<<(i-1);
            }
        }
        writeln(ans+1);
    }
}

权值线段树水过,也可以排序后二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<algorithm>
#include<memory.h>
#include<cstdio>
#include<cmath>
#define maxn 3300010
#define ll long long
#define For(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
inline int read(){ int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll ls[maxn],rs[maxn],n,q,sz,size[maxn],root;
void insert(ll l,ll r,ll &p,ll v){
if (!p) p=++sz;
if (l==r){ size[p]++; return; }
ll mid=(l+r)>>1;
if (v<=mid) insert(l,mid,ls[p],v);
else insert(mid+1,r,rs[p],v);
size[p]=size[ls[p]]+size[rs[p]];
}
ll query(ll l,ll r,ll p,ll s,ll t){
if (!p) return 0;
if (l==s&&r==t) return size[p];
ll mid=(l+r)>>1;
if (t<=mid) return query(l,mid,ls[p],s,t);
else if (s>mid) return query(mid+1,r,rs[p],s,t);
else return query(l,mid,ls[p],s,mid)+query(mid+1,r,rs[p],mid+1,t);
}
int main(){
n=read(); q=read();
For(i,1,n){
ll x=read();
insert(0,1000000000,root,x);
}
while(q--){
ll x=read(),y=read();
writeln(query(0,1000000000,root,0,y)-query(0,1000000000,root,0,x-1));
}
}

先考虑对询问的子树分块,对于询问的每个块都暴力预处理出包含了每个节点几次,预处理(nsqrt(n))。
对于每次询问,都要询问sqrt(n)个块,边界询问sqrt(n)棵子树。
考虑修改单棵子树,只考虑对询问答案块的影响,要修改sqrt(n)个块,修改n棵子树的和。
然后我们为了平衡复杂度,需要一个能O(1)查询单棵子树的和,sqrt(n)修改所有子树的和。
可以考虑dfs序。
如果用树状数组维护,两个操作都是log(n)的,复杂度会退化到nsqrt(n*log(n))。
可以考虑对dfs序进行分块,这样复杂度就是正确的了。
要注意常数。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<algorithm>
#include<cstdio>
#include<cmath>
#define maxn 200020
#define ll long long
#define For(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
inline int read(){ int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(unsigned ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
int n,m;
struct ask_tree{//L,R代表欧拉序,ls、rs分别代表欧拉序每个块的左端和右端
ll mark[maxn],Mark[maxn],sum[maxn];
int block,root,tot,cnt,v[maxn],head[maxn],next[maxn],vet[maxn],L[maxn],R[maxn],ls[maxn],rs[maxn],belong[maxn];
inline void insert(int x,int y){
next[++tot]=head[x]; head[x]=tot; vet[tot]=y;
}
inline void dfs(int x,int pre){
L[x]=cnt;
for(int i=head[x];i;i=next[i])
if (vet[i]!=pre) dfs(vet[i],x),sum[x]+=sum[vet[i]];
R[x]=cnt++;
}
inline void build(){
dfs(root,-1); int t=sqrt(n); block=n/t; block+=block*t!=n;
For(i,1,block) ls[i]=(i-1)*t+1,rs[i]=min(n,i*t);
For(i,1,block) For(j,ls[i],rs[i]) belong[j]=i;
}
inline ll ask(int x){
return Mark[R[x]]-Mark[L[x]-1]+mark[belong[R[x]]]-mark[belong[L[x]-1]]+sum[x];
}
inline void add(int x,int v){
For(i,R[x],rs[belong[R[x]]]) Mark[i]+=v;
For(i,belong[R[x]]+1,block) mark[i]+=v;
}
}tree_;
struct qqq{
int belong[maxn],L[maxn],R[maxn],block,cho[400][maxn/2];
ll mark[maxn];
unsigned ll answ[maxn];
inline void dfs1(int belong,int x,int pre,int sum_mark){
sum_mark+=mark[x]; mark[x]=0; cho[belong][x]=sum_mark;
for(ll i=tree_.head[x];i;i=tree_.next[i])
if (tree_.vet[i]!=pre) dfs1(belong,tree_.vet[i],x,sum_mark);
}
inline unsigned ll query(int x,int y){
int l=belong[x],r=belong[y]; unsigned ll ans=0;
if (l==r){
For(i,x,y) ans+=tree_.ask(i);
return ans;
}
For(i,x,R[l]) ans+=tree_.ask(i);
For(i,L[r],y) ans+=tree_.ask(i);
l++; r--;
For(i,l,r) ans+=answ[i];
return ans;
}
inline void change(int x,int v){
For(i,1,block) answ[i]+=(ll)cho[i][x]*v;
}
inline void build(){
int now=0;
while(now<n){
L[++block]=now+1;
R[block]=min(n,(now+=347));
}
For(i,1,block){
For(j,L[i],R[i]) mark[j]=1,belong[j]=i,answ[i]=answ[i]+tree_.sum[j];
dfs1(i,tree_.root,-1,0);
}
}
}que;
int main(){
n=read(); m=read();
For(i,1,n) tree_.sum[i]=tree_.v[i]=read();
For(i,1,n){
ll x=read(),y=read();
if (!x||!y) tree_.root=x+y;
else tree_.insert(x,y),tree_.insert(y,x);
}
tree_.build(); que.build();
while(m--){
ll opt=read(),x=read(),y=read();
if (opt==1) que.change(x,y-tree_.v[x]),tree_.add(x,y-tree_.v[x]),tree_.v[x]=y;
else printf("%llu\n",que.query(x,y));
}
}

可以发现答案为求i=a..c,j=b..d,k=1..n,sum(a[i][k]*b[k][j])。
然后可以把式子化开发现答案可化简为sum(a[i][k])*sum(b[k][j]),可以分开先预处理出sum(a[i][k])和sum(b[k][j]),然后每次询问只需要枚举k就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<algorithm>
#include<memory.h>
#include<cstdio>
#include<cmath>
#define ll long long
#define maxn 2010
#define For(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll n,q,a[maxn][maxn],b[maxn][maxn];
int main(){
n=read(); q=read();
For(i,1,n) For(j,1,n){ a[i][j]=read(); a[i][j]+=a[i-1][j]; }
For(i,1,n) For(j,1,n){ b[i][j]=read(); b[i][j]+=b[i][j-1]; }
while(q--){
ll ans=0,x1=read(),y1=read(),x2=read(),y2=read();
if (x1>x2) swap(x1,x2);
if (y1>y2) swap(y1,y2);
For(k,1,n) ans+=(a[x2][k]-a[x1-1][k])*(b[k][y2]-b[k][y1-1]);
writeln(ans);
}
}

首先这题可以考虑每个数是两个数gcd的次数,
可以枚举最大公约数i,若gcd(a,b)=i,则gcd(a/i,b/i)=1。
因此i出现为1..n/i范围内互质数对数。
考虑一个数x,可以只考虑比它小的互质数,发现就是phi(i)。
发现所求值类似sum(phi[j])(j=1..n/i)。
但是还要考虑比它大的以及1,因此为sum(phi[j])*(sum[phi[j]])/2-1。
sum可以预处理出。
答案为i=1..n,j=1..n/i phi[i]*sum[n/i]。
发现对于i<=sqrt(n)部分n/i差别都很大可以暴力求,
而其余部分很多重复n/i<=sqrt(n),因此也可以暴力求。
因此对于每个询问只需要sqrt(n)的时间得出答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<algorithm>
#include<memory.h>
#include<cstdio>
#include<cmath>
#define ll long long
#define maxn 10000010
#define For(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll n,pri[maxn],ans,phi[maxn],sum[maxn],cnt;
bool mark[maxn];
void init(){
For(i,2,n){
if (!mark[i]) pri[++pri[0]]=i,phi[i]=i-1;
for(ll j=1;j<=pri[0]&&i*pri[j]<=n;++j){
mark[i*pri[j]]=1;
if (!(i%pri[j])){
phi[i*pri[j]]=phi[i]*pri[j];
break;
}
phi[i*pri[j]]=phi[i]*(pri[j]-1);
}
}
}
ll ask(ll n){
ll answ=0;
for(ll i=1,j;i<=n;i=j+1){
ll p=n/i;
j=n/p;
answ+=(sum[j]-sum[i-1])*sum[p];
}
return answ;
}
int main(){
unsigned long long ans=0;
n=10000000;
init();
phi[1]=sum[1]=1;
For(i,2,n) sum[i]=sum[i-1]+phi[i];
ll T=read();
while(T--){
ll n=read(),ans=0;
writeln(ask(n)*2-sum[n]);
}
}

性质1:可以证明改变强制的顺序对答案无关。
先考虑只有强制的情况。
若一号和二号原来一号和二号各有a,b个,a/(a+b)概率选a,b/(a+b)概率选b。
第一次选1,第二次选2:a/(a+b)*b/(a+b+1)
第一次选2,第二次选1:b/(a+b)*a/(a+b+1)
可以发现改变顺序对答案没有影响。
因为分母是一定的,对于每种球的分子也是可以确定的,因此可以任意改变顺序。

性质2:再考虑没有强制要求的时候是不会对概率造成影响的。
假设原来一号和二号各有a,b个,a/(a+b)概率选a,b/(a+b)概率选b,选完后选一号概率为:a/(a+b)*(a+d)/(a+b+d)+b/(a+b)*a/(a+b+d)。
a/(a+b)和a/(a+b)*(a+d)/(a+b+d)+b/(a+b)*a/(a+b+d)都乘(a+b)*(a+b+d),都得到a^2+a*b+a*d。
因此不会后面的概率造成影响。
因此可以将所有的强制都移动到最前面。

其实还可以把随机看成很多条支路,把所有支路根据性质1都移动最后。。

#include<algorithm>
#include<memory.h>
#include<cstdio>
#define maxn 100010
#define ll long long
#define For(i,x,y)    for(ll i=x;i<=y;++i)
using namespace std;
inline ll read(){    ll x=0;char ch=getchar();    while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x;    }
inline void write(ll x){    if (x>=10) write(x/10);    putchar(x%10+'0');    }
void writeln(ll x){    write(x);    puts("");    }
ll mark[maxn],pri[maxn],a[maxn],t,n,d,answ[maxn],tot,ans1[maxn],ans2[maxn];
void init(){
    For(i,2,100000){
        if (!mark[i])    pri[++pri[0]]=i;
        for(ll j=1;j<=pri[0]&&i*pri[j]<=100000;j++){
            mark[i*pri[j]]=1;
            if (!(i%pri[j]))    break;
        }
    }
}
void mul(ll x,ll v){
    For(i,1,pri[0])
    while (!(x%pri[i]))    x/=pri[i],answ[i]+=v;
}
void cheng(ll a[],ll v){
    For(i,1,a[0])    a[i]*=v;
    For(i,1,a[0]){
        a[i+1]+=a[i]/10;
        a[i]%=10;
        if (a[i+1])    a[0]=max(a[0],i+1);
    }
}
void print(ll a[]){
    while(a[0])    write(a[a[0]--]);
}
int main(){
    ans1[0]=ans1[1]=ans2[0]=ans2[1]=1;
    init();
    t=read();    n=read();    d=read();
    For(i,1,t)    a[i]=read(),tot+=a[i];
    while(n--){
        ll x=read(),y=read();
        mul(a[y],-1);    mul(tot,1);
        tot+=d;    a[y]+=d;
    }
    For(i,1,pri[0]){
        while(answ[i]>0)    cheng(ans2,pri[i]),answ[i]--;
        while(answ[i]<0)    cheng(ans1,pri[i]),answ[i]++;
    }
    print(ans1);    putchar('/');    print(ans2);
}

首先先要判断图是不是仙人掌,可以建出dfs树,每次遇到反向边都暴力往回找并且标记,如果一个点被标记2次说明无解。
考虑到给你的一棵仙人掌中,如果存在环,显然不会存在跨越环上两个不同点的边,因此可以把所有环都拆掉,然后就变成了一片森林,只需要计算出每棵树的答案最后相乘就可以了。
考虑到一个性质,仙人掌的环不能有重边,可以考虑覆盖仙人掌的所有边,将不选改为覆盖单条边。
假设开始时所有的边都已经被覆盖,我们只需要考虑将哪些边连接起来,f[i]代表一个度数为i点连接的边有几种方式连接起来。
考虑从i-1转移到i,新加入一条边需要分2种情况讨论。
1:假设不与之前的边连接。显然答案为f[i-1]。
2:与之前的边连接,显然有i-1中方式,然后其余的i-2个点随意,答案为f[i-2]。
考虑边界f[0]=f[1]=1,f数组可以预处理出,问题已经得到圆满解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<algorithm>
#include<memory.h>
#include<cstdio>
#include<cmath>
#define ll long long
#define maxn 1000010
#define zyy 998244353
#define For(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll head[maxn],next[maxn],vet[maxn],d[maxn],cnt,tot,dfn[maxn],fa[maxn],f[maxn],ans;
bool rev[maxn];
void insert(ll x,ll y){
next[++tot]=head[x]; head[x]=tot; vet[tot]=y;
}
bool dfs(ll x){
dfn[x]=++cnt;
for(ll i=head[x],t;i;i=next[i])
if (!dfn[vet[i]]){
fa[vet[i]]=x;
if (dfs(vet[i])) return 1;
}else if (dfn[vet[i]]>dfn[x])
for(t=vet[i],d[x]-=2;t!=x;rev[t]=1,d[t]-=2,t=fa[t])
if (rev[t]) return 1;
return 0;
}
int main(){
f[0]=f[1]=1; For(i,2,500000) f[i]=(f[i-2]*(i-1)+f[i-1])%zyy;
ll T=read();
while(T--){
ll n=read(),m=read();
For(i,1,n) head[i]=dfn[i]=d[i]=rev[i]=0;
tot=0; cnt=0; ans=1;
while(m--){
ll x=read(),y=read();
d[x]++; d[y]++;
insert(x,y); insert(y,x);
}
if (dfs(1)) puts("0");
else{
For(i,1,n) ans=ans*f[d[i]]%zyy;
writeln(ans);
}
}
}