为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。

USACO/contact

来自NOCOW
跳转到： 导航, 搜索

目录

[编辑] 分析

1 <= A <= B <= 12，由于信号长度不同需要区别（0与00不是同一信号），可以转化为三进制储存，也可以用二维数组 F[i,j]表示值为i位数为j的信号出现次数。最后看储存方法不同按频率由高到低，由短到长，由小到大输出。

也可直接转成二进制处理,只需要每种字符串加一个前导'1'。具体看代码


[补充]--1小妹在这里补充一个比较“旁门左道”的方法，可以用一棵满二叉树储存，一维数组实现。每个节点值为0或1，左儿子是值为0的节点，右儿子是值为1的节点。从根节点（根节点本身无值）到该节点路径上经过的节点组成的串就是该节点表示的串。数组中下标1 shl a 到1 shl (b+1)-1的节点就是位数为从a到b的节点。具体实现见代码4。

[补充]--2最好边读入边处理，否则是存不下那么大的数据的！

[补充]--3应该可以用ansistring存下的样子啊……

[补充]--4最好别用ansistring存，本来时间空间就有些紧张……

[补充]--先统计长度为 B 的各种串的个数，然后推算 A~B-1 长度的串的个数。排序用选择排序就可以了。 (yuhc)

[补充]--5可以用约 197KB 的字符数组来存下来，空间好像没有压力。

[补充]--6可以用一个数字保存当前的n 比特为所转化的数字t。每次后移的时候，t<<=1,t+=str[i+1],str可以用bool数组 记得要把t的前面的无关的位 用1110111这样的数 做多次与运算 屏蔽掉前面的位 

 其中t为准备后移的数字，t2用来做掩码，str[j]为下一位的值(0或1)，i为当前比较的串长度，32是t的位数，len5临时变量
记录已经清理几次了从32-i位往前清理到第一位    
                   t<<=1;
			int t2=1,len5=32-i;
			t2<<=i;
			while(len5--)
			{
				t&=(t2^0xFFFFFFFF);
				t2<<=1;
			}
			t+=str[j];

[编辑] 提供一种高效的方法

提供一种高效的方法。

首先把问题分成几部分，先生成数据。 初始化 f[i,j]表示长度为i的第j元素， 

f[1,1]:='0'; f[1,2]:='1';
i:=1;
while ss[i]='1' do begin ss[i]:='0'; inc(i); end;
ss[i]:='1';
inc(shu);
f[a,shu]:=ss;

用上述方法可巧妙解决a的所有元素，接下来a+1到b的都可由1和a推导； 然后是枚举数据的位置i，由i+a-1到i+b-1枚举可能的字符，计算其十进制的数值l，l+1即是其位置 

l:=0; k:=0;
for j:=i to i+a-2 do//先算开头是i，长度为i+a-2的字串的数值
  begin
    inc(k);
    inc(l,(ord(s[j])-ord('0'))*mm[k]);
    end;
    for j:=a to b do
      begin
        if i+j-1>cha then break;
        l:=l+(ord(s[i+j-1])-ord('0'))*mm[j];//因为是在上一字符后加了一个字符，所以其数值可通过上一个l得到，mm[k]是const=（1，2，4……）；
        inc(g[j,l+1]);

最后三个条件快排，输出，搞定；最大一个点0.194s，不错，唯一缺点就是内存太大…… 程序中内存不正常的就是我的-_-

[编辑] 解码（借鉴RK算法）

其实，观察这道题可以发现，所有字符串都是由01组成的，而且长度至多12，那么把每个状态进行解码至多也不超过2^12<=10000，那不如开个统计数组（下标表示状态[1..10000])直接记录出现次数，把整个字符串进行扫描把字符串进行解码，然后添加出现状态的次数。扫描(b-a+1)次就可以做好统计（每种长度扫一次），最后把出现次数不为零的状态进行处理，就可以秒掉了。编程复杂度不高。

实际操作时应在二进制最高加一位上加一，以区别不同的匹配字符长数。扫描时，可以采取逐位推进的方法,每次


zc:=（bl shl 1+(1 or 0）） mod (1 shl weishu);

inc(shu[zc+1 shl weishu]);


来处理。 时间复杂度不高O（200000）*O（12），由于充分利用问题的特点，比Trie的还要快很多(与楼下引以为豪的Trie速度比较下）。

jzoi —————————————————————— 同学，O（200000）*O（12）是错误的表达方式，渐进时间复杂度是和问题规模有关的，它反映时间的增长速度，但是你这样写。。。 所谓的解码，和hash映射有什么区别吗？

这个和官方题解有什么区别？

用RK算法的人听着，这题不能用RK，质数非常难取，如果谁过了，求一个代码， 血的教训啊 

  Test 1: TEST OK [0.008 secs, 11576 KB]
  Test 2: TEST OK [0.014 secs, 11576 KB]
  Test 3: TEST OK [0.011 secs, 11576 KB]
  Test 4: TEST OK [0.019 secs, 11576 KB]
  Test 5: TEST OK [0.057 secs, 11576 KB]
  Test 6: TEST OK [0.062 secs, 11576 KB]
  Test 7: TEST OK [0.105 secs, 11576 KB]——七哥

[编辑] TRIE

这道题可以用TRIE解决。。详见代码（lxyxynt）

trie的确牛X……最后一组数据只用了0.227秒……我给个C版本的吧…… -by wecing

///////弱弱说一句。。二叉Trie树，最坏一组，0.043s --By Lo

....Test 6: TEST OK [0.022 secs, 2100 KB]最坏一组,哈希表+链表排序 -by Toshio

看来我写残了，用了最小堆优化排序，最大点0.4+...

[编辑] AC自动机

建立一棵深度为B的满二叉trie树，然后对于所有深度大于等于A的节点标记一个单词。对文本进行匹配，排序输出。

参见pascal代码by SRC 

  Test 1: TEST OK [0.019 secs, 9528 KB]
  Test 2: TEST OK [0.019 secs, 9528 KB]
  Test 3: TEST OK [0.011 secs, 9528 KB]
  Test 4: TEST OK [0.030 secs, 9528 KB]
  Test 5: TEST OK [0.035 secs, 9660 KB]
  Test 6: TEST OK [0.032 secs, 9528 KB]
  Test 7: TEST OK [0.057 secs, 9660 KB]——七哥

[编辑] Trie Plus

用trie做 由于主串中只有 0 1 两种字符，故可以直接将二叉树的左右子直接当成‘0’，‘1’速度上会快很多。表示最后一组数据只用了0.108秒 

  Test 1: TEST OK [0.000 secs, 3088 KB]
  Test 2: TEST OK [0.000 secs, 3088 KB]
  Test 3: TEST OK [0.000 secs, 3088 KB]
  Test 4: TEST OK [0.000 secs, 3088 KB]
  Test 5: TEST OK [0.054 secs, 3088 KB]
  Test 6: TEST OK [0.027 secs, 3088 KB]
  Test 7: TEST OK [0.108 secs, 3088 KB]

详情请参见yw100101代码 pascal

[编辑] 简易但非常高效的方法

--消逝者

将二进制转换为十进制，因为只有12位，空间没问题，所以直接建立一个统计数组 int frequency[长度][转化为十进制的数字] 之后就简单了： 

对于每一个长度L：
 枚举起始位置，将以这个起始位置的L位二进制转换为10进制并更新统计数组

建个类： 

class unit
{
 public:
	int frequency,l,num;\\频率，长度，和转换的十进制数
};

新建个队列单位为unit 

对于每一个长度L：
 对于每一个数字N：
  如果总数不为0，新建unit加入队列

对于此队列按题目输出要求快排，最后输出即可。 最大时间0.065 secs.

[编辑] 搜索时的优化

尽管不能区分0和00，只要在前面统一加上个1就行了，最后再去掉。


[编辑] 动态规划

本题可以用动态规划做，速度也很快，最长也就0.042秒 注意到该题比特序列只由0,1,组成，故可以用二进制数表示，再就是长度为n的前缀序列seq(n)出现的次数 f( seq(n) ) = f(seq(n)+'0') + f(seq(n)+'1')( + 1) //最后那项+1是当seq(n)为整个字符串结尾的后缀子串时才加一，否则不加 递推式解释:例如 对于序列 01010010010001000111101100001010011001111000010010011110010000000

序列010出现的次数 = 序列0100出现的次数 + 序列0101出现的次数 然而 序列000出现的次数 = 序列0000出现的次数 + 序列0001出现的次数 + 1 计算000的次数时，末尾加1是因为000整个序列的后缀子串，而010不是整个序列的后缀子串 


  Test 1: TEST OK [0.057 secs, 12284 KB]
  Test 2: TEST OK [0.030 secs, 12284 KB]
  Test 3: TEST OK [0.051 secs, 12284 KB]
  Test 4: TEST OK [0.046 secs, 12284 KB]
  Test 5: TEST OK [0.065 secs, 12284 KB]
  Test 6: TEST OK [0.059 secs, 12284 KB]
  Test 7: TEST OK [0.073 secs, 12284 KB] ——七哥

[编辑] 绝对朴素算法

直接爆搜，而且不用为序列前加一个1，因为虽然0和00变成二进制都是0，但是可以开数组记录每个串的长度，那么0串长度为1，00串长度为2，就可以区分了，最后一个点0.940秒，应该是涉险过关…… 代码见c++，那个最后一个点0.940秒的就是的

[编辑] C++ STL 法

用map<string,int> 保存所有串及其出现过的次数。 之后将其取出并排序即可。 

  Test 1: TEST OK [0.019 secs, 8492 KB]
  Test 2: TEST OK [0.014 secs, 8492 KB]
  Test 3: TEST OK [0.024 secs, 8492 KB]
  Test 4: TEST OK [0.062 secs, 8492 KB]
  Test 5: TEST OK [0.513 secs, 8756 KB]
  Test 6: TEST OK [0.392 secs, 8492 KB]
  Test 7: TEST OK [0.815 secs, 8756 KB]——七哥

[编辑] 参考代码

C

C++

Pascal

Java

[编辑] 引用

[1]

[2]

来自“http://www.nocow.cn/index.php?title=USACO/contact&oldid=35950”
个人工具