灯又烬

分类

学习笔记(4) 未归档(2) 算法总结(2) 题解(27)

/ 注册

TA的专栏 12篇文章 0人订阅

10篇文章 908人学习

2篇文章 899人学习

全部文章（共35篇）

New个专栏~ 来自专栏

大三临退役才开始想搞这些东西，未免晚了点，但是菜鸡还是要有梦想嘛，这个专栏就更新一些题解好了，偶尔写写cf题解，和自己刷题的结果吧。希望对自己有帮助，也希望能对读者有点帮助（虽然博主又菜语言组织能力又差）。更新：cf第二天必更，其他佛系更。

2020-10-03

1 465

New个新专栏~ 来自专栏

疫情在家期间颓废了n个月后，不知不觉就大三了，今天发现牛客可以建专栏了，就寻思把之前学到的一些算法知识之类的东西做个总结，希望记录一下学过的知识，看看自己几斤几两，也希望能留些有用的东西能帮到一些人吧。关于更新，希望自己能严格遵守每天都更新吧，但是对自己的毅力还真没信心...加油吧，为了给自己的人...

2020-10-03

1 567

网络优化 [贪心]

题意游戏***有n名用户，编号从1到n，服务器共有m条服务线，每个用户最多只能登陆一条线，第i条线最多可以容纳v[i]名用户同时在线，且只能给编号在[l[i],r[i]]范围内的用户提供服务。现在希望找出一种合理的资源分配方案，使得同时在线人数最大化，请输出这个最大人数。题解看了一眼数据范围 ...

2020-09-30

6 799

[SCOI2009]最长距离 [最短路]+[建图]

题意给出n*m的图，每个格点为1或0，1代表到此格点是一个障碍物.在可以移除t块障碍物的条件下。问所有互相可达的两点中，欧几里得距离最大的为多少。题解百度搜了一下原题数据范围才敢写....数据范围是<=30所以最多只有30*30=900个格点，可以求出每两点最少经过多少个障碍物后，枚举两...

2020-09-25

1 732

Codeforces Round #672 (Div. 2) A-D

A 题意给出长度为n的数组，问是否可以经过不超过次交换相邻两值排序使该数组递增。题解我们知道冒泡排序的最坏情况复杂度即为，故只有在最坏情况下，即整个数组为严格递减序列时才能达到次交换，所以只需要判断数组是否严格递减即可。 code #include <bits/stdc++.h> ...

2020-09-25

1 690

[HAOI2008]硬币购物 [dp]+[容斥]

题意硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。题解一眼看去一个多重背包dp...再一眼看去数据范围..1e5这样暴力背包就t了.可以转换想法，假设硬币的枚数没有限制，这样在每一组...

2020-09-24

0 679

迷宫 [dp]

题意牛牛可以在n*m的图中向右走或者向下走，每个点有一个权值，经过某点获得该点权值并对1e4+7求模，问从(1,1)走到(n,m)，在(n,m)点存在多少种权值情况。题解设一个dp三维布尔数组，dp[i][j][k]表示从(1,1)走到(i,j)点是否在(i,j)点可以产生k的权值。易知转移方...

2020-09-21

0 686

树上行走 [dfs]

题意在树上存在n个点，每个点为两种状态之一，两种状态的点之间无法相互抵达，求树上最大的可联通子树，并按递增顺序输出所有节点，若有多棵子树最大，将所有子树节点均排序输出。题解对树进行dfs，每次求一颗子树大小，并将其所有节点标记，遍历过程记录子树个数与其所有节点，最后找到最大联通子树将所有最大子...

2020-09-20

2 800

上学要迟到了 [dijkstra]

题意（啊好难总结复制了）去学校只有两种方式，坐公交车和步行，牛牛去学校是一条直线，这条直线上总共有n个车站，车站之间的距离都是相等的，每个车站只有一种公交车ai，每个公交车只在对应的公交站停车，第i种公交车过一站的时间需要ti，并且公交车是单向行驶，只能从左到到右，走路可以任意走，然而牛牛自己步行...

2020-09-20

1 590

牛牛和字符串的日常 [kmp]

题意给出一个模板串和n个字符串，设每个字符串的权值为其字串中模板串前缀的长度，求n个字符串中最大权值和。题解前置知识:kmp使用kmp的next数组即可，在两串匹配过程中不断更新j指针能在模板串中到达的最远位置，即为能匹配的最长前缀。将n个字符串逐个匹配取最大值加和即可。 code #incl...

2020-09-20

3 714