uva

## UVA11308 How many O's 可以说很经典的数位DP。 但是有一种有趣的更快的做法： 将问题变化一下，如果对于第 $i$ 位，把它变为 $0$ ，那么由于不能有前置 $0$ 且保证构造出的数不能大于原数，所以比 $i$ 大的位就是 $1—那么多$。额，不好说，比如要求 $0到11 ......

## 0. 题目大意 在一个$10\times9$的网格上，可以游玩象棋。在本题中，我们考虑如下几个简化的规则： - 每一个棋子下在交点上，一个交点不能同时有两个棋子； - 棋盘的左上角为$(1,1)$，右下角为$(10, 9)$； - 当一个棋子移动到它的敌人的棋子上，就说敌方的棋子要被“吃掉”。 ......

# Glenbow Museum 首先要发现一些性质: 1. 不能出现双O 2. 有且仅有四次双R出现(首尾相连也算) 3. R数刚好多O数四个 4. R数和O数相加等于总长 关于发现方法，可以考虑先放一个只有4*R的矩形进去，然后添加拐角(OR)，这样不难发现如上性质。 那么这道题就好许多的。 R ......

这道题主要是去理解所谓的 "看得见" 的面积是怎么组成的。 对于每个露出来的面积，其实是由多个圆弧所组成的。是的，这就是为什么要以圆弧为引入点来解决此题的原因。 那该怎么找露出来的面积呢？题目有说，在一定范围内不影响答案，所以考虑找每个圆弧的中点，然后平移一点点距离，再从覆盖顺序看最上层盖住这个点的 ......

很好的一道 DP 题。 首先按照电压排序。 然后考虑 $dp[i]$ 表示前 $i$ 盏灯的最小花费，则应该有 $dp[i]=min(dp[j]+(s[i]-s[j])*c[i]+k[i])$，其中 $s[i]$ 表示前 $i$ 盏灯的总需求数。 为什么可以这样子直接用前缀，而不用考虑 "跳着选" ......

[题目链接](https://www.luogu.com.cn/problem/UVA10684) ## 思路 一道简单模拟题。 用循环模拟每次的处理。对于每次输入的数 $N$，先判断 $N$ 的值，如果为 $0$，直接结束程序，避免死循环。否则就依次输入每次赢或输的钱数，再进行集中判断，获取连胜获 ......

[题目链接](https://www.luogu.com.cn/problem/UVA11714) ## 思路 一道结论题，代码实现非常简单。 把此题拆分成两个小问题。 - 在最坏的情况下，需要几次询问，才能找出最大的数。 - 在最坏的情况下，需要几次询问，才能找出次大数。 对于找出最大的数，可以模 ......

[题目链接](https://www.luogu.com.cn/problem/UVA10678) ## 思路 一道简单模拟题。 经过模拟，我们不难发现，牛的活动轨迹是一个椭圆。根据椭圆形面积公式得到 $S = \pi a b$。其中，牛可以到的最左边或最右边时 $a = \frac{l}{2}$， ......

[题目链接](https://www.luogu.com.cn/problem/UVA1435) ## 思路 一道找规律思维题，代码非常简单。 能否把 $c \times d$ 的矩阵分成若干个 $a \times b$ 的矩阵，其实就是问你 $a$ 或 $b$ 中有没有 $c$ 或 $d$ 的因数 ......

[题目链接](https://www.luogu.com.cn/problem/UVA10812) ## 思路 大家应该都知道绝对值是什么吧？ 那么，我们不妨直接设 $a\gt b$，这样就省去了一次分类讨论的麻烦，大大降低了程序的复杂度。即可得到此二元一次含参方程组： $$ \begin{case ......

# UVA114 Simulation Wizardry [题目传送门](https://www.luogu.com.cn/problem/UVA114) 此题为模拟类型，必须认真读题，绝不能漏掉任何一个细节。 ## 分析 解释代码中的主要部分： 1. 结构体定义：`struct POINT` 用于 ......

# UVA11732 "strcmp()" Anyone? [题目传送门](https://www.luogu.com.cn/problem/UVA11732) 一个我认为比较有趣的问题…… ## 题意 给出 $n$ 个字符串，两两比较字典序大小，求出所需比较的总次数并输出。 ## 分析 使用 tr ......

# UVA12462 Rectangle [题目传送门](https://www.luogu.com.cn/problem/UVA12462) ##### 可以说是广告印刷的加强版。 ## 题目大意 有 $n$ 个矩形依次相邻，$m$ 种颜色。第 $i$ 个矩形高度 $h_i$，宽度为 $1$，颜色 ......

# UVA11538 Chess Queen [题目传送门](https://www.luogu.com.cn/problem/UVA11538) 挺有意思的一个题目。 ## 题目大意 给定一个棋盘，在棋盘上放两个皇后（一白一黑），求使得两个皇后相互攻击（在一行、一列或对角线）的方案数。 ## 分析 ......

## 大意： 给定一个字符串 $s$ 判断 $s$ 是否符合要求。 1. 由数字，`-` 和大写英文数字 `X`，空格组成，`X` 代表 $10$ 且只能在最后出现。 2. 依次相加前面的数字的总和可以被 $11$ 整除，也就是前缀和，而且刚好 $s$ 只有 $10$ 个数字。 ## 坑点： 1. ......

从另一个网站上的我的博客里转的。感觉放在一起比较好。时间久远，而且是英文（流泪）。 # [Easy Climb](https://www.luogu.com.cn/problem/UVA12170) ## Step 1 If $x_i,d\le 100$. Then define $dp_{i,j} ......

UVA10702 Travelling Salesman 题解 题面： 有个旅行的商人，他每到一个的新城市，便卖掉所有东西再购买新东西，从而获得利润。从某城市 A 到某城市 B 有固定利润（B 到 A 的利润可能不同）。已知城市可以重复到达，从 S 点出发，经过 T 个城市，有 E 个城市能作为终点 ......

redirect_from: /_posts/2017-12-21-UVA-11275/ title: 3D Triangles tags: - 算法竞赛 - [三维几何模板](https://wu-kan.cn/_posts/2019-01-27-%E8%AE%A1%E7%AE%97%E5%87% ......

本来这篇题解是想在中考前写的，但是直到考前都没调出来，原因是 `pow()` 的精度感人。 由于 $x\equiv0\pmod{a\cdot b}$，令 $c=\dfrac{x}{ab}$，答案即 $abc\le n$ 的**无序**三元组 $(a,b,c)$ 数量。 考虑把无序转成有序，即 $a\ ......

### 前言 长沙市一中8机房0714模拟测1。 [传送门](https://www.luogu.com.cn/problem/UVA10791) [blog](https://www.luogu.com.cn/blog/JJL0610666/solution-uva10791) # 思路 本题思路 ......

#include<iostream> #include<algorithm> #include<string> #include<sstream> #include<vector> #include<queue> #include<cstring> using namespace std; cons ......

UVA12222 山路 题意： - - 一个山路只有一条车道，因此不能有两辆方向相反的车同时在车道内。同时，为了保证安全，车道内不能超车，且同向行驶的车间距必须大于10分钟。现在给你n辆车，三个参数依次表示行驶方向，到达时刻，行驶时间。问如何安排能使最后一个通过的车通过时的时刻最小，输出这个值。 分 ......

## 题目大意 给定一个N个点M条边的带权有向图，求平均值最小的回路。 ## 解法 看到这种题目，~~喜欢打暴力的我~~一下就想到：遍历整个图，找到每一个环，然后算出它们的平均值，最后比较出最小值。然而，呃...，会T飞... **既然我们不能暴力找最小值，那还有什么别的办法吗？** 我们只需要输出 ......

UVA12716 GCD等于XOR GCD XOR 一道数学题。 首先，我们可以知道，a-b>=gcd(a,b)=c; 其次，a-b<=a xor b=c; 综上，可得a-b=c,即a-b=a xor b. 由于范围不大，直接枚举。 第一层枚举c（因为c较少），第二层枚举a，（b=a-c) 再判断c ......

## 思路 首先有一个比较朴素的 DP 就是记 $f_i$ 为 $s$ 的从第 $i$ 个字符开始到字符串结尾的划分方案数，记模板串的集合为 $T$，$s$ 从第 $i$ 个字符开始到字符串结尾的子串为 $s(i)$，那么不难写出方程： $$ f_i = \sum f_{i + \operatorn ......

**记录** 15:42 2023-5-26 https://onlinejudge.org/external/103/p10305.pdf reference:《算法竞赛入门经典第二版》例题6-15 拓扑排序，存在有向环的图没有解。不包含有向环的有向图称为有向无环图（Directed Acycli ......

## Description 按顺序给出 $n$ 个棍子两个端点的坐标。如果后来的棍子与前边的棍子相交，则说后面的把前面的挡住了。问最后有多少个棍子没被挡住。 $n\leq 10^5$，且**答案不超过 $1000$**。 ## Solution 叉积基本运用。 1. 定义：$\overrighta ......

图论题还是在于建图 ## 题意 给定一个长度为 $n \times m$ 的网格图，有的地方是白方块，有的是黑方块，有的啥也没用。 给你如下四种 $L$ 形方块，询问是否存在方法，让这些方块正好就是给出的图的形状。 $ L $ 形方块如下 ![](https://cdn.luogu.com.cn/u ......

**记录** 00:22 2023-5-22 https://onlinejudge.org/external/5/p572.pdf reference:《算法竞赛入门经典第二版》例题6-12 八连块，标准的dfs。 学到的点:使用ind标记连通分量，这个可能有题会用到。 ```c++ #inclu ......

**记录** 18:34 2023-5-20 uva.onlinejudge.org/external/2/297.html reference:《算法竞赛入门经典第二版》例题6-11 非二叉树，这还是比较有趣的，图形学上还有八叉树用来划分空间的。 这道题将图和四叉巧妙的结合起来，其原理也是使用先序 ......