题意

给出一个11元组A和11元组B，给出n个11元方程，每个方程有一个日期，要让A变成B，问最少需要日期多少才可以变。

思路

因为日期满足单调性，所以可以二分答案。判断的时候就是高斯消元套模板，这个模板是要能对11取模的（因为说了数字在0到10之间）。

#include <bits/stdc++.h>

using namespace std;

const int MOD = 11;

const int MAXN = 1011;

struct Node {

    int num[11];

    int tid;

    bool operator < (const Node &rhs) const {

        return tid < rhs.tid;

    }

} init[MAXN];

int a[12][MAXN];//增广矩阵

int x[MAXN];//最后得到的解集

int s[11], e[11];

inline int gcd(int a,int b) {

    while(b != 0) {

        int t = b;

        b = a%b;

        a = t;

    }

    return a;

}

inline int lcm(int a,int b) {

    return a/gcd(a,b)*b;

}

long long inv(long long a,long long m) {

    if(a == 1)return 1;

    return inv(m%a,m)*(m-m/a)%m;

}

int Gauss(int equ, int var) {

    int max_r,col,k;

    for(k = 0, col = 0; k < equ && col < var; k++,col++) {

        max_r = k;

        for(int i = k+1; i < equ; i++)

            if(abs(a[i][col]) > abs(a[max_r][col]))

                max_r = i;

        if(a[max_r][col] == 0) {

            k--;

            continue;

        }

        if(max_r != k)

            for(int j = col; j < var+1; j++)

                swap(a[k][j],a[max_r][j]);

        for(int i = k+1; i < equ; i++) {

            if(a[i][col] != 0) {

                int LCM = lcm(abs(a[i][col]),abs(a[k][col]));

                int ta = LCM/abs(a[i][col]);

                int tb = LCM/abs(a[k][col]);

                if(a[i][col]*a[k][col] < 0)tb = -tb;

                for(int j = col; j < var+1; j++)

                    a[i][j] = ((a[i][j]*ta - a[k][j]*tb)%MOD + MOD)%MOD;

            }

        }

    }

    for(int i = k; i < equ; i++)

        if(a[i][col] != 0)

            return 0;//无解

    return 1;

}

int check(int m) {

    int equ = 11, var = m + 1; // 行数和列数

    for(int i = 0; i < 11; i++)

        for(int j = 0; j <= m; j++)

            a[i][j] = init[j].num[i];

    for(int i = 0; i < 11; i++)

        a[i][var] = (e[i] - s[i] + MOD) % MOD;

    return Gauss(equ, var);

}

int main() {

    int t; scanf("%d", &t);

    while(t--) {

        int n; scanf("%d", &n);

        for(int i = 0; i < 11; i++) scanf("%d", &s[i]);

        for(int i = 0; i < 11; i++) scanf("%d", &e[i]);

        for(int i = 0; i < n; i++) {

            for(int j = 0; j < 11; j++) scanf("%d", &init[i].num[j]);

            scanf("%d", &init[i].tid);

        }

        sort(init, init + n);

        int l = 0, r = n - 1, ans = -1;

        while(l <= r) {

            int m = (l + r) >> 1;

            if(check(m)) {

                ans = init[m].tid;

                r = m - 1;

            } else {

                l = m + 1;

            }

        }

        if(~ans) printf("%d\n", ans);

        else puts("unreachable");

    } return 0;

}

巴特西

Codeforces Gym101518F：Dimensional Warp Drive（二分+高斯消元）

题意

思路

最新文章

热门文章