首页 > 其他 > 详细

Wannafly挑战赛1,2

时间:2017-11-12 23:56:35      阅读:452      评论:0      收藏:0      [点我收藏+]

做了好久了,今天大佬讲题,好厉害,弱鸡只会几道水题。

 

Treepath

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

奇数层到奇数层,偶数层到偶数层。

 

Xorto

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

 

异或题好厉害,问题变成四个点的异或值为0。

厉害的位置是他的遍历方式O(n*nlogn)

左区间+1个元素,将产生一些新的异或值,有区间探测。(枚举的起点,不重复不遗漏)

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 1e3+5;
int a[maxn];
int sets[3276800];
 
int main()
{
    //freopen("in.txt","r",stdin);
 
    int n;
    cin>>n;
 
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
 
    long long cnt = 0;
    for(int i = 1; i <= n; i++) {
        int s = 0;
        for(int j = i; j <=n; j++) {
            s^=a[j];
            cnt+=sets[s];
        }
        s = 0;
        for(int j = i; j >= 1; j--) {
            s^=a[j];
            sets[s]++;
        }
    }
    printf("%lld\n",cnt);
 
 
    return 0;
}

 

MMSet2

给定一棵n个节点的树,点编号为1…n。
Q次询问,每次询问给定一个点集S,令技术分享
你需要求出技术分享
其中dist(u,v)表示树上路径(u,v)的边数。

 

答案就是 (点集的直径+1)/2,理由想一想就好,代码待填,嘻嘻~~~

 

Color

给一个没有重边的二分图, 要求给边染色. 有公共点的边不能同色. 问最少用多少种颜色, 并任意构造一组方案.
 
答案是:度数的最大值。
分析:肯定他是理论的下界,那么怎么才能知道他是理论的上界呢?嘻嘻。跳过,
然后染色。
 
Cut
给你一个长度为n的序列,你每次可以将一个序列分割成两个连续的的子序列,
分割的代价为原序列的总和。
现在允许你在初始时将序列重新排列一次。
问分割成n个长度为1的序列的最大总代价是多少?
 
哈夫曼
 
Travel

精灵王国有N座美丽的城市,它们以一个环形排列在Bzeroth的大陆上。其中第i座城市到第i+1座城市花费的时间为d[i]。特别地,第N座城市到第1座城市花费的时间为d[N]。这些道路都是双向的。

另外,精灵们在数千年的时间里建造了M座传送门,第i座传送门连接了城市u[i]与城市v[i],并且需要花费w[i]的时间通过(可能有两座传送门连接了同一对城市,也有可能一座传送门连接了相同的两座城市)。这些传送门都是双向的。

小S是精灵王国交通部部长,她的职责是为精灵女王设计每年的巡查路线。每次陛下会从某一个城市到达另一个城市,沿路调查每个城市的治理情况,她需要找出一条用时最短的路线。

 

枚举特殊点。

 

Wannafly挑战赛1,2

原文:http://www.cnblogs.com/TreeDream/p/7823475.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!