2017山东省赛总结

发表于 2017-05-10 分类于 Summaries and pictures Disqus：

热身赛

上机后发现pc^2不会用，问了老师才会的。

老师：你们出来比赛连这个都不会。
吉吉：我们是第一次出来比赛的。
老师：原来这样啊，那还算正常。

然后发现鼠标不太好用，跟志愿者说了，志愿者表示大家都不好用，就这样吧。热身赛题目不难，随便写写就过了。写完之后又去帮女生队测了测机器。然后开始逛校园买纪念品，等大家出来一起回宾馆。等的时候还碰到一个老师跟我们搭讪。

老师：今天题目难不难啊？我都看不懂。
吉吉：好难啊，我们费了好半天劲才做出来。
老师：明天题目也挺难的，加油拿个金牌。
我们：吼～

正式赛

一进场先配好IDE，然后电脑死机了，重启之后又死机了，跟志愿者说了，然后叫来了技术人员，跟我们说这个电脑确实卡，不要着急，我们顺道提了一句鼠标不好，然后就获得了一个新鼠标。

题目发的比较早，赶快读题，吉吉说F是水题，伟铸说G水给我说了题意，我写完之后直接交了一发，忘记用long long了WA了。改好之后又错了一发，我感觉可能题面把1e9+7写错了。改了之后过了，后来rejudge了，G2y（1）。

吉吉写了一发F，也WA了。我写I，I1y（13）。伟铸又告诉我J不难，我也感觉好写，就让他去看别的题，我一会写J。

吉吉改了改F交了一发又WA了。我来帮吉吉一块想F，我交了一发，结果也WA了。后来我们意识到0 0 0是个坑，加了个特判过了，F4y（19）。

然后我去写J，吉吉去读别的题，伟铸感觉K是个背包，过了十几分钟，我写好了，J1y（36）。吉吉给我讲了C的题意，然后去帮伟铸看K题，伟铸说K不是个普通的背包，跟顺序有关。

C题感觉跟之前做过的题挺像的，很快就推出来了式子，然后找了个组合数的模版，敲了一遍，居然不对，改了改又交一发，居然又不对。感觉思路和代码都没什么毛病。我把他俩都拉过来帮我看代码，后来才发现，组合数用除法，在取模时候的除法得用逆元做。太久不做题这个都忘了。改掉之后就对啦，C3y（55）还是个FB。

看旁边的队伍出了A，我感觉A也有希望，是个博弈，就去想A了，吉吉跟伟铸去做K。

A题我连着交错了好多次，中途还拉吉吉帮我推推算算，经历了漫长的卡题，最后一份提交的代码我俩都觉得好有道理可是还不对，于是我们暂时放弃了这道题。

我感觉D题也可以做，也是道组合数，也做过类似的，我去推了推公式就推出来了。写完之后交了一发，错了。查了一会我发现式子应该有两项结果那两项都很长，写了一项我就以为写完了，样例居然还过了。加上之后D2y（155）。

我们三个一起看K题，感觉似乎不是很简单，我又去看了看A题打印的代码，发现有个范围写错了，改过来居然就对了。A5y（159）。

K题我们一起推了一会，后来伟铸又想到了另一种排序方式，改了交了一发，然后就过了K3y（201）。

还剩三道题，伟铸看B、吉吉看E、我看H。H是个最大团一类的题，但是得改改，板子没带，而且时间也不多了，就没去写。E是个数学，但是样例算不出来，我后来跟吉吉一块读了读，感觉没读错题，但还是算不出来样例。B伟铸说题意有一点不是很明确，写个暴力试试，看看这题到底什么意思。过了会伟铸敲出来了，一眼就看出了规律，写了一发就过了B1y（264）。

关于夺冠

平时谈笑风生经常提到夺冠，没想到最后真实现了。

感觉省赛前几名的实力都相差不大，主要还是看发挥。

我们三个人原本想水个金牌，得知有17块金牌，感觉怎么打都有金，心态完全不紧张。在场上的时候经常谈笑风生，即使是在开场错好多次的时候，也没有之前比赛的紧张感。交题也比较随意，有几次编译通过就提交，过了四五道题的之后才刷榜发现登顶了，才意识到机会夺冠。

这次比赛的运气也很好，没卡数学题，我前不久刚好复习了概率论的组合计数，然后就来了两个组合数的题，而且还似曾相识，公式推的很快，中途虽然错了好几次，但找错都没浪费太多时间。

另外，在我跟吉吉谈笑风生的时候，伟铸搞掉B题也是6的不行；似乎旺仔毒奶真的有用。

UVaLive 7634 - Game of XOR

发表于 2017-04-03 分类于 UVaLive Disqus：

链接

传送门

题意

给出一个01串长度为\(s(1 \leq s \leq 100000)\)，进行\(g(1 \leq g \leq 10000)\)次分裂（貌似是这个意思，队友读的题），再给出起点、终点和两点在分裂时移动的方向，输出起点到终点的闭区间内0和1的个数。

思路

当前数字分裂生成的数字与后继数字有关，有：

\(00 \rightarrow 000\)
\(01 \rightarrow 011\)
\(10 \rightarrow 110\)
\(11 \rightarrow 101\)

因此可以DP求出每个点位分裂\(i(0 \leq i \leq g)\)次后生成的0和1的个数，剩下的就是模拟了。

有一个trick是\(g=1\)时，两个路径为空串。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int mod = 342307123;
const int maxn = 100010;
const int maxg = 10010;
const int a[5] = {0, 1, 3, 2};
const int b[5] = {0, 3, 2, 1};

char s[maxn], t1[maxg], t2[maxg];
LL cnt[5];
int dp[5][maxg];

inline int getVal(int x) {
  if (s[x + 1] == 0) {
    return (s[x] - '0') << 1;
  }
  return ((s[x] - '0') << 1) + s[x + 1] - '0';
}

LL pow_mod(LL x, int k) {
  LL res = 1, cur = x;
  while (k) {
    if (k & 1)  {
      res = (res * cur) % mod;
    }
    cur = (cur * cur) % mod;
    k >>= 1;
  }
  return res;
}

int main() {
  dp[1][0] = 0, dp[2][0] = 1, dp[3][0] = 1;
  for (int i = 1; i < maxg; ++i) {
    for (int j = 1; j < 4; ++j) {
      dp[j][i] = (dp[a[j]][i - 1] + dp[b[j]][i - 1]) % mod;
    }
  }
  int t, tt = 0;
  scanf("%d", &t);
  while (t--) {
    int g, p1, p2;
    scanf("%s%d", s, &g);
    --g;
    if (g == 0) {
      scanf("%d%d", &p1, &p2);
    } else {
      scanf("%d%s%d%s", &p1, t1, &p2, t2);
    }
    memset(cnt, 0, sizeof cnt);
    for (int i = p1; i < p2; ++i) {
      ++cnt[getVal(i)];
    }
    LL ans = 0;
    for (int i = 0; i < 4; ++i) {
      ans = (ans + cnt[i] * dp[i][g]) % mod;
    }
    int st1 = getVal(p1), st2 = getVal(p2);
    LL sum = (pow_mod(2, g) * (p2 - p1) + 1)% mod;
    for (int i = 0; i < g; ++i) {
      if (t1[i] == 'R') {
        ans = (ans - dp[a[st1]][g - i - 1] + mod) % mod;
        sum = (sum - pow_mod(2, g - i - 1) + mod) % mod;
        st1 = b[st1];
      } else {
        st1 = a[st1];
      }
      if (t2[i] == 'R') {
        ans = (ans + dp[a[st2]][g - i - 1]) % mod;
        sum = (sum + pow_mod(2, g - i - 1)) % mod;
        st2 = b[st2];
      } else {
        st2 = a[st2];
      }
    }
    ans += a[st2] >> 1;
    printf("Case %d: %d %d\n", ++tt, int((sum - ans + mod) % mod), int(ans));
  }
  return 0;
}

Codeforces 748E - Santa Claus and Tangerines

发表于 2017-03-01 分类于 Codeforces Disqus：

链接

传送门

题意

有\(n\)个橘子，分给\(k\)个人。每次可以选择一个橘子块进行均分，如果橘子的大小为奇数则其中一块比另一块大1。橘子块可以有剩余，问最后\(k\)个人中分得橘子的最小值的最大值是多少。

思路

练习赛做的题，一个很显然的贪心是每次都均分最大的橘子块，最后取最大的\(k\)块。一开始用map离散化了一下，然后类似双指针那样进行处理，超时了。后来用二分+DP卡常数过了。

赛后看了题解恍然大悟，根本不用离散化，1e7的数据量直接存下来然后双指针扫一遍就行了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = 10000010;

LL a[maxn];

int main() {
  int n, k;
  LL sum = 0;
  scanf("%d%d", &n, &k);
  for (int i = 0, x; i < n; ++i) {
    scanf("%d", &x);
    sum += x;
    ++a[x];
  }
  if (sum < k) {
    puts("-1");
    return 0;
  }
  sum = n;
  int p1 = 0, p2 = maxn - 1;
  while (sum < k) {
    sum += a[p2];
    a[p2 / 2] += a[p2];
    a[(p2 + 1) / 2] += a[p2];
    --p2;
  }
  while (sum - a[p1] >= k) {
    sum -= a[p1];
    ++p1;
  }
  while (p1 < p2 / 2) {
    sum += a[p2];
    a[p2 / 2] += a[p2];
    a[(p2 + 1) / 2] += a[p2];
    --p2;
    while (sum - a[p1] >= k) {
      sum -= a[p1];
      ++p1;
    }
  }
  printf("%d\n", p1);
  return 0;
}

Codeforces 766D - Mahmoud and a Dictionary

发表于 2017-02-20 分类于 Codeforces Disqus：

链接

传送门

题意

给出\(n\)个单词，\(m\)个关系，\(q\)个询问，每个关系有如下情况

\(1 \space x \space y\)，表示\(x\)和\(y\)是近义词；
\(2 \space x \space y\)，表示\(x\)和\(y\)是反义词。

对于关系，如果关系与之前的关系不冲突，输出“YES”；否则，输出“NO”。每个询问，给出两个单词，输出二者的关系，1、2、3分别代表近义词、反义词、没有关系。

思路

图的题做的不多，但看这个题第一反应就是并查集。看了题解做的，感觉是道不错的题。用异或和表示两个单词的关系，在Find中维护当前节点\(x\)和\(p[x]\)的关系。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <map>

using namespace std;

typedef long long LL;

const int maxn = 200010;
int p[maxn], a[maxn];
char s[maxn];
vector<int> g[maxn];
map<string, int> dict;

int Find(int x) {
  if (x == p[x]) {
    return x;
  }
  int px = p[x];
  p[x] = Find(p[x]);
  a[x] ^= a[px];
  return p[x];
}

bool Union(int u, int v, int x) {
  int fu = Find(u), fv = Find(v);
  if (fu == fv) {
    return (a[u] ^ a[v]) == x;
  }
  p[fu] = fv;
  a[fu] = a[u] ^ a[v] ^ x;
  return true;
}

int Query(int u, int v) {
  int fu = Find(u), fv = Find(v);
  if (fu == fv) {
    return (a[u] ^ a[v]) + 1;
  }
  return 3;
}

int getID() {
  scanf("%s", s);
  return dict[s];
}

int main() {
  int n, m, q;
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; ++i) {
    scanf("%s", s);
    dict[s] = p[i] = i;
    a[i] = 0;
  }
  while (m--) {
    int x;
    scanf("%d", &x);
    puts(Union(getID(), getID(), x - 1) ? "YES" : "NO");
  }
  while (q--) {
    printf("%d\n", Query(getID(), getID()));
  }
  return 0;
}

HDU 5997 rausen loves cakes

发表于 2017-01-05 分类于 HDU Disqus：

链接

传送门

题意

给出一个颜色的序列，每次有两种操作：

\(1 \space x \space y\)：将所有的颜色\(x\)变为颜色\(y\)；
\(2 \space l \space r\)：查询\([l, r]\)之间有多少个连续的颜色段。

对于每次查询操作，输出查询的结果。

思路

用bit维护当前点是不是新的颜色的开始，然后可以用前缀和算出区间内颜色的段数。对于修改进行启发式合并，储存每种颜色的位置，对于合并，将少的颜色合并到多的颜色上。

代码

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 100010;
const int maxm = 1000010;

int n, bit[maxn];
int a[maxn], p[maxm];
bool ok[maxn];
vector<int>  g[maxm];

inline int lowbit(int x) {
    return x & -x;
}

int Sum(int x) {
    int res = 0;
    while (x > 0) {
        res += bit[x];
        x -= lowbit(x);
    }
    return res;
}

void Add(int x, int d) {
    while (x <= n) {
        bit[x] += d;
        x += lowbit(x);
    }
}

void proc(int p) {
    if (ok[p] && a[p] == a[p - 1]) {
        ok[p] = false;
        Add(p, -1);
    }
}

void proc(int &x, int &y) {
    for (int &v: g[x]) {
        g[y].push_back(v);
        a[v] = y;
        proc(v);
        proc(v + 1);
    }
    g[x].clear();
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int m, op, x, y;
        scanf("%d%d", &n, &m);
        memset(ok, 0, sizeof ok);
        memset(bit, 0, sizeof bit);
        for (int i = 1; i < maxm; ++i) {
            p[i] = i;
            g[i].clear();
        }
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            g[a[i]].push_back(i);
            if (a[i] != a[i - 1]) {
                Add(i, 1);
                ok[i] = true;
            }
        }
        while (m--) {
            scanf("%d%d%d", &op, &x, &y);
            if (op == 1 && p[x] != p[y]) {
                if (g[p[x]].size() < g[p[y]].size()) {
                    proc(p[x], p[y]);
                } else {
                    proc(p[y], p[x]);
                    swap(p[x], p[y]);
                }
            } else if (op == 2) {
                int ans = Sum(y) - Sum(x - 1);
                if (!ok[x]) {
                    ++ans;
                }
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}

Codeforces 721D Maxim and Array

发表于 2016-11-09 分类于 Codeforces Disqus：

链接

传送门

题意

给出\(n\)个数，每次选择一个数字加或减\(x\)，要求进行\(k\)次操作之后所有数字的乘积最小，输出操作后的数字。

思路

分情况讨论。注意要使乘积的绝对值变大时，一定是增加绝对值最小的数字的绝对值。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <vector>
#include <queue>
#define X first
#define Y second

using namespace std;

typedef long long LL;
typedef pair<LL, int> pli;

const int maxn = 200010;

LL a[maxn];
int idx[maxn];
priority_queue<pli, vector<pli>, greater<pli>> q;

int main() {
  int n, k, x;
  scanf("%d%d%d", &n, &k, &x);
  int cnt = 0, cnt1 = 0;
  for (int i = 1; i <= n; ++i) {
    scanf("%lld", &a[i]);
    if (a[i] != 0) {
      if (a[i] < 0) {
        ++cnt1;
      }
      q.push(make_pair(abs(a[i]), i));
    } else  {
      idx[cnt++] = i;
    }
  }
  if (cnt > k) {
    a[1] += LL(k) * x;
  } else {
    if (cnt1 % 2 == 0) {
      if (cnt > 0) {
        a[idx[cnt - 1]] = -x;
        q.push(make_pair(x, idx[cnt - 1]));
        --cnt, ++cnt1;
        --k;
      } else {
        pli p = q.top();
        q.pop();
        if (p.X < LL(k) * x) {
          k -= p.X / x + 1;
          p.X -= LL(p.X / x + 1) * x;
          a[p.Y] = a[p.Y] > 0 ? p.X : -p.X;
          ++cnt1;
        } else {
          p.X -= LL(k) * x;
          a[p.Y] = a[p.Y] > 0 ? p.X : -p.X;
        }
        q.push(make_pair(abs(a[p.Y]), p.Y));
      }
    }
    if (cnt1 & 1) {
      k -= cnt;
      for (int i = 0; i < cnt; ++i) {
        a[idx[i]] = x;
        q.push(make_pair(x, idx[i]));
      }
      while (k--) {
        pli p = q.top();
        q.pop();
        if (a[p.Y] < 0) {
          a[p.Y] -= x;
        } else {
          a[p.Y] += x;
        }
        q.push(make_pair(abs(a[p.Y]), p.Y));
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    printf("%lld ", a[i]);
  }
  puts("");
  return 0;
}

Codeforces 731F Video Cards

发表于 2016-11-06 分类于 Codeforces Disqus：

链接

传送门

题意

给出\(n(1 \leq n \leq 200000)\)个数，选择其中一个\(a_i(1 \leq a_i \leq 200000)\)，将其他的数字都减少到ai的非负整数倍，输出所有数字和的最大值。

思路

对于枚举每个数字，然后二分它所有倍数的个数。因为相同的数字可以忽略，二分的次数为\(O (n\log n)\)，总的复杂度为\(O(n\log^2n)\)

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int maxn = 200010;

int a[maxn];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  sort(a, a + n);
  LL ans = 0;
  for (int i = 0; i < n; ++i) {
    if (i == 0 || a[i] != a[i - 1]) {
      LL sum = 0;
      int *cur, *pre = a;
      for (int j = 0; j <= a[n - 1]; j += a[i]) {
        cur = lower_bound(a, a + n, j + a[i]);
        sum += j * LL(cur - pre);
        pre = cur;
      }
      ans = max(ans, sum);
    }
  }
  printf("%lld\n", ans);
  return 0;
}

Codeforces 731C Socks

发表于 2016-11-06 分类于 Codeforces Disqus：

链接

传送门

题意

有\(n\)只袜子，\(m\)天，每天给出两只要穿的袜子，要求每天穿的袜子的颜色相同，问最少改变几只袜子的颜色。

思路

同一天要穿的袜子之间连一条边，然后求并查集中最多的颜色，每个并查集颜色的总数与最多颜色的差的和即为答案。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn = 200010;

int c[maxn], p[maxn];
vector<int> g[maxn];

int Find(int x) {
  return x == p[x] ? x : p[x] = Find(p[x]);
}

int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; ++i) {
    p[i] = i;
    scanf("%d", &c[i]);
  }
  while (m--) {
    int u, v;
    scanf("%d%d", &u, &v);
    int fu = Find(u), fv = Find(v);
    p[fu] = fv;
  }
  for (int i = 1; i <= n; ++i) {
    g[Find(i)].push_back(c[i]);
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    int Max = 0, tmp = 0, pre = -1;
    sort(g[i].begin(), g[i].end());
    for (int x: g[i]) {
      if (x != pre) {
        tmp = 0;
      }
      Max = max(Max, ++tmp);
      pre = x;
    }
    ans += int(g[i].size()) - Max;
  }
  printf("%d\n", ans);
  return 0;
}

Codeforces 733D Kostya the Sculptor

发表于 2016-11-06 分类于 Codeforces Disqus：

链接

传送门

题意

给出一些长方体，可以选一个长方体或两个有一面相同的长方体粘在一起变成一个大长方体。问使长方体内接球最大的选法。

思路

内接球的大小由长方体最短的棱决定，所以每次拼接只有延长最短的棱才有意义，用map存一下最短边的长度搞一搞就好啦。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define X first
#define Y second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 100010;

int a, b, c;
map<pii, pii> dict;

int main() {
  int n, Max = 0, ans = 0, x = 0, y = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d%d", &a, &b, &c);
    if (a < b) {
      swap(a, b);
    }
    if (a < c) {
      swap(a, c);
    }
    if (b < c) {
      swap(b, c);
    }
    if (c > Max) {
      ans = 1;
      x = i;
      Max = c;
    }
    pii k = make_pair(a, b);
    pii& v = dict[k];
    if (v.Y != 0) {
      int cur = min(b, v.X + c);
      if (cur > Max) {
        ans = 2;
        x = v.Y;
        y = i;
        Max = cur;
      }
    }
    if (v.X < c) {
      v = make_pair(c, i);
    }
  }
  printf("%d\n", ans);
  if (ans == 1) {
    printf("%d\n", x);
  } else {
    printf("%d %d\n", x, y);
  }
  return 0;
}

Codeforces 733C Epidemic in Monstropolis

发表于 2016-11-05 分类于 Codeforces Disqus：

链接

传送门

题意

给出两个序列\(a\)和\(b\)。每次可以将\(a\)中的两个大小不同的数字合并，合并后的数字为原来两数字之和，问能否使序列\(a\)与\(b\)相同，如果能输出合并方法。

思路

对于\(b\)中的每个数字都是由\(a\)中的一段区间和组成的，显然\(b\)中数字对应的\(a\)中的区间是唯一的，如果有区间包含的数字个数大于1且所有数字相同就无法合并。确定\(b\)中每个数对应的区间后，每次找最大且周围存在数比他小的数字合并即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>

using namespace std;

const int maxn = 510;

int a[maxn], b[maxn];
int p[maxn], Max[maxn];

int main() {
  int n, m;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  scanf("%d", &m);
  p[0] = 1;
  for (int i = 1; i <= m; ++i) {
    scanf("%d", &b[i]);
    int cnt = 0, sum = 0, j = p[i - 1];
    while (sum < b[i] && j <= n) {
      if (a[j] > Max[i]) {
        Max[i] = a[j];
        cnt = 0;
      }
      if (a[j] == Max[i]) {
        ++cnt;
      }
      sum += a[j];
      ++j;
    }
    p[i] = j;
    if (sum != b[i] || (cnt == p[i] - p[i - 1] && cnt != 1)) {
      puts("NO");
      return 0;
    }
  }
  if (p[m] != n + 1) {
    puts("NO");
    return 0;
  }
  puts("YES");
  for (int i = 1; i <= m; ++i) {
    int l = 0, r = 0, pos = 0, dt = p[i] - p[i - 1];
    if (dt == 1) {
      continue;
    }
    for (int j = 0; j < dt; ++j) {
      if (a[j + p[i - 1]] == Max[i]) {
        if (j != 0 && a[j + p[i - 1] - 1] != Max[i]) {
          printf("%d L\n", j + i);
          l = j - 1, r = dt - j - 1;
          pos = j + i - 1;
          break;
        }
        if (j != dt - 1 && a[j + p[i - 1] + 1] != Max[i]) {
          printf("%d R\n", j + i);
          l = j, r = dt - j - 2;
          pos = j + i;
          break;
        }
      }
    }
    while (l--) {
      printf("%d L\n", pos--);
    }
    while (r--) {
      printf("%d R\n", i);
    }
  }
  return 0;
}