总结

T2是一眼题,T3是规律题,T1,T4是原题,但是T1没有正确估计自己的实力,以为T1不可能考平衡树,因此就没去想,想了个分块的做法,考试调了三个小时也没A,考完重构一遍又调了两个多小时才A,本来是有时间开T3,T4也被浪费了。

这次考试应该先开T2,T3这些小码量的题,然后再开T4 T1。

分析

T1

我的做法是维护 $\sqrt{n}$ 级别个块 ,每次区间翻转就是暴力翻转,然后记录几个量,思路虽然很简单,实现起来很麻烦,这种写法用了五个多小时才A

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
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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<algorithm>

using namespace std;

typedef long long ll;

namespace mstd{

//change it if ll

inline void qread(int &x)
{
int f=1; x=0; static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x*=f; return ;
}

}

const int maxn=100030;
const int maxm=4030;

int vis[maxm][maxm];
int a[maxn],len,tmp[maxn],tot;
int n,m,b[maxn],sz[maxn],bl[maxn];
int mtot=0;

bitset <maxn> bt[maxm];

struct block{
int stinv,edinv,*f,tob,tov,swaptag;
}c[maxn],mtp[maxn];

inline void m_intreverse(int tov,int stinv,int edinv)
{
int i,j;
for(i=stinv,j=edinv;i<=edinv;i++,j--) tmp[i]=vis[tov][j];
for(i=edinv,j=edinv;i>=stinv;i--,j--) vis[tov][i]=tmp[j];
return ;
}

inline void m_blockreverse(int st,int ed)
{
int i,j;
for(i=st,j=ed;i<=ed;i++,j--) mtp[j]=c[i];
for(i=ed,j=ed;i>=st;i--,j--) c[i]=mtp[j],c[i].swaptag^=1;
return ;
}

inline void m_blockfront(int st,int ed)
{
int i; for(i=st;i<=ed;i++) c[i]=c[i+1];
}

inline void m_blockback(int st,int ed)
{
int i; for(i=ed;i>=st;i--) c[i+1]=c[i];
}

inline void m_intback(int tov,int st,int ed,int k)
{
int i; for(i=ed;i>=st;i--) vis[tov][i+k]=vis[tov][i];
}

inline int mpla(int x)
{
for(int i=1;i<=tot;i++) if(bt[c[i].tob][x]) return i;
return 0;
}

inline int mjtpla(int x,int pla)
{
if(c[pla].swaptag) m_intreverse(c[pla].tov,c[pla].stinv,c[pla].edinv),c[pla].swaptag=0;
for(int i=c[pla].stinv;i<=c[pla].edinv;i++)
if(vis[c[pla].tov][i]==x) return i-c[pla].stinv+1;
return 0;
}

inline int ask_sz(int x)
{
int ans=0,i;
for(i=1;i<=x;i++) ans+=c[i].edinv-c[i].stinv+1;
return ans;
}

inline void split(int pla,int x)
{
if(c[pla].edinv+1==x) return ;
int t1=len*4;
int t2=len*4;
int nextlen=c[pla+1].edinv-c[pla+1].stinv+1;
int l1,l2,i,j;
l1=x-c[pla].stinv;
l2=c[pla].edinv-x+1;
if(l2+nextlen<=t2&&l2<=t1&&pla+1<=tot)
{
if(c[pla+1].swaptag) m_intreverse(c[pla+1].tov,c[pla+1].stinv,c[pla+1].edinv),c[pla+1].swaptag=0;
m_intback(c[pla+1].tov,c[pla+1].stinv,c[pla+1].edinv,l2);
for(j=1;j<=l2;j++)
{
vis[c[pla+1].tov][c[pla+1].stinv+j-1]=vis[c[pla].tov][c[pla].stinv+l1+j-1];
bt[c[pla].tob][vis[c[pla].tov][c[pla].stinv+l1+j-1]]=0;
bt[c[pla+1].tob][vis[c[pla].tov][c[pla].stinv+l1+j-1]]=1;
vis[c[pla].tov][c[pla].stinv+l1+j-1]=0;
}
c[pla].edinv-=l2;
c[pla+1].edinv+=l2;
}
else
{
m_blockback(pla,tot);
mtot++,tot++;
c[pla+1].stinv=1;
c[pla+1].edinv=l2;
c[pla+1].f=vis[mtot];
c[pla+1].tob=c[pla+1].tov=mtot;
for(i=1;i<=l2;i++) vis[mtot][i]=vis[c[pla].tov][c[pla].stinv+l1+i-1],vis[c[pla].tov][c[pla].stinv+l1+i-1]=0;
for(i=1;i<=l2;i++) bt[c[pla].tob][vis[mtot][i]]=0,bt[c[pla+1].tob][vis[mtot][i]]=1;
c[pla].edinv-=l2;
}
}

inline void era(int pla)
{
m_intreverse(c[pla].tob,c[pla].stinv,c[pla].edinv);
c[pla].swaptag=0;
c[pla].stinv++;
if(c[pla].stinv>c[pla].edinv) m_blockfront(1,tot),tot--;
}

int main()
{
// freopen("sort.in","r",stdin);
// freopen("sort.out","w",stdout);
int i,j;
mstd::qread(n);
for(i=1;i<=n;i++) mstd::qread(a[i]),b[i]=a[i];
sort(b+1,b+n+1);
memset(sz,-1,sizeof(sz));
for(i=1;i<=n;i++)
{
int targetpla=lower_bound(b+1,b+n+1,a[i])-b;
sz[targetpla]++;
a[i]=targetpla+sz[targetpla];
}
len=sqrt(n);
for(i=1;i<=n;i++) bl[i]=(i-1)/len+1;
for(i=1;i<=bl[n];i++)
{
c[i].tob=i;
c[i].tov=i;
c[i].f=vis[i];
c[i].stinv=1;
c[i].edinv=(i*len>n?n%len:len);
int cnt=0;
for(j=(i-1)*len+1;j<=i*len;j++)
{
vis[i][++cnt]=a[j];
bt[i][a[j]]=1;
}
}
tot=bl[n];
mtot=tot;
for(i=1;i<=n;i++)
{
int mp=mpla(i);
int mjt=mjtpla(i,mp);
printf("%d ",ask_sz(mp-1)+mjt+(i-1));
split(mp,c[mp].stinv+mjt);
m_blockreverse(1,mp);
era(1);
}
}

T2

作为签到题,这个就很舒服,显然就是能在准备时间周围中间安排段子就在那里。

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

typedef long long ll;

namespace mstd{

//change it if ll

inline void qread(int &x)
{
int f=1; x=0; static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x*=f; return ;
}

}

const int maxn=1010;

int n,m,T,ans,tot;
int a[maxn],t[maxn];

priority_queue <int> q;

int main()
{
int i,j;
freopen("party.in","r",stdin);
freopen("party.out","w",stdout);
mstd::qread(n);
mstd::qread(T);
mstd::qread(m);
for(i=1;i<=n;i++) mstd::qread(a[i]),tot+=a[i];
for(i=1;i<=n;i++) mstd::qread(t[i]),tot+=t[i],q.push(t[i]%m),ans+=t[i]/m;
if(tot>=T)
{
printf("-1\n");
return 0;
}
T-=tot;
while(!q.empty())
{
int tmp=q.top();
int delta=m-tmp;
q.pop();
if(T>delta) ans++,T-=delta;
else break;
}
ans+=T/m;
printf("%d\n",ans);
return 0;
}

T3

打表找规律,或者用一个容斥

$\large\sum\limits_{i=1}^{\lfloor\frac{k}{r}\rfloor}(-1)^{i-1}\times C(n-k+1,i)\times C(n-ir,k-ir)$

然后按照这种做法打就可以了

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

typedef long long ll;

namespace mstd{

//change it if ll

inline void qread(int &x)
{
int f=1; x=0; static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x*=f; return ;
}

}

const int maxn=1e7+20;
const int modp=1e9+7;

int inv[maxn],ptm[maxn];
int n,k,r;

inline int getc(int n,int m)
{
return 1ll*ptm[n]*inv[n-m]%modp*inv[m]%modp;
}

int main()
{
mstd::qread(n);
mstd::qread(k);
mstd::qread(r);
inv[0]=inv[1]=1;
ptm[0]=ptm[1]=1;
int i,j;
for(i=2;i<=n;i++) inv[i]=1ll*(modp-modp/i)*inv[modp%i]%modp;
for(i=2;i<=n;i++) ptm[i]=1ll*ptm[i-1]*i%modp;
for(i=2;i<=n;i++) inv[i]=1ll*inv[i-1]*inv[i]%modp;
int ans=0,looker=1;
for(i=1;i*r<=k;i++,looker^=1)
ans=(1ll*ans+1ll*(modp+(looker?1ll:-1ll))%modp*getc(n-i*r,k-i*r)%modp*getc(n-k+1,i)%modp)%modp;
printf("%d\n",ans);
return 0;
}

T4

最小斯坦纳树板子,但是没时间去写了,做两边就相当于得到了答案转移,直接一遍过

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
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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=110;

namespace mstd{

//change it if ll

inline void qread(int &x)
{
int f=1; x=0; static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x*=f; return ;
}

}

int n,m,target;
int f[maxn][1025],pre[maxn][1025];
int head[maxn],num[11][11];
int chk[12][12];
int size,vis[maxn];
int p[maxn],cnt;
int nx[maxn],ny[maxn];
int val[maxn];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int bj[maxn];

priority_queue <pair<int,int> > q;

struct edge{
int next,to,dis;
}e[maxn*maxn*3];

inline void addedge(int next,int to,int dis)
{
e[++size].to=to;
e[size].dis=dis;
e[size].next=head[next];
head[next]=size;
}

inline void dij(int state)
{
memset(vis,0,sizeof(vis));
while(!q.empty())
{
int t=q.top().second;
q.pop();
if(vis[t]) continue;
vis[t]=1;
int i,j,k;
for(i=head[t];i;i=e[i].next)
{
j=e[i].to;
k=e[i].dis;
if(f[t][state]+k<f[j][state])
{
f[j][state]=f[t][state]+k;
pre[j][state]=t;
q.push(make_pair(-f[j][state],j));
}
}
}
}

void dfs(int t,int s)
{
while(pre[t][s]!=-1) bj[t]=1,t=pre[t][s];
for(int i=s;i;i=(i-1)&s)
{
if(f[t][s]==f[t][i]+f[t][s^i]-val[t])
{
dfs(t,i);
dfs(t,s^i);
return ;
}
}
}

int main()
{
register int i,j,k;
mstd::qread(n);
mstd::qread(m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
num[i][j]=(i-1)*m+j;
mstd::qread(val[num[i][j]]);
nx[num[i][j]]=i;
ny[num[i][j]]=j;
chk[i][j]=1;
if(val[num[i][j]]==0) p[++target]=num[i][j];
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
for(k=0;k<=3;k++)
{
if(!chk[i+dx[k]][j+dy[k]]) continue;
addedge(num[i][j],num[i+dx[k]][j+dy[k]],val[num[i+dx[k]][j+dy[k]]]);
}
memset(f,0x3f,sizeof(f));
memset(pre,-1,sizeof(pre));
for(i=1;i<=target;i++) f[p[i]][1<<(i-1)]=0;
int s=0;
for(s=0;s<=(1<<target)-1;s++)
{
for(i=1;i<=n*m;i++)
{
for(j=s;j;j=(j-1)&s) f[i][s]=min(f[i][s],f[i][j]+f[i][s^j]-val[i]);
if(f[i][s]!=f[0][0])
q.push(make_pair(-f[i][s],i));
}
dij(s);
}
dfs(p[1],(1<<target)-1);
printf("%d\n",f[p[1]][(1<<target)-1]);
for(i=1;i<=n;i++,printf("\n"))
for(j=1;j<=m;j++)
{
if(val[num[i][j]]==0) printf("x");
else if(bj[num[i][j]]) printf("o");
else printf("_");
}
return 0;
}