坑爹了呢,本来好好的一场黄的Div1,被模板坑了呢,所以纪念一下。
A
这题的操作有 DFS 的性质,反正是子树嘛,而且原来的操作叠加多次会抵消,设计一个函数 dfs(int x, int pre, int dep, int odd, int even) 直接深搜下去,O(1) 修改,O(n) 搞定了。下面是一些思考:
这题为什么可以不用线段树,其他类似的题能像这题这么搞么?这里有几道比较像的题目:CF396CCF384E
上面这两题都不能通过 DFS 直接解决,原因在于,他们的操作虽然有 DFS 的性质,也是在子树上进行的嘛,但是他们的操作的顺序给定了,而不是自由的,也就是说可能先操作深度较大的点,后操作深度较小的点,这样就没有办法维护了。但是如果像这题一样,能够保证对于同一颗子树上的点,总是先操作深度较小的点的话,也就可以通过 DFS 直接解决了。这题之所以可以这样做,就是因为我们发现,深度较小的点总是应该先改动。
代码
B
画图之后发现路径交叉于一点只有两种可能,剩下就是最经典的权值路径的 DP. (数字三角形总做过吧?)
这题的写法可以稍微考究一下:直接两个for循环就可以了。因为边界的情况,我们取的是最大值,而不存在的边界处值是0,所以肯定不会被当作最优解。所以就不用像我的代码那么蛋碎地写了边界处的DP了,(Ps,比赛的时候就是因为这个地方的DP,打错了一个字母,错误提交了依法,有时候稍微多考虑一步,减少一些代码量,对我这种粗心的渣渣,还是很关键的啊!吸取教训,加油!)
代码
C
待续
D
好吧,坑货。多年没碰 Closest_Pair 的模板了,结果我的模板大概之前自己动过,少了一行sort的代码,直接跪了,TLE on 13.
这题只需要一个想法,转化成几何,构造点 (i, s[i]),之后就是求最近点对的经典问题了。
我一开始看着表达式就很想斜率DP,结果没出来,就开始画图,然后就想到了,当时过的人还不多,贴了一个"模板",开心地房间 RANK1,结果跪了TAT。直接从RANK99变成RANK440。黄名梦想就此破灭。我是来贴版的!
Closest_Pair

//LL version
struct po{
    LL x, y;
    po (LL a = 0, LL b = 0) : x(a), y(b) {}
}p[N];

//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Attention  sort(p, p + n, cmpxy);

inline bool cmpxy(const po &a, const po &b) { //initailly  sort all points using cmpxy
 if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

inline bool cmpy(const int &a, const int &b) {return p[a].y < p[b].y;}

LL sqr(LL x) {return x * x;}

//return (dis * dis)

LL dis(const int &i, const int &j) { return sqr(p[i].x - p[j].x) + sqr(p[i].y - p[j].y);} //square of dis

int tmp[N];

LL Closest_Pair(int left, int right) { 
    LL d = INF; // square of ans
 if (left == right) return d;
    if (left + 1 == right) return dis(left, right);
    int mid = (left + right) >> 1;
    LL  dl = Closest_Pair(left, mid);
    LL dr = Closest_Pair(mid + 1, right);
    d = min(dl, dr);
    int cnt = 0;
    REPP(i, left, right) {
        if (sqr(p[mid].x - p[i].x) <= d) { //square of x
         tmp[cnt++] = i;
        } 
    }
    sort(tmp, tmp + cnt, cmpy);
    REP(i, cnt) {
        for (int j = i + 1; j < cnt && sqr(p[tmp[j]].y - p[tmp[i]].y) < d; ++j) { //square of y
         LL dd = dis(tmp[i], tmp[j]); // Attention tmp[i] not i !!!!!!!!!!!!!!!!!!!!!!!!! 
         if (d > dd) d = dd;
        }
    }
    return d;
}

//square of dis 
// dis need to change dis function and sqr part

//dou version
struct po{
    dou x, y;
    po (dou a = 0, dou b = 0) : x(a), y(b) {} 
}p[N];

inline bool cmpxy(const po &a, const po &b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

inline bool cmpy(const int &i, const int &j) {return p[i].y < p[j].y;} 

dou sqr(dou x) {return x * x;}

dou dis(const int &i, const int &j) {return sqrt(sqr(p[i].x - p[j].x) + sqr(p[i].y - p[j].y));} 

int tmp[N];

dou Closest_Pair(int left, int right) {
    dou d = 1e100;
    if (left == right) return d;
    if (left + 1 == right) {
        return dis(left, right);
    }
    int mid = (left + right) >> 1;
    dou dl = Closest_Pair(left, mid);
    dou dr = Closest_Pair(mid + 1, right);
    int cnt = 0;
    d = min(dl, dr);
    REPP(i, left, right) {
        if (abs(p[i].x - p[mid].x) <= d) {
            tmp[cnt++] = i;
        }
    } 
    sort(tmp, tmp + cnt, cmpy);
    REP(i, cnt) {
        for (int j = i + 1; j < cnt && p[tmp[j]].y - p[tmp[i]].y < d; ++j) { // !!!!!!!!!!!!!!!!!!!! tmp[i] not i
         dou dd = dis(tmp[i], tmp[j]); // !!!!!!!!!!!!!!!!!
         if (d > dd) d = dd;
        }
    }
    return d;
}

// call sort(p, p + n, cmpxy) first !!!!!!!!!!!!!!!!!!!!!!!!!!!!!


代码
推荐一道模板测试题吧:
USTCOJ1394
E
待续

整理一下以前做的 CF 的题,话说今天的 TC 做的真差,不知道为何 250 的 SG 定理也挂了,真是不开心。还是先不去管了,rating怒掉 190+,短暂的 TC & CF 双黄的生涯到此结束,估计以后也很难有了。TAT
这场 CF 题目质量貌似蛮高的,我比较喜欢 B C D 这三道题。
A
构造题,枚举加判平行。
代码
B
DP,需要观察和清晰的思维。
C
数学题,很厉害的感觉,一开始我还想当作线段树来做呢,其实是离线的,还要利用前缀和的组合数性质,我是没有直觉发现这些东西的。
题解的思路比较有启发性。注意这里的 k <= 100。
首先数组初始值是没有用的信息。关键我们处理组合数部分。
考虑 k = 0,那么相当于给一段子区间全部加 1。这个操作还可以这么表示,一个初始全为 0 的数组,在 l 处加 1,r + 1 处 减 1,然后对这个数组求前缀和,就得到了一个 [l, r] 区间内都是 1 的数组。(这里为什么要用前缀和表示呢?因为我们要加的组合数是有这样的前缀和的性质的)。
考虑 k = 1,那么按题意相当于给一段子区间加上 1,2,3 ... r - l + 1。这个可以怎么得到呢?我们先得到 [l, r] 内都是 1 的数列,然后求前缀和,就得到了和以上我们需要的序列很像的序列,只是最右边不是 0 而是一个固定值,怎么办呢?类似前面,我们先在 r + 1处加上这个数的相反数再求前缀和即可,所以这里相当于对数列设置了两次,然后进行了两次前缀和操作,由于 k <= 100,对于任意 k,题目中对应的要进行操作的序列,我们都可以类似上面对数列进行至多 100 次设置操作,然后 100 次前缀和操作得到。设置的值很容易找到规律。
好了现在问题来了,优化!如果裸着求每次设置的数列,然后把这些数组加起来,需要 O(n^2) 的时间和空间,妥妥跪,好在这个前缀和有很好的性质:
两个数列分别求前缀和然后对应位置相加得到的数列 = 两个数列先对应位置相加然后求前缀和得到的数列。(这其实一点也不神,不就是加法交换律么?)
所以对于某个 k,要对数列进行 k 次设置,k 次求前缀和,关键是 询问有 n = 10^5 个,但是所有 k 相同的要进行的 前缀和次数是一样的。所以我们可以在读入询问的时候把所有数组设置好左右值,这里因为两个 k 相同的操作,可以叠加在一个数组上,所以只需要 O(kn) 的空间,然后我们考虑求前缀和,k 的数组要求 k 次前缀和才能得到我们想要的值。难道要一个个分开算?O(nk^2),又跪了,注意两个前缀和操作的可加性,我们先做大的,比如询问里的 k 有 2,3,5,那么先做 5,5做了 2 次以后,把得到的序列和 3 的序列加起来,然后一起做前缀和,然后再做一遍,之后又可以和 2 的序列加起来做前缀和了。所以最后可以只做 k 次前缀和,复杂度降为 O(nk)。本题完全解决。
最后注意一下设置操作的值的规律是组合数,需要预处理,可以直接杨辉三角,可以预处理阶乘,利用费马小定理。
代码

A
这题告诉我们一定要看清数据范围!直接上 O(n^3 * k)。注意不要再逗比白送分了!
代码
B
爱酱觉得这题很好,需要想法,他说他想不到,结果我很幸运地想出来了,其实我觉得这题确实是蛮好的!而且有坑,我就被坑了一下,还好在没被 cha 的时候就补交了一次。题意就是你可以对最多 k (k <= 10) 个数字进行变换,让最后的矩形的连通块都是小矩形。首先,常规分析,一个数字不会操作多余 1 次,因为 2 次会变回去,浪费。然后就卡住了,怎么保证最后的状态所有相同数字的连通块是小矩形呢?暴力枚举修改哪些点么? 最后是 10000 选 10,2 的指数级别,不可能啊。怎么办?这时候我就去分析了一下,最后矩阵的可能状态,因为只有有邻边就是属于一个连通块,所以假设现在有一个 0 的小矩形,那么它的边上是 1 的小矩形,右边挨着,下边也挨着,右下角是什么呢?只能是 1 的小矩形,而且,右边和下边的 1 的小矩形有什么特点?必须刚好和我们考察的 0 这个小矩形的对应边一样大!不然超出了,这两个 1 的小矩形就会成为一个连通块,这就不是最后合法的矩阵状态了。所以这题就解决了,因为必然是 0,1 的小矩形相互间隔,而且宽度一定相同,所以上下两行之间的数字,要么完全相同,要么是取反关系!真的结束了么?还没呢!我们怎么算最后的状态呢?我一开始的直觉是必然有一行不变(这种贪心还是比较正常的想法吧?)所以就暴力枚举哪一行不变,O(n^3),写了交,居然过了 pretest!但是这题其实是有坑的!考虑下面的数据:
3 3
1 1 0
1 0 1
0 1 1
如果按我说的,必然有一行不变的话,得不到正解!而正解显然是把那些 0 全部改成 1。说明我的直觉错了,有可能有情况是所有行都会被修改的!怎么办?注意到 k <= 10 ! 设想一下你要修改每一行至少一个数,但你最多修改 10 次。说明行数很小!直接 2^n 暴力枚举修改的数字,然后就确定了这一行,然后就可以确定最后状态了!这题总算做完了,我写题解的时候忽然感觉我比赛时写的代码有小问题!但是系统没挂我,可能能证明那样可以吧?但我还是决定重新写一个正解。(这题告诉我们,直觉确实能启发思路,但要检验一下直觉的正确性啊!)
代码
C
待续
D
一看就像是原题,结果一问爱酱,真的是,想上代码,又觉得不太好,纠结了一下,上了 VJ 上岛娘的代码,比赛结束了,Rank 90左右,心里有愧疚啊!结果 FST 了,稍稍减轻了我心里的愧疚感。其实这题不难的,只是我以前没有接触过 sqrt(n) 的算法,这次总算学会了,感觉很神奇的算法啊!这题的 TL被吐槽了!我赛后交了大概30发的 TLE!当然不是 TL 的原因,是我自己写错了,让那个算法变成了 O(n^2),结果我还以为是 O(sqrt(n) * n)! TAT
算法主要思想是这样的:(看这个 comment 学习的)我们对所有点按纵坐标分组,至多 n 组,对于这些组,我们按组内的点的个数把他们分为两类,large 和 small,点数 >= sqrt(n) 为 large。这样做之后可以对不同类的不同处理。首先每个正方形都可以用最上面的两个点唯一确定!这两个点可以在 small 线上,也可以在 large 线上!假设在 small 线上,那么在这条线上的两点对是 n 级别的,然后确定了两点之后,确定了边长,可以在它下方相同距离的地方找两个有同样横坐标的点,这一步用 hash 或者 unordered _ set 可以 O(1) 解决,最后 small 线的数量是 n 所以这部分的时间复杂度是 O(sqrt(n) * n),然后考虑 large 线,large 线的数目不会超过 sqrt(n),然后我们枚举在它下方的线上的每个点,就可以唯一确定正方形的边长和点的坐标了!然后同样检查点是否存在即可。这一步有个坑!如果你枚举的是 large 线上的点,然后在在它下方的线上找点,每次都得 枚举 large 上的每个点,规模是 n,在它下方的线的规模也是 n,所以算法就成了 O(n * n),但是事实上我们应该枚举的是在它下方的点,规模是 n 然后查找是否存在是 O(1),总共最多 sqrt(n) 条 large 线,所以算法是 O(sqrt(n) * n) 的。
这题还是复习了好多东西的,挂链的 hash,新学了分块大发,(虽然这题比较特殊,不算常规应用吧?我总感觉分块是用在图论里面的),新学了 unordered _ set 的用法,加强了思维,不要随意乱写代码,让算法退化!
代码
E
待续

一夜黄名!老子终于也黄号了!虽然马上就会掉回去的!
这场也有东西可以总结!
A
首先A自己很逗,8分钟过 pretest,结果比赛过了一个小时被 hack 了,原因居然是判无解的情况的 < 和 <= 打错了。其实也是自己不对,老是喜欢用除法,整数除法有点麻烦,其实用乘法可以很简洁地表示 2 * m + 1 > n 则无解啊!白送200分。。。
B
首先这题问题数只有20,状压,但是每个人有个屏幕数的性质,怎么办?我当时就不会了,经过爱酱提示才会的,其实是可以分析出来的,我们这么想:先考虑如果每个人没有这个屏幕数的性质会怎么样呢?怎么做?01 背包直接搞啊,从左到右,如果不选这个人就是上一层的最优值,如果取了这个人,要和上一层的状态比较取最小值!很简单对吧?注意了,这样做的过程中和这些人原本的顺序没有任何关系啊,也就是说我们把这些人再任意排序,也可以这么做!好再继续考虑有屏幕的限制怎么办?每个人都有个自己的要求数,但是花费只和所选中的人中的最多的屏幕数有关,所以我们把每个人按所需屏幕数排序就可以了!从小到大做,dp[i] 保存不算屏幕数,解决状态 i 的问题所需要的雇人的最少花费,然后如果这时候已经可以解决所有问题,就加上屏幕的花费,和当前最优解比较取最小值,都不需要2个数组,直接一个数组搞定(滚动数组)。(这里滚动数组不需要开两个,这是因为用了 i 个人的状态更新了某个最优解,然后以后若用到这个被 i 更新过的状态去更新其他解,因为他已经包含了第 i 个人的状态,所以解决问题的状态不会改变,但第 i 个人的花费加了多次,显然不会最优,所以一个数组就够了这里,但是有些背包问题不一定可以这样做,视情况而定,是一个数组直接做滚动数组,还是两个数组 0 1 异或变换着 DP)。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <bitset>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#define dou double
#define mem(a) memset(a, 0, sizeof(a))
#define memm(a) memset(a, -1, sizeof(a))
#define LL long long
#define PB push_back
#define MP make_pair
#define PII pair<int, int>
#define FI first
#define SE second
#define RI(a) scanf("%d", &(a))
#define RII(a, b) scanf("%d%d", &(a), &(b))
#define RIII(a, b, c) scanf("%d%d%d", &(a), &(b), &(c))
#define RL(a) scanf("%I64d", &(a))
#define RLL(a, b) scanf("%I64d%I64d", &(a), &(b))
#define RLLL(a, b, c) scanf("%I64d%I64d%I64d", &(a), &(b), &(c)) 
#define PI(r) printf("%d\n", (r))
#define PL(r) printf("%I64d\n", (r))
#define RS(s) scanf("%s", (s))
#define SL(a) strlen(a)
#define REP(i, n) for (int i = 0; i < (int) (n); ++i)
#define REPP(i, a, b) for (int i = (int) (a); i <= (int) (b); ++i)
#define FOR(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
//Segment tree
#define MID ((l + r) >> 1)
#define L (x << 1)
#define R ((x << 1) | 1)
#define LC L, l, MID
#define RC R, MID + 1, r
#define LB(x) ((x) & (-(x)))
#define M (N - 1000)
#pragma warning (disable : 4996)
//#pragma comment(linker, "/STACK:102400000,102400000")
#define EPS 1e-8
#define INF 2000000000
#define LIM (1ll << 60)
#define MOD 1000000007
#define N 111111

using namespace std;

int n, m, b;
LL dp[2][1 << 20];

struct po{
    LL pri, k;
    int pb;
    po(LL a = 0, LL b = 0, int c = 0) : pri(a), k(b), pb(c) {}
}p[N];

bool cmp(po a, po b) {
    return a.k < b.k;
}

int main(){
    int t, x, y, z, ca = 1;
    //freopen("E:/Code/in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
 //ios :: sync_with_stdio(false);
 RIII(n, m, b);
    REPP(i, 1, n) {
        RIII(x, y, z);
        int tt = 0, tem;
        REP(j, z) RI(tem), tt |= (1 << (tem - 1));
        p[i] = po(x, y, tt);
    }
    sort(p + 1, p + 1 + n, cmp);
    int cur = 0;
    memm(dp);
    LL ans = -1;
    dp[cur][0] = 0;
    REPP(i, 1, n) {
        REP(j, 1 << m) dp[cur ^ 1][j] = dp[cur][j];
        REP(j, 1 << m) {
            if (dp[cur][j] != -1){
                if (dp[cur ^ 1][j | p[i].pb] == -1) dp[cur ^ 1][j | p[i].pb] = dp[cur][j]+ p[i].pri;
                else {
                    if (dp[cur ^ 1][j | p[i].pb] >= dp[cur][j] + p[i].pri) {
                        dp[cur ^ 1][j | p[i].pb] = dp[cur][j] + p[i].pri;
                    }
                }
            }
        }
        if (dp[cur ^ 1][(1 << m) - 1] != -1 && (ans == -1 || ans > dp[cur ^ 1][(1 << m) - 1] + p[i].k * b)) ans = dp[cur ^ 1][(1 << m) - 1] + p[i].k * b;
        cur ^= 1;
    }
    PL(ans);

    return 0;
}

C
经典的数竞构造题啊,好水,但是一想自己要过C就好激动,结果写了好久,中间小错误不断!下次一定要蛋定些啊!首先我们要把行列拆开,对任意 n 如果我们能找到一个长度为 n 的数列,使得 :

那么对行我们找到长度 n 的一个数列 An,对列我们找到一个长度为 m 的一个数列 Bm,最后我们就可以按下面的方法构造矩阵:
a1b1 a1b2 a1b3 ... a1bm
a2b1 a2b2 a2b3 ... a2bm
...
anb1 anb2 anb3 ... anbm
这个矩阵显然就满足要求了!于是我们的问题转化为如何求一个长度 n 的数列使得他们的平方和是完全平方数。
最自然的想法就是前面一些是相同的,然后最后一个数直接调整使得整个数列的平方和是完全平方数。
注意到:

这里 2n+1 是奇数,4n+4 是偶数所以已经解决了奇偶的所有情况,构造就很简单了:
比如前面所有数都是 2,那么平方和是 4*(n - 1), 为了加上最后一个数的平方后市完全平方数,可以这样,利用上面的二式,我们让4n-4 = 4x+4,于是 x = n - 2,所以取最后一个数是 n - 2 即可。好吧我发现根本不需要奇偶讨论就可以了,直接构造 2,2,...,n - 2即可,这对所有 n > 2 成立。 n = 1,2 随便构造吧,所以这题就解决了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <bitset>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#define dou double
#define mem(a) memset(a, 0, sizeof(a))
#define memm(a) memset(a, -1, sizeof(a))
#define LL long long
#define PB push_back
#define MP make_pair
#define PII pair<int, int>
#define FI first
#define SE second
#define RI(a) scanf("%d", &(a))
#define RII(a, b) scanf("%d%d", &(a), &(b))
#define RIII(a, b, c) scanf("%d%d%d", &(a), &(b), &(c))
#define RL(a) scanf("%I64d", &(a))
#define RLL(a, b) scanf("%I64d%I64d", &(a), &(b))
#define RLLL(a, b, c) scanf("%I64d%I64d%I64d", &(a), &(b), &(c)) 
#define PI(r) printf("%d\n", (r))
#define PL(r) printf("%I64d\n", (r))
#define RS(s) scanf("%s", (s))
#define SL(a) strlen(a)
#define REP(i, n) for (int i = 0; i < (int) (n); ++i)
#define REPP(i, a, b) for (int i = (int) (a); i <= (int) (b); ++i)
#define FOR(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
//Segment tree
#define MID ((l + r) >> 1)
#define L (x << 1)
#define R ((x << 1) | 1)
#define LC L, l, MID
#define RC R, MID + 1, r
#define LB(x) ((x) & (-(x)))
#define M (N - 1000)
#pragma warning (disable : 4996)
//#pragma comment(linker, "/STACK:102400000,102400000")
#define EPS 1e-8
#define INF 2000000000
#define LIM (1ll << 60)
#define MOD 1000000007
#define N 111

using namespace std;

int nn, mm, a[N], b[N];
int mp[N][N];

void go(int *p, int n) {
    if (n == 1) p[1] = 1;
    else if (n == 2) p[1] = 3, p[2] = 4;
    else if (n == 3) p[1] = 3, p[2] = 4, p[3] = 12;
    else {
        if (n & 1) {
            REPP(i, 1, n - 1) p[i] = 2;
            p[n] = (n - 2);
        }
        else {
            REPP(i, 1, n - 1) p[i] = 3;
            p[n] = (9 * n - 10) / 2;
        }
    }
}

int main(){
    int t, x, y, z, ca = 1;
    //freopen("E:/Code/in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
 //ios :: sync_with_stdio(false);
 RII(nn, mm);
    go(a, nn);
    go(b, mm);
    /*REPP(i, 1, nn) cout << a[i] << ' ';
    cout << endl;
    REPP(i, 1, mm) cout << b[i] << ' ';
    cout << endl;*/
    REPP(i, 1, nn) {
        REPP(j, 1, mm) {
            printf("%d ", a[i] * b[j]);
        }
        puts("");
    }


    return 0;
}

我又来总结自己的逗比了,三省吾身,一场比赛还是能收获不少的知识。
B
状压DP,特意看了一下自己做这题花的时间,1个小时10分钟吧。照着这速度很难在以后比赛里有什么作为啊,还拖累队友。主要这题改动太多了,一开始裸的滚动数组状压,TLE,改了代码,加上按二进制中 1 的个数先后 DP 这个优化后才过。这题其实就是来卡代码时间的,自己以后还是要多注意细节。能写好点尽量写的好点。能想到的优化都加上。赛后看到了一个不需要滚动数组的代码,然后和自己的一对比发现自己也是挺逗的,状态转移的前后肯定不会有重叠的,所以根本没有必要保存前面的状态和当前的状态,只要一个数组就够了。dp[i][j] 表示当前已经分配位置的题目所占位置的状态为 i,有趣度为 j。因为我们每次加一个题目,所以对应的状态里的 1 的个数按每组加 1 的顺序可以加速 DP。这完全可以用一个数组预处理出来。(我原来写的代码是用一个队列保存的,每次利用队列里的数可以计算出下一组数,但是这样还是太慢了)。另外这题求出了所有合理的方案数之后,就知道了单次分配成功的概率,这个事件满足几何分布,期望可以直接背公式 EX = 1/p。(最近正好学的概率论,要跪的节奏啊),其实求期望还有一种迭代法,适用于一般一些常见的情况,能快速求出期望,避免了复杂的数学公式推导:
设期望是 EX 的话,对于这题, p * 1 + (1 - p) * (EX + 1) = EX (这里迭代地利用了期望的性质) 求得 EX = 1/p。

int n, m, mp[12][12];
LL dp[1 << 12][555], fac[13];
vector<int> f[13];

int getbit(int x) {
    int re = 0;
    while (x) re++, x &= (x - 1);
    return re;
}

void Init() {
    fac[0] = 1;
    REPP(i, 1, 12) fac[i] = fac[i - 1] * i;
    REP(i, 1 << 12) f[getbit(i)].push_back(i);
}

LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }

int main(){
    int t, x, y, z, ca = 1;
    //freopen("E:/Code/in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
 //ios :: sync_with_stdio(false);
 Init();
    RI(t);
    while (t--) {
        RII(n, m);
        REP(i, n) REP(j, n) RI(mp[i][j]);
        dp[0][0] = 1;
        REPP(i, 1, n) {
            int kk = f[i - 1].size();
            REP(h, kk){
                x = f[i - 1][h];
                REP(j, n) if (((1 << j) & x) == 0) REPP(k, 0, m) if (dp[x][k]) dp[x | (1 << j)][min(k + mp[i - 1][j], m)] += dp[x][k];
            }
        }
        LL uu = dp[(1 << n) - 1][m], dd = fac[n];
        if (uu == 0) puts("No solution");
        else {
            LL d = gcd(uu, dd);
            cout << dd / d << '/' << uu / d << endl;
        }
        mem(dp);
    }

    return 0;
}

C
CF 上绝逼做过类似的题,结果还是不会做,这次再也不能忘记了,如果尝试裸的构造,思路会非常混乱,我们需要换个角度看问题,假设我们最终用了 X 次操作,相当于我们有 X 个箱子,我们要把 a1 个颜色 1 的球,a2 个颜色 2 的球...... an 个颜色 n 的球都放进这 X 个箱子里每个箱子最多放 K 个球,有什么另外的要求么?每个箱子不能有同样颜色的球。于是我们把 X个箱子水平排开,从左往右开始放球,先 a1 个颜色 1 的球然后 a2 个颜色 2 的球,继续下去,于是要求 X >= max(a[i], sum/K)。答案就是这个了,上述过程不仅给出了答案,还给出了操作方案,每个箱子求对应了一次操作。

int main(){
    int t, x, y, z, ca = 1;
    //freopen("E:/Code/in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
 //ios :: sync_with_stdio(false);
 RI(t);
    int sum, mm;
    while (t--) {
        RII(n, m);
        sum = 0, mm = 0;
        REPP(i, 1, n) RI(x), sum += x, mm = max(mm, x);
        PI(max(mm, (sum + m - 1) / m));
    }

    return 0;
}

E
我忽然觉得拓扑排序和状压 DP 这种经典东西 regional 的题目特别喜欢考,这题我们可以从图上的 O 和 X 得出行操作和列操作的先后关系,由此可以构建有向图,行列操作都作为一个节点,然后按要求进行拓扑排序就可以得到字典序最小的解了。注意一下有些节点不一定最终被操作,开个数组事先标记一下就可以了,拓扑排序的时候就可以不把它加入答案中。

int n, m, in[2 * N], vis[2 * N], ans[2 * N], re, use[2 * N];
char s[N][N];
vector<int> e[2 * N];
vector<int> q[2 * N];//r -- x     c -- x + 500

void dfs(){
    int x, y;
    REPP(i, 1, 2 * n) q[i].clear();
    int now = 0;
    while (1) {
        for (auto tt = q[now].begin(); tt != q[now].end(); ++tt) {
            x = *tt;
            if (use[x]) ans[re++] = x;
            for (auto itr = e[x].begin(); itr != e[x].end(); ++itr) {
                y = *itr;
                in[y]--;
                if (in[y] == 0 && !vis[y]) q[now + 1].push_back(y), vis[y] = 1;
            }
        }
        now++;
        if (q[now].size() == 0) break;
        sort(q[now].begin(), q[now].end());
    }
}

void go() {
    mem(use);
    REP(i, n) e[i].clear();
    REPP(i, 500, 500 + n - 1) e[i].clear();
    REP(i, n){
        REP(j, n) {
            if (s[i][j] == 'O') in[j + 500]++, e[i].push_back(j + 500); //jlie zai ihang hou
         else use[i] = 1;
        }
    }
    REP(i, n) REP(j, n) {
        if (s[i][j] == 'X') in[i]++, e[j + 500].push_back(i);
        else use[j + 500] = 1;
    }
}

int main(){
    int t, x, y, z, ca = 1;
    //freopen("E:/Code/in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
 //ios :: sync_with_stdio(false);
 RI(t);
    while (t--) {
        RI(n);
        REP(i, n) RS(s[i]);
        go();
        int st = -1;
        REP(i, n) if (in[i] == 0) {
            st = i;
            q[0].push_back(i);
        }
        REPP(i, 500, 500 + n - 1) if (in[i] == 0){
            st = i;
            q[0].push_back(i);
        }
        if (st == -1) puts("No solution");
        else {
            re = 0;
            dfs();
            REP(i, re) printf("%c%d%c", (ans[i] < 500 ? 'R' : 'C'), (ans[i] >= 500 ? ans[i] - 500 : ans[i]) + 1, (i == re - 1 ? '\n' : ' '));
        }
        q[0].clear();
        mem(in), mem(vis), mem(ans);
    }

    return 0;
}

比赛链接
F Calculate the Function
签到级别的题目,自己没做出来,一定是智商问题,只会死板得套经验,一直在推公式,递推式,企图用矩阵快速幂,这题其实是个线段树。

由上面的递推关系可以得出矩阵,但是每次乘的矩阵不一样,不能用矩阵快速幂。怎么破?线段树!每个节点保存一段区间的矩阵,然后查询,相当于做矩阵乘法。真是捉急啊。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <bitset>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#define dou double
#define mem(a) memset(a, 0, sizeof(a))
#define memm(a) memset(a, -1, sizeof(a))
#define LL long long
#define PB push_back
#define MP make_pair
#define PII pair<int, int>
#define FI first
#define SE second
#define RI(a) scanf("%d", &(a))
#define RII(a, b) scanf("%d%d", &(a), &(b))
#define RIII(a, b, c) scanf("%d%d%d", &(a), &(b), &(c))
#define RL(a) scanf("%I64d", &(a))
#define RLL(a, b) scanf("%I64d%I64d", &(a), &(b))
#define RLLL(a, b, c) scanf("%I64d%I64d%I64d", &(a), &(b), &(c)) 
#define PI(r) printf("%d\n", (r))
#define PL(r) printf("%I64d\n", (r))
#define RS(s) scanf("%s", (s))
#define SL(a) strlen(a)
#define REP(i, n) for (int i = 0; i < (int) (n); ++i)
#define REPP(i, a, b) for (int i = (int) (a); i <= (int) (b); ++i)
#define FOR(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
//Segment tree
#define MID ((l + r) >> 1)
#define L (x << 1)
#define R ((x << 1) | 1)
#define LC L, l, MID
#define RC R, MID + 1, r
#define LB(x) ((x) & (-(x)))
#define M (N - 1000)
#pragma warning (disable : 4996)
//#pragma comment(linker, "/STACK:102400000,102400000")
#define EPS 1e-8
#define INF 2000000000
#define LIM (1ll << 60)
#define MOD 1000000007
#define N 2

using namespace std;

int n, m, a[111111], ql, qr;

struct mat{
    LL a[N][N];
    mat() { mem(a); }
}I, F, matrix[4 * 111111];

void Init(mat &y, int x) {
    LL tem[N][N] = {
        {0, a[x]},
        {1, 1}
    };
    REP(i, N) REP(j, N) y.a[i][j] = tem[i][j];
}

mat mul(mat a, mat b) {
    mat re = mat();
    REP(i, N) REP(j, N) REP(k, N) {
        re.a[i][j] = (re.a[i][j] + a.a[i][k] * b.a[k][j]) % MOD;
    }
    return re;
}

void bld(int x, int l, int r) {
    if (l == r) Init(matrix[x], l);
    else {
        bld(LC), bld(RC);
        matrix[x] = mul(matrix[L], matrix[R]);
    }
}

mat que(int x, int l, int r) {
    if (ql <= l && qr >= r) return matrix[x];
    else {
        mat tt = I, rr = I;
        if (ql <= MID) tt = que(LC);
        if (qr > MID) rr = que(RC);
        return mul(tt, rr);
    }
}

int main(){
    int t, x, y, z, ca = 1;
    //freopen("E:/Code/in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
 //ios :: sync_with_stdio(false);
 RI(t);
    REP(i, N) I.a[i][i] = 1;
    while (t--) {
        RII(n, m);
        REPP(i, 1, n) RI(a[i]);
        bld(1, 1, n);
        while (m--) {
            RII(x, y);
            if (x == y) PI(a[x]);
            else if (x == y - 1) PI(a[y]);
            else {
                ql = x + 2, qr = y;
                mat re = que(1, 1, n);
                PI((a[x] * re.a[0][1] % MOD + a[x + 1] * re.a[1][1] % MOD) % MOD);
            }
        }
    }

    return 0;
}

H Power of Fibonacci
数论题,被细节坑哭了,不过这题教会了我一种新的解这种问题的方法。太强了。一直觉得自己数论还不错,现在看来弱爆了。二次剩余玩的飞起还是不会做这题,这水平不忍直视。这题是要涉及比较高深的数论知识的,即无理数在素数域内的表示。但是如果不管理解证明这个定理的话,就显得简单很多,我们利用斐波那契数列的通项公式,其中有 sqrt(5),而 sqrt(5) 在模 1e9+9 域内是可寻的,即 5 是这个模的二次剩余。于是所有 sqrt(5) 我们都可以用一个整数代替。然后利用二项式定理展开,最多 k+1 项。可以在 O(klogn) 复杂度下求出解。其中有一些细节跪哭了。交了16发吧。主要是乘以 n 不小心爆 LL 了。我曾经想先将 n 模 1e9+8,(等比数列求和,会化成一个很简单的式子,指数是n,费马小定理是可以对 n 取模 1e9+8 的),但是还有一个细节就是,等比数列求和公式的 q 不能为 1。这时候和是 n。所以如果事先将 n 取模了,这一部就会出问题。所以这两个细节还是很重要的。我还是太弱了。重点在代码中有注释突出。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <bitset>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#define dou double
#define mem(a) memset(a, 0, sizeof(a))
#define memm(a) memset(a, -1, sizeof(a))
#define LL long long
#define PB push_back
#define MP make_pair
#define PII pair<int, int>
#define FI first
#define SE second
#define RI(a) scanf("%d", &(a))
#define RII(a, b) scanf("%d%d", &(a), &(b))
#define RIII(a, b, c) scanf("%d%d%d", &(a), &(b), &(c))
#define RL(a) scanf("%lld", &(a))
#define RLL(a, b) scanf("%lld%lld", &(a), &(b))
#define RLLL(a, b, c) scanf("%lld%lld%lld", &(a), &(b), &(c)) 
#define PI(r) printf("%d\n", (r))
#define PL(r) printf("%lld\n", (r))
#define RS(s) scanf("%s", (s))
#define SL(a) strlen(a)
#define REP(i, n) for (int i = 0; i < (int) (n); ++i)
#define REPP(i, a, b) for (int i = (int) (a); i <= (int) (b); ++i)
#define FOR(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
//Segment tree
#define MID ((l + r) >> 1)
#define L (x << 1)
#define R ((x << 1) | 1)
#define LC L, l, MID
#define RC R, MID + 1, r
#define LB(x) ((x) & (-(x)))
#define M (N - 1000)
#pragma warning (disable : 4996)
//#pragma comment(linker, "/STACK:102400000,102400000")
#define EPS 1e-8
#define INF 2000000000
#define LIM (1ll << 60)
#define MOD 1000000009
#define N 111111

using namespace std;

LL n, k;
const LL K = 383008016, IK = 276601605, A = 691504013, B = 308495997, IA = 691504012;

LL qp(LL a, LL b) {
    LL re = 1;
    while (b) {
        if (b & 1) re = re * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return re;
}

LL fac[N], inv[N]; 

LL cc(LL x, LL y) {
    return fac[x] * inv[y] % MOD * inv[x - y] % MOD;
}

void Init() {
    fac[0] = 1;
    REPP(i, 1, N - 100) fac[i] = fac[i - 1] * i % MOD;
    REPP(i, 0, N - 100) inv[i] = qp(fac[i], MOD - 2);
}

LL cal() {
    LL m = qp(IK, k), q = qp(A, k), re = 0, tt = 0;
    REPP(i, 0, k) {
        if (q == 1) { //************* q == 1 不能用等比数列求和公式
         tt = n % MOD;
            tt = cc(k, i) * tt % MOD; //*************** 如果前面没取模会爆LL
         //cout << i << ' ' << tt << endl;
         if (i & 1) tt *= -1, tt %= MOD;
            re += tt;
            re %= MOD;
        }
        else {
            tt = cc(k, i) * q % MOD * (qp(q, n) - 1) % MOD * qp(q - 1, MOD - 2) % MOD;
            //cout << i << ' ' << tt << endl;
         if (i & 1) tt *= -1, tt %= MOD;
            re += tt;
            re %= MOD;
        }
        q = q * IA % MOD * B % MOD;
    }
    re *= m;
    re %= MOD;
    if (re < 0) re += MOD;
    return re;
}


int main(){
    int t, x, y, z, ca = 1;
    //freopen("E:/Code/in.txt", "r", stdin);
 //freopen("E:/Code/out.txt", "w", stdout);
 //ios :: sync_with_stdio(false);
 Init();
    RI(t);
    while (t--) {
        RLL(n, k);
        PL(cal());
    }

    return 0;
}

另外这里是一篇更详细的这题的 BLOG
我们思考一下拓展,首先下次遇见这种题目如何快速判断在模的有限域内通项中的无理数是否可循,也就是题目给的拿给特定的数字是否是模的二次剩余。考虑到这个无理数的平方一般比较小,(比如斐波那契数列是 5),那么可以利用高斯二次互反率快速判断,先判断 模是否是这个小整数的二次剩余然后利用他们的关系,判断这个小整数的二次剩余,比如下次模式是M = 1e9+7。我们做一下判断:
(5/M) * (M/5) = (-1)^[(M - 1) * (5 - 1) / 4] = 1。(这里 (x/y) 表示勒让德符号)
由于 (M/5) = (2/5),而 5 的二次剩余是 1^2 = 1,2^2 = 4,这两个,所以 2 不是 5 的二次剩余,于是 (M/5) = -1。于是 (5/M) = -1。
所以 5 不是 M 的二次剩余。可以写程序验证这一点。

表示这场比赛自己非常傻逼,前两题应该都是5分钟的水题,自己整场都在坑 B,水题 C也没去看。需要写点总结来记录一下。昨天要不是和爱酱最后7分钟交流了一下,估计 B 都出不来。绝对不是我脑子短路,是智商硬伤啊!
A
构造一个长度 n 的序列,每两个一组取 gcd,使得和为给定的 k,傻逼构造题,5分钟开始交,连 WA 两发,没考虑 n = 1 的边界情况。可预见这场的逗比正在拉开序幕。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <bitset>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#define dou double
#define mem(a) memset(a, 0, sizeof(a))
#define memm(a) memset(a, -1, sizeof(a))
#define LL long long
#define PB push_back
#define MP make_pair
#define PII pair<int, int>
#define FI first
#define SE second
#define RI(a) scanf("%d", &(a))
#define RII(a, b) scanf("%d%d", &(a), &(b))
#define RIII(a, b, c) scanf("%d%d%d", &(a), &(b), &(c))
#define RL(a) scanf("%I64d", &(a))
#define RLL(a, b) scanf("%I64d%I64d", &(a), &(b))
#define RLLL(a, b, c) scanf("%I64d%I64d%I64d", &(a), &(b), &(c)) 
#define PI(r) printf("%d\n", (r))
#define PL(r) printf("%I64d\n", (r))
#define RS(s) scanf("%s", (s))
#define SL(a) strlen(a)
#define REP(i, n) for (int i = 0; i < (int) (n); ++i)
#define REPP(i, a, b) for (int i = (int) (a); i <= (int) (b); ++i)
#define FOR(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
//Segment tree
#define MID ((l + r) >> 1)
#define L (x << 1)
#define R ((x << 1) | 1)
#define LC L, l, MID
#define RC R, MID + 1, r
#define LB(x) ((x) & (-(x)))
#define M (N - 1000)
#pragma warning (disable : 4996)
//#pragma comment(linker, "/STACK:102400000,102400000")
#define EPS 1e-8
#define INF 2000000000
#define LIM (1ll << 60)
#define MOD 1000000007
#define N 111111

using namespace std;

int n, m;

int main(){
    int t, k, x, y, z, ca = 1;
    //freopen("E:/Code/in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
 //ios :: sync_with_stdio(false);
 RII(n, k);
    if (n == 1 && k == 0) {
        puts("1");
        return 0;
    }
    else if (n == 1) {
        puts("-1");
        return 0;
    }
    if (n / 2 > k){
        puts("-1");
        return 0;
    }
    int re = (n - 2) / 2;
    x = k - re;
    printf("%d %d ", x, 2 * x);
    REP(i, n - 2) printf("%d ", i + 2 * x + 1);

    return 0;
}

B
这题绝对需要总结一下,求一个长为 j 最大值不超过 i 的序列,相邻的能整除。显然 DP。dp[i][j] 长度为 j,最大为 i 的序列的个数,如何转移呢?dp[i][j+1] 可以由 dp[x][j],x | i,转移过来。这时候有两个选择,枚举约数,那么对每个 i 会至少跑一遍 sqrt(i) 级别的时间,如果反着枚举倍数的话,就成了 log 级别的时间了,我 SB 地写了 N^3 的枚举约数,企图用前缀和优化,想了2个小时。。。足见有多 SB。这种逆向思想其实很常见,我记得某次 SRM 也有这样的题目,我也是只懂得顺着枚举,不会去想逆着枚举,但 SRM 的数据规模没有暴露我的 SB。这次终于暴露了!总结一下,这类dp:上一个状态和下一个状态之间的转移时固定的的 DP,可以在下一个状态的时候枚举是从上一个状态的那些转移过来的,这往往需要枚举每个上一层的状态,时间效率底下,题目往往告诉我们的是顺序,自然的转移关系,所以可以在上一层状态的时候直接将方案数加到下一层他可以转移的状态中去。这样时间效率是最优的,而且一般已经是时间效率上的极限。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <bitset>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#define dou double
#define mem(a) memset(a, 0, sizeof(a))
#define memm(a) memset(a, -1, sizeof(a))
#define LL long long
#define PB push_back
#define MP make_pair
#define PII pair<int, int>
#define FI first
#define SE second
#define RI(a) scanf("%d", &(a))
#define RII(a, b) scanf("%d%d", &(a), &(b))
#define RIII(a, b, c) scanf("%d%d%d", &(a), &(b), &(c))
#define RL(a) scanf("%I64d", &(a))
#define RLL(a, b) scanf("%I64d%I64d", &(a), &(b))
#define RLLL(a, b, c) scanf("%I64d%I64d%I64d", &(a), &(b), &(c)) 
#define PI(r) printf("%d\n", (r))
#define PL(r) printf("%I64d\n", (r))
#define RS(s) scanf("%s", (s))
#define SL(a) strlen(a)
#define REP(i, n) for (int i = 0; i < (int) (n); ++i)
#define REPP(i, a, b) for (int i = (int) (a); i <= (int) (b); ++i)
#define FOR(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
//Segment tree
#define MID ((l + r) >> 1)
#define L (x << 1)
#define R ((x << 1) | 1)
#define LC L, l, MID
#define RC R, MID + 1, r
#define LB(x) ((x) & (-(x)))
#define M (N - 1000)
#pragma warning (disable : 4996)
//#pragma comment(linker, "/STACK:102400000,102400000")
#define EPS 1e-8
#define INF 2000000000
#define LIM (1ll << 60)
#define MOD 1000000007
#define N 111111

using namespace std;

int n, m;
LL f[2222][2222], g[2222][2222], h[2222][2222]; //max len

int main(){
    int t, x, y, z, ca = 1;
    //freopen("E:/Code/in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
 //ios :: sync_with_stdio(false);
 RII(n, m);
    REPP(i, 1, n) f[i][1] = 1;
    REPP(j, 1, m) {
        REPP(i, 1, n) {
            REPP(k, 1, n / i) {
                f[i * k][j + 1] = (f[i * k][j + 1] + f[i][j]) % MOD;
            }
        }
    }
    LL re = 0;
    REPP(i, 1, n) re = (re + f[i][m]) % MOD;
    PL(re);

    return 0;
}

C 不难的一题,被B坑了没时间做。求逆序对的题目。归并排序。涉及到了反转操作,我们来看在有反转操作的时候逆序对有什么性质。现在有一个区间,我们把它分成左右两份,那么整个区间的逆序对可以怎么算呢?它等于左边区间的逆序对加上后边区间的逆序对,加上左右区间数字产生的逆序对。然后如果我们反转两个较短的子区间,整个区间的逆序对怎么算呢?它等于左边新的区间的逆序对(等于原区间的顺序对),右边类似,最后加上左右区间数字产生的逆序对,这一项和原来没有进行反转操作的时候是一样的。所以我们可以直接利用这点,很快求出逆序对。用两个数组存储,inv1[x]表示长度为 2^x 的所有区间,他们由左右子区间造成的逆序对的个数,inv2[x] 对称地表示顺序对的个数,那么整个区间的逆序对的个数等于所有数组元素的和,而每次更新操作,如果要求将 2^y 的子区间全部反转的话,长度大于 2^y 的区间的左右子区间产生的逆序对数不变,小于等于 2^y 的区间的左右子区产生的逆序对数变成原来顺序对数。如果再反转又变回原来的值。于是 swap 操作就可以搞定了。因此只需要写一个 merge_sort 求出所有区间的逆序对数,顺序对数。注意这里的数有相等的元素 merge_sort 的时候要注意。
这里贴一个红号写的 merge_sort,非常简洁高效。可以作为以后的模板。

vector <int> V;
LL I1[21], I2[21]; 

void Traverse(int lvl, int l, int r, vector <int> &tofill){ 
    if (lvl == 0) tofill.push_back(a[l]);
    else {
        vector <int> A, B;
        int m = l + r >> 1;
        Traverse(lvl - 1, l, m, A); Traverse(lvl - 1, m + 1, r, B);
        int i = 0, j = 0;
        while (i < A.size() || j < B.size()) {
            int mx = i < A.size() && (j == B.size() || A[i] >= B[j])? A[i]: B[j];
            int i2 = i, j2 = j;
            while (i2 < A.size() && A[i2] == mx) { tofill.push_back(mx); i2++; }
            while (j2 < B.size() && B[j2] == mx) { tofill.push_back(mx); j2++; }
            I1[lvl] += ll(i2 - i) * (B.size() - j2); I2[lvl] += ll(j2 - j) * (A.size() - i2);
            i = i2; j = j2;
        }
    }
}

//CF414C

其他代码就不贴了。很简单的实现。

总结一下最近几场TC的SRM里的很好的题目。(Topcoder里的题目总给人很灵活的感觉,看题解会发现有很多奇思妙想!)
A SRM612-Div2-1000
给定 50 个左右 2 的方幂,问这个集合的子集的和有多少种不同可能。背包显然不科学。思想看题解看来的:
考虑子集和这个数的二进制的每一位,不同的二进制表示,就代表了不同的和,所以只求不同的二进制表示有几个,一个二进制位上0 或 1 由这种大小的 2 的方幂和 比他更小的 2 的方幂的个数决定,先考虑最后一位,即 2^0 这位,如果选择一个 1,那么继续考虑其他位的时候,剩余的 1 可以作为 2(2 个当作一个), 4 (4 个当作一个)使用,等等。然后考虑其他位的时候问题忽然变得和原问题一样了,于是我们可以用递归的方式求解,每次考虑处理一位二进制位就可以了。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

#define mem(a) memset(a, 0, sizeof(a))
#define REP(i, n) for (int i = 0; i < (int) (n); ++i)
#define REPP(i, a, b) for (int i = (int) (a); i <= (int) (b); ++i)

using namespace std;

long long dp[62][62], vis[62][62];

long long dfs(vector<int> &v, int x, int y) {
    long long re = 0;
    if (vis[x][y]) return dp[x][y];
    if (y == v.size()) return 1ll;
    else {
        re += dfs(v, (x + v[y]) / 2, y + 1);
        if (x + v[y] > 0) re += dfs(v, (x + v[y] - 1) / 2, y + 1);
        vis[x][y] = 1;
        return dp[x][y] = re;
    }
}

class PowersOfTwo {
public:
    long long count(vector<long long> powers) {
        vector<int> v(62);
        REP(i, 60) v[i] = std :: count(powers.begin(), powers.end(), 1ll << i);
        return dfs(v, 0, 0);
    }
};

//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!

B SRM610-Div1-550
贪心,最优化排序的思想,白书第一章的例二就是这样的例题。哎,学的不够扎实,最基本的思想不重视,注定要吃亏。如题解所述,我们对一个给定吸纳后顺序的序列可以用动态规划,记忆话搜索递归求解。于是问题就转化成应该按什么顺序求解?答案是按 refuel 的非增顺序排序后求解。证明很简单,考虑两个任务 A,B,假设存在一个序列使得 A,B 同时被执行,那么考虑 A,B 的相对顺序,应满足什么要求呢?
如果 A 先:
F - during[A] > 0 && F - during[A] + refuel[A] > during[B]
如果 B 先:
F - during[B] > 0 && F - during[B] + refuel[B] > during[A]
前面的条件是显然的,不用讨论,因为 F 一直在递减,必然要大于两个人物的 during才可能,我们看后一个条件:
F - during[A] - during[B] > -refuel[x]
假设 refuel[A] > refuel[B] 那么按 AB 执行可行,但 BA 不一定可行,但按 BA 执行可行,能保证 AB 可行,所以我们知道最优化的排序就是按 refuel 的非递增顺序排序。(相同显然按 during非递增顺序排序)

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

#define mem(a) memset(a, 0, sizeof(a))
#define REP(i, n) for (int i = 0; i < (int) (n); ++i)
#define REPP(i, a, b) for (int i = (int) (a); i <= (int) (b); ++i)
#define SE second
#define FI first

using namespace std;

#define N 55

int dp[N][5555], n, vis[N][5555];
pair<int, int> p[N];

int dfs(int x, int y) {
    if (vis[x][y]) return dp[x][y];
    vis[x][y] = 1;
    int rr = 0, tt = 0;
    if (x >= n) return 0;
    if (y >= p[x].SE) rr = dfs(x + 1, y - p[x].SE + p[x].FI) + 1;
    tt = dfs(x + 1, y);
    return dp[x][y] = max(tt, rr);
}

class AlbertoTheAviator {
public:
    int MaximumFlights(int f, vector <int> dur, vector <int> ref) {
        n = ref.size();
        REP(i, n) p[i] = make_pair(ref[i], dur[i]);
        sort(p, p + n);
        reverse(p, p + n);
        return dfs(0, f);
    }
};

<%:testing-code%>
//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!

C SRM611-Div1-250
250都做不出来了,这题如果先做 Div2 的简单版本,那么会能很快解决,但是没有铺垫的话,我还是不会,但是一看题解就恍然大悟,TC 果然很练思维啊。由一个集合经过取所有子集的集合内元素的 LCM 可以得到一个新集合,判断 两个集合的新集合是否相等。结论就是 A B 的新集合相等等价于 A,B 的每个元素可以表示成另一个集合里的某些数的 LCM。这需要用到两个很简单的 LCM 的性质:
LCM(x,y,y) = LCM(x,y), LCM(LCM(x,y),z) = LCM(x,y,z)
这是显然的,但是在这里很有用,证明:
如果 A,B 每个元素可以表示成另一个集合里一些元素的 LCM,那么考虑 A 的任意子集,它有以下来自 A 的元素 ai,...,aj,且 ai 能表示成 bi1,...,bix 的 LCM,所以
LCM(ai,...,aj) = LCM(LCM(bi1,...,bix),...,LCM(bj1,...,bjy)) = LCM(bk1,...,bkz)= B 某个子集的 LCM
充分性,我们用反证法来证,设 A,B 的新集合相等,但 A 中某个元素不能表示成 B 中某些元素的 LCM,那么,我们取 A 的子集 为这个元素组成的单元素子集,它的 LCM 就是这个数本身,他在 A 的新集合中,但它不能表示成 B 新集合里面的元素,这与假设矛盾,证毕。
于是我们只需要判断 A,B 里面每个元素是否可以表示成另一个集合里的某些元素的 LCM。如何判断呢?对一个元素 X,我们可以把每个来自另一个集合的且是 X 的约数的数保存起来,然后判断这些数的 LCM 是否等于 X。(比如,12 属于 A,B 中只有 2,3 能整除 12, 那么 12 不能被表示)。(这个性质的证明是显然的,就不证明了)

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

#define mem(a) memset(a, 0, sizeof(a))
#define REP(i, n) for (int i = 0; i < (int) (n); ++i)
#define REPP(i, a, b) for (int i = (int) (a); i <= (int) (b); ++i)
#define FOR(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define N 111111

using namespace std;

class LCMSet {
public:
    string equal(vector <int>, vector <int>);
};

int gcd(int x, int y) {return y ? gcd(y, x % y) : x;}
int lcm(int x, int y) {return (1ll * x * y / gcd(x, y));}

bool go(int x, vector<int> A){
    int lm = 1;
    REP(i, A.size()){
        if (gcd(x, A[i]) == A[i]) lm = lcm(lm, A[i]); 
    }
    return x == lm;
}

string LCMSet::equal(vector <int> A, vector <int> B) {
    int i, j, k, fl = 0, re = 0;
    REP(i, A.size()) if (!go(A[i], B)) return "Not equal";
    REP(i, B.size()) if (!go(B[i], A)) return "Not equal";
    return "Equal";
}

D

多整几个专题,慢慢刷好题。
这里收录了一些最近做的有难度的线段树题目,很多用的离线算法。
A HDU3333
区间去重和,比较神的离线算法。去重求和,去重求异或等你可以想到的一些有比较好性质的运算的去重询问应该都可以这么搞。对询问区间按右端点排序,然后用线段树或者树状数组维护,最重要的技巧就是,对于相同的元素,要不断向右更新它所在的位置。举个例子 2 3 4 3 5,如果用线段树维护的话,第一次遇到 3 线段的位置 2 处值加 3。第二次遇到 3 的时候,先位置 2 处减 3 然后位置 4 处加 3。然后对每个区间用下区间和查询,或者前缀和(树状数组)即可。
代码
B CF396C
一类树上的奇葩操作的线段树,先 dfs 时间戳转化成线段树,然后这种操作多和节点深度有关,可以利用这点让每次修改时区间修改,最后是点询问,所以记两个值,最后用和深度有关的线性函数来得解,需要 lazy 标记。
代码
C CF311D
比较奇葩的区间操作,x 变成 x^3,询问区间和 MOD 95542721,注意这个数很特殊,有循环节,然后就和正常区间修改一样了。每个节点把所有48中循环节的信息保存下来。
代码
D CC ANUGCD
完全暴力的线段树,但是需要分析才敢大胆暴力!如何暴力呢?对每个数因式分解,保存所有在数列中出现的质数,对每个保存了的质数用一个 vector pos[i] 保存所有有这个质因子p[i] 的 a[x] 的位置,然后以这个pos[i]的元素为一段线段建线段树。我们来分析空间和时间复杂度:a[x] 的数据大小和数量大小都是 100000,一个数的质因子 >= 2,所以因子个数是 logN 级别的,所以最多保存了 NlogN个质因子,然后考虑每棵线段树的的空间,假设 pos[i].size() = y,那么要 4y 的空间,注意到所有 pos[i].size() 的和 = 每个 a[x] 的不同质因子数的总和,所以 y 的和是 NlogN。所以空间是 O(NlogN),时间就是 O(NlogNlogN) 吧。反正应该不会超时。所以时间空间对于这种暴力做法都够用。写吧。话说第一次用 vector 写线段树,然后还一些小细节呢。
代码

一直理解不能的一题(ZOJ1100),今天终于AC了,于是感觉最近可以刷一刷状压DP了,不断更新做过的好题吧。
以下是题目:(主要参考自周伟的论文)
A ZOJ1100
经典问题,状压入门题,一直不会做,一直没入门,今天会了,算入门了吧?
dp(i, j) 表示前 i 行放满,第 i+1 行状态为 j 的方案数,那么我们考虑如何递推。直接一行状态转移到另一行的状态,我们需要判断这个状态是否可以转移到另一个状态,这个过程我用 dfs 来完成。设 pre 是这行最原始的状态,now 是填充过程中当前的状态,next 是当前行填充过程造成的下一行的状态。于是当前行填满了,dp(i, next) 可以加上 dp(i-1, pre)。填充过程中,有两种可能竖放,或者横放。
代码
B SGU131
好吧这题和上面这题完全类似,只是多了几种情况,仔细讨论一下就可以了,基本不用改代码。
代码