0%

**个人题解,和比赛官方无关,仅供参考

2020工大杯题解 - F - L 同学的程序课

题目描述

上完体育课之后,L同学接下来要上程序课。程序课自然离不开写代码,而写代码也离不开修BUG。虽然L同学十分优秀,但是也难逃与BUG斗争的命运。

所幸,L同学在与BUG的长时间较量中,积累了不少的经验。他发现他的程序可能出现的BUG共有N种。对于这些BUG,L同学掌握了K种方法,每种方法可以彻底修复一个AiA_i类BUG,这需要花费T1iT_{1i}的时间。

但对于大部分BUG而言彻底修复是很困难的,在修复的过程中往往会产生一个新的BUG。对此,L同学还掌握了M种方法,每种方法可以修复一个BjB_j类BUG,但同时会产生一个CjC_j类BUG,这需要花费T2jT_{2j}的时间。

现在,为了能尽快的完成程序课作业,L同学希望能够知道使用他目前所掌握的方法,彻底修复一个第x类BUG所需要的最短时间是多少。由于L同学学业繁忙,所以只能由你来帮助他了。

输入

第一行,三个整数N、K、M,分别代表一共有N种BUG(BUG的编号从1到N)、L同学掌握K种能够彻底修复一个BUG的方法,和M种在产生一个新BUG的情况下修复一个BUG的方法。

而后K行,每行两个整数AiA_iT1iT_{1i},代表L同学掌握一种方法能够用T1iT_{1i}的时间彻底修复一个AiA_i类BUG。

而后M行,每行三个整数BjB_jCjC_jT2jT_{2j},代表L同学掌握一种方法能够用T2jT_{2j}的时间将一个BjB_j类BUG修复,但同时会产生一个CjC_j类BUG。

输出

共一行,用空格隔开的N个整数,第x个整数代表使用L同学使用掌握的方法彻底修复一个第x类BUG需要的最短时间。特别地,如果使用现有的方法无法彻底修复第x类的BUG,请在对应位置输出”INF”。

数据规模

对于100%的数据有:

1N1051 \leq N \leq 10^5

0K,M21050 \leq K,M \leq 2*10^5

0K+M21050 \leq K+M \leq 2*10^5

1Ai,Bj,CjN1 \leq A_i,B_j,C_j \leq N

1T1i,T2j1041 \leq T_{1i},T_{2j} \leq 10^4

1i=1KT1i+j=1MT2j1091 \leq \sum_{i=1}^{K}T_{1i}+\sum_{j=1}^{M}T_{2j} \leq 10^9

输入输出样例

Input

5 3 4
1 3
2 9
5 1
1 3 4
4 2 5
1 2 2
2 5 3

Output

3 4 INF 9 1 

题解

题目解法

可以把 bug 视为一个图:有一个虚拟的 0 号节点代表彻底修复的 bug。如果第 ii 个 bug 可以转变为 jj 类 bug ,则由 jj 连接到 ii 一条单向边,权重为所需时间。如果可以彻底修复第ii类 bug,则由 00 连接到 ii 一条单向边,权重为所需时间。然后求 00 号节点到每个节点的最短路即可。

分析时间复杂度:1N1051 \leq N \leq 10^5 0K,M21050 \leq K,M \leq 2*10^5 因此使用堆优化的 dijkstradijkstra (时间复杂度为O(m×log(m))O\left(m \times \log\left(m\right)\right))即可。

AC代码

#include 
#include 
#include 
using namespace std;
#define MAXN 100050
struct road{
    int from;
    int time;
    road(int from, int time): from(from), time(time){}
    bool operator>(const road& that) const {
        return time > that.time;
    }
};
vector roads[MAXN];
int dji[MAXN] = {0x3fffffff};
int vis[MAXN] = {0};
int n,k,m;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k>>m;
    int t,a,b;
    for(int i = 0; i < k; ++ i){
        cin>>a>>b;
        roads[0].emplace_back(a, b);
    }
    for(int i = 0; i < m; ++ i){
        cin>>a>>b>>t;
        roads[b].emplace_back(a, t);
    }

    int count = 0;
    priority_queue, greater > que;
    for(int i = 1; i <= n; ++ i){
        dji[i] = 0x3fffffff;
        vis[i] = 0;
    }
    dji[0] = 0;
    que.emplace(0,0);
    while(!que.empty()){
        int from = que.top().from;
        que.pop();
        if(vis[from]){
            continue;
        }
        vis[from] = 1;
        for(auto &rr: roads[from]){
            if (dji[rr.from] > rr.time + dji[from]){
                dji[rr.from] = rr.time + dji[from];
                que.emplace(rr.from, dji[rr.from]);
            }
        }
        count++;
        if(count == n+1) break;
    }

    for(int i = 1; i <= n; ++ i){
        if(dji[i] < 0x3fffffff){
            cout<

个人题解,和比赛官方无关,仅供参考

2020工大杯题解-G - L 同学的睡眠

题目描述

L同学日理万机,睡眠非常不规律,最早下午7点就会睡觉,最晚早上7点才去睡觉。但规律的睡眠才会使L同学精力充沛,善良的你快关心一下L同学吧!

输入

第一行为空格分隔的3个整数N,D,TN,D,T。在接下来的NN天里,细心的你将记录L同学每天的睡眠时间,从第2天开始,如果在你所记录的过去DD天内(包括当天)L同学最早和最晚睡眠时间差超过了TT分钟,那么善良的你需要对L同学说句“辛苦了!”。

第二行为空格分隔的NN个时间,依次表示1N1\sim N天你所记录L同学的睡眠时间,采用HH:MM格式的24小时制表示。

2N105,2D105,1T7192\le N \le 10^5, 2 \le D \le 10^5, 1 \le T \le 719

输出

输出一个整数表示你一共需要对L同学说多少次“辛苦了!”

样例输入

5 3 30
23:30 1:20 1:07 0:50 19:00

样例输出

3

题解

题目重述

2N105,2D105,1T7192\le N \le 10^5, 2 \le D \le 10^5, 1 \le T \le 719

暴力查询的时间复杂度为 O(D×N)O(D \times N),肯定是不行的。因此,需要一种区间最值查询的数据结构。因此,这是一个 RMQ 问题。

RMQ 是英文 Range Maximum/Minimum Query 的缩写,表示区间最大(最小)值。

可以使用线段树、ST 表、单调栈解决问题。由于线段树和单调栈太简单了,没意思,这里介绍 ST 表。

ST 表是用于解决 可重复贡献问题 的数据结构。

可重复贡献问题 是指对于运算 ,满足 ,则对应的区间询问就是一个可重复贡献问题。例如,最大值有 ,gcd 有 ,所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质,如果求区间和的时候采用的预处理区间重叠了,则会导致重叠部分被计算两次,这是我们所不愿意看到的。另外, 还必须满足结合律才能使用 ST 表求解。

ST 表基于 倍增 思想,可以做到 Θ(nlogn)\Theta(n\log n) 预处理, Θ(1)\Theta(1) 回答每个询问。但是不支持修改操作。

基于倍增思想,我们考虑如何求出区间最大值。可以发现,如果按照一般的倍增流程,每次跳 2i2^i 步的话,询问时的复杂度仍旧是 Θ(logn)\Theta(\log n) ,并没有比线段树更优,反而预处理一步还比线段树慢。

我们发现 max(x,x)=x\max(x,x)=x ,也就是说,区间最大值是一个具有“可重复贡献”性质的问题。即使用来求解的预处理区间有重叠部分,只要这些区间的并是所求的区间,最终计算出的答案就是正确的。

如果手动模拟一下,可以发现我们能使用至多两个预处理过的区间来覆盖询问区间,也就是说询问时的时间复杂度可以被降至 Θ(1)\Theta(1) ,在处理有大量询问的题目时十分有效。

具体实现如下:

f(i,j)f(i,j) 表示区间 [i,i+2j1][i,i+2^j-1] 的最大值。

显然 f(i,0)=aif(i,0)=a_i

根据定义式,第二维就相当于倍增的时候“跳了 2j12^j-1 步”,依据倍增的思路,写出状态转移方程: f(i,j)=max(f(i,j1),f(i+2j1,j1))f(i,j)=\max(f(i,j-1),f(i+2^{j-1},j-1))

img

以上就是预处理部分。而对于查询,可以简单实现如下:

对于每个询问 [l,r][l,r] ,我们把它分成两部分: f[l,l+2s1]f[l,l+2^s-1]f[r2s+1,r]f[r-2^s+1,r]

其中 s=log2(rl+1)s=\left\lfloor\log_2(r-l+1)\right\rfloor

根据上面对于“可重复贡献问题”的论证,由于最大值是“可重复贡献问题”,重叠并不会对区间最大值产生影响。又因为这两个区间完全覆盖了 [l,r][l,r] ,可以保证答案的正确性。

以上内容以 CC BY-SA 4.0 协议和 SATA 协议提供在 OI-WIKI

贡献者:orzAtalod, Henry-ZHR, leoleoasd, Chrogeek, H-J-Granger, ouuan

题目解法

#include 
using namespace std;
const int logn = 17;
const int maxn = 100050;
int fmax[maxn][logn+1], fmin[maxn][logn+1], Logn[maxn];
void pre() {
    Logn[1] = 0;
    Logn[2] = 1;
    for (int i = 3; i < maxn; i++) {
        Logn[i] = Logn[i / 2] + 1;
    }
}
int querymax(int x,int y){
    return max(fmax[x][Logn[y - x + 1]], fmax[y - (1 << Logn[y - x + 1]) + 1][Logn[y - x + 1]]);
}
int querymin(int x,int y){
    return min(fmin[x][Logn[y - x + 1]], fmin[y - (1 << Logn[y - x + 1]) + 1][Logn[y - x + 1]]);
}
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,d,t;
    int a,b;
    int output = 0;
    char _;
    cin>>n>>d>>t;
    for (int i = 1; i <= n; i++){
        cin>>a>>_>>b;
        fmax[i][0] = (a + 5) % 24 * 60 + b;
        fmin[i][0] = (a + 5) % 24 * 60 + b;
    }
    pre();
    for (int j = 1; j <= logn; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++){
            fmax[i][j] = max(fmax[i][j - 1], fmax[i + (1 << (j - 1))][j - 1]);
            fmin[i][j] = min(fmin[i][j - 1], fmin[i + (1 << (j - 1))][j - 1]);
        }

    for (int i = 1; i <= n; ++ i){
        int mm = querymax( max(i - d + 1, 1), i);
        int mi = querymin( max(i - d + 1, 1), i);
        if (mm - mi  > t){
            output++;
        }
    }
    cout<

个人题解,和比赛官方无关,仅供参考

2020工大杯题解 - D - L 同学的又一节体育课

题目描述

迫于忘了选体育课, L同学只能上一个没人选的奇怪的体育课. 在这门课上,
学生被要求玩一个奇怪的游戏, 叫做 “能量传输”. 在这个游戏中, 同学们的目标是组成轨道,
把球从起点传输至筒中, 并保证全程球不能脱轨, 不能把筒撞倒. 全班同学被分成两组, 分别比赛,
之后老师会根据完成小组完成任务的时间的排名来赋予平时分. L同学想要在体育课上内卷,
他想知道需要卷到什么程度. 他偷偷瞄到了另一个组的轨道,
想要问问你另一个组需要多久来完成任务.

一个轨道可以视为一个 8 个长度为 16 的字符串, 如下表示:

-
 \
  \
   -----
        \
         \  --
          -/  \
               V
  • - 表示一个横着摆放的轨道.
  • /\ 分别表示 上升/下降 的斜着摆放的轨道.
  • V 表示目标球桶.
  • 行末最后的空格 可以省略. 如, 上面的字符矩阵中的第一行, 右边省略了15个空格.

为了模拟球的行为, 我们可以认为球有以下属性:

  • 坐标 (x,y)\left(x,y\right). xx表示横坐标,yy表示高度. 1x16,1y81 \leq x \leq 16, 1 \leq y \leq 8
    左下角坐标为(1,1)\left(1,1\right), xx正方向向上, yy正方向向右.
  • 速度 v. 不考虑速度的矢量性.

不同摆放的轨道会对于球的速度有如下影响:

  • -: v -= 3
  • \: v += 10
  • /: v -= 15

在运球过程中, 有以下限制:

  • 任意时刻, 球的速度不能超过40, 否则会冲出轨道外.
  • 任意时刻, 球的速度不能小于或等于0, 否则会停止运动.
  • 落入桶中的时候, 球的速度不能超过15, 不然会把桶撞倒.

我们定义球的一次移动为球的横坐标加一的过程. 在球的一次移动中:

  • 如果当前轨道是 \:
    • 如果下一个轨道是 \: 其高度必须比当前轨道少1.
    • 如果下一个轨道是 /: 其高度必须比当前轨道少1.
    • 如果下一个轨道是 -: 其高度必须比当前轨道少1.
    • 如果下一个轨道是 V: 其高度必须比当前轨道少1.
  • 如果当前轨道是 -:
    • 如果下一个轨道是 \: 其高度必须比当前轨道少1.
    • 如果下一个轨道是 /: 其高度必须和当前轨道相同.
    • 如果下一个轨道是 -: 其高度必须和当前轨道相同.
    • 如果下一个轨道是 V: 无论高度如何, 球会脱轨.
  • 如果当前轨道是 /:
    • 如果下一个轨道是 \: 无论高度如何, 球会脱轨.
    • 如果下一个轨道是 /: 其高度必须比当前轨道多1.
    • 如果下一个轨道是 -: 其高度必须比当前轨道多1.
    • 如果下一个轨道是 V: 无论高度如何, 球会脱轨.

为了简化问题, 我们可以如下进行模拟:

  1. 球的初速度为4.
  2. 如果当前轨道是V: 则已经到达终点. 跳转到第六步.
  3. 把通过当前轨道所需时间 30/v30 / v 累加到总时间中. 做除法后保留整数部分.
  4. 通过轨道后, 根据轨道类型, 更新当前速度, 并判断是否可以进入下一个轨道.
  5. 跳转到第二步.
  6. 输出完成任务所需要的总时间. 如果不能完成任务, 请输出-1.

球的初始坐标为 (1, 8), 保证这一格的轨道为 -. 保证坐标为(16,1)\left(16, 1\right)的地方的轨道为V.

输入数据

8 行, 每行一个长度为 16 的字符串, 表示轨道.

保证每列只有一个不是空格的字符, 且其属于 / \ - V

输出数据

一个整数, 代表和 L 同学竞争的组完成任务所需时间.

如果不能完成任务, 请输出-1.

样例输入

-
 \
  \
   -----
        \
         \  --
          -/  \
               V

样例输出

80

样例解释

通过每一格的速度分别为:

4 1 11 21 18 15 12 9 6 16 26 23 8 5 2

所需时间分别为

7 30 2 1 1 2 2 3 5 1 1 1 3 6 15

题解

题目重述

大模拟题,暴力模拟即可,考察细节。

题目解法

#include 
#include 
using namespace std;

int main(){
    int height[17] = {0};
    int type[17] = {0};
    // -: 0  /: 1 \: 2 v: 3
    int delta_V[4] = {-3,-15,10,0};
    string now;
    for(int i = 0; i < 8; ++ i){
        getline(cin, now);
        int j = 0;
        for(char &c: now){
            switch(c){
                case '-':
                    height[j+1] = 8 - i;
                    type[j+1] = 0;
                    break;
                case '/':
                    height[j+1] = 8 - i;
                    type[j+1] = 1;
                    break;
                case '\\':
                    height[j+1] = 8 - i;
                    type[j+1] = 2;
                    break;
                case 'V':
                    height[j+1] = 8 - i;
                    type[j+1] = 3;
                    break;
                default:
                    break;
            }
            j++;
        }
    }
    int v = 4;
    int x = 1;
    int y = 8;
    int t = 0;
    while(true){
        //cout< 15){
                t = -1;
            }
            break;
        }
        if(v > 40 or v <= 0){
            t = -1;
            break;
        }
        t += (30 / v);
        if(type[x] == 0){
            if(type[x+1] == 0){
                if(height[x+1] != height[x]){
                    t = -1;
                    break;
                }
            }else if(type[x+1] == 1){
                if(height[x+1] != height[x]){
                    t = -1;
                    break;
                }
            }else if(type[x+1] == 2){
                if(height[x+1] != height[x]-1){
                    t = -1;
                    break;
                } else {
                    y -= 1;
                }
            }else if(type[x+1] == 3) {
                t = -1;
                break;
            }
        }else if(type[x] == 1) {
            if(type[x+1] == 0) {
                if(height[x+1] != height[x] + 1){
                    t = -1;
                    break;
                } else {
                    y += 1;
                };
            }else if(type[x+1] == 1) {
                if(height[x+1] != height[x] + 1){
                    t = -1;
                    break;
                } else {
                    y += 1;
                };
            }else if(type[x+1] == 2) {
                t = -1;
                break;
            }else if(type[x+1] == 3){
                t = -1;
                break;
            }
        }else if(type[x] == 2) {
            if(height[x+1] != height[x] - 1){
                t = -1;
                break;
            }
            y -= 1;
        }
        v += delta_V[type[x]];
        x++;
    }
    cout<

个人题解,和比赛官方无关,仅供参考

2020工大杯题解 - C - I 同学的课间

题目描述

午休期间,I 同学最爱做的就是追跑打闹了。

由于 I 同学力气很大,I 同学追跑打闹的时候,每一步都是从学校的一个教学楼跳到另一个教学楼。

但是学校的教学楼太多,为了避免迷路,I 同学决定用一根绳子跟在身后。

然而 I 同学在教学楼之间跳跃的动作会发出巨大声响,每一步都会得罪附近某栋教学楼中的同学们。

为了向 I 同学复仇,这些教学楼中的同学们决定沿着 I 同学跳跃时留下的绳子寻找位置和速度不能同时确定的 I 同学。聪明的 I 同学有时会记得身后刚刚留下的绳子,但是更多时候,聪明的 I 同学会忙着赶路,留下搭在刚刚跳过的两栋教学楼之间的绳子。

然而 I 同学很懒,他不知道向自己复仇的同学们能不能只沿着绳子就找到自己,聪明的你快来帮帮他,让 I 同学知道自己的人身是否安全吧!

输入

第一行为两个整数 N 和 Q,用一个空格分割,分别为学校教学楼的数目和 I 同学跳跃的总次数。1N10000001 \leq N \leq 1000000, 1Q5000001 \leq Q \leq 500000
学校的教学楼编号 11NN,I 同学初始在 11 号教学楼。
接下来的 Q 行,每行为三个整数,其中 X 表示 I 同学跳跃的目标楼号,Y 表示 I 同学完成此次跳跃后得罪的同学所在教学楼的编号,Z 的取值为 0 或 1,0 表示 I 同学忘记切断绳子,1 表示 I 同学切断了绳子。

输出

每次 I 同学跳跃后,输出一行,如果 I 同学很安全,输出 “MHAHAHAHAHAHAHAHA!!!”,否则,如果 I 同学可能会遇到危险,输出 “HEEEEEEELP!!!”。
考虑到输出可能过大,如果 Q > 10,则只输出一个整数,为 “MHAHAHAHAHAHAHAHA!!!” 的个数,其余不进行输出。

样例输入和输出

Input

100 10
2 1 0
3 4 1
4 5 1
6 5 0
7 5 1
8 5 0
9 5 0
10 8 0
11 7 1
6 9 1

Output

HEEEEEEELP!!!!!!!!!!!
MHAHAHAHAHAHAHAHA!!!
HEEEEEEELP!!!!!!!!!!!
HEEEEEEELP!!!!!!!!!!!
MHAHAHAHAHAHAHAHA!!!
MHAHAHAHAHAHAHAHA!!!
MHAHAHAHAHAHAHAHA!!!
HEEEEEEELP!!!!!!!!!!!
MHAHAHAHAHAHAHAHA!!!
HEEEEEEELP!!!!!!!!!!!

提示

I 同学很聪明,如果两栋楼之间已经有绳子了,I 同学就不会自寻死路了

题解

题目重述

有 n 个教学楼, I (大写 i)同学从 1 号楼出发,每次跳跃到一个教学楼。有一定可能把两个教学楼用绳子连接起来。

每跳到一个教学楼会得罪附近的一些人。附近的人可以沿着绳子自由移动。于是,我们可以把绳子连接起来的几栋教学楼视为一个整体。只要跳到了一个包括得罪的人的教学楼组中,就凉凉了。

题目解法

复杂度分析:首先,一遍更新一遍查询,应使用在线算法。

其次,查询、更新次数为500000500000,并查集时间复杂度为O(α(n))O\left(\alpha \left(n\right)\right), 可以接受。

于是用并查集。每链接一条绳子,就把两个教学楼所在集合合并到一起。每次得罪某栋楼的人,就把他所在的集合标记为已得罪。如果每次跳跃结束后,当前集合为已得罪,就凉了。反之,就稳了。

伪代码

初始化并查集
读入数据
对于每组数据:
	如果没切断绳子: 合并(当前所在,上一次所在)
	标记得罪了的集合
	输出状态或者保存 MAAAA 的次数

AC 代码

#include 
using std::cin;
using std::cout;
using std::ios;
#define MH "MHAHAHAHAHAHAHAHA!!!"
#define HELP "HEEEEEEELP!!!!!!!!!!!"
#define endl '\n'
#define MAXN 1000001
// 并查集
int father[MAXN] = {0};
int size[MAXN] = {0};

int annoyed[MAXN] = {0}; // 是否惹了

int find(int i){
    if(father[i] == i) return i;
    return father[i] = find(father[i]);
}

void uni(int a,int b){
    int fa = find(a);
    int fb = find(b);
    if (size[fa] < size[fb]) {
        return uni(b,a);
    }
    size[fa] += size[fb];
    size[fb] = 0;
    father[fb] = fa;
    annoyed[fa] += annoyed[fb];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    for(int i = 1; i <= n; ++ i){
        father[i] = i;
        size[i] = 1;
    }
    int nowpos = 1;
    int to, annoying, cut;
    int help = 0;
    int ma_sum = 0;
    for(int _ = 0; _ < q; ++ _){
        cin>>to>>annoying>>cut;
        help = 0;
        if(!cut){
            uni(nowpos, to);
        }
        nowpos = to;
        annoyed[find(annoying)] = 1;
        int nn = find(nowpos);
        help = annoyed[nn];
        if(q <= 10){
            cout<<(help?HELP:MH)< 10){
        cout<

编程中极值的选取

很多时候,在编程中我们都需要把一些变量初始化为极大、极小值。下面是对于一些常见极值的比较。

TL; DR:

比较时用 0x7fffffff, 需要参与运算(如 a = max(a+b, c) )时, 用 0x3fffffff0x3f3f3f3f

不用数了, 7 个 f。

如果是 long long, 用 0x7fffffffffffffffLL0x3f3f3f3f3f3f3f3fLL0x3fffffffffffffffLL

15 个 f。

10000000

此类极值无疑是最简单的一种, 随手写即可。初学阶段可以使用,但是后期就会产生风险。

首先,如果手欠多写了几个 0, 会发生什么呢?

可以运行一下代码测试一下:

printf("%d", 10000000000);
// Outputs 1410065408

这是为什么呢? 注意, 在 C 语言中, 字面量也是有类型的。 1000000000010000000000的类型是 int,但是他超过了 int 所能表示的最大值 21474836472147483647,所以溢出为了 14100654081410065408

其次,如果少写了几个 0,会发生什么呢?

”极大值“选取的不够大,程序就会算出错误的结果。

所以, 不建议这样选取极大值。

0x7fffffff

当需要进行比较类型的运算时,(如保存最小值的变量要用一个极大值初始化),可以初始化为0x7fffffff

原因:

  1. 他是 int 类型变量的最大值,绝大部分情境下足够大。
  2. 比 10 进制下 int 变量最大值(2147483647)\left(2147483647\right)更好记忆。 (7 后 7 个 f)

缺点:

因为它是 int 最大值,加上 1 都会溢出为负数。所以仅能在不需要进行算数运算,仅需要进行比较时使用。

0x3fffffff / 0x3f3f3f3f

需要极值参与的运算大部分情况下都是这样的:

a = max(a+b, c);
// a 和 b 可能是极大值

这种情况下,仅需要保证 a+ba+b 的过程不溢出,既保证aINT_MAX/2a \leq INT\_MAX / 2 即可。所以,a 可以初始化为0x3fffffff。(一样还是 7 个 f)

同样,在图论题中,我们经常需要把一整个二维数组赋值为极值。这种情况下,0x3fffffff不能使用memset进行一次性赋值。因此,采用略小一些的 0x3f3f3f3f 就可以一次性用memset赋值:

int data[MAXN][MAXM];
memset(data, 0x3f, sizeof data);

还记得吗? memset 函数是对于给定大小数组的每个字节赋值为指定的值。

个人题解,和比赛官方无关,仅供参考

2020工大杯题解 - B - Classmate L’s PE course.

题目描述

Classmate L forgot to elect his course, so he had to take a strange PE course. On this strange course, students will play a weird game: each male student represent aa, and each female students represent bb. When a teacher says a non-zero positive integer number of cc, xx male students and yy female students need to gather together and keep .

Classmate L is bad at math, he wants to know how many people he will be gathering together with.

Lots of students forgot to elect courses too, so we can assume that there is an infinite number of male and female students.

输入数据

One line containing three non-zero positive integer nn, aa, bb. (0n100,2a,b104)\left(0 \leq n \leq 100, 2 \leq a,b \leq 10^4 \right).

Meaning of aa and bb are described above. nn means there will be nn queries.

For the next nn line, each line contains a non-zero positive integer cc. (0c106)\left( 0 \leq c \leq 10^6 \right)

输出数据

For each query, output the number of male students and the number of
female students separated by a space.

If it’s not possible form cc, output ARE YOU KIDDING ME?.

If there are multiple answers, output the answer as the greatest
number of male students
.

样例输入

2 2 3
1
100

样例输出

ARE YOU KIDDING ME?
49 0

题目大意

每个男生代表 aa,每个女生代表bb。每次询问一个数cc,问你 L 同学需和要哪些人一起才能凑出来cc。输出男生人数最大的方案。

相当于是求以下方程中 x,yx, y 的正整数解,同时要求x1x \ge 1, 输出x1,yx-1, y

ax+by=cax + by = c

思路

读入 a,b,na, b, n。 每次查询读入 cc , 起手直接 c=cac = c - a 。然后就是解方程。

进行时间复杂度分析:0c1060 \leq c \leq 10^6, 直接暴力即可。

伪代码

读入a,b,n
循环 n 次:
	读入 c
	c = c - a
	枚举男生人数: 从(c/a) 到 0:
		算女生人数是否是整数, 是就输出
	如果失败, 输出ARE YOU KIDDING ME?

代码

#include 
using namespace std;
int main(){
    int n,a,b,c;
    cin>>n>>a>>b;
    while(n--){
        cin>>c;
        int x = 0;
        int y = 0;
        c -= a;
        for(x = c / a; x >= 0; x --){
            if ((c - a * x) % b == 0){
                y = (c - a * x) / b;
                break;
            }
        }
        if (x == -1) {
            cout<<"ARE YOU KIDDING ME?"<