noip模拟5

TLEer

06-07-2021 约 3011 字预计阅读 7 分钟

string，matrix，big，所驼门王的宝藏

T1

~~大暴力啊~~（肯定不是）先说一种40分做法：普通sort

再来一种：用前缀和统计26个字母在每一位上的累计出现次数，然后最后两位两位的减来得出每一位的字母

其实这个思路离正解挺近的

upd:还没改出来，先咕

T2

学长的blog

题干：

求出满足以下条件的 n*m 的 01 矩阵个数：（1）第 i 行第 1~li 列恰好有 1 个 1。 (li+1到ri-1不能放1) （2）第 i 行第 ri~m 列恰好有 1 个 1。（3）每列至多有 1 个 1。

这道题的思路反正我想不到，非常奇特的DP方式，dp数组定义的是表示前i列，前i列中有j列在右侧区间放1的情况，而且已经考虑了r<i的情况为了进行dp，需要分别计算左右两个区间的前缀和（指到有多少个左侧区间已经在i点结束和i向右能放1的区间个数）（这里并不指的是l-r,而是1-l和r-m这两个区间）

转移方程挺简单，无非就是放和不放两种情况

$ dp[i][j] = dp[i-1][j] + dp[i-1][j-1]*(r[i]-j+1) $

加号左边的意思是不放，右边的意思是可以在右侧的任意一个区间内放1

最后，因为左边也可以任意放，所以还要乘上 $ A_{i-j-l[i-1]}^{l[i]-l[i-1]} $

关于dp这块pyt解释的比我清楚

 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


#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010, mod = 998244353;

int qpow(int base, int power) {
  int result = 1;
  while (power > 0) {
    if (power & 1) {
      result = 1ll * result * base % mod;
    }
    power >>= 1;
    base = 1ll * (1ll * base * base) % mod;
  }
  return result;
}

int lp[maxn], rp[maxn], inv[maxn], jc[maxn], dp[maxn][maxn];
int L[maxn], R[maxn];
int n, m;
void jcinv() {
  jc[0] = 1;
  for (int i = 1; i <= m; i++) {
    jc[i] = 1ll * jc[i - 1] * i % mod;
  }
  inv[m] = qpow(jc[m], mod - 2);
  for (int i = m; i >= 1; i--) {
    inv[i - 1] = 1ll * inv[i] * i % mod;
  }
}
int A(int a, int b) {
  if (a < b) return 0;
  return 1ll * jc[a] * inv[a - b] % mod;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    int ll, rr;
    scanf("%d%d", &ll, &rr);
    L[ll]++;
    R[rr]++;
  }
  for (int i = 1; i <= m; i++) {
    L[i] += L[i - 1];
    R[i] += R[i - 1];
  }
  inv[0] = 1;
  jcinv();

  dp[0][0] = 1;
  for (int i = 1; i <= m; i++) {
    dp[i][0] = 1ll * dp[i - 1][0] * A(i - L[i - 1], L[i] - L[i - 1]) % mod; //consider left
    for (int j = 1; j <= min(i, n); j++) {
      dp[i][j] =
          (dp[i - 1][j] + 1ll * dp[i - 1][j - 1] * max(R[i] - j + 1, 0) % mod) * // right
          A(i - j - L[i - 1], L[i] - L[i - 1]) % mod;// L[i] - L[i-1] only one
    }
  }
  cout << dp[m][n] << endl;
  return 0;
}

T3

这道题又是一道很巧妙的题（废话

你需要在 $ [0,2^n) $ 中选一个整数 x，接着把 x 依次异或 m 个整数 a1~am。在你选出 x 后，你的对手需要选择恰好一个时刻（刚选完数时、异或一些数后或是最后），将 x 变为 $(\lfloor \frac{2x}{2^n} \rfloor +2x) \bmod 2^n$ 你想使 x 最后尽量大，而你的对手会使 x 最后尽量小。你需要求出 x 最后的最大值，以及得到最大值的初值数量。

首先，对x进行的操作可以转化为将x循环左移1位，若x=34(100010),则操作完成后x=5(000101),于是这个式子可以简化成这样:(x » (n - 1) & 1) + (x « 1) & ((1 « n) - 1)

然后，你还有个对手，他的目的是尽量让你的答案最小，然而他只有m+1种选择（0 - end），因此可以求每种情况(mod a[1-?] and mod a[?-n])计算后的前缀xor和和后缀xor和并把它们放在trie树中求最大值（见 the XOR largest pair）

like this：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


for (int i = m; i; i--) {
    suf[i] = suf[i + 1] ^ a[i];
  }
add(suf[1]); //一开始
int pref = 0;
  for (int i = 1; i <= m; i++) {
    pref ^= a[i]; // 顺序求就OK
    int mov = (pref >> (n - 1) & 1) + (pref << 1) & ((1 << n) - 1);
    add(mov ^ suf[i + 1]);
  }

因为x的范围为[0，2^n-1]因此不用在意x的具体值是什么，因为每种情况都一定可以取到。这样以来一来就可以理解为x先xor了前缀，然后循环左移了1位，接着又xor了后缀。但x可以取遍所有情况，于是就有了add(mov^suf[i + 1])这句话

建trie树：板子

dfs：有手就行，如果一个节点的儿子既有0又有1，那么这个节点一定没有贡献，因为在这个节点上你的对手可以和你对着干，但若只有0或1，你的对手就无能为力

code:

 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


#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;

int n, tot = 1, m;
int a[maxn], mo[maxn], trie[101][2], suf[maxn];
void add_n(int x) {
  int fa = 1;
  for (int i = n - 1; i >= 0; i--) {
    int ch = x >> i & 1;
    if (trie[fa][ch] == 0) {
      trie[fa][ch] = ++tot;
    }
    fa = trie[fa][ch];
  }
}

int ans = 0, totn;
void dfs(int id, int bit, int num) {
  // cout << bit << endl;
  if (trie[id][1] && trie[id][0]) {  // no contri
    dfs(trie[id][1], bit - 1, num);
    dfs(trie[id][0], bit - 1, num);
  } else {
    if (trie[id][1]) {
      dfs(trie[id][1], bit - 1, num + (1 << (bit - 1)));
    } else {
      if (trie[id][0]) {
        dfs(trie[id][0], bit - 1, num + (1 << (bit - 1)));
      } else {
        if (ans < num) {
          ans = num;
          totn = 1;
        } else {
          if (ans == num) totn++;
        }
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = m; i; i--) {
    suf[i] = suf[i + 1] ^ a[i];
  }
  add_n(suf[1]);
  int pref = 0;
  for (int i = 1; i <= m; i++) {
    pref ^= a[i];
    int mov = (pref >> (n - 1) & 1) + (pref << 1) & ((1 << n) - 1);
    add_n(mov ^ suf[i + 1]);
  }
  dfs(1, n, 0);
  cout << ans << endl << totn << endl;
  return 0;
}

T4

这道题洛咕上有，思路很好想（只要知道可以用tarjan并缩点）但细节很多，挺毒瘤的

同一横行上的横向的门可以构成一个环然后缩点，纵向同理，但对于第三类门最好用map把坐标和id对应起来，然后用8个循环找出来在周围的点（千万不要枚举，否则n*n的复杂度会T），另外，前向星在建新图时可以重复利用

我被后来加的数据hack掉了，so，先放code

upd:把cmp中0放到1上面就A了

?????????????????????????????????????

来自咕咕讨论

先判y的opt比先判x的opt快了一半这个和造的数据有关系，如果对于每一对Ques，前一项经常需要交换的话，那么先判x就会多耗时，那么反过来先判y也就更快。简单来说，造数据的人可能是故意这么做，也可能是数据不够随机。

  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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197


#include <bits/stdc++.h>
using namespace std;
const int maxn = 100001;

inline int read() {
  int ans = 0, f = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -f;
    c = getchar();
  }
  while (isdigit(c)) {
    ans = (ans << 3) + (ans << 1) + (c ^ 48);
    c = getchar();
  }
  return ans * f;
}

int dirx[9] = {0, -1, -1, -1, 0, 0, 1, 1, 1};
int diry[9] = {0, -1, 0, 1, -1, 1, -1, 0, 1};
int n, L, C;
int belong[maxn], numofpoint[maxn];
struct PNT {
  int x, y, type, id;
} fpo[maxn];
struct EDGE {
  int to, next, from;
} edge[maxn];
int head[maxn], tote;
void add_edge(int from, int to) {
  edge[++tote].to = to;
  edge[tote].next = head[from];
  edge[tote].from = from;
  head[from] = tote;
}

bool xcmp(PNT a, PNT b) {
  if (a.x != b.x) {
    return a.x < b.x;
  } else {
    if (a.type == 1) return 1;
    if (b.type == 1) return 0;
    return a.y < b.y;
  }
}
bool ycmp(PNT a, PNT b) {
  if (a.y != b.y) {
    return a.y < b.y;
  } else {
    if (a.type == 2) return 1;
    if (b.type == 2) return 0;
    return a.x < b.x;
  }
}
/*------------ */
int t, top, sum;
int low[maxn], dfn[maxn], stk[maxn];
bool instk[maxn];
void tarjan(int id) {
  t++;
  low[id] = dfn[id] = t;
  stk[++top] = id;
  instk[id] = true;
  for (int i = head[id]; i; i = edge[i].next) {
    int to = edge[i].to;
    if (!dfn[to]) {
      tarjan(to);
      low[id] = min(low[id], low[to]);
    } else {
      if (!belong[to]) {
        low[id] = min(low[id], low[to]);
      }
    }
  }
  if (dfn[id] == low[id]) {
    sum++;
    int k;
    do {
      k = stk[top--];
      instk[k] = false;
      belong[k] = sum;
      numofpoint[sum]++;
    } while (k != id);
  }
}
/*------------ */
int dp[maxn];
void dfs(int id, int fa) {
  if (dp[id] > numofpoint[id]) return;
  dp[id] = numofpoint[id];
  for (int i = head[id]; i; i = edge[i].next) {
    int to = edge[i].to;
    if (edge[i].to == fa) continue;
    dfs(to, id);
    dp[id] = max(dp[id], dp[to] + numofpoint[id]);
  }
}
/*------------ */
map<pair<int, int>, bool> newmap;
map<pair<int, int>, int> postonum;
int ind[maxn];
/*mainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmain*/
/*mainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmain*/
/*mainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmain*/
/*mainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmainmain*/
int main() {
  n = read();
  L = read();
  C = read();
  for (int i = 1; i <= n; i++) {
    int w, d, ll;
    w = read();
    d = read();
    ll = read();
    fpo[i].x = w;
    fpo[i].y = d;
    fpo[i].id = i;
    fpo[i].type = ll;
    postonum[pair<int, int>(fpo[i].x, fpo[i].y)] = i;
  }
  /*----------------------input---------------------- */
  int last = 1, first = 1;
  sort(fpo + 1, fpo + n + 1, xcmp);
  for (int i = 1; i <= n; i++) {
    if (fpo[i].x != fpo[i + 1].x) {
      if (last != first) add_edge(fpo[last].id, fpo[first].id);
      last = i + 1;
      first = i + 1;
    } else {
      if (fpo[last].type == 1) {
        add_edge(fpo[last].id, fpo[i + 1].id);
      }
      if (fpo[i + 1].type == 1) {
        last = i + 1;
      }
      if (fpo[first].type != 1) {
        first = last = i + 1;
      }
    }
  }
  last = first = 1;
  sort(fpo + 1, fpo + n + 1, ycmp);
  for (int i = 1; i <= n; i++) {
    if (fpo[i].y != fpo[i + 1].y) {
      if (last != first) add_edge(fpo[last].id, fpo[first].id);
      last = i + 1;
      first = i + 1;
    } else {
      if (fpo[last].type == 2) {
        add_edge(fpo[last].id, fpo[i + 1].id);
      }
      if (fpo[i + 1].type == 2) {
        last = i + 1;
      }
      if (fpo[first].type != 2) {
        first = last = i + 1;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (fpo[i].type == 3) {
      for (int j = 1; j <= 8; j++) {
        if (postonum.count(
                pair<int, int>(fpo[i].x + dirx[j], fpo[i].y + diry[j])))
          add_edge(
              fpo[i].id,
              postonum[pair<int, int>(fpo[i].x + dirx[j], fpo[i].y + diry[j])]);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (!dfn[i]) tarjan(i);
  }
  /*-------------build---------------- */
  for (int i = 1; i <= tote; i++) {
    if (belong[edge[i].from] != belong[edge[i].to]) {
      newmap[pair<int, int>(belong[edge[i].from], belong[edge[i].to])] = 1;
    }
  }
  memset(head, 0, sizeof(head));
  tote = 0;
  map<pair<int, int>, bool>::iterator it;
  for (it = newmap.begin(); it != newmap.end(); it++) {
    add_edge(it->first.first, it->first.second);
    ind[it->first.second]++;
  }
  int ansss = 0;
  for (int i = 1; i <= sum; i++) {
    if (ind[i] == 0) {
      dfs(i, 0);
      ansss = max(ansss, dp[i]);
    }
  }
  printf("%d\n", ansss);
  return 0;
}

目录

noip模拟5

T1

T2

学长的blog

T3

T4

来自咕咕讨论