2017中国大学生程序设计竞赛 - 女生专场

我会带着你远行 2022-05-25 07:15 164阅读 0赞

1.HDU-6023

[点我看题][Link 1](此链接为vjudge链接

题意：给出题目的数量，提交的次数，每次提交的题目编号，提交时间以及结果，其中罚时为每次错误提交20min+第一次成功提交的时间，问最后AC的题目数量以及总罚时。提交结果不存在CE。

分析：水题，直接计算。

参考代码：

#include<cstdio>
    #include<cmath>
    #include<cctype>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<stack>
    #include<queue>
    #include<map>
    #include<set>
    #include<list>
    #include<vector>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    const int maxn = 20;
    const int maxm = 1e3+10;
    int n,m;
    int cnt[maxn];
    int ac[maxn];
    int ans[maxn];
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while( T--)
        {
            mem(ac,0);
            mem(cnt,0);
            mem(ans,0);
            scanf("%d%d",&n,&m);
            int pro,hour,minu;
            char res[5];
            while( m--)
            {
                scanf("%d%d:%d%s",&pro,&hour,&minu,res);
                if( !ac[pro-1000])
                {
                    if( strcmp(res,"AC") == 0)
                    {
                        ac[pro-1000] = 1;
                        ans[pro-1000] = cnt[pro-1000]*20+hour*60+minu;
                    }
                    else
                    {
                        cnt[pro-1000]++;
                    }
                }
            }
            int accept = 0;
            int result = 0;
            for( int i = 1; i <= n; i++)
            {
                if( ac[i])
                {
                    accept++;
                    result += ans[i];
                }
            }
    
            printf("%d %d\n",accept,result);
        }
    
    	return 0;
    }

2.HDU-6024

[点我看题][Link 2]

题意：给出n个教室，再给出n个教室得到坐标(x轴上的)以及在每个教室上建造商店的花费，如果某个教室不建造商店的话，花费为其左边的最右商店到自己距离，问如何去建造商店可以使得最后的开销最小。

分析：简单的一个dp，dp\[i\]\[0\]为第i个教室不建造商店时的前i个教室的总花费，dp\[i\]\[1\]为在第i个教室建商店时前i个教室的花费和。可以很明显的得到dp\[i\]\[1\]=min(dp\[i-1\]\[0\],dp\[i-1\]\[1\])+c\[i\]，c\[i\]为在第i个教室建造商店的花费。要求dp\[i\]\[0\]得话，首先要找到左边最右的商店，但是这个求解是一个动态的过程，我们只能一一枚举前i-1个商店，假设我们枚举到了第j(1=<j<i)个商店，那么dp\[i\]\[0\]=min(dp\[i\]\[0\],dp\[j\]\[1\]+(sum\[i\]-sum\[j\]-(i-j)\*p\[j\]))，sum\[i\]-sum\[j\]-(i-j)\*p\[j\]这个式子表示的是第j个商店依次到第j+1,...,i个教室的距离之和，p\[i\]表示第j个超时的位置，sum\[i\]为p\[i\]的前缀和，具体过程可以自行推导。

参考代码：

#include<cstdio>
    #include<cmath>
    #include<cctype>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<stack>
    #include<queue>
    #include<map>
    #include<set>
    #include<list>
    #include<vector>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    typedef long long ll;
    const ll inf = 0x3f3f3f3f3f3f3f3f;
    const int maxn = 3e3+10;
    int n;
    struct classroom{
        ll p,c;
    };
    classroom cr[maxn];
    ll dp[maxn][2];
    ll sum[maxn];//前缀和
    
    bool cmp( classroom cr1, classroom cr2)
    {
        return cr1.p < cr2.p;
    }
    
    int main()
    {
        while( ~scanf("%d",&n))
        {
            mem(dp,inf);
            mem(sum,0);
            for( int i = 1; i <= n; i++)
                scanf("%lld%lld",&cr[i].p,&cr[i].c);
            sum[0] = 0;
            sort(cr+1,cr+n+1,cmp);
            for( int i = 1; i <= n; i++)
                sum[i] = sum[i-1]+cr[i].p;
    
            dp[1][0] = inf;
            dp[1][1] = cr[1].c;
            for( int i = 2; i <= n; i++)
            {
                for( int j = 1; j < i; j++)
                {
                    dp[i][0] = min(dp[i][0],dp[j][1]+(sum[i]-sum[j]-(ll)(i-j)*cr[j].p));
                }
    //            ll t = 0;
    //            for( int j = i-1; j > 0; j--)
    //            {
    //                t += (i-j)*(cr[j+1].p-cr[j].p);
    //               dp[i][0] = min(dp[i][0],dp[j][1]+t);
    //            }
                dp[i][1] = min(dp[i-1][0],dp[i-1][1])+cr[i].c;
            }
            printf("%lld\n",min(dp[n][0],dp[n][1]));
        }
    
    	return 0;
    }

3.HDU-6025

题意：给出一个n，然后再给出n个数，删除n个数中的一个数，使得剩下数的GCD最大并输出最大GCD。

分析：先求出这n个数的GCD，然后再依次求前i个数的GCD，如果第i个数使得当前的GCD等于n个数的GCD，就删除第i个数，求剩下数的GCD即为结果。

参考代码：

#include<cstdio>
    #include<cmath>
    #include<cctype>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<stack>
    #include<queue>
    #include<map>
    #include<set>
    #include<list>
    #include<vector>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    const int maxn = 1e5+10;
    int n;
    int a[maxn];
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while( T--)
        {
            scanf("%d%d",&n,&a[0]);
            int gcd = a[0];
            for( int i = 1; i < n; i++)
            {
                scanf("%d",&a[i]);
                gcd = __gcd(gcd,a[i]);
            }
            int cnt = 0;
            int tmp = a[0];
            if( tmp == gcd)
            {
                cnt = 1;
                tmp = a[1];
            }
    
            for( int i = 1; i < n; i++)
            {
                if( cnt == 1)
                {
                    tmp = __gcd(tmp,a[i]);
                }
                else
                {
                    if( __gcd(tmp,a[i]) == gcd)
                    {
                        cnt = 1;;
                    }
                    else
                        tmp = __gcd(tmp,a[i]);
                }
            }
            printf("%d\n",tmp);
        }
    
    	return 0;
    }

4.HDU-6026  
[点我看题][Link 3]

题意：给出一个有n个节点(0~n-1)无向有权图，去掉图的某些边，使得最后为一棵树(n-1条边)，且每个点到节点0的距离跟原来图的最短路径一样，问有多少种方法，结果mod1e9+7.

不太会图论啊= =

5.HDU-6027

[点我看题][Link 4]

题意：很明显了

分析：直接暴力，时间复杂度为O(n\*k)

参考代码：

6.HDU-6028

0ac= =

7.HDU-6029

[点我看题][Link 5]

题意：有n(1~n)个节点，对于第i(2=<i<=n)个节点有两种操作，(1)第i个节点与前i-1个节点之间都添加一条边;(2)不加边，问能否删掉一些边，使得对于每个节点有且只有一个节点与之相连，存在这种情况输出Yes，反之输出No，题目给出n以及第2~n个节点的选择。

分析：如果n为奇数的话，肯定无法形成这样的边对，如果n为偶数，每个选择2的后面都有一个1与之对应，就ok，其中我们假设第0个的选择是2。

参考代码：

8.HDU-6030

[点我看题][Link 6]

题意：小Q想串一个长度为n的项链，对于每个质数长度的珠子，要保证红色的珠子数量大于等于蓝色珠子的数量，问有多少种方法。结果mod1e9+7.

分析：要保证所有质数长度的链子满足红色珠子数量大于蓝色，其实我们只要保证连续2个和3个珠子组成的链子数中红色数量大于等于蓝色珠子的数量，为什么这么说呢，因为大于3的质数都可以用2的倍数+3的倍数表示。

当n=2的时候，有三种情况，rr、rb、br，其中r代表红色，b代表蓝色，那么当n等于3时，相当于在n=2的基础上添加一个r或b，我们发现，形成以rr结尾的情况是在rr或br额基础上添加一个r，形成rb结尾的情况是在rr的基础上添加一个b，形成以br结尾的情况是在rb的基础上添加一个r，那么我们假设a\[\]、b\[\]、c\[\]分别表示后两个字符为rr、rb、br的字符串种类数，我们根据上面的规则可以得到

a\[i\]=a\[i-1\]+c\[i-1\],b\[i\]=a\[i-1\],c\[i\]=b\[i-1\]，我们以S\[i\]表示满足条件的种类数，s\[i\]=a\[i\]+b\[i\]+c\[i\]，我们通过对上面的式子化简，可以得到s\[n\]=s\[n-1\]+s\[n-3\]，题目给出的n高达1e18，直接递推无法的到结果，要用到矩阵快速幂。

根据s\[n\]=s\[n-1\]+s\[n-3\]，我们可以得到一个三阶矩阵：

1 0 1

1 0 0

0 1 0

然后利用矩阵快速幂求解。

参考代码：

#include<cstdio>
    #include<cmath>
    #include<cctype>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<stack>
    #include<queue>
    #include<map>
    #include<set>
    #include<list>
    #include<vector>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    typedef long long ll;
    const ll mod = 1000000007;
    ll n;
    ll a[4] = {0,2,3,4};
    struct mat{
        ll a[3][3];
    };
    mat ini = { 1,0,1,1,0,0,0,1,0};
    
    mat MatMul( mat x, mat y)
    {
        mat res;
        mem(res.a,0);
        for( int  i = 0; i < 3; i++)
        {
            for( int j = 0; j < 3; j++)
            {
                for( int k = 0; k < 3; k++)
                {
                    res.a[i][j] += (x.a[i][k]*y.a[k][j])%mod;
                    res.a[i][j] %= mod;
                }
            }
        }
        return res;
    }
    
    mat MatPow( ll n)
    {
        mat c,res;
        c.a[0][0] = c.a[0][2] = c.a[1][0] = c.a[2][1] = 1;
        c.a[0][1] = c.a[1][1] = c.a[1][2] = c.a[2][0] = c.a[2][2] = 0;
        res.a[0][0] = res.a[1][1] = res.a[2][2] = 1;
        res.a[0][1] = res.a[0][2] = res.a[1][0] = res.a[1][2] = res.a[2][0] = res.a[2][1] = 0;
        while( n)
        {
            if( n%2)
                res = MatMul(res,c);
            c = MatMul(c,c);
            n >>= 1;
        }
    
        return res;
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while( T--)
        {
            scanf("%lld",&n);
            if( n < 4)
                printf("%lld\n",a[n]);
            else
            {
                mat res = MatPow(n-3);
                printf("%lld\n",(res.a[0][0]*a[3]%mod+res.a[0][1]*a[2]%mod+res.a[0][2]*a[1]%mod)%mod);
            }
        }
    
    	return 0;
    }

9.HDU-6031

10.HDU-6032

[Link 1]: https://vjudge.net/contest/227687#problem/A
[Link 2]: https://vjudge.net/contest/227687#problem/B
[Link 3]: https://vjudge.net/contest/227687#problem/D
[Link 4]: https://vjudge.net/contest/227687#problem/E
[Link 5]: https://vjudge.net/contest/227687#problem/G
[Link 6]: https://vjudge.net/contest/227687#problem/H