Orz 教主的比赛题解

T1 字符串还原:

直接暴力模拟所有情况即可。

同时，考虑一个十分方便的函数：reverse 函数。可以直接将字符串全部翻转

用法：

string s;
reserve(s.begin(), s.end());

那么，如何判断该组数据合法？

不难发现，除开翻转的那个串，剩下的两个串，一个加$k$，一个减$k$, 如果我们把他们相加起来呢？正好就是原字母的两倍。那么，利用这个性质，再和被翻转过的那个串的原串进行对比，就可以判断出这种情况是否合法了。

代码：（总共分三种情况）

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

int n;

bool judge(string s1, string s2, string s3){
    int len = s1.length();
    bool flag = 1; 
    reverse(s1.begin(), s1.end());
    for(int i = 0; i < n; i++){
        if((((int)s2[i] - 'a' + s3[i] - 'a') - 2 * (s1[i] - 'a')) % 26 != 0){
            flag = 0;
            break;
        }
    }
    return flag;
}

int main(){
    string s1, s2, s3;
    cin >> n;
    cin >> s1 >> s2 >> s3;
    if(judge(s1, s2, s3)) reverse(s1.begin(), s1.end()), cout << s1 << endl;
    else if(judge(s2, s1, s3)) reverse(s2.begin(), s2.end()), cout << s2 << endl;
    else if(judge(s3, s2, s1)) reverse(s3.begin(), s3.end()), cout << s3 << endl;
    return 0;
}

T2: 包裹快递

题目中有这样一句话：最大的xx最小。

思路秒出：二分答案。

1、我们二分什么？当然是二分速度啦。

2、如何判断当前二分的速度是否合法？当然是一直利用这个最大速度跑路啦！如果最大速度跑路，还会出现不能及时到达的情况，肯定是不合法的，需要增大速度。反之，我们要降低速度。

3、精度问题：毒瘤数据卡$double$精度，我们要开$long double$，而且二分判断退出时必须要有够大的小精度，比如$1e-6$ ~ $1e-7$左右。太高了又会超时。

#include <bits/stdc++.h>
using namespace std;
#define N 1000010
const long double inf = 1e7;
const long double eof = 1e-7;

template <class T>
inline void read(T& a){
    T x = 0, s = 1;
    char c = getchar();
    while(!isdigit(c)){
        if(c == '-') s = -1;
        c = getchar();
    }
    while(isdigit(c)){
        x = x * 10 + (c ^ '0');
        c = getchar();
    }
    a = x * s;
    return ;
}

int n; 
long double in[N], end[N], s[N];

bool check(long double speed){
    long double t = 0;
    for(int i = 1; i <= n; i++){
        t += (long double)s[i] * 1.0 / speed;
        if(t < in[i]) t = in[i];
        else if(t > end[i])
            return 0; 
    }
    return 1;
}

int main(){
    read(n);
    for(int i = 1; i <= n; i++){
        cin >> in[i] >> end[i] >> s[i];
    }
    long double l = 0.0, r = inf;
    while(r - l > eof){
        long double mid = (l + r) / 2.00;
        if(check(mid)) r = mid;
        else l = mid;
    }
    printf("%.2Lf", l);
    return 0;
}

T3: 圆环取数

模拟赛怎么可能没有$dp$呢？所以本题考虑$dp$。

设$dp_{i, j， 0/1}$表示向左/右移动 $i$ 步或者 $j$ 步的代价。

转移方程：

$dp_{i, j, 0} = min(dp_{i, j - 1, 0} + maxn, dp_{i, j-1, 1} + maxn * (i + j))$

$dp_{i, j, 1} = min(dp_{i-1, j, 1} + maxn, dp_{i-1,j, 0} + maxn * (i + j ) )$

$maxn$即为区间中的最大值，可以直接暴力预处理。

同时，因为我们反正是要把数取完的，所以数字的消耗就是所有数的和，直接统计一遍即可。

#include <bits/stdc++.h>
using namespace std;
#define N 2010
const int inf = (int)1e8;

template <class T>
inline void read(T& a){
    T x = 0, s = 1;
    char c = getchar();
    while(!isdigit(c)){
        if(c == '-') s = -1;
        c = getchar();
    }
    while(isdigit(c)){
        x = x * 10 + (c ^ '0');
        c = getchar();
    }
    a = x * s;
    return ;
}

int dp[N][N][2];
int mx[N + 1000][N + 1000];
int n, k;
int sum = 0;

int main(){
    read(n), read(k);
    for(int i = 1;i <= n; i++){
        read(mx[i][i]), sum += mx[i][i];
    }
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            mx[i][j] = max(mx[i][j-1], mx[j][j]);
    int ans = inf; 
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n - i; j++){
            if(!i && !j) continue;
            if(j > 0) dp[i][j][1] = min(dp[i][j-1][1] + mx[i+k+2][n-k-j+1], dp[i][j-1][0] + mx[i+k+2][n-k-j+1]*(i+j));
            else dp[i][j][1] = inf;
            if(i > 0) dp[i][j][0] = min(dp[i-1][j][0]+mx[i+k+1][n-k-j],dp[i-1][j][1]+mx[i+k+1][n-k-j]*(i+j));
            else dp[i][j][0] = inf;
            if(i + j == n) ans = min(ans, min(dp[i][j][1], dp[i][j][0]));
        }
    }
    printf("%d
", ans + sum);
    return 0;
}

T4: 逃脱