POI2015 - jcvb
POI2015
jcvb
posted @ 2014年11月01日 10:07
, 3129 阅读
XXII Olimpiada Informatyczna — I etap
(upd)今天数据公布了。。发现写萎了一道题。。特判时出了点小问题。。
2014-10-31 04:23:37 | Kwadraty (kwa) | Wstępne sprawdzanie: OK | 100 | |
2014-10-31 02:15:14 | Pieczęć (pie) | Wstępne sprawdzanie: OK | 100 | |
2014-10-30 06:26:14 | Czarnoksiężnicy okrągłego stołu (cza) | Wstępne sprawdzanie: OK | 68 | |
2014-10-28 13:29:42 | Kinoman (kin) | Wstępne sprawdzanie: OK | 100 | |
2014-10-28 12:35:25 | Łasuchy (las) | Wstępne sprawdzanie: OK | 100 |
要丢给bz的话还缺一个Łasuchy的spj。。
POI2015 - Czarnoksiężnicy okrągłego stołu
n个人(编号为1~n)围着圆桌坐成一圈。座位相邻的两个人,其编号之差的绝对值不可以超过p。
他们之中有些人不喜欢别人。如果a不喜欢b,那么b不能坐在a右边的那一个位置上。
现在,假设第n个人的座位已经固定,要给剩下的人安排座位,共有几种合法方案?
输入:
第一行包含三个整数n,k,p(1<=n<=1000000,0<=k<=100000,0<=p<=3)。
接下来k行,每行含两个整数a[i],b[i](1 <= a[i],b[i] <= n, a[i]≠b[i]),表示a[i]不喜欢b[i]。同一组a[i],b[i]不会重复输入。
输出:
输出一个整数,表示方案数模10^9+7后的值。
样例输入:
5 2 3
1 3
5 4
样例输出:
6
样例解释:
合法方案有53124,53142,52143,53412,52314,53214。
POI2015 - Kinoman
共有m部电影,编号为1~m,第i部电影的好看值为w[i]。
在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第f[i]部。
你可以选择l,r(1<=l<=r<=n),并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次,你会感到无聊,于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
输入:
第一行两个整数n,m(1<=m<=n<=1000000)。
第二行包含n个整数f[1],f[2],…,f[n](1<=f[i]<=m)。
第三行包含m个整数w[1],w[2],…,w[m](1<=w[j]<=1000000)。
输出:
输出观看且仅观看过一次的电影的好看值的总和的最大值。
样例输入:
9 4
2 3 1 1 4 1 2 4 1
5 3 6 6
样例输出:
15
样例解释:
观看第2,3,4,5,6,7天内放映的电影,其中看且仅看过一次的电影的编号为2,3,4。
POI2015 - Kwadraty
考虑将正整数n拆分成几个不同的平方数之和,比如30=1^2 + 2^2 + 5^2=1^2 + 2^2 + 3^2 + 4^2,而8不存在这样的拆分。
用k(n)表示n的拆分中,最大的底数最小可能是多少。如果n不存在这样的拆分,则令k(n)=∞。例如,k(1)=1,k(8)=∞,k(378)=12,k(380)=10。
定义一个数x被称为“超重”的,当且仅当存在y>x,使得k(y)<k(x)。从上面的例子可知,378是一个“超重”的数。
给定n,你需要:
(1)求出k(n)
(2)求出1~n中有几个“超重”的数。
输入:
输入仅一行,包含一个正整数n(1<=n<=10^18)。
输出:
输出一行包含两个整数,分别为对上述两个问题的答案。如果k(n)=∞,则输出一个减号'-'代替。
样例输入1:
30
样例输出1:
4 15
样例输入2:
8
样例输出2:
- 5
POI2015 - Łasuchy
圆桌上摆放着n份食物,围成一圈,第i份食物所含热量为c[i]。
相邻两份食物之间坐着一个人,共有n个人。每个人有两种选择,吃自己左边或者右边的食物。如果两个人选择了同一份食物,这两个人会平分这份食物,每人获得一半的热量。
假如某个人改变自己的选择后(其他n-1个人的选择不变),可以使自己获得比原先更多的热量,那么这个人会不满意。
请你给每个人指定应该吃哪一份食物,使得所有人都能够满意。
输入:
第一行一个整数n(2<=n<=1000000),表示食物的数量(即人数)。食物和人都从1~n编号。
第二行包含n个整数c[1],c[2],…,c[n](1<=c[i]<=10^9)。
假设第i个人(1<=i<n)左边是第i份食物,右边是第i+1份食物;而第n个人左边是第n份食物,右边是第1份食物。
输出:
如果不存在这样的方案,仅输出一行NIE。
如果存在这样的方案,输出一行共n个整数,第i个整数表示第i个人选择的食物的编号。如果有多组这样的方案,输出任意一个即可。
样例输入:
5
5 3 7 2 9
样例输出:
2 3 3 5 1
POI2015 - Pieczęć
一张n*m的方格纸,有些格子需要印成黑色,剩下的格子需要保留白色。
你有一个a*b的印章,有些格子是凸起(会沾上墨水)的。你需要判断能否用这个印章印出纸上的图案。印的过程中需要满足以下要求:
(1)印章不可以旋转。
(2)不能把墨水印到纸外面。
(3)纸上的同一个格子不可以印多次。
输入:
第一行一个整数q(1<=q<=10),表示测试点数量。
接下来q个测试点,每个测试点中:
第一行包含4个整数n,m,a,b(1<=n,m,a,b<=1000)。
接下来n行,每行m个字符,描述纸上的图案。'.'表示留白,'x'表示需要染黑。
接下来a行,每行b个字符,描述印章。'.'表示不沾墨水,'x'表示沾墨水。
输出:
对于每个测试点,输出TAK(是)或NIE(否)。
样例输入:
2
3 4 4 2
xx..
.xx.
xx..
x.
.x
x.
..
2 2 2 2
xx
xx
.x
x.
样例输出:
TAK
NIE
2014年11月24日 16:49
2014的好像都没人加上去……