noip模拟79

 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

#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 2010;
const int mod = 998244353;

#define int int64_t

template <typename NBXIN>
NBXIN read() {
  NBXIN s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

struct EDGE {
  int to, nxt;
} edge[maxn];
int tote, head[maxn];
void addEdge(int u, int v) {
  edge[++tote] = (EDGE){v, head[u]};
  head[u] = tote;
}
int n;
bitset<maxn> bts[maxn];

bool inq[maxn];
void bfs() {
  queue<int> que;
  for (int i = 1; i <= n; i++) {
    que.push(i);
    inq[i] = true;
  }
  while (que.size()) {
    int fnt = que.front();
    que.pop();
    for (int i = head[fnt]; i; i = edge[i].nxt) {
      int to = edge[i].to;
      if ((bts[to] & bts[fnt]) == bts[fnt]) continue;
      bts[to] |= bts[fnt];
      if (!inq[to]) que.push(to);
      inq[to] = true;
    }
    inq[fnt] = false;
  }
}

int qpow(int x, int y) {
  int ans = 1;
  while (y) {
    if (y & 1) ans = 1ll * ans * x % mod;
    x = 1ll * x * x % mod;
    y >>= 1;
  }
  return ans;
}

int32_t main() {
  freopen("f.in", "r", stdin);
  freopen("f.out", "w", stdout);
  n = read<int>();
  string in;
  For(i, 1, n) {
    cin >> in;
    bts[i].set(i);
    For(j, 1, n) {
      if (in[j - 1] == '1') bts[j].set(i), addEdge(i, j);
    }
  }
  bfs();
  int ans = 0;
  For(i, 1, n) { ans = (ans + qpow(bts[i].count(), mod - 2)) % mod; }
  cout << ans << endl;
  return 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

#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 8010;

template <typename NBXIN>
NBXIN read() {
  NBXIN s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

int stt[maxn];
char s[maxn], t[maxn];
int kmp[maxn];
int trans[maxn][26];

int dp[maxn][maxn];
int main() {
  freopen("s.in", "r", stdin);
  freopen("s.out", "w", stdout);
  memset(kmp, 0, sizeof(kmp));
  cin >> s + 1 >> t + 1;
  int tl = strlen(t + 1);
  int sl = strlen(s + 1);
  // cout << tl << ' ' << sl << endl;
  for (int i = 2, j = 0; i <= tl; i++) {
    while (j && t[j + 1] != t[i]) j = kmp[j];
    if (t[j + 1] == t[i]) j++;
    kmp[i] = j;
  }
  trans[0][t[1] - 'a'] = 1;
  For(i, 1, tl) {
    For(j, 0, 25) {
      trans[i][j] = ((t[i + 1] - 'a') == j) ? i + 1 : trans[kmp[i]][j];
    }
  }
  Set(dp, 0x3f);
  dp[0][0] = 0;
  For(i, 0, sl) {
    For(j, 0, tl - 1) {
      dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
      if (i < sl)
        dp[i + 1][trans[j][s[i + 1] - 'a']] =
            min(dp[i + 1][trans[j][s[i + 1] - 'a']], dp[i][j]);
    }
  }
  int ans = 0x3f3f3f3f;
  For(i, 0, tl - 1) ans = min(ans, dp[sl][i]);
  cout << ans << endl;
  return 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
 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

#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 35;

int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

template <typename NBXIN>
NBXIN read() {
  NBXIN s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}

int n, m, q;

int mat[maxn][maxn], dis[maxn][maxn][maxn][maxn][4];
int hash_tbl[maxn][maxn][4];
int vis[maxn][maxn], tmp[maxn][maxn];

int ex, ey, sx, sy, tx, ty;

int getH(int x, int y) { return abs(x - tx) + abs(y - ty); }
struct NODE {
  int x, y, d, G, H;
  bool operator<(const NODE a) const { return G + H > a.G + a.x; }
};
priority_queue<NODE> pq;  // open list

void bfs(int sx, int sy, int tx, int ty) {
  Set(tmp, 0);
  Set(vis, 0);
  queue<int> qx, qy;
  qx.push(sx), qy.push(sy);
  vis[sx][sy] = 1;
  For(i, 0, 3) dis[sx][sy][tx][ty][i] = -1;
  while (!qx.empty()) {
    int nx, ny;
    int x = qx.front(), y = qy.front();
    qx.pop(), qy.pop();
    For(i, 0, 3) {
      if (x - dir[i][0] == tx && y - dir[i][1] == ty)
        dis[sx][sy][tx][ty][i] = tmp[x][y];
      nx = x + dir[i][0], ny = y + dir[i][1];
      if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
      if (vis[nx][ny] || !mat[nx][ny] || (nx == tx && ny == ty)) continue;
      tmp[nx][ny] = tmp[x][y] + 1;
      qx.push(nx), qy.push(ny);
      vis[nx][ny] = 1;
    }
  }
}

int main() {
  freopen("y.in", "r", stdin);
  freopen("y.out", "w", stdout);
  n = read<int>();
  m = read<int>();
  q = read<int>();
  For(i, 1, n) {
    For(j, 1, m) { mat[i][j] = read<int>(); }
  }
  For(i, 1, n) {
    For(j, 1, m) {
      if (mat[i][j] == 1) {
        For(k, 0, 3) {
          if (mat[i + dir[k][0]][j + dir[k][1]] == 1) {
            bfs(i + dir[k][0], j + dir[k][1], i, j);
          }
        }
      }
    }
  }
  while (q--) {
    ex = read<int>();
    ey = read<int>();
    sx = read<int>();
    sy = read<int>();
    tx = read<int>();
    ty = read<int>();
    bfs(ex, ey, sx, sy);
    Set(hash_tbl, 0x3f);
    while (!pq.empty()) pq.pop();
    if (sx == tx && sy == ty) {
      printf("%d\n", 0);
      continue;
    }
    For(i, 0, 3) {
      if (dis[ex][ey][sx][sy][i] != -1) {
        NODE nxt = (NODE){sx, sy, i, dis[ex][ey][sx][sy][i], getH(sx, sy)};
        pq.push(nxt);
        // cout << ex << ' ' << ey << ' ' << sx << ' ' << sy << ' '
        //      << dis[ex][ey][sx][sy][i] << endl;
        hash_tbl[nxt.x][nxt.y][nxt.d] = dis[ex][ey][sx][sy][i];
      }
    }
    /*-------------------------------A*Start---------------------------------*/
    while (!pq.empty()) {
      NODE cur = pq.top();
      pq.pop();
      if (cur.x == tx && cur.y == ty) {
        printf("%d\n", cur.G);
        goto haveAns;
      }
      int eh = cur.x + dir[cur.d][0], ew = cur.y + dir[cur.d][1];

      For(i, 0, 3) {
        if (dis[eh][ew][cur.x][cur.y][i] == -1) continue;
        NODE nxt = (NODE){cur.x, cur.y, i, cur.G + dis[eh][ew][cur.x][cur.y][i],
                          cur.x};
        if (hash_tbl[nxt.x][nxt.y][nxt.d] >
            cur.G + dis[eh][ew][cur.x][cur.y][i])
          pq.push(nxt), hash_tbl[nxt.x][nxt.y][nxt.d] =
                            cur.G + dis[eh][ew][cur.x][cur.y][i];
      }
      NODE nxt = (NODE){eh, ew, cur.d ^ 1, cur.G + 1, getH(eh, ew)};
      if (hash_tbl[nxt.x][nxt.y][nxt.d] > cur.G + 1) {
        pq.push(nxt);
        hash_tbl[nxt.x][nxt.y][nxt.d] = cur.G + 1;
      }
    }
    puts("-1");
  haveAns:
    continue;
  }
  return 0;
}