熠丶

题解

未归档(32)

/ 注册

做想做的事，见想见的人

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

系数

思路本题关键点在于模数是3这样子就可以转化为根据二项展开式可以得到系数又因为模数非常小，组合数可以用Lucas定理计算代码 // Problem: 系数 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/9986/...

2021-03-02

0 614

The Cow Lineup 来自专栏

思路将整个数组进行分割，使每个子数组都包含1~k至少一次我们可以选取每个子数组最后一个数，再加上任意一个数即可组成最短不存在子序列代码 // Problem: The Cow Lineup // Contest: NowCoder // URL: https://ac.nowcoder.c...

2021-03-02

1 737

树上博弈

做法：状压dp 思路每个点与附近连边的点用二进制状态表示，1表示有边，0表示无边该状态选取的点也用二进制状态表示，1表示选了，0表示没选选取该点的值后的差值为该点的值减去转移前的差值代码 // Problem: 树上博弈 // Contest: NowCoder // URL: https://...

2021-03-02

0 606

模仿游戏

思路记录怪物的第一次第二次出现时间can[]表示叶妹妹是否具有攻击这个怪物的能力num[]表示叶妹妹不能攻击该怪物的数量sum表示叶妹妹能杀怪物的数量根据贪心策略，每一次泽鸽鸽优先攻击自己没有攻击过且第二次出现早的怪物，这样子叶妹妹就越早能杀怪如果这一时刻不存在泽鸽鸽优先没有攻击过的怪物，那...

2021-03-01

0 568

美丽的路径

思路先判断从s开始是不是能走到t 二分中位数的大小如果相邻的两个点都大于等于mid，中位数能达到mid如果大小大小交替走也成立代码 // Problem: 美丽的路径 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/conte...

2021-03-01

1 672

Coprime Subsequences 来自专栏

题意给你一个序列，问你有多少个子序列它们的最大公约数为1 思路先求出这些数中有多少个数含因子i 公约数为i的序列数为代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(...

2021-02-28

0 649

Weak Memory 来自专栏

题意每走一条边都需要花费1点能量。每经过一个特殊点都可以将当前能量值补充到能量上限。给定起点s和终点t，求可从点s到达点t的最小能量上限。做法：二分思路对能量上限答案进行二分按照能量花费跑最短路，每次遇到特殊点能量恢复到能量上限代码 // Problem: Weak Memory /...

2021-02-28

0 619

PLEASE 来自专栏

思路 010会分出两种情况100和001100会分出两种情况100和010001会分出两种情况100和001 经过i次交换后，可以得到个010 当n为偶数，当n为奇数，代码 // Problem: PLEASE // Contest: NowCoder // URL: https://a...

2021-02-27

1 716

九峰与子序列

思路 dp[i][j]表示到第i个字符串匹配到k串第j位的方案数我们可以优化第一维利用字符串哈希匹配两个字符串是否相等代码 // Problem: 九峰与子序列 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/998...

2021-02-26

0 574

温澈滢的狗狗

思路先按照颜色把每条狗存放起来对它们的亲密度进行二分，求出第 k 对亲密关系的狗的亲密度是多少 calc表示求小于等于x的有多少对数，我们利用异色点对数=总点对数-同色点对数来求然后在枚举该其亲密度，把第 k 对亲密关系的狗输出代码 // Problem: 温澈滢的狗狗 // Conte...

2021-02-26

0 713