萝卜朝天椒

题解

/ 注册

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

PonyAi2019校招(1)T1车队管理

解题思路：·如果只考虑往外扩张的车辆，发现只能扩展log层，猜想车辆的活动半径不会很大，打表发现是个类似圆形的图形，也就说明车辆的移动直径是根号n级别的，把横纵坐标都+500，可以直接用数组来模拟·会发现车辆的移动顺序是无关的，假如一个方格内有16辆车，一次移动8辆和一次移动16辆是等价的，模拟的时...

2021-01-27

0 820

List Of Integers

题意：询问[x,p,k]，找出比x大且与p互质的第k个数解题思路： idea很简单首先容斥原理可以算出某个范围内的与x互质的个数（oi-wiki上有介绍） https://oi-wiki.org/math/inclusion-exclusion-...

2020-09-24

3 915

SCI2005扫雷

题意：那是在一个n×m的矩阵里面有一些雷，要你根据一些信息找出雷来。这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图：由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第...

2020-06-18

0 803

NC17315

题目描述Applese有1个容量为v的背包，有n个物品，每一个物品有一个价值ai，以及一个大小bi然后他对此提出了自己的疑问，如果我不要装的物品装的价值最大，只是一定需要装m个物品，要使得求出来的物品价值的中位数最大Applese觉得这个题依然太菜，于是他把这个问题丢给了你当物品数量为偶数时，中位数...

2020-06-16

0 860

NC15748

题意：给定一棵 n 个节点的树，初始选择节点 s，第一天定居在s，并将s和与s相邻的节点染色。之后每一天选择一个未染色的点定居，将定居点和定居点相邻的节点染色。问最多能定居多少个节点。题解每个点都会被染***r>考虑如何给叶子节点染色，发现要把叶子节点染色，定居在叶子处最佳，所以我们首先选择...

2020-06-01

3 924

dfs

解题思路：只考虑一颗儿子全是叶子的子树时，那么最佳的匹配方案是这些叶子节点两两配对，多余的和根配对。直观感觉这个子树的边全被统计了，而且只统计了一次，如果叶子和非子树的点配对的话，这个子树的边仍然全被统计了，子树根到它父亲的边会被多次统计。按照这个思路，所有边最多只会被统计一次。现在证明这个方案是...

2020-04-02

1 924

dp计数

dp[i][j]表示在s1中选择前i个字符，在s2中选择前j个字符，能够成合法序列的方案数（这里的合法指的是每个')'都能找到一个'('与之对应）。一个长度为i+j的括号序是从(i-1,j)和(i,j-1)转移过来的,所以dp[i][j]=dp[i-1][j]+dp[i][j-1]。判断dp[i][...

2019-09-04

1 794