Snowdream

     摘要: 同樣轉自水木社區  閱讀全文

     摘要: 水木上看到的

一個K位的數N (K<=2000,N<=10^20)
找出一個比N大且最接近的數，這個數的每位之和與N相同
用代碼實現之

如：
0050 所求數為0104
112 所求數為121
  閱讀全文

maillist上有人問關于這個函數的問題，回復中有人推薦去看它的源代碼

memcpy調用了__memcpy函數執行內存的復制（__memcpy3d就先不管了），下面是這個這兩個函數的代碼

void *memcpy(void *to, const void *from, size_t n)
{
#ifdef CONFIG_X86_USE_3DNOW
 return __memcpy3d(to, from, n);
#else
 return __memcpy(to, from, n);
#endif
}

static __always_inline void * __memcpy(void * to, const void * from, size_t n)
{
int d0, d1, d2;
__asm__ __volatile__(
 "rep ; movsl\n\t"
 "movl %4,%%ecx\n\t"
 "andl $3,%%ecx\n\t"
#if 1 /* want to pay 2 byte penalty for a chance to skip microcoded rep? */
 "jz 1f\n\t"
#endif
 "rep ; movsb\n\t"
 "1:"
 : "=&c" (d0), "=&D" (d1), "=&S" (d2)
 : "0" (n/4), "g" (n), "1" ((long) to), "2" ((long) from)
 : "memory");
return (to);
}

看了一本內聯匯編的書，總算把這段代碼搞懂了。
起始時，把n/4保存在%ecx寄存器中，并把to和from的地址分別存入%edi和%esi （引用占位符）
然后重復調用movsl n/4次，接下來應該還有(n mod 4)個字節尚未復制，這里用了一個比較巧妙的方法
movl %4, %%ecx    把n的值保存到%ecx
andl $3, %%ecx    n與3做邏輯與，得到n mod 4
jz 1f             如果4 | n，跳過后面的復制
rep movsb         再復制(n mod 4)個字節

由于是按四個字節復制的，因此效率上memcpy肯定比strcpy高不少。

睡前過一道，睡覺睡得香    不管這題多簡單，咔咔

按照木塊的長度或質量排序，之后貪心即可，后面和NOIP的攔截導彈一樣。

我的做法是枚舉最遠到達的湖，減去相應的時間后貪心。

貪心時需要建立一個堆，用了STL中的priority_queue，然后就不知道如何設置less<>方法了。。。
最后是通過自定義一個類node解決的

一開始寫的operator<方法邏輯上有問題，VS 2005跑了一會兒就冒出個 Debug assert error，這個挺贊的

導致我WA的幾個數據：
1) 收益為0的幾組數據。由于一開始設置的max值為0，因此當正解也是0時并沒有記錄下當前的最優解。max初始為負值即可。
2) 同樣是0導致的問題。0收益的釣魚點也可能出現在堆中，此時應該放棄這個點，把時間保留給序數大的釣魚點。

另外我有這次比賽的測試數據和標程，需要的朋友留言即可。

 

安裝samba服務可以與Windows進行文件的共享
下面是在Arch下的簡單安裝方法：
- pacman -Sy samba
- (root) cp /etc/samba/smb.conf.default /etc/samba/smp.conf
- (root) vim /etc/samba/smb.conf （或者使用其他的編輯器）

[globle]選項塊
workgroup = HOME    # 組名，在Windows中默認是MSHOME或者WORKGROUP
netbios name = ZelluX  # 在網上鄰居中顯示的機器名
encrypt passwords = yes  # 應該設為yes。但是如果要在Windows 98/95上訪問你的服務器，得把這個設為no，因為它們不支持密碼的加密傳輸。

[homes]選項塊
最簡單的配置（登陸后方可訪問）：
browseable = no
read only = no   # 或者writable = yes

匿名可讀，登陸后可以修改：
public = yes
writable = yes
write list = @staff

如果想讓Windows用戶看到一個清晰的目錄（隱藏.開頭的文件，比如~/.bashrc）：
[homes]
path = /home/%u/smb
browseable = no
read only = no
同時要在每位用戶的主目錄下建立一個smb目錄。可以通過在/etc/skel目錄下建立smb，從而自動在所有用戶目錄下建立該目錄
mkdir /etc/skel/smb

要共享其他的目錄也很容易，只要設置path和valid users屬性即可
[music]
path = /mnt/windows/Music/
browseable = yes
read only = yes
valid users = Bryan, Michael, David, Jane
valid users屬性指定登陸后有權限訪問到這個目錄的用戶

- (root) 使用 smbpasswd -a 用戶名  增加允許登陸的用戶，并指定他們的登陸密碼
- (root) /etc/rc.d/samba stop 停止samba服務
- (root) /etc/rc.d/samba start 啟動samba服務

剛做完了Java課布置的homework，其中有一題是打印日歷
        February 2007
 ---------------------------
 Sun Mon Tue Wed Thu Fri Sat
                   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

用GregorianCalendar類幾分鐘就做好了
Java的確很方便，主要是很多庫都集成在jdk中，查一份手冊就可以使用
如果這個用C++寫，除非去找個開源的庫，否則估計就得自己計算了，印象中日期方面的競賽題都屬于難度不大，但是很容易出錯的題目。
話雖如此，還是想學好C++  -,-|||

更詳細的分析google Nim Game
http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf


發信人: flyskyf (flysky), 信區: Algorithm
標  題: 拿糖果問題
發信站: 水木社區 (Mon Oct 15 19:07:51 2007), 站內

現有4堆糖果.分別為1,2,4,8
甲乙兩人分別從中拿糖果

規則:
1 每人可以從某一堆中拿任意多個
2 甲乙兩人交替拿
3 誰拿到最后一個糖果或最后幾個糖果算贏.

請問誰有必勝把握?怎樣實現?


發信人: meeme (米鳴), 信區: Algorithm
標  題: Re: 拿糖果問題
發信站: 水木社區 (Mon Oct 15 19:26:32 2007), 站內

轉成二進制

1   =0001
2   =0010
4   =0100
8-1 =0111   +
-----------
     0222
這樣每個位上都有兩個1。
比如個位上，1和7在個位上都有一個1
對方不可能同時把這兩個1拿走。所以對方是拿不完的。
對方拿完之后，自己再拿若干個調整成這種狀態。

中間應該有不少證明...

http://www.ekany.com/wdg98/zhsx/2/2_6.htm

Ferrers圖像 

    一個從上而下的n層格子，m_i 為第i層的格子數，當m_i>=m_i+1(i=1,2,^...,n-1) ，即上層的格子數不少于下層的格子數時，稱之為Ferrers圖像，如圖(2-6-2)示。 

        

                                 圖   (2-6-2)

    Ferrers圖像具有如下性質： 

    1.每一層至少有一個格子。 

    2.第一行與第一列互換，第二行于第二列互換，…，即圖(2-6-3)繞虛線軸旋轉所得的圖仍然是Ferrers圖像。兩個Ferrers 圖像稱為一對共軛的Ferrers圖像。 

    利用Ferrers圖像可得關于整數拆分的十分有趣的結果。 

    (a)整數n拆分成k個數的和的拆分數，和數n拆分成個數的和的拆分數相等。 

    因整數n拆分成k個數的和的拆分可用一k行的圖像表示。所得的Ferrers圖像的共軛圖像最上面一行有k個格子。例如： 

      

圖   (2-6-3)      

    (b)整數n拆分成最多不超過m個數的和的拆分數，和n拆分成最大不超過m的拆分數相等。 理由和(a)相類似。 

    因此，拆分成最多不超過m個數的和的拆分數的母函數是 

       

    拆分成最多不超過m-1個數的和的拆分數的母函數是 

       

    所以正好拆分成m個數的和的拆分數的母函數為 

       

    (c)整數n拆分成互不相同的若干奇數的和的的拆分數,和n拆分成自共軛的Ferrers圖像的拆分數相等. 設 

       

其中n₁>n₂>^...>n_k 

    構造一個Ferrers圖像，其第一行，第一列都是n₁+1格，對應于2n₁+1，第二行，第二列各n₂+1格，對應于2n₂+1。以此類推。由此得到的Ferres圖像是共軛的。反過來也一樣。 

    例如 17=9+5+3 對應為Ferrers圖像為

       

圖   (2-6-4)

       

費勒斯（Ferrers）圖象

假定n拆分為n=n1+n2+n3+……+nk，且n1>=n2>=n3>=……>=nk

我們將它排列成階梯形，左邊看齊，我們可以得到一個類似倒階梯圖像，這種圖像我們稱之為Ferrers圖像，如對于20=10+5+4+1，我們有圖像：

對于Ferrers圖像，我們很容易知道以下兩條性質：

（1）      每層至少一個格子

（2）      行列互換，所對應的圖像仍為Ferrers圖像，他應該為該圖像的共軛圖像

   任意的Ferrers圖像對應一個整數的拆分，而可用Ferrers圖像方便地證明：

（1）      n拆分為k個整數的拆分數，與n拆分成最大數為k的拆分數相等

（2）      n拆分為最多不超過k個數的拆分數，與n拆分成最大數不超過k的拆分數相等

（3）      n拆分為互不相同的若干奇數的拆分數，與n拆分成圖像自共軛的拆分的拆分數相等

這兩星期里得看懂Robocode代碼，然后自己做個類似小霸王坦克大戰的游戲出來@@ 只能老老實實啃了

首先要了解了一些常用的設計模式，由于時間有限，就不去看四人幫的那本書了，偷懶google別人的文章快速入門算了

Robocode中有不少Manager類，其實就是Façade模式的應用。

http://www.fish888.com/Facade-t126336

1、官方描述：

    為子系統中的一組接口提供一個一致的界面，Facade模式定義了一個高層接口，這個接口使得這一子系統更加容易使用。

   

2、實例討論：

我們可以通過電視機遙控器的作用來理解該模式的價值和作用，電視機的內部很復雜，包括頻道調節和處理系統、圖像色彩調節處理系統、聲音調節系統等等，每個系統又包括多個類進行操作，如果把這些系統都暴露給用戶使用，而不是通過遙控器進行封裝，那么每個電視機用戶都可能需要進行一個《電視機操作使用》培訓才能使用了。相對而言，現在通過遙控器，電視機用戶在很短的時間就可以掌握常規的使用方法。
電視機遙控器及電視機內部的結構圖如下所示：

 

 3、適用性：
1）為復雜的子系統提供一個簡單的接口，子系統可能為了通用性目標，實現為可以根據使用情況進行各種定制的復雜系統，可是按照2/8法則，80%的用戶可能只是使用簡單的20%的功能，這樣通過提供Facade對子系統進行高層概括，便極大的簡化了這80%用戶的易用性；
2）子系統存在多種實現，通過Facade在用戶和子系統內部實現之間進行分離，減弱了用戶對子系統的實現依賴性，這樣就便于對子系統進行擴展和維護；
3）降低子系統之間的依賴性；

   

4、實現特征：
1）Facade不提供新的功能，僅作為子系統的高層概括和代理；
2）子系統不知道Facade的存在，即子系統中沒有對Facade的關聯，而只是Facade了解子系統內部結構；
3）Facade原則上并不禁止用戶直接訪問子系統中的對象，Facade在子系統的可定制性上層建立了一個簡單視圖；

 5、Java代碼演示：
下面代碼演示了電視機遙控器的程序結構：

 1）子系統部分代碼：
類ChannelManager（頻道管理器），負責電視頻道的相關調整和操作：

   

package qinysong.pattern.facade.subsystem;

public class ChannelManager ...{
  
  //當前頻道編號
  private int currentChannelNumber;
  
  //設置頻道(可能還會調用其它輔助類)
  public void chooseChannel(int channelNumber) ...{
    System.out.println("ChannelManager.chooseChannel(): 設置頻道(可能還會調用其它輔助類)");
    currentChannelNumber = channelNumber;
  }
  
  //上調頻道(可能還會調用其它輔助類)
  public void upSkipChannel()...{
    System.out.println("ChannelManager.upSkipChannel(): 上調頻道(可能還會調用其它輔助類)");
    currentChannelNumber++;
  }
  
  //下調頻道(可能還會調用其它輔助類)
  public void downSkipChannel()...{
    System.out.println("ChannelManager.downSkipChannel(): 下調頻道(可能還會調用其它輔助類)");
    currentChannelNumber--;
  }
  
  public void otherMethod()...{
    System.out.println("ChannelManager.otherMethod(): 其他方法");
  }
}

類AudioManager（聲頻管理器），負責聲音的相關調整和操作，該類還用到其他類，如類Volume等：

package qinysong.pattern.facade.subsystem;

public class AudioManager ...{
  
  //當前音量
  private Volume currentVolume;

  //加重音量
  public void aggravateVolume()...{
    System.out.println("AudioManager.aggravateVolume(): 加重音量(可能還會調用其它輔助類)");
    currentVolume.aggravate();
  }

  //降低音量
  public void weakenVolume()...{
    System.out.println("AudioManager.weakenVolume(): 降低音量(可能還會調用其它輔助類)");
    currentVolume.weaken();
  }

  public void otherMethod()...{
    System.out.println("AudioManager.otherMethod(): 其他方法");
  }
}

類ColorManager（色彩管理器），負責圖像色彩的相關調整和操作，該類還用到其他類，如類Color等：

package qinysong.pattern.facade.subsystem;

public class ColorManager ...{
  
  //當前色彩度
  private Color currentColor;

  //加重色彩度
  public void aggravateColor()...{
    System.out.println("ColorManager.aggravateColor(): 加重色彩度(可能還會調用其它輔助類)");
    currentColor.aggravate();
  }

  //降低色彩度
  public void weakenColor()...{
    System.out.println("ColorManager.weakenColor(): 降低色彩度(可能還會調用其它輔助類)");
    currentColor.weaken();
  }

  public void otherMethod()...{
    System.out.println("ColorManager.otherMethod(): 其他方法");
  }
}

2）視圖代碼：
類RemoteDevice（遙控器），對電視機的日常使用操作進行封裝，以便用戶使用：

package qinysong.pattern.facade;

import qinysong.pattern.facade.subsystem.AudioManager;
import qinysong.pattern.facade.subsystem.ColorManager;
import qinysong.pattern.facade.subsystem.ChannelManager;

public class RemoteDevice ...{  
  
  private AudioManager audioManager;
  private ColorManager colorManager;
  private ChannelManager channelManager;
  
  //加重音量
  public void aggravateVolume()...{
    //取得 audioManager
    audioManager.aggravateVolume();
  }
  //降低音量
  public void weakenVolume()...{
    //取得 audioManager
    audioManager.weakenVolume();
  }
  
  //加重色彩度
  public void aggravateColor()...{
    //取得 colorManager
    colorManager.aggravateColor();
  }
  //降低色彩度
  public void weakenColor()...{
    //取得 colorManager
    colorManager.weakenColor();
  }
  
  //設置頻道(可能還會調用其它輔助類)
  public void chooseChannel(int channelNumber) ...{
    //取得 channelManager
    channelManager.chooseChannel(channelNumber);
  }

  //上調頻道(可能還會調用其它輔助類)
  public void upSkipChannel()...{
    //取得 channelManager
    channelManager.upSkipChannel();
  }

  //下調頻道(可能還會調用其它輔助類)
  public void downSkipChannel()...{
    //取得 channelManager
    channelManager.downSkipChannel();
  }
}