POI2015 - jcvb
POI2015
jcvb
posted @ 2014年11月01日 10:07
, 3133 阅读
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的好像都没人加上去……