编程珠玑

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>0k > 0 的情况。

然后，我们令 S=⨁1⨁2⨁3⨁⋯⨁NS = \bigoplus 1\bigoplus 2\bigoplus 3\bigoplus\cdots\bigoplus N，其中 ⨁\bigoplus 为正负号。

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

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

因此，只要求最小的 NN，使得 S>kS > k，并且满足 S−kS - k 为偶数，因为每次变换 ⨁\bigoplus 的符号对 SS 的改变量为偶数。

 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

这道题目需要推导公式，我们令要输出的答案分别为 xx 和 yy。

假设 kk 代小猫（包括第一代），每个小猫帽子里有 NN 个小猫。

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

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

将 kk 约去，得到 log⁡H⋅log⁡N=log⁡(N+1)⋅log⁡C\log{H}\cdot\log{N} = \log{\left(N + 1\right)}\cdot\log{C}

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

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

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

当 N≠1N \neq 1 时 x=1−Nk1−N=1−C1−N=C−1N−1x = \frac{1 - N^k}{1 - N} = \frac{1 - C}{1 - N} = \frac{C - 1}{N - 1}

为了计算所有小猫的身高，我们可以得到另一个等比数列 y=H+N⋅(NN+1)⋅H+N2⋅(NN+1)2⋅H+⋯+Nk⋅(NN+1)k⋅Hy = 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=1N = 1 时 y=H⋅(1+12+14+18+⋯+12k)=H⋅(2−12k)=2⋅H−H⋅12k=2⋅H−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)^K = H，代入 N=1N = 1 得 2k=H2^k = H

当 N≠1N \neq 1 时 y=H⋅1−(N2N+1)k1−N2N+1=(N+1)⋅H−C⋅N 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=1N = 1 时，必有 C=1C = 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−xd = y - x（其中 xx 和 yy 为输入数据），s = floor(sqrt(d))，规律如下：s={2s−1,s2=d2s+1,s(s+1)<d2s,otherwises = \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=1R = 1，那么表面积 S=4πS = 4\pi。分割成 NN 部分，表面积增加 N⋅πN\cdot \pi。那么答案即为 N/4×100=25NN / 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

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

题目转化为求四边形的个数，即为 (N2)⋅(M2)\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

由于边缘不需要计算，那么答案就是 ⌈W−23⌉⋅⌈H−23⌉\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

结论题。对于 ww 维正方体，边长为 NN，其中包含的正方体（SS）、长方体（RR）的个数为：S(w)=1w+2w+3w+…+Nw S(w) = 1^w + 2^w + 3^w + … + N^w R(w)=(N⋅(N+1)2)w−S(w)R(w) = \left(\frac{N \cdot (N + 1)}{2}\right)^w - S(w)

这里补充一下幂级数求和公式：S(4)=N⋅(N+1)⋅(3N2+3N−1)30S(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

我们知道 2N<N!<2(N+1)2^N < N! < 2^{(N + 1)}，以 2 为底取对数得 N<log⁡1+log⁡2+log⁡3+⋯+log⁡N<N+1N < \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。

ans=xy−1 \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

这道题目也需要推导公式。根据题目条件，我们有：{2⋅a1=a0+a2−2⋅c12⋅a2=a1+a3−2⋅c22⋅a3=a2+a4−2⋅c3⋯2⋅aN=aN−1+aN+1−2⋅cN\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−1N - 1 个式子上，得到：{2⋅a1=a0+a2−2⋅c1a1+a2=a0+a3−2⋅(c1+c2)a1+a3=a0+a4−2⋅(c1+c2+c3)⋯a1+aN=a0+aN+1−2⋅(c1+c2+c3+⋯+cN)\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} 将上面 NN 个式子累加，得到：(N+1)⋅a1=N⋅a0+aN+1−2⋅(N⋅c1+(N−1)⋅c2+(N−2)⋅c3+⋯+cN) (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) 由此，便可得到 a1a_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;
}

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

© 2012 - 2024 退思轩
使用 Hugo 构建
主题 Stack 由 Jimmy 设计