Thusc2017 滚粗记及题面

# Day1

## T1

### 时空限制

时间限制：5s 
空间限制：512M

### 题目大意

给出一个$N*M$的四连通网格，每个格子有一个颜色$C_{i,,j}$和一个权值$V_{i,j}$。其中有一些格子是坏的，不能够被选中。现在要求你选出一个连通块，使得该连通块至少含有$K$种颜色，且面积最小，满足前两种条件下所有选中格子的权值中位数最小（定义为第$\lfloor \frac{x+1}{2} \rfloor$小的数）。
输出最优连通块所含格子数和中位数。

如果中位数出错，格子数正确，则得到该点60%的分数

### 数据范围
$N*M \leq 233$
$K \leq 5$

大暴搜有5分

对于$40\%$的点 $N*M \leq 30$
对于$70\%$的点 $N*M \leq 50$
对于$100\%$的点 $N*M \leq 233， K \leq 5$

## T2

### 时空限制

时间限制：5s 
空间限制：512M

### 题目大意

出题人喜欢完全平方数，所有就出了一道完全平方数的题。
现在给出数字集合$L , L+1, L+2 ... R $，求从中选出一个子集，使得子集内的数乘积为完全平方数的方案数有多少种？什么都不选算一种。

### 数据范围

一个测试点有T组数据

对于$50\%$的点$L,R \leq 3000 , T \leq 10 , \sum{R-L} \leq 3000$
对于$70\%$的点$L,R \leq 1,000,000 , T \leq 10 , \sum{R-L} \leq 10,000,000$
对于$100\%$的点$R \leq 10,000,000 , T \leq 100 , \sum{R-L} \leq 10,000,000$

## T3

### 时空限制

时间限制：5s 
空间限制：512M

### 题目大意

现在有$N$个圆桌，每个圆桌有$M$个位置。从$a$号圆桌的第$b$号位置走到$c$号圆桌的第$d$号位置需要花费$|c-a|*2+min(|d-b|,m-|d-b|)$的体力。
现在每位置上都有人，对于第$i$个人，他想要坐到第$L_i$到第$R_i$张圆桌之间。

现在问你能否实现，如果能最小总花费的体力是多少？

### 数据范围

对于$30\%$的点，$N \leq 10 , M \leq 10$
对于$50\%$的点, $N \leq 50 , M \leq 10$
对于$100\%$的点, $N \leq 300 , M \leq 10$

### Sadly update:
听说我day1炸飞了啊！只有预期的一半的分。我好歹是过了所有大样例的啊！

# Day2

## T1

### 时空限制

时间限制：3s 
空间限制：512M

### 题目大意

现在给出三个长度为N的数组A,B,C。
现在要求支持七种操作：
以下的$i$取遍$l$ - >  $r$

* 1 l r : $A_i=A_i+B_i$
* 2 l r : $B_i=B_i+C_i$
* 3 l r : $C_i=C_i+A_i$
* 4 l r v : $A_i=A_i+v$
* 5 l r v : $B_i=B_i*v$
* 6 l r v : $C_i=v$
* 7 l r : 令$TA= \sum A_i, TB= \sum B_i , TC= \sum C_i$,输出 $TA ，TB ，TC$。

共有$M$个操作。

### 数据范围

$N,M<=250,000$

## T2

### 时空限制

时间限制：1s 
空间限制：512M

### 题目大意

现在你有一个长度为$N$的项链，有$M$种颜色。要求每相连的$M$个珠子不能不存在颜色相同的一对。项链可以旋转，但不能翻转。旋转相同视为相同。求不同的合法染色方案数。

### 数据范围

对于$10\%$的数据，$N \leq 10, M \leq 4$
对于$40\%$的数据，$N \leq 10^9 , M \leq 7 $, 且$N$为质数。
对于另外$40\%$的数据，$N \leq 10^5 , M \leq 7 $
对于$100\%$的数据，$N \leq 10^9 , M \leq 7$。

## T3

### 时空限制

时间限制：/ 
空间限制：/

### 题目大意

这是一道提交答案题。
给出N个K维的圆，求出这些圆的所有共切K-1维超平面与这些圆交点的坐标。

保证有且仅有有限个解

### 数据范围

对于$20\%$的数据,$2 \leq K \leq 2$
对于$45\%$的数据,$2 \leq K \leq 3$
对于$100\%$的数据,$2 \leq K \leq 10, N \leq 100$

Sadly Update.
为什么我T2写了三个小时也没调出暴力。

Update.
大炸+小炸 竟然还有60分约可以签，真是良心。

wuvin

导航

最近发表

友情链接