ProjectEuler 61-100题解

发表于 | 分类于 |
字数统计: 4,193 字

继续探索

PE61

先枚举排列，然后按照排列顺序进行搜索即可。
或者按照图论，构图搜索也可以。

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
int p[6][10005], cnt[6] = {0};
int per[] = {0, 1, 2, 3, 4, 5};
int ans[6], t_ans[6];
void init(){
    int i;
    for(i = 1; (i * (i + 1) >> 1) < 1000; ++i);
    for(; (i * (i + 1) >> 1) < 10000; ++i)
        p[0][cnt[0]++] = (i * (i + 1) >> 1);
    for(i = 1; i * i < 1000; ++i);
    for(; i * i < 10000; ++i)
        p[1][cnt[1]++] = i * i;
    for(i = 1; (i * (i * 3 - 1) >> 1) < 1000; ++i);
    for(; (i * (i * 3 - 1) >> 1) < 10000; ++i)
        p[2][cnt[2]++] = (i * (i * 3 - 1) >> 1);
    for(i = 1; i * (2 * i - 1) < 1000; ++i);
    for(; i * (2 * i - 1) < 10000; ++i)
        p[3][cnt[3]++] = i * (2 * i - 1);
    for(i = 1; (i * (i * 5 - 3) >> 1) < 1000; ++i);
    for(; (i * (i * 5 - 3) >> 1) < 10000; ++i)
        p[4][cnt[4]++] = (i * (i * 5 - 3) >> 1);
    for(i = 1; i * (i * 3 - 2) < 1000; ++i);
    for(; i * (i * 3 - 2) < 10000; ++i)
        p[5][cnt[5]++] = i * (i * 3 - 2);
}
void getN(int index, int tail){
    if(index == 6){
        if(ans[5] % 100 == ans[0] / 100)
            memcpy(t_ans, ans, sizeof(ans));
        return ;
    }
    int id = per[index], hd = tail * 100;
    int _index = lower_bound(p[id], p[id] + cnt[id], hd) - p[id];
    if(p[id][_index] / 100 != tail)
        return ;
    for(int i = _index; i < cnt[id]; ++i){
        if(p[id][i] / 100 != tail)
            break ;
        ans[index] = p[id][i];
        getN(index + 1, p[id][i] % 100);
    }
}
void solve(){   
    do{
        int st = per[0];
        for(int i = 0; i < cnt[st]; ++i)
            ans[0] = p[st][i],
            getN(1, p[st][i] % 100);
    }while(next_permutation(per, per + 6));
    int sum = 0;
    for(int i = 0; i < 6; ++i)
        sum += t_ans[i];
    printf("%d\n", sum);
}

答案：28684

PE62

一个一个长度去试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
map<string, int> mp;
map<string, ll> mp2;
ll ans = INF;
void solve(){
    char s[20];
    for(ll i = 4642ll; i * i * i < 1000000000000ll; ++i){
        sprintf(s, "%lld", i * i * i);
        sort(s, s + 12);
        string ss(s);
        if(!mp.count(ss))
            mp[ss] = 1, mp2[ss] = i;
        else{
            mp[ss]++;
            if(mp[ss] == 5)
                ans = min(ans, mp2[ss]);
        } 
    }
    printf("%lld\n", ans * ans * ans);
}

答案：127035954683

PE63

拿python水过

1
2
3
4
5
6
7
8
ans = 0
for n in range(1, 22, 1):
    for i in range(1, 10, 1):
        x = i ** n
        if len(str(x)) == n:
            ans += 1

print(ans)

答案：49

PE64

这个连分数的构造方法一开始还不太容易看出来。。。
答案写在另一篇博文里了。

1
2


答案：

PE65

用python水过

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
p = 1
q = 1
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


for i in range(1, 99, 1):
    a = 0
    if (99 - i) % 3 == 2:
        a = ((98 - i) / 3 + 1) * 2
    else:
        a = 1
    pp = q
    qq = p + q * a
    p = pp
    q = qq

p = p + q + q
p /= gcd(p, q)

ans = 0
while p > 0:
    ans += p % 10
    p /= 10
print(ans)

答案：272

PE66

这个方程有名字，叫做佩尔方程。
它的解和连分数有着很大的关系，将其写在了另一篇博文里

1
2


PE67

水DP
答案：7273

PE68

PE69

筛出欧拉函数然后直接枚举。。。

1
2
3
4
5
6
7
8
9
void solve(){
    getPhi();
    int maxi;
    double d = 0;
    for(int i = 2; i <= 1000000; ++i)
        if(d < 1.0 * i / phi[i])
            d = 1.0 * i / phi[i], maxi = i;
    printf("%d\n", maxi);
}

答案：510510

PE70

枚举即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve(){
    getPhi();
    int maxi;
    double d = 10000000;
    char s1[10], s2[10];
    for(int i = 2; i < 10000000; ++i){
        sprintf(s1, "%d", i);
        sprintf(s2, "%d", phi[i]);
        int len1 = strlen(s1), len2 = strlen(s2);
        if(len1 == len2){
            sort(s1, s1 + len1);
            sort(s2, s2 + len2);
            if(!strcmp(s1, s2)){
                double dd = 1.0 * i / phi[i];
                if(dd < d)
                    d = dd, maxi = i;
            }
        }
    }
    printf("%d\n", maxi);
}

答案：8319823

PE71

对于每一个$d$二分即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve(){
    double rd = 1.0 * 3 / 7, eps = 1e6;
    int fz, fm;
    for(int d = 9; d <= 1000000; ++d){
        if(d % 7 == 0)continue;
        int l = 1, r = d - 1;
        while(r - l){
            int mid = (r + l + 1) >> 1;
            double rr = 1.0 * mid / d;
            if(rr > rd)r = mid - 1;
            else l = mid;
        }
        double rr = 1.0 * r / d;
        if(rd - rr < eps)
            eps = rd - rr, fz = r, fm = d;
    }
    printf("%d %d\n", fz, fm);
}

答案：428570

PE72

就是对1~1000000的欧拉函数求和。。。

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
bool vis[1000005] = {0};
int prime[500005], tot = 0;
int phi[1000005];
ll sum = 0;
void getPhi(){
    phi[1] = 1;
    for(int i = 2; i <= 1000000; ++i){
        if(!vis[i])
            phi[i] = i - 1, prime[++tot] = i;
        for(int j = 1; j <= tot; ++j){
            if(1ll * prime[j] * i > 1000000)
                break;
            vis[prime[j] * i] = 1;
            if(i % prime[j] == 0){
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }else
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
        sum += 1ll * phi[i];
    }
}
void solve(){
    getPhi();
    printf("%lld\n", sum);
}

答案：303963552391

PE73

注意分数为不可约。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int ans = 0;
int gcd(int a, int b){
    return (!b) ? a : gcd(b, a % b);
}
void solve(){
    double l = 1.0 / 3, r = 1.0 / 2;
    for(int i = 4; i <= 12000; ++i){
        for(int j = 1; j < i; ++j){
            if(gcd(i, j) > 1)
                continue;
            double cur = 1.0 * j / i;
            if(abs(cur - l) < 1e-7 || abs(cur - r) < 1e-7)
                continue ;
            if(cur > l && cur < r)
                ans++;
        }
    }
    printf("%d\n", ans);
}

答案：7295372

PE74

虽然这道题我给出了一个正确的答案但我还是觉得我写错了。。。
怎么回事？
做法就是顺着一个数DFS下去，然后记录步数。

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
int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int d[10000005], ans = 0, st[10000005] = {0};
bool vis[10000005] = {0};
void getD(){
    for(int i = 0; i < 10; ++i)
        d[i] = fac[i];
    for(int i = 10; i <= 10000000; ++i)
        d[i] = d[i / 10] + fac[i % 10];
}
void dfs(int x){
    vis[x] = 1;
    int nx = d[x];
    if(!vis[nx])
        dfs(nx);
    else{
        if(!st[nx]){
            st[x] = 1;
            return ;
        }
    }
    st[x] = st[nx] + 1;
}
void solve(){
    getD();
    vis[1] = vis[2] = true;
    st[1] = st[2] = 1;
    for(int i = 3; i < 1000000; ++i)
        if(!vis[i])
            dfs(i);
    for(int i = 3; i < 1000000; ++i)
        if(st[i] == 60)
            ans++;
    printf("%d\n", ans);
}

答案：402

PE75

一开始我写了一个暴力枚举，然后很干脆的挂掉了。。。
后来我想到可以枚举所有的素毕达哥拉斯三元数， 然后用类似筛法的方法让其倍数的方法数$+1$， 最后统计方法数仅为$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
int ans = 0;
int cnt[1500005] = {0};
int gcd(int a, int b){
    return (!b) ? a : gcd(b, a % b);
}
void pre(){
    for(int v = 2; v <= 1000; ++v)
        for(int u = 1; u < v; ++u){
            if((u & 1) && (v & 1))continue;
            if(gcd(u, v) != 1)continue;
            int dis = 2 * v * v + 2 * u * v;
            if(dis > 1500000)
                break;
            for(int i = dis; i <= 1500000; i += dis)
                cnt[i]++;
        }
}
void solve(){
    pre();
    for(int i = 12; i <= 1500000; i += 2)
        if(cnt[i] == 1)
            ans++;
    printf("%d\n", ans);
}

答案：161667

PE76

划分问题。
令$p(n, m)$表示$n$划分为若干个小于等于$m$的数的方法数。那么有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll p[105][105] = {0};
void solve(){
    for(int i = 1; i <= 100; ++i)
        p[1][i] = 1ll;
    for(int i = 2; i <= 100; ++i){
        p[i][1] = 1ll;
        for(int j = 2; j < i; ++j)
            p[i][j] = p[i][j - 1] + p[i - j][j];
        p[i][i] = p[i][i - 1] + 1;
        for(int j = i + 1; j <= 100; ++j)
            p[i][j] = p[i][j - 1];
    }
    printf("%lld\n", p[100][99]);
}

答案：190569291

PE77

对pe76进行一定程度的加工即可。

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
ll p[10005][10005] = {0};
bool vis[10005] = {0};
int prime[5005], tot = 0;
void init(){
    for(int i = 2; i <= 10000; ++i)
        if(!vis[i]){
            for(int j = i << 1; j <= 10000; j += i)
                vis[j] = 1;
            prime[tot++] = i;
        }
}
void solve(){
    int ans;
    for(int i = 0; i < tot; ++i)
        p[0][prime[i]] = 1ll;
    for(int i = 2; i <= 10000; ++i){
        int id = upper_bound(prime, prime + tot, i) - prime - 1;
        //int pp = prime[id];
        if(i & 1) p[i][2] = 0;
        else p[i][2] = 1;
        for(int j = 1; j <= id; ++j)
            p[i][prime[j]] = p[i][prime[j - 1]] + p[i - prime[j]][prime[j]];
        for(int j = id + 1; j < tot; ++j)
            p[i][prime[j]] = p[i][prime[j - 1]];
        if(p[i][prime[id]] > 5000){
            ans = i;
            break;
        }
    }
    printf("%d\n", ans);
}

答案：71（蜜汁小）

PE78

一开始拿pe76写了很久，结果什么都没有。。。
后来发现了一个很神奇的东西。

1
2


PE79

…手算…?
对所有询问排个序，去个重，就差不多可以发现一些问题了。
答案：73162890

PE80

考虑到精度问题，我们考虑对一个大整数开根号。
比如计算$\sqrt 2$的前一百位，可以改为计算$10^{100}\times \sqrt 2$的前一百位。
即先把根号的值放大，然后二分出具体的值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
x = 10 ** 300
ans = 0
for i in range(2, 100, 1):
    y = math.floor(math.sqrt(i) + 0.5)
    if y * y != i:
        z = i * x
        l = 1
        r = z
        while r - l > 0:
            mid = (r + l) >> 1
            if mid * mid < z:
                l = mid + 1
            else:
                r = mid
        s = str(l)
        for j in range(0, 100, 1):
            ans += eval(s[j: j + 1])

print(ans)

答案：40886

PE81

水DP
答案：427337

PE82

根据矩阵和走路的方式建图，跑最短路即可。

1
2


答案：

PE83

同上。

PE84

我不会这样的神奇概率题。。。
我就模拟这个游戏足够多次，然后根据访问次数判断哪三个地方访问概率最大。

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
int vis[49] = {0}, cur = 0;
int curc = 0, curh = 0;
int cc[20] = {0}, ch[20] = {0};
pair<int, int> pp[45];
pair<int, int> getS(){
    int i = 1 + rand() % 4, j = 1 + rand() % 4;
    return make_pair(i, j);
}
int getR(int x){
    if(x == 7)return 15;
    if(x == 22)return 25;
    if(x == 36)return 5;
}
int getU(int x){
    if(x == 7)return 12;
    if(x == 22)return 28;
    if(x == 36)return 12;
}
void init(){
    srand(time(NULL));
    cc[rand() % 16] = 1;
    int i = rand() % 16;
    while(cc[i])
        i = rand() % 16;
    cc[i] = 2;
    for(int j = 1; j <= 10; ++j){
        i = rand() % 16;
        while(ch[i])
            i = rand() % 16;
        ch[i] = j;
    }
}
void solve(){
    int lst = 0;
    for(int i = 1; i <= 100000000; ++i){
        pair<int, int> p = getS();
        int d = p.first + p.second;
        if(p.first == p.second)
            lst++;
        else lst = 0;

        if(lst == 3){
            cur = 10, lst = 0;
        }else{
            int to = (cur + d) % 40;
            if(to == 2 || to == 17 || to == 33){
                int id = cc[curc];
                curc = (curc + 1) % 16;
                if(id == 1){
                    cur = 0;
                }else if(id == 2){
                    cur = 10;
                }else{
                    cur = to;
                }
            }else if(to == 7 || to == 22 || to == 36){
                int id = ch[curh];
                curh = (curh + 1) % 16;
                if(id == 1){
                    cur = 0;
                }else if(id == 2){
                    cur = 10;
                }else if(id == 3){
                    cur = 11;
                }else if(id == 4){
                    cur = 24;
                }else if(id == 5){
                    cur = 39;
                }else if(id == 6){
                    cur = 5;
                }else if(id == 7 || id == 8){
                    cur = getR(to);
                }else if(id == 9){
                    cur = getU(to);
                }else if(id == 10){
                    cur = to - 3;
                }else{
                    cur = to;
                }
            }else if(to == 30){
                cur = 10;
            }else{
                cur = to;
            }
        }

        vis[cur]++;
    }

    for(int i = 0; i < 40; ++i)
        pp[i] = make_pair(vis[i], i);
    sort(pp, pp + 40);
    for(int i = 39; i > 36; --i)
        printf("%d", pp[i].second);
}

答案：101524

PE85

小学奥数题。
边长为$n,m$的矩形内部有个小矩形。

1
2
3
4
5
6
7
8
9
10
11
12
ll ans = INF, maxi;
void solve(){
    for(int i = 1; i <= 2000; ++i){
        for(int j = 1; j <= 2000; ++j){
            ll pp = 1ll * i * j * (i + 1) * (j + 1);
            pp >>= 2;
            if(abs(pp - 2000000) < ans)
                ans = abs(pp - 2000000), maxi = 1ll * i * j;
        }
    }
    printf("%lld\n", maxi);
}

答案：2772

PE87

直接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
bool vis[10005] = {0};
int prime[4][10005], tot[4] = {0};
bool dd[50000005] = {0};
void getP(){
    for(int i = 2; i <= 8000; ++i)
        if(!vis[i]){
            for(int j = i + i; j <= 8000; j += i)
                vis[j] = 1;
            prime[0][++tot[0]] = i;
        }
}
void solve(){
    getP();
    for(int i = 1; i < 4; ++i){
        for(int j = 1; j <= tot[i - 1]; ++j){
            if(1ll * prime[0][j] * prime[i - 1][j] >= 50000000ll){
                tot[i] = j - 1;
                break;
            }
            prime[i][j] = prime[0][j] * prime[i - 1][j];
        }
    }
    for(int k = 1; k <= tot[1]; ++k)
        for(int i = 1; i <= tot[2]; ++i)
            for(int j = 1; j <= tot[3]; ++j)
                if(prime[1][k] + prime[2][i] + prime[3][j] < 50000000)
                    dd[prime[1][k] + prime[2][i] + prime[3][j]] = 1;
    int ans = 0;
    for(int i = 1; i < 50000000; ++i)
        ans += dd[i];
    printf("%d\n", ans);
}

答案：1097343

PE90

生成组合，然后测试即可。

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
int cb[2][10], ans = 0;
void judge(){
    int l[2];
    l[0] = l[1] = 0;
    for(int o = 0; o < 2; ++o){
        int flag = 0;
        for(int i = 0; i < 6; ++i){
            l[o] |= (1 << cb[o][i]);
            if(cb[o][i] == 6 || cb[o][i] == 9)
                flag += cb[o][i];
        }
        if(flag == 6)
            l[o] |= (1 << 9);
        if(flag == 9)
            l[o] |= (1 << 6);
    }
    int flag = 1;
    for(int i = 1; i < 10; ++i){
        int g = (i * i) % 10, s = (i * i) / 10;
        g = 1 << g, s = 1 << s;
        if(((s & l[0]) && (g & l[1])) || (s & l[1]) && (g & l[0])){
            continue;
        }else{
            flag = 0;
            break;
        }
    }
    ans += flag;
}
void getC(int o, int index, int left){
    cb[o][5 - left] = index;
    if(!left){
        if(!o)
            for(int i = 0; i <= 4; ++i)
                getC(1, i, 5);
        else{
            judge();      
        }
        return ;
    }
    for(int i = index + 1; i <= 10 - left; ++i)
        getC(o, i, left - 1);
}
void solve(){
    for(int i = 0; i <= 4; ++i)
        getC(0, i, 5);
    printf("%d\n", ans >> 1);
}

答案：1217

PE91

四重循环。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int ans = 0;
void solve(){
    for(int i = 0; i <= 50; ++i)
        for(int j = 0; j <= 50; ++j)
            for(int k = 0; k <= 50; ++k)
                for(int l = 0; l <= 50; ++l){
                    if(!i && !j)continue;
                    if(!k && !l)continue;
                    if(i == k && j == l)continue;
                    int a = i * i + j * j, b = k * k + l * l,
                    c = (i - k) *(i - k) + (j - l) * (j - l);
                    if(a + b == c || a + c == b || b + c == a)
                        ans++;
                }
    printf("%d\n", ans >> 1);
}

答案：14234

PE92

直接模拟即可。。
89的比例还是挺高的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int ans = 0;
int sqr(int x){
    return x * x;
}
void solve(){
    for(int i = 2; i < 10000000; ++i){
        int j = i;
        for(; j != 1 && j != 89; ){
            int sum = 0;
            while(j)
                sum += sqr(j % 10), j /= 10;
            j = sum;
        }
        if(j == 89)ans++;
    }
    printf("%d\n", ans);
}

答案：8581146

PE94

做一些数学上的分析
根据海伦公式有：
$S=\sqrt{p(p-a)(p-b)(p-c)}$
其中$a,b,c$均为边长
在这道题中上式可以化为
$S=(p-i)\sqrt{p(p-i-1)}$
或$S=(p-i)\sqrt{p(p-i+1)}$
然后由于面积要求为正整数，所以需要$p(p-i+1)$为完全平方数
按照这个枚举即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool sqr(ll x){
    ll r = (ll)floor(sqrt(x) + 0.5);
    return r * r == x;
}
void solve(){
    int ans = 0;
    for(int i = 3; i <= 333333333; i += 2){
        ll p = (3 * i - 1) >> 1;
        p *= (i + 1) >> 1;
        if(sqr(p))
            ans += 3 * i - 1;
        p = (3 * i + 1) >> 1;
        p *= (i - 1) >> 1;
        if(sqr(p))
            ans += 3 * i + 1;
    }
    printf("%d\n", ans);
}

答案：518408346

PE95

对每一个数DFS一遍即可。

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
int d[1000005] = {0};
int ans = 0, mini;
int vis[1000005] = {0}, tot = 0;
void getD(){
    for(int i = 2; i <= 1000000; ++i){
        int j;
        for(j = 1; j * j < i; ++j)
            if(i % j == 0)
                d[i] += j + i / j;
        if(j * j == i)d[i] += j;
        d[i] -= i;
    }
}
void dfs(int x, int st){
    vis[x] = tot;
    if(d[x] > 1000000 || !d[x])
        return ;
    if(vis[d[x]] == tot){
        if(st > ans)
            ans = st, mini = d[x];
        return ;
    }else if(!vis[d[x]]){
        dfs(d[x], st + 1);
    }
}
void solve(){
    getD();
    for(int i = 2; i <= 1000000; ++i)
        if(!vis[i])
            tot++, dfs(i, 1);
    printf("%d %d\n", mini, ans);
}

答案：14316

PE96

把现成的数独模板丢上去即可。

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
#include <bits/stdc++.h>
using namespace std;
int vis[3][11][11]={0},sd[10][10]={0};
int lis[81][2],tot=0;
int tans[10][10]={0};
void get(int at){
    int mini=99,p,x,y,o;
    for(int i=at+1;i<tot;i++){
        x=lis[i][0],y=lis[i][1],o=0;
        for(int j=1;j<=9;j++){
            if(vis[0][x][j]||vis[1][y][j]||vis[2][(x/3)*3+y/3][j])continue;
            else o++;
        }
        if(o<mini)mini=o,p=i;
    }
    x=lis[at+1][0],y=lis[at+1][1];
    lis[at+1][0]=lis[p][0],lis[at+1][1]=lis[p][1];
    lis[p][0]=x,lis[p][1]=y;
}
void dfs(int at){
    int x=lis[at][0],y=lis[at][1];
    for(int i=1;i<=9;i++){
        if(vis[0][x][i]||vis[1][y][i]||vis[2][(x/3)*3+y/3][i])continue;
        vis[0][x][i]=vis[1][y][i]=vis[2][(x/3)*3+y/3][i]=1,sd[x][y]=i;
        if(at<tot-1){
            if(at!=tot-2)get(at);
            dfs(at+1);
        }else {
            memcpy(tans, sd, sizeof(sd));
        }
        vis[0][x][i]=vis[1][y][i]=vis[2][(x/3)*3+y/3][i]=0,sd[x][y]=0;
    }
}
//0 行 1 列 2 宫 
int main(){
    int ans = 0;
    char s1[10], s2[10];
    for(int i = 0; i < 50; ++i){
        int tmp;
        tot = 0;
        memset(sd, 0, sizeof(sd));
        memset(lis, 0, sizeof(lis));
        memset(vis, 0, sizeof(vis));
        scanf("%s%s", s1, s2);
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++){
                scanf("%1d",&tmp);
                if(tmp){
                    sd[i][j]=tmp;
                    vis[0][i][tmp]=vis[1][j][tmp]=vis[2][(i/3)*3+j/3][tmp]=1;
                }else lis[tot][0]=i,lis[tot++][1]=j;
            }
        dfs(0);
        ans += tans[0][0] * 100 + tans[0][1] * 10 + tans[0][2];
    }
    printf("%d\n", ans);
    return 0;  
}

答案：24702

PE97

python，这个我还能说什么。。。
答案：8739992577

PE99

化成对数比即可。

1
2
3
4
5
6
7
8
9
10
11
double maxm = 0;
int ans;
void solve(){
    for(int i = 1; i <= 1000; ++i){
        int b = read(), e = read();
        double tt = 1.0 * e * log(b);
        if(tt > maxm)
            maxm = tt, ans = i;
    }
    printf("%d\n", ans);
}

答案：709