WORIA

https://ac.nowcoder.com/acm/contest/5961 C. 二维动点   题意：平面上有一些点，每次选一个点移动到该点与当前位置所成直线上任意一处，问从（0，0）到（x，y）的最少移动次数。 容易发现最多移动3次。 当目标就是原点时，移动0次。 当目标在某点与原点直线上时，移动1次。 当目标与任意两点的连线都和这两点与原点的连线平行，即目标与任意两点，以及原点 都构成平行四边形时，移动3次。 其它情况都移动2次。 注意一些细节： 不论是询问时还是已有的点， x==0&&y==0x==0\&\&y==0x==0&&y==0 时都要注意特判！！ 要两边都平行！！ 要用map.count()！！ map.size()==0也要特判！！   123456789101112131415161718192021222324252627282930313233343536#include<bits/stdc++.h>using namespace std;#define ll long longconst int ...

https://ac.nowcoder.com/acm/contest/5205/ A. 牛妹的游戏 题意：平面上有n个点，完全图中的每条边边被红方或蓝方占领，给出了蓝方占领的边。问是否有三条同一阵营的边连成三角形。 由拉塞姆结论得到如果平面上大于等于6个点，那么必定有至少一方形成三角形。 假设AB,AC,AD属于蓝方，则BC,BD,CD一定要属于红方，否则已经有三角形了。但是BC，BD，CD又形成了三角形。所以得证。 那么只要在5个点以内暴力判断一下即可。 1234567891011121314151617181920212223242526272829303132#include <bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;int T;int n, m;int mp[100][100];int main() { scanf(&qu ...

https://ac.nowcoder.com/acm/contest/5026 E. 相似的子串   题意：给定字符串和k，要找出k个不相交的子串，最长公共前缀大于等于x，求最大的x。 二分+字符串哈希 二分结果长度，因为显然答案单调，即越短，越会成功。 固定长度check是否有至少k个不相交子串最长公共前缀大于等于x，等价变为k个等于x的不相交子串，las[i]las[i]las[i] 记录哈希值为i的字符串在左边最近出现的位置。 dp[i]dp[i]dp[i] 记录以第i位开头，长为check的长度的串出现次数。 每次在串结尾更新las保证不会相交。 关于二分，看 https://www.woria.xyz/2020/01/19/ecr80/#D-Minimax-Problem 12345678910111213141516171819202122232425262728293031323334353637383940414243#include<bits/stdc++.h>using namespace std;#define ll long long#define ...

https://ac.nowcoder.com/acm/contest/4853 C. 操作集锦   题意：问给定字符串有几个长度为 kkk 的不同的子序列。 dp dp[i][j]dp[i][j]dp[i][j] 表示到第 iii 位，长度为 jjj 的不同子序列个数。 如果第 iii 位的字母没有出现过，则可以直接再前面的所有序列末尾再加上，得到新的序列。 而如果出现过，那么就可能和最近一次相同的字母位置的dp重复，重复的数量就是前一次dp的值，因为前一次得到的序列，这一次一定都能得到。而每次都只减去最近一次的重复值，就可以保证不会多减。 1234567891011121314151617181920212223#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const ll mod = 1e9 + 7;int n, k;char s[N];ll dp[1010][1010];int b[30] ...

https://ac.nowcoder.com/acm/contest/3007 题解 https://ac.nowcoder.com/discuss/367149?type=101&order=0&pos=1&page=1 A. 配对   题意：A，B两个集合，要使每个元素两两配对，且每对求和，使第K大的和最大。 贪心 只用前K大的数配对，变成使最小的和最大，可以贪心地倒序配对，取每次地最小值，最小值一定最大。 12345678910111213141516#include<bits/stdc++h>using namespace std;const int N = 100050;int a[N], b[N], n, k, ans = 2e8;int main(){ int i, j; scanf("%d%d", &n, &k); for(i = 1; i <= n; i++)scanf("%d", &a[i]); for(i = 1; i &l ...

https://ac.nowcoder.com/acm/contest/4743 C. 装备合成   题意：牛牛有x件材料a和y件材料b，用2件材料a和3件材料b可以合成一件装备，用4件材料a和1件材料b也可以合成一件装备。牛牛想要最大化合成的装备的数量，于是牛牛找来了你帮忙。 三分合成多少第一件装备。 12345678910111213141516171819202122232425262728#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const ll mod = 1e9 + 7;int T;ll a, b;ll ck(ll x) { ll ta = a - 2 * x, tb = b - 3 * x; return x + max(0ll, min(ta / 4, tb));}int main() { scanf("%d", &T) ...

https://ac.nowcoder.com/acm/contest/4090 C. 矩阵消除游戏   题意：nm的矩阵，每次选一行或一列得到它的元素和，并把这行或列置为0，问操作k次的最大值。 状压枚举 直接枚举行的选择情况，再每次nm处理出列，取最大的。 123456789101112131415161718192021222324252627282930313233343536373839#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;int a[20][20], n, m, k;int t;int sum2[N], vc[N], ans, sum1[N];int main() { cin >> n >> m >> k; for (int i = 0; i < n; i++) { for (int j = 0; j < m ...

https://ac.nowcoder.com/acm/contest/3566 C. 小魂和他的数列   题意：给定数组，问有多少个长度为k的严格递增序列。 和求最长递增序列一样，每次更新当前长度的值，并用树状数组维护前缀和。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 5e5 + 10;const int INF = 0x3f3f3f3f;const ll mod = 998244353;int n, k, tot;int a[N], b[N];ll sum[20][N], dp[20][N];int lowbit(int x) { return x & -x; }void add(int id, int b, ll x) { for (int i = b; i ...

https://ac.nowcoder.com/acm/contest/2927 B. 数字游戏   题意：有2n-1个数：2,3,4…2n。 裁判会随机擦掉一个数字。 然后有两个非常聪明的同学甲和乙玩游戏，他们都会采取最优策略。首先乙擦掉一个，甲擦掉一个，再乙擦，再甲擦…直到黑板上只剩下两个数。 如果这两个数互质，那么甲胜，否则乙胜。 问裁判有多少种擦数的方案，使得乙必胜。 2≤n≤10182\leq n\leq 10^{18}2≤n≤1018 如果擦去奇数，则剩下的偶数比奇数多2个，最终一定可以剩下2个偶数，则乙必胜。 如果擦去偶数，例如6，则一定可以(2,3),(4,5),(7,8),(9,10)这样奇偶搭配，相邻差1，则一定互质，只要甲每次删乙删的数的对应数，一定可以剩下一对，则甲必胜。 那么就是问奇数个数即n-1. 123456789101112#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 1e5 + 10;const int INF = 0x3f3f3 ...

https://ac.nowcoder.com/acm/contest/1114 A. 超越学姐爱字符串   题意：问有多少种长为n的只有’c’和’y’的字符串满足没有两个相邻的’c’。 dp[i][0/1]dp[i][0/1]dp[i][0/1] 表示第i位为’c’或’y’，简单转移即可。 123456789101112131415161718#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;const ll mod = 1e9+7;int n;int dp[N][2];int main() { cin >> n; dp[1][0] = dp[1][1] = 1; for (int i = 2; i <= n; i++) { dp[i][0] = dp[i-1][1]; dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % m ...