Wannafly挑战赛1 A dfs B 思维,枚举

题意：给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。

tags：类似于树 dp， dfs搜一下，记录下每个子树上离子树根距离为奇数和偶数的数量。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi  first
#define se  second
#define PII  pair<ll , ll >
typedef long long ll;
const int N = 100005;

int n, x, y;
vector< int > G[N];
PII dfs(int u, int fa)
{
    if(G[u].size()==1) return MP(0,0);
    PII  ans=MP(0,0), tmp;
    for(int i=0, to; to=G[u][i], i<G[u].size(); ++i)
        if(to!=fa)
    {
        tmp = dfs(to, u);
        ans.fi += tmp.se+1;
        ans.se += tmp.fi;
    }
    return ans;
}
int main()
{
    scanf("%d", &n);
    rep(i,1,n-1)
    {
        scanf("%d%d", &x, &y);
        G[x].PB(y);   G[y].PB(x);
    }
    PII  ans = dfs(1, 0);
    ++ans.se;
    printf("%lld
", ans.fi*(ans.fi-1)/2 + ans.se*(ans.se-1)/2 );

    return 0;
}

View Code

B Xorto

题意：给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。

tags：比赛的时候给水过去的。。数据好像有点水

首先肯定预处理出前缀，然后维护一个权值数组，O(n^2) 枚举区间。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi  first
#define se  second
typedef long long ll;
const int N = 100005, M = 2000005;

int n, s[N];
ll  ans, cnt[M];
int main()
{
    scanf("%d", &n);
    int ai;
    rep(i,1,n)
    {
        scanf("%d", &ai);
        s[i] = s[i-1]^ai;
    }
    rep(i,1,n)
        rep(j,i,n)
            ++cnt[s[j]^s[i-1]];
    rep(i,1,n)
    {
        rep(j,i,n)
            --cnt[s[j]^s[i-1]];
        rep(j,1,i)
            ans += cnt[s[i]^s[j-1]];
    }
    printf("%lld
", ans);

    return 0;
}

View Code