题意：有i种物品，每种物品需要买k[i]个，然后商店会有m次特价出售，第j次为在di天出售第ti种物品，物品原价2元，特价1元，你每天上午可以获得一元，下午可以进行交易，求获取所有物品花费的最少时间为多少天？ 思路：如果第i天满足条件，则i+1天一定满足，所有二分答案.如何判断答案x是否符合：按贪心策略去判断：可以在该物品特售的最后一天将目前的全部钱去购买，没有特价买到的可以第x天花原价买。 代码： #include<bits/stdc++.h> #define ll long long using namespace std; const ll inf=1e12; const...

题意：有一颗n个节点并且以1为根的树，每一个节点有一个权值，你可以选择一些节点组成工作组，工作中中的每一个节点他的子树上的节点在工作组的数目为偶数（不包括自己），求工作组的最大权值为多少（工作组的权值等于工作组中每个节点的权值之和）？ 思路：树状dpdp[v][0/1]表示第v个节点在满足条件时该子树在工作组的个数为偶数/奇数的最大权值。首先初始化：(一开始不包括v节点)dp[v][0]=0;dp[v][1]=-inf;（极小值表示不存在）然后加入子树u：dp[v][0]=max(dp[v][1]+dp[u][1],dp[v][0]+dp[u][0]);(奇数+奇数=偶数，偶数+偶数=偶数)d...

题意：描述了一种加密技术，现在将加密后的字符串和字典给出，要你求还原后的字符串。加密方式：①将所有字母改为小写字母②将所单词翻转③将所有空格去掉 思路：你可以将字典中的单词按翻转后的结果插入字典树中。然后dfs加密后的字符串从字典树中查找满足的可划分的单词。 代码： #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <vector> #include <queue&...

题意：给出n个物品的ai和bi的值，求在满足所选物品ai之和除以bi之和等于k时ai之和最大为多少？ 思路：将每一个物品的ai看成价值，ai-bi*k看成体积，这样题目就变成了所选物品体积为0时价值最大为多少？给体积一开始就加上一个较大的值来解决下标为负的问题，这样就只是一个简单的01背包问题了。 代码： #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <vector>...

题意：给出一个长度为n的字符串和一个k，求形成k个不同子串组成的集合至少要删除多少字符？如果无法完成则输出-1. 思路：动态规划：dp[i][j]表示前i个字符组成一个长度为j的不同子串的数目；dp[i][j]=dp[i-1][j] (不加第i个字符)+dp[i-1][j-1] (加第i个字符)+dp[ma[i]-1][j-1] (去重，ma[i]表示前面的最近的s[i]的位置，因为该位置前一个位置长度为(j-1)的子串加上该位置等与加上s[i])初始换：dp[i][0]=1(0<=i<=n);结果从删除少的向删除多的方向进行就可以了。 代码： #include <cstdi...

题意：有n个参赛者，每个参赛者在做第一题和第二题都有一个罚时，两个人组成一队，每个人负责一题，该队罚时为两人罚时之和（队内会取最优策略），求该参赛者在所有可能的组队中总罚时为多少？ 思路：我们发现可以按照前一个写第一题，后一个写第二题最优来排序：既：A.a+B.b<A.b+B.a先求该参赛者与所有其他参赛者组队的总贡献：既：与排在自己前面的组队时取前面的第一题罚时，自己取第二题罚时。与排在自己后面的组队时取后面的第二题罚时，自己取第一题罚时。这过程可以用前缀和优化。然后由于某些不能组队，所有将不能组队的贡献减去即可。 代码： #include <cstdio> #includ...

题意：有一棵n个节点树，请你构造节点数据使图正好为这棵树（节点之间有边仅这二个节点位与等于 -1）。 思路：我们可以先黑白染色，因为n<=100,所以一定会有一种颜色少于等于50，所以我们就应该从位上考虑，不然为什么n<=100而不是小于100000呢，又因为只有相邻黑白节点才连接，所以我们可以考虑：将少的染成白色， -1用二进制表示为第0-59位都为1.白色：最高位为0，白色编号的位为0，其余位为1.黑色：最高位为1，相邻白色的编号的位为1，其余位为0.这样染色，因为白色最高位为0，所以白色与白色一定不连接。因为白色个数小于等于50，所以黑色有些位都为0，所以黑色与黑色一定不连接...

题意：有一个长度为N的数组R，求有多少满足条件的序列A使得0 ≤ A[i] ≤ R[i]A[0]+A[1]+...+A[N-1]=A[0] or A[1]... or A[N-1]输出答案对1e9+9取模 思路：由于A的N个数和与或结果相等，所以每一位最多存在于这n个数中的其中一个数中。所以可以从高位到低位枚举结果，用数位dp和状压思想优化。dp[i][j]表示从第0位枚举到i位并且此时状态位j时满足条件的方案数。（j在第o位为1表示第o个数在第i位取数一定小于等于该数在第i位的值，j在第o位为0表示第o个数在第i位可以随便取值，保证枚举时A[i]<=R[i]）。 代码： #includ...

题意：给出n条边，求该图至少需要设置多少个逃生点才能使无论哪一个点失去，其余点都能至少到达一个逃生点，并求出方案数。 思路：考虑点双连通分量：如果该点双连通分量只有一个割点，则需要设一个逃生点，且该点不能是割点（防止唯一的割点失去时其余点无法到达逃生点）。如果该点双连通分量有大于一个割点，则无需设置逃生点，因为你至少可以通过一个割点到达另一个点双连通分量。如果该点双连通分量没有割点，则需要设二个逃生点（防止设为逃生点的点失去时其余点无法到达逃生点） 代码： #include <bits/stdc++.h> #include <cstdio> #include <c...

题意：有一个n行m列的网格图，起点在格点(n+1，1), 终点在(1,m+1),有k个格点是不能走的障碍点。求从起点到终点的路线有多少种？（只能向上或向右） 思路：从数据范围看当n,m<=1000时我们可以用动态规划解决：dp[n+1][1]=1;dp[i][j]=dp[i+1][j]+dp[i][j-1]当n,m超过1000时，我们发现k很小，所以可以用组合数和容斥解决：从（x,y）到（x2,y2)的路线方式数目为C(x-x2,x-x2+y2-y)（既有（x-x2+y2-y）步，其中选择了（x-x2）步向上走）; 代码： #include <bits/stdc++.h> #...

题意：将n个数分成m组，求最小均方差？ 思路：随机打乱数组，然后贪心求结果，取最小值。(double)clock()/CLOCKS_PER_SEC得出程序运行的时间，单位为S。random_shuffle(a+1,a+n+1);打乱数组。贪心策略：前m个数每个数单独为一组，然后将剩余数分给当前最小数据和的组，可使用优先队列。 代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll inf=1e9+7; int a[100005]; struct w { int ...

题意：有n个石头，FFF和GGG轮流对这堆石头进行操作，每一次可以取[1,k]个石头，但FFF取完后石头数为质数，GGG取完后石头数为合数，如果FFF赢了，则输出回合数，如果GGG赢了，则输出回合数的相反数。 注意：1既不是质数，也不是合数。胜利者会尽可能的快点赢，输者会尽可能的慢点输。 思路：快点赢则胜利者会尽可能的多取点，慢点输则输者会尽可能的少取点。我们首先要知道谁赢，如果第一步都不能走则FFF输，然后如果石头数内有两质数之间相差大于k+1则FFF一定输（因为GGG取成大质数-1时FFF无法取），否则FFF一定赢（因为FFF取到小于等于3时GGG无法取） 代码： #include &lt...

题意：给你一个长度为n的目标数列，源数列为0，1，2.....,n-1。有编号为0到n-2的操作数，你可以使用编号为i的操作数交换源数列第i个和第i+1个数，请你计算源数列变成目标数列操作数的排列方式有多少种？ 思路：分治+记忆化搜索在[l,r]区间使用编号为i的操作数时数列将分为[l,i]和[i+1,r]二个小问题，因为每个编号的操作数都是唯一的，当使用了一个编号时，编号左右两边将没有联系了，所以可以划分为二个小问题，然后左边和右边二个小问题的解决方法之积乘以C(i-l(左边操作次数),r-l-1(区间操作次数-1，本次划分表示为先进行编号为i的操作))。因为左右不相关，所以当左右问题顺序确...

题意：有n个有颜色的贝壳，每一个的颜色值为col[i],小阳能进行以下三种操作：1 l r x：给 [l,r]区间里所有贝壳的颜色值加上x。 2 l r：询问 [l,r]区间里所有相邻贝壳颜色值的差（取绝对值）的最大值（若l=r输出0）。 3 l r ：询问 [l,r]区间里所有贝壳颜色值的最大公约数。 思路：先构造一个差分数组，根据差分数组构造线段树，维护区间值的和、区间值绝对值的最大值、区间值的最大公约数（gcd是具有区间可维护性的，即gcd(a,b,c,d) = gcd(gcd(a,b),gcd(c,d))）. 操作一：在线段树中更新（l-1)的位置加x,r的位置加（-x）。 操作二：在...