题解【WdOI-Codeforces Round 1】

囧仙 · 2021-10-19 19:05:31 · 个人记录

A

考虑到最优构造方案一定是把所有括号序列尽可能的构造成 ()，考虑贪心，对于每一个左括号，寻找到它后面未被匹配的第一个右括号，进行匹配即可。

在整个串都匹配完成后，如果得到的 () 串组数 \ge m，则说明有合法的构造方案，否则说明没有。

至于时间复杂度，如果你是对于每个左括号，暴力寻找它右边的第一个没匹配的右括号，则复杂度为 O(Tn^2)。当然，你也可以使用一个 queue 来将复杂度优化为 O(Tn)，但是介于此题的数据范围，没有优化的必要。

char s[100005];
int n, m, T;

signed main() {
  in(T);
  while(T--) {
    queue<int> q;
    in(n)(m)(s + 1);
    re (i, n)
      if (s[i] == ')') q.push(i);
    int ans = 0;
    re (i, n)
      if (s[i] == '(') {
        while (q.size() && q.front() < i) q.pop();
        if (q.size()) ++ans, q.pop();
      }
    out(ans >= m ? "1\n" : "0\n");
  }
  return 0;
}

B1

对于 easy version，有一个显然的结论：最优方案一定能使 A 队每一局都赢。

对于前 n 个人，通过修改 a 数组使得 A 队全胜，这样可以保证对于 a 数组的修改至多为 n 次；
对于后 n 个人，通过修改 b 数组使得 A 队全胜，这样可以保证对于 b 数组的修改至多为 n 次。

int a[N], b[N], n, T;
signed main() {
  in(T); while(T--){
    in(n)(a, 2 * n)(b, 2 * n);
    out(2 * n)('\n');
    re (i, n)
      out((b[i] - 2 + 3) % 3 + 1)(' ');
    rep (i, n + 1, 2 * n)
      out(a[i])(' ');
    out('\n');
    re (i, n)
      out(b[i])(' ');
    rep (i, n + 1, 2 * n)
      out(a[i] % 3 + 1)(' ');
    out('\n');
  }
  return 0;
}

B2

我们先把石头剪刀布所对应的编号全部减一以方便处理。

我们把每一对人偶分到两个集合中。其中 S_a 为需要修改才能使 A 获胜的下标组成的集合，S_b 为不用修改就能使 A 获胜的下标组成的集合，则：

\begin{aligned} S_a &= \{i \in \Z \mid i \in [1,2n], a_i \equiv b_i+2 \pmod 3 \}\\ S_b &= ([1,2n] \cap \Z) - S_a \end{aligned}

可以看出，\forall i\in S_a，我们可以选择改两个数组，也可以不改；\forall i \in S_b，我们可以选择改一个数组或者改两个数组。

我们先把改一个数组的给改了，假设 |S_a|=k 显然有 k\le 2n。

若 k 为偶数，我们分两半分别改其中的 a 或者 b，剩下每队各自需要改 n-\dfrac{k}{2} 个，我们直接选出这么多对暴力做就好；
否则，其中一组我们改两个数组。

int a[maxn << 1], b[maxn << 1];
int sa[maxn << 1], sb[maxn << 1], ta, tb, n;
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    ta = tb = 0;
    scanf("%d", &n);
    for (int i = 1; i <= 2 * n; ++i)
      scanf("%d", a + i), --a[i];
    for (int i = 1; i <= 2 * n; ++i)
      scanf("%d", b + i), --b[i];
    for (int i = 1; i <= 2 * n; ++i)
      switch ((a[i] + 3 - b[i]) % 3) {
      case 2:
        //可以赢
        sb[++tb] = i;
        break;
      default:
        //不行
        sa[++ta] = i;
        break;
      }
    for (int i = 1; i <= ta; ++i) {
      if (i == ta && (ta & 1)) {
        //改两次别忘了
        if (a[sa[i]] == b[sa[i]]) {
          //平局
          a[sa[i]] = (a[sa[i]] + 1) % 3;
          b[sa[i]] = (b[sa[i]] + 2) % 3;
        } else {
          swap(a[sa[i]], b[sa[i]]);
        }
      } else { //改一个
        if (a[sa[i]] == b[sa[i]]) {
          //奇数
          if (i & 1) {
            //改A
            a[sa[i]] = (a[sa[i]] + 2) % 3;
          } else {
            b[sa[i]] = (b[sa[i]] + 1) % 3;
          }
        } else {
          //奇数
          if (i & 1) {
            //改A
            a[sa[i]] = (b[sa[i]] + 2) % 3;
          } else {
            b[sa[i]] = (a[sa[i]] + 1) % 3;
          }
        }
      }
    }
    int sd = (ta >> 1) + (ta & 1); //目前为止每队总共改了几次
    sd = n - sd;                   //还要改几次
    for (int i = 1; i <= sd; ++i) {
      a[sb[i]] = (a[sb[i]] + 1) % 3;
      b[sb[i]] = (b[sb[i]] + 1) % 3;
    }
    printf("%d\n", 2 * n);
    for (int i = 1; i <= 2 * n; ++i)
      printf("%d%c", a[i] + 1, " \n"[i == 2 * n]);
    for (int i = 1; i <= 2 * n; ++i)
      printf("%d%c", b[i] + 1, " \n"[i == 2 * n]);
  }
}

C

首先考虑什么样的表达式是一个结果一定为 0，什么样的一定为 1，什么样的既可以为 0 也可以为 1。

如果运算符为 ?，则如果左操作数和右操作数确定且相同，则结果一定为左操作数。否则结果可以是 0 或 1。
如果运算符为 &，且左右操作数中至少有一个确定为 0，则结果一定为 0。否则如果两个操作数均确定，则结果为两操作数按位与的结果。否则结果可以是 0 或 1。
如果运算符为 |，且左右操作数中至少有一个确定为 1，则结果一定为 1。否则如果两个操作数均确定，则结果为两操作数按位或的结果。否则结果可以是 0 或 1。

我们可以先建立出表达式树，从叶子节点到根节点依次转移即可。

（由萌萌蓝补充）更简单的方法是贪心，容易发现把所有 ? 换成 | 结果最有可能是 0，都换成 & 结果最有可能是 1。直接建出表达式树然后进行两次 dfs 即可。

char s[N], typ[N];
int n, ls[N], rs[N], tp, ans[N];

inline int And(int x, int y) { return (x == 0 || y == 0) ? 0 : max(x, y); }
inline int Or(int x, int y) { return (x == 1 || y == 1) ? 1 : max(x, y); }

int Dfs(int x) {
  if (x <= 0) return -x;
  int l = Dfs(ls[x]), r = Dfs(rs[x]);
  if (typ[x] == '&') return ans[x] = And(l, r);
  if (typ[x] == '|') return ans[x] = Or(l, r);
  return ans[x] = ((And(l, r) == Or(l, r)) ? And(l, r) : 2);
}

signed main() {
  int T;in(T);while(T--) {
    vector<int> vec;
    in(n)(s + 1);
    re (i, n) {
      if (s[i] == '0' || s[i] == '1')
        vec.push_back(-(s[i] - '0'));
      else
        typ[++tp] = s[i], ls[tp] = vec.back(), vec.pop_back(), rs[tp] = vec.back(), vec.back() = tp;
    }
    Dfs(tp);
    int res = 0;
    re (i, tp)
      if (ans[i] == 2) ++res;
    out(res)('\n');
    rep (i, 0, n + 1)
      s[i] = 0, typ[i] = 0, ls[i] = 0, rs[i] = 0, ans[i] = 0;
    tp = 0, n = 0;
  }
  return 0;
}

D1

考虑将贡献分为两种——字符串内部的贡献和拼接处产生的贡献。第一种贡献直接暴力求即可，重点是第二种。考虑一个有长度为 i 的连续极大后缀的字符串和一个长度为 j 的极大连续前缀的字符串相拼接。会对答案造成 i+j-k+1 的贡献。我们可以预处理出有极大前缀为字符 c，长度为 i 的字符串数量 \operatorname{pre}(c,i)，极大后缀为字符 c，长度为 j 的字符串数量 \operatorname{suf}(c,j)。枚举 c,i,j，从两个集合各选出一个字符串拼接在一起的方案数为 \operatorname{suf}(c,j)\operatorname{pre}(c,i)。考虑将「所有的全排列中 k 连串数量的总和」转化为「随机洗牌后 k 连串数量的期望」。从 n 个位置中选择两个位置共有 \operatorname{C}_n^2 = n(n-1) 种方案。而这 n(n-1) 种方案中只有 (n-1) 种使得两个字符串正好相邻。也就是说，随机洗牌后这两个字符串正好相邻形成 k 连串的概率为 \dfrac{n-1}{n(n-1)}=\dfrac 1 n。所以对答案的贡献为：

\dfrac{\operatorname{suf}(c,j)\operatorname{pre}(c,i)(i+j-k+1)} n.

但是这会忽略一种特殊情况，试想有这样一组数据：

-1
2 3 2
aba
cde

正确答案显然为 0，但是根据上面那种方式得到的答案为 1，原因是因为字符串 aba 的前后缀有相同的字符，计算答案时会「自己和自己拼接」而造成贡献，我们可以记录多少个字符串有着极大前后缀字符均为 c 的，前缀长度为 i，后缀长度为 j 的字符串数量 \operatorname{same}(c,i,j)，计算答案时减去即可。故最终答案为：

\sum_{c=\verb!a!}^{\verb!z!}\sum_{i=1}^{m-1}\sum_{j=1}^{m-1}\dfrac{(\operatorname{suf}(c,i)\operatorname{pre}(c,i)-\operatorname{same}(c,i,j))(i+j-k+1)} n.

D2

考虑将贡献分五种情况：

单个串内部；
纯由相同字母组成的串拼接；
一段后缀 + 几个相同字母组成的串；
几个相同字母组成的串 + 一段前缀；
一段后缀 + 几个相同字母组成的串 + 一段前缀。

分别考虑这些情况，计算答案即可。公式的推导与 easy version 类似，这里不再重复。

设 G(i,j,k) 为后缀长度 =i，相同字母的串的个数 =j，前缀长度 =k 对答案造成的贡献。需要注意的是，统计答案的时候可能会重复统计答案，比如当 m=3,k=5 时。G(2,1,1)=1 而不是 2，因为 (2,1,1) 的情况包括 (2,1,0) 的情况，会重复计算一遍贡献。具体来说，在计算 G(x,y,z) 时，要减掉 G(x,1\cdots y,0)、G(0,1\cdots y,z)、G(0,1\cdots y,0) 的贡献。贡献的计算可以通过一个简单 DP 求出，也可以分情况直接 O(1) 判断。

int Gx(int i, int ed, int st) {
  if (ed == 0 && st == 0) {
    int res = m + k - (i - 1) * m - 1;
    if (res > m) res = i * m - k + 1;
    if (res < 0) res = 0;
    return res;
  }
  if (ed == 0 || st == 0) {
    int j = ed | st;
    int res = j + k - 1 - (i - 1) * m - j;
    if (res > m) res = i * m + j - k + 1;
    if (res > j) res = j;
    if (res < 0) res = 0;
    return res;
  }
  int mn = min(st, ed), mx = max(st, ed);
  int res = mn + k - 1 - i * m - mn;
  if (res > mx) res = i * m + mn + mx - k + 1;
  if (res > mn) res = mn;
  if (res < 0) res = 0;
  return res;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> k;
  jc[0] = jcinv[0] = 1;
  re (i, n)
    jc[i] = 1ll * jc[i - 1] * i % mo, jcinv[i] = Inv(jc[i]);
  re (i, n) {
    string s;
    cin >> s;
    int f = s[0], b = s.back();
    int l = s.find_first_not_of(f), r = m - s.find_last_not_of(b) - 1;
    f -= 'a', b -= 'a';
    if (l < 0)
      l = n, ++all[f];
    else {
      ++pre[f][l], ++suf[b][r];
      if (f == b) ++same[f][l][r];
    }
    int len = 1;
    rep (i, l, m - r - 1) {
      if (s[i] == s[i - 1])
        ++len;
      else
        len = 1;
      if (len >= k) ++ans;
    }
  }
  rep (c, 0, 25) {
    pre[c][0] = suf[c][0] = 1;
    rep (mid, 0, all[c]) {
      rep (ed, 0, m - 1) {
        rep (st, 0, m - 1) {
          int qw = Gx(mid, ed, st);
          if (qw <= 0) continue;
          int glx = (1ll * suf[c][ed] * pre[c][st] - same[c][st][ed] + mo) % mo * A(all[c], mid) %
                    mo * (n - mid + 1 - bool(st) - bool(ed)) % mo,
              gly = A(n, mid + bool(st) + bool(ed));
          ans += 1ll * qw * glx % mo * Inv(gly) % mo, umod(ans);
        }
      }
    }
  }
  cout << 1ll * ans * jc[n] % mo << '\n';
}

E

考虑只有 2 个关键点的情况。

我们只要构造出一个经过图上所有点的简单环，然后从环上的任意一个点出发，从两个方向沿着环分别去搜索，搜到两个关键点之后，已经询问过的点就构成了环上的一部分，也就是一条路径了。

现在有 4 个关键点。由于题目已经帮我们将关键点分为两组，所以我们只需要构造两个不相交且大致覆盖全图（中间的那条路径不用覆盖）的环就行了。

构造方法如图，绿色与蓝为辅助线，红色为构造的环。

构造城墙式的环，沿着中间的路径将左右两边分开来（如图中的绿线），使得每个齿的长度都是偶数，且第 2k 行与 2k-1 行（如图中的蓝色线之间的两行）的齿长度相同即可。

#include<bits/stdc++.h>
using namespace std;
class point{
    public: 
    int x,y;
    void u(){y--;}
    void d(){y++;}
    void l(){x--;}
    void r(){x++;}
    bool q(){printf("? %d %d\n",x,y);fflush(stdout);int p;scanf("%d",&p);return p;}
    void print(){printf("%d %d\n",x,y);}
};
deque<point> s,s2;
int h1,h2;
int n,m,mp[303][303];
int r[303];
void gets1(){
    point p;
    p.x=1,p.y=m;
    s.push_back(p);
    while(1){
        while(p.x!=r[p.y-1]){p.r();s.push_back(p);}
        p.u();
        s.push_back(p);
        while(p.x!=2){p.l();s.push_back(p);}
        if(p.y==h1) {p.l();s.push_back(p);while(p.y!=m-1){p.d();s.push_back(p);}break;}
        p.u();
        s.push_back(p);
    }
}
void solve1(){
    int ans1;
    for(int i=0;i<s.size();i++){
        if(s[i].q()) {ans1=i;break;}
    }
    for(int i=s.size()-1;i!=-1;i--){
        if(s[i].q()) {for(int j=ans1;j!=-1;j--)s[j].print();for(int j=s.size()-1;j>=i;j--) s[j].print();puts("-1 -1");fflush(stdout);return;}
    }
}
void gets2(){
    point p;
    p.x=n,p.y=h2;
    s2.push_back(p);
    while(1){
        while(p.x-1!=r[p.y-1]){p.l();s2.push_back(p);}
        p.u();
        s2.push_back(p);
        while(p.x!=n-1){p.r();s2.push_back(p);}
        if(p.y==1) {p.r();s2.push_back(p);while(p.y!=h2-1){p.d();s2.push_back(p);}break;} 
        p.u();
        s2.push_back(p);
    }
}
void solve2(){
    int ans1;
    for(int i=0;i<s2.size();i++){
        if(s2[i].q()) {ans1=i;break;}
    }
    for(int i=s2.size()-1;i!=-1;i--){
        if(s2[i].q()) {for(int j=ans1;j!=-1;j--)s2[j].print();for(int j=s2.size()-1;j>=i;j--) s2[j].print();puts("-1 -1");fflush(stdout);return;}
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) if(i&1) r[i]=1003;
    for(int i=1;i<n+m;i++) {int x,y;scanf("%d%d",&x,&y);mp[x][y]=1;if(y%2==0)r[y-1]=min(r[y-1],x);}
    for(int i=1;i<=m;i++) if(i&1) if(r[i]%2) r[i]--;
    h1=1;
    while(r[h1]==0) h1+=2;
    h2=m;
    while(r[h2-1]==n) h2-=2;
    gets1();
    solve1();
    gets2();
    solve2();
}

F1，F2

该问题可以转化为：有一个 4 行 n 列的矩阵，琪露诺选取了 2\cdot n 个点（假设染为黑色），每次按照题目中的流程进行，如果琪露诺和大妖精选的两个点在同行同列大妖精即得分。

定义「H(x)」为有 x 个黑格的列。

显然，一个 H(x) 可以和一个 H(4-x) 抵消。特别的，一个 H(2) 可以自己把自己消掉。

如果我们先按上述方式把能消的列都消了，那么我们会发现只会剩下 H(4) 和 H(1)（或 H(3) 和 H(0)，可以根据对称性不失一般性的只考虑其中一种），而且 H(1) 是 H(4) 数量的 2 倍。设此时 H(4) 数量为 d。

那么我们考虑先在一开始把多余的 H(4) 消掉。现在我们定义「位置为 x 的列」为唯一一个黑格在第 x 行的 H(1)。删掉多余的 H(4) 有三种方法：

第一种拿两个位置不同的 H(1) 删掉一个 H(4)。这时，当且仅当某一位置的 H(1) 超过一半时才可能删不完。可以列方程解决。具体解决方法可以把四种位置的列的数量排序后作为四个参数（设为 w,x,y,z），把每一组（如位置为 1 的列和位置为 2 的列）可能的删法的数量当作未知数（设为 a 到 f），然后解不等式。或者钦定其中两个为 0 也行。

这么消完以后，会发现只剩下 1 种位置的 H(1) 了。设此时只剩位置为 0 的 H(1)。

第二种是拿一个第 0 行为白格的 H(3) 去消。

第三种是拿一个第 0 行为白格的 H(2) 和另一个位置为 0 的 H(1) 去消。

如果还有剩下的 H(4)，只好摆烂，每个 H(4) 都得剩下一个格子不能得分。

按照上述顺序模拟过程即可。记得将多余的 H(4) 删完了之后把剩下的全匹配掉。

为什么这样最优呢？因为第 0 行的白格全部被匹配掉了。而且如果 H(1) 全部能被消完，显然能把所有多余的 H(4) 消掉。

#include <bits/stdc++.h>
#define tn (2 * n)
using namespace std;
const int N = 2e6 + 7;
int f[N][4];
int a[2 * N], cnt[N], n, ans[2 * N], anss[4 * N], siz[5], mp[4 * N], tmp, dif;
int p[5][N];
bool used[N];
int v[4][N], sizz[4];
bool chg = false;
#define re register
inline int read()
{
    re int x=0,f=1;re char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
int*GP(){static int x[]{0,1,2,3};sort(x,x+4,[](int x,int y){return sizz[x] > sizz[y];});return x;}
void out(){
    for(int p0, p4, i = 0; i < siz[0]; i++){
        p0 = p[0][i], p4 = p[4][i];
        for(int j = 0; j < 4; j++) f[p0][j] = f[p4][j] + tn;
    }
    int po = 0;
    for(int p1, p3, i = 0; i < siz[1]; i++){
        p1 = p[1][i], p3 = p[3][po];
        if(used[p1]) continue;
        while(used[p3]) po++, p3 = p[3][po];
        int v1 = 0, v2 = -1, v3 = 0, v4 = 0;
        bool flag = false;
        for(int j = 0; j < 4; j++) if(f[p1][j] && !f[p3][j]) flag = true, v1 = j;
        if(!flag){
            for(int j = 0; j < 4; j++){
                if(f[p1][j]) v1 = j;
                else if(!f[p3][j]) v4 = j;
                else v2 != -1 ? v3 = j : v2 = j;
            }
        }
        if(flag){
            for(int j = 0; j < 4; j++){
                if(v1 == j) f[p3][j] = f[p1][j] + tn;
                else f[p1][j] = f[p3][j] + tn;
            }
        }else{
            f[p1][v4] = f[p1][v1] + tn;
            f[p3][v4] = f[p3][v1] + tn;
            f[p1][v2] = f[p3][v2] + tn;
            f[p1][v3] = f[p3][v3] + tn;
        }
        po++;
    }
    for(int p2, i = 0; i < siz[2]; i++){
        p2 = p[2][i];
        if(used[p2]) continue;
        int v1 = -1, v2, v3 = -1, v4;
        for(int j = 0; j < 4; j++){
            if(f[p2][j]) v1 != -1 ? v2 = j : v1 = j;
            else v3 != -1 ? v4 = j : v3 = j;
        }
        f[p2][v3] = f[p2][v1] + tn;
        f[p2][v4] = f[p2][v2] + tn;
    }
    printf("%d\n", tn - dif);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 4; j++){
            if(f[i][j] > tn && chg) anss[mp[i + j * n]] = f[i][j] - tn - 1;
            if(f[i][j] <= tn && chg) ans[f[i][j] - 1] = i + j * n;
            if(f[i][j] > tn && !chg) ans[f[i][j] - tn - 1] = i + j * n;
        }
    }
    for(int i = 0; i < tn; i++) printf("%d ", chg ? ans[anss[i]] : ans[i]);
    exit(0);
}
int main(){
    n = read();
    for(int i = 0; i < tn; i++) a[i] = read(), f[a[i] % n][a[i] / n] = i + 1, cnt[a[i] % n]++, mp[a[i]] = i;
    for(int i = 0; i < n; i++) p[cnt[i]][siz[cnt[i]]] = i, siz[cnt[i]]++;
    if(siz[1] < siz[3]){
        chg = true;
        swap(siz[0], siz[4]);
        swap(siz[1], siz[3]);
        swap(p[0], p[4]);
        swap(p[1], p[3]);
        tmp = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 4; j++){
                if(f[i][j]) f[i][j] = 0;
                else f[i][j] = ++tmp;
            }
        }
    }
    for(int i = 0; i < siz[1]; i++){
        for(int j = 0; j < 4; j++){
            if(f[p[1][i]][j]){
                v[j][sizz[j]++] = p[1][i];
            }
        }
    }
    dif = siz[4] - siz[0];
    while(dif){
        int p4 = p[4][siz[4] - 1], v1 = GP()[0], v2 = GP()[1], v3 = -1, v4;
        if(!sizz[v2]) break;
        int p11 = v[v1][sizz[v1] - 1], p12 = v[v2][sizz[v2] - 1];
        for(int i = 0; i < 4; i++){
            if(i != v1 && i != v2) v3 != -1 ? v4 = i : v3 = i;
        }
        f[p12][v1] = f[p4][v1] + tn;
        f[p11][v2] = f[p4][v2] + tn;
        f[p12][v3] = f[p4][v3] + tn;
        f[p11][v4] = f[p4][v4] + tn;
        f[p11][v3] = f[p11][v1] + tn;
        f[p12][v4] = f[p12][v2] + tn;
        used[p4] = true, used[p11] = true, used[p12] = true;
        dif--, siz[4]--, sizz[v1]--, sizz[v2]--;
    }
    if(!dif) out();
    int v1 = GP()[0];
    for(int i = 0; i < siz[2]; i++){
        int p2 = p[2][i];
        if(f[p2][v1]) continue;
        int p11 = v[v1][sizz[v1] - 1], p12 = v[v1][sizz[v1] - 2], p4 = p[4][siz[4] - 1];
        int v2 = -1, v3 = 0, v4;
        for(int j = 0; j < 4; j++){
            if(!f[p2][j] && j != v1) v4 = j;
            else if(j != v1) (v2 != -1 ? v3 = j : v2 = j);
        }
        f[p2][v1] = f[p4][v1] + tn;
        f[p2][v4] = f[p4][v4] + tn;
        f[p11][v4] = f[p11][v1] + tn;
        f[p12][v4] = f[p12][v1] + tn;
        f[p11][v2] = f[p4][v2] + tn;
        f[p11][v3] = f[p4][v3] + tn;
        f[p12][v2] = f[p2][v2] + tn;
        f[p12][v3] = f[p2][v3] + tn;
        used[p4] = true, used[p2] = true, used[p11] = true, used[p12] = true;
        dif--, siz[4]--, sizz[v1] -= 2;
        if(!dif) out();
    }
    for(int i = 0; i < siz[3]; i++){
        if(sizz[v1] == 2) break;
        int p3 = p[3][i];
        if(f[p3][v1]) continue;
        int p11 = v[v1][sizz[v1] - 1], p12 = v[v1][sizz[v1] - 2], p13 = v[v1][sizz[v1] - 3], p4 = p[4][siz[4] - 1];
        int v2 = -1, v3 = -1, v4 = 0;
        for(int j = 0; j < 4; j++) if(j != v1) v2 != -1 ? (v3 != -1 ? v4 = j : v3 = j) : v2 = j;
        f[p3][v1] = f[p4][v1] + tn;
        f[p11][v2] = f[p11][v1] + tn;
        f[p12][v3] = f[p12][v1] + tn;
        f[p13][v4] = f[p13][v1] + tn;
        f[p12][v2] = f[p4][v2] + tn;
        f[p13][v2] = f[p3][v2] + tn;
        f[p11][v3] = f[p4][v3] + tn;
        f[p13][v3] = f[p3][v3] + tn;
        f[p11][v4] = f[p4][v4] + tn;
        f[p12][v4] = f[p3][v4] + tn;
        used[p4] = true, used[p3] = true, used[p11] = true, used[p12] = true, used[p13] = true;
        dif--, siz[4]--, sizz[v1] -= 3;
        if(!dif) out();
    }
    for(int i = 0; i < dif; i++){
        int p11 = v[v1][sizz[v1] - 1], p12 = v[v1][sizz[v1] - 2], p4 = p[4][siz[4] - 1];
        int v2 = -1, v3 = -1, v4 = 0;
        for(int j = 0; j < 4; j++) if(j != v1) v2 != -1 ? (v3 != -1 ? v4 = j : v3 = j) : v2 = j;
        f[p12][v4] = f[p4][v1] + tn;
        f[p11][v2] = f[p11][v1] + tn;
        f[p12][v3] = f[p12][v1] + tn;
        f[p12][v2] = f[p4][v2] + tn;
        f[p11][v3] = f[p4][v3] + tn;
        f[p11][v4] = f[p4][v4] + tn;
        used[p4] = true, used[p11] = true, used[p12] = true;
        siz[4]--, sizz[v1] -= 2;
    }
    out();
    return 0;
}

题解 【WdOI-Codeforces Round 1】

A

B1

B2

C

D1

D2

E

F1，F2

题解【WdOI-Codeforces Round 1】