小歪和大富翁2.0

[题目链接](https://www.nowcoder.com/practice/7ae0075e6cfe422582710924c587e470)

思路

个城市围成一圈（编号 到 ），每个城市有一个金币值（仅首次到达时获取）。每轮使用 4 张卡牌（跳 1/2/3/4 步），经过 轮后求最多获得的金币数。 保证是 的倍数。

关键观察一：分块独立

每轮使用全部 4 张卡牌，总步数为 。由于 是 的倍数，可以将城市分成 个块：

  • 第 轮从位置 出发，访问偏移量 范围内的城市（即城市 ）
  • 第 轮从位置 出发，访问城市
  • 第 轮从位置 出发，访问城市 （模 ）

每 轮一个周期，同一个块内的城市只被同一组轮次处理，不同块之间完全独立。

关键观察二：排列决定访问模式

每轮选择 4 张卡牌的使用顺序（ 的一个排列），产生 4 个访问位置（前缀和）。例如排列 的前缀和为 ，表示访问偏移 。

枚举所有 种排列，恰好产生 24 种不同的偏移集合。注意偏移 出现在每一种排列中（因为 ），所以偏移 对应的城市在有轮次时一定被访问。

关键观察三：多轮的可达集合

对于一个块，分配 轮后，最终访问的城市是各轮访问集合的并集（重复访问不再获得金币）。预计算 轮所有可达的偏移并集：

轮数 可达集合数
1 24
2 193
3 265
4 266
266（不再增长）

比 仅多一个可达集合 。因此 只需取 。

算法流程

  1. 将偏移 单独处理（必定访问）。对偏移 用位掩码编码所有可达集合。
  2. 对每个块 ，计算分配的轮数 （若 则为 ）。
  3. 枚举该轮数对应的所有可达掩码，选使得所选偏移位置的金币总和最大的掩码。
  4. 将偏移 的金币加上最优掩码的金币，累加到答案。

复杂度

  • 时间复杂度：
  • 空间复杂度：

代码

#include <bits/stdc++.h>
using namespace std;

int masks1[] = {74, 76, 82, 88, 100, 104, 138, 140, 162, 176, 196, 208, 274, 280, 290, 304, 392, 400, 548, 552, 580, 592, 648, 656};
int masks2[] = {74, 76, 78, 82, 88, 90, 92, 94, 100, 104, 106, 108, 110, 118, 120, 122, 124, 138, 140, 142, 162, 170, 174, 176, 178, 186, 188, 196, 202, 204, 206, 208, 210, 212, 214, 216, 218, 220, 222, 228, 230, 234, 236, 238, 240, 242, 244, 248, 250, 252, 274, 280, 282, 290, 304, 306, 312, 314, 338, 344, 346, 348, 350, 358, 362, 366, 370, 372, 374, 376, 378, 380, 392, 394, 396, 400, 402, 408, 410, 412, 414, 418, 426, 430, 432, 434, 440, 442, 444, 458, 460, 464, 466, 468, 470, 472, 474, 476, 486, 488, 492, 496, 498, 500, 504, 548, 552, 556, 580, 588, 590, 592, 594, 596, 598, 600, 602, 604, 612, 616, 618, 620, 622, 628, 630, 632, 634, 636, 648, 650, 652, 656, 664, 666, 668, 678, 680, 682, 684, 686, 688, 690, 692, 696, 708, 714, 716, 718, 720, 722, 724, 728, 730, 732, 740, 742, 744, 748, 752, 754, 756, 760, 806, 810, 820, 822, 824, 826, 828, 850, 854, 856, 860, 870, 880, 882, 884, 904, 912, 914, 920, 922, 936, 938, 940, 944, 946, 948, 952, 972, 976, 980, 984};
int masks3[] = {74, 76, 78, 82, 88, 90, 92, 94, 100, 104, 106, 108, 110, 118, 120, 122, 124, 126, 138, 140, 142, 162, 170, 174, 176, 178, 186, 188, 190, 196, 202, 204, 206, 208, 210, 212, 214, 216, 218, 220, 222, 228, 230, 234, 236, 238, 240, 242, 244, 246, 248, 250, 252, 254, 274, 280, 282, 290, 304, 306, 312, 314, 338, 344, 346, 348, 350, 358, 362, 366, 370, 372, 374, 376, 378, 380, 382, 392, 394, 396, 398, 400, 402, 408, 410, 412, 414, 418, 426, 430, 432, 434, 440, 442, 444, 446, 458, 460, 462, 464, 466, 468, 470, 472, 474, 476, 478, 486, 488, 490, 492, 494, 496, 498, 500, 502, 504, 506, 508, 510, 548, 552, 556, 580, 588, 590, 592, 594, 596, 598, 600, 602, 604, 606, 612, 616, 618, 620, 622, 628, 630, 632, 634, 636, 638, 648, 650, 652, 654, 656, 664, 666, 668, 670, 678, 680, 682, 684, 686, 688, 690, 692, 694, 696, 698, 700, 702, 708, 714, 716, 718, 720, 722, 724, 726, 728, 730, 732, 734, 740, 742, 744, 746, 748, 750, 752, 754, 756, 758, 760, 762, 764, 766, 806, 810, 814, 820, 822, 824, 826, 828, 830, 850, 854, 856, 858, 860, 862, 870, 874, 878, 880, 882, 884, 886, 888, 890, 892, 894, 904, 906, 908, 912, 914, 920, 922, 924, 926, 934, 936, 938, 940, 942, 944, 946, 948, 950, 952, 954, 956, 958, 970, 972, 974, 976, 978, 980, 982, 984, 986, 988, 990, 998, 1000, 1002, 1004, 1006, 1008, 1010, 1012, 1014, 1016, 1018, 1020, 1022};
int masks4[] = {74, 76, 78, 82, 88, 90, 92, 94, 100, 104, 106, 108, 110, 118, 120, 122, 124, 126, 138, 140, 142, 162, 170, 174, 176, 178, 186, 188, 190, 196, 202, 204, 206, 208, 210, 212, 214, 216, 218, 220, 222, 228, 230, 234, 236, 238, 240, 242, 244, 246, 248, 250, 252, 254, 274, 280, 282, 290, 304, 306, 312, 314, 338, 344, 346, 348, 350, 358, 362, 366, 370, 372, 374, 376, 378, 380, 382, 392, 394, 396, 398, 400, 402, 408, 410, 412, 414, 418, 426, 430, 432, 434, 440, 442, 444, 446, 458, 460, 462, 464, 466, 468, 470, 472, 474, 476, 478, 486, 488, 490, 492, 494, 496, 498, 500, 502, 504, 506, 508, 510, 548, 552, 556, 580, 588, 590, 592, 594, 596, 598, 600, 602, 604, 606, 612, 616, 618, 620, 622, 628, 630, 632, 634, 636, 638, 648, 650, 652, 654, 656, 664, 666, 668, 670, 678, 680, 682, 684, 686, 688, 690, 692, 694, 696, 698, 700, 702, 708, 714, 716, 718, 720, 722, 724, 726, 728, 730, 732, 734, 740, 742, 744, 746, 748, 750, 752, 754, 756, 758, 760, 762, 764, 766, 806, 810, 814, 820, 822, 824, 826, 828, 830, 850, 854, 856, 858, 860, 862, 870, 874, 878, 880, 882, 884, 886, 888, 890, 892, 894, 904, 906, 908, 910, 912, 914, 920, 922, 924, 926, 934, 936, 938, 940, 942, 944, 946, 948, 950, 952, 954, 956, 958, 970, 972, 974, 976, 978, 980, 982, 984, 986, 988, 990, 998, 1000, 1002, 1004, 1006, 1008, 1010, 1012, 1014, 1016, 1018, 1020, 1022};

int *all_masks[] = {nullptr, masks1, masks2, masks3, masks4};
int all_lens[] = {0, 24, 193, 265, 266};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<long long> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    int C = n / 10;
    long long ans = 0;

    for(int b = 0; b < C; b++){
        int rounds;
        if(b >= k) rounds = 0;
        else rounds = min(4, (k - 1 - b) / C + 1);

        if(rounds == 0) continue;

        long long v10 = a[(10LL * b + 10) % n];
        long long v[10];
        v[0] = 0;
        for(int i = 1; i <= 9; i++){
            v[i] = a[(10LL * b + i) % n];
        }

        int *masks = all_masks[rounds];
        int nm = all_lens[rounds];

        long long best = LLONG_MIN;
        for(int t = 0; t < nm; t++){
            int mask = masks[t];
            long long sum = 0;
            for(int i = 1; i <= 9; i++){
                if(mask & (1 << i)) sum += v[i];
            }
            best = max(best, sum);
        }

        ans += v10 + best;
    }

    cout << ans << endl;
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static int[] masks1 = {74, 76, 82, 88, 100, 104, 138, 140, 162, 176, 196, 208, 274, 280, 290, 304, 392, 400, 548, 552, 580, 592, 648, 656};
    static int[] masks2 = {74, 76, 78, 82, 88, 90, 92, 94, 100, 104, 106, 108, 110, 118, 120, 122, 124, 138, 140, 142, 162, 170, 174, 176, 178, 186, 188, 196, 202, 204, 206, 208, 210, 212, 214, 216, 218, 220, 222, 228, 230, 234, 236, 238, 240, 242, 244, 248, 250, 252, 274, 280, 282, 290, 304, 306, 312, 314, 338, 344, 346, 348, 350, 358, 362, 366, 370, 372, 374, 376, 378, 380, 392, 394, 396, 400, 402, 408, 410, 412, 414, 418, 426, 430, 432, 434, 440, 442, 444, 458, 460, 464, 466, 468, 470, 472, 474, 476, 486, 488, 492, 496, 498, 500, 504, 548, 552, 556, 580, 588, 590, 592, 594, 596, 598, 600, 602, 604, 612, 616, 618, 620, 622, 628, 630, 632, 634, 636, 648, 650, 652, 656, 664, 666, 668, 678, 680, 682, 684, 686, 688, 690, 692, 696, 708, 714, 716, 718, 720, 722, 724, 728, 730, 732, 740, 742, 744, 748, 752, 754, 756, 760, 806, 810, 820, 822, 824, 826, 828, 850, 854, 856, 860, 870, 880, 882, 884, 904, 912, 914, 920, 922, 936, 938, 940, 944, 946, 948, 952, 972, 976, 980, 984};
    static int[] masks3 = {74, 76, 78, 82, 88, 90, 92, 94, 100, 104, 106, 108, 110, 118, 120, 122, 124, 126, 138, 140, 142, 162, 170, 174, 176, 178, 186, 188, 190, 196, 202, 204, 206, 208, 210, 212, 214, 216, 218, 220, 222, 228, 230, 234, 236, 238, 240, 242, 244, 246, 248, 250, 252, 254, 274, 280, 282, 290, 304, 306, 312, 314, 338, 344, 346, 348, 350, 358, 362, 366, 370, 372, 374, 376, 378, 380, 382, 392, 394, 396, 398, 400, 402, 408, 410, 412, 414, 418, 426, 430, 432, 434, 440, 442, 444, 446, 458, 460, 462, 464, 466, 468, 470, 472, 474, 476, 478, 486, 488, 490, 492, 494, 496, 498, 500, 502, 504, 506, 508, 510, 548, 552, 556, 580, 588, 590, 592, 594, 596, 598, 600, 602, 604, 606, 612, 616, 618, 620, 622, 628, 630, 632, 634, 636, 638, 648, 650, 652, 654, 656, 664, 666, 668, 670, 678, 680, 682, 684, 686, 688, 690, 692, 694, 696, 698, 700, 702, 708, 714, 716, 718, 720, 722, 724, 726, 728, 730, 732, 734, 740, 742, 744, 746, 748, 750, 752, 754, 756, 758, 760, 762, 764, 766, 806, 810, 814, 820, 822, 824, 826, 828, 830, 850, 854, 856, 858, 860, 862, 870, 874, 878, 880, 882, 884, 886, 888, 890, 892, 894, 904, 906, 908, 912, 914, 920, 922, 924, 926, 934, 936, 938, 940, 942, 944, 946, 948, 950, 952, 954, 956, 958, 970, 972, 974, 976, 978, 980, 982, 984, 986, 988, 990, 998, 1000, 1002, 1004, 1006, 1008, 1010, 1012, 1014, 1016, 1018, 1020, 1022};
    static int[] masks4 = {74, 76, 78, 82, 88, 90, 92, 94, 100, 104, 106, 108, 110, 118, 120, 122, 124, 126, 138, 140, 142, 162, 170, 174, 176, 178, 186, 188, 190, 196, 202, 204, 206, 208, 210, 212, 214, 216, 218, 220, 222, 228, 230, 234, 236, 238, 240, 242, 244, 246, 248, 250, 252, 254, 274, 280, 282, 290, 304, 306, 312, 314, 338, 344, 346, 348, 350, 358, 362, 366, 370, 372, 374, 376, 378, 380, 382, 392, 394, 396, 398, 400, 402, 408, 410, 412, 414, 418, 426, 430, 432, 434, 440, 442, 444, 446, 458, 460, 462, 464, 466, 468, 470, 472, 474, 476, 478, 486, 488, 490, 492, 494, 496, 498, 500, 502, 504, 506, 508, 510, 548, 552, 556, 580, 588, 590, 592, 594, 596, 598, 600, 602, 604, 606, 612, 616, 618, 620, 622, 628, 630, 632, 634, 636, 638, 648, 650, 652, 654, 656, 664, 666, 668, 670, 678, 680, 682, 684, 686, 688, 690, 692, 694, 696, 698, 700, 702, 708, 714, 716, 718, 720, 722, 724, 726, 728, 730, 732, 734, 740, 742, 744, 746, 748, 750, 752, 754, 756, 758, 760, 762, 764, 766, 806, 810, 814, 820, 822, 824, 826, 828, 830, 850, 854, 856, 858, 860, 862, 870, 874, 878, 880, 882, 884, 886, 888, 890, 892, 894, 904, 906, 908, 910, 912, 914, 920, 922, 924, 926, 934, 936, 938, 940, 942, 944, 946, 948, 950, 952, 954, 956, 958, 970, 972, 974, 976, 978, 980, 982, 984, 986, 988, 990, 998, 1000, 1002, 1004, 1006, 1008, 1010, 1012, 1014, 1016, 1018, 1020, 1022};

    static int[][] allMasks = {null, masks1, masks2, masks3, masks4};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        long[] a = new long[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken());

        int C = n / 10;
        long ans = 0;

        for (int b = 0; b < C; b++) {
            int rounds;
            if (b >= k) rounds = 0;
            else rounds = Math.min(4, (k - 1 - b) / C + 1);

            if (rounds == 0) continue;

            long v10 = a[(int)((10L * b + 10) % n)];
            long[] v = new long[10];
            for (int i = 1; i <= 9; i++) {
                v[i] = a[(int)((10L * b + i) % n)];
            }

            int[] masks = allMasks[rounds];
            long best = Long.MIN_VALUE;
            for (int mask : masks) {
                long sum = 0;
                for (int i = 1; i <= 9; i++) {
                    if ((mask & (1 << i)) != 0) sum += v[i];
                }
                best = Math.max(best, sum);
            }

            ans += v10 + best;
        }

        System.out.println(ans);
    }
}