灯又烬

题解

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

/ 注册

全部文章 / 题解（共27篇）

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

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

2020-09-25

1 731

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 678

迷宫 [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 685

树上行走 [dfs]

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

2020-09-20

2 798

上学要迟到了 [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

位运算之谜

题意题解将a与b看为2进制数，根据按位与性质易知在a与b不为0的情况下，一定是大于等于的，只需要判断此数所剩的2进制位，是否均为a&b为0的2进制位。 code #include <bits/stdc++.h> #define reg register #define ll ...

2020-09-20

1 689

单词记忆方法 [模拟]

题意将字符串转换为对应权值，A-Z为1-26，若字母后面存在数字，则将前面字母或括号内权值乘以后面的数字注意多种特殊情况。题解（题解写着写着发现一组hack数据把自己昨天的代码hack了...这题数据有锅呀，hack数据 ABC5 答案应该是18）对左右括号，数字，字母进行分类讨论即可.将每对...

2020-09-20

0 662

牛牛和牛可乐的赌约2 [sg定理]

题意在大小的棋盘中，对位置的棋子进行操作，向上1或2格，向左1或2格。最终无法移动棋子的人输。题解根据SG定理画出NP点的转移图 SG定理 P点(必胜点)：即处于此位置，在双方无失误情况下此方必胜N点(必败点)：即处于此位置，在双方无失误情况下此方必败转移：1.对于所有必胜点，一定存在至少一种...

2020-09-20

3 770