天国的浣熊群水群精华

chat.txt

POJ3222.txt
misaka.99999:  11:20:53
题目等价于给边定向，使得每个点的度都是偶数。既然如此，如果一个连通分量有奇数条边，那么总点度 = 边数 = 奇数，就无解。否则，求出连通分量的一颗生成树，对于非树边随意定向。现在相当于要给树边定向，使得点度是奇数（或偶数，取决于非树边随意定向的结果）。在生成树上dfs构造，对于每个点u，考虑它父亲p到它的边(p, u)，根据下面定向的结果，我总能定向(p, u)使得点u满足。只剩下根，因为总点度是个偶数，所以根是天然满足的。证毕。

SPOJ_PGCD.txt
:  08:51:10
问一下spoj4491的miu函数到底怎么构造？
:  08:56:25
4491是什么？
:  08:56:37
求题目链接
  History Above  
:  08:58:22
就是那个莫比乌斯反演的
http://www.spoj.com/problems/PGCD/
:  08:59:25
这题O(N log N)不能过是吧？
:  08:59:58
有个做法不用枚举质数p
:  09:00:17
要重新构造miu函数
:  09:00:24
没看懂题解
:  09:01:35
不要用miu这个表达吧。。miu(d)一般就指那个函数
:  09:01:42
我们其实就是要算k(n)
:  09:01:55
假设n = p_1^e_1 p_2^e_2 ... p_m e^m
:  09:02:06
k(n) = sum { miu(n / p_i) }
:  09:02:09
我没弄错吧？
:  09:03:24
什么意思？
:  09:03:35
那结果是什么？
:  09:03:49
sum_i k(i) * [n / i] * [m / i]
:  09:04:19
就是。。。从容斥考虑吧
:  09:04:38
先算g(d)，表示gcd是d的倍数的pair数量，就是[n / i] * [m / i]
:  09:05:04
再算f(d) = sum_i miu(i) * g(d * i)，表示gcd恰好是d的pair数量
:  09:05:17
最后for 所有质数p，累加f(p)就是答案
:  09:05:25
这是最原始的形式，对吧？
:  09:06:23
对
:  09:06:39
那你看。。从g -> f，是个线性的形式吧
:  09:06:55
反正最后的答案，一定可以写作sum_i k(i) * g(i)的形式。。
:  09:06:57
怎么才能不枚举p？
:  09:07:01
关键就是要把k()的系数算出来
:  09:07:13
到这里。。k的问题说清楚了吗？
:  09:07:16
下面说怎么算。。
:  09:07:25
:  09:01:55
假设n = p_1^e_1 p_2^e_2 ... p_m e^m
:  09:02:06
k(n) = sum { miu(n / p_i) }
:  09:07:39
如果e_1 = e_2 = ... e_m = 1
:  09:07:48
那么答案就是m * (-1)^{m - 1}
:  09:08:25
如果有某个e_i > 1，假设e_1 > 1
:  09:08:46
那么啥。。那么答案就是miu(n / p_1)

cf_202.txt
misaka.99999:  01:31:05
DAG上有4个点a, b, c, d
misaka.99999:  01:31:15
a -> c, b -> d的方案数
misaka.99999:  01:31:26
等于c(a, c) * c(b, d) - c(a, d) * c(b, c)
misaka.99999:  01:31:32
c(x, y)表示x -> y的方案数。
misaka.99999:  01:32:00
感觉很好理解。。就是你a -> d, b -> c总要相交的嘛。。在相交的地方翻过来就是了
Nocturne:  01:32:01
C按集合大小是否>=sqrt(n)分类
黄宇扬:  01:32:02
我觉得是>=sqrt(n)的块和<sqrt(n)的块分开处理
misaka.99999:  01:34:08
称>= sqrt{N}的是大集合，< sqrt{N}的是小集合
misaka.99999:  01:34:21
首先预处理出intersection[big][all]
misaka.99999:  01:34:29
表示某个大集合和某个集合的交大大小
misaka.99999:  01:34:42
有了这个，每次更新集合的时候，可以暴力算对每个大集合的贡献
misaka.99999:  01:35:11
所以只有回答小集合的时候有困难，贡献有2个部分：
misaka.99999:  01:35:30
小集合 => 小集合。。这个每次update小集合。。把更新拉到每个元素上，每次暴力重新算
misaka.99999:  01:35:40
大集合 => 小集合。。for每个大集合，用intersection算。

cf_210.txt
 ftiasch   10:45:20
假设我们需要判断，A -> C, B -> C，是否存在一种方案是的A比B［严格先到］。
 ftiasch   10:45:38
如果这种方案存在，那么我们让A晚0.5秒出发，也是存在的。
 ftiasch   10:46:27
那我们现在从A, B同时开始跑最短路，dis[A] = 0.5, dis[B] = 0
 ftiasch   10:47:36
对于某个点x，如果dis[x] = ?.5，也就是说这是A先到的，那么对于x出去的边，肯定是设为lower[e]最好，因为就算B来x，A也可以通过模仿它不至于输掉
 ftiasch   10:47:42
= ?.0的同理

changsha-online.txt
misaka.99999:  20:52:45
变成求x^n + y^n，然后满足x + y = a, x * y = b这样。
misaka.99999:  20:53:17
然后x^{n + 2} + y^{n + 2} = (x + y) * (x^{n + 1} + y^{n + 1}) + (x * y) * (x^{n - 1} + y^{n - 1})
misaka.99999:  20:53:34
那么令f(n) = x^n + y^n，f(n)是2阶线性递推，可以矩阵乘法
Ran:  20:53:43
woooo...
misaka.99999:  20:54:03
我好像符号写错了，
misaka.99999:  20:53:17
然后x^{n + 2} + y^{n + 2} = (x + y) * (x^{n + 1} + y^{n + 1}) - (x * y) * (x^{n - 1} + y^{n - 1})


chengdu-online.txt
misaka.99999(826513189)  21:42:11
05：考虑序列(x_1, x_2, ..., x_m)，满足x_1 + x_2 + ... + x_m = n，且x_1, x_2, ..., x_m <= k
misaka.99999(826513189)  21:42:29
设f(d)表示，满足以上条件，而且循环节是d的序列数量
misaka.99999(826513189)  21:42:59
先求g(d)，表示循环节是d的约数的序列数量，之后可以莫比乌斯反演出f
misaka.99999(826513189)  21:43:24
答案就是sum { f(d) * n / d }


chengdu-onsite.txt
 ftiasch :  09:16:27
F：给一个无向图，有黑白两色，问是否存在一颗生成树，黑边的数量是一个fib数，边 <= 10^5

J：统计有多少个a <= x <= b, c <= y <= d，使得(x + y) mod m == p
 ftiasch :  09:43:03
a, b, c, d, m, p <= 10^9，输出分数

 ftiasch :  09:44:20
大体思路是算出x mod m == i的x有多少个，y也类似，然后就可以做了


fft_linear_recur.txt
mike_nzk  14:04:06
先把除数调到>=被除数位数/2
mike_nzk  14:04:37
然后求10^2n/除数，其中n是除数位数
mike_nzk  14:06:27
这步用牛顿迭代，大概yy一下，ax=1=>1/x-a=0，得牛顿迭代式x’=ax^2-x
mike_nzk  14:06:39
然后搞一下搞出来
 ftiasch   14:06:58
“这步”是指10^{2n} / 除数？
mike_nzk  14:06:57
然后用这个数*被除数/10^2n
mike_nzk  14:07:04
调整一下误差
mike_nzk  14:07:12
对
 ftiasch   14:07:25
调整误差是说？
mike_nzk  14:08:05
就是这里面会有一些误差 = =|| 要算余数调整
 ftiasch   14:08:29
哪里用到了FFT吗？
mike_nzk  14:08:45
牛顿迭代也是，从1位精度开始迭代的时候每一步迭代都要调整误差
mike_nzk  14:09:10
牛顿迭代要乘法，最后乘逆元也要
mike_nzk  14:09:50
总之巨麻烦。。。
mike_nzk  14:11:52
对的
mike_nzk  14:12:29
不过最近听说线性齐次递推式可以转变成高精度除法？
mike_nzk  14:13:03
然后获得tlogtlogn的复杂度？其中t是递推式阶数
 ftiasch   14:13:16
噢，是的呀。
 ftiasch   14:13:24
=-= 我一直不会做高精度除法。
 ftiasch   14:13:36
所以我只会O(t^2 log n)的。
mike_nzk  14:13:48
怎么做的 = =
 ftiasch   14:14:52
大概，假设是f[n] = sum b[k] * f[n - k]这个递推。
 ftiasch   14:15:08
普通做法的话，最后就是要算A^n。
 ftiasch   14:15:40
你可以聪明地发现，A^t = sum b[k] * A^{t - k}
 ftiasch   14:15:58
总之，可以把任意A^n用A^0, A^1, ..., A^{t - 1}线性表示。
 ftiasch   14:16:16
然后你考虑知道A^n和A^m的线性表示，你想得到A^{n + m}的线性表示。
 ftiasch   14:16:27
实际上就是两个多项式相乘，再mod掉一个多项式。
 ftiasch   14:16:38
mod是为了把超过t次的降回来。


nanjing_F.cpp
teach me plz~~
 ftiasch   17:59:58
我想想。
 ftiasch   18:00:18
你要知道，费用流不断增广，每条增广路的费用是越来越大的。
 ftiasch   18:00:40
然后我们就能算出cost[f]，表示增广f的流量，增广路的最大费用。
 ftiasch   18:00:56
然后我们二分一个答案deadline，表示大家要在deadline之前全部到达。
 ftiasch   18:01:13
我们要注意到，第i天出发的人，和第i + 1天是不互相影响的。
 ftiasch   18:01:31
那么第0天，肯定是要找一个最大的f，使得cost[f] <= deadline。
 ftiasch   18:01:41
第k天，就是找最大的f，使得cost[f] + k <= deadline。
 ftiasch   18:01:52
把所有这样的f加起来，看看够不够要求的F就行了。
???  18:03:01
是不同天出发的人互不影响？
 ftiasch   18:03:41
对。
 ftiasch   18:03:53
你能感受到嘛。对于一条路径p。
 ftiasch   18:04:06
我先走这条路径的人，总是比它先一点，是不会冲突的。
???  18:04:46
大概就是这里没想到~~
 ftiasch   18:05:40
这整个算法要说清楚挺麻烦的。
 ftiasch   18:05:45
有很多很显然的结论要说明。
 ftiasch   18:05:51
但是总之就是对的~
???  18:12:50
但是要求的F是1e9的？

第k天的k是for的吗？
 ftiasch   18:13:56
不是。
 ftiasch   18:14:03
这个题有个好处。
 ftiasch   18:14:05
f不是很大。
 ftiasch   18:14:07
你可以for f
 ftiasch   18:14:12
一段一段地算k。
???  18:15:12
f不大是这题的固有属性？
 ftiasch   18:15:57
你感受一下。
 ftiasch   18:16:00
肯定f不能太大。
 ftiasch   18:16:18
毕竟（大家会的）费用流都是f * 增广复杂度的。
???  18:17:11
大概感受到了
???  18:24:31
不知道是不是我理解的不对
???  18:24:38
那个不同天出发的人不会冲突
???  18:25:08
比如第0天A走了长度为3的路径
第1天B走了长度为2的路径
最后一条边相同，还是会冲突的吧
 ftiasch   18:28:13
不，是对同一条路径说的。
 ftiasch   18:28:26
你这两条路径。在网络流里面本来就是两条路径了。
???  18:29:19
那，我应该还没弄懂，再想一想~~


nanjing_G.cpp
#include<iostream>
#include<fstream>
#include<sstream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<cstring>
using namespace std;

#define FOR(I,A,B) for (int I=int(A);I<int(B);++I)
#define MEM(A,B) memset(A,B,sizeof(A))
#define CPY(A,B) memcpy(A,B,sizeof(B))
#define FIN(A) freopen(A, "r", stdin)
#define FOUT(A) freopen(A, "w", stdout)
typedef long long LL;
const int N(8);
int bitCnt[1 << N]; //统计二进制有多少个1
int put[N + 1][1 << N]; //预处理出每个状态的放置情况
int a[N], b[N], c[N], d[N];
vector<int> vec[N + 1][1 << N];
bool bit(int x, int y) {
    return x >> y & 1;
}
void deal(int n, int *a, int *b) { //从第1行开始处理棋盘，b为方案
    FOR(i, 0, n - 1) {
        b[i + 1] = a[i];
        a[i + 1] ^= put[n][a[i]];
        if (i < n - 2) a[i + 2] ^= a[i];
        a[i] = 0;
    }
}
void init() { //预处理过程
    FOR(i, 0, 1 << N)
        bitCnt[i] = bitCnt[i / 2] + i % 2;
    FOR(i, 1, N + 1) 
        FOR(j, 0, 1 << i)
            FOR(k, 0, i) {
                bool flag = false;
                if (k && bit(j, k - 1)) flag ^= true;
                if (bit(j, k)) flag ^= true;
                if (k < i - 1 && bit(j, k + 1)) flag ^= true;
                if (flag) put[i][j] |= 1 << k;
            }
    FOR(i, 1, N + 1) 
        FOR(j, 0, 1 << i) {
            FOR(k, 0, 1 << i) {
                MEM(a, 0);
                a[1] = b[0] = k;
                a[0] = j ^ put[i][k];
                deal(i, a, b);
                if (a[i - 1] == 0) vec[i][j].push_back(k);
            }
            //printf("State(%d, %d) = %d\n", i, j, vec[i][j].size());
        }
}
int main() {    
    int n, ca;
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    init();
    scanf("%d", &ca);
    FOR(C, 1, ca + 1) {
        scanf("%d", &n);
        FOR(i, 0, n)
            scanf("%d", &a[i]);
        int s = 0;
        b[0] = 0;
        deal(n, a, b);
        int ans = -1;
        reverse(a, a + n);
        reverse(b, b + n);
        FOR(i, 0, vec[n][a[0]].size()) {
            d[0] = vec[n][a[0]][i];
            c[0] = a[0] ^ put[n][d[0]];
            c[1] = d[0];
            deal(n, c, d);
            int tmp = 0;
            FOR(j, 0, n)
                tmp += bitCnt[b[j] ^ d[j]];
            if (ans == -1 || ans > tmp) ans = tmp;
        }
        printf("%d\n", ans);
    }
    return 0;
}


papers.txt
???  21:14:24
叉姐……1d1d决策单调性，有办法做到nlogn更好么，有办法不写栈么
???  21:14:39
总感觉应该是有优化空间的
 ftiasch   21:14:49
有。
 ftiasch   21:14:54
总能做到线性的。
 ftiasch   21:15:00
也有论文。:(
???  21:15:13
又是论文:(
 ftiasch   21:15:33
我不太记得名字了。
 ftiasch   21:15:47
要用到某个5个字母的算法。
???  21:16:06
好吧……
???  21:16:20
决策单调性英文改怎么说
 ftiasch   21:16:20
你想看么。
 ftiasch   21:16:25
我帮你找找好了。
???  21:16:26
我去搜下
???  21:16:30
感兴趣
???  21:16:33
好，谢啦
 ftiasch   21:18:17
这个有2个case
 ftiasch   21:18:26
concave的简单一些。
 ftiasch   21:18:29
能做到线性。
 ftiasch   21:18:37
另一个似乎只能做到O(\alpha n)。
 ftiasch   21:18:49
我当时似乎没有搜到这篇论文。
???  21:19:42
好，谢啦
 ftiasch   21:20:04
看懂了讲ACM队大讲坛吧。
???  21:20:29
好……我努力
 ftiasch   21:20:52
不是太难懂。。
 ftiasch   21:20:59
就是看完就忘记罢了。
???  21:21:18
感觉搞OI的时候没人提过这个东西
 ftiasch   21:21:21
我记得是有个毛子题要用这个算法。
???  21:21:22
都说nlogn的做法
 ftiasch   21:21:30
当时Mithril训练的时候做过。
???  21:21:37
当时也没想过能不能做的更好
 ftiasch   21:21:41
最后硬抠常数过了。
???  21:21:48
好吧……
 ftiasch   21:22:02
这是89年的paper啊。
 ftiasch   21:22:12
这种算法在我出生之前几年就被玩坏了。
???  21:22:18
感觉dp的论文好像都比较早
 ftiasch   21:22:51
我感觉有趣的算法都出生在80年代。:(
 ftiasch   21:22:58
现在都不做这些了。
???  21:23:10
你平时都怎么接触到这些论文的
???  21:23:13
感兴趣
???  21:23:47
以及这个东西该怎么搜呢……
 ftiasch   21:23:55
猜。
 ftiasch   21:24:03
http://cstheory.stackexchange.com/
 ftiasch   21:24:08
像这种网站，多上上。
 ftiasch   21:24:17
我看论文喜欢把reference bfs一遍。
???  21:24:29
喔……好
???  21:24:33
涨姿势了
 ftiasch   21:25:01
http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki
 ftiasch   21:25:03
这篇文章不错。
 ftiasch   21:25:09
你这种数据结构爱好者不容错过。
???  21:25:44
诶，听名字好有趣
 ftiasch   21:26:10
why I won't study theory any more? 
 ftiasch   21:26:26
since all interesting things have been discovered.
???  21:27:00
…………
???  21:27:11
好凄凉
 ftiasch   21:27:42
http://courses.csail.mit.edu/6.851/spring12/lectures/
 ftiasch   21:27:47
我猜你也没看过这个。
 ftiasch   21:27:53
也可以看一看。
???  21:28:13
这个是论文归类么
 ftiasch   21:28:18
不是，一个课。
???  21:28:37
什么大学的……
???  21:28:41
mit
???  21:28:42
……
 ftiasch   21:28:45
你可以学会传说中O(1)插入删除，O(1)询问前后关系的链表。
???  21:28:47
是厉害啊
 ftiasch   21:28:57
Erik Demaine很牛的，20岁就拿到PhD了。
 ftiasch   21:29:13
16岁开始念PhD，念了4年。
???  21:29:18
…………
 ftiasch   21:29:21
大概是MIT现在最年轻的教授吧。
 ftiasch   21:29:37
他有个学生，叫mihai。
 ftiasch   21:29:42
可惜得脑癌死了。
 ftiasch   21:29:52
mihai一年能发4偏FOCS？
???  21:29:52
听起来不像美国人？
 ftiasch   21:30:04
mihai不知道哪里人，大概是欧洲哪个地方的。
 ftiasch   21:30:18
你得知道，Warsaw U理论这么牛的地方。
 ftiasch   21:30:27
一年加起来也只有3篇。
 ftiasch   21:30:30
他们还非常高兴。
???  21:30:42
不不，我对这些论文的各个回忆什么的完全不清楚
???  21:30:51
诶，你什么时候写的论文
 ftiasch   21:31:01
我？
 ftiasch   21:31:04
我不打算写。
???  21:31:08
喔……
???  21:31:10
爷……
???  21:31:15
人称带错了
 ftiasch   21:31:48
http://corner.mimuw.edu.pl/
 ftiasch   21:31:53
这个blog也挺有趣的。
???  21:31:58
唉……有这么叼的人搞科研了……我继续掺和感觉好蛋疼啊

朱指导谈比赛策略.txt
wuyiqi:  00:18:34
求教应付区域赛该怎么练
御坂#???:  00:18:53
吃什么补什么。。。
wuyiqi:  00:19:07
比赛or专题，it's a question
朱指导:  00:19:16
把上海赛区11和上海赛区09先做一次
朱指导:  00:19:23
然后把10杭州 福州
朱指导:  00:19:26
11北京 福州
朱指导:  00:19:30
12杭州 金华做一次
朱指导:  00:19:43
然后把10成都 11大连 12长春做一次
御坂#???:  00:19:53
嗯= =
朱指导:  00:19:57
我应该没记错吧。。
御坂#???:  00:20:01
果然就是吃什么补什么。。
朱指导:  00:20:12
复旦/北大/浙大
Sd.无心插柳:  00:20:18
..这些好像。。都是复旦北大的题
朱指导:  00:20:24
至于上交和中大怎么准备，我不会
wuyiqi:  00:20:26
百题大战
御坂#???:  00:20:29
不。。他说得对。。
御坂#???:  00:20:37
不。。确实吃什么补什么。。
朱指导:  00:20:36
中大可以在hust搜SYSU
朱指导:  00:20:43
估计可能有效
御坂#???:  00:20:50
准备regional。。就做什么regional呗。。。
朱指导:  00:20:50
SJTU听天由命吧
Sd.无心插柳:  00:20:58
前几年的题从来没特意做过。。。
wuyiqi:  00:20:58
- -
朱指导:  00:21:05
能准备就这些，别的都是硬实力
wuyiqi:  00:21:17
谢谢
御坂#???:  00:21:58
你看。。。复旦大学教练倾情指导= =
御坂#???:  00:22:01
多么靠谱。。。
朱指导:  00:23:26
还是提高实力为主。。。。
朱指导:  00:23:42
还有个，就是手不能生，赛场上码速一定要快
朱指导:  00:23:45
准。。。
朱指导:  00:24:01
然后就是huanglei的指导思想什么的，糙快猛
御坂#???:  00:24:16
我觉得一般选手。。。很难有正确率的
御坂#???:  00:24:20
有个代码查不出就完蛋了。。。
叉姐粉丝团团长:  00:24:28
仰慕高端选手叉姐
wuyiqi:  00:24:33
赞
主代码手:  00:24:37
我就是一般选手
ForeverBell:  00:24:44
我就是一般选手
朱指导:  00:24:46
查不出扔掉。。。
ForeverBell:  00:24:54
哎。。
Sd.无心插柳:  00:24:54
场上debug一般都是打印下来往死里看吗..
ForeverBell:  00:25:00
查不出我就偏要搞。。
ForeverBell:  00:25:09
然后就开始意识模糊
朱指导:  00:25:16
然后就够了。。。
朱指导:  00:25:19
过了
朱指导:  00:25:25
或者，这题肯定数据错了
朱指导:  00:25:28
数据果然错了。。
主代码手:  00:25:50
真查30min查不出来就直接丢题啊>-<
朱指导:  00:26:16
赛场经验。。。
朱指导:  00:26:22
例如，题目一定要大家都看过
朱指导:  00:26:29
实在不行也至少要有2个人看过。。
朱指导:  00:26:39
不是大瓜题，上去做之前先跟队友讨论一下
朱指导:  00:26:54
开张表记录一下哪个题有谁看过
朱指导:  00:26:57
题意大致是什么
朱指导:  00:27:00
谁在负责
wuyiqi:  00:27:01
一般都是两个人看过。
御坂#???:  00:27:05
日。。。团长。。。不都你查的么？
朱指导:  00:27:12
妈蛋这些我在自己学校都没说完整过 = =

好棒

为什么不是水群精华

赞~(≧▽≦)/~