- 博客(110)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 P3868 [TJOI2009]猜数字
题目描述现有两组数字，每组 kk 个。第一组中的数字分别用 a1,a2,⋯ ,aka_1,a_2,\cdots ,a_ka1,a2,⋯,ak表示，第二组中的数字分别用 b1,b2,⋯ ,bkb_1,b_2,\cdots ,b_kb1,b2,⋯,bk表示。其中第二组中的数字是两两互素的。求最小的 n∈Nn\in \mathbb{N}n∈N，满足对于 ∀i∈[1,k]\forall i\in [1,k]∀i∈[1,k]，有 bi∣(n−ai)b_i | (n-a_i)bi∣(n−ai)输
2021-06-12 09:38:33
167
1
原创 P3811 【模板】乘法逆元
题目这是一道模板题题目描述给定 n,pn,p 求 1\sim n1∼n 中所有整数在模 pp 意义下的乘法逆元。输入格式一行两个正整数 n,pn,p。输出格式输出 nn 行，第 ii 行表示 ii 在模 pp 下的乘法逆元。输入输出样例输入10 13输出179108112534说明/提示1≤n≤3×106,n<p<200005281 \leq n \leq 3 \times 10 ^ 6, n < p < 200005281≤n≤3×
2021-06-03 17:07:47
292
1
原创 未完成的任务
未完成的任务题目1596 矩阵乘积(三种)1055 能量项链2291 分组背包1644 取数字问题 (dp、dfs 2种)博客（做了，但没写博客的题）1461 最大连续数列之和1210 最佳浏览路线1463 最长公共子序列1209 旅行1517 糖果盒1205 最大子矩阵之和2315 打砖块2666 勇闯黄金十二宫射手宫2863 合并石子（三种方案）1597 石子合并问题1639 机器分配1652 CIM1640 叠放箱子问题（两种方法）1607 没有上司的舞会2
2020-08-23 10:32:32
330
原创 【无标题】
include#include#include#includestring s;int main()cin>>s;n=s.size();i<n;++i)i<=n;++i)i<=n;++i)l[b[i]]=i;r[b[i]]=i;i<=2000010;++i)cout<<ans;
2023-05-31 21:33:35
569
原创 【51nod】3122 小陶的疑惑2
题目思路利用差分思想先将数组变为差分数列，即ci=ai−ai−1c_i=a_i-a_{i-1}ci=ai−ai−1，然后对于两个操作：第xxx个数的值为c1c_1c1到cic_ici的和将区间(x,y)加c，相当于在cxc_xcx加c，并在cy+1c_{y+1}cy+1减c。再用树状数组优化求解。代码#include<iostream>#define ll long longusing namespace std;const int M=200000;ll
2022-01-12 16:22:44
323
原创 【51nod】3121 小陶与杠铃片
题目思路求逆序对，边输入边操作，每输入一个数，他前面有多少个比他大的数，答案就加几。用 aia_iai 表示数为 iii 的个数, 那么求 iii 的前面有多少数比它大，就是求ai+1a_{i+1}ai+1到aMAXa_{MAX}aMAX的和，也就是求a1a_1a1到aMAXa_{MAX}aMAX的和 减去a1a_1a1到aia_iai的和这就可以用树状数组维护，O(nlogn)O(nlogn)O(nlogn)。代码#include<iostream>using
2022-01-12 15:37:56
320
原创 树状数组 “详” 解
简介树状数组就是一种能在O(log n)内查询或修改的数据结构，它的代码极其简洁，是水题党的好帮手 适合解决单点修改与区间查询。其大概的结构是这样的：其中AAA数组就是我们的树状数组，Ai=1A_i=1Ai=1~ iii之和，即前缀和。val代表数据的权值。思路每次将一个点进行修改时，就将它所对应的树状数组以及它的父节点更新：void update(int x,int y){ for(; x<=n; x+=x&-x) A[x]+=y;}每次查询时，...
2021-12-25 15:13:21
339
原创 YbtOJ——最小生成树【例题2】新的开始
B. 【例题2】新的开始题目思路最小生成树，先将每个点与0号点相连，边权为建立发电站的费用，然后用kruska，将边按权值从小到大排序，然后用并查集判断一边的两端点是否在同一棵树中，如果不在，则将此边加进最小生成树中。代码#include<bits/stdc++.h>using namespace std;int fa[100001],ans,n,m,t;struct node{ int u,v,c;}a[100001];bool cmp(node x,node y)
2021-12-18 10:26:10
357
原创 YbtOJ——最小生成树【例题1】繁忙都市
A. 【例题1】繁忙都市题目思路模板最小生成树，用kruska，将边按权值从小到大排序，然后用并查集判断一边的两端点是否在同一棵树中，如果不在，则将此边加进最小生成树中。代码#include<bits/stdc++.h>using namespace std;int fa[100001],ans1,ans2,n,m;struct node{ int u,v,c;}a[100001];bool cmp(node x,node y){ return x.c<y.c
2021-12-18 09:34:56
141
原创 YbtOJ——并查集【例题1】【模板】并查集
A. 【例题1】【模板】并查集题目思路模板并查集代码#include<bits/stdc++.h>using namespace std;int fa[100001],n,m,x,y,z; int find(int x)//查找{ if(fa[x]!=x) return fa[x]=find(fa[x]); return x;}void merge(int x,int y)//合并{ int fx=find(x),fy=find(y); fa[fx]=fy;
2021-12-11 17:20:34
285
原创 YbtOJ——字典树【例题2】最大异或对
B. 【例题2】最大异或对题目思路两个数不同位越靠前，异或结果越大，将每个二进制数当做一个字符串从高位到低位存入trie,然后对于每个数，在trie中寻找最优解。代码#include<bits/stdc++.h>using namespace std;const int mx=32;long long trie[10000001][2],lt=1,n,m,a[10000001],ans;void in(long long s){ int p=1; for(int i
2021-12-11 16:53:53
350
原创 YbtOJ——字典树【例题1】前缀统计
A. 【例题1】前缀统计题目思路字典树的模板题。代码#include<bits/stdc++.h>using namespace std;long long trie[100001][300],lt=1,n,m,end[100001];string s;char ch;void in(string s)//插入字符串{ long long n=s.size(),p=1; for(int i=0;i<n;++i) { int ch=s[i]-'a'; i
2021-12-04 11:16:55
215
原创 《牛客练习赛87》A. 中位数
《牛客练习赛87》A. 中位数题目思路把序列排序，每次找最大的两个数合并，最后求中位数代码#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int N=200100;long long t,n,k,a[N];int main(){ scanf("%lld",&t); while(t--) { scanf("%lld%lld
2021-08-21 11:16:33
101
原创 模拟赛20210814D T4和luogu_CF1110E Magic Stones
题目对于每次操作ai′=ai+1+ai−1−aia_i'=a_{i+1}+a_{i-1}-a_iai′=ai+1+ai−1−ai可以通过移项得到：ai−ai−1=ai+1−ai′a_i-a_{i-1}=a{i+1}-a_i'ai−ai−1=ai+1−ai′ 和 ai+1−ai=ai′−ai−1\ \ 和\ \ a{i+1}-a_i=a_i'-a{i-1} 和 ai+1−ai=ai′−ai−1
2021-08-14 16:54:26
71
原创 模拟赛20210810A T1
题目大意：给定n个数a1a_1a1~ana_nan求任意一对数（ai,aja_i,a_jai,aj） 的 ∣(i−j)∗(ai−aj)∣|(i-j)*(ai-aj)|∣(i−j)∗(ai−aj)∣之和。思路显然只有当ai,aja_i,a_jai,aj不同时，才会对答案有贡献，所以只用让每个1和每个0配对。当很多个1（i1,i2⋅⋅⋅⋅⋅⋅imi_1,i_2······i_mi1,i2⋅⋅⋅⋅⋅⋅im）和一个0（jjj）相配对时，产生(i1−j)+(i2−j)⋅⋅⋅⋅⋅⋅+(
2021-08-10 15:23:24
67
原创 模拟赛20210809A T1
模拟赛20210809A T1题目大意：一个长度为nnn的序列，求经过n−1n-1n−1次合并操作后所有可能的结果（从小到大输出）定义合并操作为：每次操作可将任意一对相邻的数a,ba,ba,b 合并成((a&b)+(a∣b)>>1((a\&b)+(a | b)>>1((a&b)+(a∣b)>>1。思路区间DP：设 fi,j,kf_{i,j,k}fi,j,k 表示 iii 到 jjj 这个区间内能否经过若干次合并得到 kkk，能为1
2021-08-09 16:48:34
72
原创 YbtOJ——Hash 和 Hash 表【例题1】字符串哈希
A. 【例题1】字符串哈希题目思路设 p[i]p[i]p[i] 表示字符串111 ~ (i−1)(i-1)(i−1)的最长相同前缀后缀，则：若 n%(n−p[n])==0n\%(n-p[n])==0n%(n−p[n])==0，答案为 n/(n−p[n])n/(n-p[n])n/(n−p[n])否则，答案为 1。代码#include<iostream>using namespace std;string s;char ch;int n,p[1000001];void pr
2021-08-08 19:51:01
120
原创 YbtOJ——KMP 算法【例题3】周期长度和
C. 【例题3】周期长度和题目思路设 p[i]p[i]p[i] 表示字符串111 ~ (i−1)(i-1)(i−1)的最长相同前缀后缀，则：若 n%(n−p[n])==0n\%(n-p[n])==0n%(n−p[n])==0，答案为 n/(n−p[n])n/(n-p[n])n/(n−p[n])否则，答案为 1。代码#include<iostream>#include<cstdio>#include<cstring>using namespace st
2021-08-08 19:34:24
121
原创 YbtOJ——KMP 算法【例题2】重复子串
B. 【例题2】重复子串题目思路设 p[i]p[i]p[i] 表示字符串111 ~ (i−1)(i-1)(i−1)的最长相同前缀后缀，则：若 n%(n−p[n])==0n\%(n-p[n])==0n%(n−p[n])==0，答案为 n/(n−p[n])n/(n-p[n])n/(n−p[n])否则，答案为 1。代码#include<iostream>using namespace std;string s;char ch;int n,p[1000001];void pre
2021-08-08 11:55:48
131
原创 YbtOJ——KMP 算法【例题1】子串查找
A. 【例题1】子串查找题目终于学会了KMP !板子就不解释了，贴上一篇别人的KMP好文：数据结构KMP算法配图详解（超详细）代码#include<iostream>using namespace std;string a,b;int p[100001],n,ans;void in(){ cin>>a>>b;}void pre(string s)//预处理最长相同前缀后缀{ p[0]=-1; p[1]=0; int j=0,k=-1;
2021-07-09 15:18:52
203
原创 YbtOJ——字符串处理【例题5】生日相同
E. 【例题5】生日相同题目代码#include<iostream>#include<cstring>using namespace std;string s,s1,s2;int l1,l2;void in(){ cin>>s, s1=s+s;//模拟首尾相连的环 cin>>s, s2=s+s;//模拟首尾相连的环 l1=s1.size(); l2=s2.size(); if(l1>l2)//短的在前，长的在后 { s
2021-07-08 11:44:35
147
原创 YbtOJ——字符串处理【例题4】字符串环
D. 【例题4】字符串环题目将源输入的字符串复制一份插到后面，模拟首尾相连的环。然后查找连续公共子串即可。代码#include<iostream>#include<cstring>using namespace std;string s,s1,s2;int l1,l2;void in(){ cin>>s, s1=s+s;//模拟首尾相连的环 cin>>s, s2=s+s;//模拟首尾相连的环 l1=s1.size(); l2=s
2021-07-08 11:31:18
122
原创 YbtOJ——字符串处理【例题3】单词替换
C. 【例题3】单词替换题目被输入坑了几次，OJ上测是不能直接getline的。我用了一种比书上简单点的方法，注释里看。代码#include<iostream>#include<cstring>using namespace std;string s[100001],a,b;int n;void in(){ char space; do { cin>>s[++n];//输入单词 space=getchar();//输入空格 } w
2021-07-08 09:58:30
111
原创 YbtOJ——二分算法【例题3】最大均值
C. 【例题3】最大均值题目若一个长度不小于LLL的子段平均值为midmidmid，那么该子段的每个数都减去midmidmid后，子段和为0。若一个长度不小于LLL的子段平均值小于midmidmid，那么该子段的每个数都减去midmidmid后，子段和为负。若一个长度不小于LLL的子段平均值大于midmidmid，那么该子段的每个数都减去midmidmid后，子段和为正。二分答案midmidmid，将序列每数减去midmidmid，找出前缀和求出平均值最大的子段之和，并做上面的判断。代码#i
2021-07-08 09:28:19
111
原创 YbtOJ——二分算法【例题2】防具布置
B. 【例题2】防具布置题目设S(i)S(i)S(i)为0~iii中所有的防具若破绽在位置mid，那么S(l)S(l)S(l)为偶数，S(r)S(r)S(r)为奇数（l<mid≤rl<mid\leq rl<mid≤r）二分答案代码#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<queue>#defi
2021-07-07 21:22:34
81
原创 YbtOJ——二分算法【例题1】数列分段
A. 【例题1】数列分段题目题解假设最优解为sumsumsum，那么sumsumsum越大，分成的段数就越小；sumsumsum越小，分成的段数就越大。所以答案符合单调性，可以用二分判定：若最优解为sumsumsum分成的段数小于mmm，则说明sumsumsum太大，需往左区间查找。反之亦然。代码#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#
2021-07-07 19:53:02
216
原创 YbtOJ——递推算法【例题5】平铺方案
E. 【例题5】平铺方案题目题解对于2∗i2*i2∗i的矩阵：若在第 iii 列竖着放一个1∗21*21∗2的瓦片，则有f[i−1]f[i-1]f[i−1]种方案。若在第 iii 列和第 i−1i-1i−1 列横着放两个1∗21*21∗2的瓦片，则有f[i−2]f[i-2]f[i−2]种方案。若在第 iii 列和第 i−1i-1i−1 列放一个2∗22*22∗2的瓦片，则有f[i−2]f[i-2]f[i−2]种方案。所以f[i]=f[i−1]+f[i−2]+f[i−2]=f[i−1]+2f[
2021-06-28 17:08:05
124
原创 YbtOJ——广度搜索【例题3】立体推箱子
C. 【例题3】立体推箱子题目题解求最少步数，当然用广搜。队列里记录当前这一步的三个状态，分别是：坐标（x,y）和箱子状态（ t ）。其中箱子的状态有三种：立着，横躺着，竖躺着。分别用0,1,2表示。箱子横着躺或竖着躺占两个格子，对于横躺，将其坐标记作右边的格子；对于竖躺，坐标记作下面的格子。再加些处理0（）代码#include<iostream>#include<algorithm>#include<cstring>#include<cs
2021-06-20 11:57:12
108
原创 YbtOJ——广度搜索【例题2】山峰和山谷
B. 【例题2】山峰和山谷题目题解先解释一下样例：红笔圈着的是两个山峰，其余的形成一个山谷。每次从未访问过的点开始BFS，对它相邻的点（八连通）进行搜索：若搜索的点等于当前点，则加入队列若搜索的点大于当前点，则标记它不可能为山峰若搜索的点小于当前点，则标记它不可能为山谷代码#include<iostream>#include<algorithm>#include<cstdio>#include<queue>using na
2021-06-19 11:12:22
190
原创 YbtOJ——字符串处理【例题2】移位包含
B. 【例题2】移位包含题目题解设长度长的一个字符串为s1s1s1，短的为s2s2s2。枚举s1s1s1的移位，对于它的每一次移位，判断s2s2s2是否为其的子串。代码#include<iostream>#include<cstring>using namespace std;string s1,s2;int l1,l2;int main(){ int n; cin>>s1>>s2; l1=s1.size(); l2=s2.s
2021-06-13 16:46:09
80
原创 YbtOJ——字符串处理【例题1】数字反转
A. 【例题1】数字反转题目题解有点困，于是在YbtOJ找了道水题，但也让我学到了点东西：sprintf(
2021-06-13 16:13:40
107
1
原创 YbtOJ——深度搜索【例题2】数独游戏
B. 【例题2】数独游戏题目题解经过不断地debug，终于用自己的方法做出这题了。我的方法跟书上的不同，自认为更简单些。用三个二维数组分别记录每一行、列、宫中是否出现1~9，即判重，来进行剪枝。dfs每个输入时就储存下来的空着的格子，枚举1~9并根据判重数组判断能否填入该数字。填完所有空格后，输出并直接退出，最后别忘了初始化那三个判重数组，因为有多组数据。若点（x,y）（x,y）（x,y）的数为 ttt，三个判重的数组可以这样写：fx[x][t]=1;//行fy[y][t]=1;//列
2021-06-13 12:01:30
238
3
原创 YbtOJ——深度搜索【例题1】拔河比赛
A. 【例题1】拔河比赛题目题目链接题解由于本题数据过水，用爆搜即可过掉。只考虑一个队伍，搜索每个人加不加进这个队伍里，若不加其实就是加进另一个队。若当前加的人数未达半数，即可加进去；若当前没加的人数未达半数，即可不加进去代码#include<iostream>#include<cmath>using namespace std;int t,n,m,ans,a[100];void dfs(int dep,int c1,int c2,int sum,int
2021-06-13 08:56:17
249
1
原创 YbtOJ——贪心算法【例题3】畜栏预定
C. 【例题3】畜栏预定题目链接内存限制：256 MiB时间限制：1000 ms标准输入输出题目类型：传统评测方式：Special Judge题目描述有 头牛在畜栏中吃草。每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏，给出第 头牛开始吃草的时间区间 ，求需要的最少畜栏数和每头牛对应的畜栏方案。输入格式第一行一个正整数 。接下来 行，第 行两个正整数 。输出格式第一行一个整数，表示需要的最少畜栏数。接下来 行，第 行一个整数表示第 头牛的对应畜栏，
2021-06-12 20:18:14
495
原创 YbtOJ——递推算法【例题4】传球游戏
D. 【例题4】传球游戏题目链接内存限制：256 MiB时间限制：1000 ms标准输入输出题目类型：传统评测方式：文本比较题目描述上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。游戏规则是这样的： n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没有传出去的那个同学就是败者，要给大家表演一个节目。聪明的小蛮提出一个
2021-06-12 19:52:52
1697
3
原创 YbtOJ——贪心算法【例题2】雷达装置
B. 【例题2】雷达装置内存限制：64 MiB时间限制：1000 ms标准输入输出题目类型：传统评测方式：文本比较题目描述有 个建筑物，第 个建筑物在笛卡尔坐标系上的坐标为 ，你需要在 轴上安装一些雷达，每个雷达的侦察半径均为 ，要求每个建筑物都至少被一个雷达侦测到，求最少要安装几个雷达。输入格式第一行两个正整数 。接下来 行，第 行两个整数 。输出格式输出一行表示答案，若没有解决方案，则答案为 。样例样例输入3 21 2-3 12 1样例输出2数据范围与
2021-06-12 19:29:10
409
原创 P1495 【模板】中国剩余定理(CRT)/曹冲养猪
题目描述自从曹冲搞定了大象以后，曹操就开始捉摸让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲满不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。举个例子，假如有 16 头母猪，如果建了 3 个猪圈，剩下 1 头猪就没有地方安家了。如果建造了 5 个猪圈，但是仍然有 1 头猪没有地方去，然后如果建造了 7 个猪圈，还有 2 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？输入格式第一行包含一个整数 n——建立猪圈的次数，接下来 n 行，
2021-06-11 21:11:42
116
原创 P5431 【模板】乘法逆元2
题目题目描述给定 n 个正整数 aia_iai，求它们在模 ppp 意义下的乘法逆元。由于输出太多不好，所以将会给定常数 kkk，你要输出的答案为:∑i=1nkiai\sum\limits_{i=1}^n\frac{k^i}{a_i}i=1∑naiki当然要对 p 取模。输入格式第一行三个正整数 n,p,k 意义如题目描述。第二行 n 个正整数 a_i ，是你要求逆元的数。输出格式输出一行一个整数，表示答案。输入输出样例输入6 233 421 4 2 8 5 7输出
2021-06-09 17:20:07
217
原创 P4139 上帝与集合的正确用法
题目描述题目链接根据一些书上的记载，上帝的一次失败的创世经历是这样的：第一天， 上帝创造了一个世界的基本元素，称做“元”。第二天， 上帝创造了一个新的元素，称作“α”。“α”被定义为“元”构成的集合。容易发现，一共有两种不同的“α”。第三天， 上帝又创造了一个新的元素，称作“β”。“β”被定义为“α”构成的集合。容易发现，一共有四种不同的“β”。第四天， 上帝创造了新的元素“γ”，“γ”被定义为“β”的集合。显然，一共会有16种不同的“γ”。如果按照这样下去，上帝创造的第四种元素将会有6553
2021-06-02 17:18:51
100
原创 P1447 [NOI2010] 能量采集
题目描述栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。栋栋的植物种得非常整齐，一共有 nn 列，每列有 mm 棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标 (x, y)(x,y) 来表示，其中 xx 的范围是 11 至 nn，yy 的范围是 11 至 mm，表示是在第 xx 列的第 yy 棵。由于能量汇集机器较大，不便移动，栋栋将它放在了一个角上，坐标正好是 (0, 0
2021-06-02 16:40:10
113
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人