本着 正难则反的原则。容易知道求抽到的概率很麻烦。那么我们求反就好了，也就是求失败的概率。失败就是每次都抽不到。容易知道每次失败的概率就是然后进行累乘就好了。因为模数是质数，逆元可以用费马小定理得出。 最后成功的概率就是(1-ans+mod)%mod #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; ll qpow(ll a,ll b){ ll ans=1; while(b){ if(b&1) ans=ans*a%mod; b>>=1; a...

把相连的都是白色的端点合并起来。然后我们可以处理出来每个联通块的大小。 然后进行枚举，对点的颜色为黑色的点进行枚举。讲该点变为白色，那么联通的个数就是该点本身+和他相连的联通点的个数之和，这一部分枚举即可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; struct Edge{ int to,next; }e[400005]; int h[100005],tot; void add(int x,int y){ e[tot]={y,h[x]}; h[x]=tot++; } int f[100005...

显然的特判 如果n+m<k 或者k=1 输出肯定是0 否则呢？ 先按照ababab顺序，填充满k个，那么容易得到a和b剩余的个数分别为n-(k+1)/2、m-k/2 对于a来说，也就是在(k+1)/2个已经放好的a内，在放剩下的n-(k+1)/2，允许放的个数为0.那这不就是隔板法吗，所以方案数就是同理容易得到b的方案数注意下、前面规定的放置顺序是ababab那么我们也可以按照babababa顺序放置。。方法和上述一样也是分别进行隔板法然后相乘。然后把两种的方案数相加即可。 #include<bits/stdc++.h> using namespace std; typede...

思路从小到达排序后，枚举选择AOE攻击的次数，前面的肯定直接都消灭掉了，算出来后面的剩余的减去AOE伤害更新最小值即可 #include <bits/stdc++.h> using namespace std; typedef long long ll; ll a[1<<18],b[1<<18]; ll n,x; int main() { cin>>n>>x; ll ans=1e18; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); for(int i=1;i&lt...

树状数组模板题、归并也行 树状数组，先查询树状数组内当前有多少个数比当前的数字大，然后再把数字更新上去即可。。 #include<bits/stdc++.h> using namespace std; int c[1<<17]; int n; void add(int x){ for(;x<=n;x+=x&-x) c[x]++; } int get(int x){ int ans=0; for(;x;x-=x&-x) ans+=c[x]; return ans; } int main(){ cin>>n; long long ans=0...

很简单对电脑按照内存或者速度进行从大到小排序，这样保证了有一个属性是从大到小的，然后我们只需要维护另一个属性的最大值。从大到小遍历，看当前电脑的第二个属性是不是存在电脑比他第二个属性大(从大到小 保证第一个属性降序) #include<bits/stdc++.h> using namespace std; pair<int,int> q[1<<17]; int main(){ int n;cin>>n; for(int i=1;i<=n;i++){ int x,y;cin>>x>>y; q[i]={x,y}; } s...

快速幂模板题。注意范围很大，可能会超过ull所以在加一个龟速乘防止爆掉 #include<bits/stdc++.h> using namespace std; typedef unsigned long long ll; ll mul(ll,ll,ll); ///快速幂模板 ll power(ll a,ll b,ll p) { ll ans=1; for(; b; b>>=1) { if(b&1) ans=mul(ans,a,p); a=mul(a,a,p); } return ans; } ///快速乘模板 ll mul(ll a,ll b,ll p) { ...

题目描述给出1-n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。输入描述:第一行为两个正整数n和b ，第二行为1~n 的排列。输出描述:输出一个整数，即中位数为b的连续子序列个数。 思路：只在乎和b的相对大小，而不在乎具体多少，所以我们可以把大于b的值都定为1，小于b的值都为-1，这样的话，问题转化为，求有多少个区间的和为0，并且包含数字b的位置。那么我们找出b的位置，然后从b的位置往前计算和，存入数组中，然后往右遍历计算和，看前面是不是已经存过了，存过了就加起来前面存的个数即可。注意b单独一个数字也是一个区间，所以算完b前...

思路：就是求所有子区间(区间长度大于1的子区间)的最大值减去最小值的和是多少。我们对原式子拆分一下可得其中max(l,r)表示区间l到r的最大值，min(l,r)表示区间l到r的最小值。那么问题就转化为 求所有区间长度大于1的子区间的最大值之和/最小值之和。暴力的方法就是两个for枚举起点和终点去计算，会TLE考虑单调栈，单调栈维护什么？ 维护以a[i]为区间的最大值，往左右两边去更新拓展。正着跑一次单调栈，倒着跑一次单调栈就能维护出来l和r数组。其中l[i]表示以a[i]为最大值，左边最多延伸到l[i]，r[i]表示以a[i]为最大值，右边最多延伸到r[i]然后怎么计算呢？右两种情况。① a...

题目描述小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题： 无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以现在小sun想问你，最少加几条边，可以完整的遍历整个图。 输入描述:第一行两个整数n，m代表图的点数和边数。 接下来m行，每行两个整数u，v代表u，v有边相连（无向边）输出描述:输出一行，代表最少要添加的边数。 思路：先不考虑走两步，就先考虑要走完整个图，那么整个图肯定是需要联通的，那么我们需要求出有多少个连通块，需要加的边数就是连通块个数-1...

试了几份ac代码 跑出来的答案都不对54 5 3 2 1 输出应该是5 4 3 2 14进 5进 5出 4出 3进 3出 2进 2出 1进 1出

这两题一样就放一起写了。无非就是值周的数据范围大一些。。 校门外的树可以直接暴力就ok。 值周的话。考虑把区间修改变成区间端点修改，即差分，m次结束后进行一次前缀和。然后统计没有被标记过的即可。 这里顺便提一下扩展的内容，就是说L很大，数组开不下，m的大小还是不变。 这里我们不能差分了，应该数组太大了开不下。那么我们可以反过来求，求有多少个被覆盖的，总长度减去被覆盖的就是答案。 那么问题就是怎么求被覆盖的点。 对m个段进行排序，以左端点升序。我们维护一个当前的最大的右端点r，为什么？因为区间的点可能会被多次覆盖。所以每到一个新的区间段，首先看这个区间的左端点是不是大于前面维护的最大的右端点r，...

胡队长带领HA实验的战士们玩真人CS，真人CS的地图由一些据点组成，现在胡队长已经占领了n个据点，为了方便，将他们编号为1-n，为了隐蔽，胡队长命令战士们在每个据点出挖一个坑，让战士们躲在坑里。由于需要在任意两个点之间传递信息，两个坑之间必须挖出至少一条通路，而挖沟是一件很麻烦的差事，所以胡队长希望挖出数量尽可能少的沟，使得任意两个据点之间有至少一条通路，顺便，尽可能的∑d[i][j]使最小（其中d[i][j]为据点i到j的距离）。输入描述:第一行有2个正整数n，m，m表示可供挖的沟数。接下来m行，每行3个数a,b,v，每行描述一条可供挖的沟，该沟可以使a与b连通，长度为v。输出描述:输出一行...

题目描述Nancy喜欢博弈！Johnson和Nancy得到了一个神奇的多重集合，仅包含一个正整数n，两个人轮流进行操作。一次操作可以将集合中一个数字分解为它的任意两个非1的因数，并加入集合中。他们想知道，在Johnson和Nancy绝顶聪明的情况下，如果Nancy先手进行操作，最后谁没有办法继续操作了呢？输入描述:第一行：一个整数n。输出描述:共一行：一个字符串，表示最后谁（Johnson或者Nancy）无法进行操作。 思路:其实就是看正整数n有多少个质因数，如果质因数有偶数个，那么会进行奇数次回合，每次会多增加一个数，结束时候是全都是质数。那么只要看质因数的个数的奇偶性就好了。注意一下如果n...