无聊了。。做个索引吧。。就当整理一下
加个推荐程度吧。。1到5。。越高越好
SGU：
103 最短路   3
111 高精度开平方  2
130 Catalan数或DP 1
134 树形DP 2
149 树形DP 3
165 构造 3
175 递归 2
187 动态数列维护，数据结构题 4
199 DP 2
200 高斯消元 3
242 网络流 2.5
247（算法） 很有意思的数学题，是以前IMO的题目 4
247（程序）
299 水题，排序之后扫描 1
302 模拟题，很水 1.5
318 并查集。 2.5
327 哈密顿路 4.5
339 暴力模拟，题目很唬人 2.5
347-357（1）
347-357（2）
362
375
377
395
415
417 高等数学+找规律 4.5
441 矩阵乘法 3.5
455
463
476 容斥原理外加一点优化 4
479
484
488 水题，DP 2
489 DP 3
491 很有技巧的枚举 4.5
499 正确估计复杂度，然后枚举答案判定 3.5
502 暴力dfs 2
507 用set维护答案，启发式合并，正确估计复杂度才敢写。。 4
PS。不知不觉居然写了这么多。。唉。。老了。。

你还再用该死的dev吗？
你还再为dev字体难看，调试麻烦而烦恼吗？
赶紧去尝试一下CodeBlocks吧。。必dev不知道要好看多少。。
http://www.codeblocks.org/home

就是说给你一个序列。第0项是1其余由上一项决定。。
如果第一个与前面的数重复的数的编号小于2000000。。就输出这个编号。。否则就输出-1.。
分析：一开始我当然想的是用hash，set之类的数据结构来搞定。。结果TLE的跟鬼一样。。
后来我在wiki上看到了寻找循环节的O（1）空间算法。。这才恍然大悟。。真的很神奇。
Link：Cycle Finding
简单的介绍一下吧。。设Fx是序列中的第x个数。。弄两个指针。。一个指向Fi。。一个指向F2*i。。
每次讲i加一，那么第一个指针前进1个。第二个前进两个。直到Fi=F2*i了。。i就是一个循环节了。。
然后从第0个数开始推起。。找出第一个x使Fx=Fx+i。。
然后再从x往后推。。找到第一个与其相等的。就是答案了。。
Code：

#include<iostream>
using namespace std;
typedef long long ll;
ll A,B,C;
const int maxn=2e6;
ll next(const ll&x)
{
return (A*x+x%B)%C;
}
void init()
{
cin>>A>>B>>C;
}
bool solve()
{
ll l=next(1),r=next(l);
for(int i=1;i<=maxn+1;i++)
{
if(l==r) break;
l=next(l);
r=next(r);r=next(r);
}
if(l!=r) return false;
l=1;int f=0;
while(l!=r)
{
l=next(l);
r=next(r);
f++;
}
r=next(l);
for(int n=f+1;n<=maxn;n++)
{
if(l==r){cout<<n<<endl;return true;}
r=next(r);
}
return false;
}
int main()
{
init();
if(!solve())cout<<-1<<endl;
}
本高亮代码使用codeHl生成，

Link：题目
就是说上次我说的那个PKU月赛题。。Tarjan离线就是NB啊。。
那个保存2的乘方的既耗空间，又耗时间。。
而Tarjan是线性的。。
这道题目就是说给你一个颗边不代权，点代权的树，有个商人要旅行。每次从一个点到另一个点，点权表示商品的价格。。商人最多进货和卖出一次，求他的最大收入(可以不交易)。。
这道题就需要维护一个并查集中顶点到并查集中父亲的路径的4个值了，最大点权，最小点权，从它到并查集中父亲一路的最大收入，从并查集父亲到它一路的最大收入。。
这是可以合并的。。然后求的时候。。终点到lca的信息要反一下。。
Code：

#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int inf=1<<20;
const int maxn=50000;int n;
const int maxm=maxn;int m;
struct edge
{
int t;
edge(int _t):t(_t){}
};
struct queryLca
{
bool s;
int t,n;
queryLca(int _t,int _n,bool _s):t(_t),n(_n),s(_s){}
};
struct query
{
int a,b,n;
query(int _a,int _b,int _n):a(_a),b(_b),n(_n){}
};
struct info
{
int Min,Max,Pro,RPro;
info(int v=0):Min(v),Max(v),Pro(0),RPro(0){}
info R()
{
info ans=*this;
swap(ans.Pro,ans.RPro);
return ans;
}
void Merge(const info& o)
{
Pro=max(Pro,o.Pro);
Pro=max(Pro,o.Max-Min);
RPro=max(RPro,o.RPro);
RPro=max(RPro,Max-o.Min);
Min=min(Min,o.Min);
Max=max(Max,o.Max);
}
};
vector<edge> E[maxn];
vector<queryLca> Lca[maxn];
vector<query> Query[maxn];
typedef vector<edge>::iterator eit;
typedef vector<queryLca>::iterator lit;
typedef vector<query>::iterator qit;
info Ans[maxm];
void add_edge(int s,int t)
{
E[s].pb(edge(t));
E[t].pb(edge(s));
}
void add_lca(int s,int t,int n)
{
Lca[s].pb(queryLca(t,n,true));
Lca[t].pb(queryLca(s,n,false));
}
info P[maxn];
int F[maxn];
void set()
{
rep(i,n) F[i]=i;
}
int find(int x)
{
int tmp=F[x];
if(F[x]!=x)
F[x]=find(F[x]),P[x].Merge(P[tmp]);
return F[x];
}
void Union(int i,int j)
{
F[j]=i;
}
bool vis[maxn]={0};
void dfs(int x)
{
vis[x]=true;
for(eit i=E[x].begin();i!=E[x].end();i++)if(!vis[i->t])
dfs(i->t),Union(x,i->t);
for(lit i=Lca[x].begin();i!=Lca[x].end();i++)
{
if(vis[i->t])
{
if(i->s)
Query[find(i->t)].pb(query(x,i->t,i->n));
else
Query[find(i->t)].pb(query(i->t,x,i->n));
}
}
for(qit i=Query[x].begin();i!=Query[x].end();i++)
{
find(i->a);find(i->b);
info&t=Ans[i->n];
t=P[i->a];t.Merge(P[i->b].R());
}
}
void init()
{
scanf("%d",&n);int s,t,c;
set();
for(int i=0;i<n;i++)
scanf("%d",&c),P[i]=info(c);
for(int i=0;i<n-1;i++)
{
scanf("%d %d",&s,&t);
add_edge(s-1,t-1);
}
scanf("%d",&m);int a,b;
for(int i=0;i<m;i++)
{
scanf("%d %d",&a,&b);
add_lca(a-1,b-1,i);
}
}
void solve()
{
dfs(0);
for(int i=0;i<m;i++)
printf("%dn",Ans[i].Pro);
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
init();
solve();
}
本高亮代码使用codeHl生成，

Link：Problem
大意是给一颗代权树。Q个询问。每个询问是两个节点。
让你回答这两个节点之间路径上的最长边和最短边。
跟PKU月赛的某题有点像。
使用离线算法类tarjan算法。
在并查集中对每个节点维护一个到父亲（并查集中的父亲）的路径上最长和最短的边。。
那么在路径压缩的时候也可以顺便合并。。
在求出两个节点之间的lca之后。。等dfs回到了这个lca。。就有充分的信息了。。
可以很方便的计算答案
PS我太依赖stl了。。这样下去怎么行
Code：

#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int inf=~0U>>1;
const int maxn=100000;int n;
const int maxm=maxn;int m;
struct edge
{
int t,c;
edge(int _t,int _c):t(_t),c(_c){}
};
struct queryLca
{
int t,n;
queryLca(int _t,int _n):t(_t),n(_n){}
};
struct query
{
int a,b,n;
query(int _a,int _b,int _n):a(_a),b(_b),n(_n){}
};
struct info
{
int Min,Max;
info():Min(inf),Max(-inf){}
info(int v):Min(v),Max(v){}
void print() const{cout<<"{"<<Min<<","<<Max<<"}";}
void Merge(const info& o)
{
//print();cout<<" + ";o.print();cout<<endl;
Min=min(Min,o.Min);
Max=max(Max,o.Max);
}
};
vector<edge> E[maxn];
vector<queryLca> Lca[maxn];
vector<query> Query[maxn];
typedef vector<edge>::iterator eit;
typedef vector<queryLca>::iterator lit;
typedef vector<query>::iterator qit;
info Ans[maxm];
void add_edge(int s,int t,int c)
{
E[s].pb(edge(t,c));
E[t].pb(edge(s,c));
}
void add_lca(int s,int t,int n)
{
Lca[s].pb(queryLca(t,n));
Lca[t].pb(queryLca(s,n));
}
info P[maxn];
int F[maxn];
void set()
{
rep(i,n) F[i]=i;
}
int find(int x)
{
int tmp=F[x];
if(F[x]!=x)
F[x]=find(F[x]),P[x].Merge(P[tmp]);
return F[x];
}
void Union(int i,int j,int c)
{
F[j]=i;
P[j]=info(c);
}
bool vis[maxn]={0};
void dfs(int x)
{
vis[x]=true;//cout<<x<<endl;
for(eit i=E[x].begin();i!=E[x].end();i++)if(!vis[i->t])
dfs(i->t),Union(x,i->t,i->c);
for(lit i=Lca[x].begin();i!=Lca[x].end();i++)
{
if(vis[i->t])
{
Query[find(i->t)].pb(query(x,i->t,i->n));
//cout<<find(i->t)<<" "<<x<<" "<<i->t<<endl;
}
}
for(qit i=Query[x].begin();i!=Query[x].end();i++)
{
find(i->a);find(i->b);
info&x=Ans[i->n];
x=P[i->a];x.Merge(P[i->b]);
}
}
void init()
{
scanf("%d",&n);int s,t,c;
set();
for(int i=0;i<n-1;i++)
{
scanf("%d %d %d",&s,&t,&c);
add_edge(s-1,t-1,c);
}
scanf("%d",&m);int a,b;
for(int i=0;i<m;i++)
{
scanf("%d %d",&a,&b);
add_lca(a-1,b-1,i);
}
}
void solve()
{
dfs(0);
for(int i=0;i<m;i++)
printf("%d %dn",Ans[i].Min,Ans[i].Max);
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
init();
solve();
}
本高亮代码使用codeHl生成，
话说我3点半了闲着无聊居然开始刷题了。。

昨天十分无聊。。看了看一个最近比较流行的新语言scala。。真是太强了。。
scala=Java+函数语言。。
我花了些时间学习了一下。。
scala有一些十分强悍的语言特性。。

1.
函数可以做参数。。这个java是不可以的。。C++和C是可以的。但没有scala这么漂亮。。
比如一个函数 是从Int到Int的（比如乘方啊。。*2啊之类的）。。
就是 (Int) => Int。。
如果是二元的。。就是
(Int,Int) => Int。。
用=>符号十分的形象。。
2.
a.method(b) <=> a method b
就是说一切这样的函数都是操作符。。比如对象a有个方法叫insert。。
那么 a.insert(x) <=> a insert x
3.
跟Java接轨。。可以使用一切java的库。。并且编出来的东西可以在JVM上运行。。
比Java更强大并且代码远远简单于Java。。效率差不多（一样的恶心。。）
4.
在面向对象方面也比java纯粹。。java中基本类型不是对象。。
scala中基本类型也是对象。是Any的子类。。
发一个scala的快速排序的代码：
5.
继承了Java的优良传统。。速度慢的跟鬼一样
函数式：
def sort(xs: Array[Int]): Array[Int] = {
if (xs.length <= 1) xs
else {
val pivot = xs(xs.length / 2)
Array.concat(
sort(xs filter (pivot >)),
xs filter (pivot ==),
sort(xs filter (pivot <)))
}
}
过程式。。感觉跟pascal有点像
def sort(xs: Array[Int]) {
def swap(i: Int, j: Int) {
val t = xs(i); xs(i) = xs(j); xs(j) = t
}
def sort1(l: Int, r: Int) {
val pivot = xs((l + r) / 2)
var i = l; var j = r
while (i <= j) {
while (xs(i) < pivot) i += 1
while (xs(j) > pivot) j -= 1
if (i <= j) {
swap(i, j)
i += 1
j -= 1
}
}
if (l < j) sort1(l, j)
if (j < r) sort1(i, r)
}
sort1(0, xs.length 1)
}
还有HelloWorld的程序。。
object HelloWorld {
def main(args: Array[String]) {
println("Hello, world!")
}
}还有一些就看scala的官网
http://www.scala-lang.org/ 上面有很多学习资料
还有wiki上的页面。。

一时兴起写了了个Java里的SPFA算法。。
。。C++0MSAC的题目我用Java要2000MS
不过我滥用了Java的特性。。类都开泛滥了。。一个SPFA开了五个类
题目是PKU 2387

import java.util.*;
class Edge
{
int t,c;
Edge(int _t,int _c)
{t=_t;c=_c;}
}
class Graph
{
int n;
List< List<Edge> > E;
Graph(int _n)
{
n=_n;
E=new ArrayList< List<Edge> >(n);
for(int i=0;i<n;i++) E.add(new ArrayList<Edge>());
}
void addEdge(int s,int t,int c)
{
E.get(s).add(new Edge(t,c));
E.get(t).add(new Edge(s,c));
}
Iterator<Edge> adj(int v)
{return E.get(v).iterator();}
}
class MyQueue extends ArrayDeque<Integer>
{
int n;boolean[] inQ;
MyQueue(int _n)
{
n=_n;
inQ=new boolean[n];
}
void put(int x)
{
if(!inQ[x])
{
super.add(x);
inQ[x]=true;
}
}
int get()
{
int t=super.poll();
inQ[t]=false;
return t;
}
}
class Spfa
{
final int inf=1<<29;
Graph G;
int[] dist;
MyQueue Q;
Spfa(Graph _G,int vs)
{
G=_G;
dist=new int[G.n];Arrays.fill(dist,inf);Q=new MyQueue(G.n);
dist[vs]=0;Q.put(vs);
while(!Q.isEmpty())
{
int t=Q.get();int cost=dist[t];
Iterator<Edge> i=G.adj(t);
while(i.hasNext())
{
Edge e=i.next();
int ncost=cost+e.c;
if(ncost<dist[e.t])
{
dist[e.t]=ncost;
Q.put(e.t);
}
}
}
}
int distTo(int v)
{
return dist[v];
}
}
public class Main
{
static Scanner in=new Scanner(System.in);
static public void main(String[] args)
{
int m=in.nextInt(),n=in.nextInt();
Graph G=new Graph(n);int s,t,c;
for(int i=0;i<m;i++)
{
s=in.nextInt();
t=in.nextInt();
c=in.nextInt();
G.addEdge(s-1,t-1,c);
}
Spfa solve=new Spfa(G,0);
System.out.println(solve.distTo(n-1));
}
}
本高亮代码使用codeHl生成，

专为百度空间设计。。非常漂亮和方便。。
在此表达对

比赛的时候没有A掉。。后来看了ikki大牛的提示算是明白了。。
由于n<=50想怎么写都行。。只要别暴力搜就可以了囧。。
首先枚举每条边。算出删掉这条边后从这条边的起点到2的最短路。。
为了方便可以把所有边的都反过来。。这样就都变成2到这个起点的最短路了。。
然后用spfa来更新答案。。就是说定义dist[i]从i节点运用最优策略到2的路程。。
那么关于j节点新的代价就是
删:deletecost of edge(j,i) /has been calculated before
不善:dist[i]+cost of edge(j,i)
那么新的代价就是这两个最大值。。
然后用这个来更新j节点。。跟平常的spfa一样就可以了。。
最后dist[0]就是所求了。。
Code：

#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 <queue>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

//Powered by [KawigiEdit] 2.0!
本高亮代码使用codeHl生成，

God。。不知道怎么回事上次我直接变蓝色了。。结果这次进Div 1了。。
我很紧张。。结果发现第一题一看就是直接二分的题目。。然后我一高兴就直接写了。。
结果悲剧了。。实际上第一题是很triky的。。比如说“0000”这种test。。根本没想到。。
我房间一个人强到其他题一分没有。。光challenge就525。。我们房间基本上被cha光了。。
第二题反而是最水的。。直接模拟就可以了。。一开始我觉得n^2*S的复杂度会超。。
结果一点事都没有。。寒。。
第三题我没有想出算法。。写了个SB程序上去。。test1都过不了的那种。。
居然没人来cha我。。搞的我很想自cha。。结果不行的。。
我现在还是不知道怎么做啊。。感觉spfa式的递推应该是可以的。。
不过很难想出怎么写。。
我发现了想得分cha别人也是一种好途径。。尤其是一种题目BT到大家都想不出一些SB的case的时候。。
就可以爽了。。
最后99名。。就第二题做出来了。。变黄色了。。