---
tags: DDJRC
---

# DDJ Regular Contest Round#7 Solution

[toc]

## [a618 A. 水題](http://203.64.191.163/ShowProblem?problemid=a617)

可以用set或者hash_table儲存有沒有寫過題目，再扣掉即可。
有個小陷阱是因為題目問說還要幾題，所以如果超過25%的話，要輸出0。

solution

unorder_map<string> mp;
int n;
string s;
cin >> n;
n = (n + 3) >> 2;
while(cin >> s){
  if(s == "0") break;
  mp[s] = 1;
  int tmp = mp.size();
  cout << (tmp > t ? n - t : 0) << '\n';
}

## [a634 B. 水有病毒題](http://203.64.191.163/ShowProblem?problemid=a634)

基本LCS做DP 8 次。(很噁心)

#include<bits/stdc++.h>
using namespace std;
string s[7];
int n;
int dp[10][10][10][10][10][10][10];
int in[7];
bool compare(){
  for(int i = 1; i < n; ++i)
    if(s[i - 1][in[i - 1] - 1] != s[i][in[i] - 1]) return false;
  return true;
}
int main(){
  cin >> n;
  for(int i = 0; i < n; ++i) cin >> s[i];
  memset(dp, 0, sizeof(dp));
  int size[7] = {0};
  for(int i = 0; i < n; ++i) size[i] = s[i].size();
  for(in[0] = 1; in[0] <= size[0]; ++in[0])
    for(in[1] = 1; in[1] <= size[1]; ++in[1])
      for(in[2] = (n >= 3); in[2] <= size[2]; ++in[2])
        for(in[3] = (n >= 4); in[3] <= size[3]; ++in[3])
          for(in[4] = (n >= 5); in[4] <= size[4]; ++in[4])
            for(in[5] = (n >= 6); in[5] <= size[5]; ++in[5])
              for(in[6] = (n >= 7); in[6] <= size[6]; ++in[6])
                if(compare()) dp[in[0]][in[1]][in[2]]
                                [in[3]][in[4]][in[5]][in[6]] = 
                              dp[in[0] - 1][in[1] - 1][in[2] - (in[2] > 0)]
                                [in[3] - (in[3] > 0)][in[4] - (in[4] > 0)]
                                [in[5] - (in[5] > 0)][in[6] - (in[6] > 0)] + 1;
                else{
                  dp[in[0]][in[1]][in[2]][in[3]][in[4]][in[5]][in[6]] =
                  max({
                    dp[in[0] - 1][in[1]][in[2]][in[3]][in[4]][in[5]][in[6]],
                    dp[in[0]][in[1] - 1][in[2]][in[3]][in[4]][in[5]][in[6]],
                    dp[in[0]][in[1]][in[2] - (in[2] > 0)][in[3]][in[4]][in[5]][in[6]],
                    dp[in[0]][in[1]][in[2]][in[3] - (in[3] > 0)][in[4]][in[5]][in[6]],
                    dp[in[0]][in[1]][in[2]][in[3]][in[4] - (in[4] > 0)][in[5]][in[6]],
                    dp[in[0]][in[1]][in[2]][in[3]][in[4]][in[5] - (in[5] > 0)][in[6]],
                    dp[in[0]][in[1]][in[2]][in[3]][in[4]][in[5]][in[6] - (in[6] > 0)],
                  });
                }
  cout << dp[size[0]][size[1]][size[2]][size[3]][size[4]][size[5]][size[6]] << '\n';
}

所以可以直接暴力搜尋就好。
(Code Author: benson0402)

vector<string> vec;
string chk;
bool dfs(int cur, int mx) {
  if(cur == mx) {
    for(auto& x : vec) {
      int i = 0;
      for(auto& c : x) if(i < mx && c == chk[i])
        ++i;
      if(i != mx) return false;
    }
    return true;
  }
  bool ret = 0;
  chk.push_back('A');
  ret = ret | dfs(cur + 1, mx);
  chk.pop_back();
  chk.push_back('T');
  ret = ret | dfs(cur + 1, mx);
  chk.pop_back();
  chk.push_back('C');
  ret = ret | dfs(cur + 1, mx);
  chk.pop_back();
  chk.push_back('G');
  ret = ret | dfs(cur + 1, mx);
  chk.pop_back();
  return ret;
}

int main(){
  ...
  for(int i = 0; i < n; ++i){
    if(dfs(0, i)){
      cout << i;
      return;
    }
  }
}

## [a638. C. 水還剩多少題](http://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a638)

整個流程基本上是：周圍跟底下先檔住，從上面灌水進去直到滿為止，再把底下打開讓水流掉。
並且也要考慮水流掉的時候會卡在凹槽，所以最後水的位置可能不會相連。

先利用dfs從上面開始搜尋，並計算出所有相連的空間有多少，這是第一步算出水能多滿。
接著從底面開始dfs往上搜尋，但這次的方向只會有上、前、後、左、右，不會往下搜尋，這樣可以算出會流掉多少水。
滿水 - 流走的水 = 最後剩餘的水

寫code的時候為了方便，把盒子上方跟下方再各加一層空間，就可以不用處理很多洞的情況(洞都都相連了)

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

int maze[110][110][110];
int dir[6][3] = {
  {-1, 0, 0}, //上
  {0, 1, 0},
  {0, -1, 0},
  {0, 0, 1},
  {0, 0, -1},
  {1, 0, 0} //下
};

int dfs(int x, int y, int z, int tar, int turn, int dirsel){
  int sum = 0;
  if(maze[x][y][z] == tar){
    sum++;
  }
  maze[x][y][z] = turn;

  for(int i = 0; i < dirsel; ++i){
    int dx = x+dir[i][0], dy = y+dir[i][1], dz = z+dir[i][2];
    if(maze[dx][dy][dz] == tar) sum += dfs(dx, dy, dz, tar, turn, dirsel);
  }
  return sum;
}

int main(){
  int n, m, s;
  while(cin >> n >> m >> s){
    memset(maze, 0, sizeof(maze));
    for(int i = 1; i <= m; ++i){
      for(int j = 1; j <= s; ++j){
        maze[1][i][j] = 1;
        maze[n+2][i][j] = 1;
      }
    }
    for(int i = 2; i <= n+1; ++i){
      for(int j = 1; j <= m; ++j){
        for(int k = 1; k <= s; ++k){
          cin >> maze[i][j][k];
        }
      }
    }
    int ans = dfs(1, 1, 1, 1, 2, 6);
    ans -= dfs(n+2, 1, 1, 2, 1, 5);
    ans -= dfs(1, 1, 1, 2, 1, 5); //上層新增的空間可能沒有流掉，dfs一次確保能處理掉
    cout << ans << '\n';
  }
}

## [a617 D. 青蛙喝水題](http://203.64.191.163/ShowProblem?problemid=a617)

BIT

時間複雜度：O(nm + qlog(n)log(m))

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

const ll MOD = 27644437;
#define mod MOD
#define lowbit(x) (x&(-x))
const int N = 5005;
ll bit[N][N], pre[N][N], arr[N][N];
void init() {
  for(int i = 1; i < N; ++i)
    for(int j = 1; j < N; ++j)
      pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + arr[i][j];
  for(int i = 1; i < N; ++i)
    for(int j = 1; j < N; ++j)
      bit[i][j] = pre[i][j] - pre[i - lowbit(i)][j] - pre[i][j - lowbit(j)] + pre[i - lowbit(i)][j - lowbit(j)];
}
void update(int x, int y, ll v){
  while(x < N){
    int ty = y;
    while(ty < N){
      bit[x][ty] = (v + bit[x][ty]) % MOD;
      ty += lowbit(ty);
    }
    x += lowbit(x);
  }
}

ll query(int x, int y){
  ll ret = 0;
  while(x){
    int ty = y;
    while(ty){
      ret = (bit[x][ty] + ret) % MOD;
      ty -= lowbit(ty);
    }
    x -= lowbit(x);
  }
  return ret;
}


int main() {
  int n, m, q; 
  cin >> n >> m >> q;
  memset(arr, 0, sizeof(arr));
  memset(bit, 0, sizeof(bit));
  memset(pre, 0, sizeof(pre));
  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= m; ++j)
      cin >> arr[i][j];
  init();
  while(q--){
    int x, y;
    ll ans;
    cin >> x >> y;
    ++x, ++y;
    ans =  (query(n, m) + query(x, y)
         - query(x, m) - query(n, y)) % mod;
    if(ans <= 0) ans += MOD;
    cout << ans % MOD << '\n';
    update(x, y, ans);
    ans = (ans + arr[x][y]) % MOD;
    arr[x][y] = ans;
  }
  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= m; ++j)
      cout << arr[i][j] << " \n"[j == m];
}

## [a635. E. 水很重要題](http://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=a635)

整個水路圖是一個tree，由於需要找到調查地點往上數k次的地點，是一個kth ancestor的問題，用爆搜的話O(n^2)最糟情況會TLE，利用jump pointer algorithm(前處理跟查詢都是O(Nlgn))，得到每次查詢的目標，統計每個點出現幾次，再找出哪些點出現最多次。

AC程式碼：

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

int jump[100005][105];

int main(){
  int n, q;
  int cnt[100005];
  cin >> n;
  memset(jump, 0, sizeof(jump));
  memset(cnt, 0, sizeof(cnt));
  for(int i = 0; i < n; ++i){
    int a, b;
    cin >> a >> b;
    jump[a][0] = b;
    if(a == b) jump[a][0] = 0;
  }
  for(int i = 1; i < __lg(n)+1; ++i){
    for(int j = 1; j <= n; ++j){
      jump[j][i] = jump[jump[j][i-1]][i-1];
    }
  }

  cin >> q;
  for(int i = 0; i < q; ++i){
    int a, k, bi = 0, ans;
    cin >> a >> k;
    ans = a;
    if(ans > n) ans = 0;
    while(k > 0){
      if(k & 1){
        if(ans == 0) break;
        ans = jump[ans][bi];
      }
      k >>= 1;
      bi++;
    }
    if(ans){
      cnt[ans]++;
      //cout << ans << ',';
    }
    //else cout << "No ans\n";
  }

  int maxn = 0;
  for(int i = 1; i <= n; ++i){
    maxn = max(maxn, cnt[i]);
  }
  for(int i = 1; i <= n; ++i){
    if(maxn == cnt[i]) cout << i << ' ';
  }
}