玖的数学&算法录
0%

2025牛客寒假算法训练营1

发表于 更新于
本文字数： 13k 阅读时长 ≈ 12 分钟

A. 茕茕孑立之影

题意：

给你一个数组a，希望给出一个不大于10^18的正整数x，满足x与数组a任意一个元素都互不为倍数关系。

数据范围

$$1\leq T\leq 10^4$$

$$1 \leq n \leq 10^5$$

$$1 \leq a_i \leq 10^9$$

题解：数学

特判1，输出任意一个>1e9的质数

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
void JiuCherish() {
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    int mx = MOD;
    for(int i=1;i<=n;i++) {
        if(a[i] == 1) {
            std::cout << -1 << endl;
            return;
        }
    }
    std::cout << mx << endl;
}

B.一气贯通之刃

题意：

有一棵树，求一条路径使得所有的节点都被经过，如果存在这么一条路径，输出起点和终点，否则输出-1。

数据范围

$$2\leq n\leq 10^5$$

$$1 \leq u_i,v_i \leq n,u_i \neq v_i$$

题解：模拟

判断这个树是不是一条链即可，如果是输出最远的两个节点。

判断是不是链可以通过度数来判定：有两个点的度数为1，其他点度数为2.输出两个度数为1的节点即可。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void JiuCherish() {
    int n;
    std::cin >> n;
    for(int i=1;i<n;i++) {
        int u,v;
        std::cin >> u >> v;
        d[u] += 1;
        d[v] += 1;
    }
    int fr = 0,sc = 0;
    for(int i=1;i<=n;i++) {
        if(d[i] > 2) {
            std::cout << -1 << endl;
            return;
        }
        if(d[i] == 1) {
            if(!fr) fr = i;
            else if(!sc) sc = i;
        }
    }
    std::cout << fr << ' ' << sc << endl;
}

C.兢兢业业之移

题意：

好矩阵的定义需要满足以下两个条件：

1.矩阵的行数和列数都是偶数。

2.将左上角的区域全部变为1，右上右下左下的区域变成0。

现在给你一个n行n列的01矩阵，你每次操作只能交换两个相邻字符，请你将矩阵变成好矩阵，保证给出的矩阵一定有解，需要给出的操作次数不超过n³/2，可以证明，在该范围内至少存在一种合法解。

输出操作次数，以及每一次的交换方案。

数据范围

$$1\leq T\leq 20$$

$$2 \leq n \leq 100$$

$$保证1的数量恰好为\frac{n^2}{4}$$

题解：模拟

确定左上方有没有1，找最近的1让他移动过去。

代码：（学习konbi的）
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
void JiuCherish() {
    int n;
    std::cin >> n;
    std::vector<std::vector<int>> f(n + 5,std::vector<int>(n + 5));
    for(int i=1;i<=n;i++) {
        std::string s;
        std::cin >> s;
        for(int j=1;j<=n;j++) {
            f[i][j] = s[j - 1] - '0';
        }
    }
    int m = n / 2;
    for(int i=1;i<=101;i++) {
        for(int j=1;j<=101;j++) {
            st[i][j] = false;
        }
    }
    std::vector<std::array<int,4>> ans;
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=m;j++) {
            st[i][j] = true;
            if(f[i][j]) continue;

            int ok = 0;
            for(int x=1;!ok and x<=n;x++) {
                for(int y=1;!ok and y<=n;y++) {
                    if(!f[x][y] or st[x][y]) continue;
                    ok = 1;
                    while(y < j) {
                        std::swap(f[x][y],f[x][y + 1]);
                        ans.pb({x,y,x,y + 1});
                        y += 1;
                    }
                    while(x < i) {
                        std::swap(f[x][y],f[x + 1][y]);
                        ans.pb({x,y,x + 1,y});
                        x += 1;
                    }
                    while(y > j) {
                        std::swap(f[x][y],f[x][y - 1]);
                        ans.pb({x,y,x,y - 1});
                        y -= 1;
                    }
                    while(x > i) {
                        std::swap(f[x][y],f[x - 1][y]);
                        ans.pb({x,y,x - 1,y});
                        x -= 1;
                    }
                }
            }
        }
    }
    std::cout << ans.size() << endl;
    for(auto [a,b,c,d] : ans) {
        std::cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
    }
}

D.双生双宿之决

题意：

我们定义双生数组：数组大小为偶数，且只有2种数组元素，并且这两种元素的出现次数相同。

现在给你一个数组，判断他是不是双生数组。

数据范围

$$1\leq T \leq 10^4$$

$$1 \leq n \leq 10^5$$

$$1 \leq a_i \leq 10^{9}$$

题解：模拟，stl

题意。

代码：
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
void JiuCherish() {
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];

    if(n % 2 != 0) {
        std::cout << "No" << endl;
        return;
    }
    std::map<int,int> mp;
    for(int i=1;i<=n;i++) mp[a[i]] += 1;
    if(mp.size() != 2) {
        std::cout << "No" << endl;
        return;
    } else {
        auto it = mp.begin();
        int fc = it->se;
        ++it;
        int sc = it->se;
        if(fc == sc) {
            std::cout << "Yes" << endl;
        } else {
            std::cout << "No" << endl;
        }
    }

}

E.双生双宿之错

题意：

我们定义双生数组：数组大小为偶数，且只有2种数组元素，并且这两种元素的出现次数相同。

现在给你一个长度为偶数的数组，你可以进行若干次操作，每次操作选择一个元素，使其加1或者减1，小红希望这个数组变成双生数组的最小操作次数。

数据范围

$$1\leq T \leq 10^4$$

$$2 \leq n \leq 10^5$$

$$1 \leq a_i \leq 10^{9}$$

题解：模拟/二分/三分

将数组排序后分成两段，前n/2小的数变成x，后n/2大的数变成y，x和y通过二分/三分的形式找出来，x和y相同的情况下直接计算操作次数即可，否则分别计算(x+1,y)、(x-1,y)、(x,y+1)、(x,y-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
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
void JiuCherish() {
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    std::sort(a + 1,a + n + 1);
    for(int i=1;i<=n/2;i++) {
        b[i] = a[i + n / 2];
    }
    int m = n / 2;
    int l = 0,r = 8e18;
    int f1 = 0;
    int f2 = 0;
    auto check = [&](int mid,int a[]) {
        int res = 0;
        for(int i=1;i<=m;i++) {
            res += std::abs(mid - a[i]);
        }
        return res;
    };
    while(l < r) {
        int mid = l + (r - l) / 2;
        int x1 = check(mid,a);
        int x2 = check(mid + 1,a);
        if(x1 <= x2) {
            r = mid;
            f1 = mid;
        } else {
            l = mid + 1;
            f1 = mid + 1;
        }
    }
    l = 0,r = 8e18;
    while(l < r) {
        int mid = l + (r - l) / 2;
        int x1 = check(mid,b);
        int x2 = check(mid + 1,b);
        if(x1 <= x2) {
            r = mid;
            f2 = mid;
        } else {
            l = mid + 1;
            f2 = mid + 1;
        }        
    }
    if(f1 == f2) {
        int x1 = check(f1,a);
        int x2 = check(f2 - 1,b);
        int ans = x1 + x2;
        
        x1 = check(f1,a);
        x2 = check(f2 + 1,b);
        ans = std::min(ans,x1 + x2);
        
        x1 = check(f1 - 1,a);
        x2 = check(f2,b);
        ans = std::min(ans,x1 + x2);   
        
        x1 = check(f1 + 1,a);
        x2 = check(f2,b);
        ans = std::min(ans,x1 + x2);   
        
        std::cout << ans << endl;
    } else {
        int x1 = check(f1,a);
        int x2 = check(f2,b);       
        std::cout << x1 + x2 << endl;
    }
}

F 双生双宿之探

题意：

我们定义双生数组：数组大小为偶数，且只有2种数组元素，并且这两种元素的出现次数相同。

现在有一个数组，她希望你计算该数组有多少连续子数组是双生数组。

子数组为从原数组中，连续的选择一段元素（可以全选、可以不选）得到的新数组。

数据范围

$$1 \leq T \leq 10^4$$

$$1 \leq n \leq 10^5$$

$$1 \leq a_i \leq 10^{9}$$

题解：双指针

如果区间内元素种类恰好为2的话，我们通过将一种元素设成1，另一种元素设成-1，也就是问有多少区间元素和为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
27
28
29
30
31
32
33
34
35
36
37
38
void JiuCherish() {
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    i64 ans = 0;
    auto get = [&](int l,int r) {
        std::map<int,int> cnt;
        cnt[0] += 1;
        i64 sum = 0;
        for(int i=l;i<=r;i++) {
            sum += (a[i] == a[l] ? 1 : -1);
            ans += cnt[sum];
            cnt[sum] += 1;
        }
    };
    std::map<int,int> mp;
    int i = 1;
    int j = 0;
    while(666) {
        while(mp.size() <= 2 and j + 1 <= n) {
            j += 1;
            mp[a[j]] += 1;
        }
        if(mp.size() == 3) {
            mp[a[j]] -= 1;
            mp.erase(a[j]);
            j -= 1;
        }
        if(mp.size() == 2) get(i,j);
        else break;
        while(mp.size() >= 2) {
            mp[a[i]] -= 1;
            if(!mp[a[i]]) mp.erase(a[i]);
            i += 1;
        }
    }
    std::cout << ans << endl;
}

G. 井然有序之衡

题意：

给定一个数组，可以进行任意次的操作，选择两个元素，使得其中一个+1，另一个-1，小红希望最终变成一个排列，问是否能实现，如果实现输出最小的操作次数，否则输出-1。

数据范围

$$1 \leq n \leq 10^5$$

$$-10^9 \leq a_i \leq 10^{9}$$

题解：排序、数学

通过排序，

如果当前的数比下标[1~n]小，那么需要进行下标-当前的数次计算次减法操作。

如果当前的数比下标[1~n]大，那么需要进行当前的数-下标次计算次加法操作。

如果加法操作和减法操作不相同，输出-1，否则输出任意一个操作次数。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void JiuCherish() {
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    std::sort(a + 1,a + n + 1);
    int add = 0,m = 0;
    for(int i=1;i<=n;i++) {
        if(a[i] < i) {
            add += i - a[i];
        } else if(a[i] > i) {
            m += a[i] - i;
        }
    }
    if(add != m) {
        std::cout << -1 << endl;
    } else {
        std::cout << add << endl;
    }
}

H.井然有序之窗

题意：

构造一个长度为 n 的排列，满足第 i 个元素的范围在 [li,ri] 范围内。

如果不满足，输出-1，否则输出排列。

原题弱化版：整整齐齐

数据范围

$$1 \leq n \leq 10^5$$

$$1 \leq l_i \leq r_i \leq n$$

题解：贪心

我们先将所有区间排序，用一个优先队列来维护“可选的区间右端点”。当我们指定某个区间为 i 的时候，我们首先将所有以 i 为左端点的区间加入优先队列，然后尽量选择目前最小的那个右端点即可。

代码：
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
void JiuCherish() {
    int n;
    std::cin >> n;
    std::vector<std::vector<int>> a;
    for(int i=0;i<n;i++) {
        int x,y;
        std::cin >> x >> y;
        x -= 1;
        y -= 1;
        a.pb({x,y,i});
    }
    std::sort(a.begin(),a.end());
    std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int>>,std::greater<std::pair<int,int>>> pq;
    std::vector<int> ans(n);
    int p = 0;    
    for(int i=0;i<n;i++) {
        while(p < n and a[p][0] <= i) {
            pq.push({a[p][1],a[p][2]});
            p += 1;
        }
        if(pq.size() == 0) {
            std::cout << -1 << endl;
            return;
        }
        auto tp = pq.top();
        pq.pop();
        if(tp.fi < i) {
            std::cout << -1 << endl;
            return;
        }
        ans[tp.se] = i;
    }
    for(auto x : ans) std::cout << x + 1 << ' ';
}

I. 井然有序之桠

题意：

给你一个长度为 n 的排列 a , 构造一个长度为 n 的排列 b ， 满足下面式子

$$\displaystyle\sum_{i=1}^{n}\gcd(a_i,b_i) = k$$

数据范围

$$1 \leq T \leq 10^5$$

$$1 \leq n\leq 10^5,1\leq k \leq \frac{n \times (n + 1)}{2}$$

$$1 \leq a_i \leq n$$

题解：打表、构造、数学

首先gcd权值最大的一定是 n * (n + 1) / 2，最小的一定是n。

要使得权值为 k ，就需要使得权值减少 S - k ，记为 d 。

从大到小枚举 x ，交换 x 和 x−1 可以使得权值减少(x+x−1)−(1+1)=2x−3 ，如果 d≥2x−3d ，直接贪心减去并交换即可，否则就跳过。

在上述过程中，如果某个时刻发现 d<x ，我们就可以直接交换 1 和 d+1 了， (d+1+1)−(1+1)=d ，因为此时小于等于 x 的数字一定没有被交换过。

建议还是打一个表+手玩几个样例，会更清楚。

代码：（贴的jiangly的代码）
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
std::vector<int> construct(int n, i64 k) {
    std::vector<int> p;
    if (n == 0) {
         
    } else if (n == 1) {
        p = {1};
    } else if (n == 3 && k == 4) {
        p = {3, 2, 1};
    } else if (n == 4 && k == 6) {
        p = {3, 4, 1, 2};
    } else if (k >= 2 * n - 1) {
        p = construct(n - 1, k - n);
        p.push_back(n);
    } else {
        p = construct(n - 2, k - 2);
        p.push_back(n);
        p.push_back(n - 1);
    }
     
    return p;
}
 
void solve() {
    int n;
    i64 k;
    std::cin >> n >> k;
     
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
     
    if (k < n) {
        std::cout << -1 << "\n";
        return;
    }
     
    auto p = construct(n, k);
    for (int i = 0; i < n; i++) {
        std::cout << p[a[i] - 1] << " \n"[i == n - 1];
    }
}

J. 硝基甲苯之袭

题意：

给你一个数组，问从中任取两个元素ai,aj(ai < aj)，满足ai xor aj == gcd(ai , aj)的方案数有多少？

数据范围

$$1 \leq n \leq 2 \times 10^5$$

$$1 \leq a_i \leq 2 \times 10^5$$

题解：位运算、数论

对于一个数而言，它和任意一个数的gcd一定是它的某个因子。

那么本题可以通过枚举每个元素x的每个因子p，作为它和其他元素的“假想gcd”，然后我们去检测p是不是等于真正的 gcd(x,x⊕p) 即可。如果确实相等，那么证明p就是真正是gcd，我们直接用map计算 x⊕px 出现的次数。

代码：
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
void JiuCherish() {
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    std::map<int,int> mp;
    for(int i=1;i<=n;i++) mp[a[i]] += 1;
    std::sort(a + 1,a + n + 1);
    int ans = 0;
    int lim = a[n] + 3;
    int idx = 1;
    while(idx <= lim) {
        for(int x=idx;x+idx<=lim;x+=idx) {
            if(mp.find(x) != mp.end()) {
                int y = x + idx;
                if(mp.find(y) != mp.end()) {
                    int now = x ^ y;
                    if(now == idx) {
                        int ct = mp[x] * mp[y];
                        ans += ct;
                    }
                }
            }
        }
        idx += 1;
    }
    std::cout << ans << endl;
}

K.硝基甲苯之魇

题意：

给你一个数组，问有多少个区间[l,r] 满足，区间内所有元素的最大公约数恰好等于他们的异或和。

数据范围

$$1\leq T\leq 10^5$$

$$1 \leq n \leq 2 \times 10^5$$

$$1 \leq a_i \leq 10^9$$

题解：st表，线段树，二分，前缀和

固定左端点的情况，移动右端点，区间gcd变化最多只会有log级别，我们可以通过st表+二分来找到区间的gcd改变点。

即问题转换成，固定左端点 l 时，有多少右端点 r 满足区间xor的值等于x。

查询区间 [l,r] 种，异或前缀和数组里有多少恰好等于 x xor sum[l - 1]。

代码：(学习konbi的)
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
const int B = 19;
struct ST {
    #define lg2(n) (63 - __builtin_clzll((long long)(n)))
    int n;
    std::vector<std::vector<int>> st;
    ST (int n, std::vector<int> &a): n(n) {
        st.assign(B, std::vector<int>(n + 5, 0));
        for (int i = 1; i <= n; i++) st[0][i] = a[i];
 
        for (int j = 1; j < B; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                st[j][i] = std::gcd(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
            }
        }
    }
 
    int query(int l, int r) {
        int k = lg2(r - l + 1);
        return std::gcd(st[k][l], st[k][r - (1 << k) + 1]);
    }
};
 
const int N = 2e5 + 5;
int tr[N * 30][2], tot;
std::vector<int> num[N * 30];
 
void insert(int x, int id) {
    int u = 1;
    for (int i = 0; i < 30; i++) {
        int one = x >> i & 1;
        if (!tr[u][one]) tr[u][one] = ++tot;
        u = tr[u][one];
    }
    num[u].pb(id);
}
 
int query(int x, int l, int r) {
    l--; r--;
    int u = 1;
    for (int i = 0; i < 30; i++) {
        int one = x >> i & 1;
        if (!tr[u][one]) return 0;
        u = tr[u][one];
    }
 
    int R = upper_bound(num[u].begin(), num[u].end(), r) - num[u].begin();
    int L = lower_bound(num[u].begin(), num[u].end(), l) - num[u].begin();
    return R - L;
}

void JiuCherish() {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 5);
    for(int i=1;i<=n;i++) std::cin >> a[i];
    for(int i=1;i<=tot;i++) {
        memset(tr[i],0,sizeof(tr[i]));
        num[i].clear();
        b[i] = 0;
    }
    tot = 0;
    insert(0,0);
    i64 res = 0;
    ST f(n,a);
    for(int i=1;i<=n;i++) {
        b[i] = b[i - 1] ^ a[i];
        int j = i;
        while(j) {
            int now = f.query(j,i);
            int l = 1,r = j;
            while(l < r) {
                int mid = l + r >> 1;
                if(f.query(mid,i) == now) r = mid;
                else l = mid + 1;
            }
            int z = b[i] ^ now;
            res += query(z,l,j);
            j = l - 1;
        }
        insert(b[i],i);
    }
    res -= n;
    std::cout << res << endl;
}

L.一念神魔之耀

题意：

有 l 盏灯排成一排，每盏灯要么是开启状态，要么是关闭状态，用01字符串来描述，其中si=0表示第i盏灯是关闭的，si=1表示第i盏灯是开启的。

每一轮，小红可以从下面两种操作任选一个进行：

  1. 选择连续的 x 盏灯，同时切换他们的状态，即关闭变开启，开启变关闭。
  2. 选择连续的 y 盏灯，同时切换他们的状态，即关闭变开启，开启变关闭。

请你帮忙判断，若能进行至多 l² 轮操作（但可以不进行操作），能否在某一轮操作结束后，同时打开所有灯。如果可以，请输出任意一个合法的方案，否则输出-1。

数据范围

$$1\leq T\leq 500$$

$$1 \leq l \leq 500,1 \leq x,y \leq \frac{l}{3}$$

$$保证字符串仅由0，1构成$$

题解：数学，裴蜀定理，gcd

首先考虑 x = y 的情况，很明显是做一个递推的过程，找到每一个‘0’的位置进行翻转，如果能转换到最后一个数的话，那么就是成立的，否则输出-1。

其次考虑 x ≠ y 的情况，那么一定存在 x,y 不覆盖的一段使得他们翻转，考虑gcd(x,y)为x与y不覆盖能构造成最小的一段连续区间，通过gcd(x,y) 与 x 和 y组合，可以延伸出很多种区间分法，即裴蜀定理（ax + by = (a,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
42
43
44
45
46
47
48
49
50
51
52
53
54
void JiuCherish() {
    int n,x,y;
    std::cin >> n >> x >> y;
    std::string s;
    std::cin >> s;
    s = '?' + s;
    std::vector<int> a(n + 5);
    for(int i=1;i<=n;i++) a[i] = s[i] - '0';
    auto b = a;
    int g = std::gcd(x,y);
    std::vector<std::pair<int,int>> ans;
    for(int i=1;i+g-1<=n;i++) {
        if(a[i]) continue;
        int l,r;
        auto b = ans;
        ans.clear();
        if(i + x - 1 <= n) {
            ans.pb({i,i + x - 1});
            l = i + g;
            r = i + x - 1;
        } else {
            ans.pb({i + g - 1 - x + 1,i + g - 1});
            l = i + g - 1 - x + 1;
            r = i - 1;
        }
        while(l <= r) {
            if(r - l + 1 >= y) {
                ans.pb({l,l + y - 1});
                l += y;
            }
            else if(r + x <= n) {
                ans.pb({r + 1,r + x});
                r += x;
            } 
            else {
                ans.pb({l - x,l - 1});
                l -= x;
            }
        }
        for(auto [l,r] : ans) {
            for(int i=l;i<=r;i++) a[i] ^= 1;
            b.pb({l,r});
        }
        ans = b;
    }
    for(int i=1;i<=n;i++) {
        if(a[i] == 0) {
            std::cout << -1 << endl;
            return;
        }
    }
    std::cout << ans.size() << endl;
    for(auto [l,r] : ans) std::cout << l << ' ' << r << endl;
}

M. 数值膨胀之美

题意：

给你一个数组，需要操作一次：选择一个非空区间，将其中所有元素都乘2，问最小化数组的极差（最大值-最小值）。

数据范围

$$1\leq n\leq 10^5$$

$$1 \leq a_i \leq 10^9$$

题解：模拟，结论

首先统计右移有多少次，如果不能整除6那么说明有一次是特殊的移动。

然后再算左移有多少次。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
void JiuCherish() {
    int n;
    std::cin >> n;
    int ans = n / 6;
    if(n % 6) ans += 1;
    n = n - 6;
    if(n % 6 == 0) {
        std::cout << ans << endl;
        return;
    }
    ans += n / 6;
    std::cout << ans << endl;
}