arc063-067
E. Integers on a Tree
构造题。一般这种二选一都是先钦定一种，再改成另一种。我们不妨假设所有儿子权值都是父节点 $+1$。
这样我们钦定父节点是儿子中权值最大的点 $-1$。如果父节点有值且比这个权值小那么直接无解。
然后考虑从上到下，如果一个子节点小于父节点 $-1$ 那么改成父节点 $-1$。如果不合法就无解。
复杂度 $O(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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define N 100010
#define inf 100000000
using namespace std;
int nxt[N<<1],to[N<<1],head[N],cnt;
void add(int u,int v)
{
nxt[++cnt]=head[u];
to[cnt]=v;
head[u]=cnt;
}
int w[N],val[N];
void dfs(int u,int p)
{
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==p) continue;
dfs(v,u);
val[u]=max(val[u],val[v]-1);
}
if(w[u]>-inf && val[u]>w[u]){puts("No");exit(0);}
val[u]=max(val[u],w[u]);
}
void dfs2(int u,int p)
{
if(w[u]>-inf && w[u]!=val[u]){puts("No");exit(0);}
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==p) continue;
if(val[v]!=val[u]+1 && val[v]!=val[u]-1) val[v]=val[u]-1;
dfs2(v,u);
}
}
int main()
{
int n,q;
scanf("%d",&n);
for(int i=1;i<=n;i++) w[i]=val[i]=-inf;
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
scanf("%d",&q);
while(q --> 0)
{
int x,v;
scanf("%d%d",&x,&v);
w[x]=v;
}
dfs(1,0);
dfs2(1,0);
puts("Yes");
for(int i=1;i<=n;i++) printf("%d\n",val[i]);
return 0;
}
|
F. Snuke’s Coloring 2
首先考虑答案一定可以达到 $2\max(n,m)+2$ 级别。换句话说要么经过 $x$ 中线，要么经过 $y$ 中线。
不妨假设经过 $x$ 中线。按照套路我们假设一个必经的 $y$ 线，然后对于每个位置我们可以处理出其左右最远延伸的位置。
由于 $x$ 和 $y$ 是线性相加的，所以可以直接单调队列 + 双指针维护最大值。
注意我们双指针的其实是左端点较小值，单调队列的是右端点的较小值。所以对于左端点上下两块作为最小值的情况都要做一遍。
复杂度 $O(n\log 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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 300010
using namespace std;
struct node{
int x,y;
bool operator <(const node a)const{return x<a.x;}
}p[N];
int lf[N],rf[N],n,m,k,mx;
int q[N],ql,qr,ans;
void solve(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
solve(l,mid);solve(mid+1,r);
lf[mid]=lf[mid+1]=0,rf[mid]=rf[mid+1]=m;
for(int i=mid-1;i>=l;i--)
{
lf[i]=lf[i+1];rf[i]=rf[i+1];
if(p[i+1].y<=mx) lf[i]=max(lf[i],p[i+1].y);
if(p[i+1].y>=mx) rf[i]=min(rf[i],p[i+1].y);
}
for(int i=mid+2;i<=r;i++)
{
lf[i]=lf[i-1];rf[i]=rf[i-1];
if(p[i-1].y<=mx) lf[i]=max(lf[i],p[i-1].y);
if(p[i-1].y>=mx) rf[i]=min(rf[i],p[i-1].y);
}
ql=1,qr=0;int tr=mid+1,tl=mid;
for(;tl>=l;tl--)
{
for(;tr<=r && lf[tr]<=lf[tl];q[++qr]=tr++)
for(;ql<=qr && rf[q[qr]]+p[q[qr]].x<=rf[tr]+p[tr].x;qr--);
for(;ql<qr && rf[tl]+p[q[ql]].x<=rf[q[ql+1]]+p[q[ql+1]].x;ql++);
ans=max(ans,p[q[ql]].x-p[tl].x+min(rf[tl],rf[q[ql]])-lf[tl]);
}
ql=1,qr=0;tr=mid+1,tl=mid;
for(;tr<=r;tr++)
{
for(;tl>=l && lf[tl]<=lf[tr];q[++qr]=tl--)
for(;ql<=qr && rf[q[qr]]-p[q[qr]].x<=rf[tl]-p[tl].x;qr--);
for(;ql<qr && rf[tr]-p[q[ql]].x<=rf[q[ql+1]]-p[q[ql+1]].x;ql++);
ans=max(ans,p[tr].x-p[q[ql]].x+min(rf[tr],rf[q[ql]])-lf[tr]);
}
}
void make()
{
sort(p+1,p+k+1);mx=m/2;
p[0]=(node){0,mx};
p[k+1]=(node){n,mx};
solve(0,k+1);
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++) scanf("%d%d",&p[i].x,&p[i].y);
ans=max(n,m)+1;
make();
swap(n,m);
for(int i=1;i<=k;i++) swap(p[i].x,p[i].y);
make();
printf("%lld",ans*2ll);
return 0;
}
|
E. Cosmic Rays
大水题。直接处理两两之间的最短路，用不带优化的 $dijkstra$。复杂度 $O(n^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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 1010
#define db double
#define inf 1e17
using namespace std;
struct cir{
int x,y,r;
}c[N],s,t;
db dist(cir a,cir b){return max(sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y))-a.r-b.r,0.0);}
db dis[N];
bool vis[N];
int main()
{
scanf("%d%d%d%d",&s.x,&s.y,&t.x,&t.y);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].r);
c[++n]=t;c[0]=s;
for(int i=1;i<=n;i++) dis[i]=dist(c[i],s);
for(int i=1;i<=n;i++)
{
int u=0;
for(int j=1;j<=n;j++)
if(!vis[j] && (!u || dis[u]>dis[j])) u=j;
vis[u]=true;
for(int j=1;j<=n;j++)
if(!vis[j]) dis[j]=min(dis[j],dis[u]+dist(c[u],c[j]));
}
printf("%.8lf",dis[n]);
return 0;
}
|
F. Rotated Palindromes
首先定义 $f_i$ 表示长度为 $i$ 且没有循环节的回文串个数。
容斥一下显然有
$$f_i=K^{\lceil\frac i2\rceil}-\sum_{d|i}f_d$$
$$\text{ans}=\sum_{i|n}f_i\times\frac i{1+[i\text{ is even}]}$$
可以发现这个式子严格不强于杜教筛的那个式子，故直接记忆化搜索复杂度 $O(n^{\frac 34})$，实际跑不满。
查看代码
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#define mod 1000000007
using namespace std;
int ksm(int a,int b=mod-2)
{
int r=1;
for(;b;b>>=1)
{
if(b&1) r=1ll*r*a%mod;
a=1ll*a*a%mod;
}
return r;
}
int n,k;
map<int,int>f;
int calc(int x)
{
if(x==1) return k;
if(f.count(x)) return f[x];
int res=ksm(k,(x+1)/2);
for(int i=1;1ll*i*i<=x;i++)
if(x%i==0)
{
res=(res-calc(i)+mod)%mod;
if(i!=1 && i*i!=x) res=(res-calc(x/i)+mod)%mod;
}
return f[x]=res;
}
int main()
{
int ans=0;
scanf("%d%d",&n,&k);
for(int i=1;1ll*i*i<=n;i++)
if(n%i==0)
{
ans=(ans+1ll*calc(i)*(i%2?i:i/2))%mod;
if(i*i!=n) ans=(ans+1ll*calc(n/i)*((n/i)%2?(n/i):(n/i/2)))%mod;
}
printf("%d",ans);
return 0;
}
|
E. Manhattan Compass
首先转切比雪夫距离，这样一个条件可以看作 $\Delta x=D,\Delta y\leq D$ 和反过来。不妨先考虑 $\Delta x=D$ 的情况。
这样对 $x$ 排序后每个 $y$ 对应的就是一个区间。但是直接连边显然会炸。考虑如果当前区间与上一个区间有交，那么只需要与上一个区间连一条边即可。
所以我们每次把连边的区间与上一个区间右端点取 $\max$，这样每个点最多被连 $2$ 次，然后跑一个 $dfs$ 即可。
复杂度 $O(n\log 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
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
#define N 200010
using namespace std;
struct node{
int x,y,u;
node(int X=0,int Y=0):x(X),y(Y),u(0){}
node(int X,int Y,int D):x(X+Y),y(X-Y),u(D){}
bool operator <(const node a)const{return x==a.x?y<a.y:x<a.x;}
}p[N];
node operator +(const node a,const node b){return node(a.x+b.x,a.y+b.y);}
int nxt[N<<3],to[N<<3],head[N],cnt;
void add(int u,int v)
{
nxt[++cnt]=head[u];to[cnt]=v;
head[u]=cnt;
}
int deg[N],n;
void solve(int dx,int dy)
{
sort(p+1,p+n+1);node lp=node(-dx,-dy),rp=node(-dx,dy+1);
for(int i=1,l=1,r=1,v=1;i<=n;i++,v--)
{
for(;l<n && p[l]<p[i]+lp;l++);
for(;r<=n && p[r]<p[i]+rp;r++);
deg[p[i].u]+=r-l;
for(v=max(v,l);v<r;v++)
add(p[i].u,p[v].u),add(p[v].u,p[i].u);
}
}
bool vis[N];
ll dfs(int u)
{
ll ans=deg[u];vis[u]=true;
for(int i=head[u];i;i=nxt[i])
if(!vis[to[i]]) ans+=dfs(to[i]);
return ans;
}
int main()
{
int a,b;
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;i++)
{
int x,y;scanf("%d%d",&x,&y);
p[i]=node(x,y,i);
}
int D=max(abs(p[a].x-p[b].x),abs(p[a].y-p[b].y));
solve(D,D);
for(int i=1;i<=n;i++) swap(p[i].x,p[i].y);
solve(D,D-1);
printf("%lld",dfs(a));
return 0;
}
|
F. Shuffling
首先如果两个操作 $[l,r],[l’,r’],l<l’$ 如果有 $r>r’$ 那么 $[l’,r’]$ 显然莫的用处。
这样我们也可以选定若干没用用处的区间，即对于每一个 $i$ 我们都找到最右端不改变答案的值 $p_i$。
考虑处理到 $i$ 时，我们能做的是讨论 $i$ 是 $0$ 还是 $1$。
考虑进行 $dp$。用 $f_{i,j}$ 表示已经处理了 $[1,p_{i-1}]$，当前候选列中还有 $j$ 个 $1$（即还有 $j$ 个 $1$ 可以被任意放置于后续位置）。
首先这次操作会使得 $(p_{i-1},p_i]$ 的 $1$ 加入候选列。如果填 $1$ 会导致候选列中 $1$ 个数减 $1$。
复杂度 $O(n^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
| #include<iostream>
#include<cstdio>
#include<cstring>
#define N 3010
#define mod 1000000007
using namespace std;
int pos[N],f[N][N];
char s[N];
int g[N],fac[N],inv[N];
int ksm(int a,int b=mod-2)
{
int r=1;
for(;b;b>>=1)
{
if(b&1) r=1ll*r*a%mod;
a=1ll*a*a%mod;
}
return r;
}
void init(int n=N-10)
{
for(int i=fac[0]=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=ksm(fac[n]);
for(int i=n-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
int C(int a,int b){return a<b || b<0?0:1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
scanf("%s",s+1);
init();
s[++n]='0';
for(int i=1;i<=n;i++) pos[i]=i;
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
pos[l]=max(pos[l],r);
}
for(int i=1;i<=n;i++) g[i]=g[i-1]+(s[i]=='1');
for(int i=2;i<=n;i++) pos[i]=max(pos[i],pos[i-1]);
f[0][0]=1;
for(int i=1;i<=n;i++)
{
int d=g[pos[i]]-g[pos[i-1]];
for(int j=0;j<=pos[i-1]-(i-1);j++)
f[i][j+d]=(f[i-1][j]+f[i-1][j+1])%mod;
}
printf("%d\n",f[n][0]);
return 0;
}
|
D. Xor Sum
可以发现
1
| x+y = (x&y)<<1 + (x ^ y)
|
容易证明，如果没有 $n$ 的限制，每一位 $(x,y)$ 只有 ${(0,0),(1,0),(1,1)}$。
对三种情况讨论，有 $f_{i,j}\rightarrow f_{i+1,j2},f_{i+1,j2+1},f_{i+1,j*2+2}$。
反过来就可以直接 $dp$。
容易发现时间复杂度 $T(n)=T(\frac{n}2)+T(\frac{n}2-1)+O(\log n)$。
容易证明复杂度 $O(\log^2 n)$ 级别。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#define ll long long
#define mod 1000000007
using namespace std;
map<ll,int>f;
int F(ll x)
{
if(f.count(x)) return f[x];
return f[x]=((ll)F(x/2)+F((x-1)/2)+F((x-2)/2))%mod;
}
int main()
{
f[0]=1;f[1]=2;
ll n;
scanf("%lld",&n);
printf("%d",F(n));
return 0;
}
|
E. Addition and Subtraction Hard
考虑括号一定加在减号后面，且最多不会套超过两层，否则一定可以被替换掉。
所以用 $f_{i,j}$ 表示到 $i$ 套了 $j$ 层括号的方案数。
复杂度 $O(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
| #include<iostream>
#include<cstdio>
#include<cstring>
#define N 100010
#define ll long long
#define inf 10000000000000000ll
using namespace std;
ll f[N][3];
char op[2];
int main()
{
int n,x;
scanf("%d%d",&n,&x);
f[1][0]=x;f[1][1]=f[1][2]=-inf;
for(int i=2;i<=n;i++)
{
scanf("%s%d",op,&x);
if(op[0]=='-') x=-x;
memcpy(f[i],f[i-1],sizeof(f[i]));
f[i][0]=max(f[i][0],f[i-1][1])+x;
f[i][1]=max(f[i][1],f[i-1][2])-x;
f[i][2]+=x;
if(op[0]=='-') f[i][2]=max(f[i][2],f[i][1]),f[i][1]=max(f[i][1],f[i][0]);
}
printf("%lld\n",max(f[n][1],f[n][0]));
return 0;
}
|
F. Contest with Drinks Hard
考虑区间 $[l,r]$ 如果选择了，那么满足条件的二元组等于 $\binom{r-l+1}{2}$。拆开显然是一个与区间程度有关的二次函数。
考虑如何处理修改。令 $f_i$ 表示 $[1,i]$ 的答案，$g_i$ 表示 $[i,n]$ 的答案，$h_i$ 表示强制选择 $i$ 的答案，显然单次修改的答案就是 $\max(f_{i-1}+g_{i+1},h_i+X-a_i)$。
$f$ 和 $g$ 可以通过斜率优化求出，考虑求出 $h$。用分治，处理区间 $[l,r]$ 强制经过 $m=\lfloor\frac{l+r}{2}\rfloor$ 的情况，可以发现左右两边各是两个斜率优化。
所以总共四个斜率优化。复杂度 $O(n\log n)$。瓶颈在于分治。
代码咕咕咕了
E. Grouping
直接 dp，令 $f_{i,j}$ 表示已经选了 $i$ 个人，当前的组是 $j$ 组。枚举一下当前组选多少个。
复杂度 $O(n^2\ln n)$。
太水了，代码咕咕咕了。
F. Yakiniku Restaurants
不带 $\log$ 的做法还是挺妙的。
首先发现 $n$ 很小，也就是说最后可以枚举答案是哪一段区间。考虑对于每一个 $b_{i,j}$ 求出它会对那些区间造成贡献，这个可以通过单调栈求出。
这样就变成一个二维数点问题。由于矩形长度只有 $5000$，直接前缀和即可。复杂度 $O(n^2+nm)$。
查看代码
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#define N 5010
#define M 210
#define inf 1000000007
#define ll long long
using namespace std;
ll a[N],c[N][N];int b[N][M];
int l[N],r[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=2;i<=n;i++) scanf("%lld",&a[i]),a[i]+=a[i-1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&b[i][j]);
for(int i=1;i<=m;i++) b[0][i]=b[n+1][i]=inf;
for(int p=1;p<=m;p++)
{
static int s[N];
int tp=1;s[1]=0;
for(int i=1;i<=n;i++)
{
while(b[s[tp]][p]<b[i][p]) tp--;
l[i]=s[tp]+1;s[++tp]=i;
}
tp=1;s[1]=n+1;
for(int i=n;i>=1;i--)
{
while(b[s[tp]][p]<b[i][p]) tp--;
r[i]=s[tp]-1;s[++tp]=i;
}
for(int i=1;i<=n;i++)
{
int v=b[i][p];
c[l[i]][i]+=v;c[i+1][i]-=v;
c[l[i]][r[i]+1]-=v;c[i+1][r[i]+1]+=v;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) c[i][j]+=c[i-1][j]+c[i][j-1]-c[i-1][j-1];
ll ans=0;
for(int l=1;l<=n;l++)
for(int r=l;r<=n;r++) ans=max(ans,c[l][r]-(a[r]-a[l]));
printf("%lld\n",ans);
return 0;
}
|