11D_Beyonder's Blog

传送门 ↬\looparrowright↬ 题目描述 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于 300003000030000 的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 输入描述 111 行，若干个整数（个数 ≤100000≤100000≤100000）。 输出描述 222 行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 示例1 输入 389 207 155 300 299 170 158 65 输出 6 2 分析 首先明确，当且仅当一颗炮弹的高度和导弹相等时，导弹可被拦截。 设第 iii 颗导弹的高度为 h[i]h[i]h[i]。 由题意，能够用一套拦截的导弹，其高度构成 ...

传送门 ↬\looparrowright↬ 题目描述 棋盘上 AAA 点有一个过河卒，需要走到目标 BBB 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 CCC 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示，AAA 点 (0,0)(0, 0)(0,0)、BBB 点 (n,m)(n, m)(n,m)，同样马的位置坐标是需要给出的。 现在要求你计算出卒从 AAA 点能够到达 BBB 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。 输入格式 一行四个正整数，分别表示 BBB 点坐标和马的坐标。 输出格式 一个整数，表示所有的路径条数。 输入输出样例 输入 #1 6 6 3 3 输出 #1 6 说明/提示 对于 100%100 \%100% 的数据，1≤n,m≤201 \le n, m \le 201≤n,m≤20，0≤马的坐标≤200≤ 马的坐标 \le 200≤马的坐标≤20。 分析 设 dp[i][j]dp[i][j]dp[i][j] 为从 (0,0)(0,0)(0,0) 走到点 (i,j) ...

传送门 ↬\looparrowright↬ 题目描述 NNN 位同学站成一排，音乐老师要请其中的 (N−K)(N-K)(N−K) 位同学出列，使得剩下的 KKK 位同学排成合唱队形。 合唱队形是指这样的一种队形：设 KKK 位同学从左到右依次编号为 1,2,…,K1,2,…,K1,2,…,K，他们的身高分别为 T1,T2,…,TKT_1,T_2,…,T_KT1​,T2​,…,TK​， 则他们的身高满足 $T_1…>T_K(1 \le i \le K)$。 你的任务是，已知所有 NNN 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 输入格式 共二行。 第一行是一个整数 N(2≤N≤100)N(2 \le N \le 100)N(2≤N≤100)，表示同学的总数。 第二行有 nnn 个整数，用空格分隔，第 iii 个整数 Ti(130≤Ti≤230)T_i(130 \le T_i \le 230)Ti​(130≤Ti​≤230) 是第 iii 位同学的身高(厘米)。 输出格式 一个整数，最少需要几位同学出列。 输入输出样例 输入 #1 8 186 186 1 ...

A. Matrix Game Ashish and Vivek play a game on a matrix consisting of nnn rows and mmm columns, where they take turns claiming cells. Unclaimed cells are represented by 000, while claimed cells are represented by 111. The initial state of the matrix is given. There can be some claimed cells in the initial state. In each turn, a player must claim a cell. A cell may be claimed if it is unclaimed and does not share a row or column with any other already claimed cells. When a player is unable to m ...

传送门 ↬\looparrowright↬ 题目描述 动物王国中有三类动物 A,B,CA,B,CA,B,C，这三类动物的食物链构成了有趣的环形。AAA 吃 BBB，BBB 吃 CCC，CCC 吃 AAA。 现有 NNN 个动物，以 111 −-− NNN 编号。每个动物都是 A,B,CA,B,CA,B,C 中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这 NNN 个动物所构成的食物链关系进行描述： 第一种说法是 1 X Y1\ X\ Y1 X Y，表示 XXX 和 YYY 是同类。 第二种说法是 2 X Y2\ X\ Y2 X Y，表示 XXX 吃 YYY 。 此人对 NNN 个动物，用上述两种说法，一句接一句地说出 KKK 句话，这 KKK 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。 当前的话与前面的某些真的话冲突，就是假话。 当前的话中 XXX 或 YYY 比 NNN 大，就是假话。 当前的话表示 XXX 吃 XXX，就是假话。 你的任务是根据给定的 NNN 和 KKK 句话，输出假话的总数。 输入格式 第一行两个整数， ...

传送门 ↬\looparrowright↬ 题目描述 有 nnn 位同学，每位同学都参加了全部的 mmm 门课程的期末考试，都在焦急的等待成绩的公布。 第 iii 位同学希望在第 tit_iti​ 天或之前得知所有课程的成绩。如果在第 tit_iti​ 天，有至少一门课程的成绩没有公布，他就会等待最后公布成绩的课程公布成绩，每等待一天就会产生 CCC 不愉快度。 对于第 iii 门课程，按照原本的计划，会在第 bib_ibi​ 天公布成绩。 有如下两种操作可以调整公布成绩的时间: ① 将负责课程 XXX 的部分老师调整到课程 YYY，调整之后公布课程 XXX 成绩的时间推迟一天，公布课程 YYY 成绩的时间提前一天；每次操作产生 AAA 不愉快度。 ② 增加一部分老师负责学科 ZZZ，这将导致学科 ZZZ 的出成绩时间提前一天；每次操作产生 BBB 不愉快度。 上面两种操作中的参数 X,Y,ZX, Y, ZX,Y,Z 均可任意指定，每种操作均可以执行多次，每次执行时都可以重新指定参数。 现在希望你通过合理的操作，使得最后总的不愉快度之和最小，输出最小的不愉快度之和即可。 输入格式 ...

01分数规划基本问题 给出两个有 nnn 个元素的数组 aia_iai​ 和 bib_ibi​，对于一组 $w_i\in \{0,1\}$，可能使得 $\Large{\frac{\sum\limits_{i=1}^n a_iw_i}{\sum\limits_{i=1}^n b_iw_i}}$ 取得最值，求这个最值。 求解——二分法 check函数 我们二分答案。假设要求的是最大值。 二分得到一个答案 xxx，假设当前 xxx 小于最大值或者正好去到最大值，那么有 ∑i=1naiwi∑i=1nbiwi⩾x\frac{\sum\limits_{i=1}^n a_iw_i}{\sum\limits_{i=1}^n b_iw_i}\geqslant xi=1∑n​bi​wi​i=1∑n​ai​wi​​⩾x，即 ∑i=1nwi(ai−xbi)⩾0\sum\limits_{i=1}^n w_i\left(a_i-xb_i\right)\geqslant 0i=1∑n​wi​(ai​−xbi​)⩾0 。如果经过检验，不存在∑i=1nwi(ai−xbi)⩾0\sum\limits_{i=1}^n w_ ...

传送门 ↬\looparrowright↬ 题目描述 小阳手中一共有 nnn 个贝壳，每个贝壳都有颜色，且初始第 iii 个贝壳的颜色为 colicol_icoli​。 现在小阳有 333 种操作。 1 l r x\text{1 l r x}1 l r x：给 [l，r][l，r][l，r] 区间里所有贝壳的颜色值加上 xxx。 2 l r\text{2 l r}2 l r：询问[l，r][l，r][l，r] 区间里所有相邻贝壳颜色值的差（取绝对值） 的最大值（若 l=rl=rl=r 输出 000）。 3 l r\text{3 l r}3 l r：询问 [l，r][l，r][l，r] 区间里所有贝壳颜色值的最大公约数。 输入描述 第一行输入两个正整数 n,mn,mn,m，分别表示贝壳个数和操作个数。 第二行输入 nnn 个数 colicol_icoli​，表示每个贝壳的初始颜色。 第三到第 m+2m + 2m+2 行，每行第一个数为 optoptopt，表示操作编号。接下来的输入的变量与操作编号对应。 输出描述 共 mmm 行，对于每个询问（操作 222 和操作 333）输出对应 ...

视频演示 自制简易画图软件演示（BV1nk4y1r72y），包含铅笔、直线、矩形、椭圆、橡皮等功能。 开发环境 开发工具为 Visual Studio 2019\text{Visual Studio 2019}Visual Studio 2019。画图软件基于 MFC\text{MFC}MFC 类库进行设计。 自定义类介绍 CMyButton CMyButton\text{CMyButton}CMyButton 是 CDC\text{CDC}CDC 的派生类，继承 CDC\text{CDC}CDC 的目的是创建位图。一个 CMyButton\text{CMyButton}CMyButton 的对象只对应一个按钮，按钮有铅笔、直线等。 位图与编号 每一个按钮都有其索引。每个按钮都有一个位图，位图所覆盖的区域在内存中有其对应的颜色作为按钮的映射。 程序启动时，根据编号加载对应的位图资源。 映射 当鼠标左键点击按钮后，可以得到光标所在坐标的颜色，因此可以用按钮所在方形区域的颜色作为按钮的映射，即一种颜色对应一个按钮。 我们在按钮区域填充对应颜色即可构建映射。 12345void CMyBut ...

传送门 ↬\looparrowright↬ 题目描述 今天 qwb\text{qwb}qwb 要参加一个数学考试，这套试卷一共有 nnn 道题，每道题 qwb\text{qwb}qwb 能获得的分数为 aia_iai​，qwb\text{qwb}qwb 并不打算把这些题全做完，他想选总共 2k2k2k 道题来做，并且期望他能获得的分数尽可能的大，他准备选 222 个不连续的长度为 kkk 的区间，即 [L,L+1,L+2,....,L+k−1][L,L+1,L+2,....,L+k-1][L,L+1,L+2,....,L+k−1]，[R,R+1,R+2,...,R+k−1][R,R+1,R+2,...,R+k-1][R,R+1,R+2,...,R+k−1](R⩾L+k)(R \geqslant L+k)(R⩾L+k) 。 输入描述 第一行一个整数 TTT(T⩽10)(T\leqslant 10)(T⩽10),代表有 TTT 组数据。 接下来一行两个整数 n,kn,kn,k(1⩽n⩽200000)(1\leqslant n\leqslant 200000)(1⩽n⩽200000)( ...