2016 CCPC网络选拔赛部分题解

约定不等于承诺〃 2021-10-19 10:26 309阅读 0赞

## HDU 5832 - [A water problem][] ##

题意：有两颗星球，一年的长度分别为37天和173天。问第n天时它们是否为新年的第一天。

思路：显然  n 同时被37和173整除时，两种历法都在新年第一天，即 n 是 37\*173=10001的倍数。

坑点：n的长度会达到1e7，我以为要用读入挂之类的，手写用getchar()读入却TLE，直接scanf("%s", n)就没事。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    using namespace std;
    
    int main() {
        int cas = 0;
        char n;
        int val = 0;
        while((n=getchar())!=EOF) {
            if(n!='\n') {
                val = val * 10 + (n-'0');
                val %= 10001;
            } else {
                printf("Case #%d: %s\n", ++cas, val==0?"YES":"NO");
                val = 0;
            }
        }
        return 0;
    }

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    using namespace std;
    char n[10000010];
    int main() {
        int cas = 0;
        while(scanf("%s", n)!=EOF) {
            int val = 0;
            for(int i=0;n[i];i++) {
                val = val * 10 + (n[i]-'0');
                val %= 10001;
            } 
            printf("Case #%d: %s\n", ++cas, val==0?"YES":"NO");
        }
        return 0;
    }

## HDU 5833 - [Zhu and 772002][]  ##

题意：给n个正整数（最大素因子不超过2000），求n个数组成平方数的方案数。

思路：**高斯消元**模板题。

把每个数的素因子加入矩阵A中，设A高斯消元后的秩为 r，则自由元个数为 n - r， 组合方案数为 2^(n - r) - 1。

手写的快速幂函数pow跟C++库重名了导致一直WA。。。

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn = 350;
    const int maxp = 2010;
    const int mod = 1e9+7;
    typedef long long ll;
    
    int pri[maxp], cnt;
    int A[maxp][maxn];
    
    void init() {
        for(int i=2;i<=maxp;i++) {
            bool f = true;
            for(int j=2;j*j<=i;j++) {
                if(i%j==0) {
                    f = false;
                    break;
                }
            }
            if(f) pri[cnt++] = i;
        }
    }
    
    int add(int k, ll val) {
        int row = -1;
        for(int i=0;i<cnt && val>=pri[i];i++) {
            while(val%pri[i]==0) {
                A[i][k] ^= 1;
    
                val /= pri[i];
                row = i;
            }
        }
        return row;
    }
    
    ll mypow(ll a, ll n) {
        ll res = 1;
        while(n) {
            if(n&1) res = res * a % mod;
            a = a * a % mod;
            n >>= 1;
        }
        return res;
    }
    
    int gauss(int m, int n) {
        int i = 0, j = 0 ;
        int r;
        while(i<m && j<n) {
            r = i;
            for(int k=i;k<m;k++) {
                if(A[k][j]) {
                    r = k;
                    break;
                }   
            }
    
            if(A[r][j]) {
                if(r!= i) {
                       for(int k=0;k<=n;k++)
                         swap(A[r][k], A[i][k]);
                } 
                for(int u=i+1;u<m;u++) {
                       if (A[u][j]) {
                           for (int k=i;k<=n;k++)
                            A[u][k] ^= A[i][k];    
                    }     
                } 
                i++;
            }
            j++;
        }
        return i;
    }
    
    
    int main() {
    
        init();
        int cas = 0, T; cin>>T;
    
        while(cas<T) {
            memset(A, 0, sizeof(A));
    
            int n, row = 0;
            ll ai;
            scanf("%d", &n);
            for(int i=0;i<n;i++) {
                scanf("%lld", &ai);
                row = max(row, add(i, ai));
            }
            printf("Case #%d:\n", ++cas);
            int r = gauss(row+1, n);
            printf("%lld\n", mypow(2, n-r)-1);
        }
        
        return 0;
    }

## HDU 5835 - [Danganronpa][] ##

题意：给n个礼物，每个礼物a\[i\]件，分配给学生，每人两件。要求1件可以任意，另一件必须相邻学生种类不同。求可以分出去的最大学生数量。

思路：分析一下可以发现，礼物能否发完只取决于最多数量的那种。先排序，如果最多的礼物减去总和的一半比剩下种类的礼物总数还要多，则能发出去的数量由剩下种类的礼物决定，即 (sum-a\[n-1\])\*2+1。否则全部都能发出去，人数即为 sum/2。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int a[12];
    int main()
    {
        int cas=0, t; cin>>t;
        while(cas<t) {
            int n; scanf("%d", &n);
            int sum = 0;
            for(int i=0;i<n;i++) {
                scanf("%d", &a[i]);
                sum += a[i];
            }
            sort(a, a+n);
            
            printf("Case #%d: %d\n", ++cas, min(sum/2, (sum-a[n-1])*2+1));
        }
        return 0;
    }

## HDU 5839 - [Special Tetrahedron][] ##

题意：给定空间中 n个点(n<=100)，求满足两个条件的特殊四面体的个数。条件1：至少4条边长度相同；条件2：如果只有4条边长度相同，则剩下两条边不能相邻。

思路：C(100, 4)不大，时限4s，暴力枚举即可。四个点不能共面，先求点积再叉积判断是否为0，即四面体体积不能为0。

TM我再次敲错了向量叉积函数cross。。。逐行debug才发现

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    struct P {
        int x, y, z;
        P(int xx=0, int yy=0, int zz=0):x(xx), y(yy), z(zz) {}
        P operator-(const P& a) {
            return P(x-a.x, y-a.y, z-a.z);
        }
        P operator*(const P& b) {
            return P(y*b.z-z*b.y, z*b.x-x*b.z, x*b.y-y*b.x);
        }
        int dis() {
            return x*x + y*y + z*z;
        }
        void print() {
            printf("(%d %d %d)\n", x, y, z);
        }
    }p[210];
    int cross(const P& a, const P& b) {
        return a.x*b.x + a.y*b.y + a.z*b.z;
    }
    
    int main()
    {
        int cas=0, t; cin>>t;
        while(cas<t) {
            int n;
            scanf("%d", &n);
            for(int i=0;i<n;i++) {
                scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].z);
            }
    
            int ans = 0;
            for(int i=0;i<n;i++) {
                for(int j=i+1;j<n;j++) {
                    for(int k=j+1;k<n;k++) {
                        int dis1 = (p[i]-p[j]).dis();
                        int dis2 = (p[i]-p[k]).dis();
                        int dis3 = (p[j]-p[k]).dis();
                        if(dis1!=dis2 && dis2!=dis3 && dis1!=dis3) continue;
    
                        int equa = -1; P t1, t2;
                        if(dis1==dis2 && dis1!=dis3) equa = dis1, t1 = p[j], t2 = p[k];
                        if(dis1==dis3 && dis1!=dis2) equa = dis1, t1 = p[i], t2 = p[k];
                        if(dis2==dis3 && dis1!=dis2) equa = dis2, t1 = p[i], t2 = p[j];
    
                        // if(equa==-1) equa = dis1;
                        for(int l=k+1;l<n;l++) {
                            if(cross((p[i]-p[j])*(p[i]-p[k]), p[i]-p[l])==0) continue;
    
                            if(equa!=-1) { 
                                if((p[l]-t1).dis()==equa && (p[l]-t2).dis()==equa) {
                                    ++ans;
                                //    printf("%d %d %d %d\n", i, j, k, l);
                                }
                            } else { // 底面三边相等 
                                int dis4 = (p[l]-p[i]).dis();
                                int dis5 = (p[l]-p[j]).dis();
                                int dis6 = (p[l]-p[k]).dis();
                                if(dis4==dis1 && dis5==dis1 || dis4==dis1 && dis6==dis1 || dis5==dis1 && dis6==dis1) {
                                    ++ans;
                                //    printf("%d %d %d %d\n", i, j, k, l);
                                }
                            }
                            
                        }
                    }
                }
            }
            
            printf("Case #%d: %d\n", ++cas, ans);
        }
        return 0;
    }

## HDU 5842 - [Lweb and String][] ##

题意：给一个字符串，可以把每个字母映射到数字。问变换后的最长上升子序列的长度是多少。

题解：显然答案为不同字母的个数。

代码：略。

转载于:https://www.cnblogs.com/izcat/p/11310824.html

[A water problem]: http://acm.hdu.edu.cn/showproblem.php?pid=5832
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211018/964b5741660245ff93d69351c825868e.png
[Zhu and 772002]: http://acm.hdu.edu.cn/showproblem.php?pid=5833
[Danganronpa]: http://acm.hdu.edu.cn/showproblem.php?pid=5835
[Special Tetrahedron]: http://acm.hdu.edu.cn/showproblem.php?pid=5839
[Lweb and String]: http://acm.hdu.edu.cn/showproblem.php?pid=5842