- 博客(163)
- 问答 (1)
- 收藏
- 关注
RSS订阅原创 acwing 1221 四平方和
题目思路就是建立一个哈希表，记录c2+d2c^2+d^2c2+d2的c、d值，然后查表就可以了#include<iostream>#include<map>using namespace std;const int MAX=5e6+5;int n;pair<int,int> a[MAX];int main(){ cin>>n; for(int i=0;i*i<=n;i++) { for(int
2022-04-08 21:11:15
408
原创 错位排列总结
首先从这个问题开始：有nnn 个人以及 nnn 顶帽子，每个人任意选取一顶帽子，求至少一个人拿对自己帽子的概率。1. 推导记事件AiA_{i}Ai为“第iii个人拿对了自己的帽子”,i∈[1,n]i\in[1,n]i∈[1,n]则所求概率为P(A1∪A2∪......∪An)P(A1 \cup A2 \cup ...... \cup An)P(A1∪A2∪......∪An)由P(A1)=P(A2)=...=P(An)=1nP(A_{1})=P(A_{2})=...=P(A_{n})=\frac{
2022-04-08 14:55:03
1242
原创 AtCoder Regular Contest 084
题目我们考虑如何搜索。很明显，我们以1为起步变成其他数字有两种方法，分别是x+1和x10，x+1是变新数字不进位的方案，进位的时候，我们为什么不从某一个状态10呢？大概思路有了，然后我们要做的就是把状态压缩到k以内，我们可以考虑对每一个x对k取模，为什么可以这么做呢，既然我们只有+和*两种方案，超过k的时候必须要从比k小的状态转移过来，取模并不影响答案，就这么做可以了。#include<cstdio>#include<algorithm>#include<iostrea
2021-11-02 00:11:52
132
原创 acwing 1247
题目其实一开始想对了，就是无论是+负数还是-正数，统统塞进-（xxxxx）里，不用分那么多类情况，归约起来其实就两种情况，有没有负号。#include<iostream>#include<string>#include<cmath>#include<vector>#include<algorithm>#define int long long#define IO ios::sync_with_stdio(false),cin.tie
2021-10-20 11:48:26
82
原创 atcoder regular 111 B
题目可以把这题，每张牌的两个颜色看作图的两个端点（一个颜色一个端点），然后每次取一种颜色，其实就是每条边只能取一个结点，问最后最多能取几个结点。我们可以发现，只要图的连通块，存在一个环，那么这个连通块所有结点都能选上。树的话就只能取n-1个，因为每条边只能选一个结点吗。所以只需要找出所有连通块，对边数和结点数取min就可以了。#include<cstdio>#include<algorithm>#include<iostream>#include<cstr
2021-10-09 10:43:39
98
原创 codeforces 742 div2 E
题目当时没想到区间合并怎么弄，这个题好好学了一次。#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<sstream>#include<queue>#include<list>#include<bitset>#include<stack&
2021-09-24 14:26:25
66
原创 codeforces global round 16 E
题目思路总体和我想的差不多，就是当时想的有一点问题。做法很简单，就是把树拆开，拆成一个一个bud，然后根据样例可以发现，每一个bud都可以去掉一个叶节点，最无论如何总有一个减不掉的，就这么求就行。#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<sstream>#include<
2021-09-24 14:15:38
58
原创 openjudge 4132 表达式求值 递归下降
题目以前不想用栈写表达式求值，代码都不想看，现在专门学了编译原理来写一下。原理百度就有了。好久没用openjudge了，这个oj的编译器是真的傻逼。/*#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<sstream>#include<queue>#include&
2021-09-23 11:11:28
85
原创 atcoder beginner 214 E
题目这玩意居然还能用并查集来做。首先贪心的想，每个球我们能往左边放就往左边放，那么我们就能尽可能的腾出位置了。那我们怎么知道这个球所能放的最左边的位置呢，我们可以用并查集来维护。设fa[x]为x这个位置能不能放，不能放的话fa[x]将告诉你最左边能放的位置在哪。具体怎么维护看代码就可以了。#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include&l
2021-08-26 00:45:43
69
原创 atcoder beginner 200 D
题目首先呢，每个数选与不选，总共有2^n-1种选数方案（因为除去所有不选），题目中给出一个要求，所有数的和%200相同，这个有什么用呢？我们总共2的n-1种选数方案，理论上说我们会有2的n次方-1种结果，那%200，就相当于把这么多结果放到200个盒子里，那我们就可以想到鸽巢原理。所以我们可以直接爆搜，反正最多两百种情况。#include<cstdio>#include<algorithm>#include<iostream>#include<cstrin
2021-08-24 01:12:04
261
原创 codeforces 734 div3 E
题目这题我们用dp，我们可以把状态设为dp[i][j]dp[i][j]dp[i][j]为前i个数字，去除j个以后能满足题目要求的个数。难点就在于吧点数删掉了，应该怎么转移。我们可以想到，我们设某个点的位置为pos，那删除了j个点，新的位置就应该为pos-j，然后就可以转移了。转移方程直接看代码就行。#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#inclu
2021-08-17 23:01:41
82
原创 2021-08-03
题目这题主要是采用其他搜索顺序，我们平时是像洪水填充那样搜完一个连通块，但这个不行，我们可以采用每次都找整副图的方法，每次找一个点，然后判这个点是否连通就可以了。这样凑满五个点，重复的话我们可以使用状态压缩判重，就这样就可以写dfs了。#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<sst
2021-08-03 22:03:45
48
原创 AtCoder Beginner Contest 212 D
题目傻了，其实就像noip2017蚯蚓那题维护就行了。那怎么取最小呢，就用优先队列呀，干嘛一定要用队列呢，那对所有元素add该怎么办呢，那就对所有后面来的元素都减呀，根据相对论，我不动，你减，那不就等于我加了嘛。#include<bits/stdc++.h>#define rep(i,n) for(int i=0;i<(int)n;i++)#define fr first#define sc second#define P pair<int,int>#define
2021-07-31 22:50:31
61
原创 codeforces 611 div3 E
题目首先这题我们要输出两个答案，最大和最小，应该怎么做呢？首先我们考虑最小，我们可以这么想，如果某个位置xxx有人，那么[x,x+2][x,x+2][x,x+2]这三个位置都可以放到x+1x+1x+1位置当中，这样贪心就是最小了。那最大应该怎么办呢，对于某个位置，如果它的位置大于1个人，且左边有空位的话，那就让一个人过去呗，右边同理，能占则占，感觉和D差不多。然后这题就完成了，不懂的看一下代码就差不多懂了。#include<cstdio>#include<algorithm&g
2021-05-12 10:33:19
71
原创 codeforces round 717 div2 D
题目这题一步一步来想，暴力的话我们该怎么做。对于每个区间l，r，我们以r为起点，往左一个一个试，看看当前这个数在划分的区间内是否与区间所有数互质，不互质直接新划分一个区间，否则继续往左找。下面我们考虑怎么加速这个过程，首先就是如何判断某个数x和一堆数（设这堆数的集合为s）是否互质。这个我们可以这么做：设集合s所有数的质因子的集合为ss，然后对x进行质因数分解，看看是不是x的所有 质因数都不在ss里面，是的话就互质，不是就不是互质。然后设dp[i][j]dp[i][j]dp[i][j]为j这个位置，往左
2021-05-10 19:40:31
83
原创 2021年北京理工大学ACM CLUB清明节组队训练赛 G Generator Grid
题目思路很简单，玩玩两个样例大概就知道可以贪心+并查集了，一开始写复杂了，其实代码简单的一匹。#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<sstream>#include<queue>#include<list>#include<bitset&
2021-04-29 17:31:36
169
原创 buuctf 新年快乐 ESP定律脱壳
查壳，发现是upx壳。我们可以直接使用脱壳机，这里使用ESP定律手动脱壳。打开IDA，发现根本分析不了：把程序拖入x32dbg，点击选项->首选项：至少选择这两个断点，否则不知道停在哪个地方。第一行就是pushad。按F7，进入到下一行，然后发现ESP已经变了。右击ESP的数字，点击在转储中跟随，右击第一行，选择断点，“硬件，存取”，双字。然后按F9继续运行。已经到了popad的位置。继续调试或者根据经验可以发现，00401280就是OEP。点击插件->Sc
2021-04-02 08:51:13
320
转载 idapython 攻防世界 no strings attached
https://blog.csdn.net/weixin_43281394/article/details/112341592
2021-03-31 22:24:22
120
原创 2021 MAR-DASCTF drinksometea
新手第一次见这种题，记录一下压缩包给了一个exe还有一个png.out，那个png.out不知道干嘛用的。查一下exe有无加壳，无，拖入ida进行分析。程序流程不难，就是先从tea.png读入数据，然后经过中间的函数处理，然后把输出输出到tea.png.out。题目要我们做的就是，用那个out文件，还原出png文件进入4010A0函数，发现ida根本分析不了：原来这就是传说中的花指令。看了别的大佬博客才知道，对于00401116，有红色的这行语句按U，然后在Hex-view那里，把那行数据
2021-03-31 22:22:32
635
1
原创 2021 Nepctf worrrrms
这题挺有意思的先是压缩包，一解压就说文件不是压缩文件，不知道干嘛了，重新下载了一个才行。解压后，拖入ida打开，发现是go语言，看不懂。然后百度一下，可以安装插件，IDAGolangHelper，谷歌百度一下就有了，安装好，再去看看。发现Go语言函数名都恢复了，虽然代码一点也不可读，但至少看着稍微顺眼一点点吧……然后找啊找，找了很久，在worrrrms_puzzle_ChkPlz 和worrrrms_puzzle_Gotcha找到了key和word，然后乱试，就把flag搞出来了。由于pysm4
2021-03-29 21:48:51
208
原创 攻防世界——新手区——re1
题目这个嘛，拖进IDA然后F5，找到一个类似字符串常量的东西。然后学到了一招，见到什么xmmword和qword的直接按R就可以让后面的xxxxxxxxh变成字符串了，但是好像顺序有点乱，把他们倒序然后乱搞试多几下就可以了...
2021-03-11 21:42:19
172
原创 atcoder beginner 194 D
题目题解，感觉这题的官方题解比搜到的好多了#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<sstream>#include<queue>#include<list>#include<stack>#include<bitset>
2021-03-09 11:02:24
102
原创 atcoder beginner 185 E
题目开始练dp了。设dp[i][j]dp[i][j]dp[i][j]为第一个字符串前i个和第二个字符串前j个，我们只有四种决策，i选j删除，i删除j选，i删除j删除，i选j选，很明显第三种根本没用的，所以我们只选其他三种决策就行。#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<sstre
2020-12-14 23:12:53
74
原创 牛客练习赛73 C D
题目C首先，这类题肯定就是算贡献的了，那我们应该怎么算呢？首先，mex的值必定为1~n+1里面的数，毕竟它只有n个数。对于每一个可能的mex值，我们可以这么考虑，设这个值为x，那么[1,x−1][1,x-1][1,x−1]的值必须全部选上,x不能选，大于x的数随便选，然后统计答案就可以了。#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include&l
2020-12-09 17:11:37
129
原创 牛客巅峰赛第六场 钻石B青铜C
题目设dp[i][j][k]dp[i][j][k]dp[i][j][k]为选了前n个音符且m个重音符，第i个音符是否为重音符，k=1是，0不是。那么就可以直接转移了，注意一点细节，当m=1时，只从m=0转移过来，因为第一个可以随便放的。class Solution {public: /** * * @param n int整型 乐谱总音符数 * @param m int整型 重音符数 * @param k int整型 重音符之间至少的间隔
2020-12-05 01:09:19
80
原创 牛客练习赛 13 D E F
题目D首先，13！已经超范围了，所以我们只需要对最多最后13位进行康托展开就行。2 3 4的康托展开我们可以映射为1 2 3进行，其他类推，然后就可以写代码了。#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<sstream>#include<queue>#incl
2020-12-02 20:58:28
81
原创 codeforces 776C
题目这题其实就是，区间长度为x的区间个数，然后我们枚举x就可以了……#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<sstream>#include<queue>#include<list>#include<stack>#include&l
2020-11-20 17:18:23
96
原创 2020蓝桥杯国赛填空题——4
题目这题一开始是想的dp，但是不知道本质不同该怎么处理。后来经过队友的讲解，我们可以设dp[i]dp[i]dp[i]为以i结尾有多少个本质不同上升子序列，我们手玩一下样例可以发现，对于k<j<i，若s[i]>s[j]，那么s[j]>s[k]也会包含在s[j]里面，根据这个，我们可以贪心地想，如果s[i]>s[j]&&s[i]>s[k]&&s[j]==s[k]，我们只需要统计s[j]的答案就可以了，因为字符在后面，能统计的字符更多。#i
2020-11-19 16:58:01
179
原创 计蒜客 数正方形
题目设dp[i][j]dp[i][j]dp[i][j]为i，j这个位置为左上角，能找到的最长正方形边长。我们可以这样考虑，只要在正方形面积里面，没有任何0就可以了。那我们就有这么一个转移方程：dp[i][j]=min(dp[i+1][j],dp[i][j+1],dp[i+1][j+1])+1dp[i][j]=min({dp[i+1][j],dp[i][j+1],dp[i+1][j+1]})+1dp[i][j]=min(dp[i+1][j],dp[i][j+1],dp[i+1][j+1])+1可以这
2020-11-19 14:45:27
101
转载 Atcoder Beginner 181 E
证明：这里#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<sstream>#include<queue>#include<list>#include<stack>#include<bitset>#include<cmath
2020-11-11 23:42:03
73
原创 luogu 2663
题目这题一开始用二维费用模板套上去，wa了，为什么呢？我们想想，二维费用背包dp[v][m]状态设计的是体积不超过v以及重量不超过m的最大收益，看回这题，这题明确要求要从全班同学中选出一半，固定了数量，而不是不超过某个数，所以直接套背包模板不大行了。那我们可以这么做，考虑dp[i][j][k]为前i个同学中用了j个同学，是否能到达k分，用可行性背包去做这题。然后转移就可以啦。#include<cstdio>#include<algorithm>#include<i
2020-11-06 13:27:59
94
原创 牛客 网易笔试题 重排数列
题目链接找规律。我们可以发现，只要一个数是四的倍数，它乘以任何一个数都是的倍数，只要有两个2的倍数相乘，它也可以组成四的倍数。所以我们可以这么想，一个四的倍数可以带走两个位置，一个2的倍数只能带走它本身，只要能带走所有的数，这道题就完成了。#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<
2020-11-05 15:22:02
127
原创 浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛（同步赛）
A平时这种题，直接开个1e8的数组去存，然后就是一个除法的问题了，但这次我们的数组开不了这么大，那该怎么办呢？那我们是不是可以，只存一部分数据，剩下的数据再从一个起点开始，直接暴力求解。然后就很好做了。#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<sstream>#inclu
2020-11-05 15:07:58
248
原创 PTA 整除光棍
一开始以为有啥数学解法，但我没想到……直接高精度就过了。这种题也可以骗分，int128过了三个点。#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<sstream>#include<queue>#include<list>#include<stac.
2020-11-05 14:48:38
98
原创 2020蓝桥杯省赛B组第二轮 H 字串分值
【问题描述】对于一个字符串 S，我们定义 S 的分值 f (S ) 为 S 中出现的不同的字符个数。例如 f (”aba”) = 2， f (”abc”) = 3, f (”aaa”) = 1。现在给定一个字符串 S [0::n − 1]（长度为 n），请你计算对于所有 S 的非空子串 S [i:: j](0 ≤ i ≤ j < n)， f (S [i:: j]) 的和是多少。【输入格式】输入一行包含一个由小写字母组成的字符串S。【输出格式】输出一个整数表示答案。【样例输入】aba
2020-10-28 23:55:45
426
原创 atcoder beginner 178 D
题目设dp[i]dp[i]dp[i]为和为i有多少种方式，然后dp就可以了……蠢了，居然没想到#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<sstream>#include<queue>#include<list>#include<stack&g
2020-10-24 22:12:29
129
1
原创 2020牛客国庆集训派对day4 F
题目对于每一个位置，统计一下它移到上升那边和下降那边分别需要多少次，然后贪心取个最小值，就可以了。#include<cstdio>#include<algorithm>#include<cstring>#include<iostream>#include<vector>#include<cmath>#include<map> #include<string>#include<queue&
2020-10-04 18:54:17
782
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人