第 45 屆國際大學生程式設計競賽（ICPC）亞洲區域賽（濟南）(熱身賽)

希望明天正賽也有好運氣吧，為隊友和自己拿個好點的成績，再見2020，，，

思路：
將數的長度分為奇數和偶數的情況進行討論，如果長度為奇數，那結果就是 1 0 l e n / 2 ? 1 10^{len/2}-1 10len/2?1；如果長度為偶數，那么如果數的前一半大于后一半，則結果就是前一半數的大小，否則結果是前一半數的大小減一，

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
char s[105];

int main() {
    scanf("%s",s + 1);
    int len = strlen(s + 1);
    int ans = 0;
    if(len % 2 == 0) {
        int n1 = 0,n2 = 0;
        for(int i = 1;i <= len / 2;i++) {
            n1 = n1 * 10 + s[i] - '0';
        }
        for(int i = len / 2 + 1;i <= len;i++) {
            n2 = n2 * 10 + s[i] - '0';
        }
        if(n1 <= n2) {
            ans = n1;
        } else {
            ans = n1 - 1;
        }
    } else {
        ans = 1;
        for(int i = 1;i <= len / 2;i++) {
            ans = ans * 10;
        }
        ans--;
    }
    printf("%d\n",ans);
    return 0;
}

思路：
大膽猜想資料達到一定范圍一定是 y e s yes yes，所以小范圍暴力，大范圍 y e s yes yes，
證明的思路來自ICPC群大佬：

• 假設有 s q r t ( 2 ? 1 e 5 ) sqrt(2*1e5) sqrt(2?1e5)個數，那么兩兩之間異或會產生不少于 1 e 5 1e5 1e5個結果，根據鴿巢原理，出現 a ⊕ b = x a ⊕ b=x a⊕b=x的對數至少兩對（由于數之間是不同的，所以不會出現 a ⊕ b = x 且 a ⊕ c = x a⊕b=x且a⊕c=x a⊕b=x且a⊕c=x），那么可以一定可以出現 a ⊕ b = x , c ⊕ d = x a⊕b=x,c⊕d=x a⊕b=x,c⊕d=x，則一定有 a ⊕ b ⊕ c ⊕ d = 0 a⊕b⊕c⊕d=0 a⊕b⊕c⊕d=0，

（但是實測 n ≥ 40 n≥40 n≥40就輸出 y e s yes yes也能過，應該有更高級的證明方法吧）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
int a[maxn];
int vis[maxn];

int main(){
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);
    }
    int len = sqrt(200000);
    if(n >= len) {
        printf("Yes\n");
        return 0;
    }
    for(int i = 2;i <= n;i++) {
        for(int j = i + 1;j <= n;j++) {
            vis[a[i] ^ a[j]]++;
        }
    }
    for(int i = 2;i <= n - 2;i++) {
        for(int j = i + 1;j <= n;j++) {
            vis[a[i] ^ a[j]]--;
        }
        for(int j = 1;j < i;j++) {
            if(vis[a[i] ^ a[j]]) {
                printf("Yes\n");
                return 0;
            }
        }
    }
    printf("No\n");
    return 0;
}

思路：
wzf給的思路，定義 d p [ i ] [ j ] dp[i][j] dp[i][j]為考慮前 i i i個天，里面有 j j j天不開心的最小數字和，
則轉移就是列舉之前天的不開心數，然后算出當前選擇 a a a數或者選擇 b b b是否會導致這一天不開心，

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e3 + 7;
const int INF = 0x3f3f3f3f;
int a[maxn],b[maxn];
int dp[maxn][maxn];

int main() {
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d%d",&a[i],&b[i]);
    }
    memset(dp,0x3f,sizeof(dp));
    dp[1][0] = min(a[1],b[1]);
    for(int i = 2;i <= n;i++) {
        for(int j = 0;j < i;j++) {
            if(dp[i - 1][j] == INF) continue;
            if(a[i] * (i - 1) < dp[i - 1][j]) {
                dp[i][j + 1] = min(dp[i][j + 1], dp[i-1][j]+a[i]);
            } else {
                dp[i][j] = min(dp[i][j],dp[i - 1][j] + a[i]);
            }

            if(b[i] * (i - 1) < dp[i - 1][j]) {
                dp[i][j + 1] = min(dp[i][j + 1],dp[i - 1][j] + b[i]);
            } else {
                dp[i][j] = min(dp[i][j],dp[i - 1][j] + b[i]);
            }
        }
    }
    int ans = n;
    for(int i = 0;i <= n;i++) {
        if(dp[n][i] != INF) {
            ans = i;break;
        }
    }
    printf("%d\n",ans);
    return 0;
}