]]>
Question:
What is 'signal' ?
#include <cstdio>using namespace std;void f(int);void (*pf)(int), (*qf)(int);void (*hf(int, void(*)(int)))(int);typedef void (*sighandler_t)(int);sighandler_t signal(int, sighandler_t);void f(int a) 
{
printf("void f(int %d)\n", a);
}void (*hf(int _i, void(*_pf)(int)))(int){ printf("_i = %d\n", _i); _pf(_i); return _pf;}sighandler_t signal(int signum, sighandler_t sighandler){ printf("signal num = %d\n", signum); sighandler(signum); return sighandler;}int main(){ pf = &f; qf = hf(12, pf); qf(23); signal(54, f); return 0;}void (*signal(int, void (*)(int)))(int);
Answer:
signal is a function, passing {an int and a pointer [to a function passing an int returning nothing (void)]}, returning {a pointer [to a function passing an int returning nothing (void)]}.
]]>
题意是问在N个点的完全图(N<=10,000)中删掉M(M<=1,000,000)条边? q有多少个点与顶?q?点~号?开?.
暴力BFS+HASH+各种WS优化的方法很? 但是出题人原意应该是O(M)的做法吧... 下面是我YY出来的O(M)的做?
只考虑qM条待删边, 能得C么信息呢? 可以先从?入手. 扫一遍与1L的点, 那么剩下没被扫到的点肯定?是连通的. 而被扫到的点?有可??不连? 所以就把那些肯定与1q通的点做标记. 从这些确定连通的点中任选一个u, 再扫描它的所有邻接点. q之? 如果一个点一p扫了2? 那么它才"有可??不连? 其它于2ơ的点肯定与1q? 因ؓ它或者与1q? 或者与uq? 而u是已知与1q通的. q样再拿Z个已l确定连通的? 扫描它的L? 把被扫过ơ数<3的又标记为已q?.....
l过上面的YY, 法基本上就出来?
把已知肯定与1q通的炚wUCؓS, 剩下不确定的为T. 一开? S中只?q一个点, 其它炚w在T? 每个Ҏ个计数器, 记录自己被扫了多次.
1) 从S中取Z个没处理q的? 把它标记为已处理, q历它的所有邻接点, 被遍历到的点的计数器?1.
2) T中所?计数<S中已处理点个?? 都可以确定是q通的, 把它们从T中删? 加入S?
3) 重复1), 直到S中所有点都处理完.
q时, S中的点就是与1q通的, T中剩下的是不连通的.
复杂度分?
d边和扫描辚w是O(M)?
S集可以用队列l护, dO(N).
T集的l护: 每一轮都要扫一遍当前的T, 把所有计数小的删? 放进S? q样, q一步的d杂度是O(sigma(T)), 会不会到达O(N^2)? 实际上是不会? 因ؓ一条边最多只会一个顶点的计数+1, 因此每一轮还剩在T中的Ҏ不会过q一轮遍历过的边? q样, 所有回合的sigma(T)p定不会超q总边? 因此q里d也是O(M)? 严格来说上W?轮有N-1个点, 也是O(M+N).
q样ȝ复杂度就是O(M)?
不过q个法d用scanf? g++跑了1000+ms, Ҏgetchar才到200+ms? 不知道排前面的神们是不是有更NB的算?
代码:
1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7
8 const int MAXN = 10010;
9 const int MAXM = 1000010;
10
11 struct Edge {
12 int v, next;
13 }edg[MAXM*2];
14 int ecnt, gg[MAXN];
15 bool yes[MAXN];
16 int que[MAXN], pq, sq, cnt[MAXN], vt[MAXN], nt;
17 int N, M;
18
19 inline int getnextint()
20 {
21 int r = 0;
22 char c;
23 while(!isdigit(c=getchar()));
24 do{
25 r = r*10 + c-'0';
26 } while(isdigit(c=getchar()));
27 return r;
28 }
29
30 inline void addedge(int u , int v)
31 {
32 edg[ecnt].v = v; edg[ecnt].next = gg[u], gg[u] = ecnt++;
33 edg[ecnt].v = u; edg[ecnt].next = gg[v], gg[v] = ecnt++;
34 }
35
36 int main()
37 {
38 int cas = 0;
39 while(~scanf("%d%d", &N, &M) && !(N==0 && M==0)){
40
41 ecnt = 0;
42 for(int i = 0; i < N; i++){
43 gg[i] = -1;
44 yes[i] = i==0 ? true : false;
45 cnt[i] = 0;
46 vt[i] = i+1;
47 }
48 nt = N-1;
49
50 for(int i = 0; i < M; i++){
51 int u = getnextint();
52 int v = getnextint();
53 addedge(--u, --v);
54 }
55
56 pq = sq = 0;
57 que[sq++] = 0;
58 yes[0] = true;
59
60 while(pq != sq) {
61 int u = que[pq++];
62 for(int e = gg[u]; e >= 0; e = edg[e].next) {
63 if(!yes[edg[e].v])
64 cnt[edg[e].v]++;
65 }
66 for(int i = 0; i < nt; i++) {
67 while(i < nt && cnt[vt[i]] < pq) {
68 yes[vt[i]] = true;
69 que[sq++] = vt[i];
70 if(i < --nt)
71 vt[i] = vt[nt];
72 }
73 }
74 }
75 printf("Case %d: %d\n", ++cas, sq-1);
76
77 }
78 return 0;
79 }
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7
8 const int MAXN = 10010;
9 const int MAXM = 1000010;
10
11 struct Edge {
12 int v, next;
13 }edg[MAXM*2];
14 int ecnt, gg[MAXN];
15 bool yes[MAXN];
16 int que[MAXN], pq, sq, cnt[MAXN], vt[MAXN], nt;
17 int N, M;
18
19 inline int getnextint()
20 {
21 int r = 0;
22 char c;
23 while(!isdigit(c=getchar()));
24 do{
25 r = r*10 + c-'0';
26 } while(isdigit(c=getchar()));
27 return r;
28 }
29
30 inline void addedge(int u , int v)
31 {
32 edg[ecnt].v = v; edg[ecnt].next = gg[u], gg[u] = ecnt++;
33 edg[ecnt].v = u; edg[ecnt].next = gg[v], gg[v] = ecnt++;
34 }
35
36 int main()
37 {
38 int cas = 0;
39 while(~scanf("%d%d", &N, &M) && !(N==0 && M==0)){
40
41 ecnt = 0;
42 for(int i = 0; i < N; i++){
43 gg[i] = -1;
44 yes[i] = i==0 ? true : false;
45 cnt[i] = 0;
46 vt[i] = i+1;
47 }
48 nt = N-1;
49
50 for(int i = 0; i < M; i++){
51 int u = getnextint();
52 int v = getnextint();
53 addedge(--u, --v);
54 }
55
56 pq = sq = 0;
57 que[sq++] = 0;
58 yes[0] = true;
59
60 while(pq != sq) {
61 int u = que[pq++];
62 for(int e = gg[u]; e >= 0; e = edg[e].next) {
63 if(!yes[edg[e].v])
64 cnt[edg[e].v]++;
65 }
66 for(int i = 0; i < nt; i++) {
67 while(i < nt && cnt[vt[i]] < pq) {
68 yes[vt[i]] = true;
69 que[sq++] = vt[i];
70 if(i < --nt)
71 vt[i] = vt[nt];
72 }
73 }
74 }
75 printf("Case %d: %d\n", ++cas, sq-1);
76
77 }
78 return 0;
79 }
]]>
某神?0,0)? 需要走?x,y)?0<x,y<=10^9), 他只能按cM马蟩的方式走, ? l出一个n, 他可以从(a,b)走到(a-1,b-n) (a+1,b-n) (a-1,b+n) (a+1,b+n) (a-n,b-1) (a+n,b-1) (a-n,b+1) (a+n, b+1) 中的一?现在l出50个不同的n[1..50], 他可以以L的n[i]方式? 每种方式的用次C? 问能否走到目的地(x,y).
很明? 此神可以沿Q意方??步的? 卛_C(+1,-n), 再走?+1,+n). 所以能否到l点, 只与奇偶性有?
l过一阵分c讨论可?
1) 如果x+y=0(mod 2), 则YES.
2) 如果x+y=1(mod 2), 且n[i]中有偶数, 则YES.
3) 否则NO.
[杂]
600pt MagicalGirlLevelTwoDivOne
l一个H*W(1<=H,W<=50)的矩阵A, 每一位上已经有一?~9的数? 或者是?.', ?.'处可以填上Q?~9的数? 再给出n和m(1<=n<=min{10,H}, 1<=m<=min{10,W}). 问一共有多少U填'?'的方? 使得整个矩阵满:
对Q意的r和c, ?r,c)开始的水^方向上连lm个数之和是奇?
对Q意的r和c, ?r,c)开始的垂直方向上连ln个数之和是奇?
首先要注意到一个性质: 对Q意r和c?A[r,c]与A[r+n,c]的奇偶性相? 很显? 因ؓ要满A[r,c]+A[r+1,c]+...+A[r+n-1,c]与A[r+1,c]+...+A[r+n-1,c]+A[r+n,c]的奇偶性相? 都是奇数. 列上同样有A[r,c]与A[r,c+m]奇偶性相?
因此在一行上, 只用记录n位的奇偶状? 列上同理. q样,所有的(r+pn,c+qm)都能合ƈ成同一个点, 且只有两U状? 奇和?/strong>. 合ƈ后该点ؓ?或偶)的方法数, {于l成它的所有点ҎCU? 最后整个矩阵合q压~成一个n*m的矩? 可以用状态DP来搞, 求每行每列之和都为奇的方法数. dp[n][1<<m], 前n? 每一列和的奇偶性对应bit??. O(1<<m)的{Ud杂度, 转移时要注意该行状?有奇C.
觉得是道很好的题, 状态设计很巧妙...
[状态DP 状态压~设计]
900pt MagicalGirlLevelThreeDivOne
某神l出K(K<=50)?1? 每个串的长度不超q?0. 用这些串l成新的串放到数lA[]? 如果i<K, 则A[i]为给出的Wi个串. 否则A[i] = A[i-1] + A[i-K-1] + A[i-2*K-1] + ... + A[i-p*K-1], 其中p是i-p*K-1>=0的最大整? 现在此神l出n, lo, hi, 要你求A[n]的子串A[n][lo...hi]中有多少个连l的1. 0<=n<=10^15, 0<=hi<= min{A[n]的长? 10^15}, 0<=lo<=hi. 所有计C0开?
首先随便打个表或者手推一下化A[i]的递推? 可以发现当i>=2*K? A[i] = A[i-1] + (A[i-K-1] + ... A[i-p*K-1]) = A[i-1] + A[i-K], 而K<=50. 所以A[i]的长度关于i是指数增长的, 50log(10^15)可能够用(严格证明不太? 求指?.#). 因此其实n<=10^15范围是坑爹的, hi不会过A[10^4]的长? 而这些串的前~都是一L, 所以A[n][lo..hi]其实与A[10^4][lo..hi]相同.
q样便可直接利用A[i] = A[i-1] + A[i-K]的关pd? 和用U段树求最长连l?串的思想差不? 每个l点的状态变量是(id,lo,hi), 存放A[id][lo..hi]的最优解. 除了存放当前D늚最大长度max? Z能合q子区间, q要记录当前区间从左端开始连l?的个数sl, 和从右端开始连l?的个数sr. 剩下的工作与U段树无? 假设要求(id, lo, hi)?max, sl, sr):
对于A[id], 它的左儿子就是A[id-1], 叛_子是A[id-K].
1)如果id<2*K, 直接暴力.
2)如果lo>=len[id-1](cM于线D|中的查询区间完全落在叛_?, 则递归查询(id-K, lo-len[id-1], hi-len[id-1]).
3)如果hi<len[id-1], 则递归查询(id-1, lo, hi).
4)否则两个儿子都要查询, q根据返回的l果求当前区间的l果.
分治思想很强? 用map写的"U段?很YD, 偶依然蒻爆了.
[分治 复杂度分析]
]]>
题意: 某神在M*N(1<=M, N<=50, M*N为偶?的格子上玩对对碰: 每个格子都有个隐藏的囑Ş. 此神一ơ行动翻开2? 如果相同, 成功消去这2个格? 如果不相? 那这2个格子又恢复隐藏状? 但是此神记忆力很NB, 能记住所有翻开q的格子是什么图? q有重要的一? 他一ơ行动时, 是先d1个格? 知道它的囑Ş之后, 再决定怎么ȝ2个格? 而不是两个格子同时翻开. 问此把所有格子都消去, 需要消耗的行动ơ数的期?
Ҏ惛_期望与翻格子的位|无? 有关的量? 当前q有多少对图形没被消? 其中有多对囑Ş已经知道其中一个的位置? so, dp[i][j], i为前? j为后? 一ơ行动中, W?个格子肯定翻之前没翻q的(一共有2i-j? Cؓs), 除非已经知道?对的位置, 直接?个都d来消? 所以{UL几种情况:
1) 从s中翻?个新囑Ş. 从剩下s-1中翻Z相同囑Ş, 消除. q样的概率是2(i-j)/s * 1/(s-1), 转移到dp[i-1][j].
2) 从s中翻?个新囑Ş. 从剩下s-1中又d新图? q样多?U已知图? 概率?(i-j)/s * 2(i-j-1)/(s-1), 转移到dp[i][j+2].
3) 从s中翻?个新囑Ş. 从剩下s-1中翻Z之前j个已知图形中的一? q样, 下一ơ就可以消耗一ơ行动把那对已知囑Ş消去, 转移到dp[i-1][j], 概率?(i-j)/s * j/(s-1).
4) 从s中翻?个已知图? 直接d与它配对的消? 转移到dp[i-1][j-1], 概率是j/s * 1.
所?dp[i][j] = p1*(dp[i-1][j]+1) + p2*(dp[i][j+2]+1) + p3*(dp[i-1][j]+2) + p4*(dp[i-1][j-1]+1).
其中2)的条件是i>=j+2, 4)的条件j>=1. 边界dp[i][i] = i. 最后dp[M*N][0]即ؓ所?
[概率 期望 DP]
1000pt Reflections
题意: 某神在三l空间中玩一个游? I间中有N?N<=20)q面, 每个q面都垂直于某个坐标? q且与该坐标轴交于整? 此神?0,0,0)处出? 惛_(X,Y,Z)? 现在他每行动一ơ可以做如下Ud:
1) 走到与他盔R?个整点上, ?x+1, y, z) (x-1, y, z) (x, y+1, z) (x, y-1, z) (x, y, z+1) (x, y, z-1)中的一?
2) 一ơ行动可以利用一个^? Ud到关于这个^面对U的点处. 每个q面在整个游戏过E中臛_只能利用一?
问此到辄点花费的最行动次?
易知三个方向是不相关? 所以只用先考虑一l的情Ş.
首先要想? 走\和反交? 是等效于先反完了再一口气走到l点? 因ؓ在反之前的走动, 不会被反动作放? 反射前移动多步, l过若干ơ反后所到达的位|? 与不Ud直接反射到达的位|? 相差正好是移动的步数.
所以可以{化ؓ先反若q次, 再行走到l点. 现在p推出反射到达的位|公?
假设每个反射轴的坐标依次是x[1], x[2], ..., x[n], 经q第kơ反后的位|是p[k].
Ҏ推出, p[1] = 2x[1], p[2] = p[1] + 2(x[2]-x[1]) = 2x[2] - 2x[1], ... p[k] = 2x[k]-2x[k-1]+2x[k-2]-...+2*(-1)^(k-1)x[1].
q是很规则的正负交替求和, 正项数等于负Ҏ, 或者比负项数多1.
到此问题转化得很清晰? ?0个数中选出k个数作ؓ正项, k(或k-1)个数作ؓ负项, 每个数至多被?? 该方案的总行动次数是选出的个?卛_反射的L?, 加上q些之和到l点的距?x后一路走q去).
选数要降低复杂度, 可以?0个数分成两个集合, 每边10个数, 先各自生?^10个和. 两边分别排序? 从小到大枚D左边? C个指针从大到扫双?
[数学 分治]
]]>
l出N(N<=50)个不于0且不大于511的整? 开始时寄存器ؓ0, 两h轮流选取一个数, 与寄存器的值OR, 把结果覆盖写入寄存器. C能重复? 如果某h操作之后寄存器的gؓ511, 或者轮到某人时数都取完? 那么q个人就负. 问先手是否有必胜{略.
Ҏ惛_2^9q一l? 记录当前每一位的0/1状? 实际? 不需要记录当前已l选过哪些? 而只用记录已l选了几个? 再由当前?/1? p推算出哪些数没选过. 有些数x满x|now != x, q些数肯定没选过. 而对那些x|now == x的数, 不必知道它具体的? 因ؓ它对后箋操作的媄响都一? 是延缓一? 把局面原不动地丢给Ҏ. 所以只需知道当前q有多少个这Lx没被使用q? q个g能由上面的信息得?
q样是一个类似极大极的必胜必|态记忆化搜烦.
状态ؓdp[1<<9][N], 转移为N.
[状态DP]
1000pt GameOfLifeDivOne
一个长为N(N<=50)的串(环状, 首尾相连, 即x[N-1]与x[0]相连), ?0', '1' ??'l成, 其中'?' 处可以填?0'?1'. 从T=0开? 每过1单位旉, 整个串会更新一? 某一? 如果上一时刻, ? 以及与它盔R的两? 一共有臛_2?1', 那么q一时刻它变?1', 否则它变?0'. 问共有多种??'的方? 使得在经qT(T<=1000)旉? q有不少于K(K<=N)?1'. 比如'101010'->'010101'->'101010'->...; '11010'->'11101'->'11111'->...
首先Ҏ观察? 两个或两个以上连l相同的位是永远不会变的. 只有01交替的子串才会发生变? 所以Q意一个串都可以看成是若干个Ş?xpy的子串首连接而成, 而且两串的首要相同才能qv? 像[xp1y][yp2x][xp3x][xp4y].... 其中pk?1交替序列, x和y都是一? 可能?0'?1'. 特别?q箋3个相同字W可以看成是xx和xx_v??位重?. 对于一个首֭W固定不变的01交替? 它在T旉后有多少?1'是很Ҏ的. 两头都是0的话, ?101010->0010100->0001000, 每时间减一?; 两头都是1的话cM, 每时间增加一?. 一头是0一?, ??的个数都不变, ?10101->001011->000111.
q样有个算法的雏Ş, cM背包: dp[pos][bit][one]表示: ?到pos-1的子D? 以bitl尾, 且T旉后包含one?的方法数. 如果从pos到某一位pos2-1, 能构造出以bit起始, 以bit2l束的交替串, 那么从状态dp[pos][bit][one]p扩展到dp[pos2][bit2][one+one2], 则把前者加到后者上? 其中one2是pos到pos2-1q个子串T旉?的个? 把原始串复制两遍, p比较方便地处理环.
枚D在原串中首次出现q箋2个相同字W的位置startpos, Ҏ个startpos做一ơ上qDP. 把所有one>=K的方法数加v来即? 此外要先预处理出Ledg[i][b1][j][b2], 即从i到j-1能否构造出以b1开? b2l尾的交替串, 如果? T旉后有多少?1'.
其实整个题就是一道背包DP, 求用若干个短子, 拼出一个权?gt;=K的长子的方法数. 只是模型隐藏得很巧妙. orz...
[背包DP]
]]>
l出若干个方形木板，每个木板有一U颜艌Ӏ现在要选出其中6个，围出一个立方体。问是否可能使{出的立方体，L两个盔R的面颜色不同?br />直接按木板的L分情况讨论就可以Q但是我漏想了一U情况@.@
其实昄Q同一U颜色最多能用两ơ，所以统计每U木板能用的个数之和,sigma(min(count[i],2))Q和不小?则可行?br />
500p CubePacking
l出Ns个边长ؓ1的立方体和Nb个边长ؓL(2<=L<=10Q的立方体。要找一个体U最的长方体，使得可以把所有立方体堆进厅R保证结果不int32?br />正是因ؓ不超int32Q所以可以直接枚举两条棱x,yQ算W?条z的最倹{枚举时循环条g x*x*x <= INF, x*y*y <= INF。计z的最值时要注意除法要向上取整Q而且判断能否把边长ؓL的立方体都放q去的条件是(x/L)*(y/L)*(z/L) >= NbQ如果z了Q要加到_大ؓ止?br />[枚D]
900p CubeBuilding
大小相同的红、绿、蓝色的立方体，分别lR、G、B?R,G,B<=25)。把q些立方体全部搭U木一L堆到N*N(N<=25)的格子棋盘中。可以在L格子中堆L高的立方体。规定一U方案是合法的，如果从北向南看的侧视图中只有一U颜艌Ӏ问一共有多少U堆砌的Ҏ?br />可以先考虑N*1的棋盘，也就是侧视图中棋盘宽度是1。先考虑没有颜色的方块怎么放，再去染色。这样不怎么堆，看到的方块数L{于所有格子堆的最大高度，则需要固定颜色的方块数就个高度，剩下的方块可以Q意染艌Ӏ同理N*N的棋盘，需要固定颜色的方块数等于所有列中需要固定的数量之和。要求的{案是Q先枚D固定方块的数目，把它们染某一U颜Ԍ剩下的方块可以用l合数直接算出有多少U染色方案，乘v来，最后求和?br />关键是要求出每一U固定方块数目的前提下，不考虑颜色Q有多少U堆放方法?br />由前面的讨论知道Q可以先在N*1的棋盘上按行扩展Q需要记录的状态是当前已用的方块敎ͼ当前的最大高度?br />然后利用q个l果按列扩展Q记录的状态是当前已用的方块敎ͼ当前已固定的方块数?br />ps.染色之前的方案数只用求一ơ，之后分别把固定的方块染成3U不同颜Ԍ只要用组合数分别?ơ，加v来就行了?br />O(9*N^5)的算法，旉有点紧?br />[DP]
]]>
[floyd最短\ 二分图最大权匚w]
]]>
电媄院有n行m列的座位, 有一些已l被预订? 求在剩下的位中, 选出同行且相ȝ两个座位的方案数.
可以按行列将已预订的座位排序, 然后Z扫一? 出盔R两个被预订位之间的Ҏ? 最后篏?
也可以用个set记录不能使用的方? 再用没有预订座位的情况下的L案数减去?
500p TheMoviesLevelTwoDivOne
若干部电? 每部电媄有一个加血的时间点. 人看电媄, 每看一分钟掉一点血. 血掉到0q? 问怎样按排序使看的电影部数最? 如果总部数相? 取字典序最的解输?
只有20部电? 状态DP卛_.
Z证字典序, 可以从后往前DP, q样每次转移时新加入的电影都是当前最先看? 保证它先择的是最的, 卌保证字典序最?
[DP]
1000p TheMoviesLevelThreeDivOne
若干部电? A和B两h看每部电q旉分别是A[i], B[i]. 初始安排, 要依ơ把W?,2,..,n部电影放入A或B的待看队列的队尾. A和B各自开始看自己队列中的电媄, 看完一部后, 如果q是另一个h没看q的, 加入它的队列中. 如果期间某h列队IZ, 那么他就l束, 再也不看新电׃. 问有多少U初始安排方? 能A和B都能看完所有电?
首先肯定不会出现一U安排得A和B都卡. 因ؓA卡肯定发生在A看完他所有的电媄之后, 且此时B没看完自q, 所以B肯定不会?
q样可以用L案数2^N分别减去A卡的和B卡的Ҏ? 考虑A卡的情况. 假设A那一整坨东西的时长是sumA, B的第一个东西是tb1, 则A卡的条g?sumA-tb1<0. 否则B看完tb1后把ta1加在sumA后面, q时卡的条g?sumA+ta1)-(tb1+tb2)<0. 依此, 如果在这q程中Q意一ơ卡的条件符? 那么后箋怎么安排都是卡的. 于是用一l状态记录目前ؓ止出现过的最的X-Y, min, q要一l记录当前的X-Y, cur, 以{Uȝ. 转移? 如果把当前电影放qA, 那么min和cur都增加A[i], 因ؓsumA增加? 如果放进B, 那么用cur和B[i]来计新的cur和min.
hint. cur=当前所有电qA[i]的和-B中电qB[i]的和, 新的min=除了新放的电影外所有放q的电媄的A[i]的和-包括新电影在内的B中电qB[i]的和.
ps. 1000的DP都很YD?..
[DP]
]]>