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
|
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 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 | 31 | 1 | 2 | 3 | | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
公告
導航
統計
- 隨筆： 100
- 文章： 0
- 評論： 2
- 引用： 0
常用鏈接
留言簿(2)
隨筆分類
隨筆檔案
博客
搜索
最新評論
閱讀排行榜
評論排行榜
|
|