SPOJ 2150 SUBSEQ

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。。。

SPOJ GSS1-3

线段树练习题啦。。。

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

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…这速度。。。

SPOJ 151 状态压缩DP

这道题算经典的状压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();
    }
}

sgu 299

排序之后再扫描。。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; }

SPOJ 3

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

SPOJ 2714

http://www.spoj.pl/problems/COWCAR/
实际上我最近做的SPOJ的题目都是一些USACO月赛的老题。。。
感觉USACO月赛的题目跟我们OI是比较贴近的。。
不过中国就是没有美国开放。。连stl都不能用。。
说实话我连heap也不会写。。要是NOIP要用我只好写左偏树了。。
这道题实际上很水。。把所有牛按速度排序。。再一个个处理。。
很明显要把每个牛放到当前能承受值最小的轨道。。放不了就扔掉。。。
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;
}

SPOJ 5271

水题。。直接暴力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;
}

USACO FALL 2003 题目

MS官网上没有了。。。
发这吧。。。
**********************************************************************
GREEN PROBLEMS
**********************************************************************
Four problems numbered 1 through 4
**********************************************************************

PROBLEM 1: Cow Exhibition [Brian Jacokes, 2003]

"Fat and docile, big and dumb, they look so stupid, they aren’t much
fun…"
– Cows with Guns by Dana Lyons

The cows want to prove to the public that they are both smart and fun.
In order to do this, Bessie has organized an exhibition that will be put
on by the cows. She has given each of the N (1 <= N <= 100) cows a
thorough interview and determined two values for each cow: the smartness
Si (-1000 <= Si <= 1000) of the cow and the funness Fi (-1000 <= Fi <=
1000) of the cow.

Bessie must choose which cows she wants to bring to her exhibition. She
believes that the total smartness TS of the group is the sum of the Si’s
and, likewise, the total funness TF of the group is the sum of the Fi’s.
Bessie wants to maximize the sum of TS and TF, but she also wants both of
these values to be non-negative (since she must also show that the cows
are well-rounded; a negative TS or TF would ruin this). Help Bessie
maximize the sum of TS and TF without letting either of these values
become negative.

PROBLEM NAME: smrtfun

INPUT FORMAT:

* Line 1: A single integer N, the number of cows

* Lines 2..N+1: Two space-separated integers Si and Fi, respectively
the smartness and funness for each cow.

SAMPLE INPUT (file smrtfun.in):

5
-5 7
8 -6
6 -3
2 1
-8 -5

OUTPUT FORMAT:

* Line 1: One integer: the optimal sum of TS and TF such that both TS
and TF are non-negative. If no subset of the cows has
non-negative TS and non- negative TF, print 0.

SAMPLE OUTPUT (file smrtfun.out):

8

OUTPUT DETAILS:

Bessie chooses cows 1, 3, and 4, giving values of TS = -5+6+2 = 3 and TF
= 7-3+1 = 5, so 3+5 = 8. Note that adding cow 2 would improve the value
of TS+TF to 10, but the new value of TF would be negative, so it is not
allowed.

**********************************************************************

PROBLEM 2: Milking Grid [Tom Widland, 2003]

Every morning when they are milked, the Farmer John’s cows form a
rectangular grid that is R (1 <= R <= 10,000) rows by C (1 <= C <=
75) columns. As we all know, Farmer John is quite the expert on cow
behavior, and is currently writing a book about feeding behavior in
cows. He notices that if each cow is labeled with an uppercase letter
indicating its breed, the two-dimensional pattern formed by his cows
during milking sometimes seems to be made from smaller repeating
rectangular patterns.

Help FJ find the rectangular unit of smallest area that can be
repetitively tiled to make up the entire milking grid. Note that the
dimensions of the small rectangular unit do not necessarily need to
divide evenly the dimensions of the entire milking grid, as indicated
in the sample input below.

PROBLEM NAME: mgrid

INPUT FORMAT:

* Line 1: Two space-separated integers: R and C

* Lines 2..R+1: The grid that the cows form, with an uppercase letter
denoting each cow’s breed. Each of the R input lines has C
characters with no space or other intervening character.

SAMPLE INPUT (file mgrid.in):

2 5
ABABA
ABABA

OUTPUT FORMAT:

* Line 1: The area of the smallest unit from which the grid is formed

SAMPLE OUTPUT (file mgrid.out):

2

OUTPUT DETAILS:

The entire milking grid can be constructed from repetitions of the
pattern ‘AB’.

**********************************************************************

PROBLEM 3: Popular Cows [Brian Dean, 2003]

Every cow’s dream is to become the most popular cow in the herd. In a
herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <=
50,000) ordered pairs of the form (A, B) that tell you that cow A thinks
that cow B is popular. Since popularity is transitive, if A thinks B is
popular and B thinks C is popular, then A will also think that C is
popular, even if this is not explicitly specified by an ordered pair in
the input. Your task is to compute the number of cows that are
considered popular by every other cow.

PROBLEM NAME: popular

INPUT FORMAT:

* Line 1: Two space-separated integers, N and M

* Lines 2..1+M: Two space-separated numbers A and B, meaning that A
thinks B is popular.

SAMPLE INPUT (file popular.in):

3 3
1 2
2 1
2 3

OUTPUT FORMAT:

* Line 1: A single integer that is the number of cows who are
considered popular by every other cow.

SAMPLE OUTPUT (file popular.out):

1

OUTPUT DETAILS:

Cow 3 is the only cow of high popularity.

**********************************************************************

PROBLEM 4: Beauty Contest [Quynh Tran, 2003]

Bessie, Farmer John’s prize cow, has just won first place in a bovine
beauty contest, earning the title ‘Miss Cow World’. As a result, Bessie
will make a tour of N (2 <= N <= 50,000) farms around the world in order
to spread goodwill between farmers and their cows. For simplicity, the
world will be represented as a two-dimensional plane, where each farm is
located at a pair of integer coordinates (x,y), each having a value in
the range -10,000 … 10,000. No two farms share the same pair of
coordinates.

Even though Bessie travels directly in a straight line between pairs of
farms, the distance between some farms can be quite large, so she wants to
bring a suitcase full of hay with her so she has enough food to eat on
each leg of her journey. Since Bessie refills her suitcase at every farm
she visits, she wants to determine the maximum possible distance she
might need to travel so she knows the size of suitcase she must bring.
Help Bessie by computing the maximum distance among all pairs of farms.

PROBLEM NAME: msworld

INPUT FORMAT:

* Line 1: A single integer, N

* Lines 2..N+1: Two space-separated integers x and y specifying
coordinate of each farm

SAMPLE INPUT (file msworld.in):

4
0 0
0 1
1 1
1 0

OUTPUT FORMAT:

* Line 1: A single integer that is the squared distance between the
pair of farms that are farthest apart from each other.

SAMPLE OUTPUT (file msworld.out):

2

OUTPUT DETAILS:

Farm 1 (0, 0) and farm 3 (1, 1) have the longest distance (square root of
2)

**********************************************************************

USACO FALL 2003题解

为了热身NOIP做了这个比赛。。
Fall 2003
水平有限。。我是沙茶。。
Problem 1:
有限制的背包问题。。
首先把S、B都大于0的选了。。
首先把S、B都小于或等于0的扔掉。。
那么所剩的就是一项正一项负了。。
按照其中的一项从大到小排序。。必然是如下形式。。
S B
+ -
+ -
。。。以(S的正负性为划分线)
-  +
-  +
。。。
设S已经有了HaveS(来源于先前已经选的东西。。肯定为正。。)
对上下两个分别运行背包。。求出上下两个容量各个选择容量时B和的最大值。。
为了方便把下面的那个背包价格S值全部取反。。这样当上面背包S为和X时。。下面的最多为X+HaveS个。。
那么可以枚举上面的背包的S值。并用个变量记录下面的最小值。。若B和的最大值加上原来先前选的B的和大于0的话。。
用于更新最优解。。
P.S实际上直接暴力背包也可以。。但我估计要TLE。。进行一些优化之后可以快N多。。
几个小优化。。
首先若上面S的和为SumS,则不需要考虑下面SumS+HaveS以后的状态。。因为根本不会用到。。
那么上面的的和自然要小。。
故在下面比上面短的时候可以交换上下两个。。(也就是交换S和B的位置)
众所周知DP需要一个序
直接的暴力DP没有考虑到题目的特性而运用了盲目的序。。
而结合题目的特性可以得出更好的序从而更高效的算法俄。。
Problem 2:
好难阿。。应该要用到分治吧。。我不会阿。。教教我阿。。
Promblem 3:
比较水的问题。。首先很明显要求出强连同分量。。然后转化成DAG。。
题目就是求一个节点到其他所有节点都有路径。。
因为没有环。。故一个节点如果有入度那么一定不能到达射向他的那个顶点。。不然就有环了。。
故只有没有入度的节点可能满足条件。。
如果有两个或以上的话。。那么这两个节点必不能互达。。故无解
如果有一个的话。。那个节点就是答案了。。
Problem 4:
OI中数据范围不一样的题目真不是一道题目阿。。
题目就是求N个点中最长的两点间距离。。假如N<1000的话直接暴力就OK了。。可惜N<50000
先求出凸包。。那么最长距离一定在凸包上。。
尽管平均意义上凸包上的点为N的三次方根的数量级。。那么直接枚举凸包上的点对就是N的三分之二次方。。
可惜那是平均意义上的。。很容易就可以构造出所有点都在凸包上的BT数据。。显然不行。。
实际上求凸包上的最远点利用对重点可以做到O(N)但我不会。。
我发现凸包上的点的距离是有单峰性的。。故可以用ternary查找其最值。。是logn的。。
加上排序。。还是NlogN。。勉强过吧。。

Page 2 of 512345