目录

ACM-ICPC 寒假练习 05

刷完了数学专题,感觉思维量有些大,同时也对浮点数的运算有些接触。最重要的还是感觉有时候题目读起来有些吃力,需要借助中文翻译。

UVaOJ 113

这道题目是集训的时候第一天晚上的题目,据说可以 double 解决,当时没有 AC。

现在重新做了一遍,需要注意的是最后输出的结果一定要转换成int,否则会 WA。

同时,double 转换为 int 的时候可以采取这样的方式:(int)floor(x + 0.5)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
#include <iostream>
#include <math.h>
 
using namespace std;
 
int main()
{
    double x, y;
    while(cin >> x >> y)
    { cout << (int)floor(pow(y, 1 / x) + 0.5) << endl; }
    return 0;
}

UVaOJ 10161

这道题目是通常的找规律题目,和一道《Cantor 的数表》是差不多的,需要注意奇偶不同的处理。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <math.h>
 
using namespace std;
 
int main()
{
    int N;
    while(cin >> N)
    {
        if(N == 0) { break; }
        int k = ceil(sqrt(N));
        int s = (k - 1) * (k - 1);
        int d = N - s;
        int x, y;
        if(d <= k) { x = d; y = k; }
        else { x = k; y = 2 * k - d; }
        if(k & 1) { swap(x, y); }
        cout << x << " " << y << endl;
    }
    return 0;
}

UVaOJ 253

这道题目如果直接考虑会非常的麻烦,我们可以考虑“颜色对”这样一个概念。

即,将互为对面的两种颜色看为一个颜色对,那么一个立方体一共有 3 个颜色对,只要匹配这三个颜色对就可以了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <string>
#include <memory.h>
 
using namespace std;
 
const int MAX = 4;
 
bool pVisited[MAX];
 
int main()
{
    string x;
    while(cin >> x)
    {
        int nCnt = 0;
        memset(pVisited, false, sizeof(pVisited));
        for(int i = 1; i <= 3; i++)
        {
            for(int j = 1; j <= 3; j++)
            {
                if((x[i - 1] == x[5 + j] && x[6 - i] == x[12 - j] ||
                    x[i - 1] == x[12 - j] && x[6 - i] == x[5 + j]) && !pVisited[j])
                {
                    nCnt++;
                    pVisited[j] = true;
                    break;
                }
            }
        }
        cout << (nCnt == 3 ? "TRUE" : "FALSE") << endl;
    }
    return 0;
}

UVaOJ 621

这道题目感觉不是数学题,应该算字符串处理。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <string>
 
using namespace std;
 
int main()
{
    int N;
    string x;
    while(cin >> N)
    {
        cin.ignore();
        for(int i = 1; i <= N; i++)
        {
            getline(cin, x);
            if(x == "1" || x == "4" || x == "78") { cout << "+" << endl; }
            else if(x.substr(x.length() - 2, 2) == "35") { cout << "-" << endl; }
            else if(x[0] == '9' && x[x.length() - 1] == '4') { cout << "*" << endl; }
            else if(x.substr(0, 3) == "190") { cout << "?" << endl; }
        }
    }
    return 0;
}

UVaOJ 10025

这道题目当时没有想出来怎么做,后来看了题解恍然大悟。

首先,根据对称性,我们可以只考虑 $k > 0$ 的情况。

然后,我们令 $S = \bigoplus 1\bigoplus 2\bigoplus 3\bigoplus\cdots\bigoplus N$,其中 $\bigoplus$ 为正负号。

如果将 $S$ 中任意一个 $\bigoplus$ 变换符号,那么 $S$ 的减少量或者增加量必定为偶数。

我们考虑 $\bigoplus$ 都为 $+$ 的情况,因为当 $S > k$ 的时候,我们可以改变其中的 $\bigoplus$ 来达到要求的 $k$。

因此,只要求最小的 $N$,使得 $S > k$,并且满足 $S - k$ 为偶数,因为每次变换 $\bigoplus$ 的符号对 $S$ 的改变量为偶数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
 
using namespace std;
 
int main()
{
    int T, K;
    cin >> T;
    for(int i = 1; i <= T; i++)
    {
        cin >> K;
        if(K < 0) { K = -K; }
        int nSum = 0;
        for(int j = 1; ; j++)
        {
            nSum += j;
            if(nSum >= K && (nSum - K)  % 2 == 0)
            { cout << j << endl; break; }
        }
        if(i != T) { cout << endl; }
    }
    return 0;
}

UVaOJ 591

贪心,计算变换后每列的末高度。将高于末高度的搬到低于末高度的地方即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
 
using namespace std;
 
const int MAX = 64;
 
int pData[MAX];
 
int main()
{
    int N, nCase = 0;
    while(cin >> N)
    {
        if(N == 0) { break; }
        int nSum = 0, ans = 0;
        cout << "Set #" << ++nCase << endl;
        for(int i = 1; i <= N; i++)
        {
            cin >> pData[i];
            nSum += pData[i];
        }
        nSum /= N;
        for(int i = 1; i <= N; i++)
        {
            if(pData[i] > nSum)
            { ans += pData[i] - nSum; }
        }
        cout << "The minimum number of moves is " << ans << "." << endl;
        cout << endl;
    }
}

UVaOJ 107

这道题目需要推导公式,我们令要输出的答案分别为 $x$ 和 $y$。

假设 $k$ 代小猫(包括第一代),每个小猫帽子里有 $N$ 个小猫。

那么我们可以得到公式 $$(N + 1)^k = H,\quad N^k = C$$

两边去对数即可得到 $$k \cdot \log{\left(N + 1\right)} = \log{H},\quad k \cdot \log{N} = \log{C}$$

将 $k$ 约去,得到 $$\log{H}\cdot\log{N} = \log{\left(N + 1\right)}\cdot\log{C}$$

根据上式,我们额可以求出 $N$,即每个小猫帽子里有几个小猫。之所以约去 $k$,是为了多次运算导致浮点数误差。

求得 $N$ 以后,我们就可以进一步的求出一共有多少只小猫不在工作。这是一个等比数列 $$x = 1 + N + N^2 + N^3 + … + N^k$$

当 $N = 1$ 时 $$x = k = \log{H} / \log{2}$$ 由 $(N + 1)^K = H$,代入 $N = 1$ 得 $2^k = H$

当 $N \neq 1$ 时 $$x = \frac{1 - N^k}{1 - N} = \frac{1 - C}{1 - N} = \frac{C - 1}{N - 1}$$

为了计算所有小猫的身高,我们可以得到另一个等比数列 $$y = H + N \cdot\left(\frac{N}{N + 1}\right)\cdot H + N^2 \cdot\left(\frac{N}{N + 1}\right)^2\cdot H + \cdots + N^k \cdot\left(\frac{N}{N + 1}\right)^k\cdot H$$

当 $N = 1$ 时 $$ y = H \cdot \left(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots + \frac{1}{2^k}\right) = H \cdot \left(2 - \frac{1}{2^k}\right) = 2\cdot H - H \cdot\frac{1}{2^k} = 2 \cdot H - 1$$ 由 $(N + 1)^K = H$,代入 $N = 1$ 得 $2^k = H$

当 $N \neq 1$ 时 $$ y = H \cdot \frac{1 - \left(\frac{N^2}{N + 1}\right)^k}{1 - \frac{N^2}{N + 1}} = (N + 1) \cdot H - C \cdot N$$

又,当 $N = 1$ 时,必有 $C = 1$,因此我们对输入数据进行分类讨论即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <math.h>
 
using namespace std;
 
int main()
{
    double H, C;
    while(cin >> H >> C)
    {
        if(H == 0 && C == 0) { break; }
        int x, y;
        if(C == 1)
        {
            x = ceil(log(H) / log(2));
            y = 2 * H - 1;
        }
        else
        {
            int N;
            for(N = 1; N < H; N++)
            {
                if(fabs(log(H) * log(N) - log(C) * log(N + 1)) < 1E-8)
                { break; }
            }
            x = (C - 1) / (N - 1);
            y = (N + 1) * H - C * N;
        }
        cout << x << " " << y << endl;
    }
    return 0;
}

UVaOJ 573

蜗牛爬墙,很经典的题目,要注意两点:

  • 上爬的衰减因子只与第一次上爬的距离有关;
  • 当上爬的距离小于0时,蜗牛不再上爬。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
 
using namespace std;
 
int main()
{
    double H, U, D, F;
    while(cin >> H >> U >> D >> F)
    {
        if(H == 0) { break; }
        F /= 100.0;
        int nDay = 0;
        double dNow = 0, dUp = U;
        while(1)
        {
            nDay++;
            dNow += dUp;
            dUp -= F * U;
            if(dNow > H) { cout << "success on day " << nDay << endl; break; }
            if(dUp < 0) { dUp = F = 0; }
            dNow -= D;
            if(dNow < 0) { cout << "failure on day " << nDay << endl; break; }
        }
    }
    return 0;
}

UVaOJ 846

这道题目一开始完全不知道怎么做,后来百度以后才发现有规律:

距离步长距离步长
1195
22106
33116
43126
54137
64147
75157
85167

我们令 $d = y - x$(其中 $x$ 和 $y$ 为输入数据),s = floor(sqrt(d)),规律如下:$$s = \begin{cases} 2s - 1, & s^2 = d \\ 2s + 1, & s(s+1) < d \\ 2s, & \mathrm{otherwise}\end{cases}$$ 当然,要注意特判相距为 0 的情况。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <math.h>
 
using namespace std;
 
int main()
{
    int T, x, y;
    cin >> T;
    for(int i = 1; i <= T; i++)
    {
        cin >> x >> y;
        int d = y - x;
        if(d == 0) { cout << "0" << endl; }
        else
        {
            int s = (int)(sqrt(d * 1.0));
            if(s * s == d) { s = 2 * s - 1; }
            else if(s * (s + 1) < d) { s = 2 * s + 1; }
            else { s *= 2; }
            cout << s << endl;
        }
    }
    return 0;
}

UVaOJ 10499

一开始没看懂题意。感觉在考英语。

我们假设一开始小球的半径 $R = 1$,那么表面积 $S = 4\pi$。分割成 $N$ 部分,表面积增加 $N\cdot \pi$。那么答案即为 $N / 4 \times 100 = 25N$。

注意,需要特判 1 的情况。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <iostream>
 
using namespace std;
 
int main()
{
    long long N;
    while(cin >> N)
    {
        if(N < 0) { break; }
        long long nPercent = N * 25;
        if(N == 1) { nPercent = 0; }
        cout << nPercent << "%" << endl;
    }
    return 0;
}

UVaOJ 10790

映射法:每个四边形对应一条对角线——每条对角线对应一个交点。

题目转化为求四边形的个数,即为 $$\binom{N}{2} \cdot \binom{M}{2}$$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <iostream>
 
using namespace std;
 
int main()
{
    int nCase = 0;
    long long x, y;
    while(cin >> x >> y)
    {
        if(x == 0 && y == 0) { break; }
        long long ans = x * (x - 1) * y * (y - 1) / 4;
        cout << "Case " << ++nCase << ": " << ans << endl;   
    }
    return 0;
}

UVaOJ 11044

由于边缘不需要计算,那么答案就是 $$\left\lceil\frac{W-2}{3}\right\rceil \cdot \left\lceil\frac{H-2}{3}\right\rceil$$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <math.h>
 
using namespace std;
 
int main()
{
    int T, W, H;
    cin >> T;
    for(int i = 1; i <= T; i++)
    {
        cin >> W >> H;
        int x = (W - 2) / 3 + ((W - 2) % 3 != 0);
        int y = (H - 2) / 3 + ((H - 2) % 3 != 0);
        cout << x * y << endl;
    }
    return 0;
}

UVaOJ 10719

模拟多项式除法,只要会多项式除法,写起来就非常的轻松。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <memory.h>
#include <string>
#include <sstream>
 
using namespace std;
 
const int MAX = 10240;
 
int pData[MAX], pAns[MAX];
 
int main()
{
    int k;
    string x;
    while(cin >> k)
    {
        memset(pData, 0, sizeof(pData));
        memset(pAns, 0, sizeof(pAns));
        int nCnt = 0, nPos = 1, r = 0;
        cin.ignore();
        getline(cin, x);
        istringstream iss(x);
        while(iss >> pData[++nCnt]);
        nCnt--;
        while(nPos < nCnt)
        {
            if(pData[nPos] != 0)
            {
                pAns[nPos] = pData[nPos];
                pData[nPos] = 0;
                pData[nPos + 1] += k * pAns[nPos];
            }
            nPos++;
        }
        if(pData[nPos]) { r = pData[nPos]; }
        cout << "q(x):";
        for(int i = 1; i < nPos; i++)
        { cout << " " << pAns[i]; }
        cout << endl;
        cout <<"r = " << r << endl;
         
    }
    return 0;
}

UVaOJ 10177

结论题。对于 $w$ 维正方体,边长为 $N$,其中包含的正方体($S$)、长方体($R$)的个数为:$$ S(w) = 1^w + 2^w + 3^w + … + N^w$$ $$R(w) = \left(\frac{N \cdot (N + 1)}{2}\right)^w - S(w)$$

这里补充一下幂级数求和公式:$$S(4) = \frac{N \cdot (N + 1) \cdot \left(3 N^2 + 3 N - 1\right)}{30}$$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
 
using namespace std;
 
int main()
{
    long long N;
    while(cin >> N)
    {
        long long s2 = (N * (N + 1) * (2 * N + 1)) / 6;
        long long s3 = (N * (N + 1) / 2) * (N * (N + 1) / 2);
        long long s4 = (N * (N + 1) * (2 * N + 1) * (3 * N * N + 3 * N - 1)) / 30;
        long long r2 = (N * (N + 1) / 2) * (N * (N + 1) / 2) - s2;
        long long r3 = (N * (N + 1) / 2) * (N * (N + 1) / 2) * (N * (N + 1) / 2) - s3;
        long long r4 = (N * (N + 1) / 2) * (N * (N + 1) / 2) * (N * (N + 1) / 2) * (N * (N + 1) / 2) - s4;
        cout << s2 << " " << r2 << " " << s3 << " " << r3 << " " << s4 << " " << r4 << endl;
    }
    return 0;
}

UVaOJ 10916

我们知道 $2^N < N! < 2^{(N + 1)}$,以 2 为底取对数得 $$N < \log{1} + \log{2} + \log{3} + \cdots + \log{N} < N + 1$$

这样,模拟一下就可以得到答案。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <math.h>
 
using namespace std;
 
int main()
{
    int N;
    while(cin >> N)
    {
        if(N == 0) { break; }
        int k = (N - 1960) / 10 + 2;
        double dSum = 0.0;
        for(int i = 1; ; i++)
        {
            dSum += log(i) / log(2);
            if(dSum > (1 << k)) { cout << i - 1 << endl; break; }
        }
    }
    return 0;
}

UVaOJ 10970

记得在 Codeforces 上做过,当时被 hack 了。这里数据范围比较小,所以可以直接用 int

$$ \mathrm{ans} = xy - 1$$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <iostream>
 
using namespace std;
 
int main()
{
    int x, y;
    while(cin >> x >> y)
    { cout << x * y - 1 << endl; }
    return 0;
}

UVaOJ 10014

这道题目也需要推导公式。根据题目条件,我们有:$$\begin{cases}2 \cdot a_1 = a_0 + a_2 - 2 \cdot c_1\\ 2 \cdot a_2 = a_1 + a_3 - 2 \cdot c_2\\ 2 \cdot a_3 = a_2 + a_4 - 2 \cdot c_3\\ \cdots \\ 2 \cdot a_N = a_{N-1} + a_{N+1} - 2 \cdot c_N \end{cases}$$ 将第一个式子分别加到下面 $N - 1$ 个式子上,得到:$$\begin{cases}2 \cdot a_1 = a_0 + a_2 - 2 \cdot c_1\\ a_1 + a_2 = a_0 + a_3 - 2 \cdot \left(c_1 + c_2\right)\\ a_1 + a_3 = a_0 + a_4 - 2 \cdot \left(c_1 + c_2 + c_3\right)\\ \cdots \\ a_1 + a_N = a_0 + a_{N+1} - 2 \cdot \left(c_1 + c_2 + c_3 + \cdots + c_N\right) \end{cases}$$ 将上面 $N$ 个式子累加,得到:$$ (N + 1) \cdot a_1 = N \cdot a_0 + a_N + 1 - 2 \cdot \left(N \cdot c_1 + (N - 1) \cdot c_2 + (N - 2) \cdot c_3 + \cdots + c_N\right)$$ 由此,便可得到 $a_1$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <iomanip>
 
using namespace std;
 
int main()
{
    int T, N;
    double s, e;
    cin >> T;
    for(int i = 1; i <= T; i++)
    {
        double ans = 0, dTmp;
        cin >> N;
        cin >> s >> e;
        ans = N * s + e;
        for(int j = 1; j <= N; j++)
        {
            cin >> dTmp;
            ans -= 2.0 * (N - j + 1) * dTmp;
        }
        cout << fixed << setprecision(2) << ans / (N + 1) << endl;
        if(i != T) { cout << endl; }
    }
    return 0;
}

刷完数学专题,感觉数学题目的思维量还是很大的,同时也要注意浮点数对结果造成的误差。