Codeforces 1255 #Codeforces

1255A.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const int maxn = 100, maxm=1e5 + 1000;

int v[] = {5, 2, 1};

void solve() {
    ll a, b;
    cin >> a >> b;
    ll diff = abs(a - b);
    ll cnt = 0;
    for(int i=0; i<3; i++){
        cnt += diff / v[i];
        diff = diff % v[i];
    }
    cout << cnt << endl;
}

signed main() {
    Android;
    int t;
    cin >> t;
    while(t--)
    solve();
}

1255B.cpp

 #include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const int maxn = 1e3 + 100;

void solve() {
    int n, m, tmp, sum=0;
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> tmp;
        sum += tmp;
    }
    if(m < n || n == 2){
        cout << -1 << '\n';
        return;
    }
    cout << 2 * sum << '\n';
    for(int i=0; i<n; i++){
        cout << (i + 1) << " " << ((i + 1) % n + 1) << "\n";
    }
}

signed main() {
    Android;
    int t;
    cin >> t;
    while(t--)
    solve();
}

1255C_1.cpp

// 利用该题的某些特点，可以减少 代码/逻辑链条 长度
// 见1255C_2.cpp
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i,n) for(int i=1;i<=n;++i)

using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const int maxn = 1e5 + 100;

int appear[maxn][4] = {0};
int num[maxn][3];
int mark[maxn] = {0};
int ans[maxn];

void solve() {
    int n, v;
    cin >> n;
    for(int i=0; i<n-2; i++){
        for(int j=0; j<3; j++){
            cin >> v;
            num[i][j] = v;
            appear[v][++appear[v][0]] = i;
        }
    }
    
    for(int i=1; i<=n; i++) {
        if(appear[i][0] == 1) {
            ans[0] = i;
            int idx = appear[i][1];
            for(int j=0; j<3; j++){
                if(num[idx][j] == ans[0]) continue;
                if(appear[num[idx][j]][0] == 2){
                    ans[1] = num[idx][j];
                    break;
                }
            }
            break; 
        }
    }
    mark[ans[0]] = mark[ans[1]] = 1;

    for(int i=2; i<n; i++){
        int pprev = ans[i-2], prev = ans[i-1];
        for(int j=1; j<=appear[pprev][0] && ans[i] == 0; j++){
            for(int k=1; k<=appear[prev][0] && ans[i] == 0; k++){
                if(appear[pprev][j] != appear[prev][k]) continue;
                int idx = appear[prev][k], next_v = -1;
                for(int j=0; j<3; j++){
                    if(num[idx][j] != pprev && num[idx][j] != prev)
                        next_v = num[idx][j];
                }
                if(!mark[next_v]){
                    mark[next_v] = 1;
                    ans[i] = next_v;
                }
            }
        }
        
    }

    for(int i=0; i<n; i++){
        cout << ans[i] << " ";
    }
    cout << "\n";

}

signed main() {
    Android;
    redirect_input();
    solve();
}

1255C_2.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0; i<n; i++)

using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const int maxn = 1e5 + 100;
vector<int> G[maxn];
bool mark[maxn] = {0};
int occur[maxn] = {0}, ans[maxn];

void solve() {
    int n, v[3];
    cin >> n;
    F(i, n-2){
        F(j, 3) cin >> v[j], occur[v[j]]++;
        F(j, 3) F(k, 3) if(j != k) G[v[j]].push_back(v[k]);
    }
    for(int i=1; i<=n; i++) if(occur[i] == 1) ans[0] = i;
    for(int i=0; i<2; i++) ans[i+1] = G[ans[0]][i]; // !!!
    if(occur[ans[2]] == 2) swap(ans[1], ans[2]);
    for(int i=0; i<3; i++) mark[ans[i]] = true;

    for(int i=3; i<n; i++){
        for(int v:G[ans[i-2]]) {
            if(!mark[v]) ans[i] = v, mark[v] = true; // !!!
        }   
    }

    F(i, n) cout << ans[i] << ' ';
}

signed main() {
    Android;
    solve();
}

1255D_1.py

 from functools import reduce
import string

class IoTool:  # a tool for input redirection 
    DEBUG = 0
    def _read_dbg():
        with open('./input.txt', 'r') as f:
            lines = f.readlines()
        for l in lines: yield l.strip() 
    def _read_oj():
        import sys
        return iter(sys.stdin.read().split('\n'))  # It does help a lot.
    reader = _read_dbg() if DEBUG else _read_oj()
    def read(): return next(IoTool.reader)

input = IoTool.read

dic = string.ascii_letters + string.digits

def readline():
    return list(map(int, input().split()))

def main():
    r, c, k = readline()
    ans = [[-1] * c for _ in range(r)]
    matrix = [list(input()) for _ in range(r)]
    rice_cnt = 0
    for line in matrix:
        rice_cnt += reduce(lambda x, y: x + (1 if y == 'R' else 0), line, 0)
    distribution = [rice_cnt // k + (1 if i < rice_cnt % k else 0) for i in range(k)]
    cur_idx = 0
    for n in range(r * c):
        x, y = n // c, n % c
        if x % 2 != 0:
            y = c - y - 1
        char = matrix[x][y]
        ans[x][y] = dic[cur_idx]
        if char == 'R':
            distribution[cur_idx] -= 1
            if distribution[cur_idx] == 0 and cur_idx + 1 < k:
                cur_idx += 1
    for l in ans:
        print(''.join(l))

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        main()

1255D_2.py

 from functools import reduce
import string

class IoTool:  # a tool for input redirection 
    DEBUG = 0
    def _read_dbg():
        with open('./input.txt', 'r') as f:
            lines = f.readlines()
        for l in lines: yield l.strip() 
    def _read_oj():
        import sys
        return iter(sys.stdin.read().split('\n'))  # It does help a lot.
    reader = _read_dbg() if DEBUG else _read_oj()
    def read(): return next(IoTool.reader)

input = IoTool.read

dic = string.ascii_letters + string.digits

def main():
    r, c, k = map(int, input().split())
    ans = [[None] * c for _ in range(r)]
    matrix = [list(input()) for _ in range(r)]
    rice_cnt = 0
    for i in range(r):
        if i % 2: matrix[i].reverse()
        rice_cnt += matrix[i].count('R')
    distribution = [rice_cnt // k + (1 if i < rice_cnt % k else 0) for i in range(k)]
    cur_idx = 0
    for x in range(r):
        for y in range(c):
            char = matrix[x][y]
            ans[x][y] = dic[cur_idx]
            if char == 'R':
                distribution[cur_idx] -= 1
                if distribution[cur_idx] == 0 and cur_idx + 1 < k:
                    cur_idx += 1
    for i in range(r):
        if i % 2:
            ans[i].reverse()
        print(''.join(ans[i]))

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        main()

1255E1.py

class IoTool:  # a tool for input redirection 
    DEBUG = 0
    def _read_dbg():
        with open('./input.txt', 'r') as f:
            lines = f.readlines()
        for l in lines: yield l.strip() 
    def _read_oj():
        import sys
        return iter(sys.stdin.read().split('\n'))  # It does help a lot.
    reader = _read_dbg() if DEBUG else _read_oj()
    def read(): return next(IoTool.reader)

input = IoTool.read

def get_prime_factor(val):
    p = 2
    result = []
    while p * p < val:
        if val % p == 0: 
            result.append(p)
            while val % p == 0: val //= p
        p += 1

    if val != 1:
        result.append(val)
    return result

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = [idx for idx, v in enumerate(a) if v == 1]
    factors = get_prime_factor(len(a))
    ans = -1
    for factor in factors:
        cost = 0
        for i in range(len(a) // factor):
            median = a[factor * (2 * i + 1) // 2]
            for j in range(factor * i, factor * (i + 1)):
                cost += abs(median - a[j])
        ans = cost if any([ans == -1, cost < ans]) else ans
    print(ans)

if __name__ == "__main__":
    main()

1255E2.cpp

 #include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0; i<n; i++)

using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5 + 100;

vector<ll> get_factor(ll val){
    vector<ll> ret;
    for(ll i=2; i*i<=val; i++){
        if(val % i==0){
            ret.push_back(i);
            while(val % i==0) val /= i;
        }
    }
    if(val > 1) ret.push_back(val);
    return ret;
}

void solve() {
    ll n;
    cin >> n;
    vector<ll> presum(n + 1, 0);
    for(int i=1; i<=n; i++) {
        cin >> presum[i];
    }
    for(int i=1; i<=n; i++) presum[i] += presum[i-1];
    vector<ll> factors = get_factor(presum[n]);
    ll gl_ans = inf;
    for(ll factor:factors){
        ll ans = 0;
        for(ll pre:presum){
            pre = pre % factor;
            ans += min(pre, factor - pre);
        }
        gl_ans = min(ans, gl_ans);
    }
    if(factors.size() == 0) gl_ans = -1;
    cout << gl_ans << endl;
}

signed main() {
    Android;
    solve();
}