每次可以随机1个1*n的矩阵x,根据交换率若a*b=c则x*a*b=x*c。
最后可能会出现答案不对的情况,可以多随机几次。

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
#include<algorithm>
#include<memory.h>
#include<cstdio>
#define maxn 1010
#define ll int
#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 a[2][maxn],b[2][maxn],x[2][maxn],n;
int main(){
For(i,1,1000) x[0][i]=rand(),x[1][i]=rand();
while(scanf("%d",&n)!=EOF&&n){
memset(a,0,sizeof a);
memset(b,0,sizeof b);
For(i,1,n) For(j,1,n){
ll key=read();
a[0][j]+=x[0][i]*key;
a[1][j]+=x[1][i]*key;
}
For(i,1,n) For(j,1,n){
ll key=read();
b[0][j]+=a[0][i]*key;
b[1][j]+=a[1][i]*key;
}
For(i,1,n) For(j,1,n){
ll key=read();
b[0][j]-=x[0][i]*key;
b[1][j]-=x[1][i]*key;
}
bool flag=1;
For(i,1,n) if (b[0][i]||b[1][i]){
puts("No"); flag=0; break;
}
if (flag) puts("Yes");
}
}

每次可以随机1个1*n的矩阵x,根据交换率若a*b=c则x*a*b=x*c。
最后可能会出现答案不对的情况,可以多随机几次。

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
#include<algorithm>
#include<memory.h>
#include<cstdio>
#define maxn 510
#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 a[2][maxn],b[2][maxn],x[2][maxn],n;
int main(){
n=read();
For(i,1,n) x[0][i]=rand()%10000+1,x[1][i]=rand()%10000+1;
For(i,1,n) For(j,1,n){
ll key=read();
a[0][j]+=x[0][i]*key;
a[1][j]+=x[1][i]*key;
}
For(i,1,n) For(j,1,n){
ll key=read();
b[0][j]+=a[0][i]*key;
b[1][j]+=a[1][i]*key;
}
For(i,1,n) For(j,1,n){
ll key=read();
b[0][j]-=x[0][i]*key;
b[1][j]-=x[1][i]*key;
}
For(i,1,n) if (b[0][i]||b[1][i]){
puts("No"); return 0;
}
puts("Yes");
}

性质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);
}

t[a][b][c][d][k]代表矩阵[a..b][c..d]中划分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
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll int
#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(""); }
double p,t[15][15][15][15][15];
ll a[15][15],s[15][15];
ll n,m,k;
double dfs(ll a,ll b,ll c,ll d,ll k){
double &res=t[a][b][c][d][k];
if (res!=-1) return res;
if (k==0){
res=s[b][d]+s[a-1][c-1]-s[a-1][d]-s[b][c-1];
res=(res-p)*(res-p);
return res;
}
res=1e9;
For(i,a+1,b) For(j,0,k-1) res=min(res,dfs(a,i-1,c,d,j)+dfs(i,b,c,d,k-j-1));
For(i,c+1,d) For(j,0,k-1) res=min(res,dfs(a,b,c,i-1,j)+dfs(a,b,i,d,k-j-1));
return res;
}
int main(){
n=read(); m=read(); k=read();
For(i,1,n) For(j,1,m) a[i][j]=read(),p+=a[i][j];
p=(double)p/k;
For(a,0,10) For(b,0,10) For(c,0,10) For(d,0,10) For(l,0,10) t[a][b][c][d][l]=-1;
For(i,1,n) For(j,1,m) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
dfs(1,n,1,m,k-1);
printf("%.2lf",sqrt(t[1][n][1][m][k-1]/k));
}

可以先每行用单调对列处理出每个点的前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
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
var
tail,head,a,b,n,i,j,ans:longint;
c,f,g,g_:array[-1..1001,-1..1001] of longint;
q,pos:array[-1..1001] of longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x)
else exit(y);
end;
begin
readln(A,b,n);
for i:=1 to a do
begin
for j:=1 to b do read(c[i,j]);
readln;
end;
readln;
for i:=1 to a do
begin
head:=0; tail:=0;
fillchar(q,sizeof(q),0);
fillchar(pos,sizeof(pos),0);
for j:=1 to b do
begin
if (j-pos[head])>=n then
begin
q[head]:=0;
inc(head);
end;
while (q[tail]<=c[i,j]) and (tail>=head) do dec(tail);
inc(tail);
q[tail]:=c[i,j];
pos[tail]:=j;
f[i,j]:=q[head];
end;
end;
for j:=1 to b do
begin
head:=0; tail:=0;
fillchar(q,sizeof(q),0);
fillchar(pos,sizeof(pos),0);
for i:=1 to a do
begin
if (i-pos[head])>=n then
begin
q[head]:=0;
inc(head);
end;
while (q[tail]<=f[i,j]) and (tail>=head) do dec(tail);
inc(tail);
q[tail]:=f[i,j];
pos[tail]:=i;
g[i,j]:=q[head];
end;
end;
fillchar(f,sizeof(f),$7f);
for i:=1 to a do
begin
head:=0; tail:=0;
fillchar(q,sizeof(q),$7f);
fillchar(pos,sizeof(pos),0);
for j:=1 to b do
begin
if (j-pos[head])>=n then
begin
q[head]:=maxlongint;
inc(head);
end;
while (q[tail]>=c[i,j]) and (tail>=head) do dec(tail);
inc(tail);
q[tail]:=c[i,j];
pos[tail]:=j;
f[i,j]:=q[head];
end;
end;
ans:=maxlongint;
for j:=1 to b do
begin
head:=0; tail:=0;
fillchar(q,sizeof(q),$7f);
fillchar(pos,sizeof(pos),0);
for i:=1 to a do
begin
if (i-pos[head])>=n then
begin
q[head]:=maxlongint;
inc(head);
end;
while (q[tail]>=f[i,j]) and (tail>=head) do dec(tail);
inc(tail);
q[tail]:=f[i,j];
pos[tail]:=i;
g_[i,j]:=q[head];
end;
end;
{for i:=1 to a do
begin
for j:=1 to b do write(g[i,j],' ');
writeln;
end;
writeln;
writeln;
for i:=1 to a do
begin
for j:=1 to b do write(g_[i,j],' ');
writeln;
end; }
for i:=n to a do
for j:=n to b do
ans:=min(ans,g[i,j]-g_[i,j]);
writeln(ans);
end.

lis nlogn做法。
先离散化,从左往右枚举,每次2分在答案的哪个位置,如果超出当前答案则答案+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
40
41
42
43
44
45
46
47
48
49
50
var
a,b,f:array[0..10000] of longint;
n,pos,tot,i,x,last,m:longint;
function find(X:longint):longint;
var
l,r,mid:longint;
begin
l:=1; r:=tot+1;
while l<r do
begin
mid:=(l+r) div 2;
if b[mid]>x then l:=mid+1
else r:=mid;
end;
exit(l);
end;
procedure solve(x:longint);
var
i:longint;
begin
last:=0;
for i:=1 to n do
if(f[i]>=x) and (A[i]>last) then
begin
write(A[i]);
if x<>1 then write(' ');
last:=a[i];
dec(X);
if x=0 then break;
end;
writeln;
end;
begin
readln(n);
for i:=1 to n do read(a[i]);
for i:=n downto 1 do
begin
pos:=find(a[i]);
if pos>tot then inc(tot);
f[i]:=pos;
b[pos]:=a[i];
end;
readln(m);
for i:=1 to m do
begin
read(X);
if x<=tot then solve(X)
else writeln('Impossible');
end;
end.

设1——n号分别由ai个。
设1号给2号x1个,2号给3号x2个……
ave为平均数
可得a1-xn+x1=ave
a2-x1+x2=ave
a3-x2+x3=ave
……
但是有一个式子在最后可以发现是没用的。
注意到答案为sum(abs(x[i])),
可以发现所有的xi-x(i-1)=ave-ai(当i-1==0则i=n)
那么只需要确定x1其他都能确定。
设ci=x1-xi,
则答案为abs(x1)+abs(x1-c2)+abs(x1-c3)+…+abs(x1-cn)。
可以把这个转化为在直线上选一个点使得其他n-1个点到当前点距离最小。
排序后取中位数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#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 n,a[1000001],c[1000001],ave,sum;
int main(){
n=read();
For(i,1,n) a[i]=read(),sum+=a[i];
ave=sum/n;
For(i,2,n) c[i]=c[i-1]+a[i]-ave;
sort(c+1,c+n+1);
ll ans=0,mid=c[(n>>1)+1];
For(i,1,n) ans+=abs(c[i]-mid);
writeln(ans);
}

设1——n号分别由ai个。
设1号给2号x1个,2号给3号x2个……
ave为平均数
可得a1-xn+x1=ave
a2-x1+x2=ave
a3-x2+x3=ave
……
但是有一个式子在最后可以发现是没用的。
注意到答案为sum(abs(x[i])),
可以发现所有的xi-x(i-1)=ave-ai(当i-1==0则i=n)
那么只需要确定x1其他都能确定。
设ci=x1-xi,
则答案为abs(x1)+abs(x1-c2)+abs(x1-c3)+…+abs(x1-cn)。
可以把这个转化为在直线上选一个点使得其他n-1个点到当前点距离最小。
排序后取中位数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#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 n,a[1000001],c[1000001],ave,sum;
int main(){
n=read();
For(i,1,n) a[i]=read(),sum+=a[i];
ave=sum/n;
For(i,2,n) c[i]=c[i-1]+a[i]-ave;
sort(c+1,c+n+1);
ll ans=0,mid=c[(n>>1)+1];
For(i,1,n) ans+=abs(c[i]-mid);
writeln(ans);
}

第一问可以二分出答案。
对于第二问,可以枚举m,注意每层暴力枚举是n^2*m。注意到转移有单调性,可以用2个指针l,r表示l——r区间可以转移到i。
很容易得出答案。

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll int
#define mod 10007
#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[50001],sum[50001],f[2][50005],q[50005],ans2,l,r,ans,n,m;
bool judge(ll x){
ll tmp=0,now=0;
For(i,1,n){
now+=a[i];
if (now>x) now=a[i],tmp++;
}
return tmp<=m;
}
void solve(){
f[0][0]=1;
ll pre,cur,tot;
For(i,1,m){
pre=i&1; cur=pre^1;
ll l=1,r=1;
q[1]=0; tot=f[cur][0];
For(j,1,n){
while(l<=r&&sum[j]-sum[q[l]]>ans)
tot=(tot-f[cur][q[l++]]+mod)%mod;
f[pre][j]=tot;q[++r]=j;
tot=(tot+f[cur][j]+mod)%mod;
}
FOr(j,n-1,1){
if(sum[n]-sum[j]>ans)break;
ans2=(ans2+f[pre][j]+mod)%mod;
}
memset(f[cur],0,sizeof(f[cur]));
}
writeln(ans2);
}
int main(){
n=read(); m=read();
For(i,1,n){
a[i]=read();
l=max(l,a[i]);
sum[i]=sum[i-1]+a[i];
}
r=sum[n];
while (l<=r){
ll mid=(l+r)>>1;
if (judge(mid)) { ans=mid; r=mid-1; }
else l=mid+1;
}
printf("%d ",ans);
solve();
}

可以先预处理出所有情况的答案,然后容斥。
也可以用背包,可以利用前缀和的思想优化。

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define inf 2000000000
#define ll long long
#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 c[100000],d[100000],f[100001],ans,n;
void dfs(ll x,ll k,ll s){
if (s<0) return;
if (x==5){
ans+=(k%2?-1:1)*f[s];
return;
}
dfs(x+1,k,s); dfs(x+1,k+1,s-(d[x]+1)*c[x]);
}
int main(){
For(i,1,4) c[i]=read();
f[0]=1; n=read();
For(i,1,4) For(j,0,100000-c[i]) f[j+c[i]]=f[j+c[i]]+f[j];
while(n--){
For(j,1,4) d[j]=read();
ll x=read(); ans=0;
dfs(1,0,x);
writeln(ans);
}
}