nowcoder 牛客挑战赛60,CD+总结(竞赛图, 递推)

發表於 更新於 分類於 Disqus： 文章字數： 1k 所需閱讀時間 ≈ 3 分鐘

比赛总结

比赛id 11200

B:

数组空间没开够等未定义行为,不会像Codeforces报overflow等,而是默认执行报WA.

D:

TLE+WA 只会报WA

竞赛图不能创造大小为2的scc

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
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
/**
 * @author      : cromarmot (yexiaorain@gmail.com)
 * @file        : D
 * @created     : 星期五 5月 13, 2022 20:35:36 CST
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)

// 竞赛图 任意不同两点间都有恰好一条单向边
int n,m; // n 1e5, m 2e5
vector<int>p2[100010];

// scc -> 成链?

class Tarjan{
  vector<int> low;
  vector<int> dfn;
  stack<int> stk;
  vector<int> res;
  int n;
  int id = 0;
  void scc(int v) {
    low[v] = dfn[v] = ++id;
    stk.push(v);
    for(auto w:p2[v]){
      if(!dfn[w]){ // 未访问过
        scc(w);
        low[v] = min(low[v],low[w]);
      } else if(!res[w]){ // 访问过但没有结果(在栈中)
        low[v] = min(low[v],dfn[w]);
      }
    }
    int u;
    if(low[v] == dfn[v])  {
      do{
        res[u = stk.top()] = v;
        stk.pop();
      }while(u != v);
    }
  }
public:
  Tarjan(int SZ):n(SZ){
    low = vector<int>(n+1,0);
    dfn = vector<int>(n+1,0);
    stk = {};
    res = vector<int> (n+1,0);
  }
  vector<int> calc(){
    rep(i,1,n+1){
      if(!res[i]){
        scc(i);
      }
    }
    return res;
  }
};

vector<int> p3[100010];
int du[100010];

void work(){
  scanf("%d %d",&n,&m);
  Tarjan tarjan(n);
  rep(i,1,n+1){
    p2[i] = {};
    p3[i] = {};
    du[i] = 0;
  }
  rep(i,0,m){
    int u,v;
    scanf("%d %d",&u,&v);
    p2[u].push_back(v);
  }
  // a->b / b->a 至少满足一条
  // scc 成链? 唯一拓扑顺序
  vector<int> num = tarjan.calc(); // scc 联通分量 标识
  vector<int> sccsz(n+1,0);
  rep(i,1,n+1){
    sccsz[num[i]]   ++;
  }
  rep(i,1,n+1){
    if(sccsz[i] == 2){
      // 竞赛图不能创造大小为2的scc!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
      printf("NO\n");
      return ;
    }
  }

  // rep(i,1,n+1){
  //   printf("scc: %lld: %d\n",i,num[i]);
  // }
  // 转化为联通分量关系
  rep(i,1,n+1){
    for(auto item:p2[i]){
      if(num[i] == num[item])continue;
      p3[num[i]].push_back(num[item]);
    }
  }
  rep(i,1,n+1){
    if(num[i] != i)continue;
    sort(p3[i].begin(),p3[i].end());
    int itr = 0;
    rep(j,0,(int)p3[i].size()){
      if(j==0 || p3[i][j] != p3[i][j-1]){ // 去重
        p3[i][itr++] = p3[i][j];
        // i -> p3[i][j]
        du[p3[i][j]]++; // 入度
      }
    }
    p3[i].resize(itr);
  }
  // 拓扑 联通分量中 唯一顺序
  // 入度为0
  vector<int> d0;
  rep(i,1,n+1){
    if(num[i] != i)continue;
    if(du[i] == 0)d0.push_back(i);
  }
  while(d0.size()) { // == 1
    if(d0.size() > 1){
      printf("NO\n");
      return ;
    }
    int i = d0[0];
    // printf("D0:%d\n",i);
    d0.pop_back();
    rep(j,0,(int)p3[i].size()){
      // i -> p3[i][j]
      du[p3[i][j]]--;
      if(du[p3[i][j]] == 0){
        d0.push_back(p3[i][j]);
        if(d0.size() > 1){
            printf("NO\n");
            return ;
        }
      }
    }
  }
  printf("YES\n");
}


int main(){
  int t;
  scanf("%d",&t);
  while(t--){
    work();
  }
  return 0;
}

C题目

https://ac.nowcoder.com/acm/contest/11200/C

大意

从1开始

  1. 每次可以移动 x = x+1
  2. 如果当前格子未被染色, 则染色当前格子并且设置 x = a[x]

a[x]保证非严格单调递增

n<=1e6

输出把所有格子都染色的方案数

题解

设 f(x)把前x个格子全部染色的方案数, 注意到虽然顺序上可能 在染前x个格子过程中,已经把后面的格子染色了,但是后面这个被染色的不计入方案统计

  • x 如果是最后一个被染色的,那么方案数为f(x-1)
  • x 如果不是最后一个被染色的, 那么对于f(x-1)中, 相当于 ? -> x -> y, $y \in [a_x,x-1]$, 所以它可以放在$x-a_x$个位置的前面

所以方案数 = $\prod_{i=1}^n(i-a_i+1)$

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
const double pi = acos(-1.0);

int n;
int a[1000010];

int main(){
  ll ans = 1;
  cin>>n;
  rep(i,1,n+1){
    scanf("%d",a+i);
    if(i-a[i]+1 <= 0){
      ans = 0;
    }else{
      (ans*=i-a[i]+1)%=MOD;
    }
  }
  printf("%lld\n",ans);
  return 0;
}

总结

状态转移的过程中, 对于上面这种,实际上也可以和方案描述不一致, 统计的时候不会包含超过当前位置的移动方案,而后面的移动方案是可以等价的插入到前面的方案中的(才可以乘法)

不过现在好的是,我能判断这个类型算是数学和转移的题了,也想到这样设计状态,但是没有细想

参考

https://ac.nowcoder.com/discuss/952589