codeforces round #424 div2

A 暴力查询，分三段查就可以了

#include<bits/stdc++.h>

using namespace std;

const int N = ;

int n, pos;

int a[N];

int main()

{

    scanf("%d", &n);

    for(int i = ; i <= n; ++i) scanf("%d", &a[i]);

    pos = -;

    for(int i = ; i <= n; ++i) if(a[i] - a[i - ] <= )

    {

        pos = i;

        break;

    }

    if(pos == -)

    {

        puts("YES");

        return ;

    }

    for(int i = pos; i <= n; ++i)

    {

        pos = ;

        if(a[i] - a[i - ] > )

        {

            puts("NO");

            return ;

        }

        else if(a[i] - a[i - ] < )

        {

            pos = i;

            break;

        }

    }

    if(!pos)

    {

        puts("YES");

        return ;

    }

    for(int i = pos; i <= n; ++i)

    {

        if(a[i] - a[i - ] >= )

        {

            puts("NO");

            return ;

        }

    }

    puts("YES");

    return ;

}

B 开个数组映射一下

#include<bits/stdc++.h>

using namespace std;

const int N = ;

int n;

char s1[N], s2[N], s[N];

int Map[N];

int main()

{

    scanf("%s%s%s", s1 + , s2 + , s + );

    n = strlen(s1 + );

    for(int i = ; i <= n; ++i) Map[s1[i] - 'a'] = s2[i] - 'a';

    for(int i = ; i <= strlen(s + ); ++i)

    {

        if(isdigit(s[i]))

            printf("%c", s[i]);

        if(islower(s[i]))

            printf("%c", (char)(Map[s[i] - 'a'] + 'a'));

        if(isupper(s[i]))

            printf("%c", (char)(Map[s[i] - 'A'] + 'A'));

    }

    return ;

}

C 没想出来，这种题目发现用b在a上算不行就应该转换用a在b上算。统计每个b对于每个a产生的初始值，如果一个初始值出现了k次，那么就是可以的。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ;

ll tot;

int n, k, ans;

ll a[N];

map<ll, int> mp;

vector<ll> v;

inline int read()

{

    int x = , f = ; char c = getchar();

    while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }

    while(c >= '' && c <= '') { x = x *  + c - ''; c = getchar(); }

    return x * f;

}

int main()

{

    scanf("%d%d", &n, &k);

    for(int i = ; i <= n; ++i)

    {

        a[i] = read() + a[i - ];

        v.push_back(a[i]);

    }

    sort(v.begin(), v.end());

    v.erase(unique(v.begin(), v.end()), v.end());

    for(register int i = ; i <= k; ++i)

    {

        int x;

        x = read();

        for(int j = ; j < v.size(); ++j)

            ++mp[x - v[j]];

    }

    for(map<ll, int> :: iterator it = mp.begin(); it != mp.end(); ++it)

        ans += (it -> second == k);

    printf("%d\n", ans);

    return ;

}

D dp，dp[i][j]表示第i个人选到第j个钥匙，dp[i][j]=min(dp[i][j-1],max(dp[i-1][j-1],abs(a[i]-b[j])+(b[j]-p))就好了

看错题目+C题这道题1小时35分才出来。。。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ;

int n, k, p;

int a[N], b[N];

ll dp[N][N];

int main()

{

    scanf("%d%d%d", &n, &k, &p);

    for(int i = ; i <= n; ++i) scanf("%d", &a[i]);

    for(int i = ; i <= k; ++i) scanf("%d", &b[i]);

    sort(a + , a + n + );

    sort(b + , b + k + );

    for(int i = ; i <= n; ++i) dp[i][]= 1e16;

    for(int i = ; i <= n; ++i)

        for(int j = ; j <= k; ++j)

            dp[i][j] = min(dp[i][j - ], max(dp[i - ][j - ], (ll)abs(a[i] - b[j]) + (ll)abs(b[j] - p)));

    ll ans = 1e16;

    for(int i = n; i <= k; ++i)

        ans = min(ans, dp[n][i]);

    printf("%lld\n", ans);

    return ;

}

E 平衡树练习题其实很简单就能搞定。我们发现如果选了一轮序列就会恢复原来的样子，只是删除了一些数。那么我们开set记录每个数出现的位置，从最小的数开始枚举，如果没到结尾加上上次到这次的距离，否则回到开头，因为每个数只删除一次，我们用size记录需要加上的答案，每删除一次size减1，到了一轮结束加上size。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ;

int n, sz;

ll ans;

int a[N], tree[N];

set<int> s[N];

int main()

{

    scanf("%d", &n);

    for(int i = ; i <= n; ++i)

    {

        scanf("%d", &a[i]);

        s[a[i]].insert(i);

    }

    sort(a + , a + n + );

    int last = ;

    ans = n;

    sz = n;

    for(int i = ; i <= n; ++i)

    {

        set<int> :: iterator it = s[a[i]].lower_bound(last);

        if(it == s[a[i]].end())

        {

            ans += sz;

            it = s[a[i]].begin();

        }

        last = *it;

        --sz;

        s[a[i]].erase(it);

    }

    printf("%lld\n", ans);

    return ;

}

巴特西

codeforces round #424 div2

最新文章

热门文章