作者存档：edward_mj

省赛 & TCO2C 后有感

今年的省赛算是毫无悬念地夺冠了。
但是感觉猛犸只要配上一个外语好的妹子帮他看题，也是可以夺冠的……
整个流程中只有我的G题稍微显得有点慢，其它的基本都是秒杀。
其实这种分类比较复杂，不容易想清楚的dp我写得比较慢已经是一种常态了。
一直想知道为什么，直到今晚TCO2C 550惨跪以后，好像明白了一点点。
主要原因我觉得有以下两个

  1. 对于相似的转移经常是硬写，并且即使是相似的转移，写到一半也会停下来重复思考这个地方怎么写。也就是不擅于处理类似的东西。所谓的以力破巧么……解决这种相似问题的转移无外乎那么几种方法：

    1. Ctrl-c, Ctrl-v
    2. 写一个函数来处理这些类似的地方(代码重用)
    3. 直接用参数表示那几种相似但不同的情况，然后通过统一的带参数的计算处理

    第一种无疑是最SB的……但是有时候也还是挺有效的。可是万一写错，就是一个个改……实在有点蠢……而且有一些差别容易忘了改掉。
    第二种是比较oop的做法，只要设计好接口。但是这样整体的case划分框架还是得弄出来，但是比第一种好多了，也比较容易让人接受。
    第三种是最神的，首先得清楚地了解哪些状态可以通过参数合并，然后再设计好对应的参数，不想清楚选这种简直是找死……（详情可以参看shi哥ZOJ3466的代码……不知道shi哥是事后看到类似的把代码缩在一起还是写之前就想到这样了-.-)
    而我发现自己很难做到第三种，大概是因为我在写代码前，根本没有做到完全想清楚每一个转移怎么搞。还有一个原因可能是不太擅于对相似的事物找出共同点并归类。
    这种感觉和看functional programming的感觉有点类似，要具备能迅速反应出a其实是b的能力才会比较舒服。

  2. 在写之前这个程序长什么样往往还没有规划好。写一半又犹豫，写一半又犹豫，其实这才是最费时的。

第一个似乎也没什么特别有效的解决方法，碰到类似的问题在AC后注意精炼一下代码也许是个不错的注意。
第二个强迫自己写之前想清楚，而不是只把一个粗略的流程想出来以后马上就开始写。虽然这很多时候有点难度，但是感觉注意一下的话，这种能力总是会提高的吧……

Codeforces Round #180 (Div. 1)

A
假设1的个数是偶数个(设为x)，那么1的个数不可能超过x个。
假设1的个数是奇数个(设为x)，那么1的个数可以变为x+1个。
当然，想要1的数目变少只要不断地pop就可以了。
显然，0可以在中间随便插，所以最后只要判1的个数。

B
当且仅当我们可以找到这样一组匹配的时候，A没法超过B：
对于每个$$0 \leq i \lt n$$有$$a[i] \leq b[match[i]]$$
证明：
1、显然有此匹配时，$$\sum a_i \leq \sum b_i$$。
2、当没有这种匹配时，对于没有被匹配到的a[i]，重量取个超级大的数，然后后面的重量都一样，那么A就可以超过B了。
所以只要a, b sort一下作一下判断就可以了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

typedef long long ll;

#define foreach(it, v) for (__typeof((v).end()) it = (v).begin(); it != (v).end(); it++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define forn(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)
#define clr(a, x) memset(a, x, sizeof(a))
#define all(v) (v).begin(), (v).end()
const int N = 100005;
int m, n, k;
int a[N], b[N];

int main() {
    scanf("%d%d%d", &m, &n, &k);
    rep (i, m) scanf("%d", &a[i]);
    rep (i, n) scanf("%d", &b[i]);
    sort(a, a + m);
    sort(b, b + n);
    int j = 0;
    bool flag = 0;
    rep (i, m) {
        while (j < n && b[j] < a[i]) j++;
        if (j == n) {
            flag = 1;
            break;
        }
        j++;
    }
    puts(flag ? "YES" : "NO");
}

C
构造题不懂……其实就是太弱，一直以为6 0 1 2 3 4 5这组数据是无解的，导致后面想歪了。
看了rng_58的代码茅塞顿开。
其实根本没有无解的情况
按s sort一下，然后令m = (n + 2) / 3。
第一部分(0 <= i < m)：a[i] = 0, b[i] = s[i] 第二部分(m <= i < m + m)：a[i] = s[i], b[i] = 0 第三部分(m + m <= i < n)：a[i] = n - i - 1, b[i] = s[i] - a[i] 第一部分的用意是把a的[1,m-1]这个区间内的值空出来 第二部分的用意是把b里[s[m - 1] + 1, +oo)这个区间的值空出来 第三部分a就把第一部分的坑填了，b则保证了大于s[m - 1]，并且b值严格递增。 不得不服。 D 先保证m<=n，然后让横的限制全满足，竖的限制满足超过一半即可。只需要0，1就够了。 E 坑