比赛链接：

　

A. City Day

题意：给出一个数列，和俩个整数\(x,y\)，要求找到序号最靠前的数字\(d\)，使得\(d\)满足\(a_d<a_j\) (\(d-x\leq j<d\) && \(d<j\leq d+y\))。

分析：由于x和y都小于7，所以直接暴力即可。

AC代码：

#include 
    
     #define SIZE 200007#define rep(i, a, b) for(int i = a; i <= b; ++i)using namespace std;typedef long long ll;void io() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    cout.tie(nullptr);}ll n, x, y, a[SIZE];int main() {    io();    cin >> n >> x >> y;    rep(i, 1, n) cin >> a[i];    rep(i, 1, n) {        bool flag = 1;        for (int k = i - 1, cnt = 1; k > 0 && cnt <= x; k--, cnt++) {            if (a[k] <= a[i]) { flag = 0; break; }        }        for (int k = i + 1, cnt = 1; k <= n && cnt <= y; k++, cnt++) {            if (a[k] <= a[i]) { flag = 0; break; }        }        if (flag) { cout << i << endl; return 0; }    }}
    

　

B. Water Lily

分析：几何水题，推个方程就好。

AC代码：

#include 
    
     using namespace std;int main() {    double l, h;    cin >> h >> l;    double s = (l * l - h * h) / 2 / h;;    printf("%.12lf", s);}
    

　

C. MP3

题意：一个数组中如果有\(K\)种不同的数，每个数的占用空间是\(k=log_2K\)，这组数总内存是\(nk\)，你有一个改变数的大小的能力，小于\(l\)可以改成\(l\)大于\(r\)可以改成\(r\)，现在给出总内存，求最少改变次数。

分析：先求出最多能存\(k\)个数，然后我们显然用\(map\)来记录数据，然后把\(map\)中的前\(k\)个数和后k个数丢进一个双向队列（因为我们至少删除\(k\)个数，而这\(k\)个数只能在首或尾），对这\(2k\)个数求前缀和，在每k个数中求出最小值。

AC代码：

#include 
    
     #define INF 0x3f3f3f3f#define SIZE 400007#define rep(i, a, b) for(int i = a; i <= b; ++i)using namespace std;typedef long long ll;void io() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    cout.tie(nullptr);}ll n, I, a[SIZE], pre[SIZE];map
     
       mp;deque
      
       
         > q;int main() {    io(); cin >> n >> I;    rep(i, 1, n) {        cin >> a[i];        ++mp[a[i]];    }    ll k = 0; I *= 8;   //用k记录最多存储几个数    while (1ll * ceil(log2(mp.size() - k))* n > I) k++;    auto it = mp.begin();    auto itr = mp.rbegin();    rep(i, 1, k) {        q.push_back(make_pair(it->first, it->second));        q.push_front(make_pair(itr->first, itr->second));        it++, itr++;    }    auto itx = q.begin();    rep(i, 1, q.size()) pre[i] = pre[i - 1] + itx++->second;    ll sum = INF;    rep(i, k, 2 * k) sum = min(sum, pre[i] - pre[i - k]);    cout << sum;}
       
      
     
    

　

D. Welfare State

题意：给定一个\(n\)个数的数列和两种操作。操作一是把序号为\(p\)的数字修改为\(x\)，操作二是把所有小于\(x\)的数字修改为\(x\)。输出最终的数列。

分析：乍一看像线段树，但是写得不好就会\(T\)（别问我怎么知道的），实际上直接乱搞就过了。我们发现对于第一种操作和第二种操作我们只需要考虑较大的那种，因此开两个数组，\(b\)数组保存操作一，\(maxx\)数组保存操作二，最后取\(max\)输出即可。

AC代码：

#include
    
     #define SIZE 200007#define rep(i, a, b) for(int i = a; i <= b; ++i)using namespace std;typedef long long ll;void io() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    cout.tie(nullptr);}ll n, m, a[SIZE], b[SIZE], sig, maxx[SIZE], pos;int main() {    io(); cin >> n;    rep(i, 1, n) cin >> a[i];    cin >> m;    rep(i, 1, m) {        cin >> sig;        if (sig == 1) {            cin >> pos;            cin >> a[pos];            b[pos] = i;        }        else cin >> maxx[i];    }    for (int i = m; i; --i) maxx[i - 1] = max(maxx[i - 1], maxx[i]);    rep(i, 1, n) cout << max(a[i], maxx[b[i]]) << ' ';}
    

　

E. Matching vs Independent Set

题意：给定一个\(3n\)个顶点，\(m\)条边的图和两个定义。定义一：如果一个边集中没有两条边共享一个端点，则称为匹配。定义二：如果一个点集中没有两个顶点与边连接，则一组顶点称为独立集。判断给定的图是否存在匹配或独立集（\(size=n\)）。

分析：乍看像一道图论，实际上并不需要图论算法。首先用vector存图。然后观察到匹配和独立集必定至少存在一个。证明：我们考虑每次取\(n\)个点，若不存在独立集，则这\(n\)个点中至少存在一条边，这样操作到最后至多存在\(n-2\)个点不连边，且不存在独立集；但是这样的构造后我们发现，在那\(2n+2\)个点中至少存在\(n+1\)条边构成匹配。因此，我们只需要处理出所有独立的点，判断是否能构成独立集，若不能则至少有\(2n+2\)个点有连边，我们两两取边加入匹配集并输出即可。

AC代码：

#include 
    
     #define SIZE 500007#define rep(i, a, b) for(int i = a; i <= b; ++i)using namespace std;typedef long long ll;void io() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    cout.tie(nullptr);}typedef long long ll;vector 
     
      
        > h[SIZE];vector 
       
         edge, vec;int n, m, T, cnt, u, v;bool vis[SIZE];int main() {    io(); cin >> T;    while (T--) {        cin >> n >> m;        edge.clear(); vec.clear(); cnt = 0;        rep(i, 1, 3 * n) { h[i].clear(); vis[i] = false; }        rep(i, 1, m) {            cin >> u >> v;            h[u].emplace_back(make_pair(v, i));            h[v].emplace_back(make_pair(u, i));        }        rep(i, 1, 3 * n) {            bool flag = false;            for (auto it : h[i]) {                int pos = it.first;                if (vis[pos]) {                    flag = true; vis[pos] = false;                    edge.emplace_back(it.second);                    break;                }            }            if (!flag) vis[i] = true, cnt++;            else cnt--;        }        if (cnt >= n) {            cout << "IndSet" << endl;            int num = 0;            rep(i, 1, 3 * n) {                if (num >= n) break;                if (vis[i]) { num++; cout << i << ' '; }            }        }        else {            cout << "Matching" << endl;            rep(i, 0, n - 1) cout << edge[i] << ' ';        }        cout << endl;    }}
       
      
     
    

　

F. Rectangle Painting 1

题意：给定一个\(n\times n\)的方格网。每次能在图中选择一个\(a\times b\)的矩形，将该矩形中的方格全部改为“.”，一次操作的花费为\(max(a,b)\)。要求把“#”全部改成“.”，求最小的花费。

分析：由于\(n\leq 50\)，所以我们考虑直接暴力四重dp。用\(f[x][y]\)记录\((1,1)\)到\((x,y)\)的“#”数量，用\(dp[x][y][i][j]\)记录\((x,y)\)和\((i,j)\)之间全部染成“.”的花费，然后转移即可。

AC代码：

#include 
    
     #define SIZE 55#define rep(i, a, b) for(int i = a; i <= b; ++i)using namespace std;typedef long long ll;void io() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    cout.tie(nullptr);}int n;char s[SIZE][SIZE];int dp[SIZE][SIZE][SIZE][SIZE];int f[SIZE][SIZE];int main() {    io(); cin >> n;    rep(i, 1, n) {        cin >> (s[i] + 1);    }    rep(i, 1, n) {        rep(j, 1, n) {            f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + (s[i][j] == '#');        }    }    rep(x, 1, n) {        rep(y, 1, n) {            rep(i, 1, n - x + 1) {                rep(j, 1, n - y + 1) {                    int tx = i + x - 1, ty = j + y - 1;                    int t = f[tx][ty] - f[i - 1][ty] - f[tx][j - 1] + f[i - 1][j - 1];                    if (!t) { dp[i][j][tx][ty] = 0; continue; }                    else dp[i][j][tx][ty] = max(x, y);                    rep(k, i + 1, tx) {                        dp[i][j][tx][ty] = min(dp[i][j][tx][ty], dp[i][j][k - 1][ty] + dp[k][j][tx][ty]);                    }                    rep(k, j + 1, ty) {                        dp[i][j][tx][ty] = min(dp[i][j][tx][ty], dp[i][j][tx][k - 1] + dp[i][k][tx][ty]);                    }                }            }        }    }    cout << dp[1][1][n][n];}