题目设置：一共5道题，只有10%~30%的样例。
考试时间：9:30~11:30，共2h。

1 题目A：整数化

1.1 题目描述

小Z在处理二维坐标点上的数据，受到性能限制，他希望把所有的点对应到距离它最近的整数点（横纵坐标均为整数）上，请你帮他完成这个程序。

如果一个点有多个距离它最近的点，取横纵坐标更小的那个点。如（1, 1.5）将对应到（1, 1）,（-1, -1.5）将对应到（-1, -2）。

1.2 输入

多组样例输入，第一-行输入一个整数T表示样例数。

对于每个样例，包含两个数表示需要整型化的点。

1.3 输出

对于每组样例，输出一行包含两个整数的坐标，用空格分割。

1.4 样例输入

3
1 1.5
2 3.2
-1 -2

1.5 样例输出

1 1
2 3
-1 -2

1.6 解题思路

一开始直接使用了取整int()，但是当输入为负数的时候，例如-1.6取整为-1，但是题意要求是-2，所以应该判断一下小数部分和0.5的关系，分类讨论。

最终这个对于部分数据AC了，但是不知道剩下的数据怎么样。

#include <iostream>
using namespace std;

int get(double x)
{
    double rest = x - (int)x;
    if (abs(rest) < 0.5) return (int)x;
    if (abs(rest) == 0.5)
    {
        if (x > 0) return (int)x;
        return (int)x + -1;
    }
    return (int)x + (x > 0 ? 1 : -1);
}

int main()
{
    int t; cin >> t;
    for (int i = 1; i <= t; i ++)
    {  
        double x, y; cin >> x >> y;
        cout << get(x) << " " << get(y);
        if (i < t) cout << endl;
    }
    return 0;
}

2 题目B：多项评价指标

2.1 题目描述

Dice系数和IoU均为衡量两个集合相似度的重要度量，是图像分割领域的最常用的评价指标，小Z希望写一个程序完成两个指标的转化。

Dice系数计算方式：

$$
Dice =\frac{T P}{T P+F P+F N}
$$

IoU计算公式：

$$
I o U=\frac{T P+T P}{T P+T P+F P+F N}
$$

二者转化公式：

$$
Dice =\frac{2 \times I o U}{I o U+1}
$$

2.2 输入

多组样例输入，第一行输入一个整数T表示样例数。

对于每个样例，输入一行，包括度量名称及度量值，中间用空格隔开，其中指标名称只能为”dice”或”iou”，例如”dice 0.45”, “iou 0.80”。

输入的IoU和Dice均在[0, 1]范围内。

2.3 输出

对于每组样例，输出一个数字表示转化为另一种度量的结果，输出四舍五入保留两位小数。

2.4 样例输入

3
dice 0.4
iou 0.8
dice 0.9

2.5 样例输出

0.25
0.89
0.82

2.6 解题思路

这题不需要使用任何算法，根据题目给出的公式直接计算即可，需要转换得到IoU的计算公式，如下：

$$
IoU =\frac{Dice }{2-Dice }
$$

#include <iostream>
using namespace std;

void work()
{
    string type;
    double val; cin >> type >> val;
    if (type == "dice")
    {
        double IoU = val / (2 - val);
        printf("%.2lf", IoU);
    }
    else
    {
        double Dice = 2 * val / (val + 1);
        printf("%.2lf", Dice);
    }
}

int main()
{
    int t; cin >> t;
    for (int i = 1; i <= t; i ++)
    {
        work();
        if (i < t) cout << endl;
    }
    return 0;
}

3 题目C：跳着数数

3.1 题目描述

小Z不喜欢0~9中较大的数字，他想知道如果去掉所有包含大数字的数之后[1, n]区间内，还剩多少个数。

例如，小Z不喜欢三个7，8，9数字，将所有任意位存在这三个数字的数去掉后，[1, 12]中只剩下了[1, 2, 3, 4, 5, 6,10, 11, 12]这9个数。

注意，9, 19, 190都包含9数字9，在计数时都需要删去。

3.2 输入

多组样例输入，第一行输入一个整数T表示样例数。

对于每个样例，包含两个数字n k，n表示需要在[1, n]内进行统计，k表示小Z不喜欢的数字为[k, 9]。

其中$n \leq 10^{18}$，$1 \leq k \leq 9$。

3.3 输出

对于每组样例，输出一个数字表示删除不喜欢的数后剩余数字的数量。

3.4 样例输入

2
12 7
100 5

3.5 样例输出

9
25

3.6 解题思路

看到n的范围比较大，所以要先用long long存储，然后如果直接枚举，肯定会超时，这里可以首先分析n是几位数，如果是之前的话可能要写一个函数判断，但是之前学了一个技巧，先将其转化字符串，然后判断这个字符串的长度，就是n的位数，记为num。

然后分析$ 1 \sim num - 1$位数中有多少个数满足要求：由于$[k, 9]$之间的数字不能出现，因此每一位只有$[0,k-1]$个选法，注意最高位不能为0，所以最高位只有k-1中选法，其他有k中选法，这也就是get函数的作用。

当判断num位数中，有多少个是小于n的（写到这里的时候突然发现考试虽然过了部分数据，但是这里应该是不对的），比如n是22，k为9，此时可以取18，但是下面的写法是没有计算18的，所以错误。

#include <iostream>
#include <string>
#include <math.h>
using namespace std;

typedef long long LL;
LL n; 
int k;

LL get(int num)
{
    // num位数
    // 最高位 k - 1 个选择 其他位置上的数都有 k 个选择
    return (k - 1) * pow(k, num - 1);
}

LL calu()
{
    // 此时位数与n相同
    // 从最高位开始判断 每次只能从n的当前这位的数a和k-1的较小值中选择
    string num = to_string(n);
    LL res = min(num[0] - '0', k - 1);
    for (int i = 1; i < num.size(); i++)
    {
        int t = min(num[i] - '0' + 1, k);
        res *= t;
    }
    return res;
}

void work()
{
    cin >> n >> k;
    // 判断每一个位置有多少个可以选
    LL ans = 0;
  
    // 先得到n是几位数
    int num = to_string(n).size();
  
    for (int i = 1; i < num; i++)
    {
        // 判断i位数有多少个数可以选
        ans += get(i);
    }
  
    // 单独处理num位数的情况
    ans += calu();
    cout << ans;
}

int main()
{
    int t; cin >> t;
    for (int i = 1; i <= t; i ++)
    {
        work();
        if (i < t) cout << endl;
    }
    return 0;
}

下面的做法是正确的：

LL calu()
{
    // 此时位数与n相同
    // 从最高位开始判断 每次只能从n的当前这位的数a和k-1的较小值中选择
    string num = to_string(n);
    int cnt = num.size();
    LL res = 0;
    
    if (num[0] > '1') res += (min(num[0] - '0' - 1, k - 1) - 1) + pow(k, cnt - 1);
    for (int i = 1; i < num.size(); i++)
        if (num[i] >= '1')
            res += (min(num[0] - '0', k) - 1) + pow(k, cnt - i - 1);
    res ++;
    return res;
}

4 题目D：掩码匹配

4.1 题目描述

数字在计算机中是以二进制存储的，小Z在监控程序运行状态。他想知道给定一个掩码，一段内存中有多少个数可以匹配该掩码。

匹配定义：待匹配数为a，掩码为b，若b的二进制表示中所有的1，在a的二进制表示的相对应位置也为1，则称a可以匹配掩码b。

例如，1为掩码，其二进制表示为”1”，则1(1)，3(11)，5(101)，7(111)，……均可匹配该掩码，括号内为该数字对应二进制表示。

又例如，13的二进制为”1101”，如果掩码为12，12的二进制为”1100”,掩码12可以匹配数字13。同时该掩码也可以匹配数字15(1111)。

为了简化问题，小Z所有的掩码保证二进制下1的个数不超过2个。

4.2 输入

第一行包含一个整数n，表示观测的内存长度，编号从1到n。

第二行包含n个整数表示内存中存储的数。

第三行包含一个整数q表示询问数量。

接下来q行每行包含三个整数s t m，表示从位置s到位置t，掩码为m。

数据范围：

$1 \leq n \leq 20000$
$1 \leq q \leq 100000$
$m > 0$且保证二进制下至多两位为1
内存中储存的数字范围为$[1, 10^8]$

4.3 输出

对于每次询问，输出一个整数表示从到s到t（包含起点和终点），可有多少数字可以匹配掩码m。

4.4 样例输入

8
1 2 3 4 5 6 7 8
3
1 8 3
1 8 1
3 8 6

4.5 样例输出

2
4
2

对于询问1，区间[1, 8]内3和7可以匹配掩码3。

对于询问2，区间[1, 8]内[1, 3, 5, 7]可以匹配掩码1。

对于询问3，区间[3, 8]内6和7可以匹配掩码6。

4.6 解题思路

当时做的时候直接使用的暴力，样例可以通过，但是剩下的测试数据中肯定会超时，所以最后又想了一个优化，但是没有时间了。

可以将输入的数据进行预处理，类似桶排序的思想，预处理出来一个数的二进制中哪些位为1，然后将这些数保存在对应的桶中，之后直接查询即可。

#include <iostream>
#include <string>
#include <math.h>
using namespace std;

const int N = 20010;
int mem[N];

int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> mem[i];
  
    int q; cin >> q;
    while (q--)
    {
        int st, ed, m; cin >> st >> ed >> m;
    
        int ans = 0;
        for (int i = st; i <= ed; i++)
            if ((mem[i] & m) == m) ans++;
        cout << ans << endl;
    }
  
    return 0;
}

5 题目E：更短的最短路

5.1 题目描述

小Z在处理一个特殊的最短路径问题，在无向图中有部分边在最初始时是上锁没法通过的，当他拿到位于节点k的钥匙后，这些边就可以通过了。

通过一条边的花费为边权值，他想知道从节点1走到节点n的最小花费是多少。

5.2 输入

多组样例输入，第一行输入一个整数T表示样例数。

对于每个样例，第一行包含两个整数n，m，k，图一共n个节点m条边，节点编号从
到1到n，钥匙在节点k。

接下来行每行包含四个整数，s t w v表示有一条从s到t的边，权重为w，如果v为0则表示不需要钥匙就可以通行，如果是1则表示该边需要拿到钥匙后才能通行。

5.3 输出

对于每组样例，输出一个整数表示从1到n的最短路，如果不能到达，则输出-1。

5.4 样例输入

2
3 3 1
1 2 1 0
2 3 1 0
1 3 5 0
4 4 3
1 3 1 0
1 2 1 0
2 4 1 1
3 4 100 0

5.5 样例输出

2
4

5.6 解题思路

需要思考的问题是这个与以往的最短路问题有什么不同？有一个钥匙的限制。

先判断是否可以只走不需要钥匙的边到达终点

可以：需要先计算获得钥匙，然后再从钥匙所在点走到终点的代价的最小值
不可以：需要先计算获得钥匙，然后再从钥匙所在点走到终点的代价

综上：最小代价就是不需要钥匙和需要钥匙的最小代价。

#include <iostream>
#include <cstring>
#include <utility>
using namespace std;

typedef long long LL;

const int N = 1005;
int n, m, k;
int dist[N];
bool st[N];
pair<int, int> g[N][N];

LL dijkstra(int source, bool key)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    dist[source] = 0;
    for (int i = 1; i <= n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
        st[t] = true;
  
      for (int j = 1; j <= n; j++)
          if (key || (!key && g[t][j].second == 0))
              dist[j] = min(dist[j], dist[t] + g[t][j].first);
    }
    return dist[n] > 0x3f3f3f3f / 2 ? -1 : dist[n];
}

void work()
{
    memset(g, 0x3f, sizeof g);
    cin >> n >> m >> k;
    while (m--)
    {
        int s, t, w, v; cin >> s >> t >> w >> v;
        g[s][t] = { w, v }, g[t][s] = { w, v };
    }
  
    LL ans1 = dijkstra(1, false);
    if (ans1 == -1)
    {
        // 没有钥匙不能到达
        // 不能拿到钥匙
        if (dist[k] > 0x3f3f3f3f / 2) cout << -1 << endl;
        else
        {
            int dist_k = dist[k];
            // 能拿到钥匙
            LL ans2 = dijkstra(k, true);
            if (ans2 == -1)
            {
                // 拿到钥匙也不能到达
                cout << -1 << endl;
            }
            else cout << dist_k + ans2 << endl;
        }
      }
      else
      {
          // 需要看一下拿到钥匙是否能有更近的路径
          int dist_k = dist[k];
          LL ans2 = dijkstra(k, true);
          cout << min(ans1, dist_k + ans2) << endl;
      }
}

int main()
{
    int t; cin >> t;
    while (t--)
        work();
  
    return 0;
}