今天考的是一套很基础的模版题，但是我这种蒟蒻竟然还是没有AK，不得不说，蒟蒻和大佬的差别不是一点点啊 

 

1.暴走的猴子（walk.pas/c/cpp)

【题目描述】

从前有一个森林，森林里生活着一群猴子，这里猴子有个恶趣味——暴走。现在给你这个森林里的树木描述，你能计算出这只猴子在暴走k步后会蹦达到哪里吗（友情提示：由于你上周帮助猎人写程序打死了猴子父亲，所以今天猴子特别不爽，故意暴走了很多很多步来为难你，从而导致了k非常的大，做好心里准备噢～）

【输入数据】

第一行两个数n，m表示树木数和询问次数

接下来n行，第i个数一个数ai表示这只猴子当前在第i棵树的话，下一步会走到第ai棵树

接下来m行，每行两个数t,k，询问如果当前猴子在第t棵树，k步之后它会到第几棵树

【输出数据】

m行为每次询问的结果

【样例输入】

3 2

2

3

2

1 2

2 4

【样例输出】

3

2

【数据范围】

共十个测试点，每个测试点数据规模如下所示

1.n=10^2,m=n,k<=10^2

2.n=10^3,m=n,k<=10^3

3.n=10^4,m=1,k<=10^9

4.n=10^5,m=1,k<=10^9

5.n=10^5,m=1,k<=10^12

6.n=10^5,m=1,k<=10^15

7.n=10^5,m=1,k<=10^18

8.n=10^5,m=n,k<=10^12

9.n=10^5,m=n,k<=10^15

10.n=10^5,m=n,k<=10^18

【时限】

1s

【想法】

我自己一直没有把样例读懂所以一直没有做这道题，直到大佬Ztraveller给（gay）我解释了一下样例我才知道自己为啥错

可能刚刚读题我不一定会知道这是怎么做的（毕竟RMQ的题我刷的比较少了）

但是RMQ 确实是一个很有趣的算法，RMQ的定义一般都是f[i][j]表示从第i位开始往后数2^j个位置

RMQ我以前做过都是一般储存f[i][j]第i位起的2^j个位置的最大最小值

但是这道题要储存为第i位开始走2^j个位置后所在的位置 

题不难，理解就好办了

这题可能唯一有理解方面的难度就是最后求值的位置，我先把代码放出来在解释一下

1     while(m--) 2     { 3         scanf("%d%I64d",&t,&k); 4         int sum=0; 5         while(k!=0) 6         { 7             if(k%2!=0)t=dp[t][sum]; 8             k=k/2; 9             sum++;10         }11         printf("%d\n",t);12     }

内部的那个while循环为啥会那样写，我就给2个例子来说明(例子中第i个数都是到第i+1个数，就是一条链)

1.初始：t=1,k=11,sum=0;——>t=d[1,0]=2,k=5,sum=1;——>t=d[2,1]=4,k=2,sum=2;——>t=4,k=1,sum=3——>t=d[4,3]=12,k=0,sum=4,跳出

2.初始：t=1,k=12,sum=0——>t=1,k=6,sum=1;——>t=1,k=3,sum=2——>t=d[1,2]=5,k=1,sum=3——>t=d[5,3]=13,k=0,sum=4,跳出

从两个例子看出，其实这个东东是和二进制挂钩的，11可以分解成8+2+1是2的3,2,0次方，所以你可以发现在t的值有变化时，j的值就是这三个

同理，12分解为8+4是2的3,2次方，所以t的值变化对应的j也是这两个值

最后看一个完整的代码

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #define maxn 100005 9 using namespace std;10 11 long long k;12 int ans,n,dp[maxn][66],m,t;13 14 int main()15 {16 freopen("walk.in","r",stdin);17 freopen("walk.out","w",stdout);18 scanf("%d%d",&n,&m);19 for(int i=1;i<=n;i++)20 scanf("%d",&dp[i][0]);21 for(int j=1;j<=62;j++)22 for(int i=1;i<=n;i++)23 {24 int nxt=dp[i][j-1];25 dp[i][j]=dp[nxt][j-1];26 }27 while(m--)28 {29 scanf("%d%I64d",&t,&k);30 int sum=0;31 while(k!=0)32 {33 if(k%2!=0)t=dp[t][sum];34 k=k/2;35 sum++;36 }37 printf("%d\n",t);38 }39 }
            
           
          
         
        
       
      

 

 

 

2.划分数列（seq.pas/c/cpp)

【题目描述】

给你一个有n个元素的数列，要求把它划分成k段，使每段元素和的最大值最小

【输入格式】

第一行两个正整数n，k

第二行为此数列ai

【输出格式】

一行一个数，为题目所求答案

【样例输入】

5 2

2 1 3 4 5

【样例输出】

9

【数据规模】

30%数据 n <= 30, k <= 10

100%数据 n <= 100000, k <= n, ai <= 10^9

150%数据 n <= 100000, k <= n, |ai| <= 10^9(附：这50分超越了noip难度，大家可以无视）

【时限】

1s

【想法】

150%的数据我自动无视了，我就只谈一谈100%的做法

连我这种蒟蒻都是一 眼看出是二分的题就肯定是二分的题了

对于这道题我错了我只想说：no zuo no die

我的原程序是正确的，但是脑子抽了去压代码去了，然后就全WA了

这道题没有啥思想难度，而且数据范围也好办，二分的r开始是总大小,l开始是1或者单个最大值都没问题，因为范围比较水

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #define maxn 100005 9 using namespace std;10 11 int n,a[maxn],sum,l,r,ans=-1,m;12 13 int check(int mid)14 {15 int tot=0,k=0;16 for(int i=1;i<=n;i++)17 {18 tot+=a[i];19 if(tot>mid)20 {21 tot=a[i];22 k++;23 if(k==m)return 0;//数字还没用完就已经不能再分区了 24 }25 }26 if(tot<=mid&&k
             
              >1;44 if(check(mid)){45 if(mid
             
            
           
          
         
        
       
      

 

 

 

3.无聊的游戏（boring.pas/c/cpp)

【题目描述】

有一个很无聊的游戏，就是——根据递推公式计算数列

没错，这道题就是这么无聊！

给你数列f(0)=1, f(n)=f(n-1)^2+1 (n > 0)

求出f(n)

（既然题目已经这么无聊了，那就不让大家写高精度了，取个模好了）

【输入格式】

一个整数n

【输出格式】

一行一个整数f(n)，结果对1200007取模

【样例输入】

3

【样例输出】

26

【数据规模】

10%数据 1<=n<=10

30%数据 1<=n<=10^6

100%数据 1<=n<=10^9

【时限】

1s

 【思想】

这道题的暴力思路很容易想，但是你可以深入思考一下，这种题数据范围这么大，肯定有正常一点的方法

虽然很多大佬对于这种情况脱口而出：打表暴力

。。。。。。。。。。。这个嘛，打表也是可以A的

但是还有一个简单的方法，就是找规律。。。。。

找规律，怎么找？？？暴力呗。你的暴力思路怎么样的，你就怎么找，这个是要取模的，所以你可以先猜测，是不是会出现循环

如果是，那么是从哪里出现循环，循环节是多少

这个时候你就可以开始跑循环了，如果发现一个位置的取模后的值和之前一个位置是一样的，就说明这里面是有猫腻滴（建议这里用hash判重）

然后你就可以以这两个位置来判断一下下你检测的对不对，手动测几组相邻的数据

然后跑出来后发现循环开始是第803个数，然后循环节是570，意思是前802个数没有循环滴，从803才开始有的

然后这就很好想了吧。803+570=1373，你保个险，随随便便打个1500以内的暴力就行了呗，反正所有的值都在这个范围内

【总结第三题】

考试时，有些题可以先打暴力找规律滴，规律找到了你就可以开始逆天了

【代码】

1 #include
      
        2 #include
       
         3 #include
        
          4 #define mod 1200007 5 using namespace std; 6 long long f[2000],n; 7 int main(){ 8     freopen("boring.in","r",stdin);freopen("boring.out","w",stdout); 9     f[0]=1;for(int i=1;i<=1500;i++){f[i]=(((f[i-1]%mod)*(f[i-1]%mod))%mod+1)%mod;}10     cin>>n;if(n<=803){cout<
         
          <