| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 10/12 | O | Ø | . | Ø | . | O | O | O | Ø | O | Ø | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
解题思路
solved by qxforever
AC代码 - by qxforever
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
186
187
188
189
190
191
192
193
using namespace std;
char s[100][20];
int r,n;
int L,R;
struct Line
{
bool after_exit;
int num,dis,id;
char s[10];
bool operator < (const Line &rhs) const{
return num<rhs.num||(num==rhs.num&&dis>rhs.dis)||(num==rhs.num&&dis==rhs.dis&&id>rhs.id);
}
}l[100];
int main()
{
cin>>r>>n;r+=3;
for(int i=1;i<=r;i++) scanf("%s",s[i]);
for(int i=1;i<=r;i++){
if(i==1||i==(r+1)/2||i==r) continue;
if(s[i-1][0]=='.'){
l[i].after_exit=true;
}
for(int j=0;j<=2;j++){
if(s[i][j]=='-') l[i].s[j]=0;
else l[i].s[j]=1;
}
for(int j=4;j<=6;j++){
if(s[i][j]=='-') l[i].s[j-1]=0;
else l[i].s[j-1]=1;
}
for(int j=8;j<=10;j++){
if(s[i][j]=='-') l[i].s[j-2]=0;
else l[i].s[j-2]=1;
}
for(int j=0;j<9;j++){
if(!l[i].s[j]) l[i].num++;
if(l[i].s[j]&&j<4) L++;
if(l[i].s[j]&&j>=5) R++;
}
l[i].dis=min(min(abs(i-1),abs(i-r)),abs(i-(r+1)/2));
l[i].id=i;
}
int id1=2,id2=(r+1)/2+1;
int i;
for(i=0;i<n;i++){
if(l[id1].num==0&&l[id2].num==0) break;
if(l[id1].num<l[id2].num) swap(id1,id2);
if(l[id1].num==l[id2].num&&id1>id2) swap(id1,id2);
l[id1].num--;int j=id1;
int p=3,q=5;
if(!l[j].s[p]||!l[j].s[q]){
if(l[j].s[p]&&!l[j].s[q]){
l[j].s[q]='a'+i;
R++;continue;
}
if(l[j].s[q]&&!l[j].s[p]){
l[j].s[p]='a'+i;
L++;continue;
}
if(R<L) l[j].s[q]='a'+i,R++;
else l[j].s[p]='a'+i,L++;
continue;
}
p=2,q=6;
if(!l[j].s[p]||!l[j].s[q]){
if(l[j].s[p]&&!l[j].s[q]){
l[j].s[q]='a'+i;
R++;continue;
}
if(l[j].s[q]&&!l[j].s[p]){
l[j].s[p]='a'+i;
L++;continue;
}
if(R<L) l[j].s[q]='a'+i,R++;
else l[j].s[p]='a'+i,L++;
continue;
}
p=0,q=8;
if(!l[j].s[p]||!l[j].s[q]){
if(l[j].s[p]&&!l[j].s[q]){
l[j].s[q]='a'+i;
R++;continue;
}
if(l[j].s[q]&&!l[j].s[p]){
l[j].s[p]='a'+i;
L++;continue;
}
if(R<L) l[j].s[q]='a'+i,R++;
else l[j].s[p]='a'+i,L++;
continue;
}
if(!l[j].s[4]){
l[j].s[4]='a'+i;continue;
}
p=1,q=7;
if(!l[j].s[p]||!l[j].s[q]){
if(l[j].s[p]&&!l[j].s[q]){
l[j].s[q]='a'+i;
R++;continue;
}
if(l[j].s[q]&&!l[j].s[p]){
l[j].s[p]='a'+i;
L++;continue;
}
if(R<L) l[j].s[q]='a'+i,R++;
else l[j].s[p]='a'+i,L++;
continue;
}
}
//for(int i=1;i<=r;i++) printf("%d ",l[i].num);puts("");
priority_queue<Line> q;
for(int i=1;i<=r;i++){
if(l[i].num>0) q.push(l[i]);
}
for(int j;i<n;i++,q.push(l[j])){
j=q.top().id;q.pop();
l[j].num--;
int p=3,q=5;
if(!l[j].s[p]||!l[j].s[q]){
if(l[j].s[p]&&!l[j].s[q]){
l[j].s[q]='a'+i;
R++;continue;
}
if(l[j].s[q]&&!l[j].s[p]){
l[j].s[p]='a'+i;
L++;continue;
}
if(R<L) l[j].s[q]='a'+i,R++;
else l[j].s[p]='a'+i,L++;
continue;
}
p=2,q=6;
if(!l[j].s[p]||!l[j].s[q]){
if(l[j].s[p]&&!l[j].s[q]){
l[j].s[q]='a'+i;
R++;continue;
}
if(l[j].s[q]&&!l[j].s[p]){
l[j].s[p]='a'+i;
L++;continue;
}
if(R<L) l[j].s[q]='a'+i,R++;
else l[j].s[p]='a'+i,L++;
continue;
}
p=0,q=8;
if(!l[j].s[p]||!l[j].s[q]){
if(l[j].s[p]&&!l[j].s[q]){
l[j].s[q]='a'+i;
R++;continue;
}
if(l[j].s[q]&&!l[j].s[p]){
l[j].s[p]='a'+i;
L++;continue;
}
if(R<L) l[j].s[q]='a'+i,R++;
else l[j].s[p]='a'+i,L++;
continue;
}
if(!l[j].s[4]){
l[j].s[4]='a'+i;continue;
}
p=1,q=7;
if(!l[j].s[p]||!l[j].s[q]){
if(l[j].s[p]&&!l[j].s[q]){
l[j].s[q]='a'+i;
R++;continue;
}
if(l[j].s[q]&&!l[j].s[p]){
l[j].s[p]='a'+i;
L++;continue;
}
if(R<L) l[j].s[q]='a'+i,R++;
else l[j].s[p]='a'+i,L++;
continue;
}
}
for(int i=1;i<=r;i++){
if(i==1||i==(r+1)/2||i==r) continue;
for(int j=0;j<=2;j++){
if(isalpha(l[i].s[j])) s[i][j]=l[i].s[j];
}
for(int j=3;j<=5;j++){
if(isalpha(l[i].s[j])) s[i][j+1]=l[i].s[j];
}
for(int j=6;j<=8;j++){
if(isalpha(l[i].s[j])) s[i][j+2]=l[i].s[j];
}
}
for(int i=1;i<=r;i++) printf("%s\n",s[i]);
}
B
题目描述
平面上有一些牛，依次在某些点加入一些栅栏，问此次加入的栅栏和之前加入的且在左下角的栅栏组成的密闭空间中有多少头牛。保证没有栅栏同$x$或同$y$。
解题思路
不妨只考虑添加完所有栅栏后，某一个$y$下的牛、栅栏分布情况。容易想到这是一个牛和栅栏交替的结构，而栅栏可以跨$y$继续向下延伸，故考虑用$set$存一下栅栏的情况（加入时间、$x$位置），然后按$y$从大到小进行枚举处理。
将所有牛和栅栏的坐标信息排序，按$y$从大到小、$x$从大到小、从栅栏到牛的顺序枚举并添加/删除信息，这就能求出最终每个栅栏圈住了几头牛。
在上面的过程中，求出来每个时间$i$放下的栅栏圈住了外面哪个时间更早放下的的栅栏$outer[i]$的牛，用并查集倒序处理即可获得答案。
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
typedef long long ll;
using namespace std;
struct P{
int x,y,t;
bool operator<(const P&a)const{
if(y==a.y)return x==a.x?t>a.t:x>a.x;
return y>a.y;
}
}a[N];
int outer[N];
set<pair<int,int>>S;
int f[N],cnt[N],ans[N];
int find(int x){return x==f[x]?f[x]:f[x]=find(f[x]);}
void uni(int x,int y){
x=find(x);y=find(y);
f[x]=y;
cnt[y]+=cnt[x];
}
int main(){
int i,n,m;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d%d",&a[i].x,&a[i].y);
scanf("%d",&m);
for(i;i<n+m;i++)scanf("%d%d",&a[i].x,&a[i].y),a[i].t=i-n+1;
for(i=1;i<=m;i++)f[i]=i;
sort(a,a+n+m);
for(i=0;i<n+m;i++){
int x=a[i].x,t=a[i].t;
pii p=mp(x,t);
if(!t){
auto j=S.upper_bound(p);
if(j!=S.end())cnt[(*j).se]++;
}
else{
S.insert(p);
auto j=S.find(p);
while(!(j==S.begin()||(*--j).se<t)){
S.erase(j);
j=S.find(p);
}
j=++S.find(p);
if(j!=S.end())outer[t]=(*j).se;
}
}
for(i=m;i;i--){
ans[i]=cnt[find(i)];
if(outer[i])uni(i,outer[i]);
}
for(i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}
C
题目描述
解题思路
AC代码
2
D
题目描述
有一个围成一个甜甜圈的$r\times c$矩阵$a$（上下可达、左右可达），初始位置在$(1,1)$，有$q$次、两种操作：走$k\leq 10^9$步并询问位置；将$a_{xy}$赋为$z$。
$r,c\leq 2000,q\leq 5000$。
解题思路
观察到$q$比较小，可以考虑记录循环节，但由于循环节是$O(rc)$级别的，考虑降级，即记录$(x,1)$走$c$步后位于$(nxt[x],1)$。询问比较容易，问题在于修改。
分别考虑$(x-1,y-1),(x-1,y),(x-1,y+1)$三个点，只有到达这三个节点的区间才有可能被更新。维护一下对应的初始区间，很容易考虑到每次$y$坐标$-1$的时候，区间只会修改端点附近的$\pm 1$，故通过这个特性更新即可。
细节很多……最后附上两个测试$nxt$数组的数据。
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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
typedef long long ll;
using namespace std;
int a[N][N],nxt[N];
char s[10];
int r,c;
int getp(int x,int n){
x%=n;if(x<=0)x+=n;
return x;
}
pii go(pii now,int dx,int dy){
return mp(getp(now.fi+dx,r),getp(now.se+dy,c));
}
pii getnext(pii now){
pii u=go(now,-1,1);
pii m=go(now,0,1);
pii d=go(now,1,1);
if(a[u.fi][u.se]>=a[m.fi][m.se]&&a[u.fi][u.se]>=a[d.fi][d.se])return u;
if(a[m.fi][m.se]>=a[u.fi][u.se]&&a[m.fi][m.se]>=a[d.fi][d.se])return m;
return d;
}
void init(){
int i,j;
for(i=1;i<=r;i++){
j=1;
pii now=mp(i,j);
do{
j=j%c+1;
now=getnext(now);
}while(j!=1);
nxt[i]=now.fi;
}
}
int vis[N];
int in(int x,int u,int d){
u=getp(u,r);d=getp(d,r);
if(u<=d)return u<=x&&x<=d;
return x<=d||x>=u;
}
//#define LOCAL 1
int main(){
int i,j,k,q,x,y,z;
FILE*out=fopen("data.in","w");
srand(time(NULL));
r=4;c=4;fprintf(out,"%d %d\n",r,c);
scanf("%d%d",&r,&c);
for(i=1;i<=r;i++)for(j=1;j<=c;j++){
a[i][j]=rand()%9+1;fprintf(out,"%d%c",a[i][j]," \n"[j==c]);
scanf("%d",&a[i][j]);
}
q=4000;fprintf(out,"%d\n",q);
scanf("%d",&q);
init();
pii now=mp(1,1);
while(q--){
s[0]=rand()%2?'m':'n';s[1]='\0';fprintf(out,"%s ",s);
scanf("%s",s);
if(s[0]=='m'){
x=rand()%r+100000000;fprintf(out,"%d\n",x);
scanf("%d",&x);
while(x&&now.se!=1){
x--;
now=getnext(now);
}
int circ=0;
memset(vis,0,sizeof(vis));
if(x>c){//find circ
int cnt=0;
do{
vis[now.fi]=++cnt;
now=mp(nxt[now.fi],1);
x-=c;
}while(!vis[now.fi]&&x>c);
if(x>c){
circ=(++cnt-vis[now.fi])*c;
//get circ
x%=circ;
while(x>c){
now=mp(nxt[now.fi],1);
x-=c;
}
}
}
while(x)x--,now=getnext(now);
printf("%d %d\n",now.fi,now.se);
}else{
#ifdef LOCAL
x=rand()%r+1,y=rand()%c+1,z=rand()%9+1;fprintf(out,"%d %d %d\n",x,y,z);
scanf("%d%d%d",&x,&y,&z);
a[x][y]=z;
for(i=-1;i<=1;i++){
pii now=mp(getp(x+i,r),getp(y-1,c));
pii t=getnext(now);
while(t.se!=1)t=getnext(t);
int up=now.fi,down=now.fi,can=1;
for(j=now.se-1;j>=1;j--){
if(down-up>=r){
up=1;down=r;
break;
}
int flag=0,nu=up,nd=down;
//(up+-1,j)->(up,j+1)?
for(k=-1;k<=1;k++){
pii pre=mp(getp(up+k,r),getp(j,c)),to=getnext(pre);
if(in(to.fi,up,down)&&!(!in(pre.fi,up,down)&&to.fi!=getp(up,r))){
flag=1;nu+=k;
break;
}
}
//(down+-1,j)->(down,j+1)?
for(k=1;k>=-1;k--){
pii pre=mp(getp(down+k,r),getp(j,c)),to=getnext(pre);
if(in(to.fi,up,down)&&!(!in(pre.fi,up,down)&&to.fi!=getp(down,r))){
flag=1;nd+=k;
break;
}
}
if(!flag||up>down){
can=0;
break;
}
up=nu;down=nd;
}
if(can)for(j=up;j<=down;j++)nxt[getp(j,r)]=t.fi;
}
for(int i=1;i<=r;i++)printf("%d%c",nxt[i]," \n"[i==r]);
}
}
return 0;
}
/*
4 4
8 8 7 3
3 9 2 4
2 2 7 9
1 2 3 7
1
change 4 2 8
4 4
3 2 6 7
1 4 3 5
5 7 5 1
5 6 9 3
1
change 1 1 9
*/
E
题目描述
解题思路
AC代码
2
F
题目描述
给定$n,p,r(n\leq 10^{18},p\leq 10^7)$，求一个序列$a$满足$a_i=i,i\neq t;a_i<i,i=t$（$t$可任选），且$\Pi_{i}a_i\equiv c\text{ mod }p$。
解题思路
根据$r$是否为$0$讨论。
若$r=0$，即可以整除$p$：当$n>p$的时候把$n$变为$p$即可；$n=p$的时候把$2$变为$1$即可，这里特判一下$p=2$的情况；否则显然无解。
若$r\neq 0$，即不可以整除$p$：当$n\geq 2p$的时候，阶乘必然至少有两个$p$的因数，只能改变其中一个，$r=0$必然成立；$p\leq n<2p$的时候，则考虑修改$a_p$的值；$n<p$的时候枚举每个$i$计算（满足$\frac {n!}{i}\times x\equiv r\text{ mod }p$的 $x$）即可。
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
typedef long long ll;
using namespace std;
ll qp(ll a,int p,ll mod){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
int main(){
ll i,n,p,r;
scanf("%lld%lld%lld",&n,&p,&r);
if(!r){
if(n<p)NO;
else{
if(n==2&&p==2)NO;
else if(n==p)printf("2 1\n");
else printf("%lld 1\n",n,1);
}
}else{
if(n>=2*p)NO;
else{
if(n>=p){
ll x=1;
for(i=p+1;i<=n;i++)x=x*i%p;
x=r*qp(x,p-2,p)%p;
ll y=1;
for(i=1;i<=p-1;i++)y=y*i%p;
y=qp(y,p-2,p);
if(x*y%p>=p)NO;
else printf("%lld %lld\n",p,(x%p*y%p)%p);
}else{
ll x=1;
for(i=1;i<=n;i++)x=x*i%p;
x=qp(x,p-2,p)*r%p;
int flag=0;
for(i=2;i<=n;i++){
if(x*i%p<i){
flag=1;
printf("%lld %lld\n",i,x*i%p);
break;
}
}
if(!flag)NO;
}
}
}
return 0;
}
G
题目描述
给一个连通无向图，初始位置在$1$号节点，目标为$n$号节点。每一天，所处位置的机器会等概率随机抽取与当前节点相邻的节点，你可以选择留在原地或者去往这个节点，问采取最优策略的情况下，到达目标的期望时间为多少。
解题思路
设$f[i]$表示点$i$到点$n$的期望时间，那么我们必然是从$f$大的向$f$小的节点走。设与$i$直接相连的的集合为$P$，有
$f[i]=1+\frac{\sum_{p\in P} min{f[p],f[i]}}{deg[i]}$
我们将所有点分为两个部分，一部分是已经确定$f$最终值的，这部分设为$S$，另一部分是未确定$f$最终值的。
初始时$f[n]=0,f[i]=inf,S=${$n$}，按照$f$从小到大的顺序从优先队列取出$S$中的元素，依次更新与其相邻且不在$S$中的节点的$f$。
容易观察得到，对于在从点$i$往外更新其他节点之前的所有$S$中的点$j$，$f[j]<f[i]$。故当更新到点$i$时，有
$f[i]=1+\frac{\sum_{p\in S}f[p]}{deg[i]}+\frac{\sum_{p\notin S}f[i]}{deg[i]}$
设与$i$相邻的$S$中元素个数为$cnt[i]$，其$f$之和为$s[i]$，则
$f[i]=1+\frac{s[i]}{deg[i]}+\frac{deg[i]-cnt[i]}{deg[i]}f[i]$
化简得到
$f[i]=\frac{s[i]+deg[i]}{cnt[i]}+1$。
于是通过类似$dijkstra$的方法一路取出并向外更新节点即可。
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;
double f[N],s[N];
struct Edge{
int e,n;
}e[N<<1];
int hd[N],cntt;
void add(int a,int b){
e[++cntt].e=b;e[cntt].n=hd[a];hd[a]=cntt;
}
int deg[N],cnt[N],vis[N];
priority_queue<pair<double,int>>Q;
int main(){
int i,n,m;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
deg[u]++;deg[v]++;
}
for(i=1;i<n;i++)f[i]=1e10;
Q.push(make_pair(0,n));
while(!Q.empty()){
int p=Q.top().second;Q.pop();
if(vis[p])continue;
vis[p]=1;
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(!vis[q]){
cnt[q]++;
s[q]+=f[p];
f[q]=(s[q]+deg[q])/cnt[q];
Q.push(make_pair(-f[q],q));
}
}
}
printf("%.10f",f[1]);
return 0;
}
H
题目描述
解题思路
solved by nikkukun
AC代码 - by nikkukun
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
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pint;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
map<string,int> a[N];
int siz[N];
int idx;
void Insert(int u, string path, int osiz){
int p = 0;
while(p < path.size()){
if(path[p] == '/') break;
p++;
}
if(p < path.size()){
auto str = path.substr(0, p);
auto npath = path.substr(p+1, path.size() - (p+1));
if(a[u].find(str) == a[u].end())
a[u][str] = ++idx;
Insert(a[u][str], npath, osiz);
}
siz[u] += osiz;
}
int gate;
void DFS(int u, string path){
bool expand = 0;
for(auto p: a[u]){
int v = p.se;
if(siz[v] >= gate) expand = 1;
}
if(expand) cout << "- ";
else if(a[u].size()) cout << "+ ";
else cout << " ";
cout << path << ' ' << siz[u] << endl;
if(expand){
for(auto p: a[u]){
int v = p.se;
DFS(v, path + p.fi + "/");
}
}
}
int main(){
ios::sync_with_stdio(0);
int n; cin >> n;
for(int i=1; i<=n; i++){
string path; int osiz;
cin >> path >> osiz;
Insert(0, path, osiz);
}
cin >> gate;
DFS(1, "/");
return 0;
}
I
题目描述
给一个$1…n$的排列$a$，$q$次询问区间$[l,r]$，问最小的覆盖$[l,r]$区间的、满足排完序后连续的区间。
解题思路
首先考虑扩展区间$[i,i+1]$，不妨设$a_i<a_{i+1}$，则要使得$[i,i+1]$区间位于连续区间中，区间$[l,r]=$$[min_{a_i\leq j\leq a_{i+1}}pos_j,max_{a_i\leq j\leq a_{i+1}}pos_j]$必然也位于同一个区间中，这里的$l,r$容易通过$rmq$求得。可以说，区间$[i,i+1]$依赖区间$[l,l+1],[l+1,l+2],…,[r-1,r]$。
把区间$[i,i+1]$抽象为一个节点，对于每一个$i$，求出其依赖区间，连边建图缩点后转化成$DAG$上的动态规划问题，从叶节点向上不断更新实际依赖区间即可。
由于建图是$n^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
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
typedef long long ll;
using namespace std;
struct RMQ{
int i,j,mn[P][N],mx[P][N];
void init(int a[],int n){
for(i=1;i<=n;i++)mn[0][i]=mx[0][i]=a[i];
for(i=1;i<=P;i++){
for(j=1;j+(1<<i-1)<=n;j++){
mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<i-1)]);
mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
}
}
}
int querymax(int l,int r){
int d=__lg(r-l+1);
return max(mx[d][l],mx[d][r-(1<<d)+1]);
}
int querymin(int l,int r){
int d=__lg(r-l+1);
return min(mn[d][l],mn[d][r-(1<<d)+1]);
}
}range,qL,qR;
int ind[N];//ind[i]:[i,i+1]'s index in segtree
struct Edge{
int e,n;
}e[N<<2];
int hd[N<<1],cnt;
void adde(int a,int b){e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;}
int lc[N],rc[N];//[i,i+1]->[lc,rc+1](constraint)
int ql[N],qr[N];//[i,i+1]->[ql,qr](finally)
int a[N],pos[N];
int sta[N],top,vis[N];
int dfn[N],low[N],tot;
int colmn[N],colmx[N],col[N],num;
struct Seg{
int L[N<<2],R[N<<2];
void build(int p,int l,int r){
L[p]=l;R[p]=r;
if(l==r){
ind[l]=p;
return;
}
build(p<<1,l,(l+r)>>1);
build(p<<1|1,((l+r)>>1)+1,r);
}
void init(int p,int l,int r){
if(l==r)return;
adde(p,p<<1);
adde(p,p<<1|1);
init(p<<1,l,(l+r)>>1);
init(p<<1|1,((l+r)>>1)+1,r);
}
void add(int p,int x,int l,int r){
if(L[p]>r||R[p]<l)return;
if(L[p]>=l&&R[p]<=r){
adde(ind[x],p);
return;
}
add(p<<1,x,l,r);
add(p<<1|1,x,l,r);
}
void initcol(int p,int l,int r){
if(l==r)return;
if(col[p]!=col[p<<1])adde(col[p],col[p<<1]);
if(col[p]!=col[p<<1|1])adde(col[p],col[p<<1|1]);
initcol(p<<1,l,(l+r)>>1);
initcol(p<<1|1,((l+r)>>1)+1,r);
}
void addcol(int p,int x,int l,int r){
if(L[p]>r||R[p]<l)return;
if(L[p]>=l&&R[p]<=r){
if(col[ind[x]]!=col[p])adde(col[ind[x]],col[p]);
return;
}
addcol(p<<1,x,l,r);
addcol(p<<1|1,x,l,r);
}
}seg;
void tarjan(int p){
int i,q;
low[p]=dfn[p]=++tot;
sta[++top]=p;vis[p]=1;
for(i=hd[p];i;i=e[i].n){
q=e[i].e;
if(!dfn[q])tarjan(q),low[p]=min(low[p],low[q]);
else if(vis[q])low[p]=min(low[q],low[p]);
}
if(dfn[p]==low[p]){
num++;
colmn[num]=seg.L[p];
colmx[num]=seg.R[p];
while(sta[top+1]!=p){
q=sta[top];
col[q]=num;
vis[q]=0;
top--;
colmn[num]=min(colmn[num],seg.L[q]);
colmx[num]=max(colmx[num],seg.R[q]);
}
}
}
void dfs(int p){
int i;
vis[p]=1;
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(!vis[q])dfs(q);
colmn[p]=min(colmn[p],colmn[q]);
colmx[p]=max(colmx[p],colmx[q]);
}
}
int main(){
int i,n,m;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]),pos[a[i]]=i;
range.init(pos,n);
seg.build(1,1,n-1);
seg.init(1,1,n-1);
for(i=1;i<n;i++){
int x=a[i],y=a[i+1];
if(x>y)swap(x,y);
lc[i]=range.querymin(x,y);
rc[i]=range.querymax(x,y);
rc[i]--;
seg.add(1,i,lc[i],rc[i]);
}
for(i=1;i<n;i++)if(!dfn[ind[i]])tarjan(ind[i]);
//after tarjan
memset(hd,0,sizeof(hd));cnt=0;
seg.initcol(1,1,n-1);
for(i=1;i<n;i++)seg.addcol(1,i,lc[i],rc[i]);
for(i=1;i<=num;i++)
if(!vis[i])dfs(i);
//rmq
for(i=1;i<n;i++){
ql[i]=colmn[col[ind[i]]];
qr[i]=colmx[col[ind[i]]];
}
qL.init(ql,n-1);
qR.init(qr,n-1);
scanf("%d",&m);
while(m--){
int x,y;
scanf("%d%d",&x,&y);
if(x==y)printf("%d %d\n",x,y);
else printf("%d %d\n",qL.querymin(x,y-1),qR.querymax(x,y-1)+1);
}
return 0;
}
J
题目描述
给一棵树，求所有的正整数$k$满足：可以把树切成若干个大小为$k$的连通块，$n<1000000$。
解题思路
solved by nikkukun
$O(\sqrt n)$枚举每个因数，对于一个因数$k$，判断是否合法。
判断合法的根据：将所有子树大小为$k$的倍数的节点，与父亲的连边割断，如果恰好割断了$\frac nk -1$条边，那么合法，否则不合法。
AC代码 - by nikkukun
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
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> pint;
const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
vector<int> a[N];
int siz[N];
void DFS(int u, int pa){
siz[u] = 1;
for(auto v: a[u]){
if(v == pa) continue;
DFS(v, u);
siz[u] += siz[v];
}
}
int main(){
int n; scanf("%d", &n);
for(int i=1; i<n; i++){
int u, v;
scanf("%d%d", &u, &v);
a[u].push_back(v);
a[v].push_back(u);
}
DFS(1, 0);
vector<int> ans;
for(int d=1; d*d<=n; d++){
if(n % d) continue;
int cnt1 = 0, cnt2 = 0;
for(int i=2; i<=n; i++){
if(siz[i] % d == 0) cnt1++;
if(siz[i] % (n / d) == 0) cnt2++;
}
if(cnt1 >= n / d - 1) ans.push_back(n / d - 1);
if(d != 1 && d * d != n && cnt2 >= d - 1) ans.push_back(d - 1);
}
sort(ans.begin(), ans.end());
for(auto s: ans)
printf("%d ", s);
return 0;
}
K
题目描述
给$n$个长度为$7$的数字，一次操作表示将某个连续区间内所有数字轮换任意次数。要让所有数字最终处于最大值，问最少操作数。
解题思路
solved by qxforever
首先排掉$7$位均相同的数字，其他数字的轮换必然有且只有一个最大值，问题转化为“有$n$个$[0,6]$之间的数，一次操作是一个区间加某个值模$7$，问多少步能够使得所有数字变为$0$”。
将数组差分，问题变为：对于差分数组，一次操作为某个数$+x$，另一个数$-x$，问多少步能使所有数字变为$7$的倍数。
那么$1,6;2,5;3,4$分别配对，最后只剩下三种未配对的情况，$dp$一下求出最多可以配成多少对即可。
AC代码 - by qxforever
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
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 503;
int n;
int a[maxn],p[maxn],cnt[maxn];
unsigned char f[maxn][maxn][maxn];
int num[7];
struct to
{
int x,y,z;
}t[500];
int c=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
int t;scanf("%d",&t);
for(int j=0;j<7;j++){
num[j]=t;
t=(t%10)*1000000+t/10;
}
if(num[0]==num[1]) continue;
a[++c]=max_element(num,num+7)-num;
}
n=c;
for(int i=1;i<=n;i++) p[i]=(a[i]-a[i-1]+7)%7,cnt[p[i]]++;
int ans=cnt[0],u[3]={0};
for(int i=1;i<=3;i++){
int mn=min(cnt[i],cnt[7-i]);
ans+=mn;
cnt[i]-=mn,cnt[7-i]-=mn;
if(cnt[i]) u[i-1]=i;
else if(cnt[7-i]) u[i-1]=7-i;
}
cnt[0]=0;
int tot=0;
for(int i=0;i<=7;i++){
for(int j=0;j<=7;j++){
for(int k=0;k<=7;k++){
if(i==0&&j==0&&k==0) continue;
if((i*u[0]+j*u[1]+k*u[2])%7==0){
t[tot++]={i,j,k};
break;
}
}
}
}
for(int i=0;i<=cnt[u[0]];i++){
for(int j=0;j<=cnt[u[1]];j++){
for(int k=0;k<=cnt[u[2]];k++){
for(int l=0;l<tot;l++){
to q=t[l];
int x=q.x,y=q.y,z=q.z;
if(i>=x&&j>=y&&k>=z)f[i][j][k]=max((int)f[i][j][k],f[i-x][j-y][k-z]+1);
}
}
}
}
printf("%d",n-ans-f[cnt[u[0]]][cnt[u[1]]][cnt[u[2]]]);
return 0;
}
L
题目描述
给定平面上一堆平行于坐标轴或者成$45$度的正方形，求总覆盖面积。
解题思路
对两种情况分别做二维前缀和，对每个格子的四部分用二进制表示状态即可。
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
typedef long long ll;
using namespace std;
int a[N][N],b[N][N],s[N][N];
char st[10];
int main(){
int i,j,k,n,x,y,d;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%s%d%d%d",st,&x,&y,&d);
x+=M;y+=M;
if(st[0]=='A'){
a[x-d/2][y-d/2]++;
a[x+d/2][y-d/2]--;
a[x-d/2][y+d/2]--;
a[x+d/2][y+d/2]++;
}else{
b[x][y-d/2]++;
b[x+d/2][y]--;
b[x-d/2][y]--;
b[x][y+d/2]++;
}
}
for(i=2;i<N;i++){
for(j=1;j<N;j++){
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
b[j][i]+=b[j-1][i-1]+b[j+1][i-1]-b[j][i-2];
if(a[i][j])
s[i][j]=15;
if(b[j][i]){
int x=j,y=i;
s[x-1][y]|=(1<<2)+(1<<3);
s[x][y]|=(1<<1)+(1<<2);
s[x-1][y+1]|=(1<<0)+(1<<3);
s[x][y+1]|=(1<<0)+(1<<1);
}
}
}
int ans=0;
for(i=1;i<N;i++)
for(j=1;j<N;j++)
for(k=0;k<4;k++)ans+=(s[i][j]>>k)&1;
printf("%.2f",ans*0.25);
return 0;
}