CF tracker
Edu List
https://codeforces.com/contest/1612
F. Armor and Weapons
n个盾，m个武器
power = 盾idx + 武器idx
有q个 idx组合是加强的 power = qi(盾idx) + qj(武器idx) + 1(比沒有加強的多1)
初始，(盾1,武器1)
如果想得到 盾k 或者武器k, 那么power 需要>= k
同时只能持有两个， 所以之前得到过但是放弃的不能用于组合 也就是(a,b) -> (a, <= a+b+(?1)) or ( <= (a+b+?1), b)
问(1,1) -> (n,m) 的最小次数
范围
n,m 2e5
q 2e5
2s 512mb
我的思路
dp[m][n] = min(dp[m][n-m ~ n-1],dp[m][n-m-1] if (m,n-m-1)在q中), 对于另一侧固定，类似的
从小到大 的角度， 在沒有q的情況，就是(1,1) -> (1,2) -> (3,2) -> (3,5) -> (8,5) 這樣是最快的
如何處理有q的？
如果没有上界 (a,b)->(a,a+b+1), 那么如果继续固定a, 那么显然 (a,a+b+1) 不会比(a,a+b) 差， 因为(a,a+(a+b+1)) 都可达
问题是如果需要(a,a+b) -> (a+a+b,a+b) 呢
既然如此，又注意到不使用q都是log级别的次数
直接dp空间不够
所以变成
dp[a][step] = maxb
也就是求min step, 使得 dp[m][step] = n
有个问题是满足局部性吗
似乎不会证明
感觉需要改一改
dpa[a][step] = maxb 为最后一次是固定a 得到的maxb
dpb[b][step] = maxa 为最后一次是固定b 得到的maxa
dpa[a][step] = max(a+dpa[a][step-1]+(?1), a+wb+(?1) (dpb[wb][step-1] >= a))
dpb 同理
问题 对于给定 step, dpa内有单调性吗
似乎可以归纳一下，设给定step, dpa和dpb都是非严格单调递增,
那么step+1时，如果dpa[step+1][a] > dpa[step+1][a+1]
a+dpa[step][a]+1 <= (a+1) + dpa[step][a+1], 所以上一次不是固定a,
如果是固定b:
有额外点数 b+dpb[step][b](==a-b-1)+1 (更大则 都是b,更小则当前不可达), 只要(b+1)+dpb[step][b+1](>=a-b-1) 存在
无额外点数 b+dpb[step][b](==a-b) (更大则 都是b,更小则当前不可达), 只要(b+1)+dpb[step][b+1](>=a-b) 存在
但注意到这种情况是 a > b 那么必定比这种情况是 之前a不存在(否则之前存在一定是通过a而不是通过b)，所以只能通过b到达，所以得证
然后需要注意的是，如果其中一个很小，那么就需要 固定一个反复跳另一个, 这个时候就不要暴力了
写了一下发现并没有单调性
4次，(1,1)(1,2)(3,2)(3,5)(3,8)
4次，(1,1)(1,2)(3,2)(3,5)(8,5)
但4次，4的话最大只能得到7
所以还是暴力吧
代码
调了很久过了
https://codeforces.com/contest/1612/submission/193227902
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for(ll i=(a);i<(ll)(n);i++)
#define per(i,a,n) for(ll i=(n);i-->(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
vector<int> a2b[200010];
const int PWR = 30;
int main(){
ll n=read();
ll m=read();
vector dpa(PWR,vector<ll>(n+1,0));
vector dpb(PWR,vector<ll>(m+1,0));
int q=read();
while(q--){
int a=read();
int b=read();
a2b[a].push_back(b);
}
rep(a,1,n+1) if(a2b[a].size()>1) sort(begin(a2b[a]),end(a2b[a]));
dpa[0][1] = 1;
dpb[0][1] = 1;
auto hasab = [&](int a,int b) -> bool{
int ib = lower_bound(begin(a2b[a]),end(a2b[a]),b) - begin(a2b[a]);
return ib < (int)size(a2b[a]) and a2b[a][ib] == b;
};
auto hasba=[&](int b,int a){return hasab(a,b);};
rep(step,1,PWR){
auto update=[&](ll na,ll nb,auto &va,const auto&vb,auto has){
rep(a,1,na+1){
ll b = va[step-1][a];
if(b == 0) break;
va[step][a] = min(a+b+has(a,b),nb);
}
vector<ll> tmp(na+1,0);
rep(b,1,nb+1){
ll a = vb[step-1][b];
if(a == 0) break;
tmp[a] = max(tmp[a],b);
}
ll b = 0;
per(a,1,na+1){
if(tmp[a] == 0 and b == 0) continue;
b = max(b,tmp[a]);
va[step][a] = max(va[step][a], min(a+b+has(a,b),nb));
}
};
update(n,m,dpa,dpb,hasab);
update(m,n,dpb,dpa,hasba);
if(dpa[step][n] == m || dpb[step][m] == n) {
printf("%lld\n",step);
return 0;
}
}
auto out=[&](ll na,ll nb,ll b,auto has){
int ans=PWR-1;
while(b < nb){
b = min(nb, na + b + has(na,b));
ans++;
}
printf("%d\n",ans);
};
if(n < m){
out(n,m,dpa[PWR-1][n],hasab);
}else{
out(m,n,dpb[PWR-1][m],hasba);
}
return 0;
}
|
G. Max Sum Array
给长m数组c
需要构建 数组a，包含[1..m] 其中i出现c[i]次
f(a) = sum(j-i) , 其中a[i] = a[j], i < j
求max f(a), 和能得到这个max值的不同a的个数 mod 1e9+7
范围
m 5e5
ci [1,1e6]
2s
256mb
我的思路
显然 不同值之间不会影响贡献， 只是插入到之间影响距离会影响贡献
那么对于同样的a, 贡献 = 最大-最小
显然是一个方案， 是否有办法更大？
只出现一次的全部放在最中间
显然 出现>=2次的如果有x个，那麼前缀x个和后綴x个一定要每个出现且只出现一次, 除了前缀和后缀，对中间的值的放置无影响
否则如果有不出现，的和重复出现的做交换一定 交换后更优
而出现了的 根据排序交换原理，总可以通过相邻交换得到
而注意到 如果 ...ij...].......[..ki... 中ki 交换， 那么i的贡献-1,而k的贡献+1 总贡献不变
所以这就是最大值且无法得到更大的
那么答案就是 x!(前缀) * x!(后缀) * binom(n-2x,c[i]-2?...)
似乎就没了
想得有点问题， 并不是最大和最小之差，因为是想等的两两之差
那么 posj-posi 被计算了 左边相等次数 * 右边相等次数
似乎相互影响的会变复杂
如果依然考虑交换呢
对于颜色 a和b
如果 交换a和b, 那么变化也是复杂的
如果先选定相邻不同颜色的位置， 再考虑颜色，和交换
1
2
3
4
| a....ba..baa..b.aa
xx
la ra
lb rb
|
那么 对于a来说 左侧-1右侧+1, -la*(ra+1) + (la+1)*ra = ra-la
那么 对于b来说 左侧+1右侧-1, lb*(rb+1) - (lb+1)*rb = lb-rb
也就是判断 (ra-la) - (rb-lb) >= 0 即ra-la >= rb - lb
注意同色点 对应的r-l 也就是 5 3 1 -1 3 5 或者 4 2 0 -2 4 的形状
所以它不至有局部性也有全局性
似乎就没了
然后注意ci * m 还是比较大，所以前缀和处理一下
算最大值同样，不妨直接从长到短放, 这样能保证距离一致
那么 +1~+3 的距离 就是 len(1) + len(2) 再乘上贡献和
t = (+1+3)/2 = 2
对于长度c 的贡献为 (c-t)(c+t)/4 = 1/4c^2 - 1/4t^2
所以需要知道多少个比它大，不同奇偶的 ci, 的 c^2/4和 与 -个数* t^2/4
类似的 -3~-1的距离 是 len(-3)+len(-2) -1
代码
https://codeforces.com/contest/1612/submission/193242305
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for(ll i=(a);i<(ll)(n);i++)
#define per(i,a,n) for(ll i=(n);i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
const int C = 1000000;
ll c[500010];
ll fac[C+10]={1};
ll qpow(ll b,ll p){
ll r=1;
while(p){
if(p%2) (r*=b)%=MOD;
(b*=b)%=MOD;
p/=2;
}
return r;
}
int main(){
int m=read();
rep(i,0,m) c[i]=read();
rep(i,1,C+1) fac[i]=fac[i-1]*i%MOD;
vector<ll> pres(C+10,0);
rep(i,0,m){
pres[(c[i] - 1)%2] += 1;
pres[c[i] + 1] -= 1;
}
ll ans = 1;
rep(i,0,C+1){
if(i > 1) pres[i] += pres[i-2];
if(i==0) (ans *= fac[pres[i]])%=MOD;
else (ans *= fac[pres[i]]*fac[pres[i]]%MOD)%=MOD;
}
vector gesqsum(C+10,0);
vector gecnt(C+10,0);
ll inv4 = qpow(4,MOD-2);
rep(i,0,m){
gecnt[c[i]]++;
(gesqsum[c[i]]+=c[i]*c[i]%MOD)%=MOD;
}
per(i,0,C){
(gesqsum[i]+=gesqsum[i+2])%=MOD;
gecnt[i]+=gecnt[i+2];
}
ll len = 0;
rep(i,0,C+1){
{
ll dis = pres[i]+pres[i+1];
ll cnt = (gesqsum[i+3]*inv4 - gecnt[i+3]*((i+1)*(i+1)%MOD)%MOD*inv4%MOD)%MOD;
(len+=dis*cnt%MOD)%=MOD;
}
if(i==0) continue;
{
ll dis = pres[i]+pres[i-1];
ll cnt = (gesqsum[i+1]*inv4 - gecnt[i+1]*((i-1)*(i-1)%MOD)%MOD*inv4%MOD)%MOD;
(len+=dis*cnt%MOD)%=MOD;
}
}
printf("%lld %lld\n",(len+MOD)%MOD,ans);
return 0;
}
|
总结
都可以自己过，就是编码太慢
F. 虽然能自己写出来 但是写了半天
G. 也自己把它过了，而且感觉细节比F好想很多
参考
官方