Codeforces Round #609 (Div. 2)【A - D】

題目來源：https://codeforces.com/contest/1269

這場可以上分的，可惜沒打。不過虛拟參與的時候也有很多問題，比如B題瘋狂WA，寫的也特别慢，最後三題，打完後補了一題。E題感覺有點複雜，不是我這個水準該寫的

1269A - Equation

題目要找滿足的a和b使a-b=n 不妨設 a=(x+1) * n，b=x * n 我們按題目的要求适當的設定一個x就好了

值得注意的是n為質數或1的情況 不能随便設 第一個樣例給了一個好開頭 讓a=9 * n，b=8 * n恰到好處

#include<iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <stack>

#define ls k<<1,l,mid
#define rs k<<1|1,mid+1,r
#define r(x) read(x)
#define rrr(x, y, z) read(x);read(y);read(z)
#define mp(x, y) make_pair(x,y)
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define FOR(i, l, r) for(int i=l;i<=r;i++)
using namespace std;

const int N = 5e5 + 5;
const int M = 1e3 + 5;
const int mod = 1e9 + 7;
const int INF = 0x7fffffff;
const int SZ = 17;
const double eps = 1e-8;
const double PI = acos(-1);
typedef long long LL;
typedef pair<int, int> pt;

int n, m;

template<class T>
inline void read(T &x) {
    char c;
    x = 1;
    while ((c = getchar()) < '0' || c > '9') if (c == '-') x = -1;
    T res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') res = res * 10 + c - '0';
    x *= res;
}

int main() {
    int t;
        r(n);
        cout<<9*n<<' '<<8*n<<endl;

    return 0;
}
           

1269B - Modulo Equality

據說這題通過一些字元串比對算法 直接O(n)解決 ，我是暴力O(n^2)寫的

思路的話：不管加多少，如果能成功比對，那串f的第一個元素一定會變成串g的某一個元素，枚舉這個n次，然後判斷比對不比對n次 複雜度O(n^2) 記得排序

#include<iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <stack>

#define ls k<<1,l,mid
#define rs k<<1|1,mid+1,r
#define r(x) read(x)
#define rrr(x, y, z) read(x);read(y);read(z)
#define mp(x, y) make_pair(x,y)
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define FOR(i, l, r) for(int i=l;i<=r;i++)
using namespace std;

const int N = 1e5 + 5;
const int M = 1e3 + 5;
const int mod = 1e9 + 7;
const int INF = 0x7fffffff;
const int SZ = 17;
const double eps = 1e-8;
const double PI = acos(-1);
typedef long long LL;
typedef pair<int, int> pt;

int n, m;
int f[N], g[N];

template<class T>
inline void read(T &x) {
    char c;
    x = 1;
    while ((c = getchar()) < '0' || c > '9') if (c == '-') x = -1;
    T res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') res = res * 10 + c - '0';
    x *= res;
}

int main() {
    r(n); r(m);
    FOR(i, 1, n) r(f[i]);
    FOR(i, 1, n) r(g[i]);
    sort(f + 1, f + n + 1);
    sort(g + 1, g + n + 1);
    int ans = INF;
    FOR(i, 1, n) {
        g[i + n] = g[i];
    }
    FOR(i, 1, n) {
        int gg = (g[i] - f[1] + m) % m;
        bool flag = 1;
        FOR(j, 2, n) {
            if ((f[j] + gg) % m != g[j+i-1]) {
                flag = 0;
                break;
            }
        }
        if (flag) ans = min(ans, gg);
    }
    cout << ans << endl;
    return 0;
}
           

1269C - Long Beautiful Integer

以前m個數為周期 循環到n個數 如果這個序列比原序列大 那就是這個序列

否則把前m個數+1 【可能要進位】 然後再循環到n

特别的是 如果原序列為m個9 ，那就要循環到n+1

#include<iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <stack>

#define ls k<<1,l,mid
#define rs k<<1|1,mid+1,r
#define r(x) read(x)
#define rrr(x, y, z) read(x);read(y);read(z)
#define mp(x, y) make_pair(x,y)
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define FOR(i, l, r) for(int i=l;i<=r;i++)
using namespace std;

const int N = 1e5 + 5;
const int M = 1e3 + 5;
const int mod = 1e9 + 7;
const int INF = 0x7fffffff;
const int SZ = 17;
const double eps = 1e-8;
const double PI = acos(-1);
typedef long long LL;
typedef pair<int, int> pt;

int n, m;
char s1[N << 1], s2[N << 1];

template<class T>
inline void read(T &x) {
    char c;
    x = 1;
    while ((c = getchar()) < '0' || c > '9') if (c == '-') x = -1;
    T res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') res = res * 10 + c - '0';
    x *= res;
}

int main() {
    r(n);
    r(m);
    scanf("%s", s1 + 1);
    for (int i = 1; i <= n; i++) {
        s2[i] = s1[(i - 1) % m + 1];
    }
    bool flag = 1;
    for (int i = 1; i <= n; i++) {
        if (s2[i] > s1[i]) {
            break;
        } else if (s2[i] < s1[i]) {
            flag = 0;
            break;
        }
    }
    if (!flag) {
        bool f9 = 1;
        for (int i = 1; i <= m; i++) {
            if (s1[i] != '9') {
                f9 = 0;
                break;
            }
        }
        if (f9) {
            cout<<n+1<<endl;
            s1[1] = '1';
            for (int i = 2; i <= m; i++) {
                s1[i] = '0';
            }
            for (int i = 1; i <= n + 1; i++) {
                cout << s1[(i - 1) % m + 1];
            }
            cout << endl;
            return 0;
        }
        for (int i = m; i >= 1; i--) {
            if (s1[i] == '9') {
                s1[i] = '0';
            } else {
                s1[i]++;
                break;
            }
        }
        for (int i = 1; i <= n + 1; i++) {
            s2[i]=s1[(i - 1) % m + 1];
        }
    }
    cout<<n<<endl;
    for (int i = 1; i <= n; i++) {
        cout<<s2[i];
    }
    cout<<endl;
    return 0;
}
           

1269D - Domino for Young

這題代碼比上一題短多了…

我就是找到了一個規律， 如果兩個相鄰的奇數之間的偶數的個數為偶數的話 那麼這兩個奇數列以及之間的都可以鋪滿

最後就 變成了找奇數列的序号是 奇數和偶數的個數 取最小值 然後加上所有數/2 的和

因為奇數和奇數之間 或 偶數和偶數之間 一定有奇數個 偶數列 ，是以每次配對都是在 奇數 和 偶數中各找一個列

#include<iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <stack>

#define ls k<<1,l,mid
#define rs k<<1|1,mid+1,r
#define r(x) read(x)
#define rrr(x, y, z) read(x);read(y);read(z)
#define mp(x, y) make_pair(x,y)
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define FOR(i, l, r) for(int i=l;i<=r;i++)
using namespace std;

const int N = 1e5 + 5;
const int M = 1e3 + 5;
const int mod = 1e9 + 7;
const int INF = 0x7fffffff;
const int SZ = 17;
const double eps = 1e-8;
const double PI = acos(-1);
typedef long long LL;
typedef pair<int, int> pt;

int n, m;
template<class T>
inline void read(T &x) {
    char c;
    x = 1;
    while ((c = getchar()) < '0' || c > '9') if (c == '-') x = -1;
    T res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') res = res * 10 + c - '0';
    x *= res;
}

int main() {
    r(n);
    LL ans1=0,ans2=0;
    FOR(i,1,n){
        int a; r(a);
        ans1+=a/2;
        ans2+=a/2;
        if(a&1){
            if(i&1) ans1++;
            else ans2++;
        }
    }
    cout<<min(ans1,ans2)<<endl;
    return 0;
}