小b有两个长度都为n的序列A,B。 现在她需要选择一些i,然后交换A[i]和B[i],使得A和B都变成严格递增的序列。 你能帮小b求出最少交换次数吗? 输入保证有解。 收起 输入 第一行输入一个正整数n,表示两个......
小b有两个长度都为n的序列A,B。 现在她需要选择一些i,然后交换A[i]和B[i],使得A和B都变成严格递增的序列。 你能帮小b求出最少交换次数吗? 输入保证有解。 收起 输入 第一行输入一个正整数n,表示两个......
1354 选数字 基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题 收藏 关注当给定一个序列a[0],a[1],a[2],...,a[n-1] 和一个整数K时,我们想找出,有多少子序列满足这么一个条件:把当前子...
标签: 数论
ACM模版描述题解这里我们通过样例可以发现A1A的数位和是21,刚好是K-1的倍数,所以我们不妨多举几组数据测试一下,发现竟然都符合这个规律( ̄┰ ̄*),那么AC就不远了。 可是这里需要强调的是,K的最小值,如果K...
ACM模版描述题解图论的问题我没有怎么深入学习,多数都是交给了队友去搞,所以看到这个题时,只知道是图上状压 DPDP,却不知道具体从何入手。看了题解发现,原来形成不相交的简单环其实就是二分图的完美匹配,最后...
石子归并 51Nod - 1021 题意: 现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价 题解: 区间dp的入门题 dp[i...
写题解前,先感谢meopass学长的指点,一语惊醒梦中人!!! 被这题卡得无心准备四六级了 题意: \qquad 求∑i=1ni×n(i,n),1≤n≤1e9\sum_{i=1}^n\frac{i\times n}{(i,n)},1 \le n \le 1e9∑i=1n(i,n)i×n,1≤n...
ACM模版描述题解典型的数位 DP 问题,也是树归~~~先进行素数筛,然后设 dp[i][j][k]dp[i][j][k] 表示前 ii 位,和为 jj,平方和为 kk,然后进行树归就 OK 了!和普通的数位 dp 相差就是一个素数筛和多了一个维度而已...
51Nod - 2599 最近公共祖先(LCA)https://vjudge.net/problem/51Nod-2599 LCA(Lowest Common Ancestors),即最近公共祖先,是指在有根树中,找出某两个节点u和v最近的公共祖先。(若u为v的祖先或者v为u的祖先,则...
标签: 打表
ACM模版描述题解先吐个槽,题面有毒,这题的出题人或者翻译人语文水平堪忧啊……这里说的分成几等分只取其中一份有问题,应该是只留下其中的一份,剩下的全部拿走。真是无语=_=这个题,没有多想,直接打表,打表后...
51Nod-1259-整数划分 V2 将N分为若干个整数的和,有多少种不同的划分方式,例如:n = 4,{4} {1,3} {2,2} {1,1,2} {1,1,1,1},共5种。由于数据较大,输出Mod 10^9 + 7的结果即可。 Input 输入1个数N(1 <= N <=...
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1483 这道题看题解了,完全没有思路。。。。 数据范围1e5,所以就把所有当前容量的倍数做了标记, 对于小于他的数,如果结果是奇数,那么也把...
Rank 23,IOI赛制
//注:题目来自51nod 这道题是一道集拓补排序和DP的好题,而且还有几个细节值得注意,先讲大体思路,再讲细节。 题目: 在这套方案里,有n个自动化工厂,分别对应着生产口罩的不同工序。不过,一些自动化工厂要开始...
51nod-1369 无穷印章 有一个印章,其完全由线段构成。这些线段的线足够细可以忽略其宽度,就像数学上对线的定义一样,它们没有面积。现在给你一张巨大的白纸(10亿x10亿大小的纸,虽然这个纸很大,但是它的面积毕竟...
题目传送门 就是求每个素数因子的个数,然后用前缀和算出答案就好了。#include #include #include #include #include #define rep(i,a,n) for (int i=a;i;i++) #define per(i,a,n) for (int i=a;...
51nod 1279扔盘子 单调栈
51nod图论题解(4级,5级算法题) 1805 小树 基准时间限制:1.5 秒 空间限制:131072 KB 分值: 80 难度:5级算法题 她发现她的树的点上都有一个标号(从1到n),这些树都在空中飘浮不在土地上生根,然而每天她的...
标签: 区间-dp
ACM模版描述题解十分巧妙的一道动态规划问题,应该算是区间 dpdp 吧!首先我们需要考虑,大的数应该更趋向于中间,而小的数则是在两边,所以我们不妨从大到小遍历,不断往已有序列进行插入,插入的方式决定了状态的...
标签: 分治
ACM模版描述题解这个题需要用到分治的思想,最最最重要的一个问题是,合法的连续区间有什么充要条件?这个不难想,某一个区间的最大值和最小值的差加一一定是这个区间的元素个数时才是合法的,因为题中说了,这是 1...
标签: 思维
1548 欧姆诺姆和糖果 题目来源: CodeForces基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题 收藏 关注一天,欧姆诺诺姆来到了朋友家里,他发现了许多糖果。有蓝色和红色两种。...
标签: 模拟
题解懵逼系列……这个题看得不是特别懂,给出官方题解帮助大家参考吧~~~难道说是熬夜的原因?题解我也看得十分懵逼!代码#include #include #include #include <iostream>using namespace std;const int MAXN = ...
https://www.51nod.com/Challenge/Problem.html#!#problemId=1161 公式比较好推 纸上一画就有了 然后就是求组合数 智障啊 就想着c(n,k)中n可能大于等于mod 然后想怎么卢卡斯 怎么分段。。 要求的组合数为c...
标签: 题解
题意简述 设f(n)f(n)f(n)为n的所有因数异或起来的结果,求f(1)xorf(2)xorf(3)⋯xorf(n)f(1) xor f(2)xorf(3)\cdots xorf(n)f(1)xorf(2)xorf(3)⋯xorf(n)的值。 数据 输入:4 输出:7 ...多亏样...
题意 1133 不重叠的线段 基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题 收藏 关注 ...X轴上有N条线段,每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。...
ACM模版描述题解典型的第二类斯特林数,很容易想到递推式 S(i,j)=j∗S(i−1,j)+S(i−1,j−1)S(i, j) = j * S(i - 1, j) + S(i - 1, j - 1),可是这种写法肯定超时,因为数据太大,复杂度 O(nm)O(nm),所以需要利用容...
题意: lyk拥有一个区间。 ...它规定一个区间的价值为这个区间中所有数and起来的值与这个区间所有数or起来的值的乘积。...它们and起来的值为2,or起来的值为7,这个区间对答案的贡献为2*7=14。...
题目描述 有一个字符串S,记录了一个大数,但不知这个大数是多少进制的,只知道这个数在K进制下是K - 1的倍数。现在由你来求出这个最小的进制K。 例如:给出的数是A1A,有A则最少也是11进制,然后发现A1A在22进制...
题解一道典型的后缀数组问题,模版题,如果想要深度学习后缀数组,可以找找看罗穗骞2009年写的一篇相关论文,十分详尽!膜拜不已,我就是看着这个论文学得后缀数组,简直碉堡了!代码#include #include #include ...
思路: 前缀和:从1->n记录和,并且记录当前位置(前缀),从小到大排序,假设为A,B, C,D A i1 i2 i3 i4 前缀 如果i2>i1那么必定是可以形成一个可能的最小子段, B-A , ...A==B那么无论i2 与i1的关系如何都不会...
【传送门:51nod-1611】 简要题意: 给出n个点,编号为1到n,一开始每个点都是不可用状态,要花费c[i]的代价才能使第i个点变为可用点 有m个奖励区间,每个区间输入l,r,d,表示如果l到r的点都为可用状态则...