| Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| 6/10 | Ø | Ø | . | Ø | . | O | . | O | . | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
有一个长为$n$的环，从$0$开始每次等概率向左向右移动一格。当所有格子被访问过至少一次后，结束移动，问停留在$m$的概率是多少。
解题思路
边界情况：$m=0$时：$n\neq 1$时概率为$0$，否则概率为$1$。
一般情况：打表可以知道，任何一点的概率均为$\frac{1}{n-1}$。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef long long ll;
using namespace std;
int mod=1000000007;
int qp(int x,int p){
int ans=1;
for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;
return ans;
}
int main(){
int i,T,n,m;
scanf("%d",&T);
ll ans=1;
while(T--){
scanf("%d%d",&n,&m);
if(n==1&&!m)printf("%lld\n",ans);
else if(m)printf("%lld\n",ans=ans*qp(n-1,mod-2)%mod);
else printf("%lld\n",ans=0);
}
return 0;
}
B
题目描述
从$0$开始沿着数轴向前走，每次等概率走$[1,2…k]$步，问经过$n$的概率。如果$n=-1$，求出$n$趋向正无穷时经过$n$的概率。
解题思路
递推一下可以发现，$p_0=1,p_i=\frac{p_{i-1}+p_{i-2}+…+p_{i-k}}{k}$，这是一个很明显的线性递推，套上板子就行了。
$n$趋向正无穷时概率相同，故在讨论无穷下的概率时可认为经过任意点的概率相同。由于走$1…k$步概率相同，我们可以假设走了$t$次$1$步，$t$次$2$步…$t$次$k$步，那么最后到达的位置是$\frac{tk(k+1)}2$，而走过的点数是$tk$，故经过某点的概率为$\frac{tk}{\frac{tk(k+1)}2}=\frac2{k+1}$。也可打表找规律。
AC代码
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
typedef long long ll;
using namespace std;
struct comp{
double x,y;
comp():x(0),y(0){}
comp(const double &_x,const double &_y):x(_x),y(_y){}
};
comp operator+(const comp &a,const comp &b){return comp(a.x+b.x,a.y+b.y);}
comp operator-(const comp &a,const comp &b){return comp(a.x-b.x,a.y-b.y);}
comp operator*(const comp &a,const comp &b){return comp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
comp conj(const comp &a){return comp(a.x,-a.y);}
double PI=acos(-1);
comp w[M+5];
int rev[M+5];
int lim,mx,mod;
void fft(comp *a,int n){
int i,j,k,lyc;
for(i=0;i<n;i++)if(i<rev[i]) swap(a[i],a[rev[i]]);
for(i=2,lyc=n>>1;i<=n;i<<=1,lyc>>=1)
for(j=0;j<n;j+=i){
comp *l=a+j,*r=a+j+(i>>1),*p=w;
for(k=0;k<(i>>1);k++){
comp tmp=*r**p;
*r=*l-tmp,*l=*l+tmp;
++l,++r,p+=lyc;
}
}
}
void fft_prepare(){
int i;
for(i=0;i<lim;i++)rev[i]=rev[i>>1]>>1|((i&1)<<(mx-1));
for(i=0;i<lim;i++)w[i]=comp(cos(2*PI*i/lim),sin(2*PI*i/lim));
}
void conv(int *x,int *y,int *z,int n,int m,int mod){
int i,j;
static comp ta[M+5],tb[M+5],a[M+5],b[M+5];
static int X[M+5],Y[M+5];
for(i=0;i<n;i++)X[i]=(x[i]+mod)%mod;
for(;i<lim;i++)X[i]=0;
for(i=0;i<m;i++)Y[i]=(y[i]+mod)%mod;
for(;i<lim;i++)Y[i]=0;
for(i=0;i<lim;i++){
ta[i]=comp(X[i]&32767,X[i]>>15);
tb[i]=comp(Y[i]&32767,Y[i]>>15);
}
fft(ta,lim);fft(tb,lim);
for(i=0;i<lim;i++){
j=(lim-i)%lim;
comp da,db,dc,dd;
da=(ta[i]+conj(ta[j]))*comp(0.5,0);
db=(ta[i]-conj(ta[j]))*comp(0,-0.5);
dc=(tb[i]+conj(tb[j]))*comp(0.5,0);
dd=(tb[i]-conj(tb[j]))*comp(0,-0.5);
a[j]=da*dc+da*dd*comp(0,1);
b[j]=db*dc+db*dd*comp(0,1);
}
fft(a,lim);fft(b,lim);
for(i=0;i<lim;i++){
ll da,db,dc,dd;
da=(ll)(a[i].x/lim+0.5)%mod;
db=(ll)(a[i].y/lim+0.5)%mod;
dc=(ll)(b[i].x/lim+0.5)%mod;
dd=(ll)(b[i].y/lim+0.5)%mod;
z[i]=(((da+((db+dc)<<15)+(dd<<30))%mod)+mod)%mod;
}
}
int qpow(ll x,int p){
int ans=1;
for(;p;p>>=1,x=x*x%mod)if(p&1)ans=ans*x%mod;
return ans;
}
void polyinv(int *A,int *ans,int n){
static int B[2][M+5];
int bas,cur,i;
memset(B,0,sizeof(B));
B[0][0]=qpow(A[0],mod-2);
for(mx=2,bas=1,lim=4,cur=1;bas<n*2;mx++,lim<<=1,cur^=1,bas<<=1){
fft_prepare();
memset(B[cur],0,sizeof(B[cur]));
for(i=0;i<bas;i++)B[cur][i]=(ll)B[cur^1][i]*2%mod;
conv(B[cur^1],B[cur^1],B[cur^1],bas,bas,mod);
conv(B[cur^1],A,B[cur^1],bas,bas,mod);
for(i=0;i<bas;i++)B[cur][i]=((ll)B[cur][i]-B[cur^1][i]+mod)%mod;
}
for(i=0;i<n;i++)ans[i]=(B[cur^1][i]+mod)%mod;
}
int flag;
void polydiv(int *a,int *b,int *H,int *R,int n,int m){
int i;
static int rF[M+5],rG[M+5],t1[M+5];
memset(t1,0,sizeof(int)*n);
for(i=0;i<=n;i++)rF[n-i]=a[i];
if(!flag){
flag=1;
for(i=0;i<=m;i++)rG[m-i]=b[i];
polyinv(rG,rG,n-m+1);
}
mx=0,lim=1;while(lim<n<<1)lim<<=1,mx++;
fft_prepare();
conv(rF,rG,H,n,n,mod);
reverse(H,H+n-m+1);
for(i=n-m+1;i<=n;i++)H[i]=0;
mx=0,lim=1;while(lim<n+m)lim<<=1,mx++;
fft_prepare();
conv(b,H,t1,m,n,mod);
for(i=0;i<m;i++)R[i]=((ll)a[i]-t1[i]+mod)%mod;
for(;i<=n;i++)R[i]=0;
}
int a[M+5],g[M+5];
int D[M+5];
int res[M+5],bas[M+5],k;
ll n;
void mtmul(int *a,int *b){
mx=0,lim=1;
while(lim<k*2)lim<<=1,mx++;
fft_prepare();
conv(a,b,a,k,k,mod);
polydiv(a,g,D,a,k*2-2,k);
}
void qpow(ll x){
res[0]=bas[1]=1;
for(;x;x>>=1,mtmul(bas,bas))
if(x&1)mtmul(res,bas);
}
signed main(){
int i,j,T;
ll x;
mod=1000000007;
scanf("%lld",&T);
while(T--){
flag=0;
scanf("%lld%lld",&k,&n);
if(k==1){
printf("1\n");
continue;
}
if(n==-1){
printf("%lld\n",2*qpow(k+1,mod-2)%mod);
continue;
}
ll invk=qpow(k,mod-2);
memset(a,0,sizeof(a));
memset(g,0,sizeof(g));
g[k]=mod-1;
for(i=1;i<=k;i++)g[k-i]=invk;
a[0]=1;
for(i=1;i<k;i++){
for(j=0;j<i;j++)(a[i]+=a[j])%=mod;
a[i]=a[i]*invk%mod;
}
if(n<k){
printf("%lld\n",a[n]);
continue;
}
memset(res,0,sizeof(res));
memset(bas,0,sizeof(bas));
qpow(n);
ll ans=0;
for(i=0;i<k;i++)(ans+=(ll)a[i]*res[i])%=mod;
printf("%lld\n",ans);
}
return 0;
}
C
题目描述
解题思路
AC代码
2
D
题目描述
给一个图，找到第$k$小团。
解题思路
先对权值排序，建立堆，每次的操作有两种，在最后插入新元素，或者将最后的元素替换掉。枚举状态即可。
AC代码
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
typedef long long ll;
using namespace std;
char a[N];
int n,k,tot;
pair<ll,int>p[N];
bitset<N>g[N],ith[M];//ith[id]:removing last, what can be added
struct tp{
ll w;int id,last;
bool operator<(const tp&a)const{return w>a.w;}
};
priority_queue<tp>Q;
int main(){
int i,j;
scanf("%d%d",&n,&k);
for(i=0;i<n;i++)scanf("%d",&p[i].f),p[i].s=i;
for(i=0;i<n;i++){
scanf("%s",a);
for(j=0;j<n;j++)if(a[j]=='1')g[i][j]=1;else g[i][j]=0;
}
sort(p,p+n);
if(!k--)return printf("0"),0;//empty set
Q.push((tp){p[0].f,0,0});
for(i=0;i<n;i++)ith[0][i]=1;
while(!Q.empty()){
tp t=Q.top();Q.pop();
ll val=t.w;int id=t.id,last=t.last;
if(!--k)return printf("%lld",val),0;
for(i=last+1;i<n;i++){//add i, del last, id remain
if(ith[id][p[i].s]){
Q.push((tp){val+p[i].f-p[last].f,id,i});
break;
}
}
ith[++tot]=ith[id]&g[p[last].s];//find what can be added
for(i=last+1;i<n;i++){//add i
if(ith[tot][p[i].s]){
Q.push((tp){val+p[i].f,tot,i});
break;
}
}
}
puts("-1");
return 0;
}
E
题目描述
解题思路
AC代码
2
F
题目描述
给定$2n$个人，要求分成两组，使得权值最大。权值的大小为任意不属于同一组的$i,j$，其$v_{ij}$之和。
解题思路
$n$大小在$14$，可以暴力$O(C_{28}^{14}\cdot 14^2)$搜出。
AC代码
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
typedef long long ll;
using namespace std;
int n,v[N][N];
ll ans,s[N],sum;
int seq[N];
void dfs(int mn,int dep){
int i,j;
if(dep==n){
if(ans<sum)ans=sum;
return;
}
for(i=mn;i<=n+1+dep;i++){
seq[dep]=i;
ll tmp=0;
for(j=0;j<dep;j++)tmp-=2*v[i][seq[j]];
tmp+=s[i];
sum+=tmp;
dfs(i+1,dep+1);
sum-=tmp;
}
}
int main(){
int i,j;
scanf("%d",&n);
for(i=1;i<=n*2;i++)
for(j=1;j<=n*2;j++){
scanf("%d",&v[i][j]);
if(i^j)s[i]+=v[i][j];
}
dfs(1,0);
printf("%lld",ans);
return 0;
}
G
题目描述
解题思路
AC代码
2
H
题目描述
给一个$01$矩阵，求出全由$1$构成的第二大矩阵。
解题思路
求最大矩阵是扫描线板子题，求第二大稍微改一下即可。
AC代码
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
using namespace std;
int n,m,mt[N][N];
int u[N][N],l[N][N],r[N][N],lm,rm;
char a[N];
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a>b?b:a;}
int main(){
int i,j,ans=0,subans=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%s",a+1);
for(j=1;j<=m;j++)mt[i][j]=a[j]-'0';
}
memset(r,0x3f,sizeof(r));
int ansl=0,ansr=0,ansi=0;
for(i=1;i<=n;i++){
lm=0;rm=m+1;
for(j=1;j<=m;j++){
if(mt[i][j]){
if(i==1)l[i][j]=lm+1;
else l[i][j]=max(l[i-1][j],lm+1);
u[i][j]=u[i-1][j]+1;
}else lm=j;
}
for(j--;j;j--){
if(mt[i][j]){
if(i==1)r[i][j]=rm-1;
else r[i][j]=min(r[i-1][j],rm-1);
}
else rm=j;
int h=u[i][j],w=(r[i][j]-l[i][j]+1),sq=h*w;
if(ans>sq)subans=max(subans,sq);
else{
if(ans<sq)subans=max(subans,ans);
else if(l[i][j]!=ansl||r[i][j]!=ansr||i!=ansi)subans=max(subans,ans);
}
if(ans<sq){
ansl=l[i][j],ansr=r[i][j],ansi=i;
ans=sq;
}
subans=max(subans,max((u[i][j]-1)*(r[i][j]-l[i][j]+1),u[i][j]*(r[i][j]-l[i][j])));
}
}
printf("%d",subans);
return 0;
}
I
题目描述
解题思路
AC代码
2
J
题目描述
有一个长为$1e9$的只含有$1,-1$的数列，其中$1$区间个数$n\leq 10^6$，$1$的个数$num\leq 10^7$，问有多少个区间$[l,r]$满足$\sum_{i=l}^ra[i]>0$。
解题思路
考虑把问题转化为：对于某一点$x$，有多少个$y$满足$y<x$且$sum[y]<sum[x]$，其中$sum[i]=\sum_{j=0}^ia[j]$。
由于区域很大，暴力求前缀和是不可取的，所以只需把$1e9$划分为多个对答案有贡献的区间，可以把这些区间连成一起求前缀和，这并不影响答案。
所以求出对答案有贡献的区间$[L_i,R_i]$，记录下前面有多少比当前前缀和小的前缀和，记录下前缀和为$k$的有多少个即可。
AC代码
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
typedef long long ll;
using namespace std;
int l[N],r[N],n;
int L[N],R[N];
int num[M];
int main(){
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
l[0]=r[0]=L[0]=R[0]=-1,l[n+1]=r[n+1]=1e9;
int len=0;
for(i=1;i<=n;i++){
len+=r[i]-l[i]+1;
R[i]=min(r[i]+len,l[i+1]-1);
len-=l[i+1]-r[i]-1;
if(len<0)len=0;
}
len=0;
for(i=n;i;i--){
len+=r[i]-l[i]+1;
L[i]=max(l[i]-len,r[i-1]+1);
len-=l[i]-r[i-1]-1;
if(len<0)len=0;
}
int now=20000001;
ll sum=0,ans=0;
num[now]=1;//change
for(i=1;i<=n;i++){
for(j=max(L[i],R[i-1]+1);j<=R[i];j++){
if(j>=l[i]&&j<=r[i]){
sum+=num[now];
num[++now]++;
}else{
sum-=num[--now];
num[now]++;
}
ans+=sum;
}
}
printf("%lld",ans);
return 0;
}