- 博客(44)
- 收藏
- 关注
RSS订阅原创 【无标题】test test
欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能，丰富你的文章UML 图表FLowchart流程图导出与导入导出导入aMarkdownText-to-HTMLAuthorsJohnLuke。
2022-08-21 20:24:18
97
1
原创 【UNSW】COMP9024 Assignment - Word Sequences
添加链接描述/*Stage 4(Task 1) 1. Set up a DAG graph by treating words as vertices and adjacent words as edges. Time complexity: O(n*n*m)(Task 2) 1. Using the idea of dynamic programming, inverse topological order and recursively solve the dp[] array
2021-11-17 22:16:42
469
原创 2021-09-06 分类 - K最近邻算法
#K最近邻算法 - KNN, kNearestNeighborimport numpy as npimport pandas as pdfrom sklearn import neighborsdic1 = {'id':[0,1,2,3,4,5,6,7,8],'yvwen':[72,66,89,81,86,91,86,89,94],'shuxue':[92,81,80,79,68,79,74,78,61], 'ClassifyResult':[3,3,2,2,1,1,1,1,1]}df = p..
2021-09-06 20:02:46
103
原创 *******
*******高考语文不及格，但是我还是想写写我的感受哈哈。比赛前一天，三个人兴致勃勃地参加了热身赛，拿了83名，本以为可以水个铜牌的样子。然后铁了… 果然，能够参加区域赛的都是些大佬。比赛前准备了两天的板子，结果真的没用上233，签到题出的有点慢，当时心态有点炸了，乱了阵脚，之后看到榜上无数人A了C题，转去看C，结果……就这样卡了将近四个小时，推不出式子来，数据都不对更没法交。推C题的这段...
2018-10-22 14:11:24
1477
原创 ZOJ - 3822 Domination （2014 牡丹江）概率dp
2014牡丹江区域赛的铜牌题，然而我想了好久都没想出转移方程……希望这个月的区域赛能搞到一个牌子吧n×m的方格，在这些方格里放石子，求使得方格的每行每列都有石子的期望个数。首先很容易想到先求出取k个石子的概率，然后根据公式求期望。开始想用三维 dp[n][m][k] 表示到第n行m列为止放k个石子的概率，结果递推式怎么也推不出来，后来看了题解才知道，dp[n][m][k] 表示的是k个石子占...
2018-10-01 17:07:24
179
原创 2017中国大学生程序设计竞赛-哈尔滨站
2017中国大学生程序设计竞赛-哈尔滨站去年哈尔滨现场赛的题目，只补了四道。 区域赛题目真的好难啊…… 补题链接：https://vjudge.net/contest/198451F - Permutation 构造给出n，构造出满足 pi≡0(mod|pi−pi−2|)pi≡0(mod|pi−pi−2|)pi≡0(mod|pi−pi−2|) 的一个长度为n的排列，注意是排列，不能...
2018-08-29 19:05:47
442
原创 socket 套接字
#include<stdio.h>#include<stdlib.h>#include<unistd.h>#include<string.h>#include<sys/types.h>#include<sys/socket.h>#include<netinet/in.h>#include<
2018-05-09 11:24:47
166
原创 Asp.net 学习资料
https://www.cnblogs.com/powertoolsteam/p/MVC_one.html保存一下吧，一个写的挺好的教程，mvc老师讲的听不懂 c#不会写 html 看不懂 TUT菜。。。
2018-04-16 20:38:30
1125
原创 概率DP种类问题 UVA - 10648 && CodeForces - 768D
最简单的例子UVA - 10648 题意：有n块巧克力，m个盒子，巧克力随机放入其中的一个盒子，问至少有一个盒子为空的概率。这时我们就要求m个盒子全满的概率，答案为1减去这个概率。当要放一个巧克力时，只有放在已经有巧克力的盒子和放在没有巧克力的盒子两种情况。所以i个巧克力放在j个盒子的概率就等于i-1个巧克力放在j个盒子的概率加上i-1个巧克力放在j-1个盒子的概率。所以状态转
2018-01-31 10:44:35
158
原创 CodeForces - 616D 尺取法 two pointer
题意：找到一个长度最长的含有最多k个不同数字的序列，输出它的坐标尺取法，比赛的时候觉的是二分。。然后T9。。之前没有做过尺取法的题目，大佬们都好厉害啊TUT，赶紧补一发尺取专题TUT#includeusing namespace std;const int N=512345;const int M=1123456;int vis[M],a[N];int main(){
2018-01-20 09:47:19
211
原创 Pyhon 2.7 环境搭建
Python 2.7 Windows 下载地址↑ 在这里下载安装点击：此电脑→属性→高级系统设置→环境变量把系统变量PATH后面加上C:\Python27\ 和 C:\Python27\Scripts\ Python27为下载到的文件夹如果原来PATH里面有别的环境变量，追加到后面就可以，用分号间隔开打开cmd窗口 输入 python 就说明配置好啦~ 嘿嘿
2018-01-06 17:38:46
156
原创 908B New Year and Buggy Bot
题意 ： 0-3代表四个方向，一共24种映射情况，求一共有几种可以从S到达E然后有一个神奇的函数，next_permutation(a,a+n); 返回值是bool类型，表示比a序列的下一个序列。用do-while()循环可以输出包括第一个排列在内的所有的排列。代码：#includeusing namespace std;const int N=123;char s[
2018-01-01 11:31:33
238
原创 Java 接口实现
嗯。。快期末考试了，预习Java开始。/(ㄒoㄒ)/~~一个类可以遵循多个接口，但必须实现接口的所有方法，不然会报错。定义一个接口 ：[public] interface InterfaceName { function1(); function2(); . . .}而某一个类要遵循一个接口需要使用implements关键字class ClassName
2017-12-25 10:50:59
490
原创 URAL - 1081 Binary Lexicographic Sequence (DP)
题意：1和1不能相邻，找出第k小的长度为n的序列0前面可以是0或者1,1前面只能是0 。 根据这一点可以写出递推公式：dp[i][0]=dp[i-1][0]+dp[i-1][1]; dp[i][1]=dp[i-1][0];dp[i][0]记录末尾为0的序列的个数，dp[i][1]记录末尾为1的序列的个数。每次编码的时候判断当前位是否可以为0，产生的排列数和k比较#include
2017-12-20 14:50:01
175
原创 UVA - 11420 Chest of Drawers (DP)
题意：有一个抽屉是竖着排的，给出抽屉的格数n和需要保证安全的抽屉数量s 一个抽屉安全的条件是它的上一层抽屉必须是上锁的。之前个人赛做过一个差不多的题，dp[i][j][0]代表i个抽屉保证j个抽屉安全且最下面一个抽屉的状态为L,dp[i][j][1]最下面一个抽屉状态为U。写出递推式就可以了。，对于一个抽屉只有两种情况U和L∴ 分两种情况讨论： ①最后一个抽屉状态为L，要保证
2017-12-20 11:46:57
306
原创 HDU - 3917 Road constructions 最大权闭合子图
论文:最小割在信息学竞赛中的应用最大权闭合子图的求法 ：源点向正权连边，原图容量为INF，负权点向汇点连边，权值为绝对值。 最大权闭合子图的值 = 正权和 - 最小割(最大流)题意：n个工程，m个公司，第二行给出m个公司向政府缴纳的税款（正权），k个公司，接下来k行表示工程的起始点，工程由哪个公司负责以及工程的补贴（负权）。求政府获得的最大利润是多少。套用一下就得到答案了。
2017-12-19 17:28:42
161
原创 HDU - 3879 Base Station 最大权闭合子图
最大权闭合子图：在一个图中，我们选取一些点构成集合，记为V，且集合中的出边(即集合中的点的向外连出的弧)，所指向的终点(弧头)也在V中，则我们称V为闭合图。最大权闭合图即在所有闭合图中，集合中点的权值之和最大的V，我们称V为最大权闭合图。图中最大权闭合子图为{3,4,5}题意：有n个城市，每个城市可以花费p[i]修建一个通信站，如果a和b都建了通信站的话就可以得到c的利润，
2017-12-18 20:16:08
150
原创 HDU - 3452 Bonsai 最小割
给出一棵无向树，要求把根节点和叶子节点分割开的最小权值最大流最小割板子题，源点题目中已经给出，需要添加一个汇点。再添加叶子节点与汇点的边，权值为INF#includeusing namespace std;const int N=3234;const int M=1123456;const int INF=0x3f3f3f3f;int n,m;struct node{
2017-12-18 16:40:34
150
原创 HDU - 6214 最小割的最小割边
上个月青岛网络赛的题目，看了半天博客愣是没看懂。。。然后查了好久的资料TUT最大流-最小割的定义：最大流最小割定理是网络流理论的重要定理。是指在一个网络流中，能够从源点到达汇点的最大流量等于如果从网络中移除就能够导致网络流中断的边的集合的最小容量和。即在任何网络中，最大流的值等于最小割的容量。通过最大流sap算法求出来的是最小割的边权和，而不是边数。所以令w=w*(E+1)+1 求出
2017-12-18 15:57:24
233
原创 LightOJ - 1265 Island of Survival
深切感觉自己的智商不够用。。TUTTUT 表示自己连题目是什么意思都搞不明白。。题意我就不多说了吧。。一共有几种情况，虎虎、鹿虎、鹿鹿、人虎、人鹿。所以只有人想要生存下来，必须所有的虎同归于尽，老虎必须是奇数。剩下就是求老虎同归于尽的概率了。每天出现两个生物。 所以每天两只老虎相遇的情况为(t-1)*t 种，所有的情况为t*(t+1)种。概率p = (t-1)/(t+1
2017-12-11 15:58:00
200
原创 LightOJ - 1248 Dice (III)
概率DP题意：给出一个骰子有n面，求出骰子每一面都出现的期望。递推公式 dp[i] = (i/n)*dp[i-1] + (n-i/n)*dp[i+1] +1 ;化简得 dp[i] = dp[i+1] + n/(n-i);#includeusing namespace std;int main(){ int t; scanf("%d",&t); int Case=0;
2017-12-10 16:52:27
186
原创 LightOJ - 1151 Snakes and Ladders (高斯消元+概率DP)
题意：10*10的方格，每掷一次骰子向前走相应的步数，给n组数，x,y 表示从x可以到直接传送到y。可以直接简化为1*100的模型，网上的一些递推公式看不太懂。每次掷骰子的时候跟前几个题是一样的，dp[i] = dp[i+1]/6 + dp[i+2]/6 + … +d[i+6]/6 +1 ; 不过要注意下边界。化简一下就可以得到 6*dp[i] - dp[i+1] - … -dp[i+6] =
2017-12-10 15:43:19
292
转载 高斯消元 kuangbin
#include#include#include#include#includeusing namespace std;const int MAXN=50;int a[MAXN][MAXN];//增广矩阵int x[MAXN];//解集bool free_x[MAXN];//标记是否是不确定的变元/*void Debug(void){ int i, j
2017-12-10 11:56:14
110
原创 LightOJ - 1030 Discovering Gold
题意：谷歌翻译的挺好我就不解释了吧= =要用到dp递推公式 : dp[i] = dp[i+1]/6 + dp[i+2]/6 + dp[i+3]/6 +dp[i+4]/6 + dp[i+5]/6 + dp[i+6]/6 + a[i] ;因为第一个点一定要走，所以要倒着推。代码：#includeusing namespace std;const int N=233;
2017-12-09 20:20:20
146
原创 LightOJ - 1027 A Dangerous Maze
题意： 给出n个数，正数为出去的时间，负数为选择该门回到起点的时间，求出出去的期望。p1 为正数的概率，p2为选择负数的概率，T1为选择正数后平均T1分钟出去，T2为选择负数后平均T2分钟回到原地。于是有了下列式子，化简一下就是结果。#includeusing namespace std;const int N=1123;int a[N];int mai
2017-12-09 19:37:52
125
转载 PAT考试重点真题选做
原文链接：http://blog.csdn.net/u013752052/article/details/52708470因为PAT考试真题有100多道，这里选取我做过的一些题目作为样例，以供大家学习参考。附件PAT.tar.gz中即为源码和注释，妈的狗日CSDN还不让传点小文件了还，改为百度盘分享链接https://pan.baidu.com/s/1c2eaDt2，万
2017-12-08 09:43:20
1833
原创 CodeForces - 107B Basketball Team (组合数学)
这个破题气死我了。。一整场比赛卡这一道题，式子推的都对，没考虑到组合数上边那个数相等的话可以约分。 还是数学没学好啊TUT 根本就没看出是可以约分的。TUTTUTTUTTUTTUT#includeusing namespace std;const int N=123;int a[N];int main(){ int n,m,h; scanf("%
2017-12-04 17:35:50
268
原创 CodeForces - 248C （几何）
几何问题，一晚上没看懂什么意思。。。需要用到点到直线的计算公式，d=|(Ax0+By0+C)/sqrt(A*A+B*B)| 直线Ax+By+C=0 点P (x0,y0)不是很会用那个画图工具，TUT然后截屏了。。。。。。TUTTUT代码 ： #includeusing namespace std;int main(){ double a,b,c,x,y
2017-11-30 09:41:24
314
原创 CodeForces - 847B Preparing for Merge Sort
我就很好奇，为什么会有二分这种操作。。非常好奇，鬼能看出来他最后那个数字是递减的啊= =；然后迷之超时。然后看了一下lower_bound()的用法，这个序列是递减的，而一般lower_bound()查找的都是从小到大排序好的序列，所以只需要在最后面加一个greater()就可以了。像这样：lower_bound(a,a+n,greater())-a; 头文件#include
2017-11-27 19:13:37
186
原创 PAT 1099. Build A Binary Search Tree (30)建立二叉排序树
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:The left subtree of a node contains only nodes with keys less than the node's key.The right subt
2017-11-23 16:25:49
117
原创 PAT1049. Counting Ones (30)数1问题
The task is simple: given any positive integer N, you are supposed to count the total number of 1's in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1's i
2017-11-19 20:22:52
141
原创 PAT 1107. Social Clusters (30)
When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A "social cluster" is a set of people who have some of th
2017-11-19 15:26:23
122
原创 1097. Deduplication on a Linked List (25)
给定一个带整数键值的单链表L，本题要求你编写程序，删除那些键值的绝对值有重复的结点。即对任意键值K，只有键值或其绝对值等于K的第一个结点可以被保留。同时，所有被删除的结点必须被保存在另外一个链表中。例如：另L为21→-15→-15→-7→15，则你必须输出去重后的链表21→-15→-7、以及被删除的链表-15→15。输入格式：输入第一行包含链表第一个结点的地址、以及结点个数N（5
2017-11-15 21:04:32
114
原创 PAT 甲级 1041 Linked List Sorting (25)
时间限制 1000 ms内存限制 65536 KB代码长度限制 100 KB判断程序 Standard(来自小小)题目描述A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure
2017-11-15 19:38:46
159
原创 PAT 1056. Mice and Rice (25)
题目描述Mice and Rice is the name of a programming contest in which each programmer must write a piece of code to control the movements of a mouse in a given map. The goal of each mouse is to eat as mu
2017-11-13 20:04:12
107
原创 最大流板子（Sap）
根据kuangbin巨巨最大流Sap的板子改的。但是，，，，为什么我写了这么多的题。。还是没记住= =!?等有时间打印一下，，有时间。。。。时间。。#includeusing namespace std;const int N=234;const int M=500010;const int INF=0x3f3f3f3f;int n,m;struct node{
2017-10-21 19:57:44
233
原创 HDU - 6214 Smallest Minimum Cut
2017青岛网络赛的题。。当时刚学了连通图，比赛的时候看到了割边，怎么想怎么是连通图，明明是最小割= =？题目就写着最小割？？好吧我还是知道的太少了。。现在学网络流看到了最小割的题目，从HDU的problem里面从后往前翻了好久，终于找到了。。最小割最少割边的裸题。。建边的时候每条边的边权w=*(m+1)+1 最大流maxflow*/(m+1) 最少割边数maxflow%(m+
2017-10-21 19:43:39
132
原创 HDU - 2883 kebab
和上一道题差不多，都是时间的最大流。 时间段的取值很大，所以加一个t数组离散化一下。#includeusing namespace std;const int N=1005;const int M=100010;const int INF=0x3f3f3f3f;struct node{ int u,v,cap,next;}eage[M];int head[N];
2017-10-20 15:36:09
146
原创 HDU - 3572 Task Schedule
建图好难 。。。想了好半天TUT，最后看博客看会的，，题意：n个任务，m台机器 每个任务有消耗时间p，开始时间s，结束时间e，问能不能完成所有的任务。这个建图真的不好想。。首先，因为我们要完成所有的任务，每个任务都有一个时间，所以就要判断完成这些任务的时间够不够，所以最大流跑的是时间。建立源点，源点指向每一个任务，权值为这个任务耗费的时间，每一个任务又指向任务对应的每一个时间点权
2017-10-19 20:12:05
170
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人