题意：有n种食材，m种菜肴，每种菜肴给出所需食材和美味值和制作时间，因为每种食材以a[i]的速率变得不新鲜，求在t秒总美味值最大为多少？ 注意：最大总美味值可能为负。 思路：贪心+01背包贪心：设二种相邻菜肴，第一种所需食材变的不新鲜的速率为w[i].a,美味值为w[i].b，制作时间为w[i].c,第二种所需食材变的不新鲜的速率为w[i+1].a,美味值为w[i+1].b，制作时间为w[i+1].c;如果顺序正确则需满足:w[i].b-w[i].aw[i].c+w[i+1].b-(w[i].c+w[i+1].c)w[i+1].a<w[i+1].b-w[i+1].aw[i+1].c+w[...

题意：求一个n长度的序列删除m个元素后不同序列的个数，结果对1000000007取模 思路：dp[i][j]为前i个元素删除j个元素序列的个数dp[i][j]=dp[i-1][j]+dp[i-1][j-1]去重：因为重复只存在于二个相同元素之间的元素全部删除后的在二个元素中删除其中一个dp[i][j]=dp[i][j]-dp[k-1][j-(i-k)]k是与该元素相同的上一个元素的下标 代码： #include<bits/stdc++.h> #define inf 1000000007 using namespace std; typedef long long ll; in...

题意：小美有一个由n个元素组成的序列{a1,a2,a3,...,an}，她想知道其中有多少个子序列{ap1,ap2,...,apm}(1 ≤ m ≤ n, 1 ≤ p1 < p2 ,..., < pm ≤ n)，满足对于所有的i,j(1 ≤ i < j ≤ m), < 成立。 思路： 同理由 得： 所以当 并且 时 所以： 用一个dp数组计数，dp[i]为以a[i]结尾满足条件的个数 代码： #include<bits/stdc++.h> using namespace std; #define ll long long #de...

题意：小团有一张n个点，m条边的无向图G，有些边上已经被标记了0或1，表示它的边权。现在你需要给剩下的边标记边权为0或1，求有几种标记的方式满足： 对于G中任意一个环，里面所有边的边权的异或值为0。环的定义如下： 对于任意k（k≥2）个点{a1,a2,...,ak}，若对于所有的i<k满足ai与ai+1之间有边，且a1=ak成立，则这k个点构成一个环。 思路： 参考了该题解：https://blog.csdn.net/jaihk662/article/details/80955631如该题解所说，首先换边权为点权，既边权为它连接的二个点权的异或值，这样对于一个环而言，所有边的...

题意：有一个n长度的A数组，求大于等于k的长度的连续子区间第K大的数加入B数组，求B数组第m大的数。 思路：二分+尺取法 代码： #include<bits/stdc++.h> using namespace std; #define ll long long #define inf 1000000007 int a[100005], b[100005], n, k; ll m; bool fun(int d) { int l=0, r=0, z=0; ll s=0; for(; l<=n-k;) { for(; ...

题意：n只糖糖分为二组做游戏，排成一排，第i只糖糖有能力值bi，从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1,b2,.....,bci都会增加1，现在，娇姐想知道在第n秒后，会有多少只糖糖存活下来。 思路：逆向模拟 代码： #include<bits/stdc++.h> using namespace std; #define ll long long #define inf 1000000007 int a[100005], b[100005], f[...

https://ac.nowcoder.com/acm/problem/23049 题意：被给予n根木棍，华华需要k根，华华可以将每根木棍裁剪成若干段自己想要的长度，并丢掉多余的部分，华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。 思路：二分寻找长度 代码 #include<bits/stdc++.h> using namespace std; #define ll long long #define inf 1000000007 int a[200005]; int n, k; int fun(int z) { ll...

题意：求所有长度为n的01串中满足如下条件的二元组个数：设第i位和第j位分别位ai和aj（i<j），则ai=1,aj=0。答案对1e9+7取模。 思路：从n个位置中选二个位置，左边一个为1，右边一个为0，其余位置随便(2的(n-2)次方)，则每一种情况都有一个二元组，由于一次只计算了选中的二个位置，所以无重复。 代码：#include<bits/stdc++.h> using namespace std;#define ll long long#define inf 1000000007 ll fun(ll n, ll k){ n=n%inf; ll s=1; ...

题意:求一棵n个点的树中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。思路：奇+奇=偶，偶+偶=偶所以用跑一遍dfs求出奇数深度结点的数目x和偶数深度结点的数目y再计算偶数路径数=(x(x-1)+y(y-1))/2; #include<bits/stdc++.h> using namespace std; #define ll long long #define inf 998244353 int n; vector<int> g[200005]; struct w { int x, y;...

题意：求一个数组中的有多少组两个互不相交的区间异或和为零。思路：直接暴力，从左到右枚举数组，将以当前元素的前一个元素为右端点，枚举该类区间的异或和，用一个数组仿map容器记录个数，再以当前元素左端点，枚举该类区间的异或和，将map容器中值相同的数的个数加起来就是结果了 代码： #include<bits/stdc++.h> using namespace std; #define ll long long #define inf 998244353 int a[1005], ma[500005]; int main() { int n; ll z=0; ...

链接：https://ac.nowcoder.com/acm/contest/1069/C 来源：牛客网 题目描述 ： 用高精度计算出S=1！+2！+3！+…+n！（n ≤ 50）其中“！”表示阶乘，例如：5！=54321。 输入描述: 输入正整数N 输出描述: 输出计算结果S 输入 3 输出 9 **思路：**由于50的阶乘比较大，long long 也无法储存，所以用字符串进行储存，进行大数加法和大数乘法； #include <stdio.h> #include <stdlib.h> #include <string.h> #include...

**红魔馆爆炸了** 题目描述 红魔馆最近迎来了两块陨石，由于防范不到位，第一块陨石从天而降，红魔馆爆炸了。馆主蕾米莉亚有着强大的力量，她决定阻止第二块陨石，方法是将陨石打爆，使其分裂成若干个小石块。为了简化问题，我们可以将一块陨石看作由连续的n个石块组成，每个石块包含了一定能量，蕾米莉亚需要毁掉其中某一段连续的石块(该段能量和为s)，被毁掉的石块将会消失，且因连锁反应还会使剩余石块总能量减少s，蕾米莉亚需要保证剩余石块总能量不大于m，红魔馆就能保存下来。蕾米莉亚想知道她最短需要毁掉的连续石块长度。 输入： 有多组输入，每组输入第1行为两个数字n、m(1<=n<=100000...