解題區/解題區 - UVa

UVa 13046 - Bus Collisions

Problem

給予兩個公車行駛路線，每台公車的速度都相同，分別從起始位置出發，請問第一個碰撞位置為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
4
0  4
2  4
2  5
0  5
4
1  7
1  2
3  2
3  7
4
5  0
6  0
6  1
5  1
4
7  0
8  0
8  1
7  1

Sample Output

1
2
Case 1: 1 5
Case 2: No Collision

Solution

抓路線長度的最小公倍數，一定能在這段時間內找到碰撞位置，否則不存在碰撞地點。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
struct Pt {
    int x, y;
    Pt(int x = 0, int y = 0): x(x), y(y) {
    }
    int dist(Pt u) {
        return abs(x - u.x) + abs(y - u.y);
    }
    bool operator==(const Pt &u) const {
        return x == u.x && y == u.y;
    }
    Pt operator-(const Pt &u) const {
        return Pt(x - u.x, y - u.y);
    }
    Pt operator+(const Pt &u) const {
        return Pt(x + u.x, y + u.y);
    }
};
int main() {
    int testcase, cases = 0;
    int N[2], x, y;
    Pt R[2][64];
    scanf("%d", &testcase);
    while (testcase--) {
        int Len[2] = {};
        for (int i = 0; i < 2; i++) {
            scanf("%d", &N[i]);
            for (int j = 0; j < N[i]; j++) {
                scanf("%d %d", &x, &y);
                R[i][j] = Pt(x, y);
            }
            for (int j = 0; j < N[i]; j++)
                Len[i] += R[i][j].dist(R[i][(j+1)%N[i]]);
        }
        
        printf("Case %d: ", ++cases);
        
        int simT = Len[0]/__gcd(Len[0], Len[1])*Len[1];
        int posIdx[2], has = 0;
        Pt posXY[2];
        for (int i = 0; i < 2; i++)
            posIdx[i] = 0, posXY[i] = R[i][0];
            
        for (int it = 0; it < simT; it++) {
            for (int i = 0; i < 2; i++) {
                // move
                if (posXY[i] == R[i][posIdx[i]])
                    posIdx[i] = (posIdx[i]+1)%N[i];
                Pt dv = R[i][posIdx[i]] - posXY[i];
                int lenDv = abs(dv.x) + abs(dv.y);
                dv.x /= lenDv, dv.y /= lenDv;
                posXY[i] = posXY[i] + dv;
            }
            if (posXY[0] == posXY[1]) {
                printf("%d %d\n", posXY[0].x, posXY[0].y);
                has = 1;
                break;
            }
        }
        if (!has)
            puts("No Collision");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1718 - Tile Cutting

Problem

請問在網格中，若頂點設置在網格邊上，構成平行四邊形的面積介於 $[l, r]$，最多的方法數和面積分別為多少。

Sample Input

1
2
3
2
4 4
2 6

Sample Output

1
2
48
620

Solution

由於是平行四邊形，假設矩形被劃分的兩個對稱三角形的底高 $a, b, c, d$，且 $a, b, c, d > 0$。

得到平行四邊形面積為

$$\begin{align*} \text{Area} &= (a + c)(b + d) - 2 \times 0.5 \times a b - 2 \times 0.5 \times c d \\ &= ad + bc \end{align*}$$

最後找到構成方法數為 ways of area = #(a, b, c, d) sat. ad + bc = Area。分別統計兩數相乘為 $x$ 的方法數 $W_x$，可以構成多項式 $W_1 x + W_2 x^2 + \cdots W_n x^n$，多項式相乘後，得到的係數就是所有的方法數。套用 FFT 的卷積計算即可。

FFT

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <algorithm>
#include <complex>
using namespace std;
struct Complex {
    double x, y;
    Complex(double x = 0, double y = 0): x(x), y(y) {}
    Complex operator-(const Complex &v) const {
        return Complex(x-v.x,y-v.y);
    }
    Complex operator+(const Complex &v) const {
        return Complex(x+v.x,y+v.y);
    }
    Complex operator*(const Complex &v) const {
        return Complex(x*v.x-y*v.y,x*v.y+y*v.x);
    }
    Complex operator/(const int &v) const {
        return Complex(x/v,y/v);
    }
    double real() {
        return x;
    }
};
template<typename T> class TOOL_FFT {
public:
typedef unsigned int UINT32;
#define MAXN (1048576<<1)
    Complex p[2][MAXN];
    int pre_n;
    T PI;
    TOOL_FFT() {
        pre_n = 0;
        PI = acos(-1);
    }
    int NumberOfBitsNeeded(int PowerOfTwo) {
        for (int i = 0; ; ++i) {
            if (PowerOfTwo & (1 << i)) {
                return i;
            }
        }
    }
    inline UINT32 FastReverseBits(UINT32 a, int NumBits) {
        a = ( ( a & 0x55555555U ) << 1 ) | ( ( a & 0xAAAAAAAAU ) >> 1 ) ;
        a = ( ( a & 0x33333333U ) << 2 ) | ( ( a & 0xCCCCCCCCU ) >> 2 ) ;
        a = ( ( a & 0x0F0F0F0FU ) << 4 ) | ( ( a & 0xF0F0F0F0U ) >> 4 ) ;
        a = ( ( a & 0x00FF00FFU ) << 8 ) | ( ( a & 0xFF00FF00U ) >> 8 ) ;
        a = ( ( a & 0x0000FFFFU ) << 16 ) | ( ( a & 0xFFFF0000U ) >> 16 ) ;
        return a >> (32 - NumBits);
    }
    
    void FFT(bool InverseTransform, vector<Complex>& In, vector<Complex>& Out) {
        // simultaneous data copy and bit-reversal ordering into outputs
        int NumSamples = In.size();
        int NumBits = NumberOfBitsNeeded(NumSamples);
        for (int i = 0; i < NumSamples; ++i) {
            Out[FastReverseBits(i, NumBits)] = In[i];
        }
        // the FFT process
        for (register int i = 1; i <= NumBits; i++) {
            int BlockSize = 1<<i, BlockEnd = BlockSize>>1, BlockCnt = NumSamples/BlockSize;
            for (register int j = 0; j < NumSamples; j += BlockSize) {
                Complex *t = p[InverseTransform];
                for (register int k = 0; k < BlockEnd; k++, t += BlockCnt) {
                    Complex a = (*t) * Out[k+j+BlockEnd];
                    Out[k+j+BlockEnd] = Out[k+j] - a;
                    Out[k+j] = Out[k+j] + a;
                }
            }
        }
        // normalize if inverse transform
        if (InverseTransform) {
            for (int i = 0; i < NumSamples; ++i) {
                Out[i] = Out[i] / NumSamples;
            }
        }
    }
    void prework(int n) {
        if (pre_n == n)
            return ;
        pre_n = n;
        p[0][0] = Complex(1, 0);
        p[1][0] = Complex(1, 0);
        for (register int i = 1; i < n; i++) {
            p[0][i] = Complex(cos(2*i*PI / n ) , sin(2*i*PI / n ));
            p[1][i] = Complex(cos(2*i*PI / n ) , -sin(2*i*PI / n ));
        }
    }
    vector<T> convolution(Complex *a, Complex *b, int n) {
        prework(n);
        vector<Complex> s(a, a+n), d1(n), d2(n), y(n);
        vector<T> ret(n);
        FFT(false, s, d1);
        s[0] = b[0];
        for (int i = 1, j = n-1; i < n; ++i, --j)
            s[i] = b[j];
        FFT(false, s, d2);
        for (int i = 0; i < n; ++i) {
            y[i] = d1[i] * d2[i];
        }
        FFT(true, y, s);
        for (int i = 0; i < n; ++i) {
            ret[i] = s[i].real();
        }
        return ret;
    }
};
TOOL_FFT<double> tool;
Complex a[MAXN], b[MAXN];
vector<double> c;
long long ret[1048576];
long long pr[1048576] = {};
int main() {
    int m;
    const int N = 500000;
    for (m = 1; m < (N<<1); m <<= 1);
    /*
		(a + c)(b + d) - 2 * 0.5 * (a b) - 2 * 0.5 * (c * d)
		= ad + bc = area
		a, b, c, d > 0,
		ways of area = #(a, b, c, d) sat. ad + bc = area
	*/
    for (int i = 1; i <= N; i++) {
    	for (int j = i; j <= N; j += i)
    		pr[j]++;
    }	
    
    memset(a, 0, sizeof(a[0]) * m);
    memset(b, 0, sizeof(b[0]) * m);
    
    for (int i = 1; i <= N; i++) {
        a[i] = Complex(pr[i], 0);
        b[m-i] = Complex(pr[i], 0);
    }	
    
    c = tool.convolution(a, b, m);
    
    for (int i = 1; i <= N; i++)
        ret[i] = (long long) (c[i] + 0.5);
        
    int testcase, L, R;
    while (scanf("%d", &testcase) == 1) {
        while (testcase--)	 {
            scanf("%d %d", &L, &R);
            assert(L <= R);
            assert(L >= 1 && R <= 500000);
            int mxA = L;
            for (int i = L; i <= R; i++) {
                if (ret[i] > ret[mxA])
                    mxA = i;
            }
            printf("%d %lld\n", mxA, ret[mxA]);
        }
    }
    return 0;
}

NTT

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <assert.h>
#include <algorithm>
#include <complex>
using namespace std;
typedef unsigned int UINT32;
typedef long long INT64;
class TOOL_NTT {
public:
#define MAXN (1048576<<1)
    const INT64 P = (479 << 21) + 1LL; // prime m = kn+1
    const INT64 G = 3;
    INT64 wn[22];
    INT64 s[MAXN], d1[MAXN], d2[MAXN], y[MAXN];
    TOOL_NTT() {
        for (int i = 0; i < 22; i++)
            wn[i] = mod_pow(G, (P-1) / (1<<i), P);
    }
    INT64 mod_mul(INT64 a, INT64 b, INT64 mod) {
        return (a*b - (long long)(a/(long double)mod*b+1e-3)*mod+mod)%mod;
//              INT64 ret = 0;
//              for (a = a >= mod ? a%mod : a, b = b >= mod ? b%mod : b; b != 0; b>>=1, a <<= 1, a = a >= mod ? a - mod : a) {
//                  if (b&1) {
//                      ret += a;
//                      if (ret >= mod)
//                          ret -= mod;
//                  }
//              }
//              return ret;
    }
    INT64 mod_pow(INT64 n, INT64 e, INT64 m) {
        INT64 x = 1;
        for (n = n >= m ? n%m : n; e; e >>= 1) {
            if (e&1)
                x = mod_mul(x, n, m);
            n = mod_mul(n, n, m);
        }
        return x;
    }
    int NumberOfBitsNeeded(int PowerOfTwo) {
        for (int i = 0;; ++i) {
            if (PowerOfTwo & (1 << i)) {
                return i;
            }
        }
    }
    inline UINT32 FastReverseBits(UINT32 a, int NumBits) {
        a = ( ( a & 0x55555555U ) << 1 ) | ( ( a & 0xAAAAAAAAU ) >> 1 ) ;
        a = ( ( a & 0x33333333U ) << 2 ) | ( ( a & 0xCCCCCCCCU ) >> 2 ) ;
        a = ( ( a & 0x0F0F0F0FU ) << 4 ) | ( ( a & 0xF0F0F0F0U ) >> 4 ) ;
        a = ( ( a & 0x00FF00FFU ) << 8 ) | ( ( a & 0xFF00FF00U ) >> 8 ) ;
        a = ( ( a & 0x0000FFFFU ) << 16 ) | ( ( a & 0xFFFF0000U ) >> 16 ) ;
        return a >> (32 - NumBits);
    }
    void NTT(int on, INT64 *In, INT64 *Out, int n) {
        int NumBits = NumberOfBitsNeeded(n);
        for (int i = 0; i < n; ++i)
            Out[FastReverseBits(i, NumBits)] = In[i];
        for(int h = 2, id = 1; h <= n; h <<= 1, id++) {
            for(int j = 0; j < n; j += h) {
                INT64 w = 1, u, t;
                int block = h/2, blockEnd = j + h/2;
                for(int k = j; k < blockEnd; k++) {
                    u = Out[k], t = mod_mul(w, Out[k+block], P);
                    Out[k] = u + t;
                    Out[k + block] = u - t + P;
                    if (Out[k] >= P)        Out[k] -= P;
                    if (Out[k+block] >= P)  Out[k+block] -= P;
                    w = mod_mul(w, wn[id], P);
                }
            }
        }
        if (on == 1) {
            for (int i = 1; i < n/2; i++)
                swap(Out[i], Out[n-i]);
            INT64 invn = mod_pow(n, P-2, P);
            for (int i = 0; i < n; i++)
                Out[i] = mod_mul(Out[i], invn, P);
        }
    }
    void convolution(INT64 *a, INT64 *b, int n, INT64 *c) {
        NTT(0, a, d1, n);
        s[0] = b[0];
        for (int i = 1; i < n; ++i)
            s[i] = b[n-i];
        NTT(0, s, d2, n);
        for (int i = 0; i < n; i++)
            s[i] = mod_mul(d1[i], d2[i], P);
        NTT(1, s, c, n);
    }
} tool;
INT64 a[MAXN], b[MAXN], c[MAXN];
long long ret[1048576];
long long pr[1048576] = {};
int main() {
    int m;
    const int N = 500000;
    for (m = 1; m < (N<<1); m <<= 1);
    /*
		(a + c)(b + d) - 2 * 0.5 * (a b) - 2 * 0.5 * (c * d)
		= ad + bc = area
		a, b, c, d > 0,
		ways of area = #(a, b, c, d) sat. ad + bc = area
	*/
    for (int i = 1; i <= N; i++) {
    	for (int j = i; j <= N; j += i)
    		pr[j]++;
    }	
    
    memset(a, 0, sizeof(a[0]) * m);
    memset(b, 0, sizeof(b[0]) * m);
    
    for (int i = 1; i <= N; i++) {
        a[i] = pr[i];
        b[m-i] = pr[i];
    }	
    
    tool.convolution(a, b, m, c);
    
    for (int i = 1; i <= N; i++)
        ret[i] = c[i];
        
    int testcase, L, R;
    while (scanf("%d", &testcase) == 1) {
        while (testcase--)	 {
            scanf("%d %d", &L, &R);
            assert(L <= R);
            assert(L >= 1 && R <= 500000);
            int mxA = L;
            for (int i = L; i <= R; i++) {
                if (ret[i] > ret[mxA])
                    mxA = i;
            }
            printf("%d %lld\n", mxA, ret[mxA]);
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 801 - Flight Planning

Problem

給予飛機在平流層飛行資訊，在每一種高度下維持飛行的耗油量成線性關係，以及每一段飛行旅程上的平流層的風速為何，藉由線性內插得到在某高度下的飛行速度，忽略在轉換高度時的耗油量，問從起點到終點的最少耗油量為何 (無條件進位)。

Sample Input

1
2
3
4
5
6
7
8
2
2
1500 -50 50
1000 0 0
3
1000 50 0
2000 0 20
1800 50 100

Sample Output

1
2
Flight 1: 35 30 13986
Flight 2: 20 30 30 23502

Solution

單源最短路徑，只是每一點要使用 $20$ 個狀態維護抵達那一層時在哪一種高度下飛行。必須窮舉轉移到下一層的所有高度，因為有可能飛行慢而增加耗油時間。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Leg {
    double mile, f20, f40;
} legs[1024];
const double VCRUISE = 400;
const double AOPT = 30000;
const double GPHOPT = 2000;
const double GPHEXTRA = 10;
const double CLIMBCOST = 50;
const int MAXN = 1024;	// maximum #legs
const int MAXH = 45;	// between 20,000 and 40,000 feet
const double DINF = 1e+20;
double inter(Leg a, double h) {
    return a.f20 + (a.f40 - a.f20) * (h - 20000) / (40000 - 20000);
}
void solve(int n) {
    double dp[MAXN][MAXH];
    int from[MAXN][MAXH];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= 40; j++)
            dp[i][j] = DINF;
    }
    
    dp[0][0] = 0;	// leg 0: altitude 0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= 40; j++) {
            if (dp[i][j] >= DINF)
                continue;
            double alti_a = j * 1000.f;
            for (int k = 20; k <= 40; k++) {
                double cc = 0, alti_b;
                alti_b = k * 1000.f;
                
                if (alti_b > alti_a)
                    cc += CLIMBCOST * (alti_b - alti_a) / 1000.f;
                double v = VCRUISE + inter(legs[i+1], alti_b);
                if (v <= 0)
                	continue;
                double c = fabs(alti_b - AOPT) * GPHEXTRA / 1000.f + GPHOPT;
                cc += c * legs[i+1].mile / v;
                if (dp[i][j] + cc < dp[i+1][k])
                    dp[i+1][k] = dp[i][j] + cc, from[i+1][k] = j;
            }
        }
    }
    
    double ret = DINF;
    int last = -1;
    vector<int> solution;
    for (int i = 20; i <= 40; i++) {
        if (dp[n][i] < ret)
            ret = dp[n][i], last = i;
    }
    for (int i = n; i > 0; i--) {
        solution.push_back(last);
        last = from[i][last];
    }
    for (int i = n-1; i >= 0; i--)
        printf(" %d", solution[i]);
    // tricky 
    printf(" %.0lf\n", ceil(ret));
}
int main() {
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lf %lf %lf",
                  &legs[i].mile, &legs[i].f20, &legs[i].f40);
        }
        printf("Flight %d:", ++cases);
        solve(n);
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

2016 Google Code Jam Round 1A

A. The Last Word

每一字串 $S$，可視為一串操作，依序讀入一個字元 $C$，可以選擇把字元 $C$ 插入字串首或尾，請問字典順序最大為何？

類似 ZJ. 一串數字 之類的貪心方式，優先考慮最大字元在哪一個位置，抓取之後拆分兩串分開貪心合併，每一次由後往前找到第一個最大字典順序字元 $T$，$T$ 移到最前方，此時會將字串分成前半 $A$ 和後半 $B$，然而後半 $B$ 要排在 $T$ 字元之後，勢必只能按照順序丟入隊尾。因此 $\textit{MAXEXPR}(F) = T + \textit{MAXEXPR}(A) + B$。

B. Rank and File

給定一個 $N \times N$ 方格，每一行或列都是嚴格遞增，現在給定數個行、數個列的排列情況，請問缺漏的那一行或列的序列為何？

明顯地每一個數字都恰好出現偶數次，按照大小順序印出奇數次數字即可。

C. BFFs

給同學都有一位摯友，給定 $N$ 個人的好友資訊，現在要求盡可能多的人圍成一圈，並且每一個人其中一側是他們自己的摯友，請問圈最多幾個人。

明顯地，若不看方向性，每一個連通圖至多一個環。若一個連通圖式一個環，保證無法與其他方案合併在一起，因此用 $\mathcal{O}(N^2)$ 優先排除是環的解，在其中找最大圈即可。

接著考慮有觸手的水母圖，當水母大小恰好由兩個點構成時才會有解，因為三個點以上不符合題目要求的環。最後找到經過兩端點的最長觸手，這些點可以自我滿足，把所有最長觸手合併在一起可以構成一組特殊解。兩種方案取最大。

Solution

A

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
#include <bits/stdc++.h>
using namespace std;
string dfs(int n, string s) {
    if (n == 0)	return "";
    char mx = s[0];
    for (int i = 0; i < n; i++)
        mx = max(mx, s[i]);
    for (int i = n-1; i >= 0; i--) {
        if (s[i] == mx) {
            string mm = string(1, mx);
            return mm + dfs(i, s.substr(0, i)) + s.substr(i+1) ;
        }
    }
    return "";
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        char cs[1024];
        scanf("%s", cs);
        int n = strlen(cs);
        string v = dfs(n, cs);
        printf("Case #%d: %s\n", ++cases, v.c_str());
    }
    return 0;
}

B

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 <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, m, x;
        map<int, int> R;
        scanf("%d", &n);
        m = 2*n-1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &x);
                R[x]++;
            }
        }
        printf("Case #%d:", ++cases);
        for (auto e : R) {
            if (e.second % 2 == 1)
                printf(" %d", e.first);
        }
        puts("");
    }
    return 0;
}

C

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
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
int g[1024][1024];
vector<int> gg[1024];
int cc[1024];
int dfs(int u, int dep) {
    int ret = dep;
    for (auto v : gg[u]) {
        if (cc[v])	continue;
        int tmp = dfs(v, dep+1);
        ret = max(ret, tmp);
    }
    return ret;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, A[1024];
        
        memset(g, 0, sizeof(g));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            gg[i].clear();
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]), g[i][A[i]] = 1, gg[A[i]].push_back(i);
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            int used[1024] = {};
            int u = i, cnt = 0;
            for (; used[u] == 0; u = A[u]) {
                used[u] = 1, cnt++;
            }
            if (u == i) 
                ret = max(ret, cnt);
        }
        memset(cc, 0, sizeof(cc));
        int cctot = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j)	continue;
                if (cc[i] || cc[j])	continue;
                if (g[i][j] == 0 || g[j][i] == 0)
                    continue;
                cc[i] = 1, cc[j] = 1;
                cctot += 2;
                cctot += dfs(i, 0) + dfs(j, 0);
            }
        }
        ret = max(ret, cctot);
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

2016 Google Code Jam Round QR

一年一度的 GCJ 資格賽又開打了，這次的題目類型挺開放的，也就是有很多不同的解法可以通過。也許是因為都用了奇怪的方法解決。全寫完 Rank 400 名以內。

打完比賽完全沒心情寫水泥數學的作業證明。不！其實是不會寫。

A. Counting Sheep

睡覺前數羊，從一個基數 $N$ 開始，數 $N$, $2N$, $3N$, …, $?N$，直到 10 個位數都出現過，請問最後一個數的數 $?N$ 為何。

除了 $N = 0$ 的特殊情況外，直接模擬即可。最重要的是它不只有看個位數字，把每一位全看的狀況下，要湊滿 0-9 所有 digits 都出現過就不是難事。

B. Revenge of the Pancakes

現在 $N$ 個煎餅位於堆上，並且有分成兩個正反面狀態，每一次可以把煎餅從堆頂開始連續得拿出，並反轉序列放回堆中，同時把煎餅正反反轉，請問從一個開始序列轉移到全部皆為正面的操作次數最少為何？

一開始的策略是亂貪心一番，甚至題目看錯都能亂過小測資。必要任務一定是先把堆底那片煎餅翻成正的，這時一定堆頂為反，進行一次反轉讓堆底便成正的，為了讓堆頂為反，貪心策略盡可能讓堆頂一連續全部變成反。不斷地模擬此步驟即可。

C. Coin Jam

產生一個數字 $X$，$X$ 長度恰為 $N$，必須首尾皆為 1，只能由 0/1 構成。請產生數字 $X$，滿足在二進制、三進制 … 到十進制下皆為合成數。

這題莫名其妙指定 $N = 16, \; 32$，特殊的 $N$ 使得找到 $J$ 個 $X$ 並不難，更由於 $J$ 不大，各種解法都可以完成。從以往得概念，假設有一個數字 $A = 123123$，那麼保證不進位的情況下，找得到一組 $A = 123 \times 1001$，因此指定 $A = 1????1$，湊滿 $X = AA \cdots A$，不管在哪個進制下，勢必被 $A$ 整除。

D. Fractiles

詭異的數學碎形考古，給一個長度為 $K$ 的起始字串 $X$，$X$ 只由 $G$ 和 $L$ 構成。碎形迭代 $C$ 次，產生長度為 $K^C$ 的字串。現在雇用 $S$ 個學生，每個學生只能檢查一個位子，只要確定那一個位子有 $G$，那麼原始字串保證有 $G$。在限定學生數量下，請問要怎麼安排學生們的檢查工作。

由於長度為 $K$ 的起始字串有 $2^K$ 種，實際上只要剃除 $LL \cdots L$ 的字串。為了要在最少檢查位置下處理，必然要一個位置能否有 $G$，就能檢查原始字串的數個位置是否有 $G$。

窮舉只有 1 個 $G$ 個字串 $GLL...L$、$LGL...L$、… 等 $K$ 個，追蹤迭代 $C$ 次後，$K^C$ 長度下，每一個字串 $G$ 的出現位置。當 $C = 2$，可以讓位置 1, 2 的 $G$ 可以同時被檢查，同理位置 3, 4 的 $G$ 可以同時被檢查。當 $C = 3$ 時，位置 1, 2, 3 的 $G$ 可以同時被檢查。根據觀察，至少要 $\textit{ceil}(K/C)$ 個學生就能滿足需求。

第 $i$ 個學生要檢查的位置為 $1 + \sum_{0 \le j < C} (C(i-1)+(C-1-j))K^j$。

Solution

A

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 <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        long long n;
        scanf("%lld", &n);
        if (n == 0) {
            printf("Case #%d: INSOMNIA\n", ++cases);
            continue;
        }
        int has[128] = {}, ten = 10;
        long long on = n;
        while (1) {
            static char buf[32];
            sprintf(buf, "%lld", n);
            for (int i = 0; buf[i]; i++) {
                if (has[buf[i]] == 0) {
                    ten--, has[buf[i]] = 1;
                }
            }
            if (ten == 0)
                break;
            n += on;
        }
        printf("Case #%d: %lld\n", ++cases, n);
    }
    return 0;
}

B

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    char s[1024];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%s", s);
        int n = strlen(s), ret = 0;
        for (int i = n-1; i >= 0; i--) {
            if (s[i] == '+')	continue;
            int has = 0, j = 0;
            for (j = 0; j <= i; j++) {
                if (s[j] == '-')	break;
                has = 1;
            }
            if (has) {
                reverse(s, s+j);
                for (int k = 0; k < j; k++) {
                    if (s[k] == '-')
                        s[k] = '+';
                    else
                        s[k] = '-';
                }
            }
            ret += has;
            if (s[i] == '+')	continue;
            reverse(s, s+i+1);
            for (int k = 0; k < i+1; k++) {
                if (s[k] == '-')
                    s[k] = '+';
                else
                    s[k] = '-';
            }
            ret++;
        }
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}

C

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases;
    scanf("%d", &testcase);
    while (testcase--) {
        int N, J;
        scanf("%d %d", &N, &J);
        printf("Case #%d:\n", ++cases);
        set<long long> R;
        for (int i = 2; i < N && J; i++) {
            if (N%i)	continue;
            for (int j = 0; j < (1<<(i-2)) && J; j++) {
                int mask = (j<<1)|1|(1<<(i-1));
                long long v = 0;
                for (int k = 0; k < N/i; k++)
                    v = (v<<i) | mask;
                if (R.count(v))	continue;
                R.insert(v);
                for (int k = N-1; k >= 0; k--)
                    printf("%d", (v>>k)&1);
                for (int B = 2; B <= 10; B++) {
                    long long div = 0, nn = 0;
                    for (int k = i-1; k >= 0; k--)
                        div = div * B + ((mask>>k)&1);
                    for (int k = N-1; k >= 0; k--)
                        nn = nn * B + ((v>>k)&1);
//					assert(nn % div == 0 && nn != div);
                    printf(" %lld", div);
                }
                puts("");
                J--;
            }
        }
        assert(J == 0);
    }
    return 0;
}
/*
1
16 3
*/

D

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
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
long long mpow(long long x, long long y) {
    long long ret = 1;
    while (y) {
        if (y&1)
            ret = ret * x;
        y >>= 1, x = x*x;
    }
    return ret;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        long long K, C, S;
        scanf("%lld %lld %lld", &K, &C, &S);
        printf("Case #%d:", ++cases);
        
        int pos = 0;
        vector<unsigned long long> A;
//		puts("");
        for (int i = 0; i < ceil(1.f*K/C); i++) {
            int item = min(C, K - pos);
            unsigned long long x = 0;
            for (int j = C-1, k = 0; j >= 0 && k < item; j--, k++) {
//				printf("%d K^%d + ", pos + k, j);
                x += (pos + k) * mpow(K, j);
            }
            A.push_back(x);
//			puts("");
            pos += C;
            if (pos > K)	pos = K;
        }
        if (A.size() > S)
            puts(" IMPOSSIBLE");
        else {
            for (int i = 0; i < A.size(); i++)
                printf(" %llu", A[i]+1);
            puts("");
        }
    }
    return 0;
}
/*
5
4 4 5
*/
Read More +
解題區/解題區 - UVa

UVa 13006 - Cake cut

Problem

兩個人均分一個簡單凸多邊形的蛋糕，蛋糕高度為 2。第一個人 $A$ 選擇一個頂點 $u$，第二個人 $B$ 選擇另一個頂點 $v$，兩點連線後，將蛋糕分成兩塊，最大那一塊會被 $A$ 拿走，小的那一塊會被 $B$ 拿走，請問在各自最佳策略下，盡可能拿到最大塊面積的結果為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
5
0  0
3  0
3  1
2  2
0  1
6
0  1
1  0
2  0
3  1
2  2
0  2
4
-100000000  -100000000
100000000  -100000000
100000000  100000000
-100000000  100000000
4
-99999995  -100000000
100000000  -100000000
100000000  99999995
-100000000  100000000

Sample Output

1
2
3
4
7 2
6 3
40000000000000000 40000000000000000
39999999999999975 39999998000000025

Solution

首先，在最佳策略下，當 $u$ 已經固定，接下來選擇頂點 $v$，$B$ 的決定必然要使最小塊最大化，而對於 $A$ 而言，選擇 $B$ 已經使最小塊最大化的所有方法中，使得最大塊最大化。

明顯地兩塊面積近似一半，由於是凸多邊形，可以根據掃描線的方式推動頂點 $v$，使得 $\overline{uv}$ 切分的面積近似一半，對於簡單多邊形面積計算由行列式計算，但行列式計算時的變數呈現環狀，先把首尾變數提出，維護中行列式中間一大段的計算，最後補足首尾變數來計算面積。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <set>
#include <limits.h>
#include <algorithm>
using namespace std;
struct Pt {
    long long x, y;
    Pt(long long a = 0, long long b = 0):
    x(a), y(b) {}
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
};
long long cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
long long area2(Pt o, Pt a, Pt b) {
    return llabs(cross(o, a, b));
}
const int MAXN = 262144;
Pt P[MAXN];
int main() {
    int N;
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i < N; i++) {
            scanf("%lld %lld", &P[i].x, &P[i].y);
            P[i+N] = P[i];
        }
        
        long long area = 0;
        for (int i = 2; i < N; i++)
            area += area2(P[0], P[i-1], P[i]);
        
        long long tmp = 0;
        pair<long long, long long> ret(0, 0);
        tmp += P[0].x * P[1].y - P[0].y * P[1].x;
        tmp += P[1].x * P[2].y - P[1].y * P[2].x;
        for (int i = 0, j = 2; i < N; i++) {
            while (1) {
                long long test = tmp + (P[j].x * P[i].y - P[j].y * P[i].x);
                if (llabs(test)*2 >= area)
                    break;
                tmp += P[j].x * P[j+1].y - P[j].y * P[j+1].x;
                j++;
            }
            long long t1, t2, p1, p2;
            t1 = llabs(tmp + (P[j].x * P[i].y - P[j].y * P[i].x));
            t2 = area - t1;
            p1 = llabs(tmp - (P[j-1].x * P[j].y - P[j-1].y * P[j].x)
                           + (P[j-1].x * P[i].y - P[j-1].y * P[i].x));
            p2 = area - p1;
            if (t1 < t2)    swap(t1, t2);
            if (p1 < p2)    swap(p1, p2);
            if (t1 > p1)    t1 = p1, t2 = p2;
            ret = max(ret, make_pair(t1, t2));
            tmp -= P[i].x * P[i+1].y - P[i].y * P[i+1].x;
        }
        printf("%lld %lld\n", ret.first, ret.second);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13010 - Galactic taxes

Problem

ACM 辦公室在銀河的各處，辦公室編號 $1$ 到 $N$，辦公室 $i$ 和辦公室 $j$ 之間的移動費用隨著時間 $t$ 成線性關係，假設移動不消耗時間，請決定移動時間 $t$，從辦公室 $1$ 移動到辦公室 $N$ 請問最少花費為何。

給定時間必須在一天以內完成，意即 $0 \le t \le 24 \times 60$。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2  1
1  2  1  0
5  8
1  2  27  610658
2  3  -48  529553
3  4  -6  174696
4  5  47  158238
3  5  84  460166
1  3  -21  74502
2  4  -13  858673
1  5  -90  473410
3  3
1  2  1  0
2  3  1  0
1  3  -1  1440
4  5
1  2  1  0
2  4  2  0
1  4  0  500
1  3  -1  1440
3  4  -2  2880
2  1
1  2  0  0

Sample Output

1
2
3
4
5
1440.00000
419431.27273
960.00000
500.00000
0.00000

Solution

明顯地，每一條邊花費都呈現線性關係，假設一張圖只有一條邊，依序加入新的邊進去，時間 $t$ 對應的路徑花費呈現凹性，因此三分搜尋時間 $t$，做一次 Dijkstra $\mathcal{O}(V \log E)$。由於需要精準度到小數五位，估計要到至少三分 50 次，總時間複雜度 $\mathcal{O}(100 V \log E)$。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <set>
#include <algorithm>
using namespace std;
const int MAXV = 2048;
const int MAXE = 131072;
const long long INF = 1e+60;
struct Edge {
    int to, eid;
    double w;
    Edge *next;
};
Edge edge[MAXE], *adj[MAXV];
int e = 0;
double dist[MAXV];
void addEdge(int x, int y, double v)  {
    edge[e].to = y, edge[e].w = v, edge[e].eid = e;
    edge[e].next = adj[x], adj[x] = &edge[e++];
}
void dijkstra(int st, double dist[], int n) {
    typedef pair<double, int> PLL;
    for (int i = 0; i <= n; i++)
        dist[i] = INF;
    set<PLL> pQ;
    PLL u;
    pQ.insert(PLL(0, st)), dist[st] = 0;
    while (!pQ.empty()) {
        u = *pQ.begin(), pQ.erase(pQ.begin());
        for (Edge *p = adj[u.second]; p; p = p->next) {
            if (dist[p->to] > dist[u.second] + p->w) {
                if (dist[p->to] != INF)
                    pQ.erase(pQ.find(PLL(dist[p->to], p->to)));
                dist[p->to] = dist[u.second] + p->w;
                pQ.insert(PLL(dist[p->to], p->to));
            }
        }
    }
}
int I[MAXE], J[MAXE], A[MAXE], B[MAXE];
double f(int N, int M, double t) {
    e = 0;
    for (int i = 1; i <= N; i++)
        adj[i] = NULL;
    for (int i = 0; i < M; i++) {
        double cost = t * A[i] + B[i];
        addEdge(I[i], J[i], cost);
        addEdge(J[i], I[i], cost);
    }
    
    dijkstra(1, dist, N);
    return dist[N];
}
int main() {
    int N, M;
    while (scanf("%d %d", &N, &M) == 2) {
        for (int i = 0; i < M; i++)
            scanf("%d %d %d %d", &I[i], &J[i], &A[i], &B[i]);
        double l = 0, r = 24 * 60, mid, midmid, md, mmd;
        double ret = 0;
        for (int it = 0; it < 100; it++) {
            mid = (l+r)/2;
            midmid = (mid+r)/2;
            md = f(N, M, mid);
            mmd = f(N, M, midmid);
            ret = max(ret, md);
            if (fabs(md - mmd) < 1e-6)
                break;
            if (md < mmd)
                l = mid;
            else
                r = midmid;
        }
        printf("%.5lf\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13014 - Keep it energized

Problem

有 $N$ 道關卡，每一道關卡需要消耗能量 $E_i$ 才能通過，每一個關卡有能量商店，只能進行一次交易，一旦交易成功，不管先前的剩餘能量為何，直接消耗 $C_j$ 元補能量到 $S_j$，請問至少花費多少錢才能闖完所有關卡。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
5 4
1 2 3 4 5
1 6 5
2 14 10
5 5 4
3 7 5
3 4
14 11 2015
1 14 23
2 11 9
3 1987 1
1 2039 33

Sample Output

1
2
14
-1

Solution

明顯地，維護一個最小堆，每一個元素紀錄 <在哪一關買商店, 累計多少花費, 購買時有多少能量>，隨著掃描線移動，依序出隊那些無法抵達的元素，並且隊首花費就是到這一關的最少花費 $C$，再依序嘗試在新的商店購買能量，累計花費後入隊。

時間複雜度 $\mathcal{O}(N \log M)$

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
#include <time.h>
using namespace std;
const int MAXN = 131072;
int E[MAXN];
long long sumE[MAXN];
vector< pair<int, int> > shop[MAXN];
struct ELE {
    long long cost;
    int x, e;
    ELE(long long cost = 0, int x = 0, int e = 0):
    cost(cost), x(x), e(e) {}
    bool operator<(const ELE &v) const {
        if (cost != v.cost)
            return cost < v.cost;
        if (x != v.x)
            return x < v.x;
        return e < v.e;
    }
};
int main() {
    int N, M;
    while (scanf("%d %d", &N, &M) == 2) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &E[i]), shop[i].clear();
        for (int i = 0; i < M; i++) {
            int L, S, C;
            scanf("%d %d %d", &L, &S, &C);
            shop[L].push_back(make_pair(S, C));
        }
        
        for (int i = 1; i <= N; i++)
            sumE[i] = sumE[i-1] + E[i];
        
        set<ELE> S;
        for (int i = 1; i <= N; i++) {
            while (!S.empty()) {
                ELE u = *S.begin();
                if (u.e < sumE[i-1] - sumE[u.x-1])
                    S.erase(S.begin());
                else
                    break;
            }
            if (S.empty() && i != 1) {
            } else {
                long long mm = i == 1 ? 0 : S.begin()->cost;
                for (int j = 0; j < shop[i].size(); j++) {
                    pair<int, int> p = shop[i][j];
                    if (p.first >= E[i])
                        S.insert(ELE(mm + p.second, i, p.first));
                }
            }
        }
        while (!S.empty()) {
            ELE u = *S.begin();
            if (u.e < sumE[N] - sumE[u.x-1])
                S.erase(S.begin());
            else
                break;
        }
        if (S.empty())
            puts("-1");
        else
            printf("%lld\n", S.begin()->cost);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13054 - Hippo Circus

Problem

馬戲團河馬過門，單一隻河馬過門需要時間 $T_a$，兩隻河馬疊在一起且滿足總高度小於 $H$，需要花費 $T_b$ 的時間。

不管任何順序過門，請問最少時間為何？

Sample Input

1
2
3
4
5
2
3  5  2  3
3  4  2
3  6  2  3
3  4  2

Sample Output

1
2
Case 1: 6
Case 2: 5

Solution

明顯地，最矮的那隻盡量跟最高的那隻配在一起過門，反之考慮分開過門，看哪一種好就選擇哪一種。

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
#include <bits/stdc++.h>
using namespace std;
int A[131072], used[131072];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int N, H, Ta, Tb;
        scanf("%d %d %d %d", &N, &H, &Ta, &Tb);
        for (int i = 0; i < N; i++)
            scanf("%d", &A[i]);
        sort(A, A+N);
        
        long long ret = 0;
        memset(used, 0, sizeof(used));
        int r = N-1;
        for (int i = 0; i < N; i++) {
            if (used[i] == 1)	continue;
            while (r > i && (A[i] + A[r] >= H || used[r] == 1))
                r--;
            if (r > i && A[i] + A[r] < H && used[r] == 0 && Ta+Ta > Tb) {
                ret += Tb;
                used[r] = used[i] = 1;
            } else {
                ret += Ta;
                used[i] = 1;
            }
        }
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 13032 - Marbles in Jars

Problem

有 $N$ 個罐子，其中有一個罐子放置彈珠時，每一個彈珠重量會是其他罐子的 1.1 倍，也就是說其中有一個魔法罐子，在魔法罐子中的彈珠都會特別重。現在限制每一個罐子放置彈珠的數量，請問有多少放置彈珠方案，可以找到魔法罐子。

Sample Input

1
2
3
4
5
6
7
3
3
1 2 3
3
1 2 2
2
2 2

Sample Output

1
2
3
Case 1: 1
Case 2: 0
Case 3: 2

Solution

從題目描述中理解到，要找到魔法罐子最簡單的策略就是每一個罐子都擁有不同數量的彈珠，由於每一個罐子限制彈珠數量不一致，做起來就稍微複雜。

假設先依照可仿製彈珠數量多寡排序，將放置少量的彈珠優先放置在前面，依序討論放入新的罐子又與之前放置不同個數的彈珠的方法數。

定義 dp[i][j] 為前 $i$ 個罐子，其中有一罐放置最多的彈珠 $j$ 個。由於已經由小到大排序好，放入新的罐子，分成兩種情況考慮，其中一種是比 $i$ 個罐子放置更多的彈珠，不然就是放置較少的彈珠數量，數學組合一下即可。時間複雜度 $\mathcal{O}(N M^2)$

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
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int N, M[128];
        scanf("%d", &N);
        for (int i = 1; i <= N; i++)
            scanf("%d", &M[i]);
        sort(M+1, M+1+N);
        
        long long dp[128][128] = {};
        dp[0][0] = 1;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= M[i]; j++) {
                if (j - (i-1) >= 0) {
                    dp[i][j] = dp[i][j] + dp[i-1][j] * (j - (i-1));
                    dp[i][j] %= MOD;
                }
                for (int k = j+1; k <= M[i]; k++) {
                    dp[i][k] = dp[i][k] + dp[i-1][j];
                    dp[i][k] %= MOD;
                }
            }
        }
        
        long long ret = 0;
        for (int i = 0; i <= M[N]; i++)
            ret = (ret + dp[N][i])%MOD;
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
Read More +