本文共 3274 字，大约阅读时间需要 10 分钟。
小 L L L热衷于 u n d e r c a r d s undercards undercards。
在 u n d e r c a r d s undercards undercards中，有四个格子。每个格子要么是空的，要么住着一只 B i g B o b BigBob BigBob。每个 B i g B o b BigBob BigBob有一个不超过 k k k的血量；血量减到 0 0 0视为死亡。那个格子随即空出。
当一只 B i g B o b BigBob BigBob受到伤害后，假如它没有死亡且剩余血量为 t t t，它会从左数第一个空格处召唤一只血量为 a [ t ] a[t] a[t]的 B i g B o b BigBob BigBob；若没有空格，则不会召唤。
法术 R R R定义为：从左往右，对每个 B i g B o b BigBob BigBob造成一点伤害；假如有 B i g B o b BigBob BigBob死亡，重复上述效果。
聪明的小 L L L发现，在某些情况下，当他发动法术 R R R时，游戏会陷入循环。
他想求出这样的初始情形有多少种。输入一个正整数 k k k；
随后一行 k − 1 k-1 k−1个正整数，表示 a [ 1 ] ～ a [ k − 1 ] a[1]～a[k-1] a[1]～a[k−1]；输出一个整数，表示答案。
22
31
B i g b o b Bigbob Bigbob最多有 2 2 2血，满血 b i g b o b bigbob bigbob受伤会召出新的。
循环的初始状态有： ( 2 , 1 , 0 , 0 ) , ( 1 , 2 , 0 , 0 ) , ( 2 , 0 , 1 , 0 ) , ( 2 , 1 , 1 , 0 ) , ( 0 , 2 , 1 , 0 ) , ( 1 , 2 , 1 , 0 ) , ( 2 , 2 , 1 , 0 ) , ( 1 , 0 , 2 , 0 ) , ( 0 , 1 , 2 , 0 ) , (2,1,0,0),(1,2,0,0),(2,0,1,0),(2,1,1,0),(0,2,1,0),(1,2,1,0),(2,2,1,0) ,(1,0,2,0),(0,1,2,0), (2,1,0,0),(1,2,0,0),(2,0,1,0),(2,1,1,0),(0,2,1,0),(1,2,1,0),(2,2,1,0),(1,0,2,0),(0,1,2,0), ( 1 , 1 , 2 , 0 ) , ( 2 , 1 , 2 , 0 ) , ( 2 , 1 , 0 , 1 ) , ( 0 , 2 , 0 , 1 ) , ( 1 , 2 , 0 , 1 ) , ( 0 , 2 , 1 , 1 ) , ( 1 , 2 , 1 , 1 ) , ( 0 , 0 , 2 , 1 ) , (1,1,2,0),(2,1,2,0),(2,1,0,1),(0,2,0,1),(1,2,0,1),(0,2,1,1),(1,2,1,1),(0,0,2,1), (1,1,2,0),(2,1,2,0),(2,1,0,1),(0,2,0,1),(1,2,0,1),(0,2,1,1),(1,2,1,1),(0,0,2,1), ( 1 , 0 , 2 , 1 ) , ( 0 , 1 , 2 , 1 ) , ( 1 , 1 , 2 , 1 ) , ( 2 , 1 , 2 , 1 ) , ( 0 , 2 , 2 , 1 ) , ( 1 , 2 , 2 , 1 ) , ( 2 , 1 , 0 , 2 ) , ( 1 , 2 , 0 , 2 ) , (1,0,2,1),(0,1,2,1),(1,1,2,1),(2,1,2,1),(0,2,2,1),(1,2,2,1),(2,1,0,2) ,(1,2,0,2), (1,0,2,1),(0,1,2,1),(1,1,2,1),(2,1,2,1),(0,2,2,1),(1,2,2,1),(2,1,0,2),(1,2,0,2), ( 2 , 0 , 1 , 2 ) , ( 2 , 1 , 1 , 2 ) , ( 0 , 2 , 1 , 2 ) , ( 1 , 2 , 1 , 2 ) , ( 2 , 2 , 1 , 2 ) , ( 2 , 1 , 2 , 2 ) (2,0,1,2),(2,1,1,2),(0,2,1,2),(1,2,1,2),(2,2,1,2),(2,1,2,2) (2,0,1,2),(2,1,1,2),(0,2,1,2),(1,2,1,2),(2,2,1,2),(2,1,2,2) 共 31 31 31种。对于 30 ％ 30％ 30％的数据， k ≤ 5 k≤5 k≤5；
对于 70 ％ 70％ 70％的数据， k ≤ 10 k≤10 k≤10, a [ i ] = k a[i]=k a[i]=k； 对于 100 ％ 100％ 100％的数据， k ≤ 15 k≤15 k≤15, 1 ≤ a [ i ] ≤ k 1≤a[i]≤k 1≤a[i]≤k。这道题是一道大模拟题。
我们就按着题目模拟一遍就可以了，判断是否会循环的时候可以用 d f s dfs dfs。#include#include using namespace std;int K,A[15],next[70001],ans,can[70001];bool in[70001],yes[70001];int place(int a, int b, int c, int d)//给每一种情况找一个地址{ return a*(K+1)*(K+1)*(K+1)+b*(K+1)*(K+1)+c*(K+1)+d;}int ch(int a,int b,int c,int d)//模拟{ bool yes=0; if (a) { a--; if (a) { if (!b) b=A[a]; else if (!c) c=A[a]; else if (!d) d=A[a]; } else yes=1; } if (b) { b--; if (b) { if (!a) a=A[b]; else if (!c) c=A[b]; else if (!d) d=A[b]; } else yes=1; } if (c) { c--; if (c) { if (!a) a=A[c]; else if (!b) b=A[c]; else if (!d) d=A[c]; } else yes=1; } if (d) { d--; if (d) { if (!a) a=A[d]; else if (!b) b=A[d]; else if (!c) c=A[d]; } else yes=1; } if (!yes) return -1; return place(a,b,c,d);}void dfs(int x)//判断是否陷入循环{ if (in[x]) return ; in[x]=1; if (next[x]==-1) { can[x]=1; return ; } dfs(next[x]); if (can[next[x]]==1) can[x]=1; else can[x]=2;}int main(){ memset(next,-1,sizeof(next));//初始化 scanf("%d",&K);//读入 for (int i=1;i
转载地址：http://pcth.baihongyu.com/