测训7 16省Ca1-网友年龄16省Cc3-平方怪圈，16省Ja3-搭积木，16省Ca6-寒假作业，算法训练 - 摆动序列

迷南。 2022-11-05 10:58 114阅读 0赞

### 16省Ca1-网友年龄 ###

[题目链接][Link 1].

【思路】枚举
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
            int a,cnt=0;
        for(a=27;a<=99;a++){
        
            int b=a%10;
            int c=a/10;
            int s=b*10+c*1;
            if(s+27==a)  {
        cout<<a<<endl;
            cnt++;}
        }
        cout << cnt << endl;
        return 0;
    }

### 16省Cc3-平方怪圈 ###

[题目链接][Link 2]  
如果把一个正整数的每一位都平方后再求和，得到一个新的正整数。  
对新产生的正整数再做同样的处理。

如此一来，你会发现，不管开始取的是什么数字，  
最终如果不是落入1，就是落入同一个循环圈。

请写出这个循环圈中最大的那个数字。

请填写该最大数字。  
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

输入  
没有输入。

输出  
1个整数  
【思路】题目考试时，我没看懂，不过写法记一下吧

#include<bits/stdc++.h>
    using namespace std;
    int main(){
        
        int b;
        cin>>b;
        int maxx=0;
        for(int i=1;i<=b;i++){
        //重点
            int a=i;
            while(a!=1){
        
                if(a%2==0) a/=2;
                else  a=a*3+1;
                if(maxx<a)
                    maxx=a;
            }
        }
        cout<<maxx<<endl;
    
    
    return 0;}

### 16省Ja3-搭积木 ###

[题目链接][Link 3].

【思路】全排列 板子题 写好检测就是

#include <bits/stdc++.h>
    
    using namespace std;
    int a[]={
        0,1,2,3,4,5,6,7,8,9},num=0;
    int main()
    {
           do{
        
         if( (a[0]<a[1]&&a[0]<a[2]) && (a[1]<a[3]&&a[1]<a[4]) && (a[2]<a[4]&&a[2]<a[5]) && (a[3]<a[6]&&a[3]<a[7]) && (a[4]<a[7]&&a[4]<a[8]) && (a[5]<a[8]&&a[5]<a[9]) )
    		num++;
    
        }while(next_permutation(a,a+10));
        cout<<num<<endl;
        return 0;
    }

### 16省Ca6-寒假作业 ###

[题目链接][Link 4].  
【思路】与上提一样 可以用全排列

#include <bits/stdc++.h>
    
    using namespace std;
    int a[]={
        1,2,3,4,5,6,7,8,9,10,11,12,13},num=0;
    void check(){
        
         if( (a[0]+a[1]==a[2]) && (a[3]-a[4]==a[5]) && (a[6]*a[7]==a[8]) && (a[10]/a[11]==a[9]))
    		num++;
    }
    int main()
    {
           do{
        
    
          check();
        }while(next_permutation(a,a+13));
        cout<<num<<endl;
        return 0;
    }

### 算法训练 - 摆动序列 ###

[题目链接][Link 5].  
我们知道当序列个数至少为2时那么k的值必须大于等于2，那么序列的个数一定是小于等k的。所以我们可以建立一个dp\[i\]\[j\] i表示序列中的数字个数，j表示k的取值.那我们可以知道当j=2时 对应k的满足上面要求的序列的个数。dp\[i\]\[2\]=i\*(i-1) (i表示对应的k的值)当我们初始化后就是求对应dp的满足上面要求的序列的个数。  
我们dp\[i\]\[j\]可以把k的上一个数的对应种数算到里面去，这种是当没有加当前k的这个值的序列个数，那我们要加当前k的数那么就应该找k-1的数在j-1里面的序列个数就是加当前k有可能组出的摆动序列。那么转移方程就是：dp\[i\]\[j\]=dp\[i-1\]\[j\]+dp\[i-1\]\[j-1\]

#include<bits/stdc++.h>
    using namespace std;
    int main(){
        
         int dp[21][21];
         memset(dp,0,sizeof(dp));
         int K;
         cin>>K;
         int k,n,ans=0;
         for(k=2;k<=K;k++){
        
            for(n=2;n<=k;n++){
        
            if(n==2) dp[k][n]=k*(k-1);
            else if(k==n)  dp[k][n]=2;
            else dp[k][n]=dp[k-1][n-1]+dp[k-1][n];
            }
    
         }
          for(int x=2;x<=K;x++){
        
            ans+=dp[K][x];
         }
         cout<<ans<<endl;
    
    return 0;}

[Link 1]: https://vijos.org/d/gadflycq/contest/6041a227f41362fb2497b7bb/5ab52601d3d8a1371224339f
[Link 2]: https://vijos.org/d/gadflycq/contest/6041a227f41362fb2497b7bb/5ab5294fd3d8a137122433ae
[Link 3]: https://vijos.org/d/gadflycq/contest/6041a227f41362fb2497b7bb/5ab52b9fd3d8a137122433b3
[Link 4]: https://vijos.org/d/gadflycq/contest/6041a227f41362fb2497b7bb/5c78ad59f41362eef13f7671
[Link 5]: https://vijos.org/d/gadflycq/contest/6041a227f41362fb2497b7bb/5a732ff6d3d8a103be7e1c2c