【题目记录】——2021“MINIEYE杯”中国大学生算法设计超级联赛（5）

阳光穿透心脏的1/2处 2022-09-04 00:41 122阅读 0赞

### 文章目录 ###

*  1003 VC Is All You Need 思维+模拟
 *  1006 Cute Tree 思维
 *  1006 Banzhuan 数学

题目集地址 [2021“MINIEYE杯”中国大学生算法设计超级联赛（5）][2021_MINIEYE_5]  
题目集原地址 [2021“MINIEYE杯”中国大学生算法设计超级联赛（5）][2021_MINIEYE_5 1]  
这次题目集我们做了3道题目,1003,1006,1007

# 1003 VC Is All You Need 思维+模拟 #

题目地址[1003 VC Is All You Need][]  
题意：给你n个点和一个k维空间，问你是否存在一个k-1维得超平面，使得对于所有n个点的所有不同的颜色组合，该平面可以使不同颜色的点分开。  
思路：有规律的，点数不能大于等于维数加2就行。。

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const ll mod = 1e9+7;
    
    int main()
    { 
        int t;
        cin>>t;
        while(t--)
        { 
            ll n,k;
            cin>>n>>k;
            if(n-k <= 1)
            { 
                cout<<"Yes"<<endl;
            }
            else
            { 
                cout<<"No"<<endl;
            }
        }
    }

# 1006 Cute Tree 思维 #

题目地址[1006 Cute Tree][]  
题意：按照题目给出的规则建一棵树，问这棵树有多少个结点。我们是打了个表，然后找规律写的。

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn=2e5+10;
    int a[maxn]= { 3,9,27,81,243,729,2187,6561,19683,59049,177147,531441};
    int main() { 
        ios::sync_with_stdio(0),cin.tie(0);
        int t,n;
        cin >>t;
        while(t--) { 
            cin >>n;
            int ans=4;
            for(int i=0; i<n; i++) { 
                int tmp;
                cin >>tmp;
            }
            if(n==1)
                cout <<1<<endl;
            else if(n==2)
                cout <<3<<endl;
            else if(n==3)
                cout <<4<<endl;
            else { 
                n-=3;
                for(int i=0; i<12; i++) { 
                    if(n>=2*a[i]) { 
                        ans+=3*a[i];
                        n-=2*a[i];
                    } else if(n<2*a[i]&&n>=a[i]) { 
                        ans+=a[i]*2+n-a[i];
                        break;
                    } else { 
                        ans+=n*2;
                        break;
                    }
                }
                cout <<ans<<endl;
            }
        }
        return 0;
    }

# 1006 Banzhuan 数学 #

题目地址[1006 Banzhuan][]  
题意：有一个n*n*n的三维空间，往里面放砖，保证从上面左面和前面看都是n\*n的矩形，在每一个位置放砖的成本是 x ∗ y 2 ∗ z x\*y^2\*z x∗y2∗z，空间符合重力规则，就是说砖头悬空会掉下来。问最大成本和最小成本。  
思路：最大成本一开始觉得就是直接放满整个空间就好结果发现有坑，放满整个空间不能直接一层一层往上放，而应该往最上面一层一直放，直到放满整个空间。  
最小成本，根据公式算得把最下面一层放满，然后沿x轴放一排，沿y轴放一排，这是最小的成本。然后推公式就好了。公式推完后，发现有除法和取模，需要用乘法逆元我们当时搞了半天没搞出来，结束后发现有人直接用java语言的大数交了一发。。下面是用逆元做的题解。

#include <iostream>
    #include <bits/stdc++.h>
    
    #define inf 0x3f3f3f3f
    #define lmax 1000
    #define pi 3.141592653589793238462643383279
    #define eps 1e-7
    
    using namespace std;
    typedef long long ll;
    typedef int type;
    const ll mod=1e9+7;
    
    ll power(ll a,ll b)//方法用的是快速幂，原理用的是费马小定理，如果有不明白的可以看上面的第三个链接，讲解很详细
    { 
        ll ans=1;
        while(b)
        { 
            if(b&1) ans=(ans*a)%mod;
            b>>=1;
            a=(a*a)%mod;
        }
        return ans;
    }
    int main()
    { 
        ll t,n;
        scanf("%lld",&t);
        while(t--)
        { 
            scanf("%lld",&n);
            if(n==1)
            { 
                printf("1\n1\n");
                continue;
            }
            if(n==2)
            { 
                printf("27\n60\n");
                continue;
            }
            ll x,y;
            n=n%mod;
            x=(n*(n+1)%mod)*power(2,mod-2)%mod;
            y=(n*(n+1)%mod)*((2*n+1)%mod)%mod*power(6,mod-2)%mod;
            ll res1=((((x-1+y-1)%mod*(x-1))%mod)+(x*y%mod))%mod;
            ll res2=(x*y%mod*n%mod*n%mod)%mod;
            printf("%lld\n%lld\n",res1,res2);
        }
        return 0;
    }

[2021_MINIEYE_5]: https://acm.hdu.edu.cn/search.php?field=problem&key=2021%A1%B0MINIEYE%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A85%A3%A9&source=1&searchmode=source
[2021_MINIEYE_5 1]: https://acm.hdu.edu.cn/contests/contest_show.php?cid=988
[1003 VC Is All You Need]: https://acm.hdu.edu.cn/showproblem.php?pid=7014
[1006 Cute Tree]: https://acm.hdu.edu.cn/showproblem.php?pid=7017
[1006 Banzhuan]: https://acm.hdu.edu.cn/showproblem.php?pid=7018