总结近日杂题。
没有代码的就是懒得写了。
模拟赛一
数据范围：。
原问题是经典单调栈，以每个位置作为最小值时算贡献，所以只需要找到左侧第一个小于自己和右侧第一个小于自己即可。
考虑修改对上述贡献带来的影响。
首先可以发现，一个位置要修改的话，改成 一定不劣。
如果这个位置是某个中心位置的左侧第一个小于中心或右侧第一个小于中心的位置，那么该中心的答案显然会变优。
所以需要对每个位置找到左侧第二个小于自己和右侧第二个小于自己的位置。
可以维护两个以高度为下标，位置为权值的树状数组，那么只需要查前缀 和后缀 即可。
所以可以枚举中间位置，然后看是左侧第一个小于自己的改更优还是右侧第一个小于自己的改更优。
还有一种情况：修改中间位置更优。
所以还需要求出左侧第一个小于 和右侧第一个小于 的位置。
复杂度 。
场上写了 暴力找的做法，直接冲到最优解了，不知道数据为什么不卡。
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
| #include"bits/stdc++.h"
#define re register
#define int long long
#define max(a,b) (a<b?b:a)
using namespace std;
const int maxn=1e6+10;
int n,H,ans;
int h[maxn],sw[maxn];
int lid[maxn],rid[maxn];
int l[maxn],r[maxn];
int top,stk[maxn];
signed main(){
freopen("poster.in","r",stdin);
freopen("poster.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>H;
for(re int i=1,w;i<=n;++i){
cin>>h[i]>>w;
sw[i]=sw[i-1]+w;
}
for(re int i=1;i<=n;++i){
while(top&&h[stk[top]]>h[i]) rid[stk[top--]]=i;
stk[++top]=i;
}
while(top) rid[stk[top--]]=n+1;
for(re int i=n;i>=1;--i){
while(top&&h[stk[top]]>h[i]) lid[stk[top--]]=i;
stk[++top]=i;
}
while(top) lid[stk[top--]]=0;
int id=0;
for(re int i=1;i<=n;++i){
if(h[i]<H) l[i]=id,id=i;
else l[i]=id;
}
id=0;
for(re int i=n;i>=1;--i){
if(h[i]<H) r[i]=id,id=i;
else r[i]=id;
}
for(re int i=1,lid2,rid2;i<=n;++i){
if(h[i]>H) ans=max(ans,(sw[rid[i]-1]-sw[lid[i]])*h[i]);
else{
ans=max(ans,(sw[r[i]-1]-sw[l[i]])*H);
lid2=0,rid2=n+1;
for(re int j=lid[i]-1;j>=1;--j) if(h[j]<h[i]){lid2=j;break;}
for(re int j=rid[i]+1;j<=n;++j) if(h[j]<h[i]){rid2=j;break;}
ans=max(ans,max((sw[rid2-1]-sw[lid[i]])*h[i],(sw[rid[i]-1]-sw[lid2])*h[i]));
}
}
cout<<ans<<'\n';
return 0;
}
|
模拟赛二
数据范围：。
一道部分分对正解没有任何启发意义的题。
先说我在场上打的部分分。
枚举 是没前途的，所以考虑对于一对 求有多少 合法。
然后发现这东西可以拆位然后 DP。
设 表示从低位到高位考虑到第 位， 是否向 进位， 是否向 进位。
转移就是考虑 这一位填什么。
答案为 。
非常麻烦，要大力分讨。
复杂度 。
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
| #include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=2e4+10,maxk=65,mod=998244353;
int n,k,cnt,S,ans;
int a[maxn],num[maxn],f[maxk][2][2];
inline string to_String(int x){
string s=" ";
for(re int i=1;i<=k;++i){
if(((x>>(i-1))&1)==1) s+='1';
else s+='0';
}
return s;
}
inline int solve(int x,int y){
string a1=to_String(x),a2=to_String(y);
for(re int i=1;i<=k;++i) for(re int j=0;j<=1;++j) for(re int p=0;p<=1;++p) f[i][j][p]=0;
for(re int i=1;i<=k;++i){
if(a1[i]=='0'&&a2[i]=='0'){
f[i][0][0]=(f[i][0][0]+(f[i-1][0][0]+f[i-1][0][1]+f[i-1][1][1]+f[i-1][0][0]))%mod;
f[i][1][0]=(f[i][1][0]+f[i-1][1][0])%mod;
f[i][1][1]=(f[i][1][1]+f[i-1][1][1])%mod;
}
if(a1[i]=='0'&&a2[i]=='1'){
f[i][0][0]=(f[i][0][0]+(f[i-1][1][0]+f[i-1][0][0]))%mod;
f[i][0][1]=(f[i][0][1]+(f[i-1][0][1]+f[i-1][0][1]))%mod;
f[i][1][1]=(f[i][1][1]+(f[i-1][1][0]+f[i-1][1][1]))%mod;
}
if(a1[i]=='1'&&a2[i]=='0'){
f[i][0][0]=(f[i][0][0]+f[i-1][0][1])%mod;
f[i][1][0]=(f[i][1][0]+(f[i-1][1][0]+f[i-1][0][0]+f[i-1][1][0]+f[i-1][1][1]))%mod;
f[i][1][1]=(f[i][1][1]+f[i-1][0][1])%mod;
}
if(a1[i]=='1'&&a2[i]=='1'){
f[i][0][0]=(f[i][0][0]+f[i-1][0][0])%mod;
f[i][1][0]=(f[i][1][0]+f[i-1][1][0])%mod;
f[i][1][1]=(f[i][1][1]+(f[i-1][0][0]+f[i-1][0][1]+f[i-1][1][1]+f[i-1][1][1]))%mod;
}
}
return (f[k][0][0]+f[k][0][1]+f[k][1][1])%mod;
}
signed main(){
freopen("subset.in","r",stdin);
freopen("subset.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;S=(1ll<<k)%mod;
for(re int i=1;i<=n;++i) cin>>a[i];
sort(a+1,a+n+1);a[0]=-1;
for(re int i=1;i<=n;++i){
if(a[i]!=a[i-1]) a[++cnt]=a[i],num[cnt]=1;
else ++num[cnt];
}
f[0][0][0]=1;
for(re int i=1;i<=cnt;++i){
ans=(ans+S*num[i]*num[i])%mod;
for(re int j=i+1;j<=cnt;++j){
ans=(ans+num[i]*num[j]*solve(a[i],a[j]))%mod;
}
}
cout<<ans;
return 0;
}
|
然后是正解。
上面这个 DP 没有任何前途，考虑换一个算贡献的方式。
首先有结论：
是 的子集等价于 是 的子集。
所以对于一对 ， 是 的子集等价于 是 的子集。
我们不需要关心 的进位，因为 ，且 ，所以不存在进位以后多贡献一次的情况。
那么只需要求在 中 的超集个数即可。
答案为 ，其中 为 的 的个数。
复杂度
模拟赛三
数据范围：。
以下假设原序列单调不降。
可以发现，只有在 时，才有可能把数变为 ，否则只能变成 或 。
那么对于 的部分是比较好做的。
我们枚举一个分界线，在分界线左侧的都变为 ，右侧的都变为 。
可以发现，这个 不用枚举，因为取右侧的中位数一定是最优的。
然后考虑 的部分。
可以发现，变为 最优的值的范围为 。
所以序列会分成 段，那么对这 段分别求即可。
怎么维护这些连续段呢？
可以发现，当 时，每一段都会向右移动，且长度单调不降。
所以可以维护 个指针，在 增大时维护指针的移动即可。
当然也有一种好写做法：每次找区间时都二分，这样会多带一个 ，不过小常数可以通过。
复杂度 。
我会弱化版。
为什么思考的角度总是不对呢···
看到这个 不好搞，所以考虑每个值在自己成为 时算答案。
那么我们需要对每个位置，找到它右侧最后一个大于它的数。
我们可以以 为下标，位置作为权值，然后做一个后缀 。
但是需要离散化，所以复杂度 。
瓶颈竟然在于离散化，绷不住了。
但我们从 入手的那一刻就注定了我们不会有更优的复杂度。
所以我们换个角度：从位置入手。
下文的 对应原题的 。
首先有性质：
且 ，都有 。
所以考虑单调栈。
若当前的数 大于栈顶的 ，则用 更新答案。
然后这个 就再也没用了，将其弹出。
重复上述过程即可。
复杂度
简单题。
假设两人的路径在点 相交，则代价为 。
枚举交点即可。
双倍经验：[NOIP2013 提高组] 货车运输
Kruskal 重构树裸题。
最小边权最大值，建出最大Kruskal 重构树然后倍增时求最小值即可。
我是换根低手。
对于这种 在 路径上的信息统计，可以考虑枚举 ，然后算 能对哪些点对产生贡献。
因为只有 才能产生贡献，所以对于 ，我们只把 的 的权值设为 ，这样就好统计了。
具体实现可以枚举 时，在算完 后把它加进去。
然后考虑 关于 的位置关系。
- 点 在 子树中，点 不在
- 点 在 子树中，点 不在
- 点 都在 子树中，但不在同一颗子树
对应到操作上只有：单点加区间加区间查。
线段树轻松维护，不过我差分了一下然后写的树状数组。
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
| #include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=2e5+10;
int n,dfn,cnt;
int head[maxn];
struct node{
int fa,l,r;
}t[maxn];
struct edge{
int to,nxt;
}e[maxn<<1];
struct BIT{
int tr[maxn];
#define lb(x) (x&(-x))
inline void add(int x,int val){while(x<=n) tr[x]+=val,x+=lb(x);}
inline void add(int l,int r,int val){add(l,val),add(r+1,-val);}
inline int query(int x){int res=0;while(x) res+=tr[x],x-=lb(x);return res;}
inline int query(int l,int r){return query(r)-query(l-1);}
}a,b;
inline void add(int u,int v){
e[++cnt]={v,head[u]};
head[u]=cnt;
}
inline void dfs(int u,int fa){
t[u].l=++dfn;t[u].fa=fa;
for(re int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs(v,u);
}
t[u].r=dfn;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(re int i=1,u,v;i<n;++i) cin>>u>>v,add(u,v),add(v,u);
dfs(1,0);
for(re int w=1;w<=n;++w){
a.add(t[w].l,t[w].r,b.query(t[1].l,t[1].r)-b.query(t[w].l,t[w].r));
a.add(1,t[w].l-1,b.query(t[w].l,t[w].r));
a.add(t[w].r+1,n,b.query(t[w].l,t[w].r));
for(re int i=head[w];i;i=e[i].nxt){
int u=e[i].to;
if(u==t[w].fa) continue;
a.add(t[u].l,t[u].r,b.query(t[w].l,t[w].r)-b.query(t[u].l,t[u].r));
}
a.add(t[w].l,t[w].l,b.query(t[w].l,t[w].r));
b.add(t[w].l,1);
}
for(re int i=1;i<=n;++i) cout<<a.query(t[i].l)<<' ';
return 0;
}
|
容易得到暴力 DP。
设 表示 的最小次数，转移为
直接考虑从哪转移来没法优化，我们考虑一个状态能向哪些状态贡献。
可以发现，。
只需要用最大的合法 去转移即可。
然后你发现这东西能单调队列。
复杂度