wweiyiのblog

祝大家新年快乐啊

只有真正的强大，才能什么都不惧怕 只有坚定的内心，才能千里取真金

CSP-S2020 游记 Day0 今年的csp没有试机，这大概是历年来襄阳参加人数最多的一次吧，可能也是参加的最水的一次吧。然而，我被推到历史的风口浪尖，准备迎接这惊涛骇浪，向着省一勇往直前。有一个高三的学哥也参加了，他因为去年参加csp没有打return 0 而死了200分，所以他只有一百五十分，这也给了我一个前车之鉴，让我更加注意，去年也有一个四中的学哥连续两年没有写对文件输入输出，因此我依据这些学哥的事例，让我更加谨慎。 CSP作为2019年noip的替代品，我们当然参加。可是今年noip复活了，为什么我们还是要参加呢？这真的是不得而知的，我们也没有不要知道，我们应该知道的事情就是要好好比赛，拿出成绩来就是了。 在这阳光明媚的日子里，我们有什么理由不好好学习呢。 今天下午四点要去华科，老师要讲要求。 老师讲完要求了，我也听了。 现在是周五 2020年11月6日 22：09分 我现在在历史的交汇点 明天将会有我无法想象的比赛等着我参加。 在这里分享一下考试技巧 进考场水不要带太多，带个半杯就够了，可以带一点吃的。 进考场之后看电脑是不是好的，最好把每一个按键都试一遍，看看能...

【解题报告】 洛谷P1462 通往奥格瑞玛的道路 题目背景 在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量 有一天他醒来后发现自己居然到了联盟的主城暴风城 在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛 题目描述 在艾泽拉斯，有n个城市。编号为1,2,3,…,n。 城市之间有m条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。 每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。 假设1为暴风城，n为奥格瑞玛，而他的血量最多为b，出发时他的血量是满的。 歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。 输入格式 第一行3个正整数，n，m，b。分别表示有n个城市，m条公路，歪嘴哦的血量为b。 接下来有n行，每行1个正整数，fi。表示经过城市i，需要交费fi元。 再接下来有m行，每行3个正整数，ai，bi，ci(1<=ai，bi<=n)。表示城市ai和城市bi之间有一条公路，如果从城市ai到城市bi，或者从城市bi...

【清北学堂国庆刷题班】 Day5 T1 blocks Description 小明是一个积木爱好者，这一天，小明堆了一堆高度连续递减的积木，假设第i个位置的积木高度为d**idi， 热爱思考的小明在想，如果每天在第i堆的积木上多加i个，即每天第i堆的积木高度加i，最短多少天能够出现两堆积木高度相等呢？ 小明试了很久也没有达到出现两堆积木高度相等的那天，于是他想找你帮忙计算一下。 Input 第一行一个数n，n堆积木的原始高度 接下来一行，n个数，第i个数d**idi，表示第i堆积木的高度 Output 一个数，即两堆积木相等至少需要的天数 Sample Input1 12537 29 24 17 9 Sample Output1 15 Sample Input2 1220569 546 511 472 443 419 388 363 324 286 258 230 209 187 154 129 100 74 53 28 Sample Output2 121 Data 40 %, n ≤ 100，di≤10000d_i\le 10000di​≤10000 70 %, n ≤ 50...

竞赛与文化课学习的计划 前情提要： 在2020.11.3这个雨雪交加天气微凉的日子里，wweiyi考出了他高一学期，甚至高中三年可能的最差成绩，这将是一个耻辱，为了改善文化课与竞赛之间的关系，促进两方面协同发展，达到双赢，我决定在此处按照日期顺序列定计划，以儆效尤 update on 2021 10.12 ：没有最差，只有更差 （先咕了）

【清北学堂国庆刷题班】 Day4 T1 油箱 【问题描述】 有 n个城市，每个城市都有加油站，有 m 条单向道路，距离为 x 的道路需要消耗 x 升的汽油。请问你的车辆可以携带的最小油箱容量，使得不限加油次数的情况下，无论你在哪个城市都可以到达任意的城市。 【输入格式】 第一行两个正整数n,m。 接下来 m 行，每行三个正整数x,y,z 表示一条 x 到 y 的有向边，边权为 z。 【输出格式】 输出符合条件的最小油箱容量，如果无法满足输出 −1 【样例输入】 1234563 51 2 11 3 22 3 53 1 42 3 1 【样例输出】 1‮4 【样例解释】 油箱容量为4时，1→2,1→3,3→1,2→3 道路可以通行，此时满足无论你在哪个城市都可以到达任意的城市。 【数据规模与约定】 20% 的数据 n≤5,m≤20n\le 5 ,m\le 20n≤5,m≤20 40% 的数据 n≤50,m≤200n\le 50,m\le 200n≤50,m≤200 60% 的数据 n≤5∗102,m≤2∗103n\le 5*10^2,m\le 2*10^3n≤5∗102,m≤2∗103...

【清北学堂周末刷题班】 Day5 T1 题目名称:大大大 题目描述：   Illyasviel:“两个数乘起来会比一个数大吗？”   Star-dust:“不知道啊，来算算吧。”   读入一个nnn,对于一个三元组(i,j,k)(i,j,k)(i,j,k)满足要求当且仅当1≤i,j,k≤n1\leq i,j,k\leq n1≤i,j,k≤n且i×j≥ki\times j \geq ki×j≥k。 输入描述:   一行一个数字nnn。 输出描述:   一行一个ansansans表示满足要求的三元组的个数。 输入样例: 10 输出样例: 900 数据范围: 对于30%的数据n≤100n\leq 100n≤100 对于60%的数据n≤5000n\leq 5000n≤5000 对于100%的数据n≤100000n\leq 100000n≤100000 思路 看到这道题目，我用2分钟的时间写出来了第一个暴力，O(n3)O(n^3)O(n3) 也就是三十分的代码：（也就是直接暴力了一下子） 12345678910111213141516171819202122#include <ios...

【清北学堂国庆刷题班】 Day3 T1 欢乐 【问题描述】 你是能看到第一题的friends呢。 ——hja 众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。 给定N，求一个K，使得K!≥N!K!K!\ge \frac {N!} {K!}K!≥K!N!​并且K尽量小。 【输入格式】 一行一个整数N。 【输出格式】 一行一个整数代表答案。 【样例输入】 10 【样例输出】 7 【数据规模与约定】 对于30%的数据，N≤10N\le 10N≤10 对于60%的数据，N≤100N\le 100N≤100 对于80%的数据，N≤1000N\le 1000N≤1000 对于100%的数据，3≤N≤1063\le N \le 10^63≤N≤106 思路 取对数 看到这道题目，我第一感觉是来模拟！PS:模拟多爽啊。 结果发现，这大于多少以上的写不出来了，程序立刻就炸了，时间分分钟超过了，整个人都崩了！ 所以就有了三十分的代码 123456789101112131415161718192021222324252627282930313233343536373839...

【清北学堂国庆刷题班】 Day2 T1 小路灯 题目描述 一条平直的公路上有n个小路灯，第ii个路灯的坐标是ai。小A需要把其中的k个点亮，使得每个小路灯与距离最近的被点亮的小路灯的距离的最大值最小。求这个最小值。 输入格式 第1行2个正整数n,k。 接下来n行，每行一个整数ai，表示第i个小路灯的坐标，保证ai是严格单调递增的。 输出格式 1行1个数表示答案。 样例数据 input 12345676 35612192027 output 16 样例解释 点亮第2、5、6个路灯，每个路灯与距离最近的被点亮的路灯的距离分为是1,0,6,1,0,0，最大值是6。可以证明没有比6更小的方案。 数据规模与约定 对于 30% 的数据，n,k≤100n,k\le 100n,k≤100。 对于 100% 的数据，1≤n≤100000,1≤k≤n,∣ai∣≤1091\le n\le 100000,1\le k \le n,|a_i|\le 10^91≤n≤100000,1≤k≤n,∣ai​∣≤109 时间限制：1s 空间限制：512MB 思路 二分答案 看题目，最大值最小，一看就知道是二分答案 ...