https://www.hackerrank.com/contests/hourrank-19/challenges
第一题略。
第二题是nim博弈，问删掉一个区间的石子，使得先手败的方案有几种，明显维护前缀异或，然后一直加方案数就好了
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
#define MP make_pair
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define PB push_back
#define mst(a,b) memset((a),(b),sizeof(a))
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> Pii;
typedef vector<int> Vi;
typedef vector<Pii> Vii;
const int inf = 0x3f3f3f3f;
const LL INF = (1uLL << ) - ;
const LL mod = ;
const int N = 5e4 + ;
const double Pi = acos(-1.0);
const int maxn = 5e5 + ;
int num[maxn];
map<int,int>cnt;
int main() {
#ifdef local
freopen("in", "r", stdin);
//freopen("w","w",stdout);
#endif
ios::sync_with_stdio();
cin.tie();
int n;
cin>>n;
int s = ;
int res = ;
LL ans = ;
cnt[]++;
rep(i,n)cin>>num[i],res^=num[i];
rep(i,n){
s ^= num[i];
ans += cnt[s^res];
cnt[s]++;
}
cout<<ans<<endl;
}
第三题Maximal Tree Diameter
题意：
选择一条边把这棵树分开，然后任选两个顶点再把这两棵树合并，使得新合成的树直径最长。
做法：
我们先树dp求出dp[u][(0,2)]分别表示这个点往下的三个最长次长第三长的路径，然后再求fu[u]表示从u这个点出发到达往父亲那条路径走的最长路径。。这里很像hdu2196的一个操作，然后我们在第一次dp时，顺便求出subtree[u]表示，u的子树的最长直径(不一定包括u),有了上面的，我们就可以维护答案了，当跑到一个点u，它的一个儿子是v时，当我们选择拆这条边我们怎么能取得最优解呢，明显，我们需要subtree[v] + dp[v][0] + max(dp[v][1],fu[v]).但是这条边很有可能是就是u的最长路径，或者次长，或者其他，所以我们才需要更新其他的一些信息。
比赛的时候没考虑到第三长的边= = 感觉很亏。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
#define MP make_pair
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define PB push_back
#define mst(a,b) memset((a),(b),sizeof(a))
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> Pii;
typedef vector<int> Vi;
typedef vector<Pii> Vii;
const int inf = 0x3f3f3f3f;
const LL INF = (1uLL << ) - ;
const LL mod = ;
const int N = 5e4 + ;
const double Pi = acos(-1.0);
const int maxn = 5e5 + ;
int dp[maxn][];
Vi edge[maxn];
int dostree[maxn];
int fu[maxn];
void um(int &a,int b){
if(a < b)a = b;
}
void sfs1(int u, int fa) {
dostree[u] = dp[u][] = dp[u][] = dp[u][] = ;
for(int v : edge[u]) {
if(v == fa)continue;
sfs1(v, u);
um(dostree[u],dostree[v]);
if(dp[v][] + >= dp[u][]){
dp[u][] = dp[u][];
dp[u][] = dp[u][];
dp[u][] = dp[v][] + ;
}else if(dp[v][] + >= dp[u][]){
dp[u][] = dp[u][];
dp[u][] = dp[v][] + ;
}else if(dp[v][] + >= dp[u][]){
dp[u][] = dp[v][] + ;
}
}
um(dostree[u],dp[u][] + dp[u][]);
}
void sfs2(int u,int fa){
for(int v : edge[u]){
if(v == fa)continue;
fu[v] = max(fu[u],dp[v][] + == dp[u][]? dp[u][] : dp[u][]) + ;
sfs2(v,u);
}
}
int res = ;
void sfs3(int u,int fa){
for(int v : edge[u]){
if(v == fa)continue;
if(dp[v][] + == dp[u][]){
um(res,dostree[v] + + dp[u][] + dp[u][]);
um(res,dostree[v] + + dp[u][] + fu[u]);
}else if(dp[v][] + == dp[u][]){
um(res,dostree[v] + + dp[u][] + dp[u][]);
um(res,dostree[v] + + dp[u][] + fu[u]);
}else {
um(res,dostree[v] + + dp[u][] + dp[u][]);
um(res,dostree[v] + + dp[u][] + fu[u]);
}
sfs3(v,u);
}
}
int main() {
#ifdef local
freopen("in", "r", stdin);
//freopen("w","w",stdout);
#endif
ios::sync_with_stdio();
cin.tie();
int n;
cin >> n;
rep(i, n - ) {
int u, v;
cin >> u >> v;
edge[u].PB(v);
edge[v].PB(u);
}
sfs1(,);
sfs2(,);
sfs3(,);
cout<<res<<endl;
}