Zory的暖心省选胡策

日期:2020.05.21 8:00~12:00,赛后将公开题解

造题人:zory,验题人:Deep_Kevin

约定:如果没有特殊说明,数字都是非负整数;代码长度限制10K;如果被识别了麻烦私聊

评测机:i5+2.9GHZ+8G内存,编译命令为-lm -static -O2 -Wl,-stack=268435456​

题目背景:作为一名春学家,无法接受选择其他元素作为题目背景,但把春物拿去当题目背景简直是玷污,所以就没有背景了

题目名称 A B C
文件名(程序与IO),大小写敏感 a b c
空间限制 1G 1G 1G
时间限制 1s 2s 1s

A

题目描述

给出n点m边简单无向图,选出边的子集E,E中每条边在k种颜色中选一种,边权为两点点权w之和,收益为边权和,最大化收益

要求为,对于每个x,独立计算一个长为k的序列A,$A_{c}=\sum_{(x,y) \in E} [color\ of\ (x,y)=c]$,A的极差不超过2

输入格式

1
2
3
n m k
w1 w2 w3.. wn
x y//m行

输出格式

按当初输入的顺序,输出每条边的颜色,不选输出0,任意解即可

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
input:
7 11 3
4 7 8 10 10 9 3
6 2
6 1
7 6
4 3
4 6
3 1
5 3
7 5
7 3
4 2
1 4
output:
1 2 3 2 1 3 1 2 2 3 1

数据范围与提示

请自觉呵护spj姬,按照正确格式来,$k>0,3 \le n \le 100,0 \le m,k,w_x \le 1e3$

测试点 限制
1,2,3 $m \le 8$
4,5 $n \le 30$
6,7,8,9 保证是一棵树
10,11 $w_x=1$
12,13 $k=2$
14,15,16 $k=3$
17,18,19,20

B

题目描述

初始有n个白球排成一排,做m次操作,按时间顺序给出每次操作时手上的颜色是蓝还是红,每次选择一段区间染色或者永久跳过此次操作,并且不能直接把白色染成蓝色,问能得到多少种本质不同的结果序列

输入格式

1
2
正整数n m
S(|S|=m,r表示红)

输出格式

一个数,模$1e9+7$下的答案

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
input1:
2 2
rb
input2:
5 2
br
input3:
7 4
rbrb
input4:
70 70
bbrbrrbbrrbbbbrbbrbrrbbrrbbrbrrbrbrbbbbrbbrbrrbbrrbbbbrbbrbrrbbrrbbbbr
output1:
9
output2:
16
output3:
1569
output4:
841634130

数据范围与提示

subtask1~6($10pt$每个):第i个为$n,m \le 10i$,且依赖于上一个

subtask7($10pt$):$n \le 100 ,m \le 50$

subtask8($30pt$):$n\le 500,m \le 100$,依赖于前面所有

C

题目描述

构造每行、每列内没有重复元素,且值域为$[1,n]$的大小为n的方阵,且满足$\sum a_{i,i}=K$

输入格式

T组数据,每组输入n和K

输出格式

每组数据先输出一行,POSSIBLEIMPOSSIBLE,若有解,再用n行输出一个矩形

样例

1
2
3
4
5
6
7
8
9
10
input:
2
3 6
2 3
output:
POSSIBLE
2 1 3
3 2 1
1 3 2
IMPOSSIBLE

数据范围与提示

请自觉呵护spj姬,按照正确格式来

$T \le 10,3 \le n \le 50,n \le k \le n^2$(样例与此限制无关)

测试点 限制
1 $n=3$
2 $4 \le n \le 5$
3 $6 \le n \le 10$
4,5 $K=n+2,n > 10$
6 $K=n+3,n > 10$
7 $K=n^2-3,n > 10$
8 $K=n^2-2,n为偶,n>10$
9,10

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/b0e70d2a.html
转载请注明出处,谢谢!