file permission

在bash設定檔案權限時打十進位就可以了

但是在C程式裡想要用chmod或是其他跟權限有關的函數

都要寫八進位:

755 -> 0755

不然會爛掉......

在cygwin使用gdb

很多人都知道

gdb提供了追蹤程式、除錯的功能

但是在筆者的win 8.1系統下

當我輸入

$ gdb dummy

時

gdb卻跟我哭說無法識別檔案

不要驚慌     這不是cygwin的問題

問題在於舊版本的gdb無法識別64bits的檔案

所以只需要將gdb更新到新版本就可以了喔


另外  不知道為什麼

我試著自己下載原始碼build

卻會出現no usable depend的錯誤

所以請去找別人build好的......

UVA-10635, Prince and Princes

這題真是魂淡

看起來一副LCS的模樣

殊不知寫LCS會TLE

於是在下很不爭氣的爬了攻略

發現其實是要把他轉成LIS

因為數字不會重複出現

所以把第一個陣列重新編號

定義a[0]=0, a[1]=1......

然後另一個陣列就轉換下去

如果找不到對應就設一個鬼東西表示絕對不會採用

code就不上了  寫得有點醜

[心得]小心LCS

LCS有時候其實並不是LCS

先看看複雜度

如果pq真他媽的大

那他就絕對不是LCS

不管看起來有多像...

關鍵在元素是否重複

[轉貼][整理] 約瑟夫問題

約瑟夫問題

n個人排成一圈
每數到第m個人就剔除，然後繼續數
請問最後剩下的人的編號?

在網路上看到幾種解法
下面是自己整理的心得

一、遞推

踢掉第一個人以後
剩下的人可以重新從零編號
然後從零再一次進行踢人的動作

因此四個人踢掉一人的狀況
其實就是五個人踢掉第二人的狀況
只不過編號需要轉換一下:
"這一輪的第i號(剩k人時)" 是 "上一輪的第(i+m)%(k+1)"

理由是這樣的:
因為每一輪都從0開始數，所以第m號就是下一輪的第0號
因此每一輪依次轉換上去就可以得到任意初始人數下的最終結果

舉個例子，如果m=3(每數三人):
那剩下一人時的第0號 (也只有第0號)
就是剩下二人時的第(0+3)%(k+1) = 1號

二、逆推

總共有n個人，每數第m個人就剔除

所以第k個被剔除的人另一個角度上就是第(k*m)-1號

然後就一圈一圈往上看

看他上一次報數時到底是幾號

當號碼落在 0~n-1 之間時就是答案了

而上一次報數和下一次報數的號碼差

剛好等於那一圈剩下的人數

要逆推回去的話就是

上一圈編號 = 這一圈編號(N) - 上一圈人數

而某一圈剩下的人數為: n-N/m 

以M代表下一圈的編號，N代表這一圈

則 M = N + n - (N/m)

=>

N = (M-n)*m/(m-1)

因此可以做下面編寫:

1 for(ans=k*m-1 ; ans>=n ; ans=(ans-n)*m/(m-1) );

ans最後存的值就是第k個被剔除的人的編號

以上就是對約瑟夫問題的小小研究心得

參考:
http://maskray.me/blog/2013-08-27-josephus-problem-two-log-n-solutions
程式碼是我自己重寫的  不知道到底對不對 改天試一下......

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 }