Lflame

THUSC 总结

    2016 年 6 月 4 日早上,我们坐飞机去了北京。令人高兴的是 zxr 和 lk 也来了。

    过去之后有些疲倦,睡了一会。中午吃完饭就很迟了,颓了一会 CS 也就差不多去吃了晚饭。晚上林老和家长们带我们走路到清华,说是要熟悉一下路,硬生生走了两个小时 23333。最后还是坐车回的宾馆,复习了一会模板就睡觉了。

    

    6 月 5 日早上,坐大巴车去了清华。早上是试机,惊奇地发现那虚拟机烂得简直可以。而且好像就是因为这个,下午让我们先到会议室休息,延迟了一个半小时才开始的...

    其实还是有点紧张....

    15:30  :考试开始,读题。第一题...看起来像是 DP?好像想一想可以想出来的样子...不过暴力分确实很 easy。瞄了一眼第三题,果然是提交答案题。

    15 : 50  : 算了还是先放一放,看第二题。诶?这道题看起来可做?二分加历史最大值乱搞搞?暴力分貌似可以做到 70 分。

    16 : 20  : 啊啊啊....不对劲啊....再想一想,这道题看起来没有那么复杂...还是想想正解更靠谱。串长小于 60 感觉会有用 ? 啊...还是先把 Trie 树敲了吧,准备建虚树后乱搞。

    16 : 50  : 突然发现算法有问题,还好还暂时没有敲虚树。

    17 : 00  : 有些困...出去洗了一把脸...感觉大家都在写代码的样子,应该是题目很水 ?

    17 : 10  : 噢天,为什么想那么复杂....这不是傻逼题??

    18 : 00  : 终于过了对拍...手速还是太慢....感觉好方啊,看榜上都有人三道题都交了,虽然不知道他们是不是正解。

    18 : 40  : 感觉已经没有时间去思考第一题了,写完了可以拿 60 分的三个暴力,随手试了试几个数据,貌似靠谱,没时间拍了,去看提答吧。

    20 : 30  : 第三题搞了大概 40 分,乱搞能力还有待提高...就这样结束考试了。

    出考场发现我这个应该只能算平均水平 ? 233333 算啦,拿不到无条件降一本也没有关系。

    晚上一起去吃了烧烤,考完果然就轻松多了。听说 ljl 过来清华找了我?maya 可是我已经坐车走了呀...走了呀...了呀... 2333这锅只能背...

    虽然第二天还要面试,依然睡得很迟。


    6 月 6 日,早上吃饭的时候听说七中考得不好,胡老也在一直给我说我的问题。然而紧张地等电话的时候,果然打过来了一个!进面试了!

    面试之前比昨天考试还要紧张....一边回忆自己的自我介绍,一边紧张地等我的名字被念到...

    听说是按名字倒序...很快就念到我了。

    进去之前感觉要好一些了,毕竟还是有准备的。里面是五个老师,有一个女老师。

    敬礼,递资料,自我介绍。感觉自我介绍有那么一点点怕忘词,哈哈 ~

    然后就是问问题了,被问到了几个很 easy 的问题,大都很迅速地回答了。感觉面试很棒?没有一点点紧张了,反而感觉很自然,老师们说话也很亲切。

    回答完问题,说可以了。于是起身敬礼,拿了资料走了出去。

    出来看到 tyh 真的没有进面试..还是挺可惜的..不过 NOI 还有机会。

    下午就在等签约了,由于奖项是倒着念的,还是有些紧张....三等奖念完了 !诶 ? 没有我 ! 最后的总排名感觉还可以,拿到了二等奖,无条件降 60,NOI 前 100 降一本。

    晚上就依然是开心的狼人杀,上海的大爷们也来啦。


    6 月 7 日,我获得了参加部分获奖选手交流的资格,坐车去清华。早上是讲题 23333,说到第二题就想说一下出题人,时间不卡 n*log^2 的就算了,空间还开 1 G,岂不是怎么做怎么过。下午是奇怪的交流,玩得还挺开心的。

    晚上,坐飞机回成都。这次 zxr 和 lk 就真的完全退役了,或许我也不远了。

    NOI 加油。

    

【2016/5/25 考题】toll 简洁巧妙的网络流

    题意: N 个点,M 条边的有向图,在每条边 (ui,vi) 上建立收费站需要花费 ci,问要使得从 1 号点到 N 号点的任意一条路径都经过且只经过一个收费站,所需要的最小代价。    (N<=100 , M<=2500)


    如果题目不要求只经过一个收费站,那么就是裸的最小割,跑一遍 Dinic 即可。

    但是现在题目要求只能经过一个,应该怎么办呢?

    考虑跑最小割时什么情况下会出现一条路径经过两个收费站。


    如图,1 为 源点 S,汇点 T 未画出。选择的 (2,3) 和 (4,5),这样便会不合法。

    我们来考虑如何避免这样的情况,即对于一条边 (u,v),避免通过同时割掉 S 到 u 路径上和 v 到 T 路径上的各一条边。

    注意到,如果连了一条容量无穷的边(a,b),说明 S 到 a 或者 b 到 T 至少有一边会被割掉。于是我们有了一个想法,对于原图的边 (u,v),连一条 (v,u),容量为正无穷,即 S 到 v 或者 u 到 T至少有一边会被割掉。由于是最小割,S 到 p 和 p 到 T 不会同时被割掉,于是若我们割了 S 到 v 则不会割 v 到 T,若割了 u 到 T 则不会割 S 到 u。也就是说,现在就一定满足限制了。


    所以概括来说,建原图的边(u,v),容量为 ci;以及一条反向的边 (v,u),容量为正无穷。跑最大流即可。构图实际上很简单,但是需要对网络流有较为深刻的理解,而这道题也不失为一道好题。


 代码:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;


long long INF=(1ll<<60)-1 , cap[10005] ;

int first[10005] , nexts[10005] , to[10005] , egnum=1 , cur[10005] , que[10005] , head , tail , d[10005] ;

int n,m ;


void add_edge(int a,int b,long long c){

nexts[++egnum]=first[a] , first[a]=egnum , to[egnum]=b , cap[egnum]=c ;

nexts[++egnum]=first[b] , first[b]=egnum , to[egnum]=a , cap[egnum]=0 ;

}


bool BFS(){

memset(d,0,sizeof(int)*(n+15)) ;

d[1]=1 , head=tail=0 ;

que[tail++]=1 ;

while(head<tail){

int a=que[head++] ;

for(int i=first[a];i;i=nexts[i]){

if(cap[i] && !d[to[i]])d[to[i]]=d[a]+1 , que[tail++]=to[i] ;

}

}

return d[n] ;

}


long long DFS(int a,long long flow){

if(!flow || a==n)return flow ;

int &i=cur[a] ;

if(i==-1)i=first[a] ;

long long ret=0 ;

for(;i;i=nexts[i]){

int b=to[i] ;

if(!cap[i] || d[b]!=d[a]+1)continue ;

long long t=DFS(b,min(flow,cap[i])) ;

cap[i]-=t , cap[i^1]+=t , flow-=t , ret+=t ;

if(!flow)break ;

}

return ret;

}


long long Dinic(){

long long ret=0 ;

while(BFS()){

memset(cur,-1,sizeof(int)*(n+15)) ;

ret+=DFS(1,INF) ;

if(ret>=INF){ ret=-1 ; break ; }

}

return ret;

}


int main(){

freopen("toll.in","r",stdin) ;

freopen("toll.out","w",stdout) ;

scanf("%d%d",&n,&m) ;

for(int i=1;i<=m;++i){

int a,b,c;

scanf("%d%d%d",&a,&b,&c) , add_edge(a,b,c) , add_edge(b,a,INF) ;

}

long long ans=Dinic() ;

printf("%lld\n",ans) ;

return 0 ;

}


支配树 !!!

     这是今天小白讲的内容,于是晚上用支配树过了一道裸题(hdu4694)。

    这里大概梳理一下。

    我们有一个有向图,可以有环,然后给定一个起点 s 。

    定义一个点 u 的支配集为 s 到 u 的每一条路径经过的点的交集,即 s 到 u 必经的点集。不过为了方便,以下讨论中点 u 的支配集均不包含 u 本身。

    定义点 u 的支配点为点 u 的支配集中,离 u 最“近”的点,也就是说删掉点 u 的支配点过后,s 仍然可以到达 u 的支配集中别的点。

    我们的目标就是要求出每个点的支配点。

    dfn表示时间戳。首先这里有一个性质, DFS 有向图过后,若 dfn[u] < dfn[v],且 u到 v 有边,  那么在 DFS 树中 u 一定是 v 的祖先。 原因是有向图的 DFS 树中不存在从 dfn 小的点到 dfn 大的点的横叉边。

    对于点 u,所有能够通过一些点 i 满足 dfn[i] > dfn[u] (不包括起点和终点)到达点 u 的点中, dfn 值最小的点为点 u 的半支配点(semi) 。即可以不经过点 u 的祖先到达点 u 的点中,dfn 最小的点。注意这个点一定是点 u 的祖先,这也是很容易就可以证明的。

 

    半支配点看起来很像支配点,但实际上并不一定是。

    
    比如这张图中,X 的半支配点就并不是 X 的支配点。(图片引自某博客)

    

    不过没有关系,我们先考虑怎么求出半支配点。

    对于一个点 u,若存在一条边 v -> u,这时我们考虑更新 u 的 semi。分两种情况,若 dfn[v] < dfn[u],说明 v 是 u 的祖先,直接用 v 更新 ;若  dfn[v] > dfn[u],那么这是一条横叉边,也就是说我们可以先走到点 v,再走到点 u,所以,这时我们应该用 v 和 v 的祖先中,不是 u 的祖先的点的  semi 来更新,因为我们可以从这个 semi 走到点 v 的祖先再走到 v 再跨过这条横叉边到 u。

    带权并查集维护一下即可。

    再考虑我们求出 semi 后,如何求出支配点,以下称之为 idom。

    唯一有可能导致出现问题的就是上面的图中那种交叉的情况。于是我们对于点 u,令 u 的 semi 为 t,考虑点 u 到 u 的 t 这条路径上(不含点 t)的点中,令点 v 是 semi 的 dfn 最小的点,若 v 的 semi 等于 t,说明没有出现交叉,于是 u 的 idom 即为 t ; 但是若 v 的 semi 不等于 t,那么就出现了交叉,此时点 u 的 idom 应该等于点 v 的 idom。

    同样是用带权并查集维护。

    至此,问题已经得到解决。

    关于实现方面,我们应该按照 dfn 从大到小的顺序处理每一个点。并且注意求 semi 和求 idom 是可以写在一起的,而且带权并查集维护的东西也是一样的。代码也只有不到一百行。

    hdu4694:

    

#include

#include

#include

#include

#include

#define my_min(a,b) ((a)<(b)?(a):(b))

#define my_max(a,b) ((a)>(b)?(a):(b))

using namespace std;

int reads(int &x)

{

bool f=false ; char t=(char)getchar() ; x=0 ;

while(t<'0'||t>'9'){

if(t=='-')f=true ;

if(t==EOF)return EOF;

t=(char)getchar() ;

}

while(t>='0'&&t<='9'){

x=(x<<1)+(x<<3)+t-'0' ;

t=(char)getchar() ;

}

if(f)x=-x ;

return 0 ;

}

int n , m , fa[50055] , val[50055] , dfn[50055] , TTT , q[50055] , qnum , semi[50055] , idom[50055] , ans[50055] ;

int ff[50055] ;

vector G1[50055] , G2[50055] , tag[50055] , G3[50055] ;

// val 存的是 semi 最浅的点的编号

void init(){

TTT=qnum=0 ;

for(int i=1;i<=n;++i)fa[i]=i , G1[i].clear() , G2[i].clear() , G3[i].clear() , tag[i].clear() , semi[i]=i , ans[i]=idom[i]=val[i]=0 ;

memset(dfn,0,sizeof(int)*(n+5)) ;

dfn[0]=(1<<30)-1 ;

//

}

inline void update_1(int &a,int b){ if(dfn[b]

inline void update_2(int &a,int b){ if(dfn[semi[b]]

int find_fa(int a)

{

if(fa[a]==a)return fa[a] ;

int tf=fa[a] ;

fa[a]=find_fa(fa[a]) ;

update_2(val[a],val[tf]) ;

return fa[a] ;

}

void dfs(int a,int f){

dfn[a]=++TTT , q[++qnum]=a , ff[a]=f ;

int len=(int)G1[a].size() ;

for(int i=0;i

int b=G1[a][i] ;

if(!dfn[b])dfs(b,a) ;

}

}

void get_idom(){

for(int i=qnum;i>=1;--i){

int a=q[i] , len=(int)G2[a].size() ;

for(int j=0;j

int b=G2[a][j] ;

if(!dfn[b])continue ;

if(dfn[b]

else  find_fa(b) , update_1(semi[a],semi[val[b]]) ;

}

len=(int)tag[a].size() ;

for(int j=0;j

int b=tag[a][j] , t;

find_fa(b) , t=semi[val[b]] ;

if(t==a)idom[b]=a ;

else idom[b]=-val[b] ;  // (debug) 这里不是 -t

}

if(i!=1) tag[semi[a]].push_back(a) ;

if(ff[a])fa[a]=ff[a] , val[a]=a ;

}

for(int i=2;i<=qnum;++i){

int a=q[i] ;

if(idom[a]<0)idom[a]=idom[-idom[a]] ;

}

}

void dfs_2(int a,int now){

int len=(int)G3[a].size() ;

ans[a]=now ;

for(int i=0;i

int b=G3[a][i] ;

dfs_2(b,now+b) ;

}

}

void solve(){

for(int i=1;i<=m;++i){

int a,b;

scanf("%d%d",&a,&b) ;

G1[a].push_back(b) , G2[b].push_back(a) ;

}

dfs(n,0) ;

get_idom() ;

for(int i=1;i<=n;++i)if(idom[i])G3[idom[i]].push_back(i) ;

dfs_2(n,n) ;

for(int i=1;i<=n;++i) printf((i==n?"%d\n":"%d "),ans[i]) ;

}

int main()

{

while(reads(n)!=EOF){

reads(m) ;

init() ;

solve() ;

}

return 0 ;

}

CTSC 与 APIO 总结

    啊..这可能是我目前为止 OI 历程中考得最差的大考了吧。

    说颠簸,可能也只是暂时,谁知道呢。


    CTSC 一试,过失性失分、审题偏差、时间分配不当....种种问题袭来,也许是不太适应,但终归是太弱。分数,30。

    CTSC 二试,状态稍微回升,然而分数依然只有 64。

    APIO,Boooooooooom。

    

    考这么差的一些考外原因或许是知道的,没有复习,不重视,实力不足。

    考完试下来,所有人都告诉我没关系,胡老说没有什么的,没有人怪我什么。但总是觉得很压抑,胡老的眉头也不经意地皱着,也许我还是能察觉到什么的。

    我们学校进入省队的人,除了我,所有参加比赛的都至少一个 Au。羡慕 ? 又能怎样。难受也只能怪自己。


    于是跌得很惨...

    于是摔入深渊...

    有些想哭...但终究忍住

    于是我站了起来。

    "要像尘埃一样地无畏。"

【2016/4/28 考题】isn 递推 巧妙计算不合法方案

    题意:给出一个长度为 n 的序列 A。如果序列 A 不是非降的,你必须从中删去一个数,重复这一操作,直到 A 非降为止。求有多少种不同的操作方案,答案模 10^9+7。 ( n<=2000 )


    令 f[i] 表示长度为 i 的非降子序列个数。那么对于一个长度 i,最后只剩长度为 i 的序列的总方案数为 f[i]*(n-i)!,即选的 n-i 个数可以任意互换顺序。

    但是总方案中会包含不合法的方案,我们来考虑减去它。不合法意味着在长度减到 i 之前,剩下的序列就已经非降了,这时,接下来无论删去什么,这个序列总是保持非降的。

    这也就是说,长度减到 i+1 之前就不合法的方案,长度减到 i+1 时一定是非降的,而最后选的显然是这 i+1 个位置中的一个 ;长度减到 i+1 时才不合法的方案,显然也满足这长度为 i+1 的序列是非降的,最后选的同样是这 i+1 个位置中的一个。所以一个不合法的方案一定会使得其长度减到 i+1 时是非降的,而长度减到 i+1 时若序列非降则这个方案一定不合法,恰好一一对应。

    于是不合法的方案数为 f[i+1]*(n-i-1)!*(i+1)。

    答案即为 sigma{ f[i]*(n-i)! - f[i+1]*(n-i-1)!*(i+1) , 1<=i<=n}。


    而f[i]的求法就很简单了,用一个 dp[i][j] 表示以下标为 i 的数结尾,长度为 j 的非降子序列个数, dp[i][j]从dp[k][j-1]转移过来,其中 k<i 且 A[k]<=A[i],用一个树状数组优化转移即可。


    

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define lowbit(x) ((x)&(-(x)))

using namespace std;


const int MOD=1000000007 , INF=(1<<30)-1;

int n , A[2005] , dp[2005][2005] , f[2005] , B[2005] , bnum ;

long long jc[2005] ;

//dp[i][j] 表示以第 i 个结尾,长度为 j 的非降子序列个数

//f[i] 表示长度为 i 的非降子序列个数


inline void update(int &a,const long long &b,const int &M=MOD){

a+=(int)b ;

if(a>=M)a-=M ;

if(a<0)a+=M ;

}


int H_MOD=1000007 , fha[1000055] , xh[1000055] ;

int H(int a){

int t=((a>>3)+(a>>8)+a)%H_MOD ;

while(fha[t]!=-INF && fha[t]!=a) update(t,107,H_MOD) ;

if(fha[t]==-INF)fha[t]=a ;

return t;

}


struct Fenwick_Tree{

int Fen[2005] ;

int query(int pos){

int ret=0 ;

while(pos)update(ret,Fen[pos]) , pos-=lowbit(pos) ;

return ret;

}


void add(int pos,int num){ while(pos<=n)update(Fen[pos],num) , pos+=lowbit(pos) ; }

}FT[2005];


void solve(){

FT[0].add(1,1) ;

for(int i=1;i<=n;++i){

int tha=H(A[i]) ;

for(int j=1;j<=i;++j) dp[i][j]=FT[j-1].query(xh[tha]) ;

for(int j=1;j<=i;++j) FT[j].add(xh[tha],dp[i][j]) ;

}

for(int i=1;i<=n;++i) for(int j=1;j<=i;++j)update(f[j],dp[i][j]) ;

int ans=0 ;

for(int i=1;i<=n;++i) {

update(ans,jc[n-i]*f[i]%MOD) ;

if(i!=n)update(ans,-jc[n-i-1]*f[i+1]%MOD*(i+1)%MOD) ;

}

printf("%d\n",ans) ;

}


int main()

{

freopen("isn.in","r",stdin) ;

freopen("isn.out","w",stdout) ;

scanf("%d",&n) ;

jc[0]=1 ;

for(int i=0;i<=1000015;++i)fha[i]=-INF ;

for(int i=1;i<=n;++i)scanf("%d",&A[i]) , jc[i]=jc[i-1]*i%MOD , B[i]=A[i] ;

bnum=n ;

sort(B+1,B+bnum+1) ;

bnum=unique(B+1,B+bnum+1)-B-1 ;

for(int i=1;i<=bnum;++i){ int tha=H(B[i]) ; xh[tha]=i ; }

solve() ;

return 0;

}

【2016/4/28 考题】seq 莫队+链表思想

    题意:给出一个长度为 n 的排列 P,以及 m 个询问。 每次询问某个区间[l,r]中,最长的值域连续段长度。(n,m <= 50000)

    (注意不要求下标连续 , 例如 3 1 7 2 的最长值域连续段为 1,2,3)


    首先这道题给了一个警示,就是一定要确定理解了题意再开始思考做法,并且要看一看样例和自己想的是否一样。不然结果会很惨。

    一眼看来,这道题就是一个裸的莫队+可撤销并查集。

    这种莫队的写法与平时的莫队不同。大概是这样的,开始是同样地将询问按照左端点所在块分别处理,块内询问按照右端点排序。不同的是,我们每次只加入这个块以右的点,处理每个询问时,先加入这个块内的点,再撤销加入。

    对于每一块的询问,块以右的每个点最多加入一次;对于 m 次查询,每次查询最多加入和撤销加入根号个点。于是复杂度也正确。


    但是,用可撤销的并查集会多一个log,测试时 TLE 了两个点。

    再考虑这道题的性质,我们用并查集是将代表值域的点连起来,这也就是说,每次连通两个值域只有可能是在原本这两个值域的边界处连通。于是我们只用对每个边界存下其对应的另一个边界在哪里即可,加入和撤销均为  O(1)。

    

#include<iostream>

#include<ctime>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define my_min(a,b) ((a)<(b)?(a):(b))

#define my_max(a,b) ((a)>(b)?(a):(b))

using namespace std;


struct questions{

int l,r,xh;

questions(int _xh=0,int _l=0,int _r=0){ xh=_xh , l=_l , r=_r ; }

}qs[50005],que[50005];


bool cmp_r(const questions &a,const questions &b){

if(a.r==b.r)return a.l<b.l ;

return a.r<b.r ;

}


int b_size , now_ans , qnum , stk[50005] , top , n , m , P[50005] ;

int ans[50005] , bl[50005] , br[50005] ;

bool has[50005] ;


void restore(){

while(top){

int t=stk[top] ;

if(t!=1&&has[t-1])br[bl[t-1]]=t-1 ;

if(t!=n&&has[t+1])bl[br[t+1]]=t+1 ;

has[t]=false , top-- ;

}

}


void get_it(int t,bool f){

int ll=t,rr=t ;

if(t!=1&&has[t-1])ll=bl[t-1] ;

if(t!=n&&has[t+1])rr=br[t+1] ;

now_ans=my_max(now_ans,rr-ll+1) ;

br[ll]=rr , bl[rr]=ll , has[t]=true ;

if(f)stk[++top]=t ;

}


void solve(){

b_size=(int)(sqrt(n)+1e-8) ;

for(int i=1;i<=n;i+=b_size){

now_ans=1 , qnum=0 ;

for(int j=1;j<=m;++j) if(qs[j].l>=i && qs[j].l<=my_min(n,i+b_size-1))que[++qnum]=qs[j];

if(!qnum)continue ;

for(int j=1;j<=n;++j)has[j]=false , bl[j]=br[j]=j ;

sort(que+1,que+qnum+1,cmp_r) ;

int now_r=my_min(n,i+b_size-1) ;

for(int j=1;j<=qnum;++j){

while(now_r<que[j].r){

int t=P[++now_r] ;

get_it(t,false) ;

}

int t_ans=now_ans ;

for(int k=my_min(my_min(n,i+b_size-1),que[j].r);k>=que[j].l;--k){

int t=P[k] ;

get_it(t,true) ;

}

ans[que[j].xh]=now_ans , restore() ;

for(int k=my_min(my_min(n,i+b_size-1),que[j].r);k>=que[j].l;--k){ has[P[k]]=false ; }

now_ans=t_ans ;

}

}

for(int i=1;i<=m;++i) printf("%d\n",ans[i]) ;

}


int main()

{

freopen("seq.in","r",stdin) ;

freopen("seq.out","w",stdout) ;

scanf("%d%d",&n,&m) ;

for(int i=1;i<=n;++i)scanf("%d",&P[i]) ;

for(int i=1;i<=m;++i){

scanf("%d%d",&qs[i].l,&qs[i].r) ;

qs[i].xh=i ;

}

solve() ;

//fprintf(stderr,"%d\n",clock()) ;

return 0 ;

}


【2016/4/25 考题】Graph 递推

    题意:求 n 个点带标号的边权为[1,m]的不同二分图的个数,对一个质数取模。注意此处的不同是指边集不同或某条边的权值不同。(题意经稍稍简化,原题需要特判 n==1 的情况)


    再次Orz  ....   这种题或许还是该再多写写 ....

    令 ans[i] 表示 i 个点的答案,递推时考虑一个常用的方法,即枚举最后点 i 放入的连通块的大小。

    于是 ans[i]=sigma{ C(i-1,j)*f[j+1]*ans[i-j-1]  , 0<=j<=i-1 },其中 f[i] 表示 i 个点的连通的二分图的个数。

    现在问题转化为怎么求 f[i],考虑补集转化,令 g[i] 表示 i 个点黑白染色后再随意连边的方案数(所有点均反色后算同一种方案)。

    则 g[i]=1/2 * sigma{ C(i,j)*(m+1)^((i-j)*j) ,  0<=j<=i } ,即枚举选哪些点染黑,然后边权随便选,边权为 0 看作不存在这条边。

    考虑从 g[i] 中减去所有不连通的方案即为 f[i],要减去的东西为:

    sigma{ C(i-1,j) * 2 * f[j+1] * g[i-j-1] ,  0<=j<=i-2 }   , 注意 j+1 是小于 i 的。为什么呢 ? 同样考虑枚举第 i 个点加入的连通块大小,连通块需要连通,所以为 f[j+1],而剩余点怎么连都无所谓,即为 g[i-j-1]。乘 2 是因为枚举的这个连通块与块外部其中一个,交换 x 部与 y 部后,会在 g[] 中视为不同的方案。


    于是先递推出 g[] , 再递推出 f[] ,再递推出 ans[] 即可。

    

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;


const int MOD=105225319 ;


long long pow_mod(long long a,long long b){

long long ret=1 ;

while(b){

if(b&1)ret=ret*a%MOD ;

a=a*a%MOD , b>>=1 ;

}

return ret;

}


int n,m ;

long long ci[1000005],jc[1005],rev_jc[1005] ;

long long ans[1005] , f[1005] , g[1005] , rev_2 ;


long long C(long long a,long long b){ return jc[a]*rev_jc[b]%MOD*rev_jc[a-b]%MOD ; }


void init(){

ci[0]=jc[0]=rev_jc[0]=1 , rev_2=pow_mod(2,MOD-2) ;

for(int i=1;i<=1000000;++i)ci[i]=ci[i-1]*(m+1)%MOD ;

for(int i=1;i<=1000;++i) jc[i]=jc[i-1]*i%MOD , rev_jc[i]=pow_mod(jc[i],MOD-2) ;

}


void solve()

{

for(int i=1;i<=n;++i){

for(int j=0;j<=i;++j)g[i]=(g[i]+C(i,j)*ci[(i-j)*j])%MOD ;

g[i]=g[i]*rev_2%MOD ;

}

for(int i=1;i<=n;++i){

f[i]=g[i] ;

for(int j=0;j<=i-2;++j) {

f[i]=(f[i]-C(i-1,j)*2*f[j+1]%MOD*g[i-j-1]%MOD) ;

if(f[i]<0)f[i]+=MOD ;

if(f[i]>=MOD)f[i]-=MOD ;

}

}

ans[1]=ans[0]=1 ;

for(int i=2;i<=n;++i){

for(int j=0;j<=i-1;++j)ans[i]=(ans[i]+C(i-1,j)*f[j+1]%MOD*ans[i-1-j])%MOD ;

}

printf("%lld\n",ans[n]) ;

}


int main()

{

freopen("graph.in","r",stdin) ;

freopen("graph.out","w",stdout) ;

scanf("%d%d",&n,&m) ;

if(n==1){

printf("0\n") ;

return 0 ;

}

init() ;

solve() ;

return 0 ;

}


【2016/4/22 考题】 TV 动态规划

    题意:有 N 个电视节目,观看第 i 个电视节目时,若观看的上一个节目和它种类相同,则获得 Ai 的愉悦度,否则获得 Bi 的愉悦度。问怎样安排一个顺序使得愉悦度最大,注意不是每一个电视节目都必须观看。

    (N<=600 , 种类数 <= N ,  |Ai|、|Bi| <= 10000)


    Orzzzz考场上怎么想也没有想到怎么做....

    首先处理出对于每个种类 i,分成 j 段(也就是说要选择 j 个 B 值)的最大愉悦度 f[i][j]。这个直接贪心即可得到。

    方案合法的条件是同一种类的段数不超过总段数的一半(上取整),于是我们枚举总段数。再用 dp[i][j] 表示前 i 个种类,分成 j 段的最大愉悦度。

    dp[i][j] 从 dp[i-1][j-k] + f[i][k] 转移过来。即先枚举总段数,再枚举 i,枚举 j,枚举 k。看起来是 O(n^4) 的,但其实所有节目的 k 的总和是 O(n)级别的,所以总复杂度为 O(n^3)。

    

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define my_min(a,b) ((a)<(b)?(a):(b))

#define my_max(a,b) ((a)>(b)?(a):(b))

using namespace std;


int n ;

int max_T ;

int T[605] , A[605] , B[605] , f[605][605] , dp[605][605] , sum[605] ;

vector<int> ele[605] ;


// f[i][j] 表示只考虑第 i 个种类,分成 j 段,最大权值


// dp[i][j] 表示考虑前 i 个种类,有 j 段,最大权值


bool cmp(const int &a,const int &b){ return B[a]-my_max(A[a],0) > B[b]-my_max(A[b],0) ; }


void init()

{

for(int i=1;i<=max_T;++i){

int len=(int)ele[i].size() ;

sum[i]=sum[i-1]+len ;

for(int j=0;j<len;++j) if(A[ele[i][j]]>0)f[i][0]+=A[ele[i][j]] ;

sort(ele[i].begin(),ele[i].end(),cmp) ;

for(int j=1;j<=len;++j){

int t=ele[i][j-1] ;

f[i][j]=f[i][j-1]+B[t]-my_max(A[t],0) ;

}

f[i][0]=0 ;

}

}


void solve()

{

int ans=0 ;

for(int limits=1;limits<=n;++limits){

int up=(limits+1)/2 ;

memset(dp,0x8f,sizeof(dp)) ;

dp[0][0]=0 ;

for(int i=1;i<=max_T;++i){

int len=(int)ele[i].size() , sj=my_min(sum[i],limits) ;

for(int j=1;j<=sj;++j){

int sk=my_min(my_min(len,j),up) ;

for(int k=0;k<=sk;++k){

dp[i][j]=my_max(dp[i][j],dp[i-1][j-k]+f[i][k]) ;

}

}

}

ans=my_max(ans,dp[max_T][limits]) ;

}

printf("%d\n",ans) ;

}


int main()

{

freopen("tv.in","r",stdin) ;

freopen("tv.out","w",stdout) ;

scanf("%d",&n) ;

for(int i=1;i<=n;++i){

scanf("%d%d%d",&T[i],&A[i],&B[i]) ;

ele[T[i]].push_back(i) ;

max_T=max(max_T,T[i]) ;

}

init() ;

solve() ;

return 0 ;

}


【bzoj 2142】 大组合数取模 --- 分段递归处理

    题意:求 m 个 C(a,b) 乘起来模 P 的答案。

    (m <= 5 , a、b <=10^9 , P 可能为非质数,P唯一分解后 1≤pi^ci≤10^5)


    这种做法在很久之前就写过一遍了,然而当时调了很久很久....

    于是再写了一遍,顺带也总结一下吧。


    考虑在模 pi^ci 下求 C(a,b) , 再用中国剩余定理合并起来。

    要怎么求呢 ? 由于有除法,且对一个数求逆元需要与模数互质,我们考虑将 C(a,b) 中的 pi 提出来,即写成 pi^k * t 的形式。

    这样 t 就可以求逆元了 。所以我们求出分子的 k1 和 t1 ,以及分母的 k2 和 t2,那么 C(a,b) 的 k 就是 k1-k2 , t 就是 t1/t2。得到 k 和 t 过后就可以知道 C(a,b) 是多少了。

    

    好的,现在问题转化成了怎么求分子和分母的 k、t,即需要求 a! 中的 k 和 t。令 MOD=pi^ci。我们将这 a 个数中是 pi 的倍数的数找出来,而其它的数直接累乘进 t。找到的这些数即为 pi、pi*2、pi*3… 然后将这些数都提出一个 pi 的因数,提出后这些数变成了 1、2、3...[a/p],也即 [a/p]!,递归处理即可。递归层数为 log 级别。

    但由于 a 会达到 10^9 级别,由题意知 MOD<=10^5,那么我们将 a! 按每 MOD 个数分成一段,每一整段的贡献是相同的,这样每一层最多处理O(MOD) 个数。

    整个算法就是这样了。


#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;


int m ;

int que[1005] , qnum , ci[1005] ;

long long P , mm[1005] , aa[1005] , n , w[6] ;


long long pow_mod(long long a,long long b,long long c)

{

long long ret=1 ;

while(b){

if(b&1)ret=ret*a%c ;

a=a*a%c , b>>=1 ;

}

return ret ;

}


long long ex_gcd(long long a,long long b,long long &x,long long &y)

{

if(b==0){

x=1 , y=0 ;

return a;

}

long long ret=ex_gcd(b,a%b,x,y) ;

long long tx=x ;

x=y , y=tx-a/b*y ;

return ret;

}


long long get_rev(long long a,long long b)//求 a 在模 b 下的逆元 (保证存在)

{

long long x,y ;

ex_gcd(a,b,x,y) ;

return (x%b+b)%b ;

}


long long xnum , xx ;

long long get_jc(long long a,long long p,long long k,long long MOD,long long &num)

{

if(a<=1)return 1;

long long ret=1 , tmp=xx , tnum=xnum ;

long long t=a/MOD ;

tnum*=t , num=num+tnum , ret=ret*pow_mod(tmp,t,MOD)%MOD ;

t=a-t*MOD ;

for(int i=1;i<=t;++i){

if(i%p==0)tnum ++ , num ++ ;

elseret=ret*i%MOD ;

}

ret=ret*get_jc(tnum,p,k,MOD,num)%MOD ;

return ret;

}


long long get_C(long long a,long long b,long long p,long long k,long long MOD)

{

xnum=0 , xx=1 ;

for(int i=1;i<=MOD;++i) {

if(i%p==0)xnum++ ;

elsexx=xx*i%MOD ;

}

long long ret=1 , num=0 , tnum=0 , tmp=1 ;

ret=ret*get_jc(a,p,k,MOD,num)%MOD ;

tmp=tmp*get_jc(b,p,k,MOD,tnum)%MOD*get_jc(a-b,p,k,MOD,tnum)%MOD ;

num-=tnum , ret=ret*get_rev(tmp,MOD) ;

if(num>=k)return 0 ;

for(int i=1;i<=num;++i)ret=ret*p%MOD ;

return ret;

}


long long C(long long a,long long b)

{

long long ret=0 ;

for(int i=1;i<=qnum;++i){

long long t=get_C(a,b,que[i],ci[i],mm[i]) , tmp=P/mm[i] ;

ret=(ret+t*tmp%P*get_rev(tmp,mm[i])%P)%P ;

}

return ret;

}


int main()

{

scanf("%lld%lld%d",&P,&n,&m) ;

long long sum=0 ;

for(int i=1;i<=m;++i)scanf("%lld",&w[i]) , sum+=w[i] ;

if(sum>n){

printf("Impossible\n") ;

return 0 ;

}

long long tmp=P ;

for(int i=2;(long long)i*i<=P;++i){

while(tmp%i==0){

tmp/=i ;

if(que[qnum]!=i)que[++qnum]=i ;

ci[qnum]++ ;

}

}

if(tmp>1)que[++qnum]=(int)tmp , ci[qnum]=1 ;

for(int i=1;i<=qnum;++i){

mm[i]=1 ;

for(int j=1;j<=ci[i];++j)mm[i]*=que[i] ;

}

long long ans=1 , res=n ;

for(int i=1;i<=m;++i){

ans=ans*C(res,w[i])%P ;

res-=w[i] ;

}

if(!ans){

printf("Impossible\n") ; return 0 ;

}

printf("%lld\n",ans) ;

return 0 ;

}

省选 --- 总结

    省选终于还是结束了。稍微概括一下这几天发生的吧。

    省选日期:4月9日、4月10日。


    从清明就开始为省选有些紧张,当时的电子科大 ACM 校赛我们队在七中高二男生队伍里面垫底了,然而前面两个队共有六个人,还是感觉到压力了。

    233333333 不过清明还是整整玩过了两天 ~

    清明结束,5日,早上是一场娱乐的考试,依然保持好心情。下午,起身前往电子科大,很多人的家长好像都来了,然而 zxr、lk还有我就直接打的 Uber。虽然貌似没有发生什么,但是隐约中,空气中还是有一种紧张的气氛。为了放轻松,晚上就一起颓了狼人杀,感觉挺棒的,哈哈哈 ~ 

    接下来的几天,数着日子地,一天天过去。几乎每天都是白天到电子科大的实验中学,晚上回酒店。过得很开心吧,毕竟有那么多人,lk说不喜欢有太多人,但是我还是觉得人多是一种幸运。


    8日,省选前夜。

    张老和林老把大家叫去开会了,主要是做明天的安排,我和zxr一起坐 tyh 家的车过去。

    回房间趁着月黑风高还是复习了一下下 23333

    我 : “Register,你紧张吗?”

    ZXR :  ”还好吧“

    zxr 一直都说自己挺娱乐的,不过我觉得他还是希望自己可以过省选吧。毕竟我们也为这个付出了那么多。


    9日,该到来的总是躲不过。

    Orz为了不睡过,设了四个闹钟.........

    6:00 : 唔..结果还是自己就醒了.......醒了就醒了吧,还好不是在三点醒的。闭眼,思考,冷静,再次睡着。

    6:30 : 闹钟响起,起床。

    7:15 : 和 zxr 还有 tyh 一起坐车出发。是有些紧张,不过还好。

    7:50 : 拿到准考证,进入考场,下载好题目。还没有公布解压密码,于是抓紧时间把 vim 和 gdb 配置好,顺手敲好了读入优化。

    8:05 : 解压密码公布,省选一试正式开始 !

    8:06 : 首先看了看时间和空间限制,只有第二题是 6s。

    开始读题 ! 第一题题目好长...看了好一会,感觉题目给的一个条件是弱智条件 ?? 啊..那为什么要给出来,稍微想了一想,好像可以贪心 !

    但是由于那个弱智条件...还是留着待会再想一想正确性...

    第二题..诶诶 ?? 链剖+线性基? O(n*logn*60*60),复杂度好像很高,而且是数据结构的题,应该不是很好写。

    第三题..诶 ?????? 不是吧 ?....这道题不是原题吗 ?? 快回忆快回忆 ! 当时 yjq 讲过,貌似是 ST表 + 并查集 ?

    8:20 : 确定做题顺序 ! 那就 3-1-2 吧 !

    第三题代码好短...没调几分钟就过了大样例,写对拍 ! 一发跑过 ! 下一题 !

    再看看第一题,啊啊...实在没有看出那个条件有什么用...稍稍用反证法推了一下,貌似贪心是正确的 ! Trie树 + 建树贪心 ! 也没有调多久就过了大样例。对拍 ! 跑过 !

    10:40 : 现在两道题比较稳,一直在跑对拍,还剩第二题没有敲,不过第二题应该不好拿满...诶 ? 机子出状况了? ... what ? 跑着跑着对拍就说我无输出,是程序的问题还是机子的问题 ??

    11:10 : WTF ? 检查了好多遍程序,两个程序都会拍出无输出 。这什么情况 !

    11:15 : 算了,放弃检查,估计是电脑的问题 ? 啊啊浪费了好多时间,不过也还好,时间还算比较多,而且还顺带发现了一个 bug !居然没有拍出来 ! 论检查代码的重要性....

    先敲暴力跑线性基,然后敲一条链的情况,写了个线段树合并线性基。

    这道题因为代码比较长,调了好一会...

    12:10 : 跑过大样例 ! Nice ! 现在加一个链剖也挺轻松的 ! 反正线段树都已经敲好了 ~ 但是唯一怕的就是复杂度,还是先造一组大数据吧。

    诶诶 ?? 跑了好几秒 ? 那加上链剖岂不是要稳 T ? 啊啊...不过加上有可能会多拿一点点分 ?

    思考了一下下....还是算了,不要冒这个险比较好。不出错的话,现在我能拿到的分是第一题 100 + 第二题 50 + 第三题 100 。感觉还是挺高了 ? 知足吧,去检查一下这三道题好了。

    13:00 : 考试结束,离开考场。

    下午等到了 4 点半才看到自己的分数,诶 ? 只有240 ? 100+40+100,第二题少了 10 分,去申诉了一下..还是40,那就算了吧,已经很不错了。

    今天考试,rank1 是 yjq,%%%%%300分 !rank2 是 zms,260分 !石室的 lcr 是rank3 ,250分 ! 然后我和 zcy 并列 rank4 。算上 NOIP,我排到全省第4,全校第3。

    不过我还是担心二试考挂,所以还变得更紧张了一些。

    诶 ? tyh 考挂了 !? tyh 考挂了 !? tyh 考挂了 !? 好惨..只有 90 分,唉..毕竟这样的考试,总会有人出现失误..还是希望他二试翻盘吧


    10日,这是最后定结果的一天了。

    7:55 : 发解压密码。二试开始 !

    看看时间和空间限制..看题....

    第一题,诶 ? 感觉可以把攻击力和防御力画成二维平面上的点,然后求凸包 + 三分 ? 但是n是 10^6,感觉有可能会被卡 ?

    第二题,这道题...看起来很像是在 Trie 树上贪心啊...但是对于每个人要加一个 x ,这可怎么做 ?

    第三题,呀...看起来好像很难的样子,暂时只会写20分暴力 ...

    呼...今天题目貌似难度大了一些 ?冷静冷静...至少第一题还有思路,虽然可能过不了,那就 1-2-3 吧 !

    其实对计算几何有一些恐惧...因为平时考试就有因为去写计算几何然后整场考试挂掉了的...不过现在也只有硬着头皮写了!毕竟只是一个凸包,只是一个三分,而且还有大样例。

    10:00 : 第一题终于过了大样例 ! 但是想了好一会的公式没有想出来,那就还是用三分吧 ... 凸壳上的点期望下是很少的 ! 而且这个算法不好卡,所以不怂 ! 加上一个卡时,做下一道题 !

    再看看第二题,诶诶 ? 为什么需要 Trie 树 ? 直接主席树 + 贪心就好了 ! 复杂度是 O(n*logn*20) !

    11:00 : 敲完第二题并且大样例和对拍都过了。感觉局势和昨天很像...

    先检查前两题吧 。    

    11:20 : 没有检查出问题,看第三题...前 20 分就写状压 DP 吧,后面有个 30 分写一个容斥貌似可行 ?

    12:30 : 搞定,饿得要死,去吃了一个沙琪玛压压惊....

    13:00 : 考试结束,等待下午的成绩出来吧,估分第一题最少20最多100,第二题100,第三题50.

    16:00 : 今天成绩出来得比较早,诶 ! 又是240 ! 幸好第一题拿的分高 !


    两天加上NOIP,排在全省第 5,全校第 4,因为女生要占一个名额的原因..刚好被 a 类卡了出来 .... 不过倒也还好,虽然是 b 类,至少还是进队了 !

    tyh 排在全校第 7,但是因为 lpx 决定不要 c 类了,tyh 也进了队。

    于是我校进队的有 :    a类 :yjq、zcy、dxq  , b类 : 我 、zms ,    c类 : tyh 。

    女生第一是 ljl ,orzzzz二试翻盘。

    但是有人翻盘...就意味着有人退役... zxr和lk都退役了... 希望回高新过后可以文化课翻盘吧 ! 加油 ! 相信你们 !

    就这样吧,为NOI2016继续准备吧 !