XDU_ACM 第二场PK赛 （gym101412）

// 比赛过去很久了，由于马上要打区域赛，整理一下当时的题解
比赛时间：2019.9.24
题目来源：https://codeforces.com/gym/101412

---

 

A Ginkgo Numbers

水题，根据第一条提示暴力判断即可。

 

C One-Dimensional Cellular Automaton

在队友提示下，每一行可以由前一行矩阵递推得到，矩阵快速幂。

#include<cstdio>
using namespace std;
int N, M;
int arr[52];
struct Mat {
    int m[52][52];
    Mat operator*(const Mat& a) {
        Mat res = {0};
        for(int i=1;i<=N;i++) {
            for(int j=1;j<=N;j++) {
                for(int k=1;k<=N;k++) {
                    if(m[i][k] && a.m[k][j])
                        res.m[i][j] = (res.m[i][j]+ m[i][k]*a.m[k][j]) % M;
                }
            }
        }
        return res;
    }
};

Mat getI() {
    Mat I = {0};
    for(int i=1;i<=50;i++) {
        I.m[i][i] = 1;
    }
    return I;
}

const Mat I = getI();

void qpow(Mat a, int n) {
    Mat res = I;
    while(n) {
        if(n&1) res = res*a;
        a = a*a;
        n >>= 1;
    }

    for(int i=1;i<=N;i++) {
        int ans = 0;
        for(int j=1;j<=N;j++) {
            ans = (ans + res.m[i][j]*arr[j]) % M;
        }
        printf("%d%c", ans, i==N?'\n':' ');
    }
}

int main() {
    int A, B, C, T;
    while(scanf("%d %d %d %d %d %d", &N, &M, &A, &B, &C, &T)!=EOF && N) {

        for(int i=1;i<=N;i++) {
            scanf("%d", &arr[i]);
        }

        Mat a = {0};
        a.m[1][1] = B, a.m[1][2] = C;
        a.m[N][N-1] = A, a.m[N][N] = B;
        for(int i=2;i<=N-1;i++) {
            a.m[i][i-1] = A;
            a.m[i][i] = B;
            a.m[i][i+1] = C;
        }
        qpow(a, T);
    }
    return 0;
}

 

D Find the Outlier

高斯消元
精度比较坑。。。

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;

double a[8][8], x[8], xx[8];
const double eps = 1e-9;

// double a[MAXN][MAXN],x[MAXN];//方程的左边的矩阵和等式右边的值，求解之后x存的就是结果
int equ, var; //方程数和未知数个数
/*
*返回0表示无解，1表示有解
*/
int Gauss() {
    int k, col, max_r;
    for(k=0,col=0;k<equ&&col<var;k++,col++) {
        max_r = k;
        for(int i=k+1;i<equ;i++) {
            if(fabs(a[i][col])>fabs(a[max_r][col]))
                max_r = i;
        }
        if(fabs(a[max_r][col])<eps) return 0;

        if(k!=max_r) {
            for(int j=col;j<var;j++) {
                swap(a[k][j], a[max_r][j]);
            }
            swap(x[k], x[max_r]);
        }

        x[k] /= a[k][col];
        for(int j=col+1;j<var;j++) {
            a[k][j] /= a[k][col];
        }
        a[k][col] = 1;

        for(int i=0;i<equ;i++) {
            if(i==k) continue;

            x[i] -= x[k]*a[i][col];
            for(int j=col+1;j<var;j++)
                a[i][j] -= a[k][j]*a[i][col];
            a[i][col] = 0;
        }
    }
    return 1;
}

int main() {
    int d;
    while(scanf("%d", &d)!=EOF && d) {
        for(int i=0;i<d+3;i++) {
            scanf("%lf", &xx[i]);
        }

        var = d+1;
        equ = d+1;
        int ans;
        double err = 0.0;
        for(int k=0;k<d+3;k++) {
            int cnt = 0;
            for(int i=0;i<d+3;i++) {
                if(i==k) continue;
                if(cnt>=d+1) break;

                a[cnt][0] = 1;
                for(int j=1;j<d+1;j++) {
                    a[cnt][j] = a[cnt][j-1]*i;
                }
                x[cnt] = xx[i];
                ++cnt;
            }

            /*
            for(int i=0;i<cnt;i++) {
                for(int j=0;j<d+1;j++) {
                    printf("%.2lf ", a[i][j]);
                }
                printf("%.2lf\n", x[i]);
            }
            */

            if(Gauss()==0) continue;

            int pos;
            if(k!=d+2) {
                pos = d+2;
            } else {
                pos = d+1;
            }
            double check = 0.0;
            double p = 1.0;
            for(int i=0;i<d+1;i++) {
                check += p*x[i];
                p = p*pos;
            }
            // printf("%.2lf %.2lf\n", check, xx[pos]);
            if(fabs(check-xx[pos])>0.01) continue;

            check = 0.0, p = 1.0;
            for(int i=0;i<d+1;i++) {
                check += p*x[i];
                p = p*k;
            }
            if(fabs(check-xx[k])>err) {
                ans = k;
                err = fabs(check-xx[k]);
            }
        }
        printf("%d\n", ans);

    }
    return 0;
}

 

F Never Wait for Weights

给定n个人中两人体重的差值信息，询问任意两人体重的差。并查集维护差值。

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 100100;
int fa[maxn];
int w[maxn];

int Find(int x) {
    if(x==fa[x]) return x;

    int root = Find(fa[x]);
    w[x] += w[fa[x]];
    return fa[x] = root;
}

int main() {
    int n, m;
    while(scanf("%d %d", &n, &m)!=EOF && n) {
        for(int i=0;i<=n;i++) {
            fa[i] = i;
            w[i] = 0;
        }

        int x, y, dif;
        while(m--) {
            char op[3];
            scanf("%s", op);
            if(op[0]=='!') {
                scanf("%d %d %d", &x, &y, &dif);
                int a = Find(x);
                int b = Find(y);

                if(a!=b) {
                    fa[b] = a;
                    w[b] = w[x] - w[y] + dif;
                }
            } else {
                scanf("%d %d", &x, &y);
                int a = Find(x);
                int b = Find(y);
                if(a==b)
                    printf("%d\n", w[y]-w[x]);
                else
                    printf("UNKNOWN\n");
            }
        }
    }
    return 0;
}