就在今天早上，我的外婆走了。
已经不是第一次经历这种场面……
上一次，是我外公。
那时我还小，还在上幼儿园
一觉醒来就满屋子找不见人，于是在家看电视
然后，等母亲回来就听到了那个噩耗
……
当时我还不怎么懂这意味着什么
直到看着我外公的遗体被火化的时候
看着母亲那种悲痛的情绪，我才明白了一点。
这之后，外婆几年内就患了老年痴呆症
然而今天，在房间外面，通过窗户
看着她被抢救
看着各种仪器的示数不断变化
看着不断有仪器运进去
……
然后，好像是预感到什么一样
他们把我这一辈的都叫去先吃点早餐
我们先是不肯
但是他们强烈要求……
当我们吃完早餐的时候
得到消息
吃完早餐不是回病房，是回家。
……
那种感觉，真是说不出口
心情很沉重很沉重
什么都不太想做
人一生下来，就注定了要归去
我们所能做到的，就只有尽力不让自己后悔
月赛时必须回宿舍zzzzZZZZZZ，于是当时没怎么捉。
我太蒟蒻了T_T
3472暂时还没看题目
3476被虐了一早上，现在在死皮赖脸地看shi哥的题解
【ZOJ3467】
一只3D骑士给定他跳的方法(x,y,z)，问两点间点字典序最小的路径
就是双向BFS，但是那个字典序不太好搞。然后最近学了map就果断使用了
判重时就要注意不是重复就给删掉……而是先比较步数，如果步数一样，则和原来的解一起从父节点link回去比较一下是哪一个的字典序优，如果现在的比较优，那么就把map里的指针指向该结点(相当于把原来那个点删掉，当然是lazy delete)。
因为WA重写了几遍= =，已经疼了，于是直接把两边3步都搜完最后再来判……
于是得到悲壮的8700MS。
Code：https://ideone.com/fqVUE
【ZOJ3468】
送分题。直接dp或者爆搜 T_T。
Code：http://ideone.com/8VheC
【ZOJ3469】
一个一维的数轴上，一个人初始站在X处送外卖，他跑的速度为V^(-1)。然后每个客户由两个元素(x,b)来描述，分别表示其位置以及纠结指数增长率。一个人收到外卖时的纠结指数为增长率*时间。求所有客户的纠结指数之和最小能是多少。
初看题目好像是最小哈密顿回路>_<，其实不然，如果你从X向右最远跑到某个地方，中间的肯定已经顺便送过了。然后时间的增长会增加所有未收到外面的纠结指数……于是乎每一段可以看成是单独的，于是就可以dp了。当然先要把结点按x排个序。
F[i,j,0]表示最左跑到i，最右跑到j，最后停在i上时最小纠结指数之和是多少。
F[i,j,1]表示最左跑到i，最右跑到j，最后停在j上时最小纠结指数之和是多少。
令tmp=b[1]+b[2]+..+b[i-1] + b[j+1]+…+b[n] (这些顾客都是没送到的)
于是
F[i,j,0]=min( F[i+1,j,0]+(tmp+b[i])*(x[i+1]-x[i]) , F[i+1,j,1]+(tmp+b[i])*(x[j]-x[i]) )
F[i,j,1]=min( F[i,j-1,0]+(tmp+b[j])*(x[j]-x[i]) , F[i,j-1,1]+(tmp+b[i])*(x[j]-x[j-1]))
Code：http://ideone.com/IAF8Y
【ZOJ3470】
这个转圈圈很难描述>_<，反正就是找到他变化的规律以后可以得出一个等差数列，然后我二分了一下，利用等差数列求和，找出第几圈的，然后分类讨论。
看着挺复杂，没想到1Y了。
Code：http://ideone.com/mWWUc
【ZOJ3471】
有n个星球，n<=10，然后给出一个邻接矩阵，w[i,j]表示i把j撞爆以后获得w[i,j]这么多分。问最后最多能得多少分？
直接状态压缩dp。F[i]（i用2进制位表示，1表示该星球已经被撞爆，0表示还在）表示i这种状态下的最高得分。转移随意。
Code：http://ideone.com/uv9qP
【ZOJ3472】
T_T还没搞
【ZOJ3473】
F[1,1,1]=1
F[i,j,k]=max(F[i’,j’,k’])+1 其中(i’|i j’|j k’|k 但是i’,j’,k’不等全部等于i,j,k)
求Sum(F[i’,j’,k’)) i’<=i && j'<=j && k'<=k
实际上这个函数就是从1,1,1这个点每次将某位乘一个数，然后变成i,j,k的最长路嘛>_<。
于是F[i,j,k]=1+i分解成素因子的个数+j分解成素因子的个数+k分解成素因子的个数。
显然他们是单独的。令d[i]表示这个数字分解成素因子的个数(可以用筛法求得)，Sum[i]=d[1]+d[2]+…+d[i]
那么ans=
i*j*k（都+1的那一部分）
+Sum[i]*j*k
+Sum[j]*i*k
+Sum[k]*i*j
后面的YY一下就知道了= =
Code：http://ideone.com/wGe5T
【ZOJ3474】
dp一下以后变成这样的题意：有n个对手，你要将他们全部打败，打某个的条件是当前体力值>Limit[i]，打完以后体力-Limit[i]+R[i]。
这个其实和JSOI某题本质是一个样的。这里有师父之前的证明。
首先如果打完会加血的，顺序随意，每次打能打的就行了。
打完了这些以后，下处理打完减血的。
假如给定一个成功的顺序，对于相邻的两个(i,j)，我们围观限制 （S是之前打了一些累积的体力变化值）
init_energe + S > Limit[i] —————–1
init_energe + S – Limit[i] + R[i] > Limit[j] ——————2
如果说(i,j)可以交换成(j,i)那么需要
init_energe + S > Limit[j] //由于-Limit[i]+R[i]<0，所以由上面第二条不等式自动获得
init_engerge+ S -Limit[j]+R[j] > Limit[i] ——————–3
把左边移剩init_energe+S
init_energe+S > Limit[j]+Limit[i]-R[i] ——————-2
init_energe+S > Limit[i]+Limit[j]-R[j] ——————–3
于是令2式右边>=3式右边。(这样必然能满足条件，使得可以交换)
Limit[j]+Limit[i]-R[i] >= Limit[i]+Limit[j]-R[j]
化简后……R[j] >= R[i] 。
就是说原来的顺序，如果满足R[j]<=R[i]，就可以交换，所以任何一个满足的顺序都可以调成R[i]递减的顺序。
于是贪心即可。
Code：http://ideone.com/k8cok
【ZOJ3475】
对于NOIER来说= =，这种程度的最小割大概都是秒杀类型的吧。
一看除了隔开以外没有什么其它要求了，那就是最小割了……
顺便制作了sap的模板。
Code：http://ideone.com/yq3cN
【ZOJ3476】 update@2011.2.17
围观了shi哥的解题报告以后没看懂神马意思= =，后来又问了叉姐，终于懂了。
就是说我们这个包围圈最外围必然是一条轮廓线，然后这条轮廓线实际上就是一个环。然后这个环有没有包含一个点呢？实际上就是判断点是否在多边形内的方法，向上作射线，如果穿过这个环的次数为奇数，那么就在环的包围内。
然后我们枚举环的起点，尝试跑一个环回来，但是我们需要知道我们跑了这个环以后，有哪些点被包围在里面。
我们先对每个在输入中存在的国家向上作射线(包括入侵者国家)，假设，我们枚举的这条外围路径跑去和某条射线相交了，那么对应这条射线的国家的存在性就要xor一下(因为对应的奇偶性变了)。
那么设d[x][y][z]为跑到(x,y)这个格子，状态为z(z是一个2进制数，表示每个国家在不在这个包围圈里面)，这时的最短路径是多少。
然后就spfa转移跑来跑去就行了……最后当然要和起点闭合才能形成合法的包围圈，最后就用d[Start_x][Start_y][z]去更新dp[z]。
现在的dp[z]表示如果要用一个包围圈，把z这个集合中的点，都包围在内，那么至少需要多少代价。
然后dp[z]还不一定是就是对应包围z个国家的最小代价。因为不一定是一个包围圈把它们包起来就行了。
还有可能外面一个大圈，中间有几只入侵者，然后再把它们围起来
所以后面还要一个枚举子集的状态压缩动态规划，来挖空这些中间部分。
T_T，看着挺复杂，其实写起来很简单。1Y了。
Code：http://ideone.com/gAPv1
【地址】https://www.spoj.pl/problems/MOD/
【题目大意】
给定a,p,c让你求满足 a^x = c (mod p)的最小非负整数解
无解输出No solution。
【算法分析】
http://hi.baidu.com/edwardmj/blog/item/c72a7c02eb9a8395e950cdf6.html
其实和这题是一模一样的，但是我当时写的太庛了。现在终于写了一个跑得挺快的。
可以作模板了……
【Result】
12009-02-26 23:07:56Robert Gerbicz accepted 1.64 2.7M
C++
4.0.0-8
22009-08-16 16:34:18Tony Beta Lambda accepted 1.70 2.8M
C
32010-07-27 09:20:10rita accepted 2.19 2.6M
C
42011-02-11 10:09:04cwj accepted
edit run 2.31 3.6M
C++
4.3.2
52011-01-10 10:46:22aekdycoin accepted 2.37 3.5M
C++
4.3.2
62010-05-02 13:18:58sevenkplus accepted 2.84 4.2M
C++
4.0.0-8
72010-07-22 11:24:18●rz accepted 3.02 4.2M
C++
4.0.0-8
82011-01-10 10:13:54aekdycoin accepted 3.10 4.2M
C++
4.0.0-8
92010-02-20 22:31:12Peter Ondrúška accepted 3.35 2.6M
C++
4.0.0-8
102009-09-07 12:46:20watashi accepted 3.65 2.7M
C++
4.0.0-8
【CODE】
#include
typedef long long lld;
const int Size=65535;
struct Hashmap{
struct edge{int y,L;edge *next;}*ls[Size+1],g[Size+10];
int e;
void init(){e=0; memset(ls,0,sizeof(ls));}
void clear(){
for (int i=0;i
}
inline
void add(int y,int L){
if (Find(y)!=-1) return;
g[e].y=y; g[e].L=L;
g[e].next=ls[y&Size];
ls[y&Size]=&g[e++];
}
inline
int Find(int y){
for (edge *t=ls[y&Size];t;t=t->next)
if (t->y==y) return t->L;
return -1;
}
}Hash;
int Power_Mod(lld a,int b,int p){
lld ret=1%p;
while (b){
if (b&1) ret=ret*a%p;
a=a*a%p;
b>>=1;
}
return ret;
}
int gcd(const int a,const int b){return b?gcd(b,a%b):a;}
int Extend_gcd(const int a,const int b,int &x,int &y){
if (!b){
x=1;
y=0;
return a;
}
int ret,t;
ret=Extend_gcd(b,a%b,x,y);
t=x; x=y; y=t-a/b*y;
return ret;
}
int Get(int x,int p,int mul){
int tx,ty,ret;
Extend_gcd(x,p,tx,ty);
ret=(lld)tx*mul%p;
return ret<0?ret+p:ret;
}
int Baby_Step_Giant_Step(int a,int c,int p){
if (c>=p) return -1;
Hash.clear();
a%p;
lld tmp,x;
int i,s,g,plus,Giant_Step;
for (i=0,tmp=1%p;i<=100;tmp=tmp*a%p,i++) if (tmp==c) return i;
for (x=1%p,plus=0;(g=gcd(a,p))>1;plus++){
if (c%g) return -1;
p/=g;
c/=g;
x=x*(a/g)%p;
}
s=(int)(sqrt(p)+1e-8);
for (tmp=1%p,i=0;i
if ( (g=Hash.Find( Get(x,p,c) )) !=-1 ) return g+i;
return -1;
}
int main(){
Hash.init();
int a,c,p;
for (;;){
cin >> a >> p >> c;
if (a+p+c==0) break;
c%=p;
int ans=Baby_Step_Giant_Step(a,c,p);
if (ans==-1) puts("No Solution");
else cout << ans << "n";
}
}
【地址】http://acm.hdu.edu.cn/showproblem.php?pid=3691
【题目大意】
给定一个无向连通图和一个源点，让你选一个汇点，使得源点到汇点的最大流最小。输出这时的最大流流量。
【算法分析】
实际上就是求全局最小割。给的那个源点是废的，因为如果图被分割开了，无论当前这个源点在那一块，总有一个汇点在另外一块。所以可以无视他给的源点。
然后直接套Stoer-Wagner算法就可以了。
推荐资料：http://www.docin.com/p-48578124.html
6edward_mj2000MS688K1683BG++2011-02-10 17:01:10
这个时间太亮了
【CODE】
http://xiudaima.appspot.com/code/detail/4696014
【提交地址】http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=16007
【题目大意】
给定一个有向图G(V,E),|V|<=100,然后边数可以接近完全图。
求一个包含点数最少的强连通分量，并要求这个强连通分量包含点1和点2。
【算法分析】
一开始我和叉姐一致认为，答案应该是这样的(其中有【可怜图】标记的边代表一条包含若干点的路径)：
但是实际上，围观这样一个图，它也可能是答案：
也就是说答案应当由数个环拼接而成的，但是这些环不一定只交于一个点，而有可能交在一条链上。
下面来感性地认识一下。图中的3个环用红圈标起来了。
被【可怜图】所代表的路径其实都是酱油的。关键在于环和环的交接处，也就是图中的每一列上面的链。（一个点也可以看作链）
很容易发现，如果要往后并入环，那么只需要交界处的信息的就可以了。
比如说已经处理了图中的第一个环以后，如果要并入第二个环，我们需要的信息就只有8 -> 3 -> 4这条链。实际上3都不需要了，只要知道这是一条从8出发，到达4的链。然后对于另外一条链，如果要并入这个环，只需要接在8和4上就够了。
所以本质上来说，带【可怜图】的边，以及每一列的链上中间的过程都不重要，所以这些部分可以直接用最短路径代替。
处理时可以建一个数组ins[i][j]，表示从i到j的路径上至少需要多少个点(这个很容易用Floyd实现)，然后直接拼接就可以了。
于是很自然地想到定义状态d[i,j]表示最后以i->j的最短链作为和下一个环的公共部分，并且i->j这条最短链已经并入1点所在的环时最少需要多少个点。然后就是各条链之间转移了。由于每次转移，包含的点必然不减，也就相当于最短路中没有负权边，所以可以利用朴素的dijkstra算法求解。
最终时间复杂度O(n^4) （一共有n^2条最短链，它们之间可能有接近完全图的边）
跑了2730MS……
求更好的算法。
【CODE】http://ideone.com/9uxRj