UVA-1382, Distant Galaxy

找一個矩形

使的"邊上"的點的數目最大

我想了好久QAQ

要維持一個"ㄈ"字型的資料 這樣就可以在n^3內完成

啊就 第一次寫出來這類的題目有點爽呵呵

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstdlib>

 4 #include <algorithm>

 5 #include <cstring>

 6 #include <set>

 7 #include <map>

 8 #include <list>

 9 using namespace std;

10 int main(){

11     int T=0;

12     set<int> tmpx;

13     set<int> tmpy;

14     set<int>::iterator tend, ti;

15     pair<map<int,int>::iterator, bool>tmppair;

16     map<int,int> transy;//map y cor to vector number

17     map<int,int> transx;//compress x cor

18     list<pair<int,int> > data;

19     int dot[105][105];

20     int sumx[105][105];

21     int sumy[105][105];

22     int tmpsum[105];

23     int right[105], left[105];

24     int n, x, y, cx, cy, ans, l;

25     while(scanf("%d", &n)){

26         if(n==0)break;

27         cx=cy=1;

28         tmpx.clear(); tmpy.clear();

29         transx.clear(); transy.clear();

30         memset(dot, 0, 101*101*4);

31         for(int i=0 ; i<n ; ++i){

32             scanf("%d%d", &x, &y);

33             tmpx.insert(x);

34             tmpy.insert(y);

35             data.push_back(pair<int,int>(x,y));

36         }

37         tend=tmpx.end();

38         for(ti=tmpx.begin() ; ti!=tend ; ti++){

39             transx[*ti]=cx++;

40         }

41         tend=tmpy.end();

42         for(ti=tmpy.begin() ; ti!=tend ; ti++){

43             transy[*ti]=cy++;

44         }

45         for(int i=0 ; i<n ; ++i){

46             dot[transx[data.front().first]][transy[data.front().second]]++;

47             data.pop_front();

48         }

49         for(int i=0 ; i<cy ; ++i){

50             sumx[0][i]=dot[0][i];

51             for(int j=1 ; j<cx ; ++j){

52                 sumx[j][i]=sumx[j-1][i]+dot[j][i];  // -

53             }

54         }

55         for(int i=0 ; i<cx ; ++i){

56             sumy[i][0]=dot[i][0];

57             for(int j=1 ; j<cy ; ++j){

58                 sumy[i][j]=sumy[i][j-1]+dot[i][j];  // |

59             }

60         }

61         ans=0;

62         for(int i=0 ; i<cy ; ++i){

63             for(int j=i+1 ; j<cy ; ++j){

64                 for(int k=0 ; k<cx ; ++k){

65                     tmpsum[k]=sumy[k][j]-sumy[k][i]-dot[k][j];

66                     right[k]=tmpsum[k]+sumx[k][i]+sumx[k][j];

67                     left[k]=tmpsum[k]-sumx[k][i]-sumx[k][j]+dot[k][i]+dot[k][j];

68                 }

69                 right[cx]=left[cx]=l=0;

70                 for(int k=1 ; k<cx ; ++k){

71                     ans=max(ans, left[l]+right[k]);

72                     if(left[k]>left[l]){

73                         l=k;

74                     }

75                 }

76             }

77         }

78         

79         printf("Case %d: %d\n",++T , ans);

80     }

81     return 0;

82 }

UVA-1121, Subsequence

利用了"下一個符合條件的區段一定在右邊"這個特性

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstdlib>

 4 using namespace std;

 5 int main(){

 6     int n, s;

 7     int sum[100001], tmp;

 8     int h, t, ans;

 9     sum[0]=0;

10     while(scanf("%d%d", &n, &s)!=EOF){

11         scanf("%d", sum+1);

12         for(int i=1 ; i<n ; ++i){

13             scanf("%d", &tmp);

14             sum[i+1]=sum[i]+tmp;

15         }

16         h=t=0;

17         ans=2147483647;

18         while(t<=n){

19             //cout<<h<<" "<<t<<' '<<sum[t]-sum[h]<<'\n';

20             if(sum[t]-sum[h]<s){++t;}

21             else{if(ans>(t-h)){ans=t-h;} ++h;}

22         }

23         if(ans==2147483647)ans=0;

24         printf("%d\n", ans);

25     }

26     return 0;

27 }

Sequence系列簡短心得

最常遇到的就是最大最小區段

但是要注意

當全正貨全負時

要你球的又不是單純的數值

而是問你最段符合條件的可能區段的話

可能可以用二分搜或是利用"下一格個符合條件的區段的頭尾絕對比較後面"這個特性

可以做到O(N)

UVA-1398, Meteor

判斷速度分量是否為零後的else忘記加大括弧讓我2WA= =

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstdlib>

 4 #include <algorithm>

 5 #include <vector>

 6 using namespace std;

 7 struct me{

 8     me(){;}

 9     me(double time, int type){this->t=time; this->type=type;}

10     me(const me& a){this->t = a.t; this->type=a.type;}

11     double t;

12     int type; //0=end, 1=start

13 };

14 bool mysort(const me& a, const me& b){

15     if(a.t-b.t<1e-9 and b.t-a.t<1e-9)return (a.type < b.type);

16     else return (a.t < b.t);

17 }

18 int main(){

19     int T;

20     int w, h, n;

21     int x, y, a, b;

22     int pt, ans, tmp;

23     double sx, sy, ex, ey;

24     vector<me> time(200002);

25     scanf("%d", &T);

26     while(T--){

27         scanf("%d%d%d", &w, &h, &n);

28         pt=ans=tmp=0;

29         for(int i=0 ; i<n ; ++i){

30             scanf("%d%d%d%d", &x, &y, &a, &b);

31             if(a==0){ sx=(x>0 and x<w)?0:2147483647; ex=(x>0 and x<w)?2147483647:0;}

32             else{ sx=(0.-x)/(double)a; ex=(double)(w-x)/(double)a;

33                 if(sx>ex){ swap(sx, ex);}

34             }

35 

36             if(b==0){ sy=(y>0 and y<h)?0:2147483647; ey=(y>0 and y<h)?2147483647:0;}

37             else{ sy=(0.-y)/(double)b; ey=(double)(h-y)/(double)b;

38                 if(sy>ey){ swap(sy, ey);}

39             }

40 

41             if(sx<0) sx=0; if(sy<0) sy=0;

42             if(ex<0) ex=0; if(ey<0) ey=0;

43             sx=max(sx, sy); ex=min(ex, ey);

44             if(ex-sx<1e-9){continue;}

45             time[pt++]=me(sx, 1); time[pt++]=me(ex, 0);

46         }

47         sort(time.begin(), time.begin()+pt, mysort);

48         for(int i=0 ; i<pt ; ++i){

49             if(time[i].type==0){

50                 --tmp;

51             }else{

52                 ++tmp;

53             }

54             if(tmp>ans) ans=tmp;

55         }

56         printf("%d\n", ans);

57     }

58     return 0;

59 }

UVA-11549, Calculator Conumdrun

重點是找環!!
第一次實寫這個...

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstdlib>

 4 #define LL long long int

 5 using namespace std;

 6 LL base;

 7 LL cal(LL a){

 8     LL tmp=(LL)a*a;

 9     while(tmp >= base)tmp/=10;

10     return tmp;

11 }

12 

13 int main(){

14     int T;

15     int n, k, ans;

16     LL a, b;

17     scanf("%d", &T);

18     while(T--){

19         scanf("%d%d", &n, &k);

20         base=1;   while(n--)base*=10;

21         ans=0;

22         a=(LL)k;

23         b=cal(k);

24         if(a > ans) ans=a;

25         if(b > ans) ans=b;

26         while(a!=b){

27             a=cal(a); if(a > ans) ans=a;

28             b=cal(b); if(b > ans) ans=b;

29             b=cal(b); if(b > ans) ans=b;

30         }

31         printf("%d\n", ans);

32     }

33     return 0;

34 }

</ pre>

UVA-1267, Network

這一題要有兩種DFS模式
初始和過程中
其他BJ4

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstdlib>

 4 #include <algorithm>

 5 #include <list>

 6 #include <set>

 7 #include <vector>

 8 using namespace std;

 9 struct node_t{

10     node_t(){;}

11     node_t(const node_t& a){this->depth=a.depth; this->num=a.num;}

12     node_t(int d, int n){this->depth=d; this->num=n;}

13     int depth;

14     int num;

15     bool operator()(const node_t& a, const node_t& b)const{

16         if(a.depth != b.depth)    

17             return (a.depth < b.depth);

18         else

19             return (a.num < b.num);

20     }

21 };

22 int T, n;

23 int s, k;

24 int a, b;

25 int ans, tmp, news;

26 vector<int> depth(1005);

27 vector<list<int> > out(1005);

28 list<int>::iterator it, oend;

29 set<node_t, node_t> notyet;

30 void cover(int d, int caller, int now){

31     depth[now]=d;

32     if(out[now].size()>1 or now==s){ //internal node

33         list<int>::iterator oend=out[now].end();

34         for(list<int>::iterator it=out[now].begin() ; it!=oend ; it++){

35             if(*it != caller)    

36                 cover(d+1, now, *it);

37         }

38     }else{ //leaf

39         if(d > k){

40             notyet.insert(node_t(d, now));

41             return;

42         }

43     }

44     return;

45 }

46 void covered(int d, int caller, int now){

47     if(d > k)return;

48     if(out[now].size()>1){

49         list<int>::iterator oend=out[now].end();

50         for(list<int>::iterator it=out[now].begin() ; it!=oend ; it++){

51             if(*it != caller)    

52                 covered(d+1, now, *it);

53         }

54     }else{

55         if(d <= k){

56             notyet.erase(node_t(depth[now], now));

57             return;

58         }

59     }

60     return;

61 }

62 int main(){     

63     scanf("%d", &T);

64     while(T--){

65         scanf("%d", &n);

66         for(int i=1 ; i<=n ; ++i){

67             out[i].clear();

68         }

69         notyet.clear();

70         ans=0;

71 

72         scanf("%d%d", &s, &k);

73         for(int i=1 ; i<n ; ++i){

74             scanf("%d%d", &a, &b);

75             out[a].push_back(b);

76             out[b].push_back(a);

77         }

78 

79         cover(0, s, s);

80         while(not notyet.empty()){

81             tmp=notyet.rbegin()->num;

82             for(int zz=0 ; zz<k ; ++zz){ //go back k length  

83                 oend=out[tmp].end();

84                 for(it=out[tmp].begin() ; it!=oend ; it++){

85                     if(depth[*it] < depth[tmp]){

86                         tmp=*it;

87                         break;

88                     }

89                 }

90             }

91             ++ans; //tmp now is a sever

92             covered(0, tmp, tmp);

93         }

94 

95         printf("%d\n", ans);

96     }

97 return 0;

98 }

UVA-12097, Pie

浮點數的題目要特別小心部分

精確位數要取好

尤其是跟圓周率有關的題目

千萬不要自己打3.1416

要用math.h算acos(-1.0)...

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstdlib>

 4 #include <cmath>

 5 #define PI acos(-1.0)

 6 using namespace std;

 7 int main(){

 8     int T, n, f, tmp;

 9     double p[10001];

10     double maxp, L, R, M;

11     int piece;

12     scanf("%d", &T);

13     while(T--){

14         scanf("%d%d", &n, &f);

15         f+=1;

16         maxp=0;

17         for(int i=0 ; i<n ; ++i){

18             scanf("%d", &tmp);

19             p[i]=1.*tmp*tmp*PI;

20             if(p[i]>maxp)

21                 maxp=p[i];

22         }

23         L=0.; R=maxp;

24         while(R-L>1e-7){

25             M=(L+R)/2;

26             piece=0;

27             for(int i=0 ; i<n ; ++i){

28                 piece+=floor(p[i]/M);

29             }

30             if(piece < f){

31                 R=M;

32             }else{

33                 L=M;

34             }

35             

36         }

37         printf("%.5f\n", L);

38         

39     }

40 return 0;

41 }

UVA-12124, Assemble

這題一開始沒想到
以為是要用二為搜索數找最小值
後來才發現直接二分搜下去就好了

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstdlib>

 4 #include <cstring>

 5 #include <set>

 6 #include <map>

 7 #include <vector>

 8 using namespace std;

 9 struct cmp_str{

10     bool operator()(char const *a, char const *b)const{

11         return ( strcmp(a, b)<0 );

12     }

13 };

14 int main(){

15     int T;

16     int n, budget;

17     char junk[21];

18     int qua, cost;

19     map<char const*, int, cmp_str> type;

20     int notype;

21     pair<map<char const*, int, cmp_str>::iterator,bool> tp;

22     vector<map<int, int> > com(1001);

23     pair<map<int, int>::iterator,bool> cp;

24     map<int,int>::reverse_iterator it, cend;

25     int minc, maxq, M, L, R, tmpc;

26     scanf("%d", &T);

27     pair<int,int> MAX(1000000001, 1000001);

28     while(T--){

29         notype=0; maxq=0;

30         type.clear();

31         scanf("%d%d", &n, &budget);

32         for(int i=0 ; i<n ; ++i)

33             com[i].clear();

34 

35         for(int i=0 ; i<n ; ++i){

36             char* ty = new char[21];

37             scanf("%s%s%d%d", ty, junk, &cost, &qua);

38             if(maxq < qua) maxq=qua;

39             tp=type.insert(pair<char const*, int>(ty, notype));

40             if(tp.second){

41                 ++notype;

42             }

43             cp=com[tp.first->second].insert(pair<int,int>(qua, cost));

44             if(not cp.second){

45                 if(cp.first->second > cost)

46                     cp.first->second=cost;

47             }

48         }

49         for(int i=0 ; i<notype ; ++i){

50             cend=com[i].rend(); it=com[i].rbegin();

51             minc=it->second; it++;

52             for( ; it!=cend ; it++){

53                 if(it->second > minc){

54                     it->second = minc;

55                 }else{

56                     minc=it->second;

57                 }

58             }

59             com[i].insert(com[i].end() , MAX);

60         }

61         L=0, R=maxq+1;

62         while(R-L!=1){

63             M=(L+R)/2;

64             tmpc=0;

65             for(int i=0 ; i<notype ; ++i){

66                 tmpc+=com[i].lower_bound(M)->second;

67                 if(com[i].lower_bound(M)->first == 1000000001){ //no match

68                     tmpc=budget+1;

69                     break;

70                 }

71             }

72             if(tmpc > budget){

73                 R=M;

74             }else{

75                 L=M;

76             }

77         }

78         printf("%d\n", L);

79     }

80     return 0;

81 }

UVA - 11384, Help is needed for Dexter

水題BJ4

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstdlib>

 4 #include <cmath>

 5 using namespace std;

 6 int main(){

 7     int n;

 8     while(scanf("%d", &n) != EOF){

 9         printf("%d\n", (int)log2(n)+1);   

10     }

11 return 0;

12 }

...

7.10.2014

花了一年的時間終於知道原來自己有多混應該還不算太晚

這一次的機會沒有把握住

不過下一次

一定會是我的

肌肉Opera...

[小畫家速繪]

在設計資訊營遊戲的美工時

開招動畫有人提議來個特寫+Cut in

不過考慮到主角是瀏覽器

還是把文字併入比較好


如果長的猛一點的話說不定就可以像這樣

http://i.imgur.com/D67YhGL.gif



那麼這樣的Opera 夠帥了吧?