8.08集训

Posted on Edited on In

上午

考试

下午

讲图论，改题

第一题

给定一个长度为\(n\)的序列，求这个序列所有长度为\(k\)的子序列的最大值之和，答案对\(1e9+7\)取模

显然，观察题面发现是“子序列”，也就是可以不连续

所以我们首先排序，然后考虑\(a[i]\)对于答案造成的贡献，发现以\(a[i]\)为最大值的序列，\(i-1\)之前的东东他都可以造成贡献，变相的说，是在前\(i-1\)个数里面，选\(k-1\)个，然后这么多次方案，\(a[i]\)对于每个方案都有贡献，

于是答案呼之欲出啊：\(Ans = \sum_\limits {i = k} ^nC_{i-1}^{k-1}\times a[i]\)，可惜在考场上没想出来，一直在想数据结构单调栈之类的去维护他，最后没办法，打了二十分暴力走人

PS:估计只有我不太清楚\(C_n^m = C_{n-1}^{m} + C_{n-1}^{m-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
29
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;

const int N = 1e5+66, mod = 1e9+7;

int n, k;
int a[N];
LL c[N][66], res;

inline int thestars() {
   cin >> n >> k;
   for (int i = 1; i <= n; ++ i) scanf ("%d", &a[i]);
   sort (a + 1, a + n + 1);
   for (int i = 0; i <= n; ++ i) c[i][0] = 1;
   for (int i = 1; i <= n; ++ i) {
      for (int j = 1; j < k; ++ j) {
         c[i][j] = (c[i - 1][j] + c[i - 1][j - 1])%mod;
      }
   }
   for (int i = k; i <= n; ++ i) res = (res + c[i - 1][k - 1]*a[i])%mod;
   cout << res;
   return 0;
}

int youngore = thestars();

signed main() {;}

第二题

题目大意：在一个有\(n\)个站点的路上，对于\(1\leq i < n\)，站点\(i\)可以一票到达站点\(i+1,i+2, i+3......Min(i+a_i, n)\)

求任意两点\(i,j\)从\(i\text~j\)的最少票数和，即求\(\sum_\limits{i=1}^{n-1}\sum_\limits{j=i}^{n} p(i,j)\)其中\(p(i,j)\)表示\(i\text~j\)的最少票数

状态：设\(f[i]\)表示\(\sum_\limits{j = i+1}^np(i,j)\)，即\(i\text~j\)的最少票数和，

转移：

  • 对于\((i,i+a_i\rbrack\)，我们可以一票卖完
  • 对于\((i+a_i,n\rbrack\)，选择一个合适的\(j\)作为跳板，跳到终点，显然选择一个\({j+a[j]}_{max}\)是最合适不过的了
  • 故当\(i+a_i=n\)时，\(f[i] = n-i\)，表示\(i+1 \text~n\)都可以一票走
  • 而当\(i+a_i<n\)时，用树状数组或线段树查询\((i,i+a_i \rbrack\)中，\(j+a_i\)最大的\(j\)
  • 转移呼之欲出：\(f[i] = a_i+f[j]-(a_i -j)+(n-a_i)\)

PS

\(a[i] = min(a[i]+i, n)\)

\(f[i] = a[i] - i\)

结果：\(Ans = \sum_\limits{i=1}^{n-1}f[i]\)

给出AC代码：

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
#include <bits/stdc++.h>
#define lowbit(x) (x&-x)
#define LL long long
#define debug
using namespace std;

const int N = 1e5+66;

int n, a[N], mp[N], t;
LL f[N], res;

inline void chenge(int x) {
   for (int i = x; i <= n; i += lowbit(i)) {
      if (a[mp[i]] < a[x]) {
         mp[i] = x;
      }
   }
}

inline int ask(int x) {
   int yhm(0);
   for (int i = x; i; i -= lowbit(i)) {
      if (a[yhm] < a[mp[i]]) {
         yhm = mp[i];
      }
   }
   return yhm;
}

inline int thestars() {
   scanf ("%d", &n);
   for (int i = 1; i <= n-1; ++ i) {
      scanf ("%d", &a[i]);
      a[i] = min (a[i]+i, n);
   }
   for (int i = n-1; i; -- i) {
      f[i] = a[i] - i;
      if (a[i] < n) t = ask(a[i]), f[i] += f[t] - (a[i] - t) + (n - a[i]);
      chenge(i);
   }
   for (int i = 1; i <= n; ++ i) res += f[i];
   cout << res;
   return 0;
}

int youngore = thestars();

signed main() {;}

第三题

没时间了，贴上题解与代码吧

一句话题意：给定一个\(1\text~n\)的序列，\(m\)次询问，每次询问\(\lfloor l_i, r_i \rfloor\)中选出两个不同的数所得的\(gcd\)的最大值

其中\(1 \leq n,m \leq 1e5\)

给出代码：

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 LL long long
#define debug
using namespace std;

const int N = 1e5+66;

vector<int>lv[N], lp[N];
int n, m, p(1), tot;
int a[N], d[N], f[N];
int pos[N], ans[N];

struct node {
   int l, r, id;
   bool operator<(const node &a) const {return r < a.r;}
}q[N];

inline void add(int x, int val) {
   for (int i = x; i; i -= (i&-i))
      f[i] = max(f[i], val);
}

inline int chaxun(int x) {
   int res(0);
   for (int i = x; i <= n; i += (i&-x)) 
      res = max(res, f[i]);
   return res;
}

inline int thestars() {
   cin >> n >> m;
   for (int i = 1; i <= n; ++ i) {
      cin >> a[i];
      pos[a[i]] = i;
   }
   for (int i = 1; i <= m; ++ i) {
      cin >> q[i].l >> q[i].r;
      q[i].id = i;
   }
   for (int i = 1; i <= n; ++ i) {
      int tot(0);
      for (int j = i; j <= n; j += i) d[++ tot] = pos[j];
      sort(d + 1, d + tot + 1);
      for (int j = 2; j <= tot; ++ j) {
         lp[d[j]].push_back(d[j - 1]);
         lv[d[j]].push_back(i);
      }
   }
   sort(q + 1, q + m + 1);
   for (int i = 1; i <= n; ++ i) {
      for (int j = 0; j < (int)lp[i].size(); ++ j) add(lp[i][j], lv[i][j]);
      while (p <= m && q[p].r <= i) {
         ans[q[p].id] = chaxun(q[p].l);
         ++ p;
      }
   }
   for (int i = 1; i <= m; ++ i) printf("%d\n", ans[i]);
   return 0;
}

int youngore = thestars();

signed main() {;}

晚上

做例题呗.....，还有一道题没有D出来

一个黄题这么操蛋.....

明星牛

click

近乎板子题，缩点之后，找出度为零的点\(x\)，答案就是\(x\)的\(size\)

PS：如果发现出度为零的\(x\)不止一个，那么\(res = 0\)

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

const int N = 1e5+66;

int n, m, res;

struct node {int to, nxt;}e[N]; int head[N], num;
inline void add_edge(int u, int v) {
   ++ num;
   e[num].to = v, e[num].nxt = head[u];
   head[u] = num;
}

vector<int>scc[N];
int tp, tot, cnt;
int dfn[N], low[N], sta[N], in[N], tar[N], d[N];
//tar[i] has showed the i belong which SCC
inline void tarjan (int x) {
   dfn[x] = low[x] = ++ tot; in[x] = 1, sta[++ tp] = x;
   for (int i = head[x]; i; i = e[i].nxt) {
      int y = e[i].to;
      if (!dfn[y]) {
         tarjan(y);
         low[x] = min(low[x], low[y]);
      } else if (in[y]) low[x] = min(low[x], dfn[y]);
   }
   if (dfn[x] == low[x]) {
      int y; ++ cnt;
      do {
         y = sta[tp --]; in[y] = 0;
         tar[y] = cnt;
         scc[cnt].push_back(y);
      } while (x != y);
   }
}

inline int thestars() {
   cin >> n >> m;
   for (int i = 1; i <= m; ++ i) {
      int u, v;
      scanf ("%d%d", &u, &v);
      add_edge(u, v);
   }
   for (int i = 1; i <= n; ++ i) {
      if (!dfn[i]) {
         tarjan(i);
      }
   }
   for (int x = 1; x <= n; ++ x) {
      for (int i = head[x]; i; i = e[i].nxt) {
         int y = e[i].to;
         if (tar[x] == tar[y]) continue;
         else d[tar[x]] = 1;
      }
   }
   for (int i = 1; i <= cnt; ++ i) {
      if (!d[i]) {
         if (res) {res = 0; break;}
         res = scc[i].size();
      }
   }
   cout << res;
   return 0;
}
//the topic aim:find all the T.size(), and the T = ("chudu" == 0)
//how can I do?
int youngore = thestars();

signed main() {;}

佳肴

click

这个题是一个拓扑排序，我们只需要把图倒着连一遍，然后跑一遍最大拓扑排序即可，把序列倒着输出就好了

正常的排序用队列，这里用优先队列

证明：

1 尽量靠前，然后2尽量靠前... 在反图反序列中就相当于1尽量靠后，然后2尽量靠后...这就相当于：能不选1就不选1，然后能不选2就不选2...

等价于：选最大的，然后再选接下来的最大的...

PS：需要特判两个地方，第一个是是否有入度为零的点，第二个是拓扑排序完成之后，判断点的个数是否等于\(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 <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;

const int N = 1e5+66;

int T, n, m, num, tp, flag;
int a[N], z[N];
int deg[N];

struct edge{int to, nxt;}e[N]; int head[N], cnt;

inline void add_edge(int u, int v) {
   ++ cnt;
   e[cnt].to = v, e[cnt].nxt = head[u];
   head[u] = cnt; ++ deg[v];
}

inline void topsort() {
   priority_queue<int>q;
   for (int i = 1; i <= n; ++ i) {
      if (!deg[i]) {
         q.push(i);
      }
   }
   while (q.size()) {
      flag = 1;
      int x = q.top(); q.pop();
      z[++ num] = x;
      for (int i = head[x]; i; i = e[i].nxt) {
         int y = e[i].to;
         if (-- deg[y] == 0) {
            q.push(y);
         }
      }
   }
}

inline int thestars() {
   cin >> T;
   while (T --) {
      flag = 0, num = 0, tp = 0, cnt = 0;
      memset(a, 0, sizeof a); 
      memset(z, 0, sizeof z);
      memset(head, 0, sizeof head);
      memset(deg, 0, sizeof deg);
      scanf ("%d%d", &n, &m);
      for (int i = 1; i <= m; ++ i) {
         int x, y;
         scanf ("%d%d", &x, &y);
         add_edge(y, x);
      }
      topsort();
      if (num == n) {
         for (int i = 1; i <= num; ++ i) a[num-i+1] = z[i];
         for (int i = 1; i <= num; ++ i) cout << a[i] << ' ';
         puts("");
      } else puts("Impossible!");
   }
   return 0;
}

int youngore = thestars();

signed main() {;}