7月28日 Codeforces Round #498
题目链接:http://codeforces.com/contest/1006

A – Adjacent Replacements & B – Polycarp’s Practice

比较水呢。。不说

C- Three Parts of the Array

思路:
也很水呢。。。就是一个双指针,记录两边的和就好了。其余的看代码。。

代码:

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int n, l, r;
LL lsum, rsum, a[1000005], ans;

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
    l=1, r=n;
    while(l<=r)
    {
        if(lsum==rsum) ans=lsum;
        if(lsum<=rsum) lsum+=a[l], l++;
        else rsum+=a[r], r--;
    }
    if(lsum==rsum) ans=lsum;
    printf("%lld\n", ans);
}

D – Two Strings Swaps

思路:
毒瘤,卡了超级久。。。首先思路很简单,因为$a_i$, $a_{n+1-i}$, $b_i$, $b_{n+1-i}$直间能够任意交换,所以我们可以把这4个元素看成一块,计算出要改几个字符。

关于答案的的计算方法很毒瘤,就是分类讨论!!有很多情况,也有很多细节,在讨论过程中思路一定要清晰,千万不要漏情况了。。我就漏了QWQ

代码:

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int n, ans;
char a[100005], b[100005];
map<char, int> mp;

int main()
{
    scanf("%d", &n);
    scanf("%s", a+1);
    scanf("%s", b+1);
    for(int i=1; i<=(n+1)/2; i++)
    {
        if(i+i==n+1)
        {
            if(a[i]!=b[i]) ans++;
            continue;
        }
        mp.clear();
        mp[a[i]]++, mp[a[n+1-i]]++;
        mp[b[i]]++, mp[b[n+1-i]]++;
        if(mp.size()==2 && mp[a[i]]!=2) ans++;
        if(mp.size()==3)
        {
            if(a[i]==a[n+1-i]) ans+=2;
            else ans++;
        }
        if(mp.size()==4) ans+=2;
    }
    printf("%d\n", ans);
}

E – Military Problem

思路:
首先一棵子树在DFS序上是连续的,我们可以利用这个性质,然后这道题就是水题了。我们只要一遍DFS处理处子树大小和整棵树的DFS序,如果$k$大于了$x$的子树大小,那么答案就是-1,否则就是DFS序在$x$后$k-1$个对应的节点。

代码:

#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;

int n, q, cnt, id, siz[MAXN],ver[MAXN], dfn[MAXN], head[MAXN];

vector<int> g[MAXN];

void dfs(int x, int fa)
{
    siz[x]=1;
    dfn[x]=++id; ver[id]=x;
    for(int i=0; i<g[x].size(); i++)
    {
        int to=g[x][i];
        if(to==fa) continue;
        dfs(to, x);
        siz[x]+=siz[to];
    }
}

int main()
{
    scanf("%d%d", &n, &q);
    for(int i=2; i<=n; i++)
    {
        int temp;
        scanf("%d", &temp);
        g[i].push_back(temp);
        g[temp].push_back(i);
    }
    dfs(1, 0);
    for(int i=1; i<=q; i++)
    {
        int x, k;
        scanf("%d%d", &x, &k);
        if(k>siz[x]) printf("-1\n");
        else printf("%d\n", ver[dfn[x]+k-1]);
    }
}

F – Xor-Paths

思路:
看范围就知道是双向爆搜。。。然后就直接码就好了,然后就是中间相交处理答案时有一些细节要注意。中间的那一条是计算过两次的,所以在更新$cnt$数组是还要异或一下那个数字。

代码:

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int n, m;
LL k, ans, a[35][35];
map<LL, LL> cnt[35][35];

void dfs1(int x, int y, LL num)
{

    if(x+y==(n+m)/2+1) {cnt[x][y][num^a[x][y]]++; return;}
    if(x<n) dfs1(x+1, y, num^a[x+1][y]);
    if(y<m) dfs1(x, y+1, num^a[x][y+1]);
}

void dfs2(int x, int y, LL num)
{

    if(x+y==(n+m)/2+1) {ans+=cnt[x][y][num^k]; return;}
    if(x>1) dfs2(x-1, y, num^a[x-1][y]);
    if(y>1) dfs2(x, y-1, num^a[x][y-1]);
}

int main()
{
    scanf("%d%d%lld", &n, &m, &k);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) scanf("%lld", &a[i][j]);
    dfs1(1, 1, a[1][1]);
    dfs2(n, m, a[n][m]);
    printf("%lld\n", ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注