组合数学+快速幂 方法一：递推+打表 首先我第一眼看到的时候就隐隐约约的感觉到了一丝熟悉的味道，这不就是高中数学的组合思想嘛，然后就快速的敲了一遍，但是却忘记了组合数学的规律，组合数学和杨辉三角紧密的联系在一起！！他的每一项系数正好是杨慧三角每一行的值，所以我们只要把杨辉三角打印出来，然后就可以快速的求解系数了，并且杨辉三角是对称的，所以最后面求解的时候n，m是不影响的，这也验证了组合数学的思想。另外对于其他的，只需要一个快速幂就可以解决了 #include <bits/stdc++.h> using namespace std; const int maxn = 1010; co...

水题 虽然这是个水题，但是还是有一些地方要注意一下，题目说了不能超过ULL的范围，我们都知道求解两个数的最小公倍数就是用a*b/gcd（a，b）。。 但是 ！！！ 这里不能超过题目给的范围，所以我们就要先相除再相乘，这样处理就不会越界了 第一种解法——利用STL内置函数 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e7 + 10; int prime[maxn], sum[maxn]; int main() { ll a, b; while...

数论+埃氏筛+前缀和 题目分析：这道题目的难度只有一颗星，但是题目给的数据范围达到了1e7之多，暴力的时间复杂度达到了O（n^2），显然是不行的，所以这个题目需要优化+转化，我们不能被题目的表现所迷惑，题目里面有gcd，但是如果去求gcd的话时间复杂度肯定很高，所以这里用了十分巧妙地方法 1.首先我们用埃氏筛去筛选素数，这是一种十分强大的方法，每次都筛去素数的倍数2.然后对其求前缀和，我们把素数的个数求出来，方法后面求素数对3.接下来就是题目的核心思想，我们要求一共有所少个素数对，首先素数对中的素数是不能相同的，其次我们枚举每一个公约数，因为素数对的倍数也是符合题目要求，这样只需要求（2，n/...

并查集+01背包（滚动数组） PS：刚开始并没有想到这是一个并查集+01背包，我就以为是一个简单的并查集然后贪心就完事了，但是当时纠结的是，两边都可以贪心（精力和利益值），当时没多想随便找一个贪心然后代码过了样例，交上去的时候却wa了，这时候就开始认真分析问题了。求解最大值有两种方式，一个是二分，一个是动态规划，这里毫无疑问是动态规划，所有的条件里面选一个最大的，这里我们用滚动数组极大的简化了代码，也使程序看起来通俗易懂，具体注释请看代码 #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10;...

贪心 这个题目我吐了，居然用long long才能过，简单排序+贪心，我们按照从小到大排序就行，这样下一步操作只是将当前最小的数去掉，这样就能保持最大数了 很简单的题目啦~ #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; typedef long long ll; ll a[maxn]; int main() { ll n, sum, ans; while (~scanf("%d", &n)) { sum = 0, ans = 0; ...

并查集模板题 这与前一个题目任意点几乎一样，只需要改一下main函数里面的一小部分代码就行我们把联通之间的点放入一个集合，最后只需要去找根节点就知道有多少个集合，我们需要集合数减一的边就可以把这些散落的集合联系起来 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int pre[maxn]; int find(int x) //路径压缩 { if (x != pre[x]) pre[x] = find(pre[x]); return pre[x]; } ...

并查集 1.首先定义一个结构体数组来存储点的信息2.路径压缩，初始化都是必要的数据结构，然后我们只需要遍历一下点的集合，如果两个点的横坐标或者众坐标相等，那么我们就把这两个点放入一个集合中3.最后我们只需要统计一下有几个集合就知道解了，解的个数就是集合的个数减一，我们可以这么想如果有两个不相交的集合，我们只需要加一个点就可以让两个集合联系起来 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; struct node { int xi, yi; } w[maxn]; int pre...

方法一：拓展欧几里得算法 模板题 需要满足gcd(a,b)能整除n就行 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; typedef long long ll; ll exgcd(ll a, ll b, ll &x, ll &y)//求一个特解 { if (b == 0) { x = 1, y = 0; return a; } ll d = exgcd(b, a % b, y, x); y -= ...

简单模拟题 方法一 首先按照题目要求我们先对总数进行降序排列，如果总数相同那么就把先出现的id排在其前面 其次我们把每个id所得到的分数存进一个数组里面，然后进行排序，最后我们只要输出第一个就行 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; struct node { int id, r, wh, b, sum; bool operator<(const node x) { if (sum != x.sum) return sum...

找规律题 /*1.如果n为偶数，不论a,b为多少都可以得到全为一面的情况2.如果n为奇数，如果0的个数是偶数可以得到全为1，如果0的个数是奇数可以得到全为0；*/ #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; char a[maxn], b[maxn]; typedef long long ll; int visa[maxn]; int main() { int t, n, a, b; scanf("%d", &t); while (t--) ...

快速幂模板题 主要思路是参考题解来的 快速幂题目思想 1.利用二进制位运算实现快速幂求解2.如果二进制位上是0就跳过发，否则就运算 具体思想参考代码就行 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 10; const int mod = 1e9 + 7; ll fastpow(ll a, ll b) { ll res = 1; //用res返回结果 while (b) { if (b & 1) ...

贪心+前缀和 熟悉的题目，这不就是雨巨直播课讲的接水问题吗，直接贪心求前缀和就ok 方法一： 1.对于每个人等待的时间求和我们可以知道对于t1已经求和n-1次，t2求和n-2次，所以按照贪心的思想我们就把等待时间小的排在前面2.对于排好序的序列，我们只需要求其前缀和然后相加求平均数就可以啦，由于题目要求我们需要保留两位有效数字 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int a[maxn]; int main() { int t, n; scanf("%d", ...

下面我将用两种题解解答这个题目 简单模拟题 方法一： 1.因为开始就是大写锁定，所以如果第一个字母是小写那么就已经按了一次转换键2.接着模拟一遍，从头开始，如果当前是小写字母下一个是大写字母那么就++，如果当前是大写字母下一个是小写字母那么也需要++3.最后得出来的就是答案 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; char s[maxn]; int main() { while (~scanf("%s", s)) { int ans = 0; ...

签到题，模拟即可 话不说说直接上代码 #include<iostream> #include<cstdio> using namespace std; int main() { int t; scanf("%d",&t); while(t --) { int n; scanf("%d",&n); long long sum=0; while(n --) { int a,b; scanf("%d %...