Description:

小埃和小森在玩一个数字游戏,小埃先从区间[L1, R1]里选择1个数字n1,小森看到小埃选的数字后,从[L2,R2]里选择1个数字n2, 将n1和n2连接在一起(n1在前, n2在后),形成一个新的数字,若这个数字可以被mod整除,那么小森获胜,否则小埃获胜。若两个人均采取最优策略,试问谁获胜?

Input:

输入测试组数T,每组数据,输入一行整数L1, R1, L2, R2, mod,其中$1<=L1<=R1<10^{9} ,1<=L2<=R2<10^{9} , 1<=mod<=10^{6}$

Output:

每组数据输出一行,若小埃获胜,输出WIN,否则输出LOSE

Sample Input:

2
6 9 3 5 1
5 10 7 8 6

Sample Output:

LOSE
WIN

题目链接

这道题目我看到别人的代码直接比较第二段区间长度和mod的大小关系判断输赢,代码如下:

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5+5;
const double eps = 1e-5;
const double e = 2.718281828459;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        ll l1, r1, l2, r2, mod;
        cin >> l1 >> r1 >> l2 >> r2 >> mod;
        if (r2 - l2 + 1 < mod) {
            cout << "WIN" << endl;
        }
        else {
            cout << "LOSE" << endl;
        }
    }
    return 0;
}

这是错误的算法,但是由于数据水也可以过。反例如:1 1 8 8 9。
题目的正确思路:先判断第二段区间长度和mod的大小关系,若第二段区间长度大于等于mod则小埃必输(因为无论小埃选择哪个数第二段区间总有一个数%mod+小埃选择的数%mod==0)。
枚举计算第一段区间内%mod的值并记录(用set记录去重比较方便)。
枚举第二段区间,分位数长度记录%mod的值(这里用一个set数组记录),然后就可以枚举 n1 的余数, 枚举 n2 每个长度的余数来判断输赢。若对每个n1的余数总有一个n2(任何长度)的余数使两数之和%mod==0则输出LOSE,否则输出WIN。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+5;
const double eps = 1e-5;
const double e = 2.718281828459;

int t;
int l1, r1, l2, r2, mod;
set<int> rem;
bool len_vis[10];
bool rem_flag[maxn][2];
bool ans_flag;
set<int> len_rem[10];

int Cal_num_len(int x) {
    int cnt = 0;
    while (x) {
        x /= 10;
        cnt++;
    }
    cnt = cnt == 0 ? 1 : cnt;
    return cnt;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--) {
        mem(len_vis, 0);
        mem(rem_flag, 0);
        cin >> l1 >> r1 >> l2 >> r2 >> mod;
        if (r2 - l2 + 1 >= mod) {
            cout << "LOSE" << endl;
            continue;
        }
        for (int i = l1; i <= r1; ++i) {
            rem.insert(i % mod);
            rem_flag[i % mod][0] = 1;
        }
        for (int i = l2; i <= r2; ++i) {
            int num_len_temp = Cal_num_len(i);
            len_vis[num_len_temp] = 1;
            len_rem[num_len_temp].insert(i % mod);
        }
        for (set<int>::iterator rem_it = rem.begin(); rem_it != rem.end(); ++rem_it) {
            for (int j = 0; j < 10; ++j) {
                if (len_vis[j]) {
                    for (set<int>::iterator len_rem_it = len_rem[j].begin(); len_rem_it != len_rem[j].end(); ++len_rem_it) {
                        if ((*rem_it + *len_rem_it) % mod == 0) {
                            rem_flag[*rem_it][1] = 1;
                        }
                    }
                }
            }
        }
        ans_flag = 1;
        for (int i = 0; i <= mod; ++i) {
            if (rem_flag[i][0]) {
                if (!rem_flag[i][1]) {
                    ans_flag = 0;
                    break;
                }
            }
        }
        if (ans_flag) {
            cout << "LOSE";
        }
        else {
            cout << "WIN";
        }
        cout << endl;
        rem.clear();
        for (int i = 0; i < 10; ++i) {
            len_rem[i].clear();
        }
    }
    return 0;
}
Last modification:March 29th, 2019 at 04:51 pm
如果觉得我的文章对你有用,请随意赞赏