题目链接：https://ac.nowcoder.com/acm/contest/5671/E题目大意：给出n，k，问有没有一个1-n的排列，使得子串长度从1~n，总存在子串的和模n等于k。解题思路：1-n的和是(n+1)n/2能模n余k，则打表可知，奇数的时候k必须为0(别忘了为0的时候不输出k，因为是1—n的排列！)，而偶数的时候k是n/2肯定是把n放在最前面，k放在第二个，后面就是1，n-1，2，n-2...如果n是奇数，P={n,k,1,n-1,2,n-2...}如果n是偶数，P={n,k,1,n-1,2,n-2...}*代码：** #include<bits/stdc++.h&...

题目链接：https://ac.nowcoder.com/acm/contest/5668/F简要题意：解题思路：状况1：a和b不互质，设其最大公因子是a/g + 1,b/g,1,b/g即是答案。状况2：a,b互质，且b的质因子数不超过1，无解。状况3：a,b互质，且相异质因子数超过1个：代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e6+7; int prime[MAXN], cnt; bool vis[MAXN]; int mp[MAXN]; ll...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6778解题思路：二分答案，用f[i][j]表示存不存在到了第i天，二进制表示为j的尾号组(对于某一个尾号，被限制为1，不被限制为0)已经被限制过的情况；对于第i+1天，枚举剩下尾号的子集，判断可行不可行，即可进行转移。 #include<bits/stdc++.h> using namespace std; char s[10]; int c[10]; bool f[10][1<<10]; bool judge(int k, int s) { for(int i = 0; i...

题目链接：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=890&pid=1003解题思路：暴力，map<node, vector<int> >map第一维是记录时间地点，第二维记录在这个时间地点有哪些元素。如果被感染就标记一下。代码：</int> #include<bits/stdc++.h> using namespace std; const int N = 2e4+7; struct node{ int t, p; bool operator &lt...

题目链接：https://ac.nowcoder.com/acm/contest/5668/C简要题意：下图为某机器人右手手印的形状，左手为右手的对称图形，现在给你一个机器人的手印(可能经过平移和旋转)，请判断是左手还是右手(保证一定是其中一只手)给你20个点，按照顺时针方向或者逆时针方向给出，如下图（该图为右掌）解题思路：计算几何顺/逆时钟判断，(与给出三角形三个顶点求面积就差个绝对值),判断出给的点是按照顺/逆时针方向给的就可以通过边来判断左手还是右手了。代码实现上这道题eps需要给大点，不需要那么精确。证明：https://www.zybang.com/question/761f8b42...

题目链接：https://ac.nowcoder.com/acm/contest/5668/A简要题意：小月有n单位的时间都在钓鱼，每个单位时间有4种状态，有蛤蜊/没蛤蜊，有鱼/没鱼。小月事先知道这n个时间点的状态。每个时间点有四种可能的动作：1.若该时间点有鱼，则可以直接钓鱼。2.若该时间点有蛤蜊，则可以用该蛤蜊制作一个鱼饵。3.若该时间点身上有至少一个鱼饵，则可以用一个鱼饵钓一条鱼，钓完后就少了一个鱼饵。4.什么都不做。 请问小月最多可以钓多少条鱼。 解题思路：贪心，从时间早考虑到时间晚，有蛤蜊的时候就做鱼饵，没蛤蜊的时候就尝试用鱼饵钓鱼，最后若发现有x包鱼饵，就把制作比较晚的x/2包鱼饵...

题目描述：总共有t首歌，每次可以从该次的备选歌中选1首歌，总共选s首。问最少按多少次按钮。备注：一开始从1开始播放，比如第一次要播放第3首歌，需要按两下按钮。样例解释：共15首歌，需要放两首，第一首可以在1、3、8、9里选一首放，第二首从12、2里选一首放。问最少按多少次按钮。解题思路：终于碰上一次01滚动优化的dp题了。计算一首歌切到另一首歌的时候需要按多少次按钮需要稍微考虑考虑。代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; ll dp[2][1010]; ll now[1010]; ...

题目链接：https://ac.nowcoder.com/acm/contest/5669/H题目描述：把1~N的数选尽量多的组，使得每组gcd大于1.输出任意一种方案。做法：看到匹配gcd大于1的，我们很容易想到质数，质数和除其倍数的数的gcd都是等于1的。考虑哪些数字是不可能在匹配里的。首先1不可能在匹配里。大于n/2的质数p，也是可以直接扔掉的。接下来会发现其他的数都不太好扔了，它们都有可能与别的数匹配。考虑怎么匹配。<=n/2的p它们是怎么匹配的？现在考虑一个质因子p，会有2p，3p，4p...，kp现在还有一个问题就是这些数有可能被别的数匹配过了，我们的策略中需要考虑到这点。我...

题目链接：https://ac.nowcoder.com/acm/contest/5669/F解题思路：有一个简单方法：1.找到四个距离中的最大值即可锁定一组对角。代码： #include<bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { int ac, ad, bc, bd; scanf("%d%d%d%d",&ac,&ad,&bc,&bd); if(ad == max(max(ac...

题目链接：https://ac.nowcoder.com/acm/contest/5669/B解题思路：我们可以直接看出当x每次都只去掉一个质因子，fc=c^(x的素因子个数)，本题T是1e6因此直接欧拉筛打表好了，维护一下素因子个数。代码： #include<bits/stdc++.h> using namespace std; const int mod = 1e9+7; const int MAXN = 1e6+7; typedef long long ll; ll quick_pow(ll a, ll b, ll m){ ll ans = 1; while(b > 0...

题目链接：https://www.jisuanke.com/contest/11486/676873题目描述：有两个等差数列A,B,给定长度N,起始点F,等差D,LCS的长度。解题笔记：这题就是个拓展欧几里得，A的某一位和B的某一位相等，则有：-> F1+D1x=F2+D2y-> D1x-D2y=F2-F1于是问题便转化为了拓展欧几里得求符合条件解的个数。看起来模板以上就解决了吧，于是我写了如下代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; ll exgcd(ll a, ll ...

转载自：https://www.cnblogs.com/1pha/p/7749828.htmlVishwas Garg提供了一种更为高效(logN)的求一个数所有素因子的方法.具体步骤1.除以所有以 2 为倍数的因子2.枚举以 i 为倍数为因子的整数, 此时 i 肯定不为 2.3.防止 n 为一个大的素数代码： void primeFactor(int n){ // 除去所有 2 的倍数的因子 while(n % 2 == 0){ printf("2 "); n /= 2; } // 经过第二步, 此时 n 一定为奇数 // 并且不存在偶数的素因子 // 所以我们可以跳过所...

LCS：设d(i,j)为A1,A2,...,Ai和B1,B2,...,Bj的LCS长度，则当A[i]=B[j]时，d(i,j)=d(i-1,j-1)+1,否则d(i,j)=max{d(i-1,j),d(i,j-1)},时间复杂度为O(nm),其中n和m分别是A和B的长度。输出LCS的思想其实就是倒过来反向推理的过程。代码： #include<bits/stdc++.h> using namespace std; const int maxn = 1e3+7; int a[maxn]; int b[maxn]; int dp[maxn][maxn]; int n, m; void p...

题目链接：https://codeforces.com/contest/1382/problem/B解题思路：假设a1>1。如果移除第一堆就赢了，玩家1会这样做。否则，玩家1可以在第一堆中只留下一块石头，迫使玩家2移除它，让玩家1处于获胜位置。否则，如果a1=1，则强制移除第一个桩。 因此，无论哪一个玩家拿到第一堆多石的胜利。也就是说，k是最大数，使得a1=⋯=ak=1。如果k是偶数，第一个玩家将获胜。否则，第二个玩家将获胜。唯一的例外是所有的桩都只有一块石头。在这种情况下，第一个玩家在k为奇数时获胜。 复杂性是O（n）代码： #include<bits/stdc++.h> ...