hnust_yangyanjun

分类

大数加法(1) 尺取法(1) 面经(4) 题解(119)

/ 注册

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

每日一题题解

30篇文章 895人学习

全部文章（共125篇）

Coprime Subsequences 来自专栏

题意：给你一个长度为n的序列，让你求序列的最大公约数为1的子序列数目为多少？思路：莫比乌斯反演首先统计一下该序列有什么数，个数为多少。然后求莫比乌斯函数。统计有i为因子的数有x。根据x求都有该因子的序列有 ( )个根据莫比乌斯函数判断该序列数是加上还是减去.最后得出结果. 代码： #include...

2021-03-05

1 767

Weak Memory 来自专栏

题意：给你一个n个点m条边的图，其中有k个节点是特殊的，起点s一定是特殊的，现在让你从s到t，每个特殊点可以加q点能量，经过一条边需要花费1点能量，求能从s到t时q最小为多少？（如果不能到达，输出-1）思路：求最小值，然后这值又具有单调性，所以可以二分枚举答案。然后判断这个答案行不行可以用bfs（...

二分 bfs

2021-03-03

1 802

PLEASE 来自专栏

题意：有这么一个游戏，有三个杯子，每次可以使用中间的杯子与二边的交换，求n次交换后中间杯子还是原来那个的概率为多少？思路：设原来杯子用1表示，其余二个杯子用0表示：010为初始状况第一次出现状态为：100、001第二次出现状态为：100、010、010、001第三次出现状态为：100、010、10...

数学

2021-03-01

1 593

Microtransactions (hard version) 来自专栏

题意：有i种物品，每种物品需要买k[i]个，然后商店会有m次特价出售，第j次为在di天出售第ti种物品，物品原价2元，特价1元，你每天上午可以获得一元，下午可以进行交易，求获取所有物品花费的最少时间为多少天？思路：如果第i天满足条件，则i+1天一定满足，所有二分答案.如何判断答案x是否符合：按贪心...

二分贪心

2021-02-28

1 591

Work Group 来自专栏

题意：有一颗n个节点并且以1为根的树，每一个节点有一个权值，你可以选择一些节点组成工作组，工作中中的每一个节点他的子树上的节点在工作组的数目为偶数（不包括自己），求工作组的最大权值为多少（工作组的权值等于工作组中每个节点的权值之和）？思路：树状dpdp[v][0/1]表示第v个节点在满足条件时该子...

树状dp

2021-02-22

1 698

Spy Syndrome 2 来自专栏

题意：描述了一种加密技术，现在将加密后的字符串和字典给出，要你求还原后的字符串。加密方式：①将所有字母改为小写字母②将所单词翻转③将所有空格去掉思路：你可以将字典中的单词按翻转后的结果插入字典树中。然后dfs加密后的字符串从字典树中查找满足的可划分的单词。代码： #include <cst...

dfs 字典树

2021-02-21

2 715

Dima and Salad 来自专栏

题意：给出n个物品的ai和bi的值，求在满足所选物品ai之和除以bi之和等于k时ai之和最大为多少？思路：将每一个物品的ai看成价值，ai-bi*k看成体积，这样题目就变成了所选物品体积为0时价值最大为多少？给体积一开始就加上一个较大的值来解决下标为负的问题，这样就只是一个简单的01背包问题了。 ...

dp

2021-02-10

1 608

Subsequences (hard version) 来自专栏

题意：给出一个长度为n的字符串和一个k，求形成k个不同子串组成的集合至少要删除多少字符？如果无法完成则输出-1. 思路：动态规划：dp[i][j]表示前i个字符组成一个长度为j的不同子串的数目；dp[i][j]=dp[i-1][j] (不加第i个字符)+dp[i-1][j-1] (加第i个字符)+d...

dp

2021-02-10

1 523

Train Hard, Win Easy 来自专栏

题意：有n个参赛者，每个参赛者在做第一题和第二题都有一个罚时，两个人组成一队，每个人负责一题，该队罚时为两人罚时之和（队内会取最优策略），求该参赛者在所有可能的组队中总罚时为多少？思路：我们发现可以按照前一个写第一题，后一个写第二题最优来排序：既：A.a+B.b<A.b+B.a先求该参赛者与...

贪心前缀和

2021-02-10

1 798

Tree Constructer 来自专栏

题意：有一棵n个节点树，请你构造节点数据使图正好为这棵树（节点之间有边仅这二个节点位与等于 -1）。思路：我们可以先黑白染色，因为n<=100,所以一定会有一种颜色少于等于50，所以我们就应该从位上考虑，不然为什么n<=100而不是小于100000呢，又因为只有相邻黑白节点才连接，所以...

构造题

2021-02-06

6 693