好吧，这次没有调出来，所以还是记录一下但它和黑妹的游戏II 是非常相似的思路：对于ALICE和BOB，每次获得的分数即为前缀和，那么令dp[i]表示当前选择i的人能获得的当前分数-对手分数的最大差值倒推，dp[i] = max(dp[i],sum[i] - dp[i+1]);而因为选择个数>=2，则对于ALICE来说1必选故答案为dp[1] 但是为什么初始化不同呢？因为在黑妹的游戏这里，对手的状态在我的状态之后而本题中，我的状态在对手的状态之后所以初始化是不同的 class Solution { public: int stoneGameVIII(vector<int>&am...

组合+容斥  /* HDU 6397 A: Character Encoding 组合计数+容斥 链接:http://acm.hdu.edu.cn/showproblem.php?pid=6397 题意:n m k 选择区间[0,n-1]的数字，每个数字可以选择最多不超过m个使得他们的和等于k； 组合计数+容斥原理 经典的球盒问题 由于和为k,不妨先进行设置每一份的大小为多少，然后对剩下的部分直接进行计算，那么再不存在 n的限制时，答案即为C(k+m-1,m-1); 由于存在限制条件，只能选0~n-1的数 如果只有c个，那么这个数x’>=n一定成立。现在我们做这样一个操作，将所有大于等于...

第一个要求a和p互质，第二个和第三个是广义欧拉降幂，不要求a和p互质，但要求b和的大小关系。 例题：洛谷P4139   处理出对应的由于2的无穷多次幂，即可通过递归来解决  #include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e9; //求欧拉函数 inline int phi(int n){ int res,a; res = a = n; for(int i=2;i*i<=a;i++){ if(a % i) continue; res = res / i *...

思路：dp[i][j]表示从(i,j)到(h,w)中当前减去对手的最大值，显然答案为(1,1),那么当前已经得到了a[i][j],那么对手一定会往大取，显然dp[i][j] = -max(dp[i][j+1],dp[i+1][j]) + a[i][j]参考了青烟大佬的题解  代码如下： #include <bits/stdc++.h> using namespace std; const int N = 505; int h,w; typedef long long ll; int a[N][N]; int f[N][N]; void solve(){ cin >> h...

题目：有 N 个人从东向西排成一排，每个人的状态用一个字符串 S 表示，第i个字符 ​表示从西边数起第 ii 个人的朝向L 表示面朝西， R 表示面朝东。对于队伍中的每个人，如果自己面前的人的朝向和自己一样，那么这个人就会感到幸福。如果面前的人朝向和自己不一样，或者面前没有人，这个人就感到不幸福。你可以进行以下操作最多 K 次（也可以一次都不进行）：选择整数，让从西边数起第 个人转身180度。经过最多 次操作后，感到幸福的人最多有多少人？ 思路：贪心，每次翻转最多只能增加两个人，那么k次之后最多只能增加到n-1个人 #include<cstdio> using namespace ...

思路：   必要性：一个骨牌必由黑和白组成 充分性：考虑选择一对黑格和白格，然后选择一条它们之间的路径，这条路径满足除起点和终点之外都是已匹配的格子，那么对这条路径进行调整就可以得到满足条件的解。  代码： #include<bits/stdc++.h> using namespace std; #define int long long int n; const int N = 3e5 + 10; signed main(){ cin >> n; int black = 0,white = 0; for(int i=1;i<=n;i++){ int x; cin...

题意  有k个点，从出发，求出一个行动字符串长度，并依次写出每次移动的距离，安排从而满足每个点都能被到达，否则输出-1  思路：本题是一个构造题，易发现如果绝对值移动距离的和有偶数和奇数两种情况，那么就一定无解，那么该如何构造？考虑到{1}，{1，2}，{1，2，4}这种情况，那么它们可以将在内的所有奇数情况构造出来，偶数的话，那么添加一个1即可，即{1,1},{1,1,2},{1,1,2,4}....诸如此类，那么就可以构造出答案了。 参考题解：代码： #include<bits/stdc++.h> using namespace std; long n,x[1000],y[10...

一个可以观察的特性是,所以先找出每个数的因子，其实不难看出，min操作的结果就是删去一个数。且只有最小值不能被删去.且gcd的操作也是单调递减的。所以最后这个数的大小一定小于等于 所以问题可以转化为：让你从n个数中选取出一个子集gcd。问你有多少种结果 ≤ 注：因为我们一旦从一个子集中gcd出一个 ≤ 的数。接下来就是把他们全min起来。这样就可以实现上述效果了。  代码如下： #include<bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; const int N ...

题意：从1~n+1中选出最小的k个数，每个数都能进行拆分，并且丢弃不需要的，从而使得1~n都出现且只出现一次 思路：考虑到从1开始加到第k个数刚好<n+1时那么这1~k个数均能用这一个数来表示，而接下来的数只能一个一个取了，并且这样是最优解，n-1则取对应的这个数  代码如下： #include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ll n; cin >> n; ll k = sqrt(2 * n); while(k * (k+1) > 2*(n+1)) ...

没有思路，只能先写写  /*1 1 2 3 5 8 13(x,y)(y,x%y)8k+5 5k+35k+3 3k+23k+2 2k+12k+1 k+1k+1 kk 11 0由于k=1时以上的各数皆是互质，那么就显然是斐波那契数列了*/代码如下：  #include<bits/stdc++.h> using namespace std; typedef long long ll; ll f[105]; int main(){ ll n; cin >> n; f[1] = 1ll; f[2] = 1ll; for(int i=3;i<=100;i++) f[i] = ...

题目链接    思路：对于，枚举每个数的倍数，然后选出两个最小的数，更新答案，复杂度O()  #include<cstdio> const int N=1e7+50; typedef long long LL; int n,x,vis[N],t1,t2,s1,s2; LL ans; int main(){ scanf("%d",&n);ans=1e14; for(int i=1;i<=n;i++){ scanf("%d",&x); if(vis[x])if(ans>x)ans=x,t1=vis[x],t2=i; //相同的数更新下答案 if(!vis[x...

考虑k >= n 时，必为2次而k < n时，则正反的次数都必为n次，而在k次放置中尽量往小放置k,因此答案为

贪心，如果当前字符比答案末尾的字符大，则一直pop_back()即可   ```   #include<bits/stdc++.h> using namespace std; int main(){     string s;     cin >> s;     string ans;     for(int i=0;i<s.size();i++){         while(ans.size() && s[i] > an...