注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

1141: [POI2009]Slw 题解  

2013-03-10 23:02:00|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
只是今天起床时突然想起此题了……这题穿过远远的回忆长廊,来到了我面前。
可惜我已经忘记是怎么做了,只记得当时觉得这题真的真的很巧妙。
这一刻真希望自己能够回头,希望当年在我的博客里,写过这题的题解。也许这题只能由我再钻到波兰文题解里才能搞懂了。
所幸在QQ聊天记录里看到了我当年的只言片语。
时光,像一缕细沙。当年使用QQ的人,仿佛已经不是我了。

聊天记录中绿色的是我说的。蓝色的是ds、Parabola、doyouloveme说的。(怎么ds的网名这么多)
紫色是我的吐槽……

18:52:55
斐波拉契单词,你做过没
18:53:03
给跪
18:53:16
……怎么突然跪了
18:53:39
一听就不会做
18:53:45
……
18:53:48
题目名字太神犇了
18:54:01
不……这是一个东西的名称……
18:54:05
不是题目名称
18:54:09
题目叫……单词
18:54:13
………………
18:54:48
0
1
10
101
10110
10110101
1011010110110
18:55:10
18:55:15
有啥性质
18:55:36
题目:http://www.lydsy.com/JudgeOnline/images/1141_1.jpg
18:55:54
……………………………………
18:55:57
暴汗
18:56:10
怎么又暴汗了
18:56:12
等我调完这一题……我就来搞这个
18:56:27
果然是神犇题
18:56:27
呜呜……那我就先无聊一会儿……
18:56:36
…………
18:56:37
因为完全不会做
18:56:45
跪…………
18:56:46
波兰人写的代码又太神
18:56:48
那我不必做了
18:56:51
………………
18:56:52
…………不要这样
18:57:03
又是unava的题?
18:57:12
unava??
18:57:26
unavailable?
18:57:27
不可见
18:57:28
嗯是的
18:57:37
T_T
18:57:38
不要因此丧失动力!
18:57:43
18:57:46
我还是想想
19:01:39
A了囧
19:01:47
orz
19:01:54
………………
19:02:06
我lower_bound写成upper_bound了…………
19:02:09
太傻差了
19:02:25
19:04:25
这是POI哪里的题
19:04:31
2009
19:04:37
哦…………
19:04:40
0
1
10
101
10110
10110101
1011010110110
101101011011010110101
19:04:43
名字叫啥
19:04:46
有个很强的性质
19:04:49
words
19:05:03
我猜一下性质
19:06:46
http://oeis.org/A061107
19:07:44
19:07:50
…………
19:07:56
你看出性质没……
19:08:00
所有性质看到了
19:08:04
………………
19:08:15
在OEIS上……
19:08:19
我不确定你看到了最重要的那个…… [这么显然的性质看不见么……]
19:08:26
说说你看到了啥……
19:09:49
a(n)=a(n-1)*2^floor(log_2(a(n-2))+1)+a(n-2)
19:09:59
这个……很显然
19:10:13
好吧……这就是我说的很重要的家伙
19:10:17
其它的就不用知道了
19:10:29
19:10:36
这个不是很弱智么…………
19:10:41
H(n) = H(n - 1) . H(n - 2) // orz php
19:10:48
对吧
19:10:59
19:11:02
H就是题目中的那家伙
19:11:24
19:11:40
然后我们要解决Hk1 . Hk2 . …… . Hkn
19:11:48
恩……
19:12:03
简记(k1, k2, k3, ..., kn) = w
19:12:18
19:12:52
1141: [POI2009]Slw - vfleaking - vfleaking的博客
然后波兰人得到上面的奇葩
19:13:13
……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………
19:13:19
太神犇了
19:13:23
完全看不懂……
19:13:32
给虐波兰文的跪了
19:14:21
1141: [POI2009]Slw - vfleaking - vfleaking的博客
这一段
19:14:37
恩,看不懂
19:14:47
大体在说……这个算法主体思想就是减少减少再减少
19:14:59
跪了
19:15:05
把k的值从很大减少到0-3
19:15:10
然后特判
19:15:18
…………
19:15:55
…………………………跪了
19:15:59
神犇方法
19:16:06
他代码中忽略特判的地方的话,就是这样子的……把所有的k都减少1……
19:16:27
我不知道为什么减少1还是合法的了
19:16:34
怎么能减少k的值啊囧
19:16:35
对啊
19:16:42
为啥是合法的
19:16:42
布吉岛
19:16:46
神犇方法
19:16:52
19:18:06
只有三个神犇A了此题啊囧
19:18:15
你怎么知道?
19:18:18
感觉不可做………………
19:18:23
1141: [POI2009]Slw - vfleaking - vfleaking的博客
19:18:30
不是不可见么
19:18:55
把别的题的status网址的编号改成这一题的…………
19:19:00
19:19:10
status和discuss都可见……
19:19:16
那sumbit的时候如法炮制?
19:19:18
但是无法submit……………………
19:19:45
[这个地方发了个图表示无法submit…………]
19:19:53
……
19:20:13
………
19:23:45
为啥可以减1啊
19:23:55
……
19:23:59
同问
19:24:05
你等等
19:26:35
找不到题解 T_T_T_T_T_T
19:28:10
为啥能减1呜呜呜……
19:28:30
………………
19:28:50
你去问7k+或者jzp吧……
19:29:08
………………………………
19:30:50
-------------------
|你去问7k+或者jzp吧|
-------------------
话说你刚才的话这样打更酷……
19:31:03
为啥
19:31:12
丁戍  19:28:30
………………
你去问7k+或者jzp吧……
………………………………
19:31:26
…………………………
19:31:26
因为你多打了一排省略号……所以吐槽下……
19:31:37
……………………
19:31:45
太囧了orz
……………………
19:32:02
-----------
|太囧了orz|
-----------
19:32:13
再次吐槽……
19:32:19
…………
19:33:46
肿么做
19:33:53
……………………
19:33:57
不会
19:34:37
他有个示范
1141: [POI2009]Slw - vfleaking - vfleaking的博客
19:34:52
……………………
19:44:02
话说你是逃之夭夭了还是一直在想这道题?
19:46:41
显然前者……………………………………………………
19:46:55
T_T_T_T_T
19:46:55
 [这个地方发了个QQ表情…………]
19:47:25
如果是Kn,你怎么把它变Kn-1
19:47:05
我想不出来啊囧
19:47:21
搜题解也搜不到…………
19:47:44
我错了……
如果是Hn,你怎么把它变Hn-1
19:48:06
 [这个地方发了个QQ表情…………]
19:48:17
 [这个地方发了个QQ表情…………]
19:49:03
……
19:49:22
 [这个地方发了个QQ表情…………]
21:19:49
翻译了下其中的某一段,也许有帮助?
关于H(k-1)到H(k)的变换的一些性质:
把H(k)变到H(k-1)的方法是,如果有个1后面有个0,就把10变为1——不然,就把1变成0。于是的到下面的特性:
(a)H(k)以1开始(当k>=1)
(b)如果k是偶数,那么H(k)以0结尾;如果k是奇数,那么H(k)以1结尾
(c)H(k)没有子串00
(d)H(k)没有子串111(因为H(k-1)具有性质c)
(e)H(k)没有子串101010(因为H(k-1)具有性质d)
21:26:40
哦哦哦!!!我貌似懂了波兰人的意思了orz!
日期: 2012-05-29
10:25:58
跪!!!!!!!!!!!!!!!!!!!!!!!!!!!
10:26:29
话说昨天我貌似还没完全懂
10:26:35
………………
10:26:37
刚才继续往下看了一段
10:27:43
他证明了一个东西:
引理:任何的k不属于{1,3},那么H(k).0不会是任何H(m)的后缀
10:28:33
………………神犇
10:28:55
他是这样证的
10:29:13
首先如果k是偶数
10:29:20
那么H(k)以0结尾
10:29:24
违反了性质3
10:29:43
00不会是任何斐波拉契单词的字串
10:29:44
10:30:38
哦……
10:30:49
如果k是奇数
10:30:57
那么k>=5
10:30:59
对吧
10:31:29
额……对
10:31:31
k>=5就肯定有后缀H(5)
10:31:45
H(5)是10110101
10:31:57
……
10:31:57
那么H(k)就肯定有后缀10101
10:32:06
再加上一个0……
10:32:12
101010
10:32:19
违反性质5
10:32:24
……
10:32:30
orz波兰人
10:32:53
orzVFK
10:33:01
又不是我想的
10:33:16
你看懂了orz
10:34:02
……
10:34:46
但是我不知道这有什么用
10:34:59
波兰人说这个引理将算法证明了
10:35:11
额……
10:36:34
那啥我不太懂Tarjan  [我当时怎么连Tarjan都没搞清楚…………]
10:36:39
给跪
10:36:46
我觉得这怎么都不是线性的
10:36:51
你装弱…………
10:36:57
喂喂喂……
10:37:01
你说的哪个Tarjan
10:37:01
我真不懂
10:37:05
LCA的
10:37:24
为啥不是线性
10:37:28
我至始至终都没搞明白过
10:37:32
…………
10:37:39
for each (u, v) in QUERY
          if visit[v]
              ans(u, v) = FIND(v)
10:37:51
LCA(x)对于每一个x只调用一次啊
10:37:51
它每个节点都要这样一下
10:38:02
好吧……
10:38:04
那岂不是O(nQ)
10:38:08
………………………………
10:38:24
O((n+q)alpha(n))
10:38:33
这个界比较精确了
10:38:52
他是这样的
10:38:53
为什么是n+q不是nq?
10:39:48
LCA(v){
  foreach child of(v){
    xxxxxx;
  }
  foreach query(v,?)              //注意这里是query(v,?)
    xxxxx;
}
10:40:17
哦……
10:40:22
…………
10:40:27
那还是很慢啊
10:40:31
…………………………
10:40:40
万一一个都没visit到呢
10:40:46
10:40:59
哦哦哦……
10:41:15
那最多也是O(n+2q)
10:41:50
如果query(a,b)中!visit[b]……必然到visit b的时候有visit[a]……
10:42:02
哦……
10:42:12
ymds
10:42:19
但是貌似确实很慢………………
10:42:29
我写的nim那么慢………………  [这里指的是我出的BZOJ 2819 Nim,ds是写的离线Tarjan]
10:42:43
估计又是我写抽了……
10:43:01
……因为你没手工栈吧也许
10:43:10
然后你还是两遍dfs吧
10:43:16
QAQ……
10:43:27
一遍dfs
10:43:33
哦…………对哦
10:43:59
那你要写手工栈也会……超级复杂啊囧
10:44:09
对 T_T
11:06:36
标程只是简单地不停地变换……然后检查0前面有没有k不属于{0,3}的家伙
11:07:00
跪了………………
11:11:30
求解 >_<
11:11:59
……?
11:13:08
还是没懂为什么可以全部减1
11:13:22
………………
11:13:25
还是没懂为什么可以只检查那个引理
11:13:26
给跪
11:13:34
给跪
11:13:47
跪啥…………
11:14:09
没啥
11:14:11
膜拜一下
11:14:16
……
11:16:12
哦……我傻了……
11:16:22
明白为啥要减1了
11:16:29
给跪了!!!!!!
11:16:50
他是想把这个东西逆变换……
11:17:06
于是就是每个家伙减1……
11:17:07
……
11:17:26
比如101
逆变换为10
来检查这家伙是否合法
11:17:49
再比如说101101101
逆变换为101010
11:17:59
再来检查是否合法
11:18:11
于是用引理orz
11:18:17
给跪烂
11:18:21
太神犇了
11:18:21
小到一定程度特判
11:18:28
对吧对吧
11:19:09
波兰人太神了……
11:19:29
对……
11:53:29  [这么简单地代码写了30分钟?!真是sb啊!!]
A了
11:53:43
给跪!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
11:54:05
对了
11:54:13
zap那题是要求啥
11:54:23
求gcd为素数还是为1
11:54:31
求gcd为k
11:54:38
哦哦……
11:55:11
zap是哪一年的………………
11:55:16
07
11:55:24
谢了
11:55:52
还是觉得斐波拉契单词那题好神啊……
11:55:55
强烈orz
11:55:58
11:56:34
1142没人提交是什么情况啊囧……
11:56:43
谔谔……
11:57:00
开始啃1142了……

这个聊天记录的结尾,是我做完1141开始做1142了。
顺着做题的时光~

我读完聊天记录终于知道这题怎么做了……
做了一题,后来却忘记是怎么做了,岂不是白做了么……

“不过说一句实话会刷题,刷题也要善于总结反思,这样才能有较大的提高。就像一个长方形,只增加它的长,增长是一次的,但是同时增加长和宽,则增长是二次的。所以各方面都要有所注意,知识是根本,刷题是手段,总结是关键,提高是目的。”
                                           ——湖北省武钢三中 王昊宇神犇 IMO2012金牌得主

最后还是贴出代码吧:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MaxN = 100000;

inline int getint()
{
char c;
while (c = getchar(), '0' > c || c > '9');

int res = c - '0';
while (c = getchar(), '0' <= c && c <= '9')
res = res * 10 + c - '0';
return res;
}

int n;
int k[MaxN];

inline bool check()
{
for (int i = 1; i < n; i++)
if (k[i] == 0 && k[i - 1] != 1 && k[i - 1] != 3)
return false;
return true;
}

inline bool handle()
{
while (n > 1)
{
if (!check())
return false;

if (k[0] == 0)
k[0] = 2;
if (k[n - 1] == 1)
n--;
else if (k[n - 1] == 3)
k[n - 1] = 2;

for (int i = 1; i < n; i++)
{
if (k[i] == 0)
{
if (k[i - 1] == 1)
k[i - 1] = 2, k[i] = -1;
else if (k[i - 1] == 3)
k[i - 1] = 2, k[i] = 2;
}
}
n = remove(k, k + n, -1) - k;

for (int i = 0; i < n; i++)
k[i]--;
}
return true;
}
int main()
{
//freopen("1141.in", "r", stdin);
//freopen("1141.out", "w", stdout);

int nCases;
cin >> nCases;
while (nCases--)
{

cin >> n;
for (int i = 0; i < n; i++)
k[i] = getint();

if (handle())
puts("TAK");
else
puts("NIE");
}

return 0;
}


  评论这张
 
阅读(1175)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017