Pandauncle-CSDN博客

原创 jia庭问题(family)

时间限制: 1000 ms 内存限制: 65536 KB 提交数: 153 通过数: 75 【题目描述】有n个人，编号为1,2,……n，另外还知道存在K个关系。一个关系的表达为二元组（α，β）形式，表示α，β为同一家庭的成员。当n，k和k个关系给出之后，求出其中共有多少个家庭、最大的家庭中有多少人？例如：n＝6，k＝3，三个关系为（1,2），(1,3)，(

2020-08-13 11:24:38 1505

原创 2019山东省赛Median

题目和这个几乎一样：珍珠比大小加一个小判断就行了。#include<bits/stdc++.h>using namespace std;typedef long long int ll;const int N=100+30;int a[N][N],b[N][N],num1[N],num2[N];void init(){ memset(a,0,sizeof(a))...

2019-05-14 09:39:31 355

题目大意：给定一个0到ｎ-1的数字组成的序列，它的逆序数，然后把第一个数字放到末尾，得到一个新的序列，再求逆序数，再把新序列的第一个数字放到末尾，一直这样做，求所有这些序列的逆序数的最小值。思路：首先用权值线段树(或树状数组)求出当前序列的逆序对数。然后把第一个数放到最后一个，计算他的贡献：即他当前能组成的逆序数对为后面比他小的数(a[i]个),把他放入最后时，他贡献的逆序对数为：(n-a[...

2018-11-30 20:45:57 371

原创 HDU6390多校GuGuFishtion

题意：就是要求那个公式和。首先：对一个数中的一个素因子进行分析贡献。设a=p^a1， b=p^a2;则phi(ab)=(p-1)*p^(a1+a2-1);phi(a)=(p-1)*p^(a1-1);phi(b)=(p-1)*p^(a2-1);当a1!=0,a2!=0时；phi(ab)/(phi(a)*phi(b))=p/(p-1)当a1=0时；phi(ab)/(phi(a)*...

2018-10-23 20:14:58 195

原创 2014ACM/ICPC亚洲区西安站 F题 color(容斥原理)

题目链接题意：n朵花排成一行，我们有m种颜色，可以给这些花涂色，保证相邻的花的颜色不同问，最后恰好使用了k种颜色的方案数。Orz博主题解//(m,k)*sigma((-1)^(k-i)*(k,i)*i*(i-1)^(n-1))#include<bits/stdc++.h>using namespace std;typedef long long int ll;con...

2018-10-15 21:48:13 385

原创数论之神

打表找规律。对于每个n当i>=sqrt(n)时可以分为根号n块,小于n的，每个独立为一块。#include<bits/stdc++.h>using namespace std;typedef long long ll;int main(){ int T; scanf("%d",&T); ll n,k; while(T--) ...

2018-10-08 19:32:45 275

原创牛客网wannafly因子

质因数分解+阶乘质因数分解，取p质因数分解的指数和阶乘质因数分解指数比值的最小值即可。#include<bits/stdc++.h>using namespace std;typedef long long int ll;#define int long long intconst ll N=100000+10;const int INF=(1LL<<63)-1...

2018-09-30 21:27:48 210

原创 D. Notepad

题意：求(b-1)b^(n-1)%mod 2<=b<=10(106),1<=n<=10(106),1<=c<=10^9;//(b-1)*b^(n-1)%mod//2<=b<=10^(10^6),1<=n<=10^(10^6),1<=c<=10^9;#include<bits/stdc++.h>

2018-09-25 19:42:50 182

原创 BZOJ2956: 模积和(分块大法好)

推完公式分块即可。#include<cstdio>#include<algorithm>#include<cmath>#include<set>#include<map>#include<vector>#define inf 1000000000#define mod 19940417#define...

2018-09-03 19:34:34 233

原创 HDU6434Problem I. Count

聚聚写的很好至于为什么i为奇数时欧拉函数要除以2,因为a只能为奇数，偶数占了一半。#include<bits/stdc++.h>using namespace std;typedef long long int ll;const int N=20000000+10;ll phi[N],prime[N];bool vis[N];ll sum[N];void get_...

2018-08-30 21:27:22 258

原创 HDU6395Sequence(矩阵快速幂+分块)

思路：这道题的范围很大所以没法使用直接跑循环地推的方法求第n项，很容易就能分析出应该转化成矩阵的方法，然后使用矩阵快速密来求解第n项的值。题目给的递推式是一个非线性的关系，所以不能直接构造出一个矩阵。当⌊P/n⌋在某一块内为确定的常数时，我们就可以构造出矩阵，进行矩阵快速幂。而某一段内的最大个数为：j=n/(n/i),j是满足n/t=i最大的t。构造的矩阵为： #includ...

2018-08-14 21:27:07 220

原创洛谷P1661扩散(二分+并查集)

首先我们先二分答案，然后用并查集记录有多少个联通块。如果两个联通块成为一个联通块，则他们的哈密顿距离小于扩散时间的一半。因此可以二分答案，检查是否等于一个联通块就行了。#include<stdio.h>#include<iostream>#include<queue>#include<algorithm>using namespace...

2018-08-12 11:40:04 604 3

原创 HDU6373Pinball(物理题)

思路：高中经典例题。分解加速度和速度就好了。#include<bits/stdc++.h>using namespace std;const double g=9.8;const int MAXN = 1000+5;int main(){ int i,j,k,n,m; int _; cin>>_; double a,b,x,...

2018-08-09 08:33:20 278

原创 HDU6330Problem L. Visual Cube(模拟)

模拟是真的恶心。#include<bits/stdc++.h>using namespace std;typedef long long int ll;const int N=100+10;char s[N][N];int main(){ int t; scanf("%d",&t); while(t--) { ...

2018-08-03 22:40:25 209

原创 HDU6319Problem A. Ascending Rating(单调队列)

题意：给定一个序列a[1…n]，对于每个长度为m的连续子区间，求出区间a的最大值以及从左往右扫描该区间时a的最大值的变化次数。分析：按照r从m到n的顺序很难解决这个问题。考虑按照r从n到m的顺序倒着求出每个区间的答案。按照滑动窗口最大值的经典方法维护a的单调队列，那么队列中的元素个数就是最大值的变化次数。#include<stdio.h>#include&...

2018-08-03 16:37:29 164

原创 POJ2823Sliding Window(单调队列)

题意：题意很简单，给出一个有n个元素的序列和一个k，让你求出从左到右每k个区间的最大值和最小值。思路：单调队列的入门题目。若从左到右求出每个区间的最大值，则队列里的数值是递减的，下标是递增的。若从左到右求出每个区间的最小值，则队列里的数值是递增的，下标是递增的。只需要维护队列里的数值则就可以求出每个区间的最大最下值。#include<stdio.h>#...

2018-08-03 14:47:14 175

原创 POJ3067Japan(树状数组)

题意：左边有Ｎ个点，右边有M个点，有K个连线，问相交点数有多少个。思路：左边的点从小到大排序，然后和右边的点如果相连的点在该点的下方有相连的线段则必与该线段相交。就转换为求区间i—m连接点的个数和问题。直接树状数组。#include <cstdio>#include <cstdlib>#include <cstring>#inc...

2018-07-29 19:42:58 207

原创 HDU6318Swaps and Inversions

注意交换次数等于逆序对数。#include<bits/stdc++.h>using namespace std;typedef long long int ll;const int N=100000+10;const int MAX=100000;int bit[N];int a[N];struct node{ int v,id; bool op...

2018-07-29 16:35:01 220

原创 POJ2299Ultra-QuickSort(树状数组求逆序对)

求逆序对，直接用树状数组求逆序对，注意离散化。#include<stdio.h>#include<istream>#include<algorithm>#include<string.h>#include<string>#include<cmath>#include<queue>using nam

2018-07-29 13:54:30 216

原创 POJ1990MooFest(树状数组)

题意：一群牛参加完牛的节日后都有了不同程度的耳聋，第i头牛听见别的牛声音，别的牛音量必须大于v[i]，当两头牛i，j交流的时候，交流的最小声音为max{v[i],v[j]}*他们之间的距离。现在有n头牛，求他们之间两两交流最少要的音量和。思路：首先暴力肯定不是不行的O(n^2)。树状数组的作用是能够快速求出某段区间的和O(logn)，根据这点。我们可以根据牛可以听见声音的音量从...

2018-07-28 22:25:43 199

原创 POJ2481Cows(树状数组)

题意：计算每个区间有多少个包含他的区间。本题和POJ 2352的stras差不多，把区间看出二维坐标上的点，这可以看出在该点左上方的点数及为包含的区间数。因此可以按照y从大到小的顺序排列，y相同的则按照x从小到大排列，就可以把二维的点变成用树状数组维护x就行了。#include<stdio.h>#include<iostream>#include...

2018-07-28 11:58:25 205

原创 POJ2352树状数组入门

题目大意：在坐标上有n个星星，如果某个星星坐标为(x, y), 它的左下位置为：(x0,y0)，x0<=x 且y0<=y。如果左下位置有a个星星，就表示这个星星属于level ａ。按照y递增，如果y相同则x递增的顺序给出n个星星，求出所有level水平的数量。因为题意给出ｙ按照递增的顺序给出，所以只要依次判断小于等于ｘ的数量有多少个及为level水平。因此用树状数组来维...

2018-07-28 11:49:30 188

原创数列分块入门 9

题目链接 Orz #include<stdio.h>#include<set>#include<vector>#include<queue>#include<iostream>#include<algorithm>#include<cmath>#include<map&gt

2018-06-20 21:09:43 415

原创数列分块入门 8

题目链接给出一个长为n的数列，以及n个操作，操作涉及区间询问等于一个数c的元素，并将这个区间的所有元素改为c。我们用一个标记记录这个块中的元素是不是都一样，一样的话进行标记，修改时在该块中的直接修改标记就好了，不在该块内的进行暴力更改。#include<set>#include<map>#include<algorithm>#include...

2018-06-19 19:44:43 612 1

原创数列分块入门 7

新技能：乘法标记题目链接#include<map>#include<set>#include<cmath>#include<stack>#include<queue>#include<cstdio>#include<vector>#include<cstring&gt

2018-06-18 21:05:13 356

原创数列分块入门6

题目链接当单块过大时，进行重新建块#include&lt;stdio.h&gt;#include&lt;set&gt;#include&lt;vector&gt;#include&lt;algorithm&gt;#include&lt;queue&gt;#include&lt;iostream&gt;

2018-06-18 18:51:21 304

原创数列分块入门 5

数据最大范围是2^31,所以最多开5次方就会话成&lt;=1的数。用一个数组进行标记块内的元素是不是全部都小于等于1。#include&lt;stdio.h&gt;#include&lt;cmath&gt;#include&lt;set&gt;#include&lt;vector&gt;#include&lt;algorithm&am

2018-06-16 20:57:26 294

原创数列分块入门 4

题目链接此题和前面的没有什么区别，只需要去维护整块内的和就行，不知整块的去暴力加和。#include<stdio.h>#include<iostream>#include<queue>#include<algorithm>#include<cmath>#include<string.h>#include...

2018-06-16 19:02:40 250

原创数列分块入门 3

题目链接根据数列分块入门2的思想做。可能用其他的STL比较方便，我这里还是用的vector。#include&lt;stdio.h&gt;#include&lt;iostream&gt;#include&lt;algorithm&gt;#include&lt;queue&gt;#include&lt;cmath&gt;#incl

2018-06-16 15:27:16 383 1

原创数列分块入门2

题目链接给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 xxx 的元素个数。根据数列分块入门1的思想，把n个数分为根号n块，不完整块的去暴力求和和查找，完整块用加法标进行标记，查找排序后进行二分查找。#include<stdio.h>#include<algorithm>#include<iostream>...

2018-06-15 19:50:51 838 2

原创数列分块入门 1

黄老师的博客题目传送门有n个元素，如果我们把每m个元素分成一块，共有n/m块，每次区间加的操作会涉及O(n/m)个整块，以及区间两侧两个不完整的块中至多2m个元素。我们给每个块设置一个加法标记（就是记录这个块中元素一起加了多少），每次操作对每个整块直接O(1)标记，而不完整的块由于元素比较少，暴力修改元素的值。每次询问时返回元素的值加上其所在块的加法标记这样总复杂度是O（n*(...

2018-06-14 19:34:14 182

原创 BZOJ1013: [JSOI2008]球形空间产生器sphere

1013: [JSOI2008]球形空间产生器sphereTime Limit: 1 Sec Memory Limit: 162 MB Submit: 6875 Solved: 3617 [Submit][Status][Discuss] Description　　有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在，你被困在了这个n维球体中，你只知道球面上n+1个点...

2018-06-09 15:20:28 162

原创 HDU5969最大的位或

Problem Description B君和G君聊天的时候想到了如下的问题。给定自然数l和r ,选取2个整数x,y满足l <= x <= y <= r ,使得x|y最大。其中|表示按位或，即C、 C++、 Java中的|运算。Input 包含至多10001组测试数据。第一行有一个正整数，表示数据的组数。接下来每一行表示一组数据，包含两个整数l,r。保...

2018-06-08 18:56:45 183

转载 P1080 国王游戏

博主讲的好很好 https://blog.csdn.net/Rlt1296/article/details/52793197#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>using namespace std;int n,pai[...

2018-05-30 19:14:38 583

原创浙江省省赛 Now Loading!!!

根据题意可以得出分母的范围为：1-30，对于每个a[j]是p^i到p^(i+1)范围内分母都为i+1，对于每个pi最多可以把a[i]数列分为30组，所以枚举每个pi在a[i]中进行二分查找。然后用前缀和处理下a[i]/j。#include<bits/stdc++.h>using namespace std;typedef long long int ll;const int N=500005+

2018-05-06 22:32:53 237

原创 B. Jzzhu and Sequences

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=100000+10;const ll MOD =1000000007 ;struct Mar{ ll mat[2][2]; Mar operator *(const Mar &m )const {

2018-05-05 21:34:53 220

原创 BZOJ 2818 GCD

思路：因为要求GCD（x,y)=m，m为素数，有多少有序对。则可以转化为求GCD（a,b)=1，x=a*m，y=b*m，有多少有序对。假设x<=y,则a<=b，因为1<=x<=y<=n，则b<=(n/m).通过枚举素数m，求小于b，与b互斥的有多少个。通过处理欧拉函数的前缀和，每次会多求出一个a=b=1，GCD（a,b)=1的解，又因为是有序对，所以结果为sum[b]*2-1.#include<bi

2018-04-19 20:11:33 184

原创 2017 杭州CCPC HDU 6265 Master of Phi

首先要求的是一个积性函数。然后根据积性函数的笛利克雷卷积还是积性函数。具体推导过程： #include<bits/stdc++.h>using namespace std;typedef long long int ll;const int N=10000+10;#define MOD 998244353ll power(ll a,ll b){ ll res=1; wh

2018-04-18 20:57:28 1091

原创杭州CCPC Master of GCD

差分#include<bits/stdc++.h>using namespace std;typedef long long int LL;const int N=100000+10;#define Mod 998244353#define INF 1<<31-1LL c2[N],c3[N];LL ans2[N],ans3[N];LL quick_power(LL a,LL b){

2018-04-16 18:15:03 470

原创欧拉函数的线性筛法

欧拉函数：对正整数n，欧拉函数是小于等于n的数中与n互质的数的数目。欧拉函数又称为φ函数。下面是欧拉函数的一些性质：如果n为某一个素数p，则φ(p)=p-1；如果n为某一个素数p的幂次pap^a，则φ(pap^a)=(p-1)*p(a−1)p^(a-1) ；如果n为任意两个互质的数a,b的积，则：φ(a*b)=φ(a)*φ(b)；如果p为质数。如果i mod p =0，那么φ

2018-03-15 18:29:28 496

空空如也

空空如也