2014
02-23

Relax! It’s just a game

You: What’s the score? Did I miss much?

Me: It’s 2-1 for elAhli and the second half just started. The first half was quite boring.

You: Who scored first? elAhli or ezZamalek?

Me: What difference does it make?

You: Big difference! I can predict the outcome of the match if I knew the order of which goals were scored in the first half.

Me: What do you mean?

You: It’s 2-1 for elAhli, right? One of three things could have happened: elAhli scored two goals then ezZamalek scored; Or, elAhli scored its first goal, then ezZamalek, then elAhli again; Or, ezZamalek scored first, then elAhli scored its two goals.

Me: So?!! I still don’t understand what difference does that make? It’s still 2-1 for elAhli! Why don’t you just relax and let us continue watching the game in peace.

You: You don’t understand!! I believe the probability of who’ll win depends on the order of how goals were scored. Now I have to predict the outcome for 3 possibilities.

Me: And what if the score was 3-2? What would you have done then?

You: I would have to work for 5 different possibilities. No?

Me: Of course not! The number of possibilities isn’t always equal to the sum.

You: Can you tell me when will it be equal to the sum?

Me: You’re a programmer, why don’t you write a program that counts the number of possibilities and compare it to the sum?

You: I don’t have the time, I want to watch the match. Besides, I have nine other problems to worry about.

Me: I’ll give you a hint. The possibilities will be equal to the sum only if one of the teams scored a certain number of goals.

Your program will be tested on one or more test cases. Each test case specifies two natural numbers (A and B ) (separated by one or more spaces) representing the score of the first half. No team will be able to score more than 10 goals. The last line of the input file contains two -1′s (which is not part of the test cases.)

Your program will be tested on one or more test cases. Each test case specifies two natural numbers (A and B ) (separated by one or more spaces) representing the score of the first half. No team will be able to score more than 10 goals. The last line of the input file contains two -1′s (which is not part of the test cases.)

2 1
1 0
-1 -1

2+1=3
1+0=1

1<n<10^5 显然直接单源最短路径的djkstra会爆内存,只能用SPFA了.

#include <cstdio>
#include <map>
#include <cstring>
#include <vector>
using namespace std;
#define inf 9999999
const int maxn=10000+5;
const int maxm=100+10;
struct Node
{
int to,val;
Node(int x,int y):to(x),val(y){}
};
int g[maxm][maxm],st[maxm],dist[maxn],que[maxn];
bool mark[maxn];
map<int,int>Map;
vector<Node>edge[maxn];
int n,h;
void SPFA(int v)
{
for(int i=1; i<=n; i++) dist[i]=inf,mark[i]=0;
dist[v]=0;
int front=0,back=0;
que[back++]=v;
mark[v]=true;
while(front!=back)
{
int u=que[front++];
if(front==maxn) front=0;
mark[u]=false;
for(int i=0; i<edge[u].size(); i++)
{
int to=edge[u][i].to;
int val=edge[u][i].val;
if(dist[to]>dist[u]+val)
{
dist[to]=dist[u]+val;
if(!mark[to])
{
mark[to]=true;
que[back++]=to;
if(back==maxn) back=0;
}
}
}
}
for(int i=1; i<=n; i++)
if(dist[i]<=600)
g[Map[v]][Map[i]]=1;
}
void floyd()
{
for(int k=0; k<=h+1; k++)
for(int i=0; i<=h+1; i++)
for(int j=0; j<=h+1; j++)
if(g[i][j]>g[i][k]+g[k][j])
g[i][j]=g[i][k]+g[k][j];
}
int main()
{
while(~scanf("%d",&n)&&n)
{
Map.clear();
for(int i=1; i<=n; i++) edge[i].clear();
scanf("%d",&h);
for(int i=1; i<=h; i++)
{
scanf("%d",&st[i]);
Map[st[i]]=i;
}
st[0]=1;st[h+1]=n;
Map[1]=0;Map[n]=h+1;
int m;
scanf("%d",&m);
while(m--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
edge[u].push_back(Node(v,w));
}
for(int i=0; i<=105; i++)
for(int j=0; j<=105; j++)
if(i!=j) g[i][j]=inf;
else g[i][j]=0;
for(int i=1; i<=h; i++)
SPFA(st[i]);
floyd();
if(g[0][h+1]==inf) printf("-1\n");
else printf("%d\n",g[0][h+1]-1);
}
return 0;
}

1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。

2. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧

3. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.