第七場比賽 題解
=
>啦啦啦啦啦
>
>嚕嚕嚕嚕嚕
>
>嘟嘟嘟嘟嘟
>
>野野野野野

# [z061](https://judge.cp.ccns.io/problem/z061)：
這題出自 [Codeforces Prefix Sum Primes](https://codeforces.com/contest/1150/problem/C)

詳細的討論在一開始的累計到達 $2, 3, 5 ...$ 的方式

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

int n, one, two;

int main() {
  cin >> n;
  one = two = 0;

  int tmp;
  for(int i = 0; i < n; i++) {
    cin >> tmp;
    if(tmp == 1) one++;
    else two++;
  }
  if(two >= 1 && one >= 1) {
    cout << 2 << " " << 1;
    for(int i = 0; i < two-1; i++) cout << " " << 2;
    for(int i = 0; i < one-1; i++) cout << " " << 1;
  }
  else if(one >= 1) {
    if(one >= 3) {
      for(int i = 0; i < 3; i++) cout << (i == 0? "": " ") << 1;
      for(int i = 0; i < two; i++) cout << " " << 2;
      for(int i = 0; i < one-3; i++) cout << " " << 1;
    }
    else {
      cout << 1;
      for(int i = 0; i < two; i++) cout << " " << 2;
      for(int i = 0; i < one-1; i++) cout << " " << 1;
    }
  }
  else {
    for(int i = 0; i < two; i++) cout << (i==0?"": " ") << 2;
  }

  cout << endl;
  return 0;
}

# [z062](https://judge.cp.ccns.io/problem/z062)：
因為可以隨便亂排，為了保證一定可以達到題目中的要求，先對其中一項排序，再對另一項做 LIS，另外，由於 $n$ 較大，本題僅能使用 $nlgn$ 的 LIS

#include <bits/stdc++.h>
using namespace std;
struct node {
  int wei;
  int money;
};
bool cmp(node& a, node& b) {
  if (a.wei == b.wei) {
    return a.money < b.money;
  }
  return a.wei < b.wei;
}
bool cmp2(node a, node b) { return a.money > b.money; }
int main() {
  int n, m, i, j, k;
  vector<node> v;
  n = 0;
  int a, b;
  while (cin >> a >> b) {
    v.push_back({a, b});
    n++;
  }
  sort(v.begin(), v.end(), cmp);

  vector<node> LIS;
  LIS.push_back(v[0]);
  for (i = 1; i < n; i++) {
    if (v[i].money < LIS.back().money && v[i].wei > LIS.back().wei) {
      LIS.push_back(v[i]);
    } else {
      *lower_bound(LIS.begin(), LIS.end(), v[i], cmp2) = v[i];
    }
  }

  cout << LIS.size() << endl;

  return 0;
}

# [z063](https://judge.cp.ccns.io/problem/z063)：
這題出自 [UVa OJ 11770 Lighting Away](https://uva.onlinejudge.org/external/117/11770.pdf)
利用 SCC 當找出每組 SCC 時，判斷對於這個 SCC 是不是只有出沒有進。

team14, team6, team21, team11, team5 被 team22 hack成功！
🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣🤣

#include <bits/stdc++.h>
#define vi vector<int>
#define pb push_back
using namespace std;

vector< vi > edge, invedge;
vi dfn, low;

stack<int> s;
vector<bool> instack;

int T, n, m, idx_dfn, ans;

void init() {
  idx_dfn = 1, ans = 0;
  edge.clear(); invedge.clear(); dfn.clear(); low.clear(); instack.clear();
  edge.resize(n+1); invedge.resize(n+1); dfn.assign(n+1, -1); low.resize(n+1); instack.resize(n+1);
  while(s.size()) s.pop();
}

void dfs(int u) {
  dfn[u] = low[u] = idx_dfn++;

  s.push(u);
  instack[u] = 1;

  for(int v: edge[u]) {
    if(dfn[v] == -1) {
      dfs(v);
      low[u] = min(low[u], low[v]);
    }
    else if(instack[v]) low[u] = min(low[u], dfn[v]);
  }



  if(dfn[u] == low[u]) {
    queue<int> group;
    set<int> who_in;
    int tmp;

    do {
      tmp = s.top(); s.pop();
      instack[tmp] = 0;
      group.push(tmp);
      for(int v: invedge[tmp]) who_in.insert(v);
    }while(tmp != u);

    while(group.size()) {
      auto it = who_in.find(group.front());
      if(it != who_in.end()) who_in.erase(it);
      group.pop();
    }
    if(who_in.size() == 0) ans++; //nobody come in this group
  }
}


int main() {
  cin >> n >> m;
  init();
  for(int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    edge[u].pb(v);
    invedge[v].pb(u);
  }
  for(int i = 1; i <= n; i++) if(dfn[i] == -1) dfs(i);

  cout << ans << endl;
  return 0;
}

# [z064](https://judge.cp.ccns.io/problem/z064)：
題目要求輸出有**多少種不同**的贈品，而 sakura 擁有一些贈品，這個關係能構成下圖：

digraph {
rankdir="LR"
sakura -> 1 [label=p_1]
1 -> output [label=1]
sakura -> 2 [label=p_2]
2 -> output [label=1]
sakura -> ":" -> output [style=invis]
":" [shape=plaintext]
sakura -> m [label=p_m]
m -> output [label=1]
}

若同學(student) 擁有 $x$ 個 $a$ 贈品，沒有 $b$ 贈品
根據交換規則 ：
- 他最多可**換出** $x-1$ 件 $a$
- 他至多可**換入** $1$ 件 $b$

所以有關係圖：

digraph {
rankdir="LR"
student -> a [label="x-1"]
student -> b [label=1, dir=back]
}

也就是說，題目就是要求從 sakura 加入流，找出 output 的最大流量

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

int const maxn = 60;
int const INF = maxn*50;

int n, m, R[maxn][maxn];

int main()
{
  scanf("%d%d", &n, &m);
  
  for(int i = 1; i <= n; i++) {
    int t, p;
    scanf("%d", &t);
    while(t--) scanf("%d", &p), R[i][n+p]++;
  }
  
  int out = n + m + 1; // out := output
  for(int p = 1; p <= m; p++) R[n+p][out] = 1;

  // 同學們與贈品的關係圖
  for(int i = 2; i <= n; i++)
    for(int p = 1; p <= m; p++) {
      if(R[i][n+p] == 0) R[n+p][i] = 1;
      else R[i][n+p]--;
    }


  // 找出最大流量
  int s = 1, pre[maxn], flow[maxn], max_flow = 0; // s := sakura
  bool vis[maxn];

  while(1) {
    memset(vis, false, sizeof(vis));
    vis[s] = true;

    memset(flow, 0, sizeof(flow));
    flow[s] = INF;

    queue<int> Q;
    Q.push(s);

    while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      if(u == out) break;

      for(int v = s; v <= out; v++) {
        if(vis[v] || !R[u][v]) continue;

        vis[v] = true;
        flow[v] = min(flow[u], R[u][v]);
        pre[v] = u;
        Q.push(v);
      }
    }

    if(flow[out] == 0) break;
    max_flow += flow[out];

    for(int v = out; v != s; v=pre[v]) {
      int u = pre[v];

      R[u][v] -= flow[out];
      R[v][u] += flow[out];
    }
  }

  printf("%d\n", max_flow);


  return 0;
}

這裡 sakura 與同學們的編號為 $1, 2, ... n$
而每種贈品編號為 $n+1, n+2, ..., n+m$
output 的編號為 $n+m+1$

# [z065](https://judge.cp.ccns.io/problem/z065)：
這題出自 [UVa OJ 10731 Test](https://uva.onlinejudge.org/external/107/10731.pdf)
做一下 SCC 就過了
我不知道怎麼寫題解@~@

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

bool first = 0, instack[maxN];
int n, num, idx, k, t, dfn[maxN], low[maxN];
map<string, int> id;
string x, y[5], name[maxN], temp[maxN];
vector<int> g[maxN];
stack<int> s;
set<string> ans;

void dfs(int u)
{
  dfn[u] = low[u] = idx++;
  s.push(u);
  instack[u] = 1;
    
  for(int v : g[u])
    if(dfn[v] == -1) {
      dfs(v);
      low[u] = min(low[u], low[v]);
    }
    else if(instack[v])
      low[u] = min(low[u], dfn[v]);
	
  if(dfn[u] == low[u]) {
    k = 0;
    do {
      t = s.top();
      s.pop();
      temp[k++] = name[t];
      instack[t] = 0;
    }while(t != u);
    sort(temp, temp + k);
    for(int i = 1; i < k; i++)
      temp[0] += (" " + temp[i]);
    ans.insert(temp[0]);
  }
}

int main()
{
  while(cin >> n && n) {
    num = 0;
    idx = 0;
    id.clear();
    ans.clear();
    for(int i = 0; i < maxN; i++) {
      g[i].clear();
      dfn[i] = low[i] = -1;
      instack[i] = 0;
    }
    while(s.size())
      s.pop();
    	
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < 5; j++) {
        cin >> y[j];
        if(id.find(y[j]) == id.end()) {
          name[num] = y[j];
          id[y[j]] = num++;
        }
      }
      cin >> x;
      for(int j = 0; j < 5; j++)
        if(y[j] != x)
          g[id[x]].push_back(id[y[j]]);
    }
		
    for(int i = 0; i < num; i++)
      if(dfn[i] == -1)
        dfs(i);
		
    if(first)
      cout << '\n';
    first = 1;
    for(string i : ans)
      cout << i << '\n';
  }
  return 0;
}