昨天的比赛思维和坑点也挺多的，考虑问题还是不全面，实现速度也不够快，继续努力吧

A – City of Lights(水题 模拟)

题目链接

题意：

有N盏灯，k次操作，每次操作会改变第i、2i、3i…盏灯的状态（亮的灭，灭的亮），问过程中最多几盏灯灭。

题目分析：

水题，模拟走一遍记录当前灭灯数，每次更新最大值即可。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e6 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;

int a[maxn], ans;

int main(int argc, char const *argv[]) {
    int n, k;
    cin >> n >> k;
    for(int i = 0 ; i<=n ;i++) a[i] = 1;
    int now = 0;
    while (k--) {
        int x;
        cin >> x;
        for (int i = x; i <= n; i = i + x) {
            if (a[i] == 0) {
                a[i] = 1;
                now--;
            } else if (a[i] == 1) {
                a[i] = 0;
                now++;
            }
        }
        ans = max(ans, now);
    }
    cout << ans << endl;
    return 0;
}

B – Blurred Pictures（思维 技巧）

题目链接

题意：

N * N的一张照片，每行给出一个区间[a, b],表示这一行正常像素的范围，其余位置像素模糊。裁剪照片使得剩下一个正方形照片里只有正常像素，求最长边长。有个额外信息：图中任意两个像素间的横线和垂线上不存在模糊像素。

题目分析：

用ans表示最长可行的边长，ans从1开始，循环一遍每行，判断以此行为上边界，ans+1为边长是否可以裁出合适的正方形，如果可以ans++继续判断，如果不可以则ans不变，判断以下一行为上边界是否可以裁处正方形，循环一遍所有行即可。这里判断是否为正方形可以直接判断上下边界是否满足即可，不用判断上下边界间的像素是否可行，原因是题目保证任意两个像素间的横线和垂线上没有模糊像素。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int a[maxn], b[maxn];
int n;
bool check(int top, int len) {
    if(a[top] + len - 1 > b[top] || top + len - 1 > n) return false;
    int bottom = top + len - 1;
    int l = max(a[top], a[bottom]);
    if(l + len - 1 <= b[top] && l + len - 1 <= b[bottom]) return true;
    return false;
}

int main(int argc, char const *argv[]) {
    cin >>n;
    for(int i = 0; i < n; i++) {
        scanf("%d %d",&a[i], &b[i]);
    }
    int ans = 1;
    for(int i = 0; i <n; i++) {
        while(check(i, ans+1)) ans++;
    }
    cout << ans <<endl;
    return 0;
}

D – Monument Tour（中位数）

题目链接

题意：

一个x * y的矩形地图上有几个点，任意选取一条从西到东的路径为主路径，去往每个点后返回主路径，要求走遍所有的点后从地图东边离开，求选取一条主路径使得总路径长度最小。

题目分析：

可以想到中位数的性质，将所有x坐标相等的点连成一条线，然后将这条线的上顶点和下顶点的y坐标放入一个数组中，对所有的x坐标都这样处理，然后将数组进行排序，找到中位数，就是最优主路径的y坐标。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 2e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int mi[maxn], ma[maxn];
vector<int> vec;
int main(int argc, char const *argv[]) {
    int x, y, n;
    cin >> x >> y >> n;
    memset(mi, 0x3f, sizeof(mi));
    memset(ma, -1, sizeof(ma));
    int u, v;
    for (int i = 0; i < n; i++) {
        cin >> u >> v;
        mi[u] = min(mi[u], v);
        ma[u] = max(ma[u], v);
    }
    for (int i = 0; i < 100010; i++) {
        if (mi[i] != 0x3f3f3f3f && ma[i] != -1) {
            vec.push_back(mi[i]);
            vec.push_back(ma[i]);
        }
    }
    sort(vec.begin(), vec.end());
    LL ans = x - 1;
    int mid = vec[(vec.size() - 1) / 2];
    for (int i = 0; i < 100010; i++) {
        if (mi[i] != 0x3f3f3f3f && ma[i] != -1) {
            ans += ma[i] - mi[i] + abs(mid - mi[i]) + abs(ma[i] - mid);
        }
    }
    cout << ans << endl;
    return 0;
}

E – Rounding（思维）

题目链接

题意：

p个人，给出每个人四舍五入后的概率值（这里所有人概率相加后不一定为100），求出每个人可能的最大实际概率值和最小实际概率值（实际概率只有两位小数）

题目分析：

通过四舍五入的规则可知，若四舍五入后的值为x，则其实际值可能为[x-0.5 , x+0.49]，所以要想求一个人实际概率的最大值，就把其他人的概率都设为可能的最小值，用100减去其他人的最小值之和就是这个人的最大可能概率，最小可能概率同理。无解的情况有：算出的最小值大于可能的最大值，或者算出的最大值小于实际的最小值。并且有两个坑要注意：1.题目可能有概率小于0.5的人，如果-0.5，其最小概率为负数了，这是不合理的，需要进行特殊处理。2.算出一个人的最小概率不能为负数，算出的最大概率不能超过其可能的最大概率，最后输出时也需要判断。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
double ma[maxn], mi[maxn], rea[maxn];
char name[maxn][30];
int main(int argc, char const *argv[]) {
    int p;
    cin >> p;
    double mma = 0, mmi = 0;
    for (int i = 0; i < p; i++) {
        cin >> name[i] >> rea[i];
        if (rea[i] != 0) {
            ma[i] = rea[i] + 0.49;
            mma += ma[i];
            mi[i] = rea[i] - 0.5;
            mmi += mi[i];
        }
        else {
            ma[i] = 0.49;
            mi[i] = 0;
            mma += 0.49;
        }
    }
    for (int i = 0; i < p; i++) {
        double a = 100 - mmi + mi[i];
        double b = 100 - mma + ma[i];
        if (a < mi[i] || b > ma[i]) {
            puts("IMPOSSIBLE");
            break;
        }
        printf("%s %.2lf %.2lf\n", name[i], max(max(b,0.0),mi[i]), min(max(a, 0.0), ma[i]));
    }
    return 0;
}

K – Dishonest Driver（区间DP）

题目链接

题意：

给出一个字符串，如果字符串的一部分（可以是整个字符串）由几个循环节组成，则可以用这个循环节代替这一部分，求最终字符串可以压缩成多小。

题目分析：

用到了区间dp的思想，$dp[i][j]$表示从i到j的子串可以压缩的最小长度。对于$i$到$j$之间的$k$，若$i$到$k$为$i$到$j$的一个循环节，则$dp[i][j] = min(dp[i][j],dp[i][k])$,否则，$dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j])$,状态转移有了，剩下就是代码实现了。最外层循环表示子串长度，第二层表示子串在字符串中开始的位置，第三层枚举所有的k，其中循环节可以用kmp来查找，长为 $len$ 的子串的最小循环节长度就是$len – next[len]$。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 800;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
int Next[maxn], dp[maxn][maxn], n;
char s[maxn];
int kmp(int start, int end) {
    Next[0] = -1;
    int n = end - start + 1;
    int i = -1, j = 0;
    while(j < n) {
        if(i == -1 || s[i+start] == s[j+start]){
            i++;
            j++;
            Next[j] = i;
        }
        else {
            i = Next[i];
        }
    }
    return n - Next[n];
}

int main(int argc, char const *argv[]) {
    for(int i = 0; i < 800; i++){
        for(int j = 0; j < 800; j++) dp[i][j] = 0x3f3f3f3f;
    }
    cin >> n >> s+1;
    for(int i = 1; i <= n; i++) dp[i][i] = 1;
    for(int len = 2; len <= n; len++) {
        for(int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            int loop = kmp(i,j);
            for(int k = i; k < j; k++) {
                int x = k - i + 1;
                if(len % x == 0 && x % loop == 0) dp[i][j] = min(dp[i][j],dp[i][k]);
                else dp[i][j] = min(dp[i][j],dp[i][k] + dp[k+1][j]);
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}