BZOJ 1141 [POI2009]Slw 分类讨论

题意:链接方法:分类讨论解析:

Idea rozwizania wzorcowego polega na przeksztacaniu danego cigu w = (k1,…, kn) przez co w rodzaju funkcji odwrotnej do h. Okazuje si, e dla duych elementów cigu w cofanie funkcji h polega na zwykym ich zmniejszaniu, a dla maych (nie wikszych ni 3) trzeba czasem rozpatrywa pewne przypadki szczególne. Operacje wykonywane w algorytmie maj t wasno, e cig dobry przeksztacaj w cig dobry, a zy — w zy. Proces ten doprowadza w końcu do cigu jednoelementowego, który oczywicie jest dobry (wtedy cig pocztkowy te by dobry), lub do cigu, o którym potrafimy stwierdzi, e na pewno jest zy (wtedy pocztkowy by zy). w:=(k1,…,kn) while |w|>1 do begin if w zawiera fragment k,0 dla k ∈ {1,3} then return false Wykonaj kolejno nastpuj ce operacje na cigu w: zamien, je zeli wystepuje, pierwszy element 0 ˙ → 2 zamien, je zeli wystepuje, ostatni element 3 ˙ → 2 usun, je zeli wystepuje, ostatni element równy 1 ˙ zamien wszystkie fragmenty 1 ,0 → 2 zamien wszystkie fragmenty 3 ,0 → 2,2 zmniejsz wszystkie elementy o 1

看懂上面的波兰文你就AC了。其实翻译过来大概是这个意思。我们可以不断的将连接起来的串进行逆转换。然后伪代码具体给出了方式。如果当前序列仅剩一个元素则为可行。如果在序列中存在一个元素为零，则如果他前面的元素不是1或3，则返回0.这是为什么呢?首先对于本题来说，显然我们可以通过手画来搞出来几个数据，，然后我们可以发现其实所有的串是个斐波那契形式每一个是上一个与上上一个的连接。

zamien, je zeli wystepuje, pierwszy element 0 ˙ → 2

上面那句话的意思是如果首位是0的话那么把它转成2.

zamien, je zeli wystepuje, ostatni element 3 ˙ → 2

上面那句话的意思是如果末位是3的话那么把它转成2.然后就是什么找序列中有0的数如果前一个是1，则用2替换两个数。如果前一个是3，则用3替换两个数然后所有元素-1，递归就好了。这是为什么呢?观察下表3->1015->10110101其实总的规律就是什么两个0不能连起来啊不能有101010这种串什么的。代码:;int n;int a[N];int check(){while(n>1){if(!a[1])a[1]=2;if(a[n]==1)a[n]=-1;else if(a[n]==3)a[n]=2;for(int i=2;i<=n;i++){if(!a[i]){if(a[i-1]==1)a[i]=-1,a[i-1]=2;else if(a[i-1]==3)a[i]=a[i-1]=2;;}}int m=0;for(int i=1;i<=n;i++){if(a[i]!=-1)a[++m]=a[i];}n=m;for(int i=1;i<=n;i++)a[i]–;}return 1;}int main(){int t;scanf(“%d”,&t);while(t–){scanf(“%d”,&n);for(int i=1;i<=n;i++)scanf(“%d”,&a[i]);puts(check()?”TAK”:”NIE”);}}

才能做到人在旅途，感悟人生，享受人生。