Atcoder abc264

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
F(DP),G(spfa),Ex(树)

https://atcoder.jp/contests/abc264/tasks

F - Monochromatic Path

给定 h行 w列 黑/白 格子

可以 支付R[i] 翻转第i行

可以 支付C[j] 翻转第j列

求最小代价,让从(1,1)到(h,w) 有一条同色只向下/右走的路径

范围

h,w 2000

ri,ci 1e9

2s

1024mb

我的思路

然后 记走到 dp[i][j][i行是否翻转 0/1][j列是否翻转0/1]的最小代价

dp[i][j][计算出是否翻转][sj] = dp[i-1][j][0/1][sj] 因为知道[i-1][j]的颜色和j的翻转状态

dp[i][j][si][计算出是否翻转] = dp[i][j-1][si][0/1] 因为知道[i][j-1]的颜色和i的翻转状态

那么 就没了?

代码

https://atcoder.jp/contests/abc264/submissions/35595592

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _(i,n) for (ll i=0;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}

ll dp[2010][2010][2][2];
const ll INF=0x3f3f3f3f3f3f3f3f;
ll r[2010];
ll c[2010];

int a[2010][2010];
char s[2010];
void setMin(ll&a,ll b){a=min(a,b);}

int main(){
  int h=read();
  int w=read();
  _(i,h)r[i]=read();
  _(j,w)c[j]=read();
  _(i,h){
    scanf("%s",s);
    _(j,w)a[i][j]=s[j]-'0';
  }
  _(i,h)_(j,w)_(x,2)_(y,2)dp[i][j][x][y]=INF;
  _(x,2)_(y,2)dp[0][0][x][y]=x*r[0]+y*c[0];
  _(i,h)_(j,w)_(x,2)_(y,2){
    ll cost=dp[i][j][x][y];
    if(cost==INF)continue;
    int color=a[i][j]^x^y;
    if(i+1<h){
      int rev=color^a[i+1][j]^y;
      setMin(dp[i+1][j][rev][y],cost+rev*r[i+1]);
    }
    if(j+1<w){
      int rev=color^a[i][j+1]^x;
      setMin(dp[i][j+1][x][rev],cost+rev*c[j+1]);
    }
  }
  ll ans=INF;
  _(x,2)_(y,2)setMin(ans,dp[h-1][w-1][x][y]);
  printf("%lld\n",ans);
  return 0;
}

G - String Fair

小写字母非空字符串S的得分 = n个标准的得分和

第i个标准的得分 = S中字符串Ti作为连续子串 出现的次数 乘上Pi

输出最大的S的得分

如果可以无限大 输出Infinity

范围

n 18278=26*(1+26*(1+26))

1 <= |Ti| <= 3, 两两不等

2s

1024mb

我的思路

其实, 如果能找到一个循环节

(…)(…)

然后每个循环单位的贡献和为正, 则可以无限大

比如 (a,b,z) => 循环单位是 (abz,bza,zab,ab,bz,za,a,b,z)

(a,b) => 循环单位是 (ab,ba,a,b)

从这个角度,似乎比较难推出 至少要多少长度, 才能让”有正循环节”出现

考虑所有长1的里,如果有正贡献, 则用它即可

否则, 所有长1 贡献为0或负

那么如果长2里有正贡献 (ab) 且 (ab+ba+a+b > 0) 则选它

否则, 所有长1, a<=0, 长2的 (ab+ba+a+b<=0)

似乎 也不太行

在就是直接建图

每个3个字符一个节点

(a,b,c) -> (b,c,d) 有一条边其中代价为 d+cd+bcd

其中还有 (空,空,空), (空,空,c),(空,b,c) 这种点

那么问题是从(空,空,空) 出发的最大值

那么问题变成 判断是否有正环, 若没有求最大的

考虑说 值+距离来做??, 大概像spfa那样

感觉上是对的,没有数学证明

代码

https://atcoder.jp/contests/abc264/submissions/35596046

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}

const int N=27; // [0,N)
pair<ll,int> f[N][N][N]; // sum, max visit code in path
const ll INF=0x3f3f3f3f3f3f3f3f;
char t[10];
ll cost[N*N*N+10];
int enc(int a,int b,int c){return c+N*(b+N*a);}
int main(){
  int n=read();
  rep(i,0,n){
    char*s=t+2;
    rep(j,0,2)t[j]=0; // 0 1 2 3 4
    scanf("%s",s);    //     x x x
    int sz=strlen(s);
    rep(j,0,sz)s[j]-='a'-1;
    cost[enc(t[sz-1],t[sz],t[sz+1])]=read();
  }
  rep(i,0,N)rep(j,0,N)rep(k,0,N)f[i][j][k]={-INF,-1};
  ll ans=-INF;
  vector<pair<pair<ll,int>,tuple<int,int,int> > > smabc={{{0,-1},{0,0,0}}};
  rep(i,0,smabc.size()){
    auto [sm,abc]=smabc[i];
    auto [s,m]=sm;
    auto [a,b,c]=abc;
    if(f[a][b][c].first > s)continue;
    if(enc(a,b,c)!=0)ans=max(ans,s); // 非起始点
    if(m==enc(a,b,c)){
      printf("Infinity\n");
      return 0;
    }
    rep(ch,1,N){ // a,b,c -> b,c,ch
      ll nc = s+cost[enc(b,c,ch)]; // newcost
      if(c) nc +=cost[enc(0,0,ch)];
      if(b) nc +=cost[enc(0,c,ch)];
      if(f[b][c][ch].first<nc)smabc.push_back({f[b][c][ch]={nc,max(m,enc(a,b,c))},{b,c,ch}});
    }
  }
  printf("%lld\n",ans);
  return 0;
}

Ex - Perfect Binary Tree

n点根为1的树

对于k=1..n

问 在 [1..k] 中选 含点1 的 点集, 有多少 按照祖先关系导出图 满足 生成的是一个2^d-1节点的 完美满二叉树(节点要么是叶子,要么两个子节点, 所有叶子在最后一层)

就是 导出图就是, 如果u和v都被选了,且原图u,v有边,则新图里也有边

范围

n 3e5

3s

1024mb

我的思路

啊, 就树上dp?

dp[u为根][dep] = {map[最大出现的值] = 方案数}

但似乎这样最大出现的值 会 让状态数很多

随着k增大 从下向上更新

因为pi < i

所以每次 到k时 多出来的所有合法方案,一定是含有k的(其实题目样例1的解释里 有一点这个想法的感觉

所以每次选了k, 让当前位置 方案+1

然后向上算

u时 方案增加t

那么fa(u) 方案增加 t*(count[fa(u)][dep] - count[u][dep-1]) ,再向上, 当为0时退出,

而又注意到要生成的是 完美满二叉树, 所以 不会超过 log(2,3e5) < 20

似乎就可以做了?

代码

https://atcoder.jp/contests/abc264/submissions/35596646

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}

const int PWR=22;

int fa[300010];
mint cnt[300010][PWR]; // cnt[u][从这向下dep] = 方案数
mint sum[300010][PWR]; // u的子一层 cnt之和

mint toroot(int u,int d,mint x){
  if(d==PWR)return 0;
  if(u==1){
    cnt[u][d]+=x;
    return x;
  }
  int v=fa[u]; // v->
  mint inc = x*(sum[v][d+1]-cnt[u][d]); // sum[v][d+1] = sum( cnt[...child][d+1])
  sum[v][d+1]+=x;
  cnt[u][d]  +=x;
  return toroot(v,d+1,inc);
}

int main(){
  int n = read();
  rep(i,2,n+1) fa[i]=read();
  mint ans=0;
  rep(k,1,n+1){
    ans+=toroot(k,0,1);
    printf("%d\n",ans.val());
  }
  return 0;
}

总结

F

没啥难的

G

虽然糊过了, 但总感觉上面有点问题, 这样做判断环 ,会不会多个增在环上跑, 导致 O(并行的bfs指针 * 环长)的复杂度

还是应该搞个maxPQ?

Ex

emmm, 过了个橙题, 虽然我还是觉得G更难点

参考

官方题解