Codeforces Round #498 (Div. 3) 简要题解

[比赛链接]

[题解]

Problem A. Adjacent Replacements

[算法]

将序列中的所有偶数替换为奇数即可

时间复杂度： O(N)

[代码]

#include<bits/stdc++.h>

using namespace std;

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

int main()

{

        int n;

        read(n);

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

        {

                int x;

                read(x);

                if (x & ) printf("%d ",x);

                else printf("%d ",x - );

        }

        printf("\n");

        return ;

}

Problem B. Polycarp's Practice

[算法]

要求k天的和最大化，我们不妨将这些数加入一个堆中，取出前k大值

构造一组合法的解即可

时间复杂度： O(NlogN)

[代码]

#include<bits/stdc++.h>

using namespace std;

#define MAXN 2010

int ans[MAXN];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

int main()

{

        int n , k , t =  , value = ;

        static priority_queue< pair<int,int> > q;

        read(n); read(k);

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

        {

                int x;

                read(x);

                q.push(make_pair(x,i));

        }

        while (t < k)

        {

                value += q.top().first;

                ans[++t] = q.top().second;

                q.pop();

        }

        sort(ans + ,ans + k + );

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

        for (int i = ; i <= k - ; i++) printf("%d ",ans[i] - ans[i - ]);

        printf("%d\n",n - ans[k - ]);

        return ;

}

Problem C. Three Parts of the Array

[算法]

用Two Pointers扫描求出答案即可

也可以通过std :: set等数据结构求解

时间复杂度： O(N)

[代码]

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2e6 + ;

long long a[MAXN];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

int main()

{

        long long n;

        read(n);

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

        long long l =  , r = n;

        long long s1 =  , s2 =  , ans = ;

        while (l <= r)

        {

                if (s1 < s2)

                {

                        s1 += a[l++];

                        if (s1 == s2) ans = s1;

                }    else if (s2 < s1)

                {

                        s2 += a[r--];

                        if (s1 == s2) ans = s1;

                } else

                {

                        if (l == r) break;

                        s1 += a[l++];

                        s2 += a[r--];

                        if (s1 == s2) ans = s1;

                }

        }

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

        return ;

}

Problem D. Two Strings Swaps

[算法]

枚举字符串的前[n/2]个字符 ([x]表示向下取整) ,

如果字符串a和字符串b的第i个字符和第(n - i + 1)个字符共有4个不同的字符，显然对答案产生2的贡献

如果有3个不同字符，当字符串a的第i个字符和第(n - i + 1)个字符相同，则对答案产生2的贡献，否则对答案产生1的贡献

如果有2个不同字符，如果第a的第i个字符出现次数不为2 ，则对答案产生1的贡献

当字符串长度为奇数时，若字符串a的第(n + 1) / 2和字符串b的第(n + 1) / 2个字符不相等，则对答案产生1的贡献

[代码]

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + ;

int n , ans;

char a[MAXN],b[MAXN];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

int main()

{

        scanf("%d",&n);

        scanf("%s%s",a + ,b + );

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

        {

                map< char,int > mp;

                mp.clear();

                mp[a[i]]++;

                mp[a[n - i + ]]++;

                mp[b[i]]++;

                mp[b[n - i + ]]++;

                if ((int)mp.size() == ) ans += ;

                if ((int)mp.size() == )

                {

                        if (a[i] == a[n - i + ]) ans += ;

                        else ans++;

                }

                if ((int)mp.size() == )

                {

                        if (mp[a[i]] != )

                            ans++;

                }

        }

        if ((n & ) && a[n /  + ] != b[n /  + ]) ans++;

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

        return ;

}

Problem E. Military Problem

[算法]

不妨先求出整棵树的DFS序，记为Dfn[]

然后，我们用Pos[i]表示DFS序为i的节点

对于询问(ui , ki) , 显然，答案为Pos[Dfn[ui] - 1 + k]

时间复杂度： O(N)

[代码]

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + ;

int n , q , timer;

int size[MAXN],ans[MAXN],depth[MAXN],dfn[MAXN];

vector< int > G[MAXN];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

inline void dfs(int u)

{

        size[u] = ;

        dfn[u] = ++timer;

        ans[timer] = u;

        for (unsigned i = ; i < G[u].size(); i++)

        {

                depth[G[u][i]] = depth[u] + ;

                dfs(G[u][i]);

                size[u] += size[G[u][i]];

        }

}

int main()

{

        read(n); read(q);

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

        {

                int x;

                read(x);

                G[x].push_back(i);

        }

        dfs();

        while (q--)

        {

                int u , k;

                read(u); read(k);

                if (size[u] < k)

                {

                        printf("-1\n");

                        continue;

                }

                printf("%d\n",ans[dfn[u] + k - ]);

        }

        return ;

}

Problem F. Xor Paths

[算法]

显然，所有的路径长度都为(n + m - 1)

考虑使用Meet-In-The-Middle( 中途相遇法）

第一遍DFS求出前(n + m - 1)步，每个位置上出现的异或和情况数

第二遍DFS求出后(n + m) / 2步，根据第一遍DFS求出的情况数统计答案

时间复杂度： O(2 ^ ((n + m - 2) / 2) * (n + m - 2) / 2)

[代码]

#include<bits/stdc++.h>

using namespace std;

#define MAXN 25

#define MAXS 100005

int n , m;

long long a[MAXN][MAXN];

long long val , ans = ;

map< long long,int > cnt[MAXN][MAXN];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

inline bool valid(int x,int y)

{

        return x >=  && x <= n && y >=  && y <= m;

}

inline void dfs1(int x,int y,int step,long long k)

{

        if (step == (n + m - ) / )

        {

                cnt[x][y][k]++;

                return;

        }

        if (valid(x + ,y)) dfs1(x + ,y,step + ,k ^ a[x + ][y]);

        if (valid(x,y + )) dfs1(x,y + ,step + ,k ^ a[x][y + ]);

}

inline void dfs2(int x,int y,int step,long long k)

{

        if (step == (n + m) / )

        {

                if (valid(x,y - )) ans += cnt[x][y - ][val ^ k];

                if (valid(x - ,y)) ans += cnt[x - ][y][val ^ k];

                return;

        }

        if (valid(x - ,y)) dfs2(x - ,y,step + ,k ^ a[x - ][y]);

        if (valid(x,y - )) dfs2(x,y - ,step + ,k ^ a[x][y - ]);

}

int main()

{

        read(n); read(m); read(val);

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

        {

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

                {

                        read(a[i][j]);

                }

        }

        if (n ==  && m == )

        {

                if (a[][] == val) printf("1\n");

                else printf("0\n");

                return ;

        }

        dfs1(,,,a[][]);

        dfs2(n,m,,a[n][m]);

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

        return ;

}

巴特西

Codeforces Round #498 (Div. 3) 简要题解

最新文章

热门文章