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();
    }
}

早上起来习惯性的去刷题。。
刷了两道发现NOIP已经过去了。。
发呆30秒。。想不出还可以做WHAT。。。
于是接着刷题。。。

NOIP 2009总结教训。。。
这次实在是太失败啦。。考试的时候发烧了。
头很昏。。结果悲剧死。。
第一题。。无视算了。。但是莫名其妙错了一个点。。。
第二题算法应该对但是写的太次了TLE了5个点。。(我直接超暴力分解质因数。。太SB了。。至少也生成个素数表的。。)
第三题看错了题目以为是任何一个点出发都可以。。。结果写了1个半小时的强连通。。一分也没有。。赛后改了下就AC了。。。
第四题时间不够了写了暴力搜索。。本来是能拿40的。。结果最后的时候我不知道是神经短路了还是智商错乱了。。加了一句flcose(fout)。。
结果。。。CE了。。。
现在医院里躺着实在是郁闷死。。但是一个人失败也就罢了。。要是失败后还没有教训就是SB了。。
总结一下教训阿。。。
网上OJ做的太多了。。一般都直接交的WA了再改的。。
导致我检查算法，做测试数据的能力基本为0哎，第二题如果我写个做大数据的程序我就可以立马发现会TLE了。。
但是我太懒了。。以后要多培养一点做数据的经验。。。
题目都会看错。。你说我SB不SB。。不过大概可能是发烧了的缘故吧。。脑子都不清楚了。。
奇怪了星期五晚上还是好好的。。怎么现在就烧到39了呢。。我悲剧就悲剧在星期五晚上太兴奋。。
到处找大牛讨论。。染上了跨市病毒。。。
最后考试快结束的时候我眼前似乎已经一片空白了。。。连编译一下都忘了。。
算了。。机会还有很多。。老子明年又是一条好汉阿。。。
以后的路又该怎么走呢。。。可能我日子过的太顺了吧。。NOIP前感觉自己天下无敌了（太SB了）。。
结果就悲剧了。。难道这就是传说中的嚣张被雷劈？。。很有可能。。
但我参加这类比赛的经验还是太少了。。。网上比赛数据是很多的。。
弄点BOI阿。。CEOI阿。。之类的题目多做一点实战。。或许就不会那么SB了吧。。
还有就是比赛心态的问题。。我看到卷子之后。。头脑发昏。。
差点就高呼一声这次400分神牛是我了。。结果只有140。。。比赛的时候实际上是很"顺"的。。
不怎么熟悉的强连通也调出来了。。结果我就被麻痹了。。比赛后还说肯定有300。。。
悲剧阿。。。
P.S第四题这种BT搜索题总算A掉了。。用了改顺序+最优化剪枝+数独问题的传统剪枝。。最后还卡了下时。。哎。。明年再说了。。我还要中考呢。。祝福大家NOIP都取得好成绩。。别跟我这样悲剧阿。。
我得到寒假才有时间搞OI了。。

Sum[i..j]=S[j]-S[i-1]…

所以一个个插入。。直接用MAP。。

慢的吓人。。。

应该用Hash的。。。不过懒的写了。。

#include<iostream>#include<cstdio>#include<map>#define REP(i,n) for(int i=0;i<n;i++)using namespace std;typedef long long LL;typedef map<LL,int>::iterator It;int t;void solve(){ scanf("[^/n]"); int n;scanf("%d",&n); LL s=0,ans=0,t; map<LL,int> M; M[0]=1; REP(i,n) { scanf("%lld",&t);s+=t; It a=M.find(s-47); if(a!=M.end()) ans+=(*a).second; a=M.find(s); if(a!=M.end()) (*a).second++; else M[s]=1; } cout<<ans<<endl;}int main(){ cin>>t; while(t–) { solve(); }}5.8s。。。

线段树练习题啦。。。

都很水的样子。。不过由于我直接写指针了。。速度实在是。。。

1…

#include<iostream>#define REP(i,n) for(int i=0;i<n;i++)#define Renew(x,c)x=max(x,c)using namespace std;typedef long long LL;const int maxn=60000,maxv=maxn*4,inf=~0U>>2;int A[maxn],n;struct Tree{ LL Max,Lmax,Rmax,Sum; Tree(){} Tree(int M,int L,int R,int S):Max(M),Lmax(L),Rmax(R),Sum(S){Lch=Rch=0;} Tree* Lch,*Rch; }*root;inline void Update(Tree*F,Tree*Lch,Tree*Rch){ F->Sum=Lch->Sum+Rch->Sum; F->Lmax=max(Lch->Lmax,Lch->Sum+Rch->Lmax); F->Rmax=max(Rch->Rmax,Rch->Sum+Lch->Rmax); F->Max=max(max(Lch->Max,Rch->Max),Lch->Rmax+Rch->Lmax);}Tree* build(int l,int r){ if(l==r) return new Tree(A[l],A[l],A[l],A[l]); Tree* now=new Tree; int mid=(l+r)/2; now->Lch=build(l,mid);now->Rch=build(mid+1,r); Update(now,now->Lch,now->Rch); return now;}Tree* ask(Tree*T,int l,int r,int first,int last){ if(l==first&&r==last) return T; int mid=(l+r)/2; if(first>mid) return ask(T->Rch,mid+1,r,first,last); if(last<=mid) return ask(T->Lch,l,mid,first,last); Tree* ans=new Tree; Update(ans,ask(T->Lch,l,mid,first,mid),ask(T->Rch,mid+1,r,mid+1,last)); return ans;}int main(){ cin>>n; REP(i,n) scanf("%d",A+i); root=build(0,n-1); int q,s,t;cin>>q; REP(i,q) { scanf("%d %d",&s,&t);s=max(s,1);t=min(t,n); printf("%lldn",ask(root,0,n-1,s-1,t-1)->Max); } }4.1s…这速度。。。

这道题算经典的状压DP了。。

DP[S][P]表示完成了S集合的任务，现在在第P个任务的落脚点。。。

那么直接推就OK了。。

#include<iostream>
#include<string.h>
#include<queue>
#define REP(i,n) for(int i=0;i<n;i++)
#define Renew(x,c) x=min(x,c)
#define floyd(d) REP(k,n) REP(i,n) REP(j,n) Renew(d[i][j],d[i][k]+d[k][j]);
using namespace std;
const int maxn=120,inf=~0U>>3,maxb=13;
int n,m,b,cnt=0;
int dist[maxn][maxn];
int Go[maxb+1],Reach[maxb+1];

void init(){
    cin>>n>>m>>b;b--;cnt=0;
    REP(i,n) REP(j,n) dist[i][j]=(i==j?0:inf);
    while(m--) {
        int s,t,c;cin>>s>>t>>c;s--;t--;
        dist[s][t]=dist[t][s]=min(c,dist[s][t]);
    }
    int z;cin>>z; while(z--) {
        int s,t,c;cin>>s>>t>>c;s--;t--; while(c--) {
            Go[cnt]=s;Reach[cnt]=t;cnt++;
        }
    }
    Reach[cnt]=b;
}

int dp[1<<maxb][maxb+1];

struct node{
    int f,p;
    node(int f,int p):f(f),p(p){}
};

void solve(){
    floyd(dist); memset(dp,0,sizeof(dp));
    queue<node> Q; Q.push(node(0,cnt)); while(Q.size()){
        node cur=Q.front();Q.pop();
        int cost=dp[cur.f][cur.p];
        for(int i=0;i<cnt;i++)if(!(cur.f&(1<<i))) {
            int nf=cur.f|(1<<i); int get=cost+dist[Reach[cur.p]][Go[i]]+dist[Go[i]][Reach[i]];
            if(dp[nf][i]==0||dp[nf][i]>get) dp[nf][i]=get,Q.push(node(nf,i));
        }
    }
    int ans=inf; REP(i,cnt) Renew(ans,dp[(1<<cnt)-1][i]+dist[Reach[i]][b]); cout<<ans<<endl;
}5

int main(){
    int t;cin>>t; while(t--) {
        init(); solve();
    }
}