T1

对于&来说,还是比较容易处理的。

贪心思路,对于二进制由高到低每一位,如果存在两个以上的数的这一位是1就选,没有的话就把当前一位的值删掉去看下一位,当选到这么一个位置后,在这一位是1的所有数的后面部分做同样的事情。

对于xor,就是trie树,在存trie树的时候在树上尽量跑这个数的反码,最后取max即可。

 

对于or来说,对于一个数,我们看它0的那一位是否有1,用bit去存它的最大反码,再利用桶判断这个反码是否存在。

 

可能说的不是很清楚,若有疑问,欢迎访问本人。

T1

记忆化搜索,不管对谁我们如果能从接下来的两个状态中找到可令另一个人走到绝路的状态我们就是必胜的。

对于一般情况:

上面这行代码就是,如果接下来两个状态另一个人都必胜,当前状态就是必负,否则必胜。

可以前缀和预处理出每个点可以往哪走,以及这个点是否无路可走,即可轻松AC

不开读入优化见祖宗

T2

找规律打表。。

以下内容抛开第一层

首先我们可以发现第i层共有6*(i-1)个数

对于每一层都有6个数只与上一层的一个数相邻

并且这6个数的间距为层数-1

对于新的一层,我们从第一个位置开始枚举填数,并在上一层用一个指针来找与它相邻的1个/2个数

再用题中的要求找出一个合理的数填入即可填充这个10000的图。

T3

算出每个前缀和sum[i]%k后存在桶里,如果之前有过sum[j]%k=sum[i]%k

那么j到i就是一个合法的区间

所以对于sum[i] 每次

O(n)复杂度求解即可

 

T1

斐波那契数列…f[1]=2,f[2]=3 往下递推即可

如果看不出来可开一个二维数组,f[i][j]表示第i个放与不放共有多少种情况

道理和斐波那契一样的

T2

dfs,首先dfs(i)返回值表示i及子树都知道这个消息需要的时间

双向存边,枚举每个点为根,对于叶子节点可以直接return 1;

对于一个有很多儿子的点,把他们儿子dfs返回值从大到小排序,在这其中对于返回值+位置getmax,就是这个点及子树需要的时间。

在整个过程中,我们可以看出一颗同样的子树,可能会被搜很多次,所以还可以记忆化搜索进行优化。

DFS代码:

T3

二分ans,把整个图更新为边权为

p[i]-ans*t[i]

的图,SPFA跑最长路,如果dis[n]>0说明速度还可以再大一些,如果存在正环,一定存在从1到n的正权路,此时check()return true;

 

 

 

 

 

 

 

 

 

若有不懂,欢迎访问本人

 

原题依旧保密…

T1

设f[1]=p,后手动递推可以清楚的看出两个斐波那契数列。

f[0]=1;

f[1]=1*p;

f[2]=1*p+1;

f[3]=2*p+1;

f[3]=3*p+2;

f[4]=5*p+3……

所以可得出f[i]=fib[i]*p+fib[i-1];(fib是fib[1]=1,fib[2]=1的斐波那契数列)

然后预处理fib,O(1)求解

AC啦!

代码…略

(不开long long见祖宗?)

 

T2

题面的翻转据说暴露了归并排序,然而我没看出来…

首先大家注意题面中说每个区间长度都是偶数,这个看似无用的条件却是解题的关键,将每个区间翻转后,新区间必然最长为2(认真考虑)

如果没有这个条件 举个栗子:

6 1 5 9 4

1 6 5 4 9

会发生这种不友好的变化…(我模拟的时候就是以为偶数没什么用举了这个例子然后放弃考虑逆序对的…)

所以以后再每次操作都只会将一组逆序对交换,即使这对逆序对不相邻,日后总会相见…

所以这道题就变成了求逆序对的水题…

然后轻松AC,拿到200分即将走上人生巅峰!

代码实现:

T3

(这道题,我看了好长好长好长的时间,才写出以下题解,我其实也没有完全弄懂…)

长话短说,这就是到dp题,然而你需要用十八般武艺去优化它,让它能不TLE。

首先比较好想的就是二分答案,二分一个lim’,为理想的女友指数上限。然而还是不行…

所以在二分的check函数中,我们还需要做一些优化,不难发现,如果把每个人的h[]画成函数的话,每一段的h[]为那个峰值,我们姑且叫这个人为团长,一个班由几个团组成…所以每次操作也与这些团长有关,于是我们用一个单调队列来维护它,记录每个团长的位置,使O(n)的复杂度下降。

check的实现:

差不多…就这样?代码…上面那些应该够了..

原题保密2333..

T1很简单,贪心思路,开一个优先队列,没个时间取出最大,减小b后,放回队列,直到队首小于a*t即可

代码…略?

T2 RMQ那种写法我跪了…

新的写法-(类似于?)DP:在网上看了个题解,没太看懂,自己想了想,dp[i]记录以i为结尾合法的序列的起点为dp[],在这个过程中,不断增大长度,求出最大值即可

dp转移:对于i向前找,如果!a[j]<a[i]就可以break 如果dp[j]<dp[i]并且h[dp[j]]<h[dp[i]]就可以合并两个序列

时间复杂度:O(n^2)….但是经过评测发现最多只跑了0.1s左右..

 

T3刚开始看这道题很没头绪,写了个随机数撞大运?

一种合理的解法就是先算出每个点的前缀和,然后对于sum[i]<=c/2的点,二分向后查找,找到第一个sum[j]>=c/2+sum[i]的点,然后与j-1相比较,一顿操作…最后取max即可

时间复杂度为O(nlogn),代码只有27行。。。

 

题目描述

东非大裂谷中有一片神秘的丛林,是全世界探险家的乐园,著名黄皮肤探险家BB一直想去试试。正好我国科学家2005年4月将首次对东非大裂谷进行科考,BB决定随科考队去神秘丛林探险。在出发之前,他搜集了国内外有关神秘丛林探险的资料,并绘制成一张地图:该地图上有若干安全点(包括入口点和出口点),并将这些安全点编号为1、2、…、n;如果一个安全点和另一个安全点有一条路直接相通,则用一条边标示;该图是一个连通图(任意两点间有至少一条路径),地图上每条路的长度和走这条路需要耗费的体力都做了标示。 KK行走速度为1,并知道自己体力为K。他想知道根据自己的体力情况能否成功地穿过丛林。

输入

第一行两个整数n(< =5000)    m(< =40000),分别表示地图上安全点的个数和边的数目; 第2行至第m+1  行每行4个整数x    y    c  d,x、y表示有直接相联边的两个点的编号,c走这条路需要耗费的体力;d表示边的长度;(其中150< =c,d< =300) 第m+2行两个整数s    t,分别表示安全的入口点和出口点的编号; 第m+3行一个整数k,表示BB的体力值;(K< 10^9) 同一行上的多个数据用空格隔开。

输出

一个整数,如果BB能安全地从如入口穿过丛林到达出口,输出最短时间,否则输出-1

样例输入

样例输出

 

首先,这题是可以用SPFA做的,在relax的时候再加体力判定即可,具体可以问YJY大哥.

而我的做法十分简单粗暴,dfs加剪枝就可以过了

 

如果哪里不太清楚(或者我写的有bug),可以找本人…