埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 D 数字游戏

Description:

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

Input:

输入测试组数T，每组数据，输入一行整数L1, R1, L2, R2, mod,其中 $1 < = L 1 < = R 1 < 1 0^{9}, 1 < = L 2 < = R 2 < 1 0^{9}, 1 < = m o d < = 1 0^{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;
}