CodeForces 344C， CodeForces 359A
前言
这次只包含题1和题2的题解，题3和题4实在是太水了，从题5开始都是我要看别人的题解的了QAQ
各题链接
下面有好多都是缺图的QAQ，各位看官可以点链接看
- CodeForces 344C —— Rational Resistance： http://codeforces.com/problemset/problem/344/C
- CodeForces - 359A —— Table http://codeforces.com/problemset/problem/359/A
- UVA - 10970 —— Big Chocolate https://vjudge.net/problem/UVA-10970
- CodeForces - 758B —— Blown Garland http://codeforces.com/problemset/problem/758/B
- UVA - 11997 —— K Smallest Sums https://vjudge.net/problem/UVA-11997
- CodeForces - 672D —— Robin Hood http://codeforces.com/problemset/problem/672/D
- UVA - 11134 —— Fabled Rooks https://vjudge.net/problem/UVA-11134
- UVA - 11925 —— Generating Permutations https://vjudge.net/problem/UVA-11925
CodeForces 344C —— Rational Resistance
Description
Mad scientist Mike is building a time machine in his spare time. To finish the work, he needs a resistor with a certain resistance value.
However, all Mike has is lots of identical resistors with unit resistance R0 = 1. Elements with other resistance can be constructed from these resistors. In this problem, we will consider the following as elements:
one resistor;
an element and one resistor plugged in sequence;
an element and one resistor plugged in parallel.
With the consecutive connection the resistance of the new element equals R = Re + R0. With the parallel connection the resistance of the new element equals . In this case Re equals (R = 1/(1/Re + 1/R0)) the resistance of the element being connected.
Mike needs to assemble an element with a resistance equal to the fraction . Determine the smallest possible number of resistors he needs to make such an element.
Input
The single input line contains two space-separated integers a and b (1 ≤ a, b ≤ 10^18). It is guaranteed that the fraction a/b is irreducible. It is guaranteed that a solution always exists.
Output
Print a single number — the answer to the problem.
Please do not use the %lld specifier to read or write 64-bit integers in С++. It is recommended to use the cin, cout streams or the %I64d specifier.
Sample Iutput
1 1
3 2
199 200
Sample Output
1
3
200
Hint
In the first sample, one resistor is enough.
In the second sample one can connect the resistors in parallel, take the resulting element and connect it to a third resistor consecutively. Then, we get an element with resistance 1/(1/1 + 1/1) = 3/2 . We cannot make this element using two resistors.
思路
题目的大意是用n个R=1的元件通过并联、串联组成R=a/b的电路，求n
首先注意到 给定的a/b，转换为b/a也是一样的 ，因为若a > b， 则给定的电路一定至少存在一个储在外部的串联元件，因为最外围的如果是并联的，即整个电路为并联电路，那么R < 1，a < b，与 a > b矛盾，既然存在一个外部的串联元件，则可以将其并联得到新的R = 1/(a/b -1 + 1) = b/a，因此两者所需的元件是相同的
因此给定a/b，若 a < b，即为并联电路，则转换为b/a，将其转换为串联电路，这时可以求出外部到底有几个串联元件，只需将 b/a 不断减1, 减到小于1即可，因此这部分的外部串联元件数为 b/a，减完的结果为 (b%a)/a， 此时的电路为并联电路，重复以上步骤，累加外部串联的元件数即是结果
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
ll a, b;
while(cin >> a >> b){
ll sum = 0;
while(a != 1 && b != 1){
if(a < b) swap(a, b);
sum += a/b;
a %= b;
}
sum += max(a, b);
cout << sum << endl;
}
return 0;
}
CodeForces - 359A —— Table
Description
Simon has a rectangular table consisting of n rows and m columns. Simon numbered the rows of the table from top to bottom starting from one and the columns — from left to right starting from one. We’ll represent the cell on the x-th row and the y-th column as a pair of numbers (x, y). The table corners are cells: (1, 1), (n, 1), (1, m), (n, m).
Simon thinks that some cells in this table are good. Besides, it’s known that no good cell is the corner of the table.
Initially, all cells of the table are colorless. Simon wants to color all cells of his table. In one move, he can choose any good cell of table (x1, y1), an arbitrary corner of the table (x2, y2) and color all cells of the table (p, q), which meet both inequations: min(x1, x2) ≤ p ≤ max(x1, x2), min(y1, y2) ≤ q ≤ max(y1, y2).
Help Simon! Find the minimum number of operations needed to color all cells of the table. Note that you can color one cell multiple times.
Input
The first line contains exactly two integers n, m (3 ≤ n, m ≤ 50).
Next n lines contain the description of the table cells. Specifically, the i-th line contains m space-separated integers ai1, ai2, …, aim. If aij equals zero, then cell (i, j) isn’t good. Otherwise aij equals one. It is guaranteed that at least one cell is good. It is guaranteed that no good cell is a corner.
Output
Print a single number — the minimum number of operations Simon needs to carry out his idea.
Sample Iutput
3 3
0 0 0
0 1 0
0 0 0
4 3 0 0 0 0 0 1 1 0 0 0 0 0
Sample Output
4
2
Hint
In the first sample, the sequence of operations can be like this:
For the first time you need to choose cell (2, 2) and corner (1, 1).
For the second time you need to choose cell (2, 2) and corner (3, 3).
For the third time you need to choose cell (2, 2) and corner (3, 1).
For the fourth time you need to choose cell (2, 2) and corner (1, 3).
In the second sample the sequence of operations can be like this:
For the first time you need to choose cell (3, 1) and corner (4, 3).
For the second time you need to choose cell (2, 3) and corner (1, 1).
思路
题目大意为，给一个矩阵染色，每次可以选择 矩阵上值为1的点 和 矩阵的4个顶点其中的一个，这两点为顶点所构成的矩形为矩阵本次的染色范围， 已知矩阵上值为1的点不会出现在矩阵的四个顶点处，求给给定的矩阵完全染色颜色，至少要染几次色
本题很水！这题最大的坑在于样例2, 样例2完全可以选择(2, 3)(4, 3) 和 (2, 3)(1, 1)，换句话说点(3, 1)是没用的，也就是 只要有一个在边缘的点就只需要染2次， 如果点都不在边缘，无论他们如何配合着染色，都至少需要染4次
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
int m, n;
while(cin >> m >> n){
bool flag = false;
int tmp;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
cin >> tmp;
if(tmp == 1 && (i == 0 || i == m - 1 || j == 0 || j == n - 1)){
flag = true;
}
}
}
cout << (flag ? 2 : 4) << endl;
}
return 0;
}
