这绝对是树窝。。全是关于树的题目。。。倒。。
1984.Navigation Nightmare
大意:
就是一个地图。。每次告诉你一个点相对于另一个点的坐标。。然后有一些询问。。
都是问两个点之间的曼哈顿距离是多少。。如果信息不够就输出-1。。
好像有点难。。如果不是动态查询的话只好算出每个点的坐标就可以了。。但这里是动态的。
很麻烦。。我想了想发现是可以用并查集做的。。
对每个点i。F[i]是其父亲。。D[i]是相对于其父亲他的坐标。。
那么在路径压缩的时候可以顺便维护D[i]。。
对于一个点Find一下就可以算出其对于根的坐标。。查询如果根不同则不知道。。
连接的时候记得要转换一下相对的坐标。。
否则就是坐标的曼哈顿距离。。
Code。。
#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
const int maxn=40000;
typedef pair<int,int> pi;
inline int abs(int x){return x<0?-x:x;}
inline pi operator+(const pi&x,const pi&y)
{
return pi(x.first+y.first,x.second+y.second);
}
inline pi operator-(const pi&x,const pi&y)
{
return pi(x.first-y.first,x.second-y.second);
}
inline int dist(const pi&x,const pi&y)
{
return abs(x.first-y.first)+abs(x.second-y.second);
}
pi get(int l,char d)
{
switch(d)
{
case ‘N’:return pi(0,l);
case ‘S’:return pi(0,-l);
case ‘E’:return pi(l,0);
case ‘W’:return pi(-l,0);
}
}
struct data
{
int s,t,l;
char d;
}D[maxn];
struct query
{
int x,y,t,n;
bool operator<(const query&x) const
{return t<x.t;}
}Q[maxn];
int n,m,k;
void init()
{
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++)
scanf("%d %d %d %c",&D[i].s,&D[i].t,&D[i].l,&D[i].d);
scanf("%d",&k);
for(int i=0;i<k;i++)
scanf("%d %d %d",&Q[i].x,&Q[i].y,&Q[i].t),Q[i].n=i;
sort(Q,Q+k);
}
int F[maxn];
pi P[maxn];
void set(int n)
{
for(int i=0;i<n;i++)
F[i]=i,P[i]=pi(0,0);
}
void find(int x)
{
if(x!=F[x])
find(F[x]),P[x]=P[x]+P[F[x]],F[x]=F[F[x]];
}
void Union(int x,int y,pi d)
{
find(x);d=d-P[x];x=F[x];
find(y);d=d+P[y];y=F[y];
F[x]=y;P[x]=d;
}
int ask(int x,int y)
{
find(x);find(y);
if(F[x]!=F[y]) return -1;
return dist(P[x],P[y]);
}
void deal(data x)
{
x.s–;x.t–;
pi d=get(x.l,x.d);
Union(x.s,x.t,d);
}
int main()
{
init();
set(n);
int last=0;
int Ans[maxn];
for(int i=0;i<k;i++)
{
for(int j=last;j<Q[i].t;j++)
{
deal(D[j]);
}
last=Q[i].t;Ans[Q[i].n]=ask(Q[i].x-1,Q[i].y-1);
}
for(int i=0;i<k;i++)
printf("%dn",Ans[i]);
}1985.Cow Marathon
大意:
一颗树，求其中距离最远的两点的距离。。
经典算法。。两次dfs。。
也可以DP。。
水题就不多说了。。。
Code。。
#include<cstdio>
#include<utility>
#include<vector>
#include<cstring>
using namespace std;
typedef pair<int,int> pi;
typedef vector<pi>::iterator it;
const int maxn=40000;
int n,m;
vector<pi> E[maxn];
inline void add(int s,int t,int c)
{
E[s].push_back(pi(t,c));
E[t].push_back(pi(s,c));
}
void init()
{
scanf("%d %d",&n,&m);int s,t,c;char a;
while(m–)
{
scanf("%d %d %d %c",&s,&t,&c,&a);s–;t–;
add(s,t,c);
}
}
int dist[maxn];
bool vis[maxn];
void dfs(int x,int d)
{
vis[x]=true;dist[x]=d;
for(it i=E[x].begin();i!=E[x].end();i++)
if(!vis[i->first])
{
dfs(i->first,d+i->second);
}
}
int find(int t)
{
memset(vis,false,sizeof(vis));
dfs(t,0);int mi=0;
for(int i=1;i<n;i++)
if(dist[i]>dist[mi])
mi=i;
return mi;
}
int main()
{
init();
int t=find(0);
printf("%dn",dist[find(t)]);
}

N久没做sgu了。。。
这道题意思是说给你一个n*m的棋盘每个数或为1或为0，每一个2*2的子矩阵的和都是2。。
求方法数。。
n和m那么大肯定是有公式的。。
先是写了状压DP算了一下。。看出公式是2^m+2^n-2。。
我是这么推导的。。
因为第一行有2^m种放法。。其中除了010101和101010之外。。
第一行一确定其他行也都确定了。。于是就有2^m-2种。。
又如果第一行是010101或101010。。那么第二行也只能选这两种。。
每一行都有两种选择。。于是就是2^n种。。
加一下就是答案了。。。
#include<iostream>
#include<cstring>
using namespace std;
const int maxl=1000;
struct bignum
{
int Q[maxl],last;
bignum()
{
memset(Q,0,sizeof(Q));last=0;
}
void set(int a)
{               
Q[last]=a;
}
int& operator[](int v){return Q[v];}
bignum operator+(bignum&x)
{
bignum ans;ans.last=max(last,x.last);int d=0;
for(int i=0;i<=ans.last;i++)
{
d+=x[i]+Q[i];
ans[i]=d%10;
d/=10;
}
if(d)ans[++ans.last]=d;
return ans;
}
void operator-=(int x)
{   
for(int i=0;i<=last;i++)
{
if(Q[i]>=x) {Q[i]-=x;return;}
else{Q[i]=10+Q[i]-x;x=1;}
}
}
bignum operator*(int x)
{
int d=0;bignum ans;ans.last=last;
for(int i=0;i<=ans.last;i++)
{
d+=Q[i]*x;
ans[i]=d%10;
d/=10;
}
while(d)
{
ans[++ans.last]=d%10;
d/=10;
}
return ans;
}
void operator=(const bignum&x)
{
memmove(Q,x.Q,sizeof(Q));
last=x.last;
}
void print()
{
for(int i=last;i>=0;i–)
cout<<Q[i];
}
}a,b;
int main()
{
int n,m;cin>>n>>m;
if(n<m){int t=n;n=m;m=t;}
b.set(1);
for(int i=1;i<=n;i++)
{
b=b*2;
if(i==m) a=b;
}
a=a+b;
a-=2;
a.print();cout<<endl;
}

https://www.spoj.pl/problems/GSS5/
这道题不难关键是我这个写法。。
实在是太NB了。。（这个烧饼疯了。。）
首先很明显如果y1<x2的话。。
设S为部分和序列。。那么ans=Max(S,x2..y2)-Min(S,x1-1..y1-1..)。。
如果有重叠的话。。分三种情况讨论。。设答案是Ai..Aj
i<x2,ans=Max(S,x2..y2)-Min(S,x1-1..x2-1)
j>y1,ans=Max(S,y1+1..y2)-Min(S,x1-1..y1-1..)
i>=x2&&j<=y 转化成经典问题了。。。
如果直接写3个线段树会很BT。。只写一个的话又浪费时间。。
我的Code中写了个线段树的模板。。然后根据信息直接弄出3个线段树。。NB阿（。。。）

#include<cstdio>
#include<iostream>
#define Renew(x,c) x=max(x,c)
using namespace std;
struct MinNum
{
int Min;
MinNum(int a=0):Min(a){}
MinNum operator+(const MinNum&Rch)
{
MinNum f;
f.Min=min(Min,Rch.Min);
return f;
}
};
struct MaxNum
{
int Max;
MaxNum(int a=0):Max(a){}
MaxNum operator+(const MaxNum&Rch)
{
MaxNum f;
f.Max=max(Max,Rch.Max);
return f;
}
};
struct ContMax
{
int Max,Lmax,Rmax,Sum;
ContMax(int a=0):Max(a),Lmax(a),Rmax(a),Sum(a){}
ContMax operator+(const ContMax&Rch)
{
ContMax f;
f.Lmax=max(Lmax,Sum+Rch.Lmax);
f.Rmax=max(Rch.Rmax,Rch.Sum+Rmax);
f.Sum=Sum+Rch.Sum;
f.Max=max(Max,Rch.Max);
f.Max=max(f.Max,Rmax+Rch.Lmax);
return f;
}
};
template<class info>
class Tree
{
int*A;int L,R;
struct tree
{
tree*Lch,*Rch;
info Ans;
tree(int a=0):Ans(a){}
}*root;
tree* build(int l,int r)
{
if(l==r) return new tree(A[l]);
int mid=(l+r)/2;
tree* T=new tree;
T->Lch=build(l,mid);
T->Rch=build(mid+1,r);
T->Ans=T->Lch->Ans+T->Rch->Ans;
return T;
}
info ask(tree*T,int l,int r,int ll,int rr)
{
if(l==ll and r==rr) return T->Ans;
int mid=(l+r)/2;
if(ll>mid) return ask(T->Rch,mid+1,r,ll,rr);
if(rr<=mid) return ask(T->Lch,l,mid,ll,rr);
return ask(T->Lch,l,mid,ll,mid)+ask(T->Rch,mid+1,r,mid+1,rr);
}
public:
Tree(int A[],int L,int R):A(A),L(L),R(R)
{
root=build(L,R);
}
info operator()(int l,int r)
{
return ask(root,L,R,l,r);
}
};
const int maxn=10000+100,inf=~0U>>1;
void solve()
{
int A[maxn],S[maxn],n;S[0]=0;
cin>>n;for(int i=1;i<=n;i++) scanf("%d",A+i),S[i]=A[i]+S[i-1];
Tree<MaxNum> RMQMax(S,0,n);
Tree<MinNum> RMQMin(S,0,n);
Tree<ContMax> SegTree(A,1,n);
int m,x1,y1,x2,y2;cin>>m;
while(m–)
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);int ans=-inf;
if(x2>y1)
ans=RMQMax(x2,y2).Max-RMQMin(x1-1,y1-1).Min;
else
{
if(y1<y2) Renew(ans,RMQMax(y1+1,y2).Max-RMQMin(x1-1,y1-1).Min);
if(x1<x2) Renew(ans,RMQMax(x2,y2).Max-RMQMin(x1-1,x2-1).Min);
Renew(ans,SegTree(x2,y1).Max);
}
printf("%dn",ans);
}
}
int main()
{
int t;cin>>t;
while(t–) solve();
}

看到句很NB的话。。
书是人类进步的阶梯。。
电子书是人类进步的电梯。。

http://acm.pku.edu.cn/JudgeOnline/problem?id=1988
http://acm.pku.edu.cn/JudgeOnline/problem?id=1989
http://acm.pku.edu.cn/JudgeOnline/problem?id=1990
http://acm.pku.edu.cn/JudgeOnline/problem?id=1991
@@@@1@@@@
。。。想到了WHAT？黑书上的银河英雄传说么。。
小样。。穿上马甲我照样认出你阿。。。
#include<cstdio>
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=30000+100;
int F[maxn],D[maxn],S[maxn];
void set(int n)
{
REP(i,n) F[i]=i,D[i]=0,S[i]=1;
}
void find(int x)
{
if(x!=F[x])
find(F[x]),D[x]+=D[F[x]],F[x]=F[F[x]];
}
void Union(int x,int y)
{
find(x);find(y);
x=F[x];y=F[y];
F[x]=y;D[x]=S[y];S[y]+=S[x];
}
int main()
{
set(maxn);
int P;scanf("%d",&P);
char c;int a,b;
while(P–)
{
scanf("n%c",&c);
if(c==’M’)
scanf("%d %d",&a,&b),Union(a,b);
else
scanf("%d",&a),find(a),printf("%dn",D[a]);
}
}@@@@2@@@@
想了N久。。发现如果想要搞出所有n长的组合的话。。所有数必须能分成两部分。。
一部分能搞出所有n-1长的组合。。另一部分有1～k所有的数。。
又想了一会发现能分成n个包含1~k所有数的部分就能搞出所有n长的排列。。
所以直接上了。。。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100000,maxk=10000;
bool e[maxk]={0};
int n,k;
int main()
{
cin>>n>>k;int t,l=k,ans=0;
for(int i=0;i<n;i++)
{
scanf("%d",&t);t–;
if(!e[t]) l–;
e[t]=true;
if(!l){memset(e,false,sizeof(e));l=k;ans++;}
}
cout<<ans+1<<endl;
}

代码短。。可是想的时间长阿。。。

@@@@3@@@@
从声音大的到声音小的算。。然后再一个个删。。
结果再用数状数组维护一下。。就OK了。。
#include<iostream>
#include<utility>
#include<algorithm>
#define low(i) (i&(-i))
using namespace std;
const int maxn=20000+100;
typedef long long LL;
int N,Pv[maxn],Px[maxn],Rx[maxn];
pair<int,int> A[maxn];
bool cmp1(const int&x,const int&y)
{
return A[x].first<A[y].first;
}
bool cmp2(const int&x,const int&y)
{
return A[x].second<A[y].second;
}
LL S[maxn]={0},C[maxn];
void add(LL C[],int l,int d)
{
for(;l<=N;l+=low(l))
C[l]+=d;
}
LL sum(LL C[],int l)
{
LL ans=0;
for(;l>0;l-=low(l))
ans+=C[l];
return ans;
}
LL sum(LL C[],int l,int r)
{
return sum(C,r)-sum(C,l-1);
}
int main()
{
cin>>N;
for(int i=1;i<=N;i++)
cin>>A[i].first>>A[i].second,Pv[i]=Px[i]=i;
sort(Pv+1,Pv+N+1,cmp1);
sort(Px+1,Px+N+1,cmp2);
for(int i=1;i<=N;i++)
{
Rx[Px[i]]=i;
add(C,i,1);
add(S,i,A[Px[i]].second);
}
LL ans=0;
for(int i=N;i>=1;i–)
{
int t=Pv[i],v=A[t].first,x=A[t].second,u=Rx[t];
ans+=(sum(C,1,u-1)*x-sum(S,1,u-1))*v;
ans+=(sum(S,u+1,N)-sum(C,u+1,N)*x)*v;
add(C,u,-1);
add(S,u,-x);
}
cout<<ans<<endl;
}@@@@4@@@@
这不是宋神牛交作业么？倒。。。
不会不会不会不会。。。写了个LJ贪心暴掉了。。。
@@@@Summary@@@@
2004的OPEN好easy阿。。。
我这种沙茶都搞定了3道。。。

http://acm.pku.edu.cn/JudgeOnline/problem?id=3044
http://acm.pku.edu.cn/JudgeOnline/problem?id=3045
http://acm.pku.edu.cn/JudgeOnline/problem?id=3046
@@@1@@@
考虑一块房子(就是两边都是地。。)
那么其中最矮的一块的高度必然是这一块中最矮的。。
那么贪心的选择自然是让它变得最宽。。然后再往上搭。。。
我直接暴力实现了。。平均是O(nlogn)。。最坏是Ｏ(n^2)。。幸好数据很厚道。。
暴力找最小值。。
官方程序只要栈扫描就ＯＫ了。。我ＳＢ阿。。
#include<iostream>
#include<cstdio>
using namespace std;
const int maxy=500000,maxn=50000;
int w,n;
int H[maxn];
int cal(int i,int j)
{
if(i>j) return 0;
if(i==j) return H[i]>0;
int c=maxy;
for(int o=i;o<=j;o++)
c=min(H[o],c);
int a=i,ans=0;
for(int o=i;o<=j;o++)
if(H[o]==c)
ans+=cal(a,o-1),a=o+1;
ans+=cal(a,j);
if(c) ans++;
return ans;
}
int main()
{
cin>>n>>w;int x;
for(int i=0;i<n;i++)
{
scanf("%d %d",&x,H+i);
}
cout<<cal(0,n-1)<<endl;
}@@@@2@@@@
看两个牛i和i’。。设他们重量和力量分别为A,B,A’,B’..
他们上面的牛总重为Ｓ
假如A+B>A’+B’　那么　A-B’>A’-B
Ｓ
Ａ　Ｂ
Ａ‘　Ｂ’
max(S-B,S+A-B’) i在上面。。
max(S-B’,S+A’-B) i’在上面。。
那么总是i’在上面更好。。。
同理如果A+B=A’+B’。。
那么Ｂ大的在上面好。。。
直接排序就OK了。。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=50000,inf=~0U>>1;
int n;
struct node
{
int w,s;
bool operator<(const node&x) const
{
int a=w+s,b=x.w+x.s;
if(a!=b) return a<b;
return w<x.w;
}
}Q[maxn];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d %d",&Q[i].w,&Q[i].s);
}
sort(Q,Q+n);
int Sum=0,ans=-inf;
for(int i=0;i<n;i++)
{
ans=max(ans,Sum-Q[i].s);
Sum+=Q[i].w;
}
cout<<ans<<endl;
}@@@@3@@@@
这道题让我想到了母函数。。
然后我就直接上母函数了。。。
#include<iostream>
using namespace std;
const int maxn=1000,maxl=100000,Mod=1000000;
struct P
{
int *C;
int n;
P(int n):n(n)
{
C=new int[n+1];
for(int i=0;i<=n;i++)
C[i]=1;
}
int& operator[](int v){return C[v];}
void operator*=(P&x)
{
int*now=new int[n+x.n+1];
for(int i=0;i<=n+x.n;i++) now[i]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=x.n;j++)
{
now[i+j]+=C[i]*x[j];
now[i+j]%=Mod;
}
delete[] C;
C=now;n+=x.n;
}
};
int C[maxn]={0};
int T,A,S,B;
int main()
{
cin>>T>>A>>S>>B;
while(A–)
{
int t;cin>>t;
C[t-1]++;
}
P ans(0);
for(int i=0;i<T;i++)
{
P now(C[i]);
ans*=now;
}
int sum=0;
for(int i=S;i<=B;i++)
sum+=ans[i],sum%=Mod;
cout<<sum<<endl;
}

@@@@1@@@@
水题。。。每行每列建个ＸＸ然后二分图然后最小覆盖集。。
太水不想写。。
@@@@2@@@@
DP阿。。
加入l之后。。
DP[1][l][r]目前在r。。最小的总代价。。
DP[0][l][r]目前在l。。最小的总代价。。
Ans=min(DP[0][0][n-1],DP[1][0][n-1])
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=1000+10,inf=~0U>>1;
int P[maxn];
int DP[2][maxn][maxn];
bool inQ[2][maxn][maxn]={0};
struct node
{
int d,l,r;
node(int d,int l,int r):d(d),l(l),r(r){}
};
queue<node> Q;
inline void Push(int d,int l,int r)
{
inQ[d][l][r]=true;
Q.push(node(d,l,r));
}
inline void Renew(int d,int l,int r,int c)
{
if(DP[d][l][r]>c)
{
DP[d][l][r]=c;
if(!inQ[d][l][r])
Push(d,l,r);
}
}
int n,l;
int main()
{
cin>>n>>l;
for(int i=0;i<n;i++) cin>>P[i];
P[n]=l;n++;
for(int d=0;d<2;d++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
DP[d][i][j]=inf;
sort(P,P+n);
int i=lower_bound(P,P+n,l)-P;
DP[0][i][i]=DP[1][i][i]=0;
Push(0,i,i);Push(1,i,i);
while(Q.size())
{
int d,l,r;
node c=Q.front();Q.pop();inQ[d=c.d][l=c.l][r=c.r]=false;
int cost=DP[d][l][r],num=n-(r-l+1);
if(c.d==0)
{
if(l) Renew(0,l-1,r,cost+num*(P[l]-P[l-1]));
if(r<n-1) Renew(1,l,r+1,cost+num*(P[r+1]-P[l]));
}
else
{
if(l) Renew(0,l-1,r,cost+num*(P[r]-P[l-1]));
if(r<n-1) Renew(1,l,r+1,cost+num*(P[r+1]-P[r]));
}
}
cout<<min(DP[0][0][n-1],DP[1][0][n-1])<<endl;
}@@@3@@@
???怎么没文件的。。
难道要事先搞到程序里面去？靠。。ＢＳ阿。。。

题目来自PKU。。
PKU太强大了。。有差不多200道USACO的月赛题（可以搜索之）。。。
http://acm.pku.edu.cn/JudgeOnline/problem?id=3660 Cow Contest
http://acm.pku.edu.cn/JudgeOnline/problem?id=3661 Running
http://acm.pku.edu.cn/JudgeOnline/problem?id=3662 Telephone Lines
官方题解。。http://ace.delos.com/JAN08
1个半小时A完阿。。病好了状态暴涨阿。。要是NOIP的时候。。（这个烧饼又开始作白日梦了。。
@@@@1@@@@
很容易看出谁强谁弱的关系是传递的。。直接传递闭包。。
那么一个人位置确定就是打败他的人+他打败的人+他自己＝总人数。。
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=100;
int n,m;
bool d[maxn][maxn]={0};
int main()
{
cin>>n>>m;int s,t;
while(m–)
{
cin>>s>>t;s–;t–;
d[s][t]=true;
}
REP(k,n) REP(i,n) REP(j,n) d[i][j]=d[i][j] or (d[i][k] and d[k][j]);
int ans=0;
REP(i,n)
{
int a=0,b=0;
REP(j,n) if(d[j][i]) a++;
REP(j,n) if(d[i][j]) b++;
if(a+b==n-1) ans++;
}
cout<<ans<<endl;
}@@@@2@@@@
暴力DP阿。。还能干WHAT？
D[i]为i开始时那啥啥为0时能跑多远。。
睡大觉:D[i]->D[i+1]..
跑K步。。再休息K分钟（劳逸结合？）。。D[i]+Sum[i..i+j]->D[i+2j]。。
注意答案是D[N+1]（N+1分钟开始的时候就是N分钟结束的时候。。）
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=10000,maxm=500+10,inf=~0U>>1;
int n,m;
int D[maxn],S[maxn];
void init()
{
cin>>n>>m;
REP(i,n) cin>>D[i];
REP(i,n) S[i]=0;
}
inline void Renew(int&x,int c)
{
x=max(x,c);
}
void solve()
{
S[0]=0;
REP(i,n)
{
int cost=S[i];
Renew(S[i+1],cost);
int pos=i,sum=S[i];
for(int j=0;j<m&&pos<n;j++)
{
pos+=2;
sum+=D[i+j];
Renew(S[pos],sum);
}
}
cout<<S[n]<<endl;
}
int main()
{
init();
solve();
}@@@@3@@@@
这个有点意思。。
设F[i][u]是在i点。用了u次特权（就是耍赖不交费。。）。。所需费用的最小值。。
我们共产党与民一心，不搞特权:F[i][u]->F[i][u+1]。。
连接阿。。:设j与i相连。。F[j][u]=max(Cost[i][j],F[i][u]),F[j][u+1]=F[i][u];
用SPFA更新来更新去就OK了。。。
答案是F[N][K]。。。
#include<iostream>
#include<cstdio>
#include<queue>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=1000,inf=~0U>>1;
struct edge
{
int t,c;
edge*next;
edge(int t,int c,edge*n):t(t),c(c),next(n){}
}*E[maxn];
void add(int s,int t,int c)
{
E[s]=new edge(t,c,E[s]);
E[t]=new edge(s,c,E[t]);
}
int N,P,K;
void init()
{
cin>>N>>P>>K;
while(P–)
{
int s,t,c;scanf("%d %d %d",&s,&t,&c);s–;t–;
add(s,t,c);
}
}
struct node
{
int pos,cost;
node(int p,int c):pos(p),cost(c){}
};
bool inQ[maxn][maxn]={0};
int cost[maxn][maxn];
queue<node> Q;
inline void Renew(int p,int u,int c)
{
if(u>K) return;
if(cost[p][u]>c)
{
cost[p][u]=c;
if(!inQ[p][u])
Q.push(node(p,u)),inQ[p][u]=true;
}
}
void solve()
{
REP(i,N) REP(j,K+1) cost[i][j]=inf;
Q.push(node(0,0));cost[0][0]=0;inQ[0][0]=true;
int p,u;
while(Q.size())
{
node c=Q.front();Q.pop();inQ[p=c.pos][u=c.cost]=false;
int get=cost[p][u];
Renew(p,u+1,get);
for(edge*i=E[p];i;i=i->next)
{
Renew(i->t,u,max(get,i->c));
Renew(i->t,u+1,get);
}
}
if(cost[N-1][K]==inf) cout<<-1<<endl;
else cout<<cost[N-1][K]<<endl;
}
int main()
{
init();
solve();
}

https://www.spoj.pl/problems/FPOLICE/

分层图最短路。。spfa。。。
怎么可能这么快0.02s？怀疑数据太水了。。。

#include<iostream>
#include<queue>
#include<vector>
#include<stdio.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=100,maxt=250+10,inf=~0U>>1;
int Time[maxn][maxn],Risk[maxn][maxn];
int dist[maxn][maxt];
bool inQ[maxn][maxt];
int N,T;
struct node
{
    int n,t;
    node(int n,int t):n(n),t(t) {}
};
queue<node> Q;
void solve()
{
    cin>>N>>T;
    REP(i,N) REP(j,N) scanf("%d",&Time[i][j]);
    REP(i,N) REP(j,N) scanf("%d",&Risk[i][j]);
    REP(i,N) REP(j,T+1) dist[i][j]=inf,inQ[i][j]=false;
    dist[0][0]=0;
    Q.push(node(0,0));
    inQ[0][0]=true;
    while(Q.size())
    {
        node cur=Q.front();
        Q.pop();
        inQ[cur.n][cur.t]=false;
        int cost=dist[cur.n][cur.t],get,nt;
        for(int i=0; i<N; i++) if(i!=cur.n)
            {
                if((nt=Time[cur.n][i]+cur.t)>T) continue;
                get=cost+Risk[cur.n][i];
                if(get<dist[i][nt])
                {
                    dist[i][nt]=get;
                    if(!inQ[i][nt])
                    {
                        Q.push(node(i,nt));
                        inQ[i][nt]=true;
                    }
                }
            }
    }
    int Min=inf,x=-1;
    REP(i,T+1)
    if(dist[N-1][i]<Min)
        Min=dist[N-1][i],x=i;
    if(x==-1)
    {
        cout<<-1<<endl;
        return;
    }
    cout<<Min<<" "<<x<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t–) solve();
}

https://www.spoj.pl/problems/MINCOUNT/
。。实际上就是正三角和倒三角重叠部分越多越好。。
那么画个图尝试一下。。感觉重叠部分最大是2/3。。
那么就有1/3需要移动。。。写了个暴搜发现是对的(就是枚举位移。。看重合。。)。。
那么就。。。直接上了。。
圆圈有h*(h+1)/2个。。
那么有h*(h+1)/6个要移动。。可惜不能直接算出来。。要溢出的。。
设h=2a+b,h+1=3c+d;
那么h*(h+1)=6ac+3bc+2ad+bd。。
h*(h+1)/6=ac+(3bc+2ad+bd)/6。。。
就可以避免一出了。。
就是不知道如果6换成一个素数的话。。该怎么搞？

#include<iostream>
#include<stdio.h>
using namespace std;
unsigned long long h,ans,a,b,c,d;

void solve()
{
    scanf("%lld", &h);
    a=h/2;b=h%2;h++;c=h/3;d=h%3;
    ans=a*c+(3*b*c+2*a*d+b*d)/6;
    printf("%lld\n", ans);
}
int main()
{
    int t;cin>>t;
    while(t--)
    {
        solve();
    }
}