题目链接:https://codeforces.com/contest/1119

A. Ilya and a Colorful Walk

题解:感觉我写了一个很麻烦的写法。我是先将所有相同的元素整合在一起,分别存对应元素最左端点ll和最右端点rr。那么枚举元素,只需要考虑这个元素与它不同元素的最大差即可。作两遍枚举

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

const int INF = 0x3f3f3f3f;
const int N = 3e5 + 5;
int n;
vector<int> v;
struct node {
    int x,id;
}a[N];
struct per {
    int minn = INF, maxx = 0;
}e[N];
int getid(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
int main() {
    read(n);
    for(int i = 1; i <= n; i++) {
        read(a[i].x); a[i].id = i;
        v.push_back(a[i].x);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i = 1; i <= n; i++) {
        int x = getid(a[i].x);
        e[x].maxx = max(a[i].id, e[x].maxx);
        e[x].minn = min(a[i].id, e[x].minn);
    }
    int ans = 0;
    int maxx = 0, minn = INF;
    for(int i = 0; i < v.size(); i++) {
        int x = getid(v[i]);
        if(maxx != 0) ans = max(abs(maxx - e[x].minn), ans);
        if(minn != INF) ans = max(abs(e[x].maxx - minn), ans);
        maxx = max(e[x].maxx, maxx);
        minn = min(e[x].minn, minn);
    }
    maxx = 0, minn = INF;
    for(int i = v.size() - 1; i >= 0; i--) {
        int x = getid(v[i]);
        if(maxx != 0) ans = max(abs(maxx - e[x].minn), ans);
        if(minn != INF) ans = max(abs(e[x].maxx - minn), ans);
        maxx = max(e[x].maxx, maxx);
        minn = min(e[x].minn, minn);
    }
    cout << ans;
    return 0;
}

B. Alyona and a Narrow Fridge

很显然有一个贪心的思路,对于更长的bottle我们应该把它和跟他差不多长的放在一起。所以先枚举kk,对于前kk个贪心尝试是否可行即可

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

const int INF = 0x3f3f3f3f;
const int N = 1e3 + 5;
int a[N];
int n,h;
bool cmp(int a, int b) {
    return a > b;
}
int main() {
    cin >> n >> h;
    for(int i = 1; i <= n; i++) read(a[i]);
    for(int i = 1; i <= n; i++) {
        vector<int> v;
        for(int j = 1; j <= i; j++) v.push_back(a[j]);
        sort(v.begin(), v.end(), cmp);
        int now = 0;
        bool ok = true;
        for(int k = 0; k < (v.size() & 1 ? v.size() - 1 : v.size()); k += 2) {
            now += v[k];
            if(now > h) {
                ok = false; break;
            }
        }
        if(v.size() & 1) {
            now += v[v.size() - 1];
            if(now > h) ok = false;
        }
        if(!ok) {
            cout << i - 1; return 0;
        }
    }
    cout << n;
    return 0;
}

C. Ramesses and Corner Inversion

可以观察这个operation,我们可以发现每次operation要么对于任意的行列,0和1的数量都不改变,要么0的数量减2,1的数量加2,要么0的数量加2,1的数量减2,列也同理。所以只需要枚举每行每列的0和1的数量判断即可

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

const int INF = 0x3f3f3f3f;
const int N = 505 + 5;
int a[N][N];
int b[N][N];
int tot_1[2],tot_0[2];
int n,m;
int main() {
    read(n); read(m);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++)
            read(a[i][j]);
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            read(b[i][j]);

    for(int i = 1; i <= n; i++) {
        mem(tot_1, 0); mem(tot_0, 0);
        for(int j = 1; j <= m; j++) {
            if(a[i][j] == 0) tot_0[0]++;
            if(a[i][j] == 1) tot_1[0]++;
            if(b[i][j] == 0) tot_0[1]++;
            if(b[i][j] == 1) tot_1[1]++;
        }
        if(tot_0[0] + tot_1[0] != tot_0[1] + tot_1[1]) {
            cout << "No"; return 0;
        }
        if(abs(tot_0[0] - tot_0[1]) % 2 == 1 || abs(tot_1[0] - tot_1[1]) % 2 == 1) {
            cout << "No"; return 0;
        }
    }
    for(int i = 1; i <= m; i++) {
        mem(tot_1, 0); mem(tot_0, 0);
        for(int j = 1; j <= n; j++) {
            if(a[j][i] == 0) tot_0[0]++;
            if(a[j][i] == 1) tot_1[0]++;
            if(b[j][i] == 0) tot_0[1]++;
            if(b[j][i] == 1) tot_1[1]++;
        }
        if(tot_0[0] + tot_1[0] != tot_0[1] + tot_1[1]) {
            cout << "No"; return 0;
        }
        if(abs(tot_0[0] - tot_0[1]) % 2 == 1 || abs(tot_1[0] - tot_1[1]) % 2 == 1) {
            cout << "No"; return 0;
        }
    }
    cout << "Yes";
    return 0;
}

D. Frets On Fire

首先先将数字排序,很显然这是不影响结果的。其次,我们求出相邻两个之间的差分dd,我们可以发现 当 $d > (r - l + 1) (rl+1)很显然 这个差分的贡献为(r - l + 1),否则则为它们之间的差分d$ (画画图就能明白)
然后我们将所有差分排序,对于每次的询问二分答案即可。时间复杂度$O((n + q)logn) $

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

const int INF = (ll) 1e18;
const int N = 1e5 + 5;
ll n,a[N],d[N],sum[N];
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        read(a[i]);
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i < n; i++) {
        d[i] = a[i + 1] - a[i];
    }
    sort(d + 1, d + n);
    for(int i = 1; i < n; i++) {
        sum[i] = sum[i - 1] + d[i];
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++) {
        ll l,r;
        read(l); read(r);
        ll del = r - l + 1;
        int p = upper_bound(d + 1, d + n, del - 1) - d;
        ll ans = sum[p - 1] + del * (n - p) + del;
        cout << ans << " ";
    }
    return 0;
}

E. Pavel and Triangles

先考虑什么情况能组成三角形,要么是两个相同的和一个不同的,要么是三个相同的。
那么我们考虑贪心,考虑到第2i2^i长度的木棍时,我们尽可能的用22取,和之前剩下来的配,然后之后再考虑用33取。很显然是对的(假设优先用33取,会使得三角形数量更小。)

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
#define sqr(x) ((x)*(x))
#define ls (k << 1)
#define rs (k << 1 | 1)
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

const int INF = 0x3f3f3f3f;
const int N = 3e5 + 5;
ll a[N];
int n;
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        read(a[i]);
    ll res = 0;
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ll tri = min(res, a[i] / 2);
        ans += tri; a[i] -= tri * 2; res -= tri;
        ans += a[i] / 3;
        a[i] %= 3;
        res += a[i];
    }
    cout << ans;
    return 0;
}