【总结】2019.3.23模拟赛

两道数学水题,一道状压DP。T1想麻烦了爆零,T2想简单了TLE,T3不会状压深搜打表没打完

T1

题干

t1-1.PNG

t1-2.PNG

给出一个方程$ax+by=c$,输入$a$ $b$ $c$,求出是否有整数解,并输出$x$非负最小解和$y$非负最小解

程序实现

思路

扩欧求出一组解,然后通过对$a$ $b$取模调成正确答案。我看到负数以为不能取模,然后往下扣往上调,各种特判然后就错了。其实模之前求一下绝对值就行了

代码

爆零版
#pragma GCC optimize(3)
#include <iostream>
#include <fstream>

using namespace std;

int Exgcd(int a, int b, int &x, int &y) {//gcd(a, b) == a * x + b * y
    if (!b) {
        x = 1; 
        y = 0;
        return a;
    }
    int q = Exgcd(b, a % b, y, x);
    y -= a / b * x;
    return q;
}

int main() {
    #ifndef ONLINE_JUDGE
    #define cin FIN
    #define cout FOUT
    ifstream FIN("in.txt"); ofstream FOUT("out.txt");
    #endif
    ios :: sync_with_stdio(false);
    int t, a, b, c, x, y, ans;
    cin >> t;
    while (t--) {
        cin >> a >> b >> c;
        ans = Exgcd(a, b, x, y);
        if (c % ans != 0) {
            cout << "No" << endl;
            continue;
        }
        int tmp = c / ans;
        x *= tmp; y *= tmp;
        if (x >= 0) {
            int k = x / b;
            cout << x - (k * b) << ' ' << y + (k * a);
        } else {
            int k = (-x) / b;
            int tmpx = x + (k * b), tmpy = y - (k * a);
            if (tmpx < 0) tmpx += b, tmpy -= a;
            cout << tmpx << ' ' << tmpy;
        }
        cout << ' ';
        if (y >= 0) {
            int k = y / a;
            cout << x + (k * b) << ' ' << y - (k * a) << endl;
        } else {
            int k = (-y) / a;
            int tmpy = y + (k * a), tmpx = x - (k * b);
            if (tmpy < 0) tmpy += a, tmpx -= b;
            cout << tmpx << ' ' << tmpy << endl;
        }
    }
    return 0;
}
AC代码
#include <iostream>
#include <fstream>

using namespace std;

typedef long long LL;

#define Abs(x) (x < 0 ? -x : x)

LL Exgcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    } else {
        LL x0, y0;
        LL d = Exgcd(b, a % b, x0, y0);
        x = y0;
        y = x0 - (a / b) * y0;
        return d;
    }
}

int main() {
    int t;
    ios :: sync_with_stdio(false); cin.tie(NULL);
//    ifstream fin("in.txt"); ofstream fout("out.txt");
//    #define cin fin
//    #define cout fout
    cin >> t;
    while (t--) {
        LL a, b, c, d, x0, y0, x1, y1, dx, dy;
        cin >> a >> b >> c;
        d = Exgcd(a, b, x0, y0);
        if (c % d) {
            cout << "No" << endl;
        } else {
            x1 = x0 * c / d;
            y1 = y0 * c / d;
            dx = b / d;
            dy = -a / d;
            x1 = (x1 % Abs(dx) + Abs(dx)) % Abs(dx);
            y1 = (c - a * x1) / b;
            cout << x1 << ' ' << y1 << ' ';
            y1 = (y1 % Abs(dy) + Abs(dy)) % Abs(dy);
            x1 = (c - b * y1) / a;
            cout << x1 << ' ' << y1 << endl;
        }
    }
    return 0;
}

T2

题干


20190322171323_31745.jpg

20190322171334_87141.jpg


两个人玩游戏,起初得分都是$a$,每一局有一个系数$k$,输的人分数$*k$,赢的人分数$*k^2$。现在给出两个数,判断是否可能是最后的比分。

程序实现

先看两数之积是否是立方数,然后从两个数当中往出消数。中间写麻烦了,还给立方数打了个表,其实用二分或者是math.h库里的pow函数求立方根就能判立方数了

代码

TLE
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

int64_t cube[2000010];

int gcd(int a, int b) {
    return __gcd(a, b);
}

int T;

void Yes() {
    fwrite("Yes\n", 1, 4, stdout);
}

void No() {
    fwrite("No\n", 1, 3, stdout);
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    cin >> T;
    for (int i = 1; i <= 2000000; i++) {
        cube[i] = i * i * i;
    }
    while (T--) {
        int x, y;
        cin >> x >> y;
        int ret = gcd(x, y);
        x /= ret, y /= ret;
        if (x * y == ret) {
            Yes();
            continue;
        }
        if (ret % x != 0 or ret % y != 0) {
            No();
            continue;
        }
        ret /= x;
        ret /= y;
        for (int i = pow(ret, 1.0 / 3.0) + 1; i>=2; i--) {
            if (ret % cube[i] == 0) {
                ret /= cube[i];
            }
        }
        if (ret == 1) {
            Yes();
        } else {
            No();
        }
    }
    return 0;
}
AC
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

#define gcd(a,b) __gcd(a,b)

int main() {
    ifstream fin("in.txt"); ofstream fout("out.txt");
    #define cin fin
    #define cout fout
    ios :: sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int g = gcd(n, m);
        int x = n / g, y = m / g;
        if (g % (x * y) > 0) {
            cout << "No" << endl;
            continue;
        }
        int ans = g / (x * y);
        double k = pow((double)ans, 1.000000 / 3.000000);
        if ((k >= floor(k) and k - floor(k) < 1e-8) or (k <= ceil(k) and ceil(k) - k < 1e-8)){
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

T3

题干

t3-1.PNG

t3-2.PNG

给出棋盘大小,求出用多米诺骨牌填满棋盘的方案数

程序实现

状压DP,我深搜打表,考完试才打完的。。。状压标程如下

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
#include<stack>
#include<iostream>

#define rep(i, a, b) for(int i = a; i <= b; i++)
#define sz(x) (int)((x).size())
#define ms(x, y) memset(x, y, sizeof(x))
#define pb push_back
#define ll long long
using namespace std;

int r, c;
ll f[13][2050];

bool ok(int x) {
    int z = 0;
    rep(i, 1, c) {
        if (x & 1) {
            if(z & 1)
                return false;
        }
        else
            z ^= 1;
        x >>= 1;
    }
    if (z & 1) return false;
    return true;
}
    
int main() {
    freopen("domino.in","r",stdin);
    freopen("domino.out","w",stdout);
    scanf("%d%d", &r, &c);
    if((r & 1) && (c & 1))
        printf("0\n");
    else {
        ms(f, 0);
        int m = (1 << c) - 1;
        rep(i, 0, m)
            if(ok(i))
                f[1][i] = 1;
        rep(i, 2, r)
            rep(j, 0, m)
                rep(k, 0, m) // 1 in k means vertical dominoes
                    if( (!(j & k)) && ok(j | k)) //0 in j | k means horizontal dominoes
                        f[i][k] += f[i-1][j];
        cout << f[r][0] << endl;
    }
    return 0;
}