雅礼集训2019

雅礼集训2019

D1

雅礼2019冬令营day1.pdf

t1

请先思考后再展开

hotel原题,之前写过题解

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
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(int num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define PB push_back
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
const int MAX_N=51000;
vector<int> son[MAX_N];
int mxdep[MAX_N],gson[MAX_N];
ll ans;
ll *f1[MAX_N],*f2[MAX_N];
ll real[MAX_N*31],*tot;
void dfs(int x,int fa)
{
mxdep[x]=0;gson[x]=0;
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];if(y==fa) continue;
dfs(y,x);chmax(mxdep[x],mxdep[y]+1);
if(mxdep[y]>=mxdep[gson[x]]) gson[x]=y;
}
}
void dp(int x,int fa)
{
if(gson[x])
{
f1[gson[x]]=f1[x]+1;
f2[gson[x]]=f2[x]-1;
dp(gson[x],x);
if(mxdep[gson[x]]>=1) ans+=f2[gson[x]][1];
}
f1[x][0]++;
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];if(y==fa or y==gson[x]) continue;
f1[y]=tot;tot+=2*mxdep[y]+10;
f2[y]=tot;tot+=2*mxdep[y]+10;
dp(y,x);
for(int d=mxdep[y];d>=1;d--) ans+=f1[x][d-1]*f2[y][d];
for(int d=0;d<=mxdep[y];d++)
{
if(d+1<=mxdep[x]) ans+=f2[x][d+1]*f1[y][d];
if(d) f2[x][d-1]+=f2[y][d];
if(d+1<=mxdep[x]) f2[x][d+1]+=f1[x][d+1]*f1[y][d];
if(d+1<=mxdep[x]) f1[x][d+1]+=f1[y][d];
}
}
}
void main()
{
while(1)
{
int n;scanf("%d",&n);
if(n==0) break;
for(int i=1;i<=n;i++) son[i].clear();
for(int i=1;i<=n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);
son[x].PB(y);son[y].PB(x);
}
dfs(1,0);
ans=0;
tot=real+mxdep[1]*2+10;f1[1]=tot;
tot+=mxdep[1]*2+10;f2[1]=tot;tot+=mxdep[1]*2+10;
dp(1,0);
printf("%lld\n",ans);
for(int i=0;i<=n;i++) gson[i]=mxdep[i]=0,f1[i]=f2[i]=0;
for(int x=0;x<=n*30;x++) real[x]=0;
}
}
};
int main()
{
srand(time(0));
mine::main();
}

t2

请先思考后再展开

神仙题
题解1
题解2

t3

请先思考后再展开

$sin(kx)=2cos(x)sin((k-1)x)-sin((k-2)x)$
神仙数学题

D2

雅礼2019冬令营day2.pdf

t1

请先思考后再展开

苦死无果后,为了避免正解可能会利用图形的性质,就发现二维取点的询问一定是贴着左或右的
然后我觉得没什么用……结果一看题解,我去,利用贴边的性质,
把边排个序,线段树每个节点开个有序的deque,每次就是删除两边
每条边会被删除log次,时间为 $O(nlogn)$

t2

请先思考后再展开

看到树上路径先点分治,然后如果能求出一个多项式,就能卷积起来

$ans(a+b)+=\sum A[段数a][sy] \times B[段数b][-sy]$

注意A和B不重叠,而且点分治套路容斥一下

然后就是考虑怎么求这个多项式,以及复杂度怎么证明了(其实是同一个问题……考场上因为假设第一个能求发现不会第二个,就自闭了)

求的话,考虑一个前缀合法的序列的特性(1和-1),就是后面那一段是后缀和最大的一段(向上),如果是后缀合法(向下)则为最小,然后把段数清空。

然后我们直接枚举剩余系sy,然后直接卷起来,复杂度为 $\sum_{sy} mx_{段数}$ ,考虑到新进入一个剩余系的时候段数会被清空,而且一个点最多让其+1,所有复杂度为 $O(nlog^2n)$

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
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
#define double long double
const double PI=acos(-1);
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(int num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define PB push_back
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
const int MAX_N=51000;
struct Cp
{
double a,b;Cp(double x=0,double y=0) {a=x,b=y;}
friend Cp operator +(Cp x,Cp y){return Cp(x.a+y.a,x.b+y.b);}
friend Cp operator -(Cp x,Cp y){return Cp(x.a-y.a,x.b-y.b);}
friend Cp operator *(Cp x,Cp y){return Cp(x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a);}
};
struct FFT
{
int R[MAX_N];void preR(int n){R[0]=0;for(int i=1;i<n;i++) R[i]=(R[i>>1]>>1)|( (i&1)<<( (int)log2(n)-1 ) );}
Cp w[2][MAX_N];//i ak ioi
void prew(int n)
{
for(int i=0;i<n;i++) w[0][i]=Cp( cos(PI*i*2/n),sin(PI*i*2/n) );
for(int i=0;i<n;i++) w[1][i]=Cp( cos(-PI*i*2/n),sin(-PI*i*2/n) );
}
void solve(Cp a[],int n,int f)
{
for(int i=0;i<n;i++) if(i<R[i]) swap(a[i],a[R[i]]);
for(int ln=1;ln<=n/2;ln*=2)
for(int st=0;st<n;st+=ln*2)
for(int k=0;k<ln;k++)
{
Cp x=a[st+k],y=w[f][k*(n/ln/2)]*a[st+k+ln];
a[st+k]=x+y;a[st+k+ln]=x-y;
}
}
}fft;
int n;
vector<int> son[MAX_N];bool v[MAX_N];
int val[MAX_N],G,all,siz[MAX_N];
void getrt(int x,int fa)
{
val[x]=0;siz[x]=1;
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];if(y==fa or v[y]) continue;
getrt(y,x);siz[x]+=siz[y];chmax(val[x],siz[y]);
}
chmax(val[x],all-siz[x]);
if(val[x]<val[G]) G=x;
}
char str[MAX_N][10];int mxsy;
void dfs(int x,int fa,vector<int> A[],int sy,int cnt,int now,bool op)//剩余系、段数、当前前缀和
{
now+=(str[x][0]=='('?1:-1);
if(!op) {if(now>0) sy+=now,now=0,cnt=-1;}
else {if(now<0) sy+=now,now=0,cnt=-1;}
int ac=op?-sy:sy;chmax(mxsy,ac);
if(now==0)
{
cnt++;
while((int)A[ac].size()<=cnt) A[ac].PB(0);
A[ac][cnt]++;
}
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];if(v[y] or y==fa) continue;
dfs(y,x,A,sy,cnt,now,op);
}
}
int ans[MAX_N];vector<int> A[MAX_N],B[MAX_N];
Cp aa[MAX_N],bb[MAX_N];
void calc(int tt)
{
for(int sy=0;sy<=mxsy;sy++)
{
int ln1=A[sy].size(),ln2=B[sy].size()+(sy>0);if(ln1==0 or ln2-(sy>0)==0) continue;
int ln=1;while(ln<ln1+ln2-1) ln*=2;fft.preR(ln);fft.prew(ln);
for(int i=0;i<(int)A[sy].size();i++) aa[i]=Cp(A[sy][i]);fft.solve(aa,ln,0);
for(int i=0;i<(int)B[sy].size();i++) bb[i+(sy>0)]=Cp(B[sy][i]);fft.solve(bb,ln,0);
for(int i=0;i<ln;i++) aa[i]=aa[i]*bb[i];fft.solve(aa,ln,1);
for(int i=0;i<ln;i++) ans[i]+=round(aa[i].a/ln)*tt;
for(int i=0;i<ln;i++) aa[i]=Cp(),bb[i]=Cp();
}
for(int sy=0;sy<=mxsy;sy++) A[sy].resize(0),B[sy].resize(0);
}
void solve(int x,int sum)
{
if(sum==1) return;
v[x]=1;B[0].PB(1);
mxsy=0;dfs(x,0,A,0,0,0,0);for(int t=0;t<(int)son[x].size();t++) if(!v[son[x][t]]) dfs(son[x][t],0,B,0,0,0,1);
calc(1);
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];if(v[y]) continue;
mxsy=0;dfs(y,0,A,(str[x][0]=='('?1:0),0,(str[x][0]=='('?0:-1),0);dfs(y,0,B,0,0,0,1);
calc(-1);
}
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];if(v[y]) continue;
G=0;all=siz[y];getrt(y,x);solve(G,siz[y]);
}
}
void main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;scanf("%d%d",&x,&y);
son[x].PB(y);son[y].PB(x);
}
for(int i=1;i<=n;i++) scanf("%s",str[i]);
val[0]=INF;G=0;all=n;getrt(1,0);solve(G,n);
int q;scanf("%d",&q);
while(q--)
{
int t=qread();if(t==0) puts("error");
printf("%d\n",ans[t]);
}
}
};
int main()
{
srand(time(0));
mine::main();
}

t3

请先思考后再展开

bzoj3308

最优方案的两个神仙性质:

  1. 每个数,最多两个不同质因子
  2. 若两个,一个在根号内,一个在根号外

那么这是一个二分图,显然可以最大费用流,可得80分
考虑如何优化,先将只有一个质因子的数放入答案,然后费用流的边权改为f(x,y)-f(x)-f(y),显然去掉了负权边,而且让图更简单了
实测极限数据从几秒变秒出

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
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(int num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define PB push_back
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
bool isp(int x)
{
if(x<=1) return 0;
for(int i=2;i*i<=x;i++) if(x%i==0) return 0;
return 1;
}
const int MAX_N=210000;
int hou[MAX_N];
struct Edge{int y,c,w,g;}e[500000];
int ln=0;int oth(int x) {return (x&1)?x+1:x-1;}
void ins(int x,int y,int c,int w)
{
e[++ln]=(Edge){y,c,w,hou[x]};hou[x]=ln;
e[++ln]=(Edge){x,0,-w,hou[y]};hou[y]=ln;
}
int st,ed;
ll dis[MAX_N],ans=0;bool v[MAX_N];
int fm[MAX_N];
queue<int> q;
bool solve()
{
memset(dis,-0x3f,sizeof dis);dis[st]=0;
q.push(st);v[st]=1;
while(q.size())
{
int x=q.front();q.pop();
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(dis[y]<dis[x]+e[k].w and e[k].c>0)
{
dis[y]=dis[x]+e[k].w;fm[y]=k;
if(!v[y]) v[y]=1,q.push(y);
}
}
v[x]=0;
}
if(dis[ed]<0) return 0;
ans+=dis[ed];
for(int x=ed;x!=st;x=e[oth(fm[x])].y) e[fm[x]].c--,e[oth(fm[x])].c++;
return 1;
}
int num1[MAX_N],num2[MAX_N],tmp[MAX_N];
bool no[MAX_N];
int pp=0,prime[MAX_N],T,a=0,b=0,n;
void pre()
{
for(int i=2;i<=n;i++)
{
if(!no[i])
{
prime[++pp]=i;
if((ll)i*i<=n) ins(st,++a,1,0),num1[a]=i;
else num2[++b]=i,ins(T+b,ed,1,0);
}
for(int j=1;j<=pp and (ll)i*prime[j]<=n;j++)
{
no[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
void main()
{
scanf("%d",&n);T=sqrt(n)+1;
st=0;ed=n+2;pre();
for(int i=1;i<=a;i++)
{
int mx=-1;
for(ll x=num1[i];x<=n;x*=num1[i]) chmax(mx,x);
tmp[num1[i]]=mx;ans+=mx;
}
for(int i=1;i<=b;i++)
{
int mx=-1;
for(ll x=num2[i];x<=n;x*=num2[i]) chmax(mx,x);
tmp[num2[i]]=mx;ans+=mx;
}
for(int i=1;i<=a;i++) for(int j=1;j<=b;j++)
{
int mx=-1;
for(ll x=num1[i];x<=n;x*=num1[i])
for(ll y=num2[j];x*y<=n;y*=num2[j])
chmax(mx,x*y);
int tt=mx-tmp[num1[i]]-tmp[num2[j]];
if(tt>0) ins(i,T+j,1,tt);
}
while(solve()) ;
printf("%lld",ans+1);
}
};
int main()
{
srand(time(0));
mine::main();
}

D4

t1 cf1061e

请先思考后再展开

感觉其实和jcp之前给的网络流题目很像?
流量表示选择的情况
左边为树1,右边为树2,流量各自限制好
然后对于每个节点,在中间建边,表示好代价
然后非法情况,就是两边没有满流,还有边的流量可能是负数,这个忘记判断错了好久……

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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
//#define pr pair<double,int>
#define FR first
#define SE second
#define MP make_pair
const int MAX_N=510;
int n,rt1,rt2,w[MAX_N];
struct Tree
{
int hou[MAX_N],f[MAX_N];
struct Edge{int y,g;}e[MAX_N*2];
int ln;void ins(int x,int y) {e[++ln]=(Edge){y,hou[x]};hou[x]=ln;}
int nfa[MAX_N],ned[MAX_N];
//nfa=最近的关键祖先
Tree() {ln=0;memset(hou,0,sizeof hou);memset(ned,-1,sizeof ned);}
int getnum(int x,int fa,int st)
{
if(st==0 and ned[x]>=0) return ned[x];
int tot=0;
for(int k=hou[x];k>0;k=e[k].g) if(e[k].y!=fa) tot+=getnum(e[k].y,x,0);
return tot;
}
void dfs(int x,int fa,int tfa)
{
nfa[x]=ned[x]>=0?x:tfa;f[x]=fa;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
dfs(y,x,nfa[x]);
}
}
}t1,t2;
struct MCMF
{
int hou[MAX_N*2];
struct Edge
{
int y,g,c;ll w;
}e[MAX_N*MAX_N];
int ln;int oth(int x) {return x&1?x+1:x-1;}
void ins(int x,int y,int c,int w)
{
if(c<0)
{
puts("-1");
exit(0);//debug
}
e[++ln]=(Edge){y,hou[x],c,w};hou[x]=ln;
e[++ln]=(Edge){x,hou[y],0,-w};hou[y]=ln;
}
ll dis[MAX_N*2];bool v[MAX_N*2];
int fm[MAX_N*2],mif[MAX_N*2];
queue<int> q;
ll flow,cost;
bool solve(int st,int ed)
{
memset(dis,-63,sizeof dis);dis[st]=0;
q.push(st);mif[st]=INF;v[st]=1;
while(q.size())
{
int x=q.front();q.pop();
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(dis[y]<dis[x]+e[k].w and e[k].c>0)
{
dis[y]=dis[x]+e[k].w;
mif[y]=min(e[k].c,mif[x]);
fm[y]=k;
if(!v[y]) v[y]=1,q.push(y);
}
}
v[x]=0;
}
if(dis[ed]==dis[MAX_N*2-1] or mif[ed]==0) return 0;
flow+=mif[ed];cost+=dis[ed]*mif[ed];
int x=ed;
while(x!=st)
{
int t=fm[x];
e[t].c-=mif[ed];e[oth(t)].c+=mif[ed];
x=e[oth(t)].y;
}
return 1;
}
MCMF() {ln=0;flow=cost=0;memset(hou,0,sizeof hou);}
}mcmf;
void input()
{
scanf("%d%d%d",&n,&rt1,&rt2);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<=n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);
t1.ins(x,y);t1.ins(y,x);
}
for(int i=1;i<=n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);
t2.ins(x,y);t2.ins(y,x);
}
int q1;scanf("%d",&q1);
while(q1--)
{
int x,y;scanf("%d%d",&x,&y);
t1.ned[x]=y;
}
int q2;scanf("%d",&q2);
while(q2--)
{
int x,y;scanf("%d%d",&x,&y);
t2.ned[x]=y;
}
}
void main()
{
input();
t1.dfs(rt1,0,0);t2.dfs(rt2,0,0);
int st=0,ed=2*n+1;
for(int i=1;i<=n;i++)
{
int fx=t1.nfa[i],fy=t2.nfa[i];
mcmf.ins(fx,n+fy,1,w[i]);
if(t1.ned[i]>=0) mcmf.ins(st,i,t1.ned[i]-t1.getnum(i,t1.f[i],1),0);
if(t2.ned[i]>=0) mcmf.ins(n+i,ed,t2.ned[i]-t2.getnum(i,t2.f[i],1),0);
}
while(mcmf.solve(st,ed)) ;
if(mcmf.flow!=t1.ned[rt1]) puts("-1");
else printf("%lld",mcmf.cost);
}
};
int main()
{
srand(time(0));
mine::main();
}

t2 cf1045h

请先思考后再展开

一直在想dp,原来隔板法一下就可以直接做了
因为有上界,要按位处理一下

t3 cf780h

请先思考后再展开

神仙结论题……这个坑不填了

D5

雅礼2019冬令营day5.pdf

t1

请先思考后再展开

根号算法为设计两个算法,相互配合,比较显然
然后个人感觉log方的其实快不了太多
就是从左到右考虑左边界,然后把串建个trie,每个节点上用个set表示
第一次的时候,暴力建树,然后顺便把子树内ans求和
答案统计方面,对于每个长度的每个种类,将每个子矩阵的最上面那个作为贡献,从而唯一计数
(也就是上下端点的限制,这个东西似乎最近经常被mj熏陶)
然后接下来随着左端点的右移,大致思路就是合并两个trie子树,如果复杂度只和小的那棵树有关,那么就是启发式合并的复杂度 $O(nmlognm)$
考虑每个右端点,随着左端点的右移,字符串的种类只会减少,不需要合并(不进入)的子树可以直接统计其siz
对于合并的时候,既然要求只和小的那个有关,我们必须换一种统计方式
仔细观察一下原先那个,发现对于每个种类,所有内部存在这种的那些子矩阵都被统计了,那么每次插入set的贡献就是新包含这行的
大值域,要写map

t2

请先思考后再展开

看到与运算居然没想nlogn个数,感觉比noip时还菜了……
那么相当于一条线,离线一下,然后线段树维护区间加、区间和即可

t3

请先思考后再展开

已经另开题解了,自行搜索

D7

雅礼2019冬令营day7.pdf

t1

请先思考后再展开

连dp的状态都没想到
设 $dp(i,j,k)表示k轮后Pi>Pj的概率$
然后就各种方式优化一下转移

t2

请先思考后再展开

$f(n,k)=max( f(n-1,k),f(n-1,k-1)+k \times a_n )$
然后想到这个以后我直接就放弃了,因为很死板地认为连状态数量都超过范围了
但仔细观察这个方程,发现边界非常简单,然后决策也非常简单
最关键的是,值大部分可以从上一行保留下来加以利用
更近一步,很容易发现对于某个n,一旦某个k选择了决策二,那么后面都会选择决策二,具有单调性!
说到这里做法应该很显然了,用个平衡树动态维护当前行的dp值的差分
那么每次二分一个分界点(差分后更加容易了),然后插入一个数(偏移),再给后缀加 $a_n$

t3

请先思考后再展开

请先阅览几何一章,刚学的……
总之会了多边形求面积后,就没什么好说的了
把环拆两倍,维护一下前缀和及其前缀和即可

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
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(int num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define PB push_back
#define pr pair<ll,ll>
#define FR first
#define SE second
#define MP make_pair
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
const int MAX_N=2e6+10,MOD=1e9+7;
void add(ll &x,ll y) {x+=y;if(x>=MOD) x-=MOD;if(x<=-MOD) x+=MOD;}
ll gs(ll x) {ll t=(x>=MOD?x-MOD:x);return t<=-MOD?t+MOD:t;}
pr p[MAX_N];
ll cross(pr a,pr b)
{
return a.FR*b.SE-a.SE*b.FR;
}
int n;
int id(int x)
{
while(x>n) x-=n;
while(x<=0) x+=n;
return x;
}
ll real[MAX_N*2],sum[MAX_N*2],S[MAX_N*2],xx[MAX_N*2],yy[MAX_N*2];
void main()
{
freopen("convex.in","r",stdin);
freopen("convex.out","w",stdout);
n=qread();for(int i=1;i<=n;i++) p[i].FR=qread(),p[i].SE=qread();
for(int i=1;i<=2*n;i++)
{
real[i]=cross(p[id(i+1)],p[id(i)]);sum[i]=sum[i-1]+real[i];
S[i]=gs(S[i-1]+sum[i]%MOD);xx[i]=gs(xx[i-1]+p[id(i)].FR);yy[i]=gs(yy[i-1]+p[id(i)].SE);
}
ll ans=0;
for(int i=1,j=i+2;i<=n;i++)
{
if(j==i) j=i+2;
while(1)
{
int tj=j+1;
ll a=sum[tj-1]-sum[i-1]+cross(p[id(i)],p[id(tj)]);
if(a>sum[n]-a) break;
j++;
}
if(2ll*(sum[j-1]-sum[i-1]+cross(p[id(i)],p[id(j)]))>sum[n]) continue;
ll tmp=gs(S[j-1]-S[i])-sum[i-1]%MOD*(j-1-i)%MOD;tmp=gs(tmp);
ll t2=p[i].FR*(yy[j]-yy[i+1])%MOD-p[i].SE*(xx[j]-xx[i+1])%MOD;t2=gs(t2);
tmp=2*gs(tmp+t2)%MOD;add(ans,gs(sum[n]%MOD*(j-1-i)%MOD-tmp));
}
printf("%lld",(ans+MOD)%MOD);
}
};
int main()
{
srand(time(0));
mine::main();
}

D8

雅礼2019冬令营day8.pdf

t1

请先思考后再展开

首先,跟具体点无关的话就是经典的连通图计数
$g_n=f_n-\sum_{i=1}^{n-1} g_i f_{n-i}$
然后因为我比较sb,改为子集的时候是考虑这个子集的最小值的
于是就非常蛋疼了,只想到两个n的……
但其实因为我们只是需要求整体的答案,就假设所有g都包含节点n+1,f则不包含
复杂度为分层子集卷积的两个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
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(int num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define PB push_back
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
const int MOD=1e9+7;
void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<=-MOD) x+=MOD;}
const int MAX_N=21;
int bin[MAX_N],mp[MAX_N][MAX_N],siz[1<<MAX_N];
void FWT(int A[],int n,int f)
{
for(int i=0;i<n;i++)
for(int j=bin[n]-1;j>=0;j--) if(j&bin[i])
add(A[j],f*A[j-bin[i]]);
}
int f[MAX_N][1<<MAX_N],g[MAX_N][1<<MAX_N];
void main()
{
bin[0]=1;for(int i=1;i<MAX_N;i++) bin[i]=bin[i-1]<<1;
int n;scanf("%d",&n);
siz[0]=0;for(int i=1;i<bin[n];i++) siz[i]=siz[i>>1]+(i&1);
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) scanf("%d",&mp[i][j]);
n--;
for(int s=1;s<bin[n];s++)
{
f[siz[s]][s]=1;
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++)
if(s&bin[i] and s&bin[j]) f[siz[s]][s]=(ll)f[siz[s]][s]*(mp[i][j]+1)%MOD;
}
for(int i=1;i<=n;i++) FWT(f[i],n,1);
g[0][0]=1;FWT(g[0],n,1);
for(int ab=1;ab<=n;ab++)
{
for(int a=0;a<=ab-1;a++)
for(int s=0;s<bin[n];s++)
add(g[ab][s],(ll)g[a][s]*f[ab-a][s]%MOD);
FWT(g[ab],n,-1);
for(int s=0;s<bin[n];s++)
if(siz[s]==ab)
{
ll tmp=f[ab][s];
for(int i=0;i<n;i++) if(s&bin[i]) tmp=tmp*(mp[i][n]+1)%MOD;
g[ab][s]=(tmp-g[ab][s])%MOD;
}
else g[ab][s]=0;
FWT(g[ab],n,1);
}
FWT(g[n],n,-1);
printf("%d",(g[n][bin[n]-1]+MOD)%MOD);
}
};
int main()
{
srand(time(0));
mine::main();
}

题解是子集卷积的除法运算,写了教程

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
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(int num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define PB push_back
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
const int MOD=1e9+7;
void add(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;if(x<=-MOD) x+=MOD;}
int bin[30],mp[20][20],siz[1<<20];
void FWT(int A[],int n,int f)
{
for(int i=0;i<n;i++)
for(int j=bin[n]-1;j>=0;j--) if(j&bin[i])
add(A[j],f*A[j-bin[i]]);
}
int f[20][1<<20],f2[20][1<<20],ans[20][1<<20];
void main()
{
bin[0]=1;for(int i=1;i<30;i++) bin[i]=bin[i-1]<<1;
int n;scanf("%d",&n);
siz[0]=0;for(int i=1;i<bin[n];i++) siz[i]=siz[i>>1]+(i&1);
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) scanf("%d",&mp[i][j]);
n--;
for(int s=0;s<bin[n];s++)
{
f[siz[s]][s]=1;
for(int i=0;i<n;i++) for(int j=i+1;j<n;j++)
if(s&bin[i] and s&bin[j]) f[siz[s]][s]=(ll)f[siz[s]][s]*(mp[i][j]+1)%MOD;
}
memcpy(f2,f,sizeof f);
for(int s=0;s<bin[n];s++) for(int i=0;i<n;i++) if(s&bin[i])
f2[siz[s]][s]=(ll)f2[siz[s]][s]*(mp[i][n]+1)%MOD;
//ans=f2/f
for(int i=0;i<=n;i++) FWT(f[i],n,1),FWT(f2[i],n,1);
for(int i=0;i<=n;i++)
for(int s=0;s<bin[n];s++)
{
for(int j=0;j<i;j++) add(f2[i][s],-(ll)f[i-j][s]*ans[j][s]%MOD);
ans[i][s]=f2[i][s];
}
FWT(ans[n],n,-1);
printf("%d",(ans[n][bin[n]-1]+MOD)%MOD);
}
};
int main()
{
srand(time(0));
mine::main();
}

t2

请先思考后再展开

概率神仙题
至少目前羊也不会
题解

t3

请先思考后再展开

有两类点,一类是最大在子树内的,主席树即可
第二类是在父亲那边的
两个log的做法:树剖取出那log区间个前,两类区间在静态主席树上处理
一个log的做法dfs处理每个点两次,开两个线段树分别表示祖先们以及其他节点

code(两个log)

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
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(int num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define PB push_back
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
const int MAX_N=1e5+10;
struct CMT
{
struct Nod{int c,lc,rc;}p[MAX_N*30];
int id;CMT(){id=0;memset(p,0,sizeof p);}
void add(int &x,int l,int r,int pos)
{
if(x==0) x=++id;
p[x].c++;
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) add(p[x].lc,l,mid,pos);
else add(p[x].rc,mid+1,r,pos);
}
void merg(int x,int &y,int l,int r)
{
if(x==0) return;
if(y==0) {y=x;return;}
p[y].c+=p[x].c;
int mid=(l+r)>>1;
merg(p[x].lc,p[y].lc,l,mid);
merg(p[x].rc,p[y].rc,mid+1,r);
}
int getsum(int x,int y,int l,int r,int pos)
{
if(l==r) return p[y].c-p[x].c;
int mid=(l+r)>>1,left=p[p[y].lc].c-p[p[x].lc].c;
if(pos<=mid) return getsum(p[x].lc,p[y].lc,l,mid,pos);
return left+getsum(p[x].rc,p[y].rc,mid+1,r,pos);
}
int getk(int x,int y,int l,int r,int k)
{
if(l==r) return l;
int mid=(l+r)>>1,left=p[p[y].lc].c-p[p[x].lc].c;
if(k<=left) return getk(p[x].lc,p[y].lc,l,mid,k);
return getk(p[x].rc,p[y].rc,mid+1,r,k-left);
}
}cmt;
int rt[MAX_N];
vector<int> son[MAX_N];
int siz[MAX_N],gson[MAX_N],ff[MAX_N];
void pre(int x)
{
siz[x]=1;gson[x]=0;
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];pre(y);siz[x]+=siz[y];
if(siz[y]>siz[gson[x]]) gson[x]=y;
}
}
int dfn[MAX_N],id=0,to[MAX_N],top[MAX_N];
void pre2(int x,int tp)
{
dfn[x]=++id;to[id]=x;top[x]=tp;
if(gson[x]) pre2(gson[x],tp);
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];if(y==gson[x]) continue;
pre2(y,y);ff[y]=x;
}
}
int mx1,mx2,mi;
void insert(int num)
{
if(num>=mx1) mx2=mx1,mx1=num;
else if(num>=mx2) mx2=num;
chmin(mi,num);
}
pr now[30],now2[100];bool is[100];
void main()
{
int n;scanf("%d",&n);
if(n==1) {puts("0");return;}
for(int i=2;i<=n;i++) son[qread()].PB(i);
pre(1);pre2(1,1);
for(int i=1;i<=n;i++)
{
cmt.add(rt[i],1,n,siz[to[i]]);
cmt.merg(rt[i-1],rt[i],1,n);
}
for(int x=1;x<=n;x++)
{
mx1=mx2=0,mi=INF;if(x!=1) insert(n-siz[x]);
int fm=-1;for(int t=0;t<(int)son[x].size();t++) {insert(siz[son[x][t]]);if(siz[son[x][t]]==mx1) fm=son[x][t];}
if(mx1==mx2) {printf("%d\n",mx1);continue;}
int ans=mx1,wt=(mx1-mi)/2;
if(fm>0)
{
int l=dfn[fm]+1,r=dfn[fm]+siz[fm]-1;
int a=cmt.getsum(rt[l-1],rt[r],1,n,wt);
int tmp=cmt.getk(rt[l-1],rt[r],1,n,a);
chmin(ans, max(mx1-tmp,max(mx2,mi+tmp)) );
tmp=cmt.getk(rt[l-1],rt[r],1,n,a+1);
chmin(ans, max(mx1-tmp,max(mx2,mi+tmp)) );
}
else
{
int tt=0,tt2=0;
int tmp=x;
while(tmp!=0)
{
int l=dfn[top[tmp]],r=dfn[tmp];
now[++tt]=MP(l,r);
tmp=ff[top[tmp]];
}
reverse(now+1,now+tt+1);
memset(is,0,sizeof is);
now2[++tt2]=MP(2,now[1].FR-1);now[++tt]=MP(dfn[x]+1,dfn[x]+1);
for(int i=1;i<=tt-1;i++)
{
now2[++tt2]=now[i];is[tt2]=1;
now2[++tt2]=MP(now[i].SE+1,now[i+1].FR-1);
}
now2[++tt2]=MP(dfn[x]+siz[x],n);
for(int i=1;i<=tt2;i++)
{
int l=now2[i].FR,r=now2[i].SE;if(l>r) continue;
int a=cmt.getsum(rt[l-1],rt[r],1,n,wt+(is[i]?siz[x]:0));
int tmp=cmt.getk(rt[l-1],rt[r],1,n,a)-(is[i]?siz[x]:0);
chmin(ans, max(mx1-tmp,max(mx2,mi+tmp)) );
tmp=cmt.getk(rt[l-1],rt[r],1,n,a+1)-(is[i]?siz[x]:0);
chmin(ans, max(mx1-tmp,max(mx2,mi+tmp)) );
}
}
writeln(ans);
}
}
};
int main()
{
srand(time(0));
mine::main();
}

D10

雅礼2019冬令营day10.pdf

t1

请先思考后再展开

原来bitset跑10w是常规操作啊……

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
66
67
68
69
70
#include "coin.h"
#include<string>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<algorithm>
#include<vector>
using namespace std;
string a="0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
int lst;
int tryask(string tmp)
{
int tt=ask(tmp);
if(tt==0)
{
for(int j=0;j<100;j++)
if(a[j]=='0') a[j]='1';
else a[j]='0';
ask(a);
}
return tt;
}
void unknow(int i);
void know0a(int i);
void know0b(int i);
void know1b(int i);
void know0a(int i)
{
unknow(i+1);
}
void know0b(int i)
{
int now=tryask(a);
if(lst==now) a[i]='0',lst=now,know1b(i);
else lst=now,unknow(i+1);
}
void know1b(int i)
{
int now=tryask(a);
if(lst==now) a[i]='1',lst=now,know0b(i);
else lst=now,unknow(i+1);
}
void unknow(int i)
{
if(i==100)
{
ask(a);
srand(time(0));
while(1)
{
a="";for(int i=0;i<100;i++) a+=('0'+rand()%2);
tryask(a);
}
return;
}
a[i]='1';int now=tryask(a);
if(now==lst+1 or now==lst) a[i]='0',lst=now,know1b(i);//1
else lst=now,know0a(i);//0
}
void guess()
{
a="0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
lst=tryask(a);
unknow(0);
}

t3

请先思考后再展开

有点神仙,大致就是转化为计数,然后花式dp

D11

没想到我的排名高潮是在最后一天……骗了个rk9

t1

在30乘16的地图上玩扫雷,地图按照某种方式随机。
随机种子不超过10000种

请先思考后再展开

随机算法ac本题……其实我能拍出卡我的数据,但我的种子可是lucky number,概率约为6/1000

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
#include "mine.h"
#include <bits/stdc++.h>
using namespace std;
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
bool mine[11000][50][50];
int sum[11000][50][50];
bool in[11000];int tot;
int n,m;
bool v[50][50];
int info[50][50];
bool is[50][50];//mine
int dx[8]={0,0,-1,-1,-1,1,1,1};
int dy[8]={1,-1,-1,0,1,-1,0,1};
bool can(int x,int y)
{
return 0<=x and x<n and 0<=y and y<m;
}
pr calc(int x,int y)//ͳ����֪�������յ���
{
int cnt=0,cnt2;
for(int i=0;i<8;i++) if(can(x+dx[i],y+dy[i]))
{
if(is[x+dx[i]][y+dy[i]]) cnt++;
else if(v[x+dx[i]][y+dy[i]]) cnt2++;//�յ�
}
return MP(cnt,cnt2);
}
int calc2(int x,int y)
{
int cnt=0;
for(int i=0;i<8;i++) if(can(x+dx[i],y+dy[i])) cnt++;
return cnt;
}
void check(int x,int y)
{
for(int i=100;i<=10000;i++) if(in[i])
{
if(sum[i][x][y]<0 and info[x][y]>=0) in[i]=0,tot--;
else if(sum[i][x][y]>=0 and sum[i][x][y]!=info[x][y]) in[i]=0,tot--;
}
if(tot==1)
{
int ss;for(int i=100;i<=10000;i++) if(in[i]) ss=i;
for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(!v[i][j] and !mine[ss][i][j]) open(i,j);
exit(0);
}
}
//vector<pr> know;
struct Pt
{
int x,y;
friend bool operator < (Pt a,Pt b)
{
return info[a.x][a.y]<info[b.x][b.y];
}
};
set<Pt> know;
set<Pt>::iterator it,it2,it3;
void del()
{
it3=it;
it2=++it;
know.erase(it3);
it=it2;
}
pr randnxt()
{
for(it=know.begin();it!=know.end();)
{
Pt now=*it;
random_shuffle(dx,dx+8);
random_shuffle(dy,dy+8);
for(int i=0;i<8;i++)
{
int tx=now.x+dx[i],ty=now.y+dy[i];
if(can(tx,ty) and v[tx][ty]==0) return MP(tx,ty);
}
del();
}
//int tt=0;
while(1)
{
int x=rand()%n,y=rand()%m;
if(v[x][y]==0) return MP(x,y);
}
}
void solve(int x,int y);
void update()//free award
{
for(it=know.begin();it!=know.end();)
{
//pr now=know[i];
Pt now=*it;
pr gg=calc(now.x,now.y);
if(gg.FR==info[now.x][now.y])//��֪�����׶������� ʣ�µĶ��ǿյ�
{
for(int i=0;i<8;i++)
{
int tx=now.x+dx[i],ty=now.y+dy[i];
if(can(tx,ty) and !v[tx][ty])
{
solve(tx,ty);
return;
}
}
del();
}
else if(gg.SE+info[now.x][now.y]==calc2(now.x,now.y) )//���пյض������� ʣ�µĶ�����
{
for(int i=0;i<8;i++)
{
int tx=now.x+dx[i],ty=now.y+dy[i];
if(can(tx,ty)) is[tx][ty]=1,info[tx][ty]=-1,v[tx][ty]=1,check(tx,ty);
}
del();
}
else ++it;
}
}
void solve(int x,int y)
{
v[x][y]=1;info[x][y]=open(x,y);
if(info[x][y]<0) is[x][y]=1;
know.insert((Pt){x,y});
check(x,y);
update();
}
//g++ mine.cpp grader.cpp -o mine -O2 -std=c++11
/*
16 30 191 609=9
16 30 159 5828=8
*/
void sweep(int H, int W, int K)
{
n=H,m=W;tot=0;
srand(20030122);
for(int s=100;s<=10000;s++)
{
int now=s,cnt=0;
while(cnt<K)
{
now=48271ll*now%2147483647;
int x=(now/m)%n,y=now%m;
if(mine[s][x][y]==0)
{
mine[s][x][y]=1,cnt++;
sum[s][x][y]=-0x3f3f3f3f;
for(int i=0;i<8;i++) if(can(x+dx[i],y+dy[i])) sum[s][x+dx[i]][y+dy[i]]++;
}
}
in[s]=1;++tot;
}
int x=rand()%n,y=rand()%m;
solve(x,y);
while(1)
{
pr nxt=randnxt();
solve(nxt.FR,nxt.SE);
}
}

t2

大小为n的正方形01矩阵,每次可以询问一个矩阵是否为其子矩阵,在5n方的次数内得出结论,n小于60

请先思考后再展开

暴力:n3方得到合法的行,n2拼接
那么我们只需要优化前面的部分

暂时咕咕咕……

t3

你需要猜测一个长度为1000的01串,你每次可以询问一个区间内的1的个数,
但有50%的概率交互库会随机返回一个[0,r-l+1]内不是答案的数
要求询问次数在6000内

请先思考后再展开

永久咕咕咕……

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/caf.html
转载请注明出处,谢谢!