题意 给你一个长度为数组，每个元素只能用一次，问从中配对的对数最多有多少对。 题解 可以考虑排序后从数组中找一个最长的段，该段满足，那么答案就是，因为但大于后，答案只能是另一半。找最长段时可以用双指针法来找。 复杂度 时间复杂度 代码 #include <bits/stdc++.h> using namespace std; const int N = 1e6+5; int a[N]; int main() { int n, k, ans = 0; scanf("%d%d", &n, &k); for (int i = 1; i <= n;...

题意 给你一个长度为的序列，问这个序列中最长的不能被整除的子段的长度是多少。 题解 首先整个序列的和不能被整除那答案就是，那么接下来考虑我们可以使用双指针来扫一遍。这是根据一个点来实现的，就是几个数的和若能被整除，那么删去一个不能被整除的数，那么和也不能被整除，使用我们在遇到第一个不能被整除的点时候就可以跳出了。 复杂度 时间复杂度##代码 #include <iostream> using namespace std; const int N=1e5+5; int a[N]; int main() { int t; scanf("%d",&t); wh...

题意 给你一个和，问能否拆成个奇数或个偶数相加。若可以输出这个数。 题解 我们可以进行两次判断，若是奇数这说明可以用个和进行构造，在判断是否是偶数，若其是偶数说明可以用个和来构造。否则就说明无解，因为这是最小的解了，奇偶性可以用一个数进行转移。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { int n,k; scanf("%d%d",&n,&k); in...

题意 给你两个字符串，问是否可以通过操作将串转化为串。操作为从串中可以任取然后令，然后将用或进行替换。 题解 首先可以发现变换规律为 。那么若串为全串的话是肯定可以变为串的(除非串为全串)。由于存在，所以可以将串全变为若串中有时。所以结论就是当串中有且串中有时，是可以转化的，或两个串都是全串，但是一个是全，另一个中有时就不能了。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { string ...

题意 有一个的盒子，还有半径为的弹珠，将弹珠放入盒子中就固定位置了，牛牛和牛妹依次放置，牛妹先手，谁不能再放了那么另外一个人就胜利了，问最终谁会胜利。 题解 结论是若第一次可以放置那么牛妹必胜，否则牛牛必胜。因为盒子也可以看作一个矩形，那么第一次牛妹可以将球心放到盒子矩形的中心点。这样盒子就被分割成了两部分，那么无论牛牛放在哪里，牛妹都可以对称的放在另一边。所以牛妹是必胜的。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&...

题意 给你一个串，已知串中的是由，是由，是由分裂来的。现在给你结果串，问你原串有多少种可能。 题解 考虑全是的串其原串有哪些可能呢。这个可能数其实一个斐波那契数列，从可以看出来，可以变为和，所以。也就是也就是斐波那契数列。那么结果就是每当遇到连续的一段或或时统计其个数，总的方案数=原方案数*，这里为斐波那契数列。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; const int N=1e5+5; long long f[N]; int main() { f[0]=1; f...

题意 给你一个字符串，你必须翻转其中一个子串，问翻转后该字符串中，和交错出现的子序列最长为多少。 题解 由于翻转子串，该子串内部的和交错的长度便不会增多或减少，而其影响的只有在这个子串之前的序列和子串之后的序列，那么最多也只有增加两个，即这种情形时我们只要翻转中间的就可以增加两个。所有扩展一下对于这样的我们翻转就可以了。也就是说，字符串中存在时答案增加，存在时答案增加。 复杂度 时间复杂度 代码 #include <bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t)...

题意 给你一个个点和条边的无向图。每个节点都有一个权值，现在将图分解了，即依次删点。每次删点时，将花费与该点相连的点上权值加起来。问将整个图删完最小的花费是多少。 题解 从贪心的角度来做是可以的。由于删点等于把每条边都给删了，其实也可以从删边的角度来看。删点肯定先删权值大的。那么针对与每条边来说，其两端的节点肯定有一个是有贡献的，那么一定是选择小的较优。我们结论就变得很简单了，我们遍历每条边，最后的最小花费就是每条边两端权值较小的那个。 复杂度 时间复杂度 代码 #include <bits/stdc++.h> using namespace std; const int N=1e...

题意 给你个小球和个盒子，把小球放入盒子中，要求每个盒子中至少有一个小球，并且任意两个相邻的盒子中的小球数量相差不超过。问编号为的盒子中最多可以放多少个小球。 题解 我们可以去二分第个盒子中小球的数量，由于可以贪心的去做，让相邻盒子中的小球比第个盒子中的小球少一，这样就可以推出其他和盒子中小球的数量。若当前这样发现所有盒子中的小球数量之和大于，则说明二分大了，反之说明二分小了。这样就能得到最大的值。 复杂度 时间复杂度 代码 #include <bits/stdc++.h> using namespace std; int n,m,k; bool f(int x) { int su...

题意 给你和，牛牛想知道的结果是多少。 题解 可以发现每项公式的分子都含有，那么对取模都可以得到，那么我们可以打表尝试一下，会发现。对于不同的来说结果都是，但是在为的倍数时答案就为。所以结果就非常的简单。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { int n,p; scanf("%d%d",&n,&p); if(n%(p-1)==0) printf(...

题意 给你一个长度为且各个元素不同的序列，问将序列，划分为连续的段，对每段内部进行从小到大排序，然后将各个段按顺序拼接起来，求让整体是从小到大有序的。 题解 由于序列中的每个数都不同，可以将元素映射到。排序完之后就是的形式。那么也就是的值是多少，那么他最后的下标也是。从这个性质上来看，我们对于每个数字可以将其现在的位置与排序后所在的位置看成一段区间，也就是说每个数字可以有一段区间。若两段区间之间有交叉也就是排序时两个区间必须合并。所以我们可以将区间按左端点进行排序之后从头到尾合并一下，最后剩下几个不重叠的区间也就是要找的最大的。 复杂度 时间复杂度 代码 #include<bits/st...

题意 找一个长度为的最小整数，其可以被整。 题解 也就是说要找一个长度为的整数能被整除。可以转化为的问题，那我们可以看的结果是多少，令，我们在加上，就是位长度下最小能被整除的整数了，这样做复杂度为，还有可以发现，是存在循环节的，也就是说也存在循环节。我们通过打表发现的顺序为。所以我们就可以直接输出了。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; char str[7][3]= {"05", "08", "17", "02", &qu...

题意 给你一棵树每个节点上的度数，以及该节点与其相连的其他节点之间的异或和(与该节点相连的点的异或和,除该节点之外)，让你利用这些信息恢复出这棵树，输出这棵树的高度。 题解 首先可以发现的是，度数为一的点都是叶子节点。那么我们可以从叶子节点入手，可以发现叶子节点的异或值就是与该节点连接的节点编号。然后我们可以将该叶子节点删除，然后将与其相连的点的度数减一并且异或和异或上叶子节点的编号。重复这个操作再找到度数为的点，这样就可以恢复出整棵树，我们在删点的同时就可以知道当前叶子节点和什么点连接在一起也就获得了边的信息。利用边的信息就可以得到树的高度了。 复杂度 时间复杂度 代码 #include&l...

题意 求大于等于的第一个质数的质数，质数的质数定义为，将质数按顺序排列，取出下标为质数的质数，即有序列。 题解 根据数据范围，所以我们可以先多筛一些质数。将筛出来的质数存到数组中，然后处理质数的质数，可以存到数组中。 for(int i=1;prime[i]<cnt;i++) a[num++]=prime[prime[i]];这样由于询问次数较多，查询需要级别才可以，所以我们可以用二分来查询第一个大于等于的质数的质数，c++可以使用。 复杂度 查询 代码 #include<bits/stdc++.h> using namespace std; const int N=3e6+...