早上起来习惯性的去刷题。。
刷了两道发现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();
    }
}

排序之后再扫描。。SB死了。。。#include<iostream>#include<string>#include<algorithm>#include<string.h>using namespace std;int n;const int maxn=1000;const int maxl=520;struct bignum{ int Q[maxl],last; bignum(){memset(Q,0,sizeof(Q));last=0;} void Read() { string a;cin>>a;last=a.size()-1; for(int i=0;i<=last;i++) Q[i]=a[last-i]-‘0’; } void Write() { for(int i=last;i>=0;i–) cout<<Q[i]; } bool operator<(const bignum&x) const { if(last!=x.last) return last<x.last; for(int i=last;i>=0;i–) { if(Q[i]<x.Q[i]) return true; if(Q[i]>x.Q[i]) return false; } return false; } bignum operator+(const bignum&x) const { bignum n; n.last=max(x.last,last);int d=0; for(int i=0;i<=n.last;i++) { d+=x.Q[i]+Q[i]; n.Q[i]=d%10; d/=10; } if(d) n.Q[++n.last]=d; return n; }}A[maxn];int main(){ cin>>n; for(int i=0;i<n;i++) A[i].Read(); sort(A,A+n); for(int i=0;i+2<n;i++) if(A[i+2]<(A[i]+A[i+1])) { A[i].Write();cout<<" ";A[i+1].Write();cout<<" "; A[i+2].Write();cout<<endl; return 0; } cout<<"0 0 0"<<endl; }

这道题只能用brainfuck之类的BT语言做。。。
你可能会想，都快NOIP了那个SB去做这种无聊题目。。
你说对了。。我就是那个SB。。
++++++++++++++++++++++++[->>>>>>>>>>>++++++++++[->>,—————————-
——————–<<[->>>>>>>>>>+<<<<<<<<<<]>>>>[-]+>[-]>>[-]+<<<<<<<>>>>>>>>>
>]++++++++++[-[-<<<<<<<<<<+>>>>>>>>>>]<<<<<<<<<<]<<<<<<<<<<>>,<<>>>>>>>>>><<<<<<
<<<<>>>>>>>>>>+++++[->>>>>,————————————————<<<<<
[->>>>>>>>>>+<<<<<<<<<<]>>>>>>>>>>]+++++[-[-<<<<<<<<<<+>>>>>>>>>>]<<<<<<<<<<]<<<
<<<<<<<>>,<<>>>>>>>>>><<<<<<<<<<++++++[-[->>>>>>>>>>+<<<<<<<<<<]>>>>>>>>>>>>>>>>
>>+<<<<<<<<<<<<<<<<<+++++[-[->>>>>>>>>>+<<<<<<<<<<]>>>>>>>>>>>>>>[<<<->>>>]>[<]<
<<<[>>>>>>[-]<<<<<]>[<]>>[<<<+>>>>]>[<]>>[->>>>>>>>>>+<<<<<<<<<<]<<<<<<<]>>>>>>>
>>>>>>>>>>[>[-]+<-]><<<<<<<<<<[->>>>>>>>>>[-]+<<<<<<<<<<]<<<<<<<<+++++[-[-<<<<<<
<<<<+>>>>>>>>>>]>>>>[->>>>>>>>>>+<<<<<<<<<<]<<<<<<<<<<<<<<]<>>>>>>>>>>]>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>++++++++++++++++++++++++++++++
++++++++++++++++++.[-]<++++++++++.[-]<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
<<<<<<<<<<<<<<<++++++[-[-<<<<<<<<<<+>>>>>>>>>>]<<<<<<<<<<]<]

在ＳＰＯＪ上逛的时候看到了Query on a tree居然一共有５个版本。。
I,II,III,IV,V。。太ＮＢ了。。
我只知道I和II使用路径剖分的。。II要用树套树。。
其他我就囧了。。。

http://www.spoj.pl/problems/COWCAR/
实际上我最近做的SPOJ的题目都是一些ＵＳＡＣＯ月赛的老题。。。
感觉ＵＳＡＣＯ月赛的题目跟我们ＯＩ是比较贴近的。。
不过中国就是没有美国开放。。连stl都不能用。。
说实话我连heap也不会写。。要是ＮＯＩＰ要用我只好写左偏树了。。
这道题实际上很水。。把所有牛按速度排序。。再一个个处理。。
很明显要把每个牛放到当前能承受值最小的轨道。。放不了就扔掉。。。
Code。。
我为了图方便把所有数取负了。。。
#include<queue>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<functional>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxm=50000;
int N,M,D,L;
int S[maxm];
void init()
{
cin>>N>>M>>D>>L;
REP(i,N) scanf("%d",S+i);
sort(S,S+N);
}
int main()
{
init();
priority_queue<int> Q;
REP(i,M) Q.push(-L);
int ans=0;
for(int i=0;i<N;i++)
{
int cur=-Q.top();
if(cur>S[i])
continue;
Q.pop();cur+=D;Q.push(-cur);ans++;
}
cout<<ans<<endl;
}

水题。。直接暴力DP。。。
dp(pos,last)表示当前在pos。。上一次拿了last。最多能拿多少钱。。
Code。。
#include<iostream>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=2010,maxlast=1010;
int dp[maxn][maxlast]={0};
int C[maxn],n;
void init()
{
cin>>n;
REP(i,n) REP(j,n/2+1)
dp[i][j]=-1;
for(int i=0;i<n;i++)
{
cin>>C[i];
C[i]+=i?C[i-1]:0;
}
}
int DP(int i,int last)
{
int rest=C[n-1]-C[i-1];
last<<=1;
if(n-i-1<=last)
return rest;
if(dp[i][last]!=-1)
return dp[i][last];
int get,ans=0;
for(int take=1;take<=last;take++)
{
get=rest-DP(i+take,take)+C[i+take]-C[i-1];
ans=max(ans,get);
}
return dp[i][last]=ans;
}
int main()
{
init();
cout<<DP(0,1)<<endl;
}