11526 uva
UVA1485 Permutation Counting
传送门 description 一个长度为 \(n\) 的排列 \(a\),其权值为满足 \(a_i>i\) 的位置的数量。 求权值恰为 \(k\) 的长度为 \(n\) 的排列的方案数。 \(n,k\leq 1000\) solution 设 \(f_{i,j}\) 表示考虑前 \(i\) 个数, ......
[UVA12683] Odd and Even Zeroes
Description 给出 \(n\),求出 \(0!, 1!, 2! \ldots, n!\) 中有几个末尾有偶数个 \(0\)。 \(1\le n\le 10^{18}\)。 Solution 根据基本结论,一个数末尾 \(0\) 的个数等于该数有几个因数 \(5\)。而一个数的阶乘末尾有几个 ......
题解 UVA437
题解 UVA437 每种方块都可以将 \(x\times y,x\times z,y\times z\) 的面放在水平面上,所以每块都有 \(3\) 种状态,每次从剩余所有 \(n-1\) 个块的 \(3\) 种状态中选取能放置在此方块上方的方块,(即选取水平面矩形对应的边小于当前水平面边权),并且 ......
救济金发放(The Dole Queue, UVa 133)
#include<stdio.h> #include<string.h> #define maxn 100 int n,k,m,a[25]; int left, chance; int win, lose; char s[maxn], s2[maxn]; int go(int p, int d, i ......
UVA12046 题解
前言: 有些虚高,建议降蓝。感觉比 CF55D 要简单。 题目大意: 定义一个数为好数,满足以下要求: 每个数位都能整除原数。 每个数位都小于等于 \(6\)。 求长度为 \(n\) 的好数有多少个。 思路: 首先,\(0\) 整除任何数都没有意义,可以不枚举。其次,要满足条件二,所以每个数位可以只 ......
UVA1366 Martian Mining 题解
这个题可以用动态规划解决。 令\(sbe_{i,j}\) 为第 \(j\) 列 \(1\) 至 \(i\) 个格子 \(BE\) 矿总和,令\(snw_{i,j}\) 为第 \(i\) 行 \(1\) 至 \(j\) 个格子 \(NEW\) 矿总和。 \(dp_{i,j,0}\) 表示为以第(\(i ......
【位运算】UVA12716 GCD等于XOR GCD XOR 题解
UVA12716 一道挺有意思的位运算的题。 \(\gcd(a,b)\) 与 \(a\oplus b\) 本来是没有什么联系的,也不好直接转化。 那么就需要一个中间数进行转化,一般来说会是一个临界值,否则不好找答案。 先观察 \(\gcd(a,b),a\leqslant b\),可得 \(\gcd( ......
UVA1471 防线 Defense Lines 题解
传送门 首先可以将题意大概可以简化为:取两端不重复的连续子序列,组成一个最长的连续递增子序列。 我们先 dp 预处理出以 \(i\) 为结尾的连续递增子序列长度 \(dpr_{i}\)。 同样预处理出以 \(i\) 为开头的连续递增子序列长度 \(dpl_{i}\)。 考虑对于每个 \(dpr_{i ......
UVA10054 The Necklace 题解
好可恶一道题,怎么没人告诉我输出之间有空行( 思路是先抽象成图,然后跑一边dfs记录边的前后顺序。 对于不能成环的情况,只需要再开个数组记录度数判断奇点即可。 若存在奇点则break掉,剩下的跑dfs、 //produced by miya555 //stupid mistakes:1.多测要清空 ......
UVA12655 Trucks 题解
题目传送门 前言 中文题目可以看 link 。 前置知识 Kruskal 重构树 | 最近公共祖先 简化题意 给定一个 \(N\) 个点 \(M\) 条边的有向图,共有 \(S\) 次询问,每次询问从 \(L\) 到 \(H\) 所有的路径中最小的权值的最大值(多组数据)。 本题即最大瓶颈路问题。 ......
题解 UVA1537 Picnic Planning
这道题在显然是最小生成树,但是很显然我是不会打最小生成树的。 题意描述 给定一张 \(n\) 个点 \(m\) 条边的无向图,求出无向图的一棵最小生成树,满足一号节点的度数不超过给定的整数 \(s\)。 具体思路 首先,看到这种度数最多为 \(s\) 的题,显然想到 wqs 二分。但是 wqs 二分 ......
题解 UVA1566 John
题目描述 两个人轮流取石子,每人每次可以 \([1,a_i]\) 个石子,最后取完石子的人为负。问最终谁会赢。 具体思路 若堆数为 \(1\) 且该堆数量为 \(1\),先手必败。 若堆数不为 \(1\) 且每堆数量都为 \(1\),若有奇数堆,先手比败,否则,先手必胜。 若堆数不为 \(1\),转 ......
洛谷 UVA10714 Ants の 题解
这道题只有一个点比较难想。 大概思路就是先输入个 $t$,表示要跑几轮,后面的照常输入。因为蚂蚁都是一样的,所以两个蚂蚁碰面的时候相互穿过和各自掉头是没有区别的,我们按照前者模拟就好,其余思路暴力求解即可。 #include <iostream> #include <cmath> using nam ......
洛谷 UVA10852 Less Prime の 题解
这道题更像是结论题,因为他要推一个小结论,才能做出这道题。 大概思路是先打个素数表,存到数组 $a$ 内, $cnt$ 是素数表的最后一个元素的下标。之后循环 $M$ 次去输入 $N$,每次输入 $N$ 之前都要定义两个变量,分别是 $mx$,存 $n - p \cdot x$ 的最大值,$ans$ ......
Sol.UVA10127
题意:给定 \(n\),找到形如 \(1111...1111\) 的数 \(y\),使得 \(y \equiv 1\mod x\),最终输出 \(y\) 的位数。 思路:形如 \(1111...1111\) 的数可以拆分成 \(10...00 \times 1 +10...0 \times 1 + ......
UVA1030 题解
思路分析 猜想 我们可以在题目中看出一下几个突破口: 能“看穿”的位置所对应的单位立方体是一定不存在的。 如果前视图的右上角的颜色 \(A\) 和顶视图的的右下角颜色 \(B\) 不同,那么对应的格子就一定不存在。 在删除这个立方体后,我们还可以发现,挖去立方体的左侧和 \(B\) 左侧的颜色不同。 ......
UVA11210 题解
思路分析 一道大模拟。 一共只有 \(34\) 种牌,因此可以一次判断是否“听”这些牌。比如,为了判断是否“听”一万,只需要判断自己拿到这张一万后能否可以继续和牌。这样,问题就转化成了给定 \(14\) 张牌,判断是否可以和牌。为此,我们可以递归求解:首先将两张牌作为“将”,然后每次选 \(3\) ......
UVA11464 题解
思路分析 暴力枚举? 我们可以枚举每个数字变或不变,最后判断整个矩阵是否满足条件。但是,这样做最多需要枚举 \(2^{255}≈5\times10^{67}\) 中情况,是一定会超时的。 大眼观察 注意到 \(n\le15\),第一行只有不超过 \(2^{15}=32768\) 种可能,所以第一行的 ......
UVA1352 题解
思路分析 构造排列表 立方体只有 \(4\) 个,暴力法是可行的。但是如果我们要暴力,首先得清楚一个立方体到底有几种不同的旋转方式。 接下来,我们用“姿态”一词代替“旋转方法”。假设 \(6\) 个面的编号为 \(1\sim6\),从中选择一个面作为“顶面”,“顶面”的对面为“底面”。然后我们在剩下 ......
UVA202 题解
思路分析 前言 又是一道小模拟题,不过细节巨多,可以用来锻炼自己的代码能力。 解法 本题实际上就是模拟长除法的计算过程,其中每一步除法时都有被除数及其余数,当被除数出现重复时就表示出现循环节了。所以需要记录每一次的被除数及其在循环小数中的位置,需要判断当除数不够除,每一次补零也需要记录其对应的位置。 ......
UVA11809 题解
思路分析 前言 一道比较简单的数学题。 解法 根据题意可以推算出最大值 $v=\Big(1-\dfrac{1}{2{M+1}}\Big)\times2{2{E-1}}=A\times10B$。因为两边都比较大,所以可以同时求以 $10$ 为底的对数:$\lg v=\lg(2{M+1}-1)-(M+1 ......
UVA10368 题解
`2023-08-06 15:18:08 solution` [双倍经验](https://www.luogu.com.cn/problem/P1290) 这种有限轮游戏的博弈通常都是有两种状态,必胜态和必败态。 对于必胜态,指的是从它可以转移到必败态。 对于必败态,指的是从它不论如何只能转移到必胜 ......
UVA220 黑白棋 题解
某网站的题解标点符号的要求真是a piece of bloody shit. 在这里会自由一些. ## 0. 题目大意 题目的大意是模拟黑白棋游戏。简单而言有如下的要求: - 列出可能的移动。合法移动的规则是:新下的棋子必须 "夹住" 原来的。所谓夹住,其实就是一段横向、竖向、斜向的棋子之间的两段必 ......
UVA10054 The Necklace题解
### 题意 给定一个无向图,其中至多有 $50$ 个结点,求是否有欧拉回路。 ### 题解 很明显就是一个无向图求欧拉回路的板子,我们用 $\tt{Hierholzer}$,先说存图,要明确的一个点是这个无向图里是有可能有重边的,所以我们要注意记录的时候不应是单独地记录某一条边是否存在,而是要记录 ......
UVA967的题解
设 $check_i$ 为 $1\sim n$ 中满足题意的数的数量。 显然答案为 $check_j-check_{i-1}$。 注意到 $check$ 能直接暴力求出来。 那么就可以先把 $10^6$ 范围内的所有质数求出来,然后所有数跑一遍,每个数都去旋转得出所有数后判断是否均为质数,记录下来。 ......
UVA908[Re-connecting Computer Sites]题解
[原题](https://www.luogu.com.cn/problem/UVA908) ## 1.题意分析 题意就是给你很多组数,对于每组数,有三组小数据。第一组小数据先输入一个n表示顶点数,然后再输入n-1条边表示初始边数。其它组小数据先输入一个数k,表示增加的边的数量,然后再输入k条边,表示 ......
UVA10192题解
为了尽可能满足父母亲的要求,我们应该取两个字符串的最长公共子序列。 [洛谷模板题](https://www.luogu.com.cn/problem/P1439) 设 $dp_{i,j}$ 为 $a$ 串匹配到第 $i$ 位,$b$ 串匹配到第 $j$ 位时的最长公共子序列长度。 则易知 $dp_{ ......
P7 UVA11481 Arrange the Numbers
## UVA11481 Arrange the Numbers 组合数问题。 做法貌似很多,显然在前 $m$ 个数中选 $k$ 个,即 $C(m,k)$,然后后面有 $m-k$ 个数需要保证不放在自己的位置上,所以后面整体是一个禁位问题,貌似可以用棋盘多项式去推禁位公式,但是暂时不会。不过还有另外一 ......
UVA1108 Mining Your Own Business 题解
[题目传送门](https://www.luogu.com.cn/problem/UVA1108) # 题意 在一个无向图上选择尽量少的点涂黑,使得删除任意一个点后,每个连通分量里都至少有一个黑点(多组数据)。 # 正文 观察题意,发现这是个 Tarjan 求点双连通分量的板子。 考虑在求点双连通分 ......
UVA12390 Distributing Ballot Boxes 题解
[题目传送门](https://www.luogu.com.cn/problem/UVA12390) ## 题意 有 $n$ 个城市,$b$ 个投票箱,第 $i$ 个城市有 $a_i$ 人,每个人均有一张票,将 $b$ 个投票箱分给 $n$ 个城市,每个城市的票分摊在投票箱里,求所有城市中最多的投票 ......