jzoj专题

Jzoj 条件循环（while，do while）部分代码（共25题）

1020: 【入门】编程求1+3+5+...+n #include <bits/stdc++.h>using namespace std;int n, sum;int main() {scanf("%d", &n);for(int i=1; i<=n; i+=2){sum+=i;} printf("%d", sum);return 0;} 1012: 【入门】两数比大小 #i

Jzoj 二维数组部分代码（共13题）

2788: 【入门】二维数组的输入输出边输入边输出 #include <bits/stdc++.h>using namespace std;int n, m, a[11][11];int main(){scanf("%d %d", &n, &m);//边输入边输出for(int i=1; i<=n; ++i){for(int j=1; j<=m; ++j){scanf("%d", &

jzoj 5770 可爱精灵宝贝

题目题解 –是区间dp（好像dfs加神秘玄学剪枝也能过？）首先，我们可以发现这个人走过的位置是一个区域，而且区域内部的精灵要么被抓，要么消失了（总之就是与以后的转移没有关系）所以，状态定义： f[l][r][t] :当这个人走过区间[l,r]，且目前在l处，时间为t时的最大分值注意，l，r的左右位置要根据大小自己判断然后我们又发现，现在这个人只有两种方法：左走或右走

[离散化][区间DP]JZOJ 5770 可爱精灵宝贝

日常黑Pokeman Go Description Branimirko是一个对可爱精灵宝贝十分痴迷的玩家。最近，他闲得没事组织了一场捉精灵的游戏。游戏在一条街道上举行，街道上一侧有一排房子，从左到右房子标号由1到n。刚开始玩家在k号房子前。有m个精灵，第i只精灵在第A[i]栋房子前，分值是B[i]，以及它在T[i]秒内（含）存在，之后消失。Branimirko可以选择移动至相邻的房子，耗时

[权值线段树]JZOJ 3236 矮人排队

Description 在七山七海之外的一个小村庄，白雪公主与N个矮人住在一起，所有时间都花在吃和玩League of Legend游戏。白雪公主决心终结这样的生活，所以为他们举办了体育课。在每节课开始时，矮人必须按他们的身高站队。假定矮人们有高度1，2，...，N（每个人高度互不相同）。然而，由于不健康的生活方式，矮人的智力有所恶化，所以他们没有能力依照自己的高度排序。因此，白雪公主发

JZOJ 1495. 宝石（附加扫描线讲解）

JZOJ 1495. 宝石题目大意：给你N个 ( K + 1 ) × ( K + 1 ) (K+1)\times(K+1) (K+1)×(K+1)的正方形以及他们左上角的那个顶点的坐标和它的权值，求最大的覆盖的权值。这一题可以用二维前缀和做，但是无法拿到满分。满分做法：扫描线。假如现在有这么两个长方形，权值都为1（不要问为什么是长方形，这里只是为了方便讲解而已），它们摆放如图：首

【JZOJ A组】大逃杀

Description 自从 Y 君退役之后，她就迷上了吃鸡，于是她决定出一道吃鸡的题。 Y 君将地图上的所有地点标号为 1 到 n，地图中有 n − 1 条双向道路连接这些点，通过一条双向道路需要一定时间，保证从任意一个点可以通过道路到达地图上的所有点。有些点上可能有资源，Y 君到达一个有资源的点后，可以选择获取资源来使自己的武力值增加 wi，也可以选择不获取资源。如果 Y 君获取了

[数位dp][斯特林反演] Jzoj P5765 相互再归的鹅妈妈

Description Input Output Sample Input Input 13 1101Input 24 310Input 35 1001 Sample Output Output 11Output 21978Output 3598192244 Data Constraint 对于所有数据，保证

#线段树#JZOJ 1959 最大值

线段树 #include <cstdio>#include <cctype>#include <climits>#include <algorithm>using namespace std;struct node{int w;}tree[400001]; int a[100001],n,m,ans;inline int in(){int ans=0,f=1; char c=getc

#欧拉函数#jzoj 1709 洛谷 2158 仪仗队

题目求C君一次能看到多少人。分析：首先3个点是绝对看得到的（1，0），（0，1），（1，1）然后从第三行开始为 φ ( n − 1 ) \varphi(n-1) φ(n−1)把它们加起来*2+3便是答案。代码 #include <cstdio>using namespace std;unsigned short n,phi[40001]; int ans;int

#乘法逆元，组合计数#洛谷 1313 codevs 1137 jzoj 3027 计算系数

题目给定一个多项式$ (ax + by)^k$ ，请求出多项式展开后 $xnym $项的系数。分析根据二项式定理，有 ( a x + b y ) k = ∑ i = 0 k C k i a i b k − i x i y k − i (ax+by)^k=\sum_{i=0}^kC_k^ia^ib^{k-i}x^iy^{k-i} (ax+by)k=i=0∑kCkiaibk−ixi

#动态规划，多重背包#codevs 1068 洛谷 1541 jzoj 1863 乌龟棋

题目求通过走卡片的步数获得的最大得分（一开始在1，自动加上得分）分析长得挺像背包的，比较简单233 int now=1+i+j*2+k*3+p*4;if (i) f[i][j][k][p]=max(f[i][j][k][p],f[i-1][j][k][p]+a[now]);if (j) f[i][j][k][p]=max(f[i][j][k][p],f[i][j-1][k][

jzoj 1234 洛谷 1203 codevs 1542 坏掉的项链破碎的项链

题目求把圆环拆成链，从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子，在另一端做同样的事，能得到的最大的珠子数。分析可以把链扩大3倍，然后纯模拟233 代码 #include <iostream>using namespace std;string a; int n,ans;int max(int a,int b){return (a>b)?a:b;}int

#树形dp#jzoj 1824 debug

题目删去最少的边，使每个节点的度不超过2。分析考虑一个邻接点不是叶子节点的点，那么优先选择割断与父亲节点的边。 why？ First：如果该点只有一个叶子节点，那么删去与叶子节点的边不需要这么做 Second：如果该点有多个叶子节点，保留一条原来被删除与叶子节点之间的边，得到的仍然是一个最优解所以就可以构造出算法，从最下方的非叶子节点开始，当度超过2，那么累加删去的边，并使父亲节

#单调队列，动态规划#洛谷 2627 jzoj 2202 2321（高中）codevs 4654 修剪草坪

题目在n头奶牛里选择若干头，使连续的奶牛不超过k头并让总价值最大。分析这道题正向选择比较难选，所以就想到了n头奶牛都选并去掉奶牛后使总价值最大。用单调队列维护，时间复杂度O（n）代码 #include <cstdio>#include <cctype>using namespace std;typedef long long ll;ll n,k,l,r,q[10

#树形dp#JZOJ 1087 鱼肉炸弹

题目有n栋楼房，两栋楼房可以看见当且仅当中间的楼房不高于两栋楼房，使用炸弹可破坏某一栋楼房，问使用K枚炸弹使得能看见楼房i的楼房数的最大值最小。分析树形dp，容易得出 f [ x ] [ i + j ] = m i n ( f [ x ] [ i + j ] , m a x ( f [ l ] [ i ] , f [ r ] [ j ] ) + b [ x ] ) f[x][i+

#网络流，费用流#洛谷 3159 JZOJ 2765 交换棋子

题目给出一个黑白棋盘的起始状态，每个棋子可以向相邻或对角相邻的棋子交换，但是有限定的交换次数，问最少交换多少次到达目标状态分析一开始的思路就是跑费用流，但是单纯的建图貌似不对，因为如果直接拆点会中间点交换两次，那么可以把次数取一半，对于原先是黑棋子而最后是白棋子向源点连边，原白后黑向汇点连边代码 #include <cstdio>#include <cstrin

#网络流，费用流，SLF优化，SPFA，zkw费用流#jzoj 1586 codevs 1362 洛谷 2604 网络扩容

题目有两个问题，首先求1到 n n n的最大流（不解释了），然后求1到n使最大流扩展 k k k的费用，每扩展一个最大流，扩展一次边的费用分析当然如何做第二个问题，可以重新建一个汇点流量是最大流 + k +k +k，费用为0，并且原来的边再建一次从 u u u到 v v v，费用为该边的费用，流量无限跑一次最大流，then就讲完了代码 #include <cstd

#堆优化dijkstra#洛谷 1828 jzoj 1287 codevs 2038 ssl 1693 香甜的黄油

题目有 n n n个点，求每个点的单源最短路径的最短和分析其实跑 n n n遍 s p f a spfa spfa或 d i j k s t r a dijkstra dijkstra堆优化就行了代码 #include <cstdio>#include <queue>struct node{int y,w,next;}e[2901];int n,m,dis[801]

#莫比乌斯反演，整除分块#bzoj 2154 bzoj 2693 jzoj 1938 洛谷 1829 Crash的数字表格 or JZPTAB

题目求 ∑ i = 1 n ∑ j = 1 m l c m ( i , j ) \sum_{i=1}^n\sum_{j=1}^mlcm(i,j) i=1∑nj=1∑mlcm(i,j) 分析原式= ∑ i = 1 n ∑ j = 1 m i j g c d ( i , j ) \sum_{i=1}^n\sum_{j=1}^m\frac{ij}{gcd(i,j)} i=1∑nj=1

#斜率优化，动态规划#jzoj 2318 洛谷 3628 bzoj 1911 特别行动队

洛谷链接分析首先给出朴素的方程( s [ i ] = ∑ j = 1 i x [ j ] s[i]=\sum_{j=1}^{i}x[j] s[i]=∑j=1ix[j]) d p [ i ] = m i n { d p [ j ] + a ( s [ i ] − s [ j ] ) 2 + b ( s [ i ] − s [ j ] ) + c } dp[i]=min\{dp[j]+

#贪心，线性基#BZOJ 2460 洛谷 4570 JZOJ 2439 元素

题目链接分析首先取到权值和最大答案越优，所以要先进行权值大到小排序，接着若序号异或值为0那么显然会让答案变小，所以要尽量让异或值不为0，所以说需要用到线性基，当可以插入线性基中也就是说明序号异或值不为0，那么加上权值和即可代码 #include <cstdio>#include <cctype>#include <algorithm>#define rr registe

#线性基，博弈论#洛谷 4301 JZOJ 3200 BZOJ 3105 新Nim游戏

题目 Nim游戏进阶，第一轮可以拿走若干堆的石子，之后与Nim游戏相同问先手是否必胜，是的话输出第一轮拿走的最小值，不是输出-1 分析那么 N i m Nim Nim游戏先手必胜当且仅当A1 xor A2 xor…xor An不等于0，那么就要让把等于0的情况去掉，那么可以用到线性基，当无法插入也就说明异或和为0，所以累计答案，但是题目又说取最小值，那么从大到小排序，让大的早点被取掉

#回文自动机#洛谷 3649 JZOJ 3654 回文串

题目给你一个由小写拉丁字母组成的字符串 s s s。我们定义 s s s的一个子串的存在值为这个子串在 s s s中出现的次数乘以这个子串的长度。对于给你的这个字符串 s s s，求所有回文子串中的最大存在值。分析回文自动机模板，不解释代码 #include <cstdio>#include <cstring>#define rr register#define m

#主席树、二分、树状数组#洛谷 3157 JZOJ 2287 动态逆序对

题目分析首先如果不带修改操作那么就是一道主席树题目，但是既然有了修改，那么还必须用上树状数组维护，时间复杂度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n) 代码 #include <cstdio>#include <cctype>#include <algorithm>#define rr registerusing namespace

#组合计数，动态规划#JZOJ 1523 洛谷 2481 代码拍卖会

题目问多少个 n n n位数满足数位从左到右数字不下降且为 P P P的倍数分析慢慢填坑吧代码 #include <cstdio>#define rr registerusing namespace std;typedef long long ll;const ll mod=999911659;ll n,p,rep,cnt[501],pos[501],dp[50