Codeforces Round #690 (Div. 3)

Codeforces Round #690 (Div. 3)

A. Favorite Sequence

Solution

按要求输出即可

#include 
#include 
using namespace std;

const int maxn = 333;

int a[maxn], n;

int main()
{
    int t; cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 0; i < n; ++i) cin >> a[i];
        vector ans;
        int l = 0, r = n - 1;
        while(l <= r) {
            if(l == r) ans.push_back(a[l]);
            else {
                ans.push_back(a[l]);
                ans.push_back(a[r]);
            }
            l++;
            r--;
        }
        for(auto k:ans) cout << k << " ";
        cout << endl;
    }
    return 0;
}

B. Last Year's Substring

Solution

因为只能删一次，所以可能情况有三种2020位于开头，2020位于结尾，2020拆分成两部分位于开头和结尾，分别考虑即可。

#include 
#include 
#include 
using namespace std;

const int maxn = 222;

char str[maxn];
int n;

int main()
{
    int t; cin >> t;
    while(t--) {
        cin >> n;
        cin >> str;
        bool fl = false;
        if(str[0] == '2' && str[1] == '0' && str[2] == '2' && str[3] == '0') {
            fl = true;
        }
        else if(str[n - 4] == '2' && str[n - 3] == '0' && str[n - 2] == '2' && str[n - 1] == '0') {
            fl = true;
        }
        else if(str[0] == '2' && str[n - 3] == '0' && str[n - 2] == '2' && str[n - 1] == '0') {
            fl = true;
        }
        else if(str[0] == '2' && str[1] == '0' && str[n - 2] == '2' && str[n - 1] == '0') {
            fl = true;
        }
        else if(str[0] == '2' && str[1] == '0' && str[2] == '2' && str[n - 1] == '0') {
            fl = true;
        }
        cout << (fl ? "YES" : "NO") << endl;
    }
    return 0;
}

C. Unique Number

Solution

DFS搜索满足条件的最小数字即可。

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long ll;

const ll INF = 111111111111;

int vis[13], ans[13];
ll mn;

void dfs(int x, int ad)
{
    if(x == 0) {
        ll k = 0;
        for(int i = 0; i < ad; ++i) {
            k = k * 10 + ans[i];
        }
        mn = min(mn, k);
        return;
    }
    for(int i = 0; i <= 9; ++i) {
        if(ad >= 2 && i <= ans[ad - 1]) continue;
        if(i <= x && vis[i] == 0) {
            vis[i] = 1;
            ans[ad] = i;
            dfs(x - i, ad + 1);
            vis[i] = 0;
        }
    }
    return;
}

int main()
{
    int t; cin >> t;
    while(t--) {
        int x; cin >> x;
        memset(vis, 0, sizeof(vis));
        mn = INF;
        for(int i = 1; i <= 9 && i <= x; ++i) {
            vis[i] = 1;
            ans[0] = i;
            dfs(x - i, 1);
            vis[i] = 0;
        }
        cout << (mn == INF ? -1 : mn) << endl;
    }
    return 0;
}

D. Add to Neighbour and Remove

Solution

将题意转换，即为将原序列分成若干连续的段，使得每段和相同，求满足条件的情况下，最多能分多少段（段数越多，合并操作越少）。DFS即可。

#include 
#include 
#include 
#include 
using namespace std;

const int maxn = 3333;

int a[maxn], n, mx;

void dfs(int la, int sum, int count)
{
    if(la >= n) {
        mx = max(mx, count);
        return;
    }
    int add = 0;
    for(int i = la; i < n; ++i) {
        add += a[i];
        if(add > sum) return;
        if(add == sum) dfs(i + 1, add, count + 1);
    }
    return;
}

int main()
{
    int t; cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 0; i < n; ++i) cin >> a[i];
        mx = 1;
        int sum = 0;
        for(int i = 0; i < n; ++i) {
            sum += a[i];
            dfs(i + 1, sum, 1);
        }
        cout << n - mx << endl;
    }
    return 0;
}

E. Close Tuples

Solution

题意为，寻找所有极差小于\(k\)的长度为\(m\)的序列，输出个数。

因为限制条件为极差，所以我们可以从序列的最大最小值入手，对于每个最小值而言，可行最大值为\([v_{min},k+v_{min}]\)，位于该区间的所有数都可以与最小值\(v_{min}\)作为一个极差来确定一组序列（序列中其他元素值均介于\([v_{min},v_{max}]\)），因此只需要枚举最小值，计算可行最大值的数量\(a\)，即可计算出当前情况下的序列个数（\(C_{a}^{m}\)），取和即可。

不清楚可以参考LeetCode1498.满足条件的子序列数目，两题基本相同。

#include 
#include 
#include 
using namespace std;

typedef long long ll;

const int maxn = 211111;
const ll mod = 1e9 + 7;

int a[maxn], n, m, k;
ll sp[maxn];

ll qpow(ll a, ll b)
{
    ll ans = 1;
    while(b) {
        if(b & 1) {
            ans = (ans * a) % mod;
        }
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

ll C(int n, int m)
{
    if(m > n) return 0;
    ll M = qpow(sp[m], mod - 2);
    ll NM = qpow(sp[n - m], mod - 2);
    return (sp[n] * M % mod) * NM % mod;
}

int main()
{
    sp[0] = 1;
    for(int i = 1; i <= 200000; ++i) {
        sp[i] = sp[i - 1] * i % mod;
    }
    int t; cin >> t;
    while(t--) {
        cin >> n >> m >> k;
        for(int i = 0; i < n; ++i) cin >> a[i];
        sort(a, a + n);
        ll ans = 0;
        for(int i = 0; i + m <= n; ++i) {
            int ad = int(upper_bound(a, a + n, a[i] + k) - a);
            ad = ad - i - 1;
            ans = (ans + C(ad, m - 1)) % mod;
        }
        cout << ans << endl;
    }
    return 0;
}

F. The Treasure of The Segments

Solution

题意说白了就是计算一个区间能和多少区间相交，对\(n\)个区间计算最大值。

二分计数即可。

#include 
#include 
#include 
using namespace std;

const int maxn = 211111;

pair a[maxn];
int n;
vector l, r;

int main()
{
    int t; cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 0; i < n; ++i) {
            cin >> a[i].first >> a[i].second;
            l.push_back(a[i].first);
            r.push_back(a[i].second);
        }
        sort(l.begin(), l.end());
        sort(r.begin(), r.end());
        int ans = n;
        for(int i = 0; i < n; ++i) {
            int cl = int(lower_bound(r.begin(), r.end(), a[i].first) - r.begin()) - 1;
            int cr = int(upper_bound(l.begin(), l.end(), a[i].second) - l.begin());
            ans = min(ans, cl + n - cr + 1);
            //cout << a[i].first << "-" << a[i].second << ":" << cl << " " << cr << endl;
        }
        cout << ans << endl;
        l.clear();
        r.clear();
    }
    return 0;
}