Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

12/31
13:46
TEST

Good Bye 2016

2016的最后一天了,凌晨打了CF……做得很差 rating又掉惨了TAT 在这里写一下前三题的做法吧……

A. New Year and Hurry

给定n个问题,按难度拍好了序,解决第i个问题花费的时间为5*i,从20:00开始到24:00,期间还要花费k分钟去另一个地方,问最多能解决多少问题。

Examples

input
3 222

output
2

input
4 190

output
4

input
7 1

output
7

直接for一遍即可。

 

B. New Year and North Pole

一只北极熊从北极出发,共有n次操作:North \South\ East\ West +一段距离

特殊的:

  • 当北极熊在北极或经过北极时,只能往南走
  • 当北极熊在南极或经过南极时,只能往北走
  • 最后,北极熊必须在北极点

n次操作后,满足所有以上条件输出"YES";否则,输出"NO"

Examples

input
5
7500 South
10000 East
3500 North
4444 West
4000 North

output
YES

input
2
15000 South
4000 East

output
NO

input
5
20000 South
1000 North
1000000 West
9000 North
10000 North

output
YES

input
3
20000 South
10 East
20000 North

output
NO

input
2
1000 North
1000 South

output
NO

input
4
50 South
50 North
15000 South
15000 North

output
YES

Note Drawings below show how Limak's journey would look like in first two samples. In the second sample the answer is "NO" because he doesn't end on the North Pole.

也是模拟,注意随时判一下那几个条件即可。

 

C. New Year and Rating

模拟CF赛制,共有n场比赛,每场比赛两个信息,rating变化,以及在哪一组.(rating在1900及以上时div1;1899及以下时div2) 求n场比赛后rating最大可能是多少。

Examples
input
3
-7 1
5 2
8 2

output
1907

input
2
57 1
22 2

output
Impossible

input
1
-5 1

output
Infinity

input
4
27 2
13 1
-50 1
8 2

output
1897

Note In the first sample, the following scenario matches all information Limak remembers and has maximum possible final rating:

Limak has rating 1901 and belongs to the division 1 in the first contest. His rating decreases by 7. With rating 1894 Limak is in the division 2. His rating increases by 5. Limak has rating 1899 and is still in the division 2. In the last contest of the year he gets  + 8 and ends the year with rating 1907. In the second sample, it's impossible that Limak is in the division 1, his rating increases by 57 and after that Limak is in the division 2 in the second contest.

嗯……刚开始听a神犇说是线性规划做,好吧还是我太弱了TAT

二分是可以的

 

剩下的题目就当挖个坑吧……以后再去做

11/15
10:33
TEST

11.15 test

试题

T1:

询问把n个数变成互不相同的数的最小价值。

n <= 10w, ai<=10w

这个做法有很多……可以 先排个序 或者 用set来做 都是可以的

说一下我在考场上的做法:是用到了并查集的思想。开一个数组fa, fa[i]表示大于等于i的第一个没有出现的数字。然后每次修改 find一下就好了

预处理的话 fa[i] = i。 如果一个数出现过的话,fa[i]改为i+1

 

T2:

n个点 m条有向边,求所有点到一号点的最短路之和。如果有任意一个点无法到达,输出-1.

奇怪的边权生成方式:w = (上一条边的边权 a + b) % c . w初始值为10,第一条边的权值为(10 a + b) % c

对于 30%的数据 n<= 200 , m <= 500 , a,b <= 100, c<=10000 对于 60%的数据 n<=10000 m <= 15000 a,b<=10000 c <= 10^7 对于 100%的数据 n <= 100000 m <= 200000 a,b <= 10^16, c <= 10^9

30分做法:floyd 同时w = (上一条边的边权 * a + b) % c不会爆掉int

60分做法:spfa 同时w = (上一条边的边权 * a + b) % c不会爆掉long long

100分做法:spfa 而这时需要及时取模 w = (((w % c) * (a % c)) % c + (b % c)) % c 要知道%运算时满足分配律的

30分floyd

 

100分spfa

 

T3:

划分型DP 自行百度书本整理即可

 

11/9
21:30
TEST

钟神的P73

P73

T1

题意:给定两个日期,求它们之间间隔了多少毫秒。

对于100%的数据,两个日期一定都是 21 世纪的某一天,且第二个日期一定 大于等于第一个日期。

当然是大力暴力啦!分别求出当前日期从2000-01-01 00:00:00开始一共过去了多少毫秒,然后输出差值就可以了。

 

T2

题意:n个人,m个位置,n个人按顺序打sif,每个人需要耗费一定的时间,问轮到第n+1个人打sif的时间。

n<=100000, m <= 50000.

这就是一个打水问题嘛,用优先队列搞一下就好了。

 

T3

题意:背包是个好东西,希望我也有。 给你一个二维的背包,它的体积是𝑁 × 𝑀。现在你有一些大小为1 × 2和1 ×3的物品,每个物品有自己的价值。你希望往背包里面装一些物品,使得它们的价值和最大,问最大的价值和是多少。

对于20%的数据,𝑁, 𝑀 ≤ 10, 𝑛1, 𝑛2≤ 100。 对于70%的数据,𝑁, 𝑀 ≤ 100, 𝑛1, 𝑛2≤ 2000。 对于100%的数据,1 ≤ 𝑇 ≤ 10,1 ≤ 𝑁, 𝑀 ≤ 500,0 ≤ 𝑛1, 𝑛2≤ 10000。

嗯……刚开始没有想到正解,但感觉一般情况下可以抽象成一个容量为n*m的背包,而两种物品的体积分别为2和3,这样就变成了01背包问题。但是因为memset的原因,tle了三个点……没有拿全40分 要不然就rank3了,哼唧

 

关于正解!是一个贪心……枚举1*3的物体放多少个即可得到正解。

当然,处理不是这么简单的。

一般情况下,13的物体最多可以放nm/3个;

而当背包的长或宽为2的时候,也就是说13的物体只能横着或竖着放。如果背包的宽为2,长为k3+2(k >= 0)的时候,13的物体最多可以放(nm-4)/ 3个

也就是

这样处理完就可以了,同时注意n1和n2可能不够的情况。