- 博客(38)
- 收藏
- 关注
RSS订阅原创 [SDOI2011]拦截导弹
对于第一问：暴力 dpdpdp 不行，用 CDQCDQCDQ 优化，左右区间合并时确保左边区间已更新好，然后把右区间排序更新左区间对右区间的影响，还原后再递归右区间。对于第二问：概率等于选择当前导弹的方案数除以总方案数，分别求出以这个i结尾和开始的最长上升子序列的长度，当长度相加 −1-1−1 等于最长长度时计算答案，所以再跑一边 CDQCDQCDQ。#include<bits/stdc++.h>#define maxn 200005#define db double#define i
2022-02-12 20:47:05
254
原创 【题解】 P1594 护卫队
首先因为处理完前面的车队之后后面的车队不会影响前面的车队，所以无后效性可以用动态规划。设 dp[i]dp[i]dp[i] 表示前 iii 个车的最小时间，转移时就枚举 jjj 把车队分成之前的和 jjj 到 iii 两段，把两段加起来。取枚举所有 jjj 所对应的值的最小值，注意判断区间内总重不能超过桥。dp[i]=min(dp[j−1]+L/st)dp[i] = min(dp[j-1] + L / st)dp[i]=min(dp[j−1]+L/st)其中 LLL 为桥长， ststst 为 jjj
2021-01-07 22:05:52
206
原创 【题解】 UVA306 Cipher
题目相当于是求一个串按某种指定方式换位多次后形成的串。因为 kkk 很大，所以不能直接模拟。我们考虑样例，对于一个以 4 5 3 7 2 8 1 6 10 9 为标准的转移，我们若转移两次，就相当于进行一次以 7 5 3 1 2 8 4 6 10 为标准的转移，并且每次换的方式是固定的，所以满足结合律，可以用快速幂来解决。时间复杂度为 O(nlogk)O(nlogk)O(nlogk)#include<bits/stdc++.h>using namespace std;const in
2021-01-07 22:04:52
127
原创 【模板】后缀自动机SAM
详细讲解例题有点难懂，关于复杂度的证明见链接。#include<bits/stdc++.h>using namespace std;const int M=2e6+5;struct node{ int ch[26]; int len,fa; node(){memset(ch,0,sizeof(ch));len=0;}}dian[M];vector<int> G[M];int las=1,tot=1;//指向一个空状态long long sum[M],ans;
2021-01-02 22:27:18
166
1
原创 【模板】后缀数组SA
详细讲解例题模板题：用后缀数组计算出 sasasa 和 heightheightheight 后，用一个单调栈就解决了。#include<cstdio>#include<algorithm>#include<cstring>#include<stack>using namespace std;const int M=5e5+5; void write(int x){ if(x<=9){ putchar(x+'0
2021-01-02 22:12:14
97
原创 【模板】莫队
普通莫队例题#include<bits/stdc++.h>using namespace std;const int M=5e4+5;long long e,ans;void read(long long &x) { int f=1;x=0;char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') {x=(x
2021-01-02 22:00:58
87
原创 【题解】「THUPC 2017」体育成绩统计 / Score
题目题目题解首先输入并处理，用一个结构体将每个人的信息存好，然后把阳光跑步的信息按人分类，每个人单独处理，具体细节见注释。#include <bits/stdc++.h>//#define int long longusing namespace std;const int M = 5e3 + 5, N = 1e4 + 5;int n, m;int tianshu[100] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 3
2020-11-27 22:36:51
473
原创 【题解】CF514E Darth Vader and Tree
题意翻译有一个无限大的有根树，树上的每一个节点都有n个子节点 (1≤n≤105)( 1 \leq n \leq 10^5 )(1≤n≤105)，任意一个节点它的第iii个子节点之间的距离为di(1≤di≤109)d_i( 1 \leq d_i \leq 10^9 )di(1≤di≤109)。给出一个数x(0≤x≤10)x(0 \leq x \leq 10)x(0≤x≤10)，求有多少个节点到根节点的距离小于等于xxx ( 答案模1e9+71e9+71e9+7 )。题解首先可以想到一个很简单的DP
2020-11-20 23:26:26
172
1
原创 【题解】儒略日
P7075 儒略日由于题目太长就不放这里了。就是这道题让我考试时自闭了。题解首先把时间抽分段，公元前[4713,1]一段，公元后[1,1582)一段，[1582,1583)，[1583,1600]，(1600, ∞\infty∞]。儒略历就4年一段，格里高利历就400年一段。然后就是许多细节，什么加一减一，反正面向数据编程。问候出题人#include<cstdio>#define int long longusing namespace std;int D[13]={0,3
2020-11-20 21:46:22
340
原创 区间DP总结
2.1.3 区间DP2.1.3.1 基本概念 区间DP，顾名思义是在区间上DP，它以“区间长度”作为DP的“阶段”，使用两个坐标(区间的左、右端点)描述每个维度。它的主要思想就是先在小区间进行DP得到最优解，然后再利用小区间的最优解合并求大区间的最优解。2.1.3.2 核心思路 既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度 lenlenlen 为每次分割成的小区间长度(((由短到
2020-11-13 21:46:39
249
原创 【题解】石子合并
有nnn堆石子排成一条直线，每堆石子有一定的重量。现在要合并这些石子成为一堆石子，但是每次只能合并相邻的两堆。每次合并需要消耗一定的体力，该体力为所合并的两堆石子的重量之和。问最少需要多少体力才能将n堆石子合并成一堆石子？假设只有2堆石子，显然只有1种合并方案。不管怎么合并，总之最后总会归结为2堆，如果我们把最后两堆分开，左边和右边无论怎么合并，都必须满足最优合并方案，整个问题才能得到最优解。m[i][j]={0i=jmin(m[i][k]+m[k+1][j])+w[i][j]i<jm[i]
2020-11-13 21:03:54
281
原创 【题解】戳西瓜
有 n 个西瓜，编号为 000 到 n−1n-1n−1 ，每个西瓜上都标有一个数字，这些数字存在数组 numsnumsnums 中。现在要求你戳破所有的西瓜。每当你戳破一个西瓜iii时，你可以获得 nums[left]∗nums[i]∗nums[right]nums[left]*nums[i]*nums[right]nums[left]∗nums[i]∗nums[right] 个硬币。这里的 leftleftleft 和 rightrightright 代表和 iii 相邻的两个西瓜的序号。注意当你戳破了西
2020-11-13 21:01:16
176
原创 【模板】主席树
#include<bits/stdc++.h>#define M 200005using namespace std;int n,T;int tot,cnt,it;int a[M],lsh[M],rx[M],ly[M<<5],ry[M<<5],sum[M<<5];void read(int &x) { int f=1;x=0;char c=getchar(); while(c<'0'||c>'9') {if(c=='-'
2020-10-31 23:45:21
74
原创 逆元学习笔记
定义若在mod p意义下，对于一个整数a，有a*b≡1(mod p)，那么这个整数b即为a的 乘法逆元，同时a也为b的乘法逆元， 一个数有逆元的充分必要条件是gcd(a,p)=1，此时a才有对p的乘法逆元运用主要是用于取模。模板费马小定理long long qkpow(long long x,long long y,long long p){ long long ans=1; while(y){ if(y&1) ans=ans*x%p; x=x*x%p; y>&
2020-10-05 14:04:54
206
4
原创 【题解】CF489E Hiking
题目描述一个旅行者正在计划沿着河水进行一场水上远足。经过探测，他已经探明了这条河上适合晚上休息的n个地点，记录了这些地点与出发点的距离。上述的每一个地点都有一个美丽度。也就是说，对于第i个地点，它和起点的距离为xix_ixi，它的美丽度为bib_ibi。上述的每一个地点都在出发点的下游，且这个旅行者在旅行的时候只会顺流而下。简言之，我们可以把河流看成一个数轴，出发点的坐标是0，第i个地点的坐标是xix_ixi。旅行者只会沿正方向前进。这个旅行者对他一天的前进距离，设定了一个基准值lll，
2020-10-05 08:11:08
955
5
原创 【模板】LCA
tarjan#include<bits/stdc++.h>using namespace std;const int M=1e5*2+5;int n,m,fa[M],ans[M];int vis[M];vector<int> G[M];vector<int> q[M];vector<int> q_[M];void add(int x,int y){ G[x].push_back(y); G[y].push_back(x);}
2020-09-23 21:29:27
107
原创 考试前三题题解
T1 数你太美【第一周】答案肯定不是一位就是两位，先扫描看是否有相同的数，没有就排序取最小的。#include<bits/stdc++.h>using namespace std;const int M=15;int a[M],b[M],n,m;bool vis[M],_vis[M];int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); vis
2020-09-12 16:30:04
186
原创 【模版】拓扑排序
概念拓扑序代表了元素之间的条件关系，拓扑排序就是用有向图无环来存储关系并求出序列。实现直接邻接表存图，当某个点入度为0，就记录并删掉与它相连的边。优先队列确保字典序最小。#include <bits/stdc++.h>using namespace std;const int M=1e6*5+5;vector<int> G[M];priority_queue<int,vector<int>,greater<int> > q;in
2020-08-21 22:24:59
148
2
原创 【模版】欧拉路
定义判定实现采用栈+邻接表#include <bits/stdc++.h>using namespace std;const int M=1e6*5+5;int Stack[M],_Stack[M],Head[M],Next[M],ans[M],ver[M],per[M],top,cnt,tot,_tot,t;int size[M],in[M],out[M];int fa[M],vis[M],_vis[M];int T,len,S;void makeset(int n)
2020-08-21 22:13:15
153
原创 野餐规划（最小度限制生成树）
题目题目描述一群小丑演员，以其出色的柔术表演，可以无限量的钻进同一辆汽车中，而闻名世界。现在他们想要去公园玩耍，但是他们的经费非常紧缺。他们将乘车前往公园，为了减少花费，他们决定选择一种合理的乘车方式，可以使得他们去往公园需要的所有汽车行驶的总公里数最少。为此，他们愿意通过很多人挤在同一辆车的方式，来减少汽车行驶的总花销。由此，他们可以很多人驾车到某一个兄弟的家里，然后所有人都钻进一辆车里，再继续前进。公园的停车场能停放的车的数量有限，而且因为公园有入场费，所以一旦一辆车子进入到公园内，就必须
2020-08-17 20:36:27
789
5
原创 北极网络（Kruskal）
题目描述国防部（DND）希望通过无线网络连接几个北部前哨站。在建立网络时将使用两种不同的通信技术：每个前哨站都有一个无线电收发器，一些前哨站还有一个通信卫星。任意两个拥有通信卫星的前哨站不论它们的位置如何，都可以通过卫星进行通信。而如果利用无线电进行通信，则需要两个前哨站的距离不能超过D方可进行通信。而D的大小取决于收发器的功率，收发器的功率越大，D也就越大，但是需要的成本也就越高。出于采购和维护的考虑，所有的前哨站都采用相同的收发器，也就是说所有前哨站的无线电通信距离D都是相同的。你需要确定
2020-08-14 00:08:55
479
2
原创 双人文字对战游戏
#include<bits/stdc++.h>#include<windows.h>using namespace std;string name1,name2;int hp1,hp2,gj1,gj2,fy1,fy2;string jin[30]={"会心一击","回复术","闪电拳","诅咒","治愈魔法","火球术","雷击术","重击","生命之轮","减速术","撞击","背刺","铁壁","吸血攻击","净化","伤害反弹盾","瘟疫","攻击","攻击","攻击
2020-08-13 23:52:46
1152
2
原创 【模版】最短路
Dijkstra+优化#include<iostream>#include<stack>#include<algorithm>#include<cstdio>#include<cmath>#include<cstring>#include<cctype>#include<iomanip>#include<vector>#include<queue>using name
2020-08-10 20:36:27
153
原创 【模版】字符串Hash
字符串哈希就是将字符串映射成数，方便操作处理for(int i=1;i<=len;i++){ hash[i]=hash[i-1]*k+(s[i]-'A'+1);//转化为k进制数 wei[i]=wei[i-1]*k;//记录数位权值}计算区间区间[l,r]的Hash值int Get_Hash(int l, int r) { return hash[r] - hash[l - 1] * pre[r - l + 1]; //pre[i]=k^i}拓展[l,mid-1]+[mid
2020-08-10 20:25:37
134
原创 【模版】欧拉函数
定义φ(N)表示N的欧拉函数。φ(N)表示小于N且与N互质的数的个数(包含1)。求法对于一个正整数N的素数幂分解N=p1q1 * p2q2 … * pn qn.φ(N)=N*(1-1/p1) * (1-1/2) …*(1-1/pn).因为容斥原理，所以1~n中除去与n拥有相同质因子的数剩下的与n互质。化简过程省略。计算上面的式子，我们只需要分解质因数。int eular(int n){ int ans=n; for(int i=2;i*i<=n;i++){
2020-08-10 20:09:57
226
1
原创 【模版】素数筛
朴素void get_prime(int n){ memset(isprime,1,sizeof(isprime)); isprime[1]=0; for(int i=2;i<=n;i++){ if(isprime[i]){ for(int j=i*i;j<=n;j+=i){ isprime[j]=0; } } }}埃筛void get_prime(int n){ memset(isprime,1,sizeof(isprime)); isprim
2020-08-10 19:40:37
134
原创 「CCO 2017」专业网络
Kevin 正在一个社区中开发他的专业网络。不幸的是，他是个外地人，还不认识社区中的任何人。但是他可以与 个人建立朋友关系 。然而，社区里没几个人想与一个外地人交朋友。Kevin 想交朋友的 个人都有类似但不同的与外地人交友的准则。在 Kevin 已经直接认识了社区中的 个人后，第 个人就愿意与 Kevin 交朋友了，否则 Kevin 就要付出 的代价与他成为朋友。你的任务是，使 Kevin 与这 个人都交上朋友，并且最小化他付出的代价。输入格式第一行包含整数 。接下来的 行每行包含两
2020-07-26 22:39:05
435
1
原创 关于vector作为二维数组使用
最近几天在学STL，总结一下。最基本的：vector<int> a;//定义一个不定长数组a数组+vector：vector<int> a[3];//定义了一个二维数组，第一维为3，第二维不定长a[1].push_back(1);//可直接压入值cout<<a[1][0];//用二维形式调用vector+vector：vector<vector<int> > a;//定义了一个二维数组，第一维不定长，第二维不定长a.resiz
2020-07-22 19:18:04
959
1
原创 分离与合体
题目描述经过在机房里数日的切磋，LYD 从杜神牛那里学会了分离与合体，出关前，杜神牛给了他一个测试……杜神牛造了 个区域，他们紧邻着排成一行，编号 。在每个区域里都放着一把 OI 界的金钥匙，每一把都有一定的价值，LYD 当然想得到他们了。然而杜神牛规定 LYD 不能一下子把他们全部拿走，而是每次只可以拿一把。为了尽快得到所有金钥匙，LYD 自然就用上了刚学的分离与合体特技。一开始 LYD 可以选择 中的任何一个区域进入，我们不妨把这个区域记为 。进入后 LYD 会在 区域发生分离，从而分离成两
2020-07-19 20:11:34
235
原创 （数位DP） 绝世好题
题目描述给定一个长度为n的数列ai，求ai的子序列bi的最长长度，满足bi&b(i-1)!=0(2<=i<=len)。输入格式输入文件共2行。第一行包括一个整数n。第二行包括n个整数，第i个整数表示ai。输出格式输出文件共一行。包括一个整数，表示子序列bi的最长长度。样例样例输入31 2 3样例输出2数据范围与提示n<=100000,ai<=2*10^9真是一道绝世好(水)题。首先是 80~90分 的做法。设dp[i] 为以 i 结尾的最
2020-06-19 23:24:36
330
1
原创 dp种树的艺术
题目描述有N棵高度不一样的树要种成一行，为了让种树更加有艺术性，制定一个种树规则，希望从左边看过去只能看到L棵树，从右边看过去只能看到R棵树，请问有多少种不同的种树方案。输入格式输入包含多组数据。首先第一行包含一个整数t，表示数据的组数。之后t行，每行包含三个数N，L，R，以空格隔开，表示树的棵数N以及从左边看过去的棵数L和从右边看过去的棵数R。输出格式共t行，每行一个数，表示每组数据所对应的种树的方案数。答案可能很大，请对 998244353取模。样例样例输入24 1 24 2 1
2020-06-11 22:11:28
250
原创 P5189 [COCI 2010] ZUMA
题目描述译自 COCI 2010.03.06 T4. ZUMAMirko 将颗弹子排成一排，依次编号为 。 号弹子的颜色为 。他发现，如果他触摸 颗连续的弹子，且这些弹子的颜色相同，魔法会使这些弹子消失；此后，这 颗弹子前面的弹子便与这颗弹子后面的弹子相邻。Mirko 家里有很多弹子，他想在这颗弹子之间（也可以在开头的弹子前面或末尾的弹子后面）插入尽可能少的弹子，使得这颗弹子+插入的所有弹子消失。输入格式第一行：。第二行：。输出格式一行，一个整数，表示他至少要插入几颗弹子。样例
2020-06-09 23:35:41
295
5
原创 忙碌(分组背包)
题目描述魔法世界历史上曾发生过多次大规模灭绝战争。例如疯狂屠杀世界人口约２亿人以至于荣登“吉尼斯世界纪录”的蒙帝国铁骑军，其幕后推手即是天顶星人。但在人类文明生死存亡之际，总会涌现出许许多多的英雄人物奋起抗争，拯救人民于水火之中。现在，抵御天顶星人进攻的重任落在了魔法学院众师生的肩上。这天墨老师安排了n组工作让楚继光完成，时间为T，每个工作组中有m个工作，每一组工作有个分类值为s，如s是0表示组内至少要做一件工作，如s是1表示组内最多做一件工作，s是2表示组内工作随意完成，每项工作均有需花费的时间和获得
2020-06-08 22:38:57
244
1
原创 三角形牧场
题目描述奶牛建筑师Hei想建造围有漂亮白色栅栏的三角形牧场。她拥有N(3≤N≤40)块木板，每块的长度Li(1≤Li≤40)都是整数，她想用所有的木板围成一个三角形使得牧场面积最大。请帮助Hei小姐构造这样的牧场，并计算出这个最大牧场的面积。输入格式第1行：一个整数N第2…N+1行：每行包含一个整数，即是木板长度。输出格式仅一个整数：最大牧场面积乘以100然后舍尾的结果。如果无法构建，输出-1。样例样例输入511334样例输出692数据范围与提示692=舍尾后的（100
2020-06-07 23:11:35
278
1
原创 偏树
题目描述告诉你有n个结点，f(i) 表示度为i的结点的凉爽值，现在你需要做的就是加 n-1 条边，构成一棵树，并使得这棵树的每个结点的凉爽值之和，即coolness最大，输出最大的coolness。输入格式第一行：一个正整数T，代表样例个数。接下来，共T个样例：n（ > 100）n - 1 个整数，代表f（i）输出格式coolness值。样例样例输入232 145 1 4样例输出519由于有n-1条边，那么，这棵树的总的度数便是2n-2，又由于每个点至少有一个度，
2020-06-06 22:53:25
242
原创 夏季特惠【第五周】
这是一道水题，板的不能再板。题目描述Steam2019年夏季促销开始了！⼩Y同学决定⼊⼿⼀些游戏，⼩Y同学⼀共有x元的预算，该平台上所有的n个游戏均有折扣，标号为i的游戏的原价ai元，现价只要bi元（也就是说该游戏可以优惠ai−bi元,每款游戏最多只能购买⼀次），并且⼩Y同学购买该游戏能获得快乐值为wi。由于优惠的存在，⼩Y作为剁⼿党可能做出⼀些冲动消费导致最终买游戏的总费⽤超过预算，但只要满足获得的总优惠金额不低于超过预算的总金额，那在⼩Y同学⼼理上就不会觉得吃亏(买到就是赚到!真⾹!)。现在⼩Y
2020-06-05 22:42:33
400
2
原创 前缀单词(好题)
题目描述一组单词是安全的，当且仅当不存在一个单词是另一个单词的前缀，这样才能保证数据不容易被误解。现在你手上有一个单词集合，你需要计算有多少个子集是安全的。注意空集永远是安全的。输入格式第一行一个数表示集合的大小，以下n行。每行一个由构成的字符串。输出格式安全子集的个数。样例输入 #13hellohellhi输出 #16首先：设dp[i]表示前i个集合以i结尾的集合数核心代码：dp[i] = dp[j]（1<=j<i且a[i]与a[j]不互为前缀）+ 1 (原
2020-06-05 22:28:23
281
原创 最长公共上升子序列
1.O(n*m2)比较好理解，不展开叙述。状态转移方程为 :①F[i][j] = F[i-1][j] (a[i] != b[j])②F[i][j] = max { F[i-1][k] }+1 (0<k<j&&b[K]<b[j]) = max { F[i-1][k] }+1 (0<= k< j&&b[k]<a[i])上代码#include<algorithm>#include<cstdio>using
2020-06-05 22:19:04
166
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人