Meul

分类

11eyes的算法笔记(4) ACM(1) Atcoder(14) BFS(1) codeforces(38) DFS(2) dp(3) ICPC(1) sublime text 3(1) 容斥(1) 未归档(10) 模拟(1) 洛谷(2) 牛客(26) 牛客题霸(1) 题解(74)

/ 注册

TA的专栏 13篇文章 1人订阅

11eyes的每日一题

3篇文章 872人学习

11eyes的排位日记

10篇文章 971人学习

0篇文章 0人学习

全部文章（共180篇）

NC23049

题意你有段小木棍，对每段小木棍切割，要求得到段长度相等为(正整数)的小木棍，求最大为多少？思路答案具有单调性，故考虑二分，时间复杂度 #include<bits/stdc++.h> using namespace std; typedef long long ll; typede...

二分

2020-04-16

0 635

NC14731

NC14731 题意求所有长度为的01串中满足如下条件的二元组个数：设第位和第位分别位和，则答案对取模。思路题目让我们求逆序对，长度的01子串1在0的左边有多少种方案，由于题中1和0的地位是等价的，故正序对的个数和逆序对个数是一样的。表示从个数里选个1剩下的全部为0，所构成的01子序列的个数...

数学组合数学

2020-04-16

1 561

NC14248

NC14248 题意给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同思路 DFS 树数据结构这道题和CF1339D十分相像，有兴趣的可以做一下。把题意转化为给你一颗n个结点的树，树上所有的边权值为1，求树...

DFS 树数据结构

2020-04-14

2 798

NC14247

NC14247 题意给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。思路枚举预处理异或前缀和为了便于我们求任意区间的异或和，预处理异或前缀和。为了避免区间重叠，我们枚举两个区间的分界点，记录(包含)即左边的异或区间值。我们发现左侧区间扩大，则左边异...

前缀异或枚举

2020-04-13

0 513

NC5026E

NC5026E 题意把原题意转化为给你一个长为的字符串，求至少有个相同且不相交的长为(可为)的子串，为多少？思路二分+哈希字符串时间复杂度这道题不要求得到所求子串为什么，而要求子串所能取得最大长度，且答案具有严格单调性，故可以二分答案。那么如何验证？首先预处理字符串Hash得到Hash数组表...

哈希字符串二分哈希

2020-04-12

1 684

NC5026D

题意一张连通有向图，另一条边反向，是否缩短了1到n的最短路？保证开始给定的图从城市1可以到达城市n，若边反向后城市1不能到达城市n，我们视为最短路径长度没有变短。思路数据范围较大，最原始的暴力每次djikstra一遍肯定是TLE的，于是思考预处理，预先djiksra一遍。每次反向一条边和没反向...

最短路 djikstra

2020-04-11

3 566

NC5026C

题意总共12道题，以A,B,C,D为答案的有na，nb，nc，nd个，且有一些题目答案要一致。思路答案一致想到并查集合并到一起，然后我就很蠢的开始想排列组合了，后来发现排列组合的情况很多，不好写，遂开始思考dp，发现还是不会，这时候瞟了一眼数据，这个数据范围很小，直接暴力模拟利用stl中的ne...

暴力

2020-04-11

1 717

NC5026B

题意你有n个苹果和m个香蕉，你可以花一天时间使得其中一种水果翻倍，或者花一天时间同时吃掉1个苹果和1个香蕉，苹果和香蕉必须同时吃掉。求最少多少天可以吃完？思路贪心：我们翻倍要做到既让水果得到最大程度的补充，又不能超过，则进行翻倍。这里苹果和香蕉是等地位的，为了方便我们先把大的给到,小的给到,看...

2020-04-11

1 624

NC5026A

题意 h，a，H，A，代表你的血量和攻击力以及毛球怪的血量和攻击力。求你能杀多少只毛球怪，若你能杀无限只，则输出"-1"。（你先手）思路计算你需要打一只毛球怪次他才会死，计算你每杀一只毛球怪所消耗的血量，由于你先手你所扣的血量为你攻击毛球怪的次数。若消耗的血量为0，则输出"-1"，否则输出，这里...

2020-04-11

0 723

NC13611

NC13611 题意一棵有n个结点的树，我们有k种不同颜色的染料给树染色。当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同时，染色方案是合法的。请统计方案数。思路把题目转化为给你一颗n结点的树，将其分成个连通块涂上不同的颜色，此时发现染色方案的数量与这棵树...

DP 组合数学

2020-04-10

0 724