Rain on your Parade
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 655350/165535 K (Java/Others)
Total Submission(s): 1310 Accepted Submission(s): 373
Problem Description
You’re giving a party in the garden of your villa by the sea. The party is a huge success, and everyone is here. It’s a warm, sunny evening, and a soothing wind sends fresh, salty air from the sea. The evening is progressing just as you had imagined. It could be the perfect end of a beautiful day.
But nothing ever is perfect. One of your guests works in weather forecasting. He suddenly yells, “I know that breeze! It means its going to rain heavily in just a few minutes!” Your guests all wear their best dresses and really would not like to get wet, hence they stand terrified when hearing the bad news.
You have prepared a few umbrellas which can protect a few of your guests. The umbrellas are small, and since your guests are all slightly snobbish, no guest will share an umbrella with other guests. The umbrellas are spread across your (gigantic) garden, just like your guests. To complicate matters even more, some of your guests can’t run as fast as the others.
Can you help your guests so that as many as possible find an umbrella before it starts to pour?
Given the positions and speeds of all your guests, the positions of the umbrellas, and the time until it starts to rain, find out how many of your guests can at most reach an umbrella. Two guests do not want to share an umbrella, however.
Input
The input starts with a line containing a single integer, the number of test cases.
Each test case starts with a line containing the time t in minutes until it will start to rain (1 <=t <= 5). The next line contains the number of guests m (1 <= m <= 3000), followed by m lines containing x- and y-coordinates as well as the speed si in units per minute (1 <= si <= 3000) of the guest as integers, separated by spaces. After the guests, a single line contains n (1 <= n <= 3000), the number of umbrellas, followed by n lines containing the integer coordinates of each umbrella, separated by a space.
The absolute value of all coordinates is less than 10000.
Output
For each test case, write a line containing “Scenario #i:”, where i is the number of the test case starting at 1. Then, write a single line that contains the number of guests that can at most reach an umbrella before it starts to rain. Terminate every test case with a blank line.
Sample Input
2
1
2
1 0 3
3 0 3
2
4 0
6 0
1
2
1 1 2
3 3 2
2
2 2
4 4
Sample Output
Scenario #1:
2
Scenario #2:
2
Source
Recommend
lcy
先用匈牙利算法的DFS版本，一直超时，
后改用Hopcroft-Carp算法，顺利AC。
超时版代码：、
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
#define eps 1e-6
#define MAXN 3005
struct Node1
{
int x,y,s;
}guests[MAXN];
struct Node2
{
int x,y;
}um[MAXN];
double dis(Node1 a,Node2 b)
{
double x=a.x-b.x;
double y=a.y-b.y;
return sqrt(x*x+y*y);
}
int uN,vN;
int g[MAXN][MAXN];
bool used[MAXN];
int linker[MAXN];
bool dfs(int u)
{
int v;
for(v=0;v<vN;v++)
if(g[u][v]&&!used[v])
{
used[v]=true;
if(linker[v]==-1||dfs(linker[v]))
{
linker[v]=u;
return true;
}
}
return false;
}
int hungary()
{
int res=0;
int u;
memset(linker,-1,sizeof(linker));
for(u=0;u<uN;u++)
{
memset(used,0,sizeof(used));
if(dfs(u)) res++;
}
return res;
}
int main()
{
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
int n,m,t,i,j;
int T,iCase=0;
scanf("%d",&T);
while(T--)
{
iCase++;
scanf("%d",&t);
scanf("%d",&m);
for(i=0;i<m;i++)
scanf("%d%d%d",&guests[i].x,&guests[i].y,&guests[i].s);
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d",&um[i].x,&um[i].y);
uN=0;vN=n;
bool cnt;
memset(g,0,sizeof(g));
for(i=0;i<m;i++)
{
cnt=false;
for(j=0;j<n;j++)
{
if(dis(guests[i],um[j])/guests[i].s-t<eps)
{
g[i][j]=1;cnt=true;
}
}
if(cnt) uN++;
}
printf("Scenario #%d:\n%d\n\n",iCase,hungary());
}
return 0;
}
AC代码：
#include<stdio.h>
#include<queue>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
#define eps 1e-6
const int MAXN=3005;
const int INF=1<<28;
int g[MAXN][MAXN],Mx[MAXN],My[MAXN],Nx,Ny;
int dx[MAXN],dy[MAXN],dis;
bool vst[MAXN];
struct Node1
{
int x,y,s;
}guests[MAXN];
struct Node2
{
int x,y;
}um[MAXN];
double distance(Node1 a,Node2 b)
{
double x=a.x-b.x;
double y=a.y-b.y;
return sqrt(x*x+y*y);
}
bool searchP()
{
queue<int>Q;
dis=INF;
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
for(int i=0;i<Nx;i++)
if(Mx[i]==-1)
{
Q.push(i);
dx[i]=0;
}
while(!Q.empty())
{
int u=Q.front();
Q.pop();
if(dx[u]>dis) break;
for(int v=0;v<Ny;v++)
if(g[u][v]&&dy[v]==-1)
{
dy[v]=dx[u]+1;
if(My[v]==-1) dis=dy[v];
else
{
dx[My[v]]=dy[v]+1;
Q.push(My[v]);
}
}
}
return dis!=INF;
}
bool DFS(int u)
{
for(int v=0;v<Ny;v++)
if(!vst[v]&&g[u][v]&&dy[v]==dx[u]+1)
{
vst[v]=1;
if(My[v]!=-1&&dy[v]==dis) continue;
if(My[v]==-1||DFS(My[v]))
{
My[v]=u;
Mx[u]=v;
return 1;
}
}
return 0;
}
int MaxMatch()
{
int res=0;
memset(Mx,-1,sizeof(Mx));
memset(My,-1,sizeof(My));
while(searchP())
{
memset(vst,0,sizeof(vst));
for(int i=0;i<Nx;i++)
if(Mx[i]==-1&&DFS(i)) res++;
}
return res;
}
int main()
{
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
int n,m,t,i,j;
int T,iCase=0;
scanf("%d",&T);
while(T--)
{
iCase++;
scanf("%d",&t);
scanf("%d",&m);
for(i=0;i<m;i++)
scanf("%d%d%d",&guests[i].x,&guests[i].y,&guests[i].s);
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d",&um[i].x,&um[i].y);
Nx=m;Ny=n;
memset(g,0,sizeof(g));
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(distance(guests[i],um[j])/guests[i].s-t<eps)
{
g[i][j]=1;
}
}
}
printf("Scenario #%d:\n%d\n\n",iCase,MaxMatch());
}
return 0;
}
/**********************************************
二分图匹配（Hopcroft-Carp的算法）。
初始化：g[][]邻接矩阵
调用：res=MaxMatch(); Nx,Ny要初始化！！！
时间复杂大为 O(V^0.5 E)
适用于数据较大的二分匹配
***********************************************/
const int MAXN=3001;
const int INF=1<<28;
int g[MAXN][MAXN],Mx[MAXN],My[MAXN],Nx,Ny;
int dx[MAXN],dy[MAXN],dis;
bool vst[MAXN];
bool searchP()
{
queue<int>Q;
dis=INF;
memset(dx,-1,sizeof(dx));
memset(dy,-1,sizeof(dy));
for(int i=0;i<Nx;i++)
if(Mx[i]==-1)
{
Q.push(i);
dx[i]=0;
}
while(!Q.empty())
{
int u=Q.front();
Q.pop();
if(dx[u]>dis) break;
for(int v=0;v<Ny;v++)
if(g[u][v]&&dy[v]==-1)
{
dy[v]=dx[u]+1;
if(My[v]==-1) dis=dy[v];
else
{
dx[My[v]]=dy[v]+1;
Q.push(My[v]);
}
}
}
return dis!=INF;
}
bool DFS(int u)
{
for(int v=0;v<Ny;v++)
if(!vst[v]&&g[u][v]&&dy[v]==dx[u]+1)
{
vst[v]=1;
if(My[v]!=-1&&dy[v]==dis) continue;
if(My[v]==-1||DFS(My[v]))
{
My[v]=u;
Mx[u]=v;
return 1;
}
}
return 0;
}
int MaxMatch()
{
int res=0;
memset(Mx,-1,sizeof(Mx));
memset(My,-1,sizeof(My));
while(searchP())
{
memset(vst,0,sizeof(vst));
for(int i=0;i<Nx;i++)
if(Mx[i]==-1&&DFS(i)) res++;
}
return res;
}
文章来源: http://www.cnblogs.com/kuangbin/archive/2011/08/12/2135898.html
猜数字
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 852 Accepted Submission(s): 481
Problem Description
猜数字游戏是gameboy最喜欢的游戏之一。游戏的规则是这样的：计算机随机产生一个四位数，然后玩家猜这个四位数是什么。每猜一个数，计算机都会告诉玩家猜对几个数字，其中有几个数字在正确的位置上。
比如计算机随机产生的数字为1122。如果玩家猜1234,因为1,2这两个数字同时存在于这两个数中，而且1在这两个数中的位置是相同的，所以计算机会告诉玩家猜对了2个数字，其中一个在正确的位置。如果玩家猜1111,那么计算机会告诉他猜对2个数字，有2个在正确的位置。
现在给你一段gameboy与计算机的对话过程，你的任务是根据这段对话确定这个四位数是什么。
Input
输入数据有多组。每组的第一行为一个正整数N(1<=N<=100)，表示在这段对话中共有N次问答。在接下来的N行中，每行三个整数A,B,C。gameboy猜这个四位数为A，然后计算机回答猜对了B个数字，其中C个在正确的位置上。当N=0时，输入数据结束。
Output
每组输入数据对应一行输出。如果根据这段对话能确定这个四位数，则输出这个四位数，若不能，则输出"Not sure"。
Sample Input
6
4815 2 1
5716 1 0
7842 1 0
4901 0 0
8585 3 3
8555 3 2
2
4815 0 0
2999 3 3
0
Sample Output
Author
lwg
#include<stdio.h>
bool check1(int num1,int num2,int t)
{
int a[4],b[4];
int c[4];
int i,j;
for(i=0;i<4;i++)
{
a[i]=num1%10;
num1/=10;
b[i]=num2%10;
num2/=10;
c[i]=0;
}
int m=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(c[j]==0&&a[i]==b[j])
{
m++;
c[j]=1;
break;
}
if(m==t) return true;
else return false;
}
bool check2(int num1,int num2,int t)
{
int a[4],b[4];
int i,j;
int m=0;
for(i=0;i<4;i++)
{
a[i]=num1%10;
num1/=10;
b[i]=num2%10;
num2/=10;
if(a[i]==b[i]) m++;
}
if(m==t) return true;
else return false;
}
int main()
{
int a[101],b[101],c[101];
int cnt,res;
int n,i,j;
while(scanf("%d",&n),n)
{
for(i=0;i<n;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]);
cnt=0;
for(i=1000;i<=9999;i++)
{
for(j=0;j<n;j++)
{
if(check1(i,a[j],b[j])==false)break;
if(check2(i,a[j],c[j])==false)break;
}
if(j>=n)
{
cnt++;
res=i;
}
if(cnt>=2)break;
}
if(cnt==0||cnt>=2) printf("Not sure\n");
else printf("%d\n",res);
}
return 0;
}
文章来源: http://www.cnblogs.com/kuangbin/archive/2011/08/12/2136005.html
大连赛区(大连理工大学)
网络赛(DLUT-OJ)：2011.09.03 12:00-17:00
现场赛时间：2011.09.24-25
竞赛主页：http://icpc.dlut.edu.cn
上海赛区(复旦大学)
网络赛(HDOJ)：2011.09.10 12:00-17:00
现场赛时间：2011.10.15-16
竞赛主页：http://www.cs.fudan.edu.cn/computer/acm/
北京赛区(北京邮电大学)
网络赛(BUPT-OJ)：2011.09.18 12:00-17:00
现场赛时间：2011.10.22-23
竞赛主页：http://acm.bupt.edu.cn
成都赛区(成都东软学院)
网络赛(HDOJ)：2011.09.11 12:00-17:00
现场赛时间：2011.11.05-06
竞赛主页：
福州赛区(福建师范大学)
网络赛(HDOJ)：2011.10.07 12:00-17:00
现场赛时间：2011.11.19-20
竞赛主页：http://acm.fjnu.edu.cn/icpc 文章来源: http://www.cnblogs.com/kuangbin/archive/2011/08/12/2136029.html
爆头
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 752 Accepted Submission(s): 275
Problem Description
gameboy是一个CS高手，他最喜欢的就是扮演警察，手持M4爆土匪的头。也许这里有人没玩过CS，有必要介绍一下“爆头”这个术语：所谓爆头，就是子弹直接命中对方的头部，以秒杀敌人。
现在用一个三维的直角坐标系来描述游戏中的三维空间（水平面为xoy平面，z轴正方向是上方）。假设游戏中角色的头是一个标准的球。告诉你土匪的身高，头部半径，所站位置的坐标；gameboy所控警察的身高，头部半径，所站位置的坐标，以及枪头所指方向的单位向量。gameboy所控警察所握的是M4，抢瞄准时枪膛中的子弹跟视线基本同线，我们忽略它们的距离，就当成同线。由于土匪手持AK47,所以他是很嚣张地正立着。而警察手持M4，正在瞄准，由于瞄准时身体微弯，视线从头心出发，他头部的实际高度比正立时低10%。
你的任务就是，计算gameboy在这一刻扣下扳机，能否爆土匪的头。注意：这里忽略子弹的直径和重力作用，也就是说子弹是无限小的，弹道是一条笔直的射线，警察与土匪间没有障碍物。并且只要子弹擦到头部，哪怕是边缘，也算爆头。
Input
测试数据的第一行有一个正整数T，表示有T组测试数据。每组数据的第一行有五个实数，h1,r1,x1,y1,z1，分别表示土匪的身高，头部半径以及所站的位置。第二行有八个实数，h2,r2,x2,y2,z2,x3,y3,z3，分别表示警察的身高，头部半径，所站位置，以及枪头所指方向的方向向量。
Output
每一组输入数据对应一行输出。如果能爆土匪的头，输出"YES",否则输出"NO"。
Sample Input
2
1.62 0.1 10.0 10.0 10.0
1.80 0.09 0.0 0.0 0.0 1.0 1.0 1.0
1.62 0.1 0.0 0.0 0.0
1.80 0.09 10.0 10.0 10.0 -1.0 -1.0 -1.0
Sample Output
Author
lwg
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
#define eps 1e-6
struct Node
{
double x,y,z;
}line[2];
double chaji(Node a,Node b)//计算两个向量的叉积
{
double x1=a.x;
double y1=a.y;
double z1=a.z;
double x2=b.x;
double y2=b.y;
double z2=b.z;
double x=y1*z2-z1*y2;
double y=z1*x2-x1*z2;
double z=x1*y2-y1*x2;
return sqrt(x*x+y*y+z*z);
}
int main()
{
double h1,r1,x1,y1,z1;
double h2,r2,x2,y2,z2,x3,y3,z3;
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lf%lf%lf%lf%lf",&h1,&r1,&x1,&y1,&z1);
scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&h2,&r2,&x2,&y2,&z2,&x3,&y3,&z3);
line[0].x=x3;line[0].y=y3;line[0].z=z3;
line[1].x=x1-x2;line[1].y=y1-y2;
line[1].z=z1+h1-r1-(h2*0.9+z2-r2);
double d=chaji(line[0],line[1]);
d/=sqrt(x3*x3+y3*y3+z3*z3);
if(d-r1<eps) printf("YES\n");
else printf("NO\n");
}
return 0;
}
很简单，虽然也感觉做得没有很完美，但是AC了，也没有怎么优化了！！
文章来源: http://www.cnblogs.com/kuangbin/archive/2011/08/12/2136185.html
"Accepted today?"
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1476 Accepted Submission(s): 649
Problem Description
Do you remember a sentence "Accepted today?" Yes, the sentence is mentioned frequently in lcy's course "ACM Programming"!
The contest is still in progress this moment. How excited it is! You, smart programmer, must have AC some problems today. "Can I get copper medal, silver medal, or even golden medal?" Oh, ha-ha! You must be considering this question. And now, the last problem of this contest comes.
Give you all submitting data in the contest, and tell you the number of golden medals, silver medals and copper medals; your task is to output someone's contest result.
Easy? Of course! I t is the reason that I designed the problem.
When you have completed this contest, please remember that sentence〃 Accepted today?〃兒
Input
Input contains multiple test cases. Each test case starts with five numbers N (4 =< N <= 130 -- the total number of attendees), G, S, C (1<=G<=S<=C<N --G, S, C denoting the number of golden medals, silver medals and copper medals respectively) and M (0<M<=N). The next N lines contain an integer P (1<=P<=8 --number of problems that have been solved by someone) and a time T(for example,"02:45:17", meaning 2 hours and 45 minutes and 17 seconds consumed according to contest rules) each. You can assume that all submit data are different.
A test case starting with 0 0 0 0 0 terminates input and this test case should not to be processed.
Output
For each case, print a sentence in a line, and it must be one of these sentences:
Accepted today? I've got a golden medal :)
Accepted today? I've got a silver medal :)
Accepted today? I've got a copper medal :)
Accepted today? I've got an honor mentioned :)
Note:
You will get an honor mentioned if you can't get copper medal, silver medal or golden medal.
Sample Input
10 1 2 3 6
2 02:45:17
2 02:49:01
2 03:17:58
2 03:21:29
4 07:55:48
3 04:25:42
3 06:57:39
2 02:05:02
2 02:16:45
2 02:41:37
0 0 0 0 0
Sample Output
Accepted today? I've got a silver medal :)
Author
lcy
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
struct Node
{
int num;
char time[15];
}students[150];
bool cmp(Node a,Node b)
{
if(a.num>b.num) return 1;
else if(a.num==b.num&&strcmp(a.time,b.time)<0) return 1;
else return 0;
}
int main()
{
int n,G,S,C,m;
int num1,i;
char time1[15];
while(scanf("%d%d%d%d%d",&n,&G,&S,&C,&m))
{
if(n==0&&G==0&&S==0&&C==0&&m==0) break;
for(i=0;i<n;i++)
{
scanf("%d%s",&students[i].num,&students[i].time);
}
num1=students[m-1].num;
strcpy(time1,students[m-1].time);
sort(students,students+n,cmp);
for(i=0;i<n;i++)
{
if(students[i].num==num1&&strcmp(students[i].time,time1)==0) break;
}
i++;
if(i<=G) printf("Accepted today? I've got a golden medal :)\n");
else if(i<=G+S) printf("Accepted today? I've got a silver medal :)\n");
else if(i<=G+S+C) printf("Accepted today? I've got a copper medal :)\n");
else printf("Accepted today? I've got an honor mentioned :)\n");
}
return 0;
}
文章来源: http://www.cnblogs.com/kuangbin/archive/2011/08/12/2136483.html
Liang Guo Sha
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 214 Accepted Submission(s): 162
Problem Description
Maybe you know “San Guo Sha”, but I guess you didn’t hear the game: “Liang Guo Sha”!
Let me introduce this game to you. Unlike “San Guo Sha” with its complicated rules, “Liang Guo Sha” is a simple game, it consists only four cards, two cards named “Sha”, and the other named “Shan”.
Alice and Bob are good friends, and they’re playing “Liang Guo Sha” now. Everyone has two cards: a “Sha” and a “Shan”. Each round, everyone choose a card of his/her own, and show it together(Just show the selected card, do not need to put it away). If both of them choose “Sha”, then Alice gets A points, and Bob loses A points; if both of them choose “Shan”, then Alice gets B points, and Bob loses B points; otherwise, Bob gets C points, and Alice loses C points.
Both Alice and Bob wants to get points as many as possible, they thought a optimal strategy: Calculating a percentage of choosing card “Sha” in order to ensure that even the opponent uses the optimal strategy, he/she can still get a highest point exceptation.
Here is the question, if both Alice and Bob use the optimal strategy to make their points higher, what is the expectation point which Alice can get in a round?
Input
Several test case, process to EOF.
Each test case has only a line, consists three positive integers: A, B, C respectively.
1 <= A, B, C <= 100000
Output
Each test case just need to output one line, the expectation point that Alice can get. Round to 6 decimal points.
Sample Input
Sample Output
0.200000 0.000000
Hint
In test case 1, both Alice and Bob calculated the best percentage of choosing “Sha”, and the their percentage are the same: 70%. If Bob do not choose the best percentage, his strategy might be targetd. For example, if Bob choose 100%, then Alice can change her percentage to 100%, Bob might lose many points. Bob is clever, so he won’t do that.
Source
Recommend
lcy
题目意思难懂，其实想通了也很简单。
就是一个人得分的数学期望不要受另外一个人的影响！
设Alice取sha的概率为x,Bob取sha的概率为y。
则Alice得分的数学期望为：
x*y*A+(1-x)*(1-y)*B-x*(1-y)*C-y*(1-x)*C
=(1-x)*B-x*C+(x*A-(1-x)*B+x*C-(1-x)*C)y
令y的系数为0可以解得x，
x=(B+C)/(A+B+2*C)
故数学期望为：(1-x)*B-x*C
程序：
#include<stdio.h>
int main()
{
int A,B,C;
while(scanf("%d%d%d",&A,&B,&C)!=EOF)
{
double x=(double)(B+C)/(A+B+C*2);
printf("%.6lf\n",(1-x)*B-x*C);
}
return 0;
}
文章来源: http://www.cnblogs.com/kuangbin/archive/2011/08/13/2137237.html
题目链接：http://poj.org/problem?id=3264
作者：kuangbin（转载请注明出处，谢谢！！）
更多详细文章，请访问博客：www.cnblogs.com/kuangbin
ACM POJ 3264 Balanced Lineup
这到题目是线段树的练习题目。
很简单，练练手！！
AC程序：
/*
POJ 3264 Balanced Lineup
题目意思：给定Q（1<=Q<=200000)个数A1,A2,```,AQ,
多次求任一区间Ai-Aj中最大数和最小数的差
*/
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAXN 200005
#define INF 10000000
int nMax,nMin;//记录最大最小值
struct Node
{
int l,r;//区间的左右端点
int nMin,nMax;//区间的最小值和最大值
}segTree[MAXN*3];
int a[MAXN];
void Build(int i,int l,int r)//在结点i上建立区间为(l,r)
{
segTree[i].l=l;
segTree[i].r=r;
if(l==r)//叶子结点
{
segTree[i].nMin=segTree[i].nMax=a[l];
return;
}
int mid=(l+r)>>1;
Build(i<<1,l,mid);
Build(i<<1|1,mid+1,r);
segTree[i].nMin=min(segTree[i<<1].nMin,segTree[i<<1|1].nMin);
segTree[i].nMax=max(segTree[i<<1].nMax,segTree[i<<1|1].nMax);
}
void Query(int i,int l,int r)//查询结点i上l-r的最大值和最小值
{
if(segTree[i].nMax<=nMax&&segTree[i].nMin>=nMin) return;
if(segTree[i].l==l&&segTree[i].r==r)
{
nMax=max(segTree[i].nMax,nMax);
nMin=min(segTree[i].nMin,nMin);
return;
}
int mid=(segTree[i].l+segTree[i].r)>>1;
if(r<=mid) Query(i<<1,l,r);
else if(l>mid) Query(i<<1|1,l,r);
else
{
Query(i<<1,l,mid);
Query(i<<1|1,mid+1,r);
}
}
int main()
{
int n,q;
int l,r;
int i;
while(scanf("%d%d",&n,&q)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
Build(1,1,n);
for(i=1;i<=q;i++)
{
scanf("%d%d",&l,&r);
nMax=-INF;nMin=INF;
Query(1,l,r);
printf("%d\n",nMax-nMin);
}
}
return 0;
}
另外附一参考程序：
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
#define MY_MIN 99999999
#define MY_MAX -99999999
struct CNode
{
int L,R;
int nMin,nMax;
CNode * pLeft, * pRight;
};
int nMax, nMin;
CNode Tree[1000000];
//CNode Tree[20];
int nCount = 0;
void BuildTree(CNode * pRoot, int L,int R)
{
pRoot->L = L;
pRoot->R = R;
pRoot->nMin = MY_MIN;
pRoot->nMax = MY_MAX;
if ( L != R) {
nCount ++;
pRoot->pLeft = Tree + nCount;
nCount ++;
pRoot->pRight = Tree + nCount;
BuildTree( pRoot->pLeft, L, ( L + R )/2);
BuildTree( pRoot->pRight, (L + R) / 2 + 1,R);
}
}
void Insert( CNode * pRoot , int i,int v)
{
if( pRoot->L == i && pRoot->R == i ) {
pRoot->nMin = pRoot->nMax = v;
return;
}
pRoot->nMin = _cpp_min(pRoot->nMin,v);
pRoot->nMax = _cpp_max(pRoot->nMax,v);
if( i <= (pRoot->L + pRoot->R )/2 )
Insert( pRoot->pLeft,i,v);
else
Insert( pRoot->pRight,i,v);
}
void Query(CNode * pRoot, int s, int e)
{
if( pRoot->nMin >= nMin && pRoot->nMax <= nMax )
return;
if( s == pRoot->L && e == pRoot->R) {
nMin = _cpp_min(pRoot->nMin,nMin);
nMax = _cpp_max(pRoot->nMax,nMax);
return ;
}
if( e <= (pRoot->L + pRoot->R) / 2 )
Query(pRoot->pLeft, s,e);
else if( s >= (pRoot->L + pRoot->R) / 2 + 1)
Query(pRoot->pRight, s,e);
else {
Query(pRoot->pLeft, s,(pRoot->L + pRoot->R) / 2);
Query(pRoot->pRight, (pRoot->L + pRoot->R) / 2 + 1 ,e);
}
}
int main()
{
int n,q,h;
int i,j,k;
scanf("%d%d",&n,&q);
nCount = 0;
BuildTree(Tree,1,n);
for( i = 1;i <= n;i ++ ) {
scanf("%d",&h);
Insert( Tree,i,h);
}
for( i = 0;i < q;i ++ ) {
int s,e;
scanf("%d%d", &s,&e);
nMax = MY_MAX;
nMin = MY_MIN;
Query(Tree,s,e);
printf("%d\n",nMax - nMin);
}
return 0;
}
文章来源: http://www.cnblogs.com/kuangbin/archive/2011/08/14/2137862.html
题目链接：http://poj.org/problem?id=3468
本文作者：kuangbin
博客地址：http://www.cnblogs.com/kuangbin/
题目：
A Simple Problem with Integers
| Time Limit: 5000MS |
|
Memory Limit: 131072K |
| Total Submissions: 22796 |
|
Accepted: 6106 |
| Case Time Limit: 2000MS |
Description
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15
Hint
The sums may exceed the range of 32-bit integers.
Source
简单的线段树练习题。
主要是树的节点存储哪些信息。
每个一个数都更新到叶子节点不是明智的做法，很消耗时间。
故每个节点加一个Inc来记录增量的累加。
具体看代码：
/*
POJ 3468 A Simple Problem with Integers
题目意思：
给定Q个数：A1,A2,```,AQ,以及可能多次进行下列两个操作：
1）对某个区间Ai```Aj的数都加n（n可变）
2）对某个区间Ai```Aj求和
*/
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=100000;
int num[MAXN];
struct Node
{
int l,r;//区间的左右端点
long long nSum;//区间上的和
long long Inc;//区间增量的累加
}segTree[MAXN*3];
void Build(int i,int l,int r)
{
segTree[i].l=l;
segTree[i].r=r;
segTree[i].Inc=0;
if(l==r)
{
segTree[i].nSum=num[l];
return;
}
int mid=(l+r)>>1;
Build(i<<1,l,mid);
Build(i<<1|1,mid+1,r);
segTree[i].nSum=segTree[i<<1].nSum+segTree[i<<1|1].nSum;
}
void Add(int i,int a,int b,long long c)//在结点i的区间（a,b）上增加c
{
if(segTree[i].l==a&&segTree[i].r==b)
{
segTree[i].Inc+=c;
return;
}
segTree[i].nSum+=c*(b-a+1);
int mid=(segTree[i].l+segTree[i].r)>>1;
if(b<=mid) Add(i<<1,a,b,c);
else if(a>mid) Add(i<<1|1,a,b,c);
else
{
Add(i<<1,a,mid,c);
Add(i<<1|1,mid+1,b,c);
}
}
long long Query(int i,int a,int b)//查询a-b的总和
{
if(segTree[i].l==a&&segTree[i].r==b)
{
return segTree[i].nSum+(b-a+1)*segTree[i].Inc;
}
segTree[i].nSum+=(segTree[i].r-segTree[i].l+1)*segTree[i].Inc;
int mid=(segTree[i].l+segTree[i].r)>>1;
Add(i<<1,segTree[i].l,mid,segTree[i].Inc);
Add(i<<1|1,mid+1,segTree[i].r,segTree[i].Inc);
segTree[i].Inc=0;
if(b<=mid) return Query(i<<1,a,b);
else if(a>mid) return Query(i<<1|1,a,b);
else return Query(i<<1,a,mid)+Query(i<<1|1,mid+1,b);
}
int main()
{
int n,q;
int i;
int a,b,c;
char ch;
while(scanf("%d%d",&n,&q)!=EOF)
{
for(i=1;i<=n;i++) scanf("%d",&num[i]);
Build(1,1,n);
for(i=1;i<=q;i++)
{
cin>>ch;
if(ch=='C')
{
scanf("%d%d%d",&a,&b,&c);
Add(1,a,b,c);
}
else
{
scanf("%d%d",&a,&b);
printf("%I64d\n",Query(1,a,b));
}
}
}
return 0;
}
文章来源: http://www.cnblogs.com/kuangbin/archive/2011/08/14/2138408.html
敌兵布阵
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8754 Accepted Submission(s): 3647
Problem Description
C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:"你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说："我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.
Input
第一行一个整数T，表示有T组数据。
每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。
接下来每行有一条命令，命令有4种形式：
(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
(4)End 表示结束，这条命令在每组数据最后出现;
每组数据最多有40000条命令
Output
对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数最多不超过1000000。
Sample Input
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End
Sample Output
Author
Windbreaker
Recommend
Eddy
/*
HDU 1166 敌兵布阵
*/
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
const int MAXN=50005;
struct Node
{
int l,r;
int nSum;
}segTree[MAXN*3];
int num[MAXN];
void Build(int i,int l,int r)
{
segTree[i].l=l;
segTree[i].r=r;
if(l==r)
{
segTree[i].nSum=num[l];
return;
}
int mid=(l+r)>>1;
Build(i<<1,l,mid);
Build(i<<1|1,mid+1,r);
segTree[i].nSum=segTree[i<<1].nSum+segTree[i<<1|1].nSum;
}
void Add(int i,int t,int b)
{
segTree[i].nSum+=b;
if(segTree[i].l==t&&segTree[i].r==t) return;
int mid=(segTree[i].l+segTree[i].r)>>1;
if(t<=mid) Add(i<<1,t,b);
else Add(i<<1|1,t,b);
}
int Query(int i,int l,int r)
{
if(l==segTree[i].l&&r==segTree[i].r)
return segTree[i].nSum;
int mid=(segTree[i].l+segTree[i].r)>>1;
if(r<=mid) return Query(i<<1,l,r);
else if(l>mid) return Query(i<<1|1,l,r);
else return Query(i<<1,l,mid)+Query(i<<1|1,mid+1,r);
}
int main()
{
int T;
int iCase=0;
int n,i;
char str[10];
int a,b;
scanf("%d",&T);
while(T--)
{
iCase++;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&num[i]);
Build(1,1,n);
printf("Case %d:\n",iCase);
while(scanf("%s",&str))
{
if(strcmp(str,"End")==0) break;
scanf("%d%d",&a,&b);
if(strcmp(str,"Add")==0) Add(1,a,b);
else if(strcmp(str,"Sub")==0) Add(1,a,-b);
else printf("%d\n",Query(1,a,b));
}
}
return 0;
}
文章来源: http://www.cnblogs.com/kuangbin/archive/2011/08/15/2139834.html
|
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 27 | 28 | 29 | 30 | 31 | 1 | 2 | | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | 10 | 11 | 12 | 13 | 14 | 15 | 16 | | 17 | 18 | 19 | 20 | 21 | 22 | 23 | | 24 | 25 | 26 | 27 | 28 | 29 | 30 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
公告
导航
统计
- 随笔： 100
- 文章： 0
- 评论： 2
- 引用： 0
常用链接
留言簿
随笔分类
随笔档案
博客
搜索
最新评论
阅读排行榜
评论排行榜
|
|