新兴的 CCPC，真的能不负算法选手的众望，超越日渐下滑的 ICPC 吗

ACM算法日常

发布于 2021-09-28 16:26:15

8260

发布于 2021-09-28 16:26:15

文章被收录于专栏：ACM算法日常ACM算法日常

近几年，ICPC 的题目质量日渐下滑。CCPC 能不能守住题目质量的最后红线，还给算法竞赛选手一个公平公开的比赛环境。

CCPC，中国大学生程序设计竞赛（China Collegiate Programming Contest，简称CCPC）是由教育部高等学校计算机类专业教学指导委员会主办的面向全国高校大学生的年度学科竞赛。

今天我们来看一套 CCPC 2017 年的总决赛题目。

比赛链接

比赛的题目可以在 HDU 中看到，题目编号范围：

https://acm.hdu.edu.cn/showproblem.php?pid=6243

...

https://acm.hdu.edu.cn/showproblem.php?pid=6253

Problem A

题意：超级签到题，1至n，任意排列，求有多少个数不在原位置的期望

题解：输出n-1即可。每个数在自己位置上的期望是

\frac{(n-1)!}{n!}

。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int cas,n;
    scanf("%d",&cas);
    for(int casc = 1;casc <= cas;casc++){
        scanf("%d",&n);
        printf("Case #%d: %d\n",casc,n - 1);
    }
    return 0;
}

Problem C

题意：两个人玩游戏，我赢一分我给你

，我输一分给你

，问你最多能赢几场。

题解：比较简单的贪心题，分情况讨论一下即可。

这里有一个稍微特殊一点的规则就是平局的时候就是必须领先两分，所以局数可以无限增加，所以当

X>Y

的时候，必定是每一句都可以赢的。

#include <bits/stdc++.h>
using namespace std;
#define LL long long

int main()
{
    int cas,n,a,b,k;
    scanf("%d",&cas);
    for(int casc = 1;casc <= cas;casc++){
        scanf("%d%d%d",&b,&a,&k);
        int ans = 0;
        if (b > a) ans = k;
        else{
            for (int i = 1; i <= k; i++){
                if (11 * i * b >= (k - i) * (11 * a - 9 * b)){
                    ans = k - i; break;
                }
            }
        }
        printf("Case #%d: %d\n",casc,ans);
    }
    return 0;
}

Problem E

题意：超级大水题，输出从

到

的数乘以

1.1

求和。

题解：如上操作一番。

#include <bits/stdc++.h>
using namespace std;
#define LL long long

int main()
{
    int cas,n,a;
    scanf("%d",&cas);
    for(int casc = 1;casc <= cas;casc++){
        scanf("%d",&n);
        int ans = 0;
        for(int i = 1;i <= n;i++){
            scanf("%d",&a);
            ans += a;
            ans += (a + 9) / 10;
        }
        printf("Case #%d: %d\n",casc,ans);
    }
    return 0;
}

Problem F

题意：n组人，每组

a_i

个人，每组要么全选，要么不选，总人数不超过m。设计多种选择方案，给每种方案一个概率，使得每个组被选中的概率相等，并最大化。(n <= 10)

题解：因为n很小，所以可以枚举

2^n

种方案，并且设选择每种方案为

x_i

,那么满足

\sum_{i=0}^{2^n-1} x_i = 1

,对于所有总人数超过m的方案，

x_j = 0

。设最后最后每个队伍被选中的概率为

x_{2^n}

，可以列出每个式子,对于i从1到n,满足

\sum_{j = 0}^{2^n-1}{ 2^n and j}x_j = x_{2^n}

。用单纯形法可以解出

x_{2^n}

的最大值。

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int a[20];
int cas,N,M;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-9;

struct Linear_Programming{
    double A[5100][5100],B[5100],c[5100],v;
    int n,m;
    void Pivot(int l,int e){
        int i,j;
        B[l] /= A[l][e];
        for (i = 1; i <= n; i++) if (i != e)
            A[l][i] /= A[l][e];
        A[l][e] = 1 / A[l][e];
        for(i = 1; i <= m; i++)
            if(i != l && fabs(A[i][e]) > EPS){
                B[i] -= A[i][e] * B[l];
                for(j = 1; j <= n; j++) if (j != e)
                    A[i][j] -= A[i][e] * A[l][j];
                A[i][e] = -A[i][e] * A[l][e];
            }
        v += c[e]*B[l];
        for(i = 1; i <= n; i++) if(i!=e)
            c[i] -= c[e] * A[l][i];
        c[e] = -c[e] * A[l][e];
    }
    void Clear(int i)
    {
        for(int j = 1;j <= n;j++)
            A[i][j] = 0;
    }
    void print()
    {
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++)
               printf("%6d  ",(int)A[i][j]);
            cout << B[i]<<endl;
        }
    }
    void build(){
        m = 2 * N;
        n = (1 << N) + 1;
        for(int i = 1;i < n;i++)
            c[i] = 0;
        c[n] = 1;
        for(int i = 1;i <= 2 * N;i += 2){
            Clear(i);
            Clear(i + 1);
            B[i] = 0,B[i + 1] = 0;
            A[i][n] = 1,A[i + 1][n] = -1;
        }
        for(int i = 0;i < (1 << N);i++){
            int sum = 0;
            for(int j = 0;j < N;j++)
                if(i & (1 << j)) sum += a[j + 1];
            if(sum > M){
                m++;
                Clear(m);
                A[m][i + 1] = 1,B[m] = 0;
                continue;
            }
            for(int j = 0;j < N;j++){
                if(i & (1 << j) ){
                    A[j * 2 + 1][i + 1] = -1;
                    A[j * 2 + 2][i + 1] = 1;
                }
            }
        }
        m++;
        Clear(m);
        B[m] = 1;
        for(int i = 1;i <= n - 1;i++)
            A[m][i] = 1;
        m++;
        Clear(m);
        B[m] = -1;
        for(int i = 1;i <= n - 1;i++)
            A[m][i] = -1;
    }


    double Simplex(){
        build();
        v = 0;
        //print();
        int i,l,e;
        while(1){
            for(i=1; i<=n; i++) if(c[i]>EPS) break;
            if((e=i) == n+1) return v;
            double temp = INF;
            for(i = 1; i <= m; i++)
                if( A[i][e]>EPS && B[i]/A[i][e]<temp )
                    temp = B[i] / A[i][e], l = i;
            if (temp == INF) return INF;
            Pivot(l,e);
        }
    }
}Linear;
int main()
{
    scanf("%d",&cas);
    for(int casc = 1;casc <= cas;casc++){
        scanf("%d%d",&N,&M);
        for(int i = 1;i <= N;i++)
            scanf("%d",&a[i]);
        printf("Case #%d: %.14f\n",casc,Linear.Simplex());
    }
}

Problem G

题意：

个区间，取

个区间，使得这些区间并里不同的整数最多。

题解：三方的 dp 轻松推出来

O(mnk)

，然后优化成平方。

对于区间长度那一维可以在更新完所有区间后再更新，那么复杂度为

O(nk+mk)

。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
typedef pair <int, int> P;
const int Maxn = 2010;
int f[Maxn][Maxn] = {};
P a[Maxn];
int main()
{
    int cas, n, m, k;
    scanf("%d",&cas);
    for(int casc = 1;casc <= cas;casc++){
        scanf("%d%d%d",&m, &n, &k);
        for (int i = 1; i <= n; i++){
            int x, y;
            scanf("%d%d", &x, &y);
            a[i] = P(x, y);
        }
        for (int i = 0; i <= m; i++)
            for (int j = 0; j <= k; j++)
                f[i][j] = i;
        for (int j = 1; j <= k; j++){
            for (int i = 1; i <= n; i++){
                f[a[i].second][j] = min(f[a[i].second][j], f[a[i].first - 1][j - 1]);
            }
            for (int i = 1; i <= m; i++){
                f[i][j] = min(f[i][j], f[i - 1][j] + 1);
                //cout << i << " " << j << " " << f[i][j] << endl;
            }
            for (int i = m - 1; i >= 1; i--){
                f[i][j] = min(f[i + 1][j], f[i][j]);
                f[i][j + 1] = f[i][j];
                //cout << i << " " << j << " " << f[i][j] << endl;
            }
            f[m][j + 1] = f[m][j];
        }
        printf("Case #%d: %d\n", casc, m - f[m][k]);
    }
    return 0;
}

Problem H

题意：给定

个

维的点,两两之间距离为1，求最多能加多少个点保证这一性质，并输出坐标。

题解：考虑从

个点加新的一个点的情况，只需要找到

个点所在的

m-1

维平面上的中心以及法向量，可以找规律发现新加的点离

维平面的距离为

\sqrt{\frac{m + 1}{2 * m}}

中心非常好求，法向量则可以通过两点之间的中垂面(高维中不知道叫什么)的交线来确定，这个可以利用高斯消元求出来（没用的维数用1来代替，最后乘以距离的权重就可以）。

列的方程是

(\vec{p_{i + 1}} - \vec{p_{i}}) \times \vec{x} ^ {T} = 0

（

是已添加的点,由于方程个数少于未知数，将未知数后若干位直接标为1就可以求出确定的向量了）。

#include <bits/stdc++.h>
using namespace std;
int const maxn = 110;
const double eps=1e-10;
double a[maxn][maxn],x[maxn];
int equ,var;
double sqr(double x) {return x * x;}
int Gauss()
{
    int i, j, k, max_r, col;
    double tmp;
    col = 0;

    for(k = 0; k<equ && col<var; k++, col++)
    {
        max_r = k;
        for(i = k+1; i < equ; i++)
            if(fabs(a[i][col])-fabs(a[max_r][col]) > eps)
            max_r = i;

        if(max_r != k)
            for(j = k; j < var+1; j++)
            swap(a[k][j], a[max_r][j]);

        if(fabs(a[k][col]) < eps)
        {
            k--;
            continue;
        }
        for(i = k+1; i < equ; i++)
        {
            if(fabs(a[i][col]) > eps)
            {
                double t = a[i][col]/a[k][col];  //这里和整型的不同。
                a[i][col] = 0.0;

                for(j = col; j < var+1; j++)
                a[i][j] -= a[k][j]*t;
            }
        }
    }
    for(i = var-1; i >= 0; i--)
    {
        if(fabs(a[i][i]) < eps) continue;
        tmp = a[i][var];
        for(j = i+1; j < var; j++)
        if(a[i][j] != 0)
        tmp -= a[i][j]*x[j];

        //if(tmp%a[i][i] != 0) return -2;
        x[i] = tmp/a[i][i];
    }
    return 0;
}
bool check(){

}
double X[maxn][maxn];
int main(){
    int cas;
    scanf("%d",&cas);
    for(int casc = 1;casc <= cas;casc++){
        int n, m;
        scanf("%d%d", &n, &m);
        printf("Case #%d: %d\n", casc, n + 1 - m);
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++){
                scanf("%lf", &X[i][j]);
                if (m == 1 && j != 1) X[2][j] = X[1][j];
        }
        if (m == 1){
            X[2][1] = X[1][1] + 1, m++;
            for (int j = 0; j < n; j++){
                printf("%.12f%c", X[2][j + 1], j == n - 1 ? '\n' : ' ');
            }
        }
        for (int i = m; i <= n; i++){
            equ = i - 1, var = i - 1;
            double cen[maxn] = {};
            for (int j = 1; j <= i; j++)
                for (int k = 1; k <= n; k++)
                    cen[k] += X[j][k] / i;
            for (int j = 0; j < i; j++){
                double tmp = 0;
                for (int k = 0; k < var; k++)
                    a[j][k] = X[j + 2][k + 1] - X[j + 1][k + 1], x[k] = 0;
                for (int k = var; k < n; k++)
                    tmp -= X[j + 2][k + 1] - X[j + 1][k + 1], x[k] = 1.0;
                //cout << tmp << endl;
                a[j][var] = tmp;
            }
            Gauss();
            double div = 0;
            for (int j = 0; j < n; j++) div += x[j] * x[j];
            div = sqrt(div / (i + 1) * (2 * i));
            for (int j = 0; j < n; j++){
                x[j] /= div;
                //cout << x[j] << endl;
                X[i + 1][j + 1] = cen[j + 1] + x[j];
                printf("%.12f%c", cen[j + 1] + x[j], j == n - 1 ? '\n' : ' ');
            }
            for (int j = 1; j < i; j++){
                double tmp = 0;
                for (int k = 1; k <= n; k++){
                    tmp += sqr(X[i][k] - X[j][k]);
                }
                //cout << j << " " << tmp << endl;
            }
        }
    }
}

Problem I

题意：联通且颜色相同的边算作一组，会有

次修改，求每一次修改以后的组数。

题解：我们用

f[i]

表示结点

连出去的边所拥有的颜色数量，因为直接

\sum f[i]

会有

条边重复计算，所以一个图上的总的组数就是

\sum f[i]-n

但是应该很容易的注意到一种特殊情况：当基环树环上的颜色相同时，我们应该把答案变成

\sum f[i]-n+1

这样一来，我们就可以直接在线处理了。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int n,m,f[200010],fa[200010],c[200010],v[200010];
int pre;
map<int,int> a[200010];
map<int,int> edge[200010];
map<int,int> loop[200010];
struct data
{
    int x,y,z;
}E[200010];
int flag;

void dfs(int x,int par)
{
    if (flag) return ;
    v[x]  = 1;
    //cout<<x<<" "<<par<<endl;
    for(map<int,int>::iterator ite = edge[x].begin();ite != edge[x].end();ite++)
    {
        if (flag) return ;
        //cout<<x<<" "<< ite -> first<<" "<<par<<endl;
        if( ite -> first != par )
        {
            if (v[ite -> first])
            {
                flag=1;
                loop[ite -> first][x]=1,loop[x][ite -> first]=1;
                //cout<<"loop"<<ite -> first<<" "<<x<<endl;
                int y=x;
                while(y!=ite -> first)
                {
                    loop[y][fa[y]]=1;
                    loop[fa[y]][y]=1;
                    //cout<<"loop"<<y<<" "<<fa[y]<<endl;
                    y=fa[y];
                }
                return ;
            }
            fa[ite -> first]=x;
            dfs(ite -> first,x);
        }
    }
}

int main()
{
    int cas;
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    scanf("%d",&cas);
    for(int casc = 1;casc <= cas;casc++)
    {
        memset(c,0,sizeof(c));
        memset(v,0,sizeof(v));
        memset(f,0,sizeof(f));
        printf("Case #%d:\n",casc);
        scanf("%d%d",&n,&m);
        int x,y,z;int ans=0;
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            E[i].x=x,E[i].y=y,E[i].z=z;
            if (a[x][z]==0) a[x][z]=1,f[x]++,ans++;else a[x][z]++;
            if (a[y][z]==0) a[y][z]=1,f[y]++,ans++;else a[y][z]++;
            edge[x][y]=z,edge[y][x]=z;
        }
        flag=0;dfs(1,0);
        int s=0;
        for (int i=1;i<=n;i++)
            if (loop[E[i].x][E[i].y]==1||loop[E[i].y][E[i].x]==1)
            {
                if (c[E[i].z]==0) s++;
                c[E[i].z]++;
            }
        for (int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            a[x][edge[x][y]]--;a[y][edge[x][y]]--;
            if (a[x][edge[x][y]]==0) ans--,f[x]--;
            if (a[y][edge[x][y]]==0) ans--,f[y]--;
            if (loop[x][y]==1||loop[y][x]==1)
            {
                c[edge[x][y]]--;
                if (c[edge[x][y]]==0) s--;
            }
            if (a[x][z]==0) a[x][z]=1,f[x]++,ans++;else a[x][z]++;
            if (a[y][z]==0) a[y][z]=1,f[y]++,ans++;else a[y][z]++;
            if (loop[x][y]==1||loop[y][x]==1)
            {
                if (c[z]==0) s++;
                c[z]++;
            }
    //printf("%d\n",s);
            edge[x][y]=z,edge[y][x]=z;
            if (s==1) printf("%d\n",ans-n+1);else printf("%d\n",ans-n);
        }
        for (int i=1;i<=n;i++)
            a[i].clear(),edge[i].clear(),loop[i].clear();
    }
    return 0;
}

Problem J

题意：给出

个时刻两个人分别在的位置，求一种可行的相邻车站之间所要花费的时间，使得满足限制条件。

题解：查分约束系统。对于形如

|d_i-d_j| \le x

的式子，我们可以条件负号，是的所有的不等式同向，然后添加边

cost(i,j)=x

，在图上直接跑最短路径即可。

这道题目，我们对于两个人都是同时在一个站台的，及a a b b形式的，我们只需要一个约束条件

b-a\le x

而对于其余形如a b c d型的，我们则需要两个约束条件

c-b\le x-1

d-a\ge x+1

最后所有的

d[i]-d[i-1]

就是我们所求的答案

#include <bits/stdc++.h>
using namespace std;
#define LL long long

int n,m,x,v[2010],chu[2010];
struct data
{
 int x;LL y;
 data(int a=0,int b=0):x(a),y(b){}; 
};
LL f[2010];
const LL inf=1000000000000000000LL;

int main()
{
    int cas;
    scanf("%d",&cas);
    for(int casc = 1;casc <= cas;casc++)
    {
     vector<data> a[2010];
     scanf("%d%d%d",&n,&m,&x); 
  for (int i=2;i<=n;i++)
   a[i-1].push_back(data(i,-1LL)),v[i]=0,chu[i]=0,f[i]=inf;
  int A,B,C,D;
  for (int i=1;i<=m;i++)
  {
   scanf("%d%d%d%d",&A,&B,&C,&D);
   if (A==B&&C==D) a[C].push_back(data(A,(LL)x)),a[A].push_back(data(C,(LL)-x));
   else a[A].push_back(data(D,(LL)-x-1)),a[C].push_back(data(B,(LL)x-1));
  }
  v[1]=1,chu[1]=0;int ans=0;f[1]=0;
  queue<int> q;q.push(1);
  while(!q.empty())
  {
   int x=q.front();q.pop();chu[x]++;v[x]=0;
   //cout<<x<<" "<<f[x]<<endl;
   if (chu[x]>n) {ans=1;break;}
   for (int i=0;i<a[x].size();i++)
    if (f[x]+a[x][i].y<f[a[x][i].x])
    {
     f[a[x][i].x]=f[x]+a[x][i].y;
     if (!v[a[x][i].x]) v[a[x][i].x]=1,q.push(a[x][i].x);
    }
  }
  printf("Case #%d: ",casc);
  if (ans) puts("IMPOSSIBLE");
  else
  {
   for (int i=2;i<n;i++)
    printf("%d ",-f[i]+f[i-1]);
   printf("%d\n",-f[n]+f[n-1]);
  }
    }
    return 0;
}

Problem K

题意：给你一个无限大的平面，从一个点开始，让马跳日，每一次可以跳八个方向，问第

次跳完后，一共占领了多少个地方。

题解：手算或者bfs打表找规律，可以发现在

n\ge 4

以后，直接查分就可以得到等差数列

可以推出公式就是

(n-6)*176+(n-6)*(n-7)*14+473

由于这道题目的答案会爆long long,所以需要用unsigned long long，但用unsigned long long需要注意公式里面

n-7

会出问题

#include <bits/stdc++.h>
using namespace std;
#define LL unsigned long long

int main()
{
    int cas;
    LL n;
    scanf("%d",&cas);
    for(int casc = 1;casc <= cas;casc++){
        scanf("%llu",&n);
        if (n==0) printf("Case #%d: 1\n",casc);
        else if (n==1) printf("Case #%d: 9\n",casc);
        else if (n==2) printf("Case #%d: 41\n",casc);
        else if (n==3) printf("Case #%d: 109\n",casc);
        else if (n==4) printf("Case #%d: 205\n",casc);
        else if (n==5) printf("Case #%d: 325\n",casc);
        else if (n==6) printf("Case #%d: 473\n",casc);
        else printf("Case #%d: %llu\n",casc,(n-6)*176+(n-6)*(n-7)/2*28+473);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2021-09-19，如有侵权请联系 cloudcommunity@tencent.com 删除

https