机器人正在玩一个古老的基于DOS的游戏。 游戏中有N+1座建筑——从0到N编号，从左到右排列。 编号为0的建筑高度为0个单位，编号为i的建筑高度为H(i)个单位。 起初，机器人在编号为0的建筑处。 每一步，它跳到下一个（右边）建筑。 假设机器人在第k个建筑，且它现在的能量值是E，下一步它将跳到第k+1个建筑。 如果H(k+1)>E，那么机器人就失去H(k+1)−E的能量值，否则它将得到E−H(k+1)的能量值。 游戏目标是到达第N个建筑，在这个过程中能量值不能为负数个单位。 现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？ 输入格式 第一行输入整数N。 第二行是N个空...
四平方和定理，又称为拉格朗日定理： 每个正整数都可以表示为至多4个正整数的平方和。 如果把0包括进去，就正好可以表示为4个数的平方和。 比如： 5=0^2+0^2+1^2+2^2 7=1^2+1^2+1^2+2^2 对于一个给定的正整数，可能存在多种平方和的表示法。 要求你对4个数排序： 0≤a≤b≤c≤d 并对所有的可能表示法按a,b,c,d为联合主键升序排列，最后输出第一个表示法。 输入格式 输入一个正整数N。 输出格式 输出4个非负整数，按从小到大排序，中间用空格分开。 数据范围 0<N<5∗1e6 输入样例： 5 输出样例： 0012 题解: 暴力three重循环判...
字符串A中删除字符串B中所有相同字母（无论大小写） / @func: 字符串A中删除字符串B中所有相同字母（无论大小写） @date2024/05/06 @version1.0：版本 CopyRight(c)2023-2024ni456xinmie@163.comAllRightReseverd / voidrepeat(chara,constcharb) { chartmp=a;//用来写入新字符串的指针 chartemp_b=b;//用来遍历b字符串的临时变量 while(a) { intfound=0;//标记是否找到了匹配的字符,如果找到，赋值为1，并退出循环；如果没找到则进行赋值操作...
100可以表示为带分数的形式：100=3+69258/714还可以表示为：100=82+3546/197注意特征：带分数中，数字1∼9分别出现且只出现一次（不包含0）。 类似这样的带分数，100有11种表示法。 输入格式 一个正整数。 输出格式 输出输入数字用数码1∼9不重复不遗漏地组成带分数表示的全部种数。 数据范围 1≤N<1e6 输入样例1： 100 输出样例1： 11 输入样例2： 105 输出样例2： 6 题解: 枚举所有a的情况,在每种a的前提下,再枚举所有c的情况 根据a,c,n计算出b 判断是否满足[1,9]仅出现过一次,且a,b,c中不含有0 代码并...
小明正在玩一个“翻硬币”的游戏。 桌上放着排成一排的若干硬币。我们用表示正面，用o表示反面（是小写字母，不是零）。 比如，可能情形是：oooooo 如果同时翻转左边的两个硬币，则变为：oooooooo 现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？ 我们约定：把翻动相邻的两个硬币叫做一步操作。 输入格式 两行等长的字符串，分别表示初始状态和要达到的目标状态。 输出格式 一个整数，表示最小操作步数 数据范围 输入字符串的长度均不超过100。数据保证答案一定有解。 输入样例1： oo 输出样例1: 5 输入样例...
小明开了一家糖果店。 他别出心裁：把水果糖包成4颗一包和7颗一包的两种。 糖果不能拆包卖。 小朋友来买糖的时候，他就用这两种包装来组合。 当然有些糖果数目是无法组合出来的，比如要买10颗糖。 你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。 大于17的任何数字都可以用4和7组合出来。 本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。 输入格式 两个正整数n,m，表示每种包装中糖的颗数。 输出格式 一个正整数，表示最大不能买到的糖数。 数据范围 2≤n,m≤1000， 保证数据一定有解。 输入样例： 47 输出样例： 17 题解: 这题其实就是一个结论,...
长100厘米的细长直杆子上有n只蚂蚁。 它们的头有的朝左，有的朝右。 每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。 当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。 这些蚂蚁中，有1只蚂蚁感冒了。 并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。 请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。 输入格式 第一行输入一个整数n,表示蚂蚁的总数。 接着的一行是n个用空格分开的整数Xi,Xi的绝对值表示蚂蚁离开杆子左边端点的距离。 正值表示头朝右，负值表示头朝左，数据中不会出现0值，也不会出现两只蚂蚁占用同一位置。 其中，第一个数据代表的蚂蚁感冒了。 输出格式 输出1个整数，表示...
博客园 我的博客 快速沃尔什变换解决的卷积问题 快速沃尔什变换（FWT）是解决这样一类卷积问题： \[c_i=\sum_{i=j\odotk}a_jb_k\] 其中，\(\odot\)是位运算的一种。举个例子，给定数列\(a,b\)，求： \[c_i=\sum_{j\oplusk=i}a_jb_k\] FWT的思想 看到FWT的名字，我们可以联想到之前学过的FFT（很可惜，我没有写过FFT的笔记，所以没有链接），先看看FFT的原理： 把\(a,b\)变换为\(A,B\)，\(O(n\logn)\)； 通过\(C_i=A_iB_i\)计算，\(O(n)\); 把\(C\)变...
摘要：在当今的数字世界中，密码安全是至关重要的。为了保护用户密码免受未经授权的访问和破解，Password-BasedKeyDerivationFunction2(PBKDF2)算法成为了一种重要的工具。 在PBKDF2算法中，SHA表示SecureHashAlgorithm，它是一系列密码哈希函数的标准，其中SHA-1、SHA-256、SHA-384和SHA-512等是常见的版本。因此，PBKDF2-SHA就是使用SHA系列算法作为其内部哈希函数的密码派生函数。 PBKDF2-SHA算法的工作原理是通过多次迭代将输入的密码和盐值进行混合和计算，以生成一个安全的密钥。这样设计可以增加攻击者破解...
有N件物品和一个容量是V的背包。每件物品只能使用一次。 第i件物品的体积是vi，价值是wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。 输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。 接下来有N行，每行两个整数vi,wi，用空格隔开，分别表示第i件物品的体积和价值。 输出格式 输出一个整数，表示最大价值。 数据范围 0<N,V≤1000 0<vi,wi≤1000 输入样例 4512243445 输出样例： 8 题解: 每个物品都有两种情况,选或者不选,所以要从2^n中方案中找到最大值 f[i][j]...
AAtCoderLine(abc352A) 题目大意 给定\(x,y,z\)，问\(z\)是否在\(x,y\)之间。 解题思路 如果\(x>y\)，则交换\(x,y\)，然后判断是否有\(x\leqz\leqy\)即可。 神奇的代码 include<bits/stdc.h> usingnamespacestd; usingLL=longlong; intmain(void){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); intn,x,y,z; cin>>n>>x>>y>...
给定一个长度为N的数列，A1,A2,…AN，如果其中一段连续的子序列Ai,Ai+1,…Aj之和是K的倍数，我们就称这个区间[i,j]是K倍区间。 你能求出数列中总共有多少个K倍区间吗？ 输入格式 第一行包含两个整数N和K。 以下N行每行包含一个整数Ai。 输出格式 输出一个整数，代表K倍区间的数目。 数据范围 1≤N,K≤100000,1≤Ai≤100000 输入样例： 5212345输出样例：6 题解: 先求前缀和 对前缀和s[i]取余,余数相同的前缀和互相相减是k的倍数(ps:如果余数相同的个数是4,那么答案应该加上3+2+1;相同的个数是3的话,应该加上2+1,还不懂的话看下图) ...
AThebottomoftheninth(abc351A) 题目大意 给定\(9\)个\(a_i\)和\(8\)个\(b_i\)，问最后一个\(b_9\)是多少，使得\(\suma_i<\sumb_i\)。 解题思路 答案就是\(\suma_i\sumb_i+1\)。 神奇的代码 a=sum(map(int,input().split())) b=sum(map(int,input().split())) print(ab+1) BSpottheDifference(abc351B) 题目大意 给定两个二维矩阵，仅一个位置元素不一样，找出那个位置。 解题思路 二维遍历一下就找到...
儿童节那天有K位小朋友到小明家做客。 小明拿出了珍藏的巧克力招待小朋友们。 小明一共有N块巧克力，其中第i块是Hi×Wi的方格组成的长方形。 为了公平起见，小明需要从这N块巧克力中切出K块巧克力分给小朋友们。 切出的巧克力需要满足： 形状是正方形，边长是整数 大小相同 例如一块6×5的巧克力可以切出6块2×2的巧克力或者2块3×3的巧克力。 当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？ 输入格式 第一行包含两个整数N和K。 以下N行每行包含两个整数Hi和Wi。 输入保证每位小朋友至少能获得一块1×1的巧克力。 输出格式 输出切出的正方形巧克力最大可能的边长...
原题链接你玩过“拉灯”游戏吗？ 25盏灯排成一个5×5的方形。 每一个灯都有一个开关，游戏者可以改变它的状态。 每一步，游戏者可以改变某一个灯的状态。 游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。 我们用数字1表示一盏开着的灯，用数字0表示关着的灯。 下面这种状态 1011101101101111000011011在改变了最左上角的灯的状态后将变成： 0111111101101111000011011再改变它正中间的灯后状态将变成： 0111111001110011010011011给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都...
空中唤醒功能，英文名称为WakeonRadio(WOR)，其原理主要是通过减少接收端射频处于接收状态的时间，而在其余时间使设备处于深度睡眠模式，以此来实现设备功耗的显著降低。这种机制确保了设备在不需要接收数据时保持低功耗状态，而在需要接收数据时能够迅速被唤醒至接收状态。 具体来说，空中唤醒功能的实现依赖于发送特殊的前导码来唤醒设备。当设备处于休眠状态时，一旦接收到这个前导码，它就会从睡眠状态中醒来并进入接收状态，准备接收来自发送端的数据。如果在一定时间内没有接收到数据，设备会自动回到休眠状态，等待下一次的唤醒信号。 空中唤醒技术还涉及到对设备唤醒和休眠时间的精确配置。唤醒时间指的是设备保持唤醒...
"飞行员兄弟"这个游戏，需要玩家顺利的打开一个拥有16个把手的冰箱。 已知每个把手可以处于以下两种状态之一：打开或关闭。 只有当所有把手都打开时，冰箱才会打开。 把手可以表示为一个4×4的矩阵，您可以改变任何一个位置[i,j]上把手的状态。 但是，这也会使得第i行和第j列上的所有把手的状态也随着改变。 请你求出打开冰箱所需的切换把手的次数最小值是多少。 输入格式输入一共包含四行，每行包含四个把手的初始状态。 符号+表示把手处于闭合状态，而符号表示把手处于打开状态。 至少一个手柄的初始状态是关闭的。 输出格式第一行输出一个整数N，表示所需的最小切换把手次数。 接下来N行描述切换顺序，每行输出两个...
原题链接 暴力做法(时间复杂度O(n^2)) 每次选取下标i为峰值,进行n次，对每次取max就可以找到答案 对于i左边的序列:需要满足序列是非递减的,同时每个值尽可能大 所以满足:j的位置上的数<=(j,i]上的最小的值(等于时取得最大值),同时需要保证j位置上的数要小于heights[j](题目中的要求，美丽塔的要求);即t=min(pre,heights[j])pre表示的是下标是(j,i]的最小的值 对于i右边的序列:需要满足序列是非递增的，同时每个值尽可能大 所以满足：j的位置上的数<=[i,j)上的最小的值(等于时取得最大值),同时需要保证j位置上的数要小于heigh...
滑动窗口限流 滑动窗口限流是一种常用的限流算法，通过维护一个固定大小的窗口，在单位时间内允许通过的请求次数不超过设定的阈值。具体来说，滑动窗口限流算法通常包括以下几个步骤： 初始化：设置窗口大小、请求次数阈值和时间间隔。 维护窗口：将请求按照时间顺序放入窗口中，并保持窗口内请求数量不超过阈值。 检查通过：每当有新的请求到达时，检查窗口内请求的总数是否超过阈值，如果未超过则允许通过，同时移除窗口最老的请求。 更新窗口：随着时间的推移，更新窗口内的请求情况，确保窗口内的请求符合限流条件。 滑动窗口限流算法可以有效控制系统的请求流量，避免系统被大量请求压垮。同时，由于其简单高效的特点，被广泛应用...
一、贪心算法 贪心算法，又称贪婪算法，是算法设计中的一种思想 其期待每一个阶段都是局部最优的选择，从而达到全局最优，但是结果并不一定是最优的 举个零钱兑换的例子，如果你有1元、2元、5元的钱币数张，用于兑换一定的金额，但是要求兑换的钱币张数最少 如果现在你要兑换11元，按照贪心算法的思想，先选择面额最大的5元钱币进行兑换，那么就得到11=5+5+1的选择，这种情况是最优的 但是如果你手上钱币的面额为1、3、4，想要兑换6元，按照贪心算法的思路，我们会6=4+1+1这样选择，这种情况结果就不是最优的选择 从上面例子可以看到，贪心算法存在一些弊端，使用到贪心算法的场景，都会存在一个特性： 一旦一...