题意:求\([(\sqrt{2}+\sqrt{3})^{2n}] mod 1024\) 分析: 把指数的2带入 原式等于 \([(5+2\sqrt{6})^n]\) 有一个重要的结论是n次运算后其结果最终形式也是\(a_n+b_n\sqrt{6}\) 的形式 记最终的解 [F(n) = a_n+b_n\sqrt{6}] [F(n-1) = a_{n-1}+b_{n-1}\sqrt{6}] [\frac{F(n)}{F(n-1)} = 5+2\sqrt{6}] [F(n) = (5+2\sqrt{6})F(n-1)] [F(n) = (5+2\sqrt{6})a_{n-1...
BZOJ - 1257 分块 详解
中文题面 这道题就是LightOJ某题的升级版 前段时间我是直接用√k前暴力后分块的处理方式,然后直接套个等差求和 这次看到了dalao的证明再次让我知道我好菜啊 在这里做下笔记,学习一下对于整除运算的分析方法 关于\([\frac{k}{i}]×i,i∈[1,n]\)的处理 令\(x∈[1,k],g(x)=[k/[k/x]],f(x)=k/x\) 有\(g(x) = [k/[f(x)]] ≥ [k/f(x)] = x\) 得到\(g(x) ≥ x\),换为底 \([k/g(x)]≤[k/x]\) ① 另一方面\([k/g(x)] = [k/[k/[k/x]]] ≥...
POJ - 1456 贪心 堆常用操作 注意细节
题意:给定n个商品的deadline和profit,求每天卖一件的情况下的最大获利 显然是一道贪心 按deadline从小到大排序好,动态维护小根(profit)堆的大小<=当前deadline的天数,往里面符合条件的尽可能塞更优解 注意有n为0的情况 /*H E A D*/ struct Node{ ll p,d,id; }a[maxn]; bool cmp(Node a,Node b){ if(a.d!=b.d)return a.d<b.d; return a.p>b.p; } ll n; int main(){ whi...
BZOJ - 4260 01字典树+前后缀
题意:给定\(a[1...n]\),求\((a_{i}⊕a_{i+1}⊕\cdots ⊕a_{j})+(a_{p}⊕a_{p+1}⊕\cdots⊕a_{q})\)的最大值,其中\(1≤i≤j<p≤q≤n\) 前后缀最优解预处理后然后枚举断点即可 /*H E A D*/ struct trie{ int ch[maxn<<5][2],sz[maxn<<5],val[maxn<<5],tot,root; void init(){ ch[0][0]=ch[0][1]=0; sz[0]=0;val[0]=0; tot=1;root...
BZOJ - 2457 思維+貪心
//為什麼我的Chrome OS更新後變成強制繁體了?? 題目要求使用最少的雙端隊列來維護一個單調非降序列 先來看下規律 首先，val肯定是單調非降的，在相等val範圍內的id可以xjb亂放不影響 其次，在單調可解的val範圍內，id一定是中間小兩邊大（中間是最初維護的，而兩邊是不斷地插入肯定越來越大） 即id在某一範圍內是v型分布的 因為val是單調的，所以對不同的val進行分塊管理對應的id，很顯然最低成立的條件是相同val（塊）的id肯定是緊挨著的，而且是每一個塊逐步往右靠（單調嘛） 如果不可解，那就意味著id的分布至少是vv型的，即至少多了一個極大值拐點，那麼拐...
HDU - 4699 对顶栈
Get到了全新O(1)替代部分伸展树功能的姿势 左栈stk1维护当前信息，右栈stk2维护历史删除信息 题目求的是严格的前缀和（且小于当前指针）那就每次左栈新增时再更新前缀和信息就好 即使把题面换成最大子段和也是一样搞法 要是O(1)求1到k的最大/小值？再来多一个维护历史的栈..应该可以吧 /*H E A D*/ stack<int> stk1,stk2; ll sum[maxn],maxsum[maxn]; int main(){ int Q,op,x,k; char str[50]; while(~iin(Q)){ ...
POJ - 2018 二分+单调子段和
求一个长度为n的序列中的一个平均值最大且长度不小于L的子段，输出最大平均值 最值问题可二分，从而转变为判定性问题：是否存在长度大于等于L且平均值大于等于mid的字段和 每个数与mid作差再转变为求非负子段 子段和问题应该利用前缀和C，长度大于等于L的字段和最大值可表示为 max{Aj+1 + Aj+2 … + Ai},i-j+1-1>=L,j+1>=1 等价于 max{Ci-min{Cj}},L<=i<=n,0<=j<=i-L 注意是i=L时j=0 只要i单调递增,j也单调递增，可O(1)更新答案，然后不断二分尺取即可 j+1的表...
POJ - 3263 差分+前缀和
给出n头牛的身高，和m对关系（a[i]与b[i]可以相互看见。即他们中间的牛都比他们矮）。已知最高的牛为第p头，身高为h，求每头牛的身高最大可能是多少。 只需不断维护相对值的前缀就能得到解 这种思想第一次是在树状数组区间更新那里看到的,由于题目要求是1~n所以直接可以用前缀和维护 注意不能直接-1 +1 /*H E A D*/ int delta[maxn]; map<P,int> vis; int main(){ int n,I,h,r,a,b; while(~iin(n)){ I=read();h=read();r=read(); memse...
POJ - 1845 约数和
求\(A^B\)的约数和模MOD 对A质因子分解P1^k1*P2^k2….P^kn A^B既指数对应部分乘以B 对于每个P都有(1+P^1+P^2+…+P^ki)的选择 连乘每一个P的等比数列之和即可 这里用了分治法,我觉得有必要记一下,不然推错就麻烦了 奇数部分sum(p,c)=(1+p^(c+1»1))sum(p,c-1»1) 偶数部分sum(p,c)=(1+p^(c»1))sum(p,c/2-1)+p^c /*H E A D*/ inline int mod(ll a){ return a%MOD; } int fpw(ll a,ll n){ l...
BZOJ - 2157 树链剖分+线段树
/*H E A D*/ int from[maxn<<1],to[maxn<<1],nxt[maxn<<1],cost[maxn<<1],head[maxn],tot; int size[maxn],fa[maxn],depth[maxn],top[maxn],son[maxn],dfn[maxn],pre[maxn],tot2; void init(){ memset(head,-1,sizeof head); memset(son,0,sizeof son); memset(size,0,sizeof siz...
BZOJ - 1013 高斯消元
n维空间中给出n+1个球面上的点求圆心坐标(x0,x1,…xn-1) 任选其中一个点坐标如第一个点(a0,b0…z0) (x0-a0)^2+(x1-b0)^2+…=r^2 对于剩下的n个点都与上面的式子作差,把高次方的消去得到线性方程组 2(a1-a0)x0+2(b1-b0)x1+2(c1-c0)x2+…=dis1-dis0 … 共n行n列, 然后构造Ax=b丢进去高斯消元就行了 //其实我只是来试试板子(来自挑战程序设计竞赛) #include<bits/stdc++.h> #define rep(i,j,k) for(int i=j;i<=k;...
BZOJ - 1003 DP+最短路
#include<bits/stdc++.h> #define rep(i,j,k) for(int i=j;i<=k;i++) using namespace std; const int maxn = 4e4+11; typedef long long ll; const int oo = 0x3f3f3f3f; vector<int> vec[333];//block int to[maxn<<1],nxt[maxn<<1],cost[maxn<<1],head[maxn],tot; void init(){...
线性筛小总结
线性筛的思想是每个数只会被筛一遍，因此时间复杂度是线性的（实际全局vis是大于n的，但以每个数的遍历次数来说恰好是1） 设一个合数的来源只有两种：素数 × 素数，或者是 合数 × 最小的素数，这样可以保证每个合数不会重复遍历 如果i为素数，那就令prime[j]小于等于i来避免重复遍历，所以i%prime[j]保证了prime[j]不大于i 如果i为合数，那假如i%prime[j]不为0，那prime[j]就是i×prime[j]分解的最小的素数，否则就意味着i里面含有prime[j]，而prime[]表是递增的，后者的i×prime[j+1]所含素数的最小素数肯定不是prim...
简易随机数
实测手动实现1e7范围比内置快3倍左右 unsigned int SEED = 17; inline int Rand(){ SEED=SEED*1103515245+12345; return (SEED/65536)%666; } PS xjb乱敲也是可以的 #include<stdio.h> unsigned int xjb=2333333; int Rand(){ return (xjb=xjb*12345+23333)%7; } int arr[33],cnt,i; int main(){ while(cnt++<2...
POJ - 1080 枚举 / DP
要求max{F/P},先枚举下界lowf,再贪心求符合约束条件的n个最小价值和 记录F的离散值和去重可以大幅度常数优化 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<vector> #include<iterator> using namespace std; const int maxn = 1e5+11; typedef pair<int,int> P; vector<P...
Codeforces - 722C 区间合并
要求断裂的数列之和的最大值,只需在断裂处的下标修改为一个足够负无穷大的值就可以用线段树维护 这道题数据还是弱了点,如果n和ai均取最大可能我这个程序早就爆ll了 本着死马当活马医的可贵精神直接改回ll碰碰运气,没想到A了 //听说正解是倒着用的并查集?! #include<bits/stdc++.h> using namespace std; const int maxn = 1e5+11; typedef long long ll; const ll oo = 1ll*100000*(2e9+2e8); typedef long long BIG; #defin...
UESTC - 1437 LCA模板
UESTC - 1437 随便找的倍增模板… #include<bits/stdc++.h> using namespace std; const int maxn = 1e5+11; int to[maxn<<2],nxt[maxn<<2],cost[maxn<<2]; int head[maxn],tot; int fa[maxn][20],dep[maxn]; void init(){ memset(head,-1,sizeof head); memset(fa,0,sizeof fa); tot=0;...
Codeforces - 316C2 棋盘模型
Let’s move from initial matrix to the bipartite graph. The matrix elements (i, j) for which i + j are even should be place to one part, the matrix elements (i, j) for which i + j are uneven should be place to another part. The edges are corresponding to squares which are situated side by side. ...
UVALive - 3645 时序模型
按航班拆点 注意返边的条件 #include<bits/stdc++.h> using namespace std; const int maxn = 1e6+11; const int oo = 0x7fffffff; int to[maxn<<1],nxt[maxn<<1],cap[maxn<<1],flow[maxn<<1]; int head[maxn],tot; void init(){ memset(head,-1,sizeof head); tot=0; } void add(int u,i...
UVA - 11082 行列模型
行列二分图模型，行指向列即表示权重w[i][j] 避免零流的方法就是使下界为1 #include<bits/stdc++.h> #define rep(i,j,k) for(int i = j; i <= k; i++) #define repp(i,j,k) for(int i = j; i < k; i++) #define rrep(i,j,k) for(int i = j; i >= k; i--) #define repe(i,u) for(int i = head[u]; ~i; i = nxt[i]) #define scan(a) s...
网络流模板
ISAP #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int maxn = 1e5+11; const int oo = 0x7fffffff; int to[maxn<<1],nxt[maxn<<1],cap[maxn<<1],flow[maxn<<1]; int head[maxn],tot; void init(){ m...
Codeforces - 321B 最大费用流
MCMF必须是满足流量最大为前提下的最小费用流(这里是最大费用流) 因此还必须不断地枚举m的流量才行 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int maxn = 1e5+11; const int oo = 0x3f3f3f3f; int to[maxn<<1],cost[maxn<<1],cap[max...
高精度模板
UVA12333 #include<iostream> #include<cstdio> #include<cstring> #include<cctype> #include<cmath> #include<vector> #include<queue> #include<map> #include<algorithm> #include<set> #define scnaf scanf #define cahr char #define bug puts("b...
DX12 Chapter6人肉机翻
6.1 顶点与输入布局 Direct3D 的顶点可以包含除空间坐标外的其他数据.如: struct Vertex1 { XMFLOAT3 Pos; XMFLOAT4 Color; }; struct Vertex2 { XMFLOAT3 Pos; XMFLOAT3 Normal; XMFLOAT2 Tex0; XMFLOAT2 Tex1; }; 一旦定义了一个顶点结构体,我们需要给 Direct3D 提供一个我们的顶点结构体的说明因此它直到每个成分是做什么的.该说明以用 D3D12_INPUT_LAYOUT_DESC 结构体表示的 input layout de...
DX12 Chapter4人肉机翻
早期的，基本乱翻，随便看 4.1.2 COM 我们经常引用一个 COM 对象作为接口,因此可以当作一个C++类来使用. 不能通过new来创建一个新的COM接口. 除此以外,COM对象是引用计数的,当我们被一个称为Release方法的接口(所有COM接口继承自IUnknown COM接口,它提供该方法)而不是delete处理时,COM接口会在引用计数归0时释放他们的内存. 为了辅助管理COM对象的生命周期,Windows Runtime Library (WRL)提供一个 *Microsoft::WRL::ComPtr 类(#include )* 它可以被认为是一个COM...