|
|
今天做的還可以，當然，對我來說。唯一的缺點是別人當水題做的D我沒做出來。簡單的BFS，我愣是不會。哎，還是要把基礎打好啊。最后A掉3道，還有一道線段樹的沒有過，過些時間補上。我該抓緊時間復習了...  A - River Pollution
線段樹，求面積的并，很基礎的線段樹+離散化+掃描線，但我就是不會~
B - Middle number
今天這個是第一個過的，如果這個不過我相信后邊會更加艱難。給定一個數的序列，然后不斷的插入數字并保持遞增，最后詢問中間的數是多少。如果
數的個數是偶數，輸出中間兩個中小的。數據很大，時間是5s，我冒了個險，第一次先排序，每次二分找到要插入的位置，然后順序修改后邊的序列，過了！
二分的效率啊!!我看到后邊這個題無數人TLE到死。。。這個題給了我很大信心，不然。。。
現在知道了，正解是用兩個堆，一個大頂堆，一個小頂堆，大頂堆只能和小頂堆元素個數相同或者正好多一個。開始時將小的一般給大頂堆，大的一半給小頂堆，插入時和堆頂元素比一下，若大于大頂堆的堆頂元素，則插給小堆，否則給了大堆。詢問時只需輸出大堆的堆頂元素就可以了。
C - Game of Stones
JL出的題，乍一看很難，但是后來才知道簡單的要命：兩個人A和B玩游戲，有兩堆石子M和N，每次兩個人都至少從兩堆中任意一堆拿至少一個石子，直到兩堆石子都為空最后一個拿的人WIN。，A總是第一個拿，給定M和N，問A能否獲勝。( 0 < M , N < 10^50 )
答案：如果M==N，A輸，否則，A贏。我考慮到奇偶上了，結果WA了5次，哎。。。
D - The longest athletic track
給定N個點，和一棵生成樹（N-1條邊），最后問最長的一條路是多少。
上圖的答案是80。
求樹的直徑，兩次BFS，第一次任選起點，則終點一定是直徑的一個端點。然后再來一次BFS就可以了。
E - Buy Car
Brent喜歡騎摩托，現在有N個城市，Brent 想把所有城市逛一遍，但是他怕油不夠。每升油可以跑10km，他可以在任何一個城市加油。給出M條邊，
最后問Brent的摩托的容量最小是多少，如果不能逛完所有城市，輸出-1。
簡單的最小生成樹(正是Brent講座講的~)，找出最小生成樹最小的一條邊長度為A。如果A%10==0，答案是A/10;否則答案是A/10+1;
最后排名大概是10名？(除去老隊員和admin大概是7,8名的樣子)，問題應該不大了。嘻嘻，加油吧~ 可惡的BFS。。。一定搞定它。
這道題用到了一個我不知道的定理，Pick定理。意思是格子面上的多邊形的邊的點的個數on和內部點的個數in的關系式Area = on / 2 + in - 1; 求Area可以用叉乘法。注意最后那個Area/=2.0。 Code：
  /**//*TOJ 1011 Area
 pick theory */
 #include<stdio.h>
#include<stdlib.h>
#include<math.h>
int px[100],py[100];
int gcd(int a,int b) {
 int temp;
  while(b!=0){
temp=b;
b=a%b;
a=temp;
 }
return a;
}
int main(void)
{
int cas,dx,dy,on,in,i,j,n;
double area;
scanf("%d",&cas);
for(j=1;j<=cas;j++){
scanf("%d",&n);
px[0]=py[0]=dx=dy=area=on=0;
for(i=1;i<=n;i++){
scanf("%d%d",&dx,&dy);
on+=gcd(abs(dx),abs(dy));
px[i]=px[i-1]+dx;
py[i]=py[i-1]+dy;
area+=(px[i-1]*py[i]-px[i]*py[i-1]);
}
area=area/2.0;
in=area+1-on/2;
printf("Scenario #%d:\n%d %d %.1lf\n\n",j,in,on,area);
}
}
簡單的DP，大意是給出N場比賽球隊的輸，平，贏的場數，最后問M場比賽至少拿S分的概率。贏一場3分，平一場1分，輸0分。 dp[i][j]表示 i 場比賽得 j 分的概率。則有轉移方程dp[i][j]=dp[i-1][j-3]*r1+dp[i-1][j-1]*r2+dp[i-1][j]*r3;(r1,r2,r3分別表示每一場贏，平，輸的概率) Code：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
double dp[90][270];
int main()
{
int i,j,k,n,m;
double r1,r2,r3,sum;
while(scanf("%d%d",&n,&m),n+m){
scanf("%d%d%d",&i,&j,&k);
r1=i*1.0/(i+j+k);
r2=j*1.0/(i+j+k);
r3=k*1.0/(i+j+k);
memset(dp,0,sizeof(dp));
dp[1][0]=r3;dp[1][1]=r2;dp[1][3]=r1;
for(i=2;i<=n;i++)
for(j=0;j<=3*i;j++){
if(j<=0) // 防止數組下標出現負數
dp[i][j]=dp[i-1][j]*r3;
else if(j<=1) //同上
dp[i][j]=dp[i-1][j]*r3+dp[i-1][j-1]*r2;
else
dp[i][j]=dp[i-1][j]*r3+dp[i-1][j-1]*r2+dp[i-1][j-3]*r1;
}
sum=0.0;
for(i=m;i<=3*n;i++)
sum+=dp[n][i];
printf("%.1lf\n",sum*100);
}
}
一個結論很簡單的問題，對于任意兩個數a,b(a,b>=2)
1)如果gcd (a,b)==1，則最大的不能由a，b線性表示的數為a*b-a-b；
2)否則這個數時無窮大
至于證明，期待大牛給出，我還是不懂，一開始往拓展歐幾里得想的，但后來也沒什么結論。
哪位神牛知道證明給點提示，不勝感謝~
Code略去(太水了)
一個求逆序對的題，N個數，N<=500000，問排成遞增序列需要相鄰的數交換多少次。一開始沒有仔細看題，上來就做，后來才發現數的范圍是999999999。因為最多500000個數，所以數和數之間的間隔很大，可以處理一下，使數的間隔變小，然后使用樹狀數組統計某個數前邊的比它大的數的個數。將所有的數放到一個結構體里，稱作num，并增加一個成員id，然后按num遞增排列，再另開一個數組給每個數重新編號，使數的范圍都在N以內。然后就可以很自然的用樹狀數組做了。時間500ms。據說歸并排序比這個要快。 Code：
1 #include<iostream>
2 #include<algorithm>
3 #define M 500001
4 using namespace std;
5 int c[M],aa[M],n; //aa數組為排序后重新編號用
6 struct digit
7 {
8 int num,id;
9 }a[M]; //num為數的大小
10 bool cmp(digit a,digit b){
11 return a.num<b.num;
12 }
13 int lowbit(int t){
14 return t&(t^(t-1));
15 }
16 int sum(int t){
17 int total=0;
18 while(t>0){
19 total+=c[t];
20 t-=lowbit(t);
21 }
22 return total;
23 }
24 void update(int t,int key){
25 while(t<=n){
26 c[t]+=key;
27 t+=lowbit(t);
28 }
29 }
30 int main()
31 {
32 int i,j;
33 long long ans;
34 while(scanf("%d",&n),n){
35 memset(c,0,sizeof(c));
36 ans=0;
37 for(i=1;i<=n;i++){
38 scanf("%d",&a[i].num);
39 a[i].id=i;
40 }
41 sort(a+1,a+n+1,cmp);
42 aa[a[1].id]=1; //最小的數編號為1
43 for(i=2;i<=n;++i){
44 if(a[a[i].id].num!=a[a[i-1].id].num) //如果前后兩個數不等，則編號為下標
45 aa[a[i].id]=i;
46 else
47 aa[a[i].id]=aa[a[i-1].id]; //否則編號與前一個相同
48 }
49 //for(i=1;i<=n;i++) printf("%d ",aa[i]);
50 for(i=1;i<=n;++i){
51 update(aa[i],1);
52 ans+=(sum(n)-sum(aa[i])); //每次累加該數前邊比它大的數的個數
53 }
54 printf("%lld\n",ans);
55 }
56 }
簡單的二維樹狀數組，求一個矩形區域內的和，因為要隨時增減，而且可能減的數比原來都大，所以需要保留原來的數組。 在求矩形區域和的時候，只要用最大的矩形減去兩個小的，再加上那個多減的最小的，就OK了。1y~~ Code：
1 #include<iostream>
2 #define M 1300
3 int c[M][M],a[M][M],n;
4 int lowbit(int t){
5 return t&(t^(t-1));
6 }
7 int sum(int p,int q){
8 int x=p,y,total=0;
9 while(x>0){
10 y=q;
11 while(y>0){
12 total+=c[x][y];
13 y-=lowbit(y);
14 }
15 x-=lowbit(x);
16 }
17 return total;
18 }
19 void modify(int p,int q,int key){
20 int x=p,y;
21 while(x<=n){
22 y=q;
23 while(y<=n){
24 c[x][y]+=key;
25 y+=lowbit(y);
26 }
27 x+=lowbit(x);
28 }
29 }
30 int main()
31 {
32 int i,j,k,jj,kk,m,order,ans;
33 scanf("%d%d",&i,&n);
34 memset(c,0,sizeof(c));
35 memset(a,0,sizeof(a));
36 while(scanf("%d",&order)!=EOF){
37 if(order==3) break;
38 else if(order==1){
39 scanf("%d%d%d",&j,&k,&m);
40 ++j; ++k;
41 if(m<0&&m*(-1)>a[j][k]){
42 m=(-1)*a[j][k];
43 modify(j,k,m);
44 a[j][k]=0;
45 }
46 else{
47 modify(j,k,m);
48 a[j][k]+=m;
49 }
50 }
51 else if(order==2){
52 scanf("%d%d%d%d",&j,&jj,&k,&kk);
53 ++j; ++jj; ++k; ++kk;
54 //printf("%d ",sum(n,n));
55 ans=sum(k,kk)+sum(j-1,jj-1)-sum(k,jj-1)-sum(j-1,kk);
56 printf("%d\n",ans);
57 }
58 }
59 }
今天聯系樹狀數組，但是我發現我真的很笨，做了好幾道了還是不熟。這個題和前邊的也沒什么分別，是說每個牛有一個區間[s,e],兩個牛[s1,e1], [s2,e2]，當s1<=s2并且e1>=e2并且e1-s1>e2-s2時，我們說牛1比牛2強，給N個牛的區間，對于每個牛，輸出比這個牛強的牛的個數。 還是需要預處理，先對每個牛的e進行降序排序，e相同時對s進行升序排列，這樣循環時可以保證后邊的牛絕對不比前邊的牛強。在循環時，只需找出比當前牛s小的牛的個數。如果遇到特殊情況，即兩個牛區間完全一樣，賦值就可以了。哎，加油吧~ Code：
1 #include<iostream>
2 #include<algorithm>
3 #include<map>
4 #define MAX 100002
5 using namespace std;
6 int c[MAX],ans[MAX],n,imax;
7 struct cow
8 {
9 int l,r,id;
10 }a[MAX];
11 bool cmp(cow a,cow b){
12 if(a.r==b.r) //如果兩個牛區間右邊界相同，按左邊界的升序排列
13 return a.l<b.l;
14 return a.r>b.r; //按右邊界的降序排列
15 }
16 int lowbit(int t){
17 return t&(t^(t-1));
18 }
19 int sum(int t){
20 int total=0;
21 while(t>0){
22 total+=c[t];
23 t-=lowbit(t);
24 }
25 return total;
26 }
27 void modify(int posi,int key){
28 while(posi<=imax){
29 c[posi]+=key;
30 posi+=lowbit(posi);
31 }
32 }
33 int main()
34 {
35 int i,j,k,n;
36 while(scanf("%d",&n),n){
37 memset(c,0,sizeof(c));
38 imax=0;
39 for(i=1;i<=n;i++){
40 scanf("%d%d",&a[i].l,&a[i].r);
41 a[i].id=i; //每個牛有個id防止排序完順序變亂
42 ++a[i].l; ++a[i].r;
43 if(imax<a[i].l) imax=a[i].l; //用imax表示右邊界最大值，即求和時的邊界
44 }
45 sort(a+1,a+n+1,cmp);
46 for(i=1;i<=n;++i){
47 if(i==1){
48 ans[a[i].id]=sum(a[i].l); //這里注意是ans[a[i].id]而不是ans[i]
49 modify(a[i].l,1);
50 }
51 else{
52 if(a[i].l==a[i-1].l&&a[i].r==a[i-1].r) //如果兩個牛完全相同，直接賦值
53 ans[a[i].id]=ans[a[i-1].id];
54 else
55 ans[a[i].id]=sum(a[i].l); //否則找出左邊界l比這個牛小的
56 modify(a[i].l,1);
57 }
58 }
59 for(i=1;i<n;++i)
60 printf("%d ",ans[i]);
61 printf("%d\n",ans[i]);
62 }
63 }
64
這道題和那道Star如出一轍，可我還是做了很長時間 ...太菜了...有K條連接東西兩個城市的路，東西方向每個城市都有一個編號M,N，從北到南，最后問共有多少個十字路都，即有多少個交點。 先預處理，用結構體表示每條邊，對結構體按N進行從小到大的排序，如果N相同，按M從小到大排序。接下來就和Star一樣了，唯一不同的是Star那道題是每次求出當前星星前邊的個數，而這個是求當前點后邊的個數。用c[]表示樹狀數組，sum(n)求出的是N編號小于等于n的city的個數，只需每次拿出一個city，求出N編號大于它的city的個數，然后更新數組就可以了。 關鍵代碼：
1 long long ans=0;
2 for(i=1;i<=K;i++){ //K表示邊的個數
3 ans+=sum(max)-sum(a[i].east); //east即為N編號
4 modify(a[i].east,1); //將a[i].east插入到當前數組
5 }
6
解決了這一步，其余就是套路了，很簡單。 Code：
1 #include<iostream>
2 #include<algorithm>
3 #define MAX 10005 //最大的city個數
4 using namespace std;
5 int c[MAX],n,N,M,K,omax;
6 struct road
7 {
8 int west,east;
9 }a[MAX*MAX]; //MAX*MAX為最多的邊的個數
10 bool cmp(road a,road b){
11 if(a.west==b.west)
12 return a.east<b.east;
13 return a.west<b.west;
14 }
15 int lowbit(int t){
16 return t&(t^(t-1));
17 }
18 int sum(int t){
19 int total=0;
20 while(t>0){
21 total+=c[t];
22 t-=lowbit(t);
23 }
24 return total;
25 }
26 void modify(int posi,int key){
27 while(posi<=omax){
28 c[posi]+=key;
29 posi+=lowbit(posi);
30 }
31 }
32 int main()
33 {
34 int i,j,k,m,cas;
35 long long ans;
36 scanf("%d",&cas);
37 for(i=1;i<=cas;++i){
38 omax=0; //用omax表示所有east的最大值，以確定求和區間
39 memset(c,0,sizeof(c));
40 scanf("%d%d%d",&N,&M,&K);
41 for(j=1;j<=K;++j){
42 scanf("%d%d",&a[j].east,&a[j].west);
43 if(a[j].east>omax)
44 omax=a[j].east;
45 }
46 sort(a+1,a+1+K,cmp);
47 ans=0;
48 for(j=1;j<=K;++j){ //key code
49 ans+=(sum(omax)-sum(a[j].east));
50 modify(a[j].east,1);
51 }
52 printf("Test case %d: %lld\n",i,ans);
53 }
54 }
55
大意是N個星星，規定每個星星的等級為在它左下方星星的數量（包括某個坐標相等），N范圍是15000，輸入按y坐標的升序給出，如果兩個星星y坐標相等，按x坐標升序給出。 用樹狀數組，不用管y坐標（因為已經是升序，后邊的星星不影響前邊星星的等級），用sum(n)來統計x坐標為n以前的星星個數，但是千萬注意樹狀數組需要數組以1為首項，由于坐標有0，所以每次需要給x坐標+1。另外，通過這個題，我發現++i果然比i++快。兩者一個420ms，一個360ms。還是差不少的，以后盡量用++i了:D Code：
1 #include<stdio.h>
2 #include<string.h>
3 #define M 32006 //坐標范圍是32000
4 int c[M],ans[M/2]; //c為樹狀數組，ans[i]表示level為i的星星個數
5 int lowbit(int t){
6 return t&(t^(t-1));
7 }
8 int sum(int m){
9 int total=0;
10 while(m>0){
11 total+=c[m];
12 m-=lowbit(m);
13 }
14 return total;
15 }
16 void modify(int position){
17 while(position<=32002){
18 ++c[position];
19 position+=lowbit(position);
20 }
21 }
22 int main()
23 {
24 int x,y,i,j,n;
25 scanf("%d",&n);
26 j=n;
27 memset(c,0,sizeof(c));
28 memset(ans,0,sizeof(ans));
29 while(n--){
30 scanf("%d%d",&x,&y);
31 ++ans[sum(x+1)];
32 modify(x+1);
33 }
34 for(i=0;i<j;++i)
35 printf("%d\n",ans[i]);
36 }
TOJ有道題，大意是有N個位置，每個位置有若干瓶子，Mike很淘氣，他每次會增加或減少位置i的瓶子數，然后有M次詢問，求位置A到B的瓶子數的和。最開始，我一直用最直觀的做法，但是由于是O(n)的復雜度，所以一直超時。今天看了BIT的相關東西，才發現那個題其實是典型的BIT題目，而且是最基礎的，但是就和RMQ問題一樣，高效的算法背后深刻的數學理論還是不能很透徹的理解，這個只有靠以后熟練的慢慢來了：D
先來看一下樹狀數組的概念：樹狀數組是一種靜態樹狀數據結構，它的首要作用是維護前綴和，即改變數組中某一元素a[i]的值，若要詢問前N項的和，樹狀數組便可完美解決。時間復雜度O(logn)。
先來直觀看一下樹狀數組的結構（圖片來自http://fqq11679.blog.hexun.com/21722866_d.html#）
在上圖中，紅色的數組c[]便是樹狀數組。改變數組a的某一個元素i，則需要相應的改變數組c，若要詢問前N項和，只需累加相應的c，而這當中一個核心的問題便是相應的數組c的下標問題。可以用位操作lowbit解決。c[i]=a[i-2^k+1]到a[i]的和，k是指i用二進制表示時末位0的個數，即將i表示成冪方和后最小的指數。利用位運算，我們可以得知2^k=i&(i^(i-1));
相應的代碼為：
1 int lowbit(int n)
2 {
3 return n&(n^(n-1));
4 }
這樣，當a[i]改變時，我們只需從c[i]開始一直向上回溯，改變路上相應的數組c的值，若要求前N項和，只需求N以前所有最大子樹c[]的和。然后我們來看相應下標的操作：
修改a[i],則修改一路的父節點c[p], p=i-bit(i);
若要前i項求和，只需一路找子節點c[p], p=i-lowbit(i);
求前N項和：
1 int sum(int n)
2 {
3 int total=0;
4 while(n>0){
5 total+=c[n];
6 n-=lowbit(n);
7 }
8 return total;
9 }
TOJ 3505 Naughty mike Code：
1 /*TOJ 3505 Naughty mike*/
2 #include<stdio.h> //注意在使用樹狀數組時下標一定不能從0開始
3 #include<string.h>
4 #define M 100002
5 int a[M],n;
6 int c[M];
7 int lowbit(int t) //關鍵的位操作確定數組下標
8 {
9 return t&(t^(t-1));
10 }
11 int sum(int end) //求前end項和的函數，通過不斷累加最大子樹得到
12 {
13 int i;
14 int total=0;
15 while(end>0){
16 total+=c[end];
17 end-=lowbit(end);
18 }
19 return total;
20 }
21 void modify(int t,int key) //對數組某一項進行修改時，只需沿該項一直向上回溯修改相應的數組c
22 {
23 while(t<=n){
24 c[t]+=key;
25 t+=lowbit(t);
26 }
27 }
28 int main()
29 {
30 int i,j,k,m,cas;
31 char e[50];
32 scanf("%d",&cas);
33 while(cas--){
34 scanf("%d",&n);
35 memset(c,0,sizeof(c));
36 for(i=1;i<=n;i++){
37 scanf("%d",&a[i]);
38 modify(i,a[i]);
39 }
40 scanf("%d",&m);
41 while(m--){
42 scanf("%s%d%d",e,&i,&j);
43 if(e[0]=='A'){
44 modify(i,j);
45 a[i]+=j;
46 }
47 else if(e[0]=='D'){
48 if(j>=a[i]) j=(-1)*a[i]; //由于可能刪除的比現有的還多，需要分開考慮
49 else j*=(-1);
50 modify(i,j);
51 a[i]+=j;
52 }
53 else
54 printf("%d\n",sum(j)-sum(i-1)); //區間[i,j]的和
55 }
56 }
57 }
58
|