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();
  }
}