- 博客(38)
- 收藏
- 关注
RSS订阅原创 POJ 3690
题意给定N,M,T,P,QN,M,T,P,QN,M,T,P,Q对于只包含000和∗*∗的二维字符数组，给定一个N∗MN*MN∗M的矩阵，有TTT次询问，每次询问一个P∗QP*QP∗Q的矩阵是否是其子矩阵题解可以用二维哈希来做。有关知识参考二维哈希这道题目卡常情况非常严重，我的AC代码跑了2766ms/3000ms如果有更好的解法请告知另外：我一开始是将所有主矩阵中所有p∗qp*qp...
2020-03-09 10:15:09
124
原创 博弈论
博弈论巴什博弈（Bash Game）只有一堆nnn个物品，两个人轮流从这堆物品中取，规定每次至少取一个，最多取mmm个，最后取光者得胜。如果n=(m+1)r+s,rn=(m+1)r+s,rn=(m+1)r+s,r为任意自然数，s≤ms\le ms≤m,那么先取者拿sss个，后取者拿k(≤m)k(\le m)k(≤m)个，那么先取者再拿走m+1−km+1-km+1−k个，剩下(m+1)(r−1...
2019-10-17 20:46:29
255
原创 多项式
多项式前置知识多项式的度：多项式f(x)f(x)f(x)的最高次项的次数为该多项式的度，记为deg fdeg\ fdeg f。多项式的逆元：对于多项式f(x)f(x)f(x)，若存在g(x)g(x)g(x)满足：f(x)g(x)≡1(modxn)f(x)g(x)\equiv 1\pmod{x^n}f(x)g(x)≡1(modxn)deg g≤deg&nb...
2019-10-17 00:06:58
2218
原创 线性代数
线性代数矩阵矩阵的逆AAA的逆矩阵PPP是使得A∗P=IA*P=IA∗P=I的矩阵。逆矩阵可以用高斯消元的方式来求。矩阵乘法Ci,j=∑k=1MAi,kBk,jC_{i,j}=\sum\limits_{k=1}^{M}A_{i,k}B_{k,j}Ci,j=k=1∑MAi,kBk,j常用矩阵快速幂来解决线性递推式。优化：（降常数）// 以下文的参考代码为例inline m...
2019-10-14 19:07:03
175
原创 数论与数论函数
数论与数论函数整除及其性质素数1、素数的个数：素数计数函数：小于等于xxx的素数的个数，用π(x)\pi(x)π(x)表示，随着xxx的增大，有近似结论：π(x)∼xln(x)\pi(x)\sim\frac{x}{\ln(x)}π(x)∼ln(x)x2、素数判定：暴力判定：O(n)O(\sqrt {n})O(n)素性测试：O(klog3n)O(k \log^3n)O(klog...
2019-10-04 23:07:18
819
原创 2019牛客多校第一场C
2019牛客多校第一场C题题目大意：给定nnn维空间中的一个点A(a1m,a2m,…,anm)A(\frac{a_1}{m},\frac{a_2}{m},…,\frac{a_n}{m})A(ma1,ma2,…,man),aia_iai和mmm都是整数。现在，我们需要确定一个点P=(p1,p2,…,pn)P=(p_1,p_2,…,p_n)P=(p1,p2,…,pn)满足：1...
2019-09-29 15:01:43
96
原创 The Preliminary Contest for ICPC Asia Nanjing 2019 super_log
The Preliminary Contest for ICPC Asia Nanjing 2019B题：super_log求aaa…a%ma^{a^{a^{…^a}}}\%maaa…a%m（b次a）考虑欧拉降幂：ab≡ab%φ(p)+φ(p)modp(b≥φ(p))a^b\equiv a^{b\%\varphi(p)+\varphi(p)}mod p(b\geq \varphi(p))a...
2019-09-05 10:21:16
78
原创 The Preliminary Contest for ICPC Asia Nanjing 2019 E K Sum
The Preliminary Contest for ICPC Asia Nanjing 2019E题 K Sum题意：定义fn(k)=∑l1=1n∑l2=1n…∑lk=1n(gcd(l1,l2,…,lk))2f_n(k)=\sum\limits_{l_1=1}^{n}\sum\limits_{l_2=1}^{n}…\sum\limits_{l_k=1}^{n}(gcd(l_1,l_2,…...
2019-09-04 21:10:21
118
原创 HDU 6706
2019CCPC网络赛1005问题求解：∑i=1n∑j=1igcd(ia−ja,ib−jb)[gcd(i,j)=1]%(mod),mod=1e9+7,a和b互素，且a≥b\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}gcd(i^a-j^a,i^b-j^b)[gcd(i,j)=1]\%(mod),mod=1e9+7,a和b互素，且a\geq bi=1∑nj...
2019-08-28 16:58:07
196
原创 HDU6703
2019CCPC网络选拨赛1002这里要用到权值线段树，因为题目保证了ai属于[1,n]，且不重复。这里要用到权值线段树，因为题目保证了a_i属于[1,n]，且不重复。这里要用到权值线段树，因为题目保证了ai属于[1,n]，且不重复。那么用权值为下标，线段树的值是i,即原序列的下标。那么用权值为下标，线段树的值是i,即原序列的下标。那么用权值为下标，线段树的值是i,即原序列的下标。题目可以转...
2019-08-26 22:26:00
315
原创 HDU6441
由费马大定理，an+bn=cn当n>2时无正整数解a^n+b^n=c^n当n>2时无正整数解an+bn=cn当n>2时无正整数解当n=1时，随便取b的值，c=a+b就行了当n=1时，随便取b的值，c=a+b就行了当n=1时，随便取b的值，c=a+b就行了当n=2时，a,b,c为勾股数当n=2时，a,b,c为勾股数当n=2时，a,b,c为勾股数当a为大于1的奇...
2019-08-03 10:05:49
149
原创 CF1182E
这题我的做法与网上部分题解不太相同，常数稍微大了一点，但是不影响AC，依旧30ms跑完。当时打这场CF时，取了一个对数，lnfx=(2x−6)lnc+lnfx−1+lnfx−2+lnfx−3lnf_x=(2x-6)lnc+lnf_{x-1}+lnf_{x-2}+lnf_{x-3}lnfx=(2x−6)lnc+lnfx−1+lnfx−2+lnfx−3;后三项不用说，直接矩阵快速幂就行了，但...
2019-08-02 00:45:06
140
原创 CF510D
说是dp，其实是枚举了所有的可能性，mp[i]表示了gcd=i时最小花费，初始时只有mp[0]=0;每当加入一个元素时，将其与已有的元素取gcd，维护mp[gcd]的最小值，(mp=0时表示未出现过这个gcd)；能过的原因是因为300个数产生的gcd是有限的。。。。#include<iostream>#include<map>#define ll long long...
2019-08-01 22:53:09
138
原创 HDU2973
威尔逊定理：(p-1)!≡\equiv≡-1(mod p)当且仅当p为素数时成立；当3n+7为素数时,(3n+6)!+1可记为m*(3n+7),⌈(3n+6)!3n+7 ⌉\lceil \frac{(3n+6)!}{3n+7}\ \rceil⌈3n+7(3n+6)! ⌉的结果为m-1；此时SnS_{n}Sn=Sn−1S_{n-1}Sn−1+1;当3n+7不是素数时，...
2019-08-01 21:38:04
154
原创 POJ3304
n很小，只有100.可以枚举任意两条线段的两个端点，叉积判断是否和其他所有线段相交。时间复杂度O(n3)O(n^{3})O(n3)证明：若有直线l与所有线段相交，则可保持l和所有线段相交，左右平移l到和某一个线段交于端点时无法在移动了，然后绕这个交点旋转，到转不动了，将会与另一线段交于一端点。#include<cstdio>#include<iostream> #i...
2019-08-01 21:07:21
309
原创 匈牙利算法详解
//匈牙利算法，邻接表建图#include <iostream>#include <cstdio> #include <queue>#include <cstring>using namespace std;const int maxn = ;//max(n,m),n为左图节点数,m为右图节点数int head[maxn],ver[m...
2019-04-02 18:23:09
245
原创 CH2101 可达性统计
给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。N,M≤30000。输入格式第一行两个整数N,M，接下来M行每行两个整数x,y，表示从x到y的一条有向边。输出格式共N行，表示每个点能够到达的点的数量。题解：从点x出发能够到达的点构成的集合是f(x),有：f(x)={x}U(U存在有向边(x,y) f(y))，从x出发能够到达的点，是从“x的各个后继点y”出发...
2019-03-29 19:47:47
351
原创 POJ 3349
描述You may have heard that no two snowflakes are alike. Your task is to write a program to determine whether this is really true. Your program will read information about a collection of snowflakes, a...
2019-03-13 15:46:48
74
原创 CH1301 邻值查找
给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 AiA_iAi，求：min(1≤j&lt;i)∣Ai−Aj∣min(1≤j&lt;i) |A_i-A_j|min(1≤j<i)∣Ai−Aj∣以及令上式取到最小值的 j（记为 PiP_iPi）。若最小值点不唯一，则选择使 AjA_jAj 较小的那个。题解：可以借助set来实现，se...
2019-03-13 13:50:35
284
原创 Team Queue POJ2259
题目描述Queues and Priority Queues are data structures which are known to most computer scientists. The Team Queue, however, is not so well known, though it occurs often in everyday life. At lunch time t...
2019-03-12 17:08:54
105
原创 栈
CH1101 火车进栈有n列火车按1到n的顺序从东方左转进站，这个车站是南北方向的，它虽然无限长，只可惜是一个死胡同，而且站台只有一条股道，火车只能倒着从西方出去，而且每列火车必须进站，先进后出。现在请你按《字典序》输出前20种可能的出栈方案。题解：可以按照排列组合的顺序推导，check一下每种排列对不对，出栈顺序必须满足的要求是当一个较大的数出栈后，比它小的数出栈顺序必须是递减的。#inc...
2019-03-12 13:18:26
154
原创 高精度乘法---deque实现
//需要说明的是deque中每一个空间存储的是一个小于1e9的数字，//输出的时候记得补齐前导零const int HEX=1e9;deque<int> operator * (const deque<int> &op1,int op2){ deque<int> res; int carry = 0; ll tmp; for(ll i = ...
2019-03-12 10:54:46
97
原创 POJ3614 Sunscreen
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=2510;struct COW{ int minSPF; int maxSPF; bool operator <(const COW &b)const{ return minSPF>b.min...
2019-03-06 15:59:56
102
原创 奇数码问题CH0503
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=500*500+10;int n;int a[maxn],b[maxn];ll cnt1,cnt2,cnt;void merge_sort(int l,int r){ if(r-l>0){ ...
2019-03-06 10:49:36
221
原创 Ultra-QuickSort POJ2299 求逆序对个数
给定长度为n(<=5e5)的序列a，如果只能交换相邻的两个数，求至少需要多少次交换才能把a从小到大排序。题解：明显，求个逆序对就完事了，归并排序可求逆序对。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=5e5+10;int a[N],b[N];ll cnt;v...
2019-03-06 00:27:57
275
原创 七夕祭 CH0502/BZOJ3032
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5+10;ll ans=0,sum_row,sum_column;int N,M,T,is_row=0,is_column=0;int X[maxn],Y[maxn];int A[maxn],B[maxn],...
2019-03-06 00:02:46
159
原创 仓库选址CH0501
在一条数轴上有N家商店，坐标分别为A[1]~A[N].现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5+10;ll...
2019-03-05 22:52:00
442
原创 ACM学习记录--二分
二分的实现方法多种多样，但是细节之处需要仔细考虑，特别是对于终止边界、左右区间取舍的开闭的问题。例题：Best Cow Fences (POJ2018)给定正整数数列A，求一个平均数最大的、长度不小于L的（连续的）子段。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn...
2019-03-05 22:24:42
192
原创 ACM学习记录--前缀和与差分
前缀和前缀和S[i]=A[1]+A[2]+……+A[i];可以用A[i]=S[i]-S[i-1]来还原;还有二维的前缀和S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j];这个公式可以用容斥原理推得。差分对于一个给定的数列A，它的差分数列B定义为：B[1]=A[1],B[i]=A[i]-A[i-1] (2&lt;=i&lt;...
2019-03-04 20:39:57
735
原创 ACM学习记录--递推与递归
一、递推与递归的简单应用1、多项式型枚举：一般遍历方式：循环(for)、递推。状态空间规模：nk，几重循环k就是几。此种枚举十分的常见。2、指数型枚举：一般遍历方式：递归、位运算。状态空间规模：kn。例如：从1~n（n&lt;20）个整数中随机选取任意个，输出所有可能的方案。#include&lt;iostream&gt; #include&lt;vector&gt;usin...
2019-03-03 21:20:51
181
原创 Strange Towers of Hanoi(POJ1958)
题解：设d[n]是三塔问题的解，f[n]是4塔的解，那么可以推导出，f[n]=min(2*f[i]+d[n-i]),1<=i<n;#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=21;ll d[maxn],f[maxn];int main(){ int...
2019-03-03 14:06:03
106
原创 费解的开关CH0201
在一个5*5的01矩阵中，点击任意一个位置，该位置以及它上、下、左、右四个相邻位置中的数字都会变化（0变成1,1变成0），求最少需要多少次点击可以把一个给定的01矩阵变成全1矩阵？题解：枚举第一行的点击方法，共32种，对于每种情况，固定第一行，若第一行中有0，唯一的解决方案就是点击对应得第二行的数字，递推后可以发现固定第一行以后点击方案是确定的，那么枚举32种情况计算最小值即可。#includ...
2019-03-03 13:58:25
324
原创 ACM学习记录--位运算
1.移位操作：快速幂：1.1求a的b次方对p取模的值，数据范围小于等于1e9；int power(int a, int b, int p){ **//快速幂** int ans=1%p; while(b){ if(b&amp;amp;1) ans=ans*a%p; a=a*a%p; b&amp;gt;&amp;gt;=1; } return ans;} 算法思想很简单。将b视为二进...
2019-03-03 12:11:41
320
原创 最短Hamilton路径(CH0103)
给定一张n(n&lt;=20)个点的带权无向图，点从0~n-1标号，求起点0到终点n-1的最短Hamilton路径。Hamilton路径定义为每个顶点正好经过一次的路径。题解：枚举所有情况的时间复杂度是O(n*n!),使用二进制状态压缩DP可以优化到O（n2*2n）用一个数组f[i][j]维护当i（0&lt;=i&lt;2n）表示"点是否被经过的状态"对应的二进制数，且目前处于点j（0&lt;...
2019-03-03 11:59:06
386
原创 ACM学习记录--目录
目录一、基本算法1、位运算2、递推与递归3、前缀和与差分4、二分5、排序6、倍增7、贪心小结1二、基本数据结构1、栈2、队列3、链表与邻接表4、Hash5、字符串6、字典树7、二叉堆小结2三、搜索1、dfs2、bfs3、剪枝4、迭代加深5、A*6、IDA*小结3四、数学1、质数2、约数3、同余4、矩阵乘法5、高斯消元与线性空间6、组...
2019-03-02 21:15:34
167
原创 POJ1995
//题目大意：计算多个a^b的和modM，快速幂就可以过。#include<iostream> using namespace std;typedef long long ll;ll Z,M,H,A,B;int solve(ll A, ll B, ll M){ ll ant=1%M; while(B){ if(B&1){ ant=ant*A%M...
2019-02-28 22:40:31
233
原创 CodeForces 731C Socks(并查集)
Arseniy is already grown-up and independent. His mother decided to leave him alone formdays and left on a vacation. She have prepared a lot of food, left some money and washed all Arseniy's clothes....
2018-08-03 19:32:48
106
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人