浮云世事改, 过月此心明

纸牌游戏题目来源：牛客竞赛ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛牛客竞赛OJ (nowcoder.com) 下面给出这道题的题面 原题题面题目描述 Cubercsl 和 Oneday 在玩一个纸牌游戏。两个人手中都有 n 张数字牌，每张牌面上都包含 0∼9其中一个阿拉伯数字。 游戏规则是需要将手中的牌选出恰好 k 张，组成一个能被 3 整除的非负整数（不能含有多余前导零），组成的数大的获胜。 Cubercsl 自然是想取得胜利，所以他需要找到符合条件的最大的数。 输入描述: 第一行包含一个整数 T (T≤1000)，表示测试数据的组数。对于每组测试数据，包含一个数字构成的串 s (1≤∣s∣≤10^5) 和一个整数 k (1≤k≤∣s∣)，中间以空格分隔，分别表示 Cubercsl 手中的牌和要选出的牌的数量。输入保证 ∑|s| < 10 ^ 6。 输出描述: 对于每组测试数据，在一行输出一个整数，表示最大的能被 3 整除的数。特别地，如果无解，输出 -1。 输入样例： 9 998244353 1 998244353 ...

两点路径问题想法来源 在周四晚上pta竞选赛时写了一道题目，题目给出了一个无向图，没有闭环，给出了两个点a, b, 要求求出a到b之间有多少种路径，输出路径的数量，在考试的时候我直接跳过了，因为当时时间紧任务重没思路跳过了，考完试后便开始思考这道题怎么写，可以计算出所有路径的同时还可以把路径给输出出来，于是乎，便有了这么一个学习笔记(逼真)！ 下面我们来模拟来一道题目 模拟题目给定一个无向图，不存在重根和闭环，给出两个点n, m，要求求出从n点开始到m点有多少种走法，请输出所有的走法和走法的数量 输入格式 第一行输入两个值n和m，分别表示点的数量和路径数 第2行到第n + 1行， 输入两个点a , b，表示a点和b点之间有一条双向路径 最后一行输入两个点op和ed，表示询问op到ed有多少条路可走 输出格式 输出所有可行的路径，隔行输出走法的数量 数据范围 1 <= n, m <= 10^3 样例输入： 7 10 1 2 1 3 1 4 2 5 3 5 4 6 3 6 5 6 5 7 6 7 1 7 样例输出： 1 4 6 7 1 4 6 5 7 1 4 6 3 5 7 1 ...

超市前言：肚子好饿哦，我们去超商买点东西吧，好啊，可是我们没钱了欸，你回去拿点了啊，不行的，我爸妈不给我，这里有面包你们要吃吗？好啊，我家还蛮大的，你们可以来我家van（误 题目来源这道题来自于acwing，下面是链接 145. 超市 - AcWing题库 同时，这道题也可以在算法竞赛进阶指南，POJ，和kuangbin专题里面找到 原题题面超市里有 N 件商品，每件商品都有利润 pi和过期时间 di，每天只能卖一件商品，过期商品不能再卖。 求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。 输入格式 输入包含多组测试用例。 每组测试用例，以输入整数N 开始，接下来输入 N 对 pi 和 di，分别代表第i件商品的利润和过期时间。 在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。 输出格式 对于每组产品，输出一个该组的最大收益值。 每个结果占一行。 数据范围 0≤N≤100001≤pi , di≤10000最多有 14 组测试样例 输入样例： 4 50 2 10 1 20 2 30 1 7 20 1 2 1 1 ...

小沙の赌气前言：你干嘛，哈哈，哎呦，赌，赌什么嘛 题目来源今天这道题来自于2023牛客寒假算法集训营，链接如下： D-小沙の赌气_2023牛客寒假算法基础集训营5 (nowcoder.com) 下面给出该题的题面 原题题面小沙和小雅在一起打游戏，因为赌气，他们想要比比看谁打通的关卡数更多，在游戏过程中，他们两个人都可以获得一些奇怪的道具来帮助他们通关，假设小沙和小雅都从第一关开始，他们必须一关一关通，只有通过了第 x 关，第 x+1 关才会解锁。每次同时卡关他们各自会获得了一个道具，第 i个道具可以使他们通过 [li ri]之间的每一关，在获得每个道具之后，小沙想询问你目前已有的道具游玩下去，谁会领先，领先多少。 输入格式 第一行输入一个数 n ，代表 n 个发放道具，1 ≤ n≤ 10^5。 接下来 n 行，每行输入两个整数 1≤ l ≤ r ≤ 10^9 ，代表小沙获得的游戏道具能帮助他通过哪些关卡。 接下来 n 行，每行输入两个整数 1≤ l ≤r ≤ 10^9，代表小雅获得的游戏道具能帮助她通过哪些关卡。 输出格式 对于每一次获得道具后，目前的领先状况。 每次询问共输出两 ...

页码问题题目来源这道题来自于牛客 https://ac.nowcoder.com/acm/problem/15327 下面给出该题的题面 原题题面小明前几天看书看累了，脑海中突然闪过，这书的页码也很可爱啊。一本书的页码从自然数1按自然顺序编码到n.每个页码不会含有多余的前导数字0.例如，第6页用数字6表示，而不是06、006表示。下面问题来了，你能帮忙小明解决以下问题：给定总页码n，计算出书的全部页码中分别用到的多少次数字0，1，2，…，9. 输入格式 输入书的总页码一个整数n。 输出格式 输出总共10行。在第k行输出页码中用到数字k-1的次数。（k=1,2,…,10） 题目解释 暴力 首先，我是直接暴力解法，把每个数的每一位得出来的数字依次相加，设一个数组来记录0到9的数字个数，然后牛客说我超时了，用dev的时候发现在1e9的时候甚至要27s。想了很久没想明白，之后我借鉴了一个大佬的想法，直接算每一个数字的个数，通过一些规律来计算。 优化 我们先设置一个数，以11459为例 先从1开始，从个位开始数，1，2，3，4，5，6，7，8，9，10每十位就有一个数的个位上是1，那么11459 ...

多重背包问题题目题面有 N种物品和一个容量是 V的背包。 第 i种物品最多有 si件，每件体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。 数据范围0< N , V ≤ 100000 < vi , wi , si≤ 10000 解法1(朴素算法)#include<iostream> #include<algorithm> using namespace std; const int N = 110; int n,m,v[N],w[N],s[N]; int f[N][N]; int main() { cin>>n>>m; for(int i = 1;i <= n;i++) cin>>w[i]>>v[i]>>s[i]; for(int i = 1;i <= n;i++) for(int j = 0;j ...

指针前言：祝大家新年快乐哦！ヽ(✿ﾟ▽ﾟ)ノ 题目来源今天的这道题来自于acwing的一道周赛题，链接如下： 4498. 指针 - AcWing题库 下面给出该题的题面 原题题面给定一个如下图所示的全圆量角器。 初始时，量角器上的指针指向刻度 0。 现在，请你对指针进行 n 次拨动操作，每次操作给定一个拨动角度 ai，由你将指针拨动 ai 度，每次的拨动方向（顺时针或逆时针）由你自由决定。 请你判断，能否通过合理选择每次拨动的方向，使得指针最终仍然指向刻度 0 输入格式 第一行包含整数 n 接下来 n 行，每行包含一个整数 ai，表示一次操作的拨动角度。 输出格式 如果可以做到指针最终仍然指向刻度 0，则输出 YES，否则输出 NO。 数据范围所有测试点满足 1 ≤ n ≤ 15，1 ≤ ai ≤ 180 输入样例1： 3 10 20 30 输出样例1： YES 输入样例2： 3 10 10 10 输出样例2： NO 输入样例3： 3 120 120 120 输出样例3： YES 题目解释优化思路 通过一系列的分析，我们可以大致得到一个思路，就是我们要灵活的计算出一个有效的方式，使得我 ...

Tokitsukaze and a+b=n前提提要： 今天的这道题，是来源于2023牛客寒假算法集训营的第二次练习的problem c 题目来源C-Tokitsukaze and a+b=n (hard)_2023牛客寒假算法基础集训营2 (nowcoder.com) 注意，只要报名了的人才可以进入网站 原题题面题目描述 Tokitsukaze 有一个整数 n， 以及 m 个区间 [L,R] 她想知道有多少种选法，满足：从 m 个区间中选择两个区间 [Li​,Ri​], [Lj​,Rj​] (i≠j)，并从第一个区间选择一个整数 a (Li≤a≤Ri​)，从第二个区间选择一个整数 b (Lj≤b≤R​)，使得 a+b=n 对于两种选法，若 i, j, a, b 中有任意一个数不同，则算作不同的选法。 由于答案可能很大，请输出对 998 244 353 取模后的结果。 输入描述: 第一行包含两个整数 n, m (2 ≤n,m≤ 4 * 10^5)。 接下来 m 行，每行包含两个整数 L, R (1 ≤ L ≤ R ≤ 2 * 10^5) 输出描述: 输出一个整数表示答案对 9 ...

雪花雪花雪花题目来源这道题可以在以下几个地方找到 1.acwing137. 雪花雪花雪花 - AcWing题库 2.北大的POJ3349 — Snowflake Snow Snowflakes (poj.org) 3.算法竞赛进阶指南 题目介绍有 N 片雪花，每片雪花由六个角组成，每个角都有长度。 第 i片雪花六个角的长度从某个角开始顺时针依次记为 ai,1,ai,2,…,ai,6 因为雪花的形状是封闭的环形，所以从任何一个角开始顺时针或逆时针往后记录长度，得到的六元组都代表形状相同的雪花。 例如 ai,1,ai,2,…,ai,6 和 ai,2,ai,3,…,ai,6，ai,1 就是形状相同的雪花。 ai,1,ai,2,…,ai,6和 ai,6,ai,5,…,ai,1 也是形状相同的雪花。 我们称两片雪花形状相同，当且仅当它们各自从某一角开始顺时针或逆时针记录长度，能得到两个相同的六元组。 求这 N 片雪花中是否存在两片形状相同的雪花。 输入格式 第一行输入一个整数 N，代表雪花的数量。 接下来 N 行，每行描述一片雪花。 每行包含 6 个整数，分别代表雪花的六个角的长度（这六个数即为 ...

数据结构初见：KMP今天，我们来看看这么一个数据结构KMP，下面我们来通过了解KMP的基本用法和一些典型例题来逐步了解它吧，(●ˇ∀ˇ●) KMP的基本用法像往常一样，这次我们依然通过一道题来走进KMP的世界，现在有这么一个情景，我们有两个已知大小的字符串，分别是ababa，ababacaababa ​ 现在，有一个问题，问我们第一个字符串在第二个字符串里面出现了几次，同时输出对应的下标。在这么个情景中，我们很容易可以发现，第一个字符串可以在第二个字符串里面找到两次，同时对应的下标是0和7， ​ 这道题大家是怎么想的呢？我在第一次想的时候，就是两个for循环，对第二个字符串进行遍历，对于每一个字符，都进行逐一匹配，如果发现了一组，那么就输出对应的下标，这种方法可以保证正确性，但是不保证速度，因此，前辈们研究出来了这么一个数据结构，可以让我们在更短的时间里面找到最优解，而由于这个方法是三个人发现的，于是就取了他们三人名字的首字母，也就是我们现在说的KMP字符串 我们先来重新看看我们第一次想的朴素算法，第一步，我们设立两个指针，一个指向第一个字符串，一个指向第二 ...