111qqz的小窝

老年咸鱼冲锋!

弱校连萌 2016 10.3

题目链接

。。。sad…..

果然没睡够&起来就写题脑子完全就是不清醒的状态。。。

这个不清醒。。。主要体现在。。。。10+次。。。忘记删条件编译。。。

2016-10-03-14-56-24-%e7%9a%84%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be

改着改着。。。就忘记这件事了。。。好烦啊。。。本来早就A了。。。结果又接着去改。。。

 

题目链接:jag2016

就水了三道题。。。。

A是个暴力。。直接O(n2)算乘积,然后再check一下合法性就好。。。尼玛wa到我怀疑人生。。。过了好久才考虑也许是不支持条件编译的问题。

 

B是bfs…我的做法是先算每个点有士兵到达的最小时间。然后公主跑到某个点的时候判断当前时间是否小于这个格子士兵到达的最小时间。

不过这样做会Tle,可以加个剪枝,就是在处理每个点有士兵到达的最小时间的时候,如果某个点存在比当前士兵到达的时间的更短的时间。。。那么这个士兵其实就没用了。。。直接不再入队。。。(同时要记得先把所有士兵位置标记一下再跑bfs)

 

d题:构造。。一开始思路错了。。。以为让所有的数都是三角形数会比较优秀。。。然而当A为8的时候。。按照这个思路,答案为)()()))(((

但实际上存在更优的答案为))())(((

造成这个错误的原因是。。。忽视了每一部分之间的关联。。。以为减去一个三角形数以后就成了一个新 的问题。。。

但是实际上不是这样。。。

我们可以手写从A=6到A=10的情况。。。。规律比较显然。。。

具体写的时候我预处理了小于等于A的三角形数。。。

 

剩下的题没来得及看。。。。。。。不过目测还有2道可以做(?

 

hdu 5833 || ccpc 2016 网络赛 1002 Zhu and 772002 (高斯消元)

hdu 5833 题目链接

题意:n个数,保证每个数的素因子不超过2000,从中取若干个,问乘积是完全平方数的方案数。

思路: 完全平方数就是要求每个质因子的指数是偶数次。

列方程组,a1,a2,a3……am分别表示bi是否在集合中。对于每一个素因子,建立异或方程组,要求因子个数为偶数,即异或为0

然后得到自由元的个数为num,答案为2^num-1 (减去空集)

 

hdu 5842 || 2016 ccpc 网络赛 1011 Lweb and String(set)

hdu 5842题目链接

题意:给一个只由小写字母组成的字符串,每个字符映射到一个数字,问映射之后的最长上升子序列的长度。。

思路:上来写nlogn的LIS是我无脑了。。。wa了之后想了下。。其实只要统计不同的字母数就好了啊。。。set一下

 

 

codeforces #120 div 2 (Virtual Participation)

比赛链接

选区_033

选区_034

两题QAQ

A:7分钟1A 有n个大人m个小孩乘公交车,票价每人一元,一个大人最多免费带一个小孩,没有大人陪同的小孩不能乘车。 问是否有解,如果有解输出所有乘客付的钱的可能的最小值和可能的最大值。

思路:最小值就是先尽量利用每个大人带一个孩子。最大值就是把所有孩子都给一个大人。

特殊情况是:没有大人的时候,孩子不能乘车,无解。没有小孩的时候,大人没办法免费带孩子,也要特殊考虑。

 

 

B:有两个被包围的城市,给出城市的坐标以及敌人距离城市的距离。敌人向着城市移动。要求建一个雷达,使得雷达能够感应到两伙敌人(分别朝着两个方向移动)的“the start of the movements”。问雷达的最小半径是多少。

反思:思维不够清楚,太呆

思路:两个圆有五种(一开始想成了三种,所以wa7)位置关系,分别考虑。

相离时,答案为(圆心距-半径之和)/2

外切时:把雷达建在切点,答案为0.

相交时:把雷达建在交点,答案为0

内切时:把雷达建在交点,答案为0.

内含时:答案为(abs(半径之差)-圆心距离)/2.

 

 

C:给出一个pair 和int 序列,问能否恢复成一个合法的类型表示。如果能,保证有唯一解,输出这个唯一解。

细节略多。

没搞出来QAQ

 

粤ICP备18103363