暑假测试 Day 4

问题 A: 七天使的通讯

时间限制: 2 Sec  内存限制: 256 MB

提交: 422  解决: 122

[​​提交​​​][​​状态​​​][​​讨论版​​]

题目描述

n个天使排成一条直线，某些天使之间需要互相联系，他们之间的通讯可以通过黑白两种通道中的一种；所有通道必须在直线同侧（另一侧是地面）；为了保证通讯效率，同种颜色的所有通道之间不能相交。请计算能否建立这种通讯方案。

输入

    第一行一个数T，表示接下来有T个询问。

    对于每个询问：第一行两个数n，m，分别表示有n个天使、需要建立通讯线路的天使有m对；接下来有m行，每行两个数a、b，表示a、b两个天使需要通讯。

输出

对于每个询问，输出一行“sane”表示有可行方案、“non”表示无解

样例输入

1

7 5

1 3

2 7

3 4

7 4

6 5

样例输出

sane

提示

【样例解释】

样例中共有一个询问。

在(1,3)、(4,7)、(5,6)之间连黑色通道，在(2,7)、(3,4)之间连白色通道，每条通道都成功建立，且同种颜色的通道没有相交，所以输出sane。

【数据规模和约定】

对于 20%的数据，1<=n<=50，1<=m<=15

对于 50%的数据，1<=n<=1000，1<=m<=300

对于 100%的数据，1<=n<=5000，1<=m<=1000，1<=T<=10，1<=a<=n，1<=b<=n

数据保证每对(a,b)不重复，且a不等于b

【提示】

当两条线路有一对相同的端点时，这两条线路不相交。

也就是说，对于线路(a,b)和线路(c,d)（a<b且c<d），当且仅当a<c<b<d或者c<a<d<b时这两条线路相交。

~~:

A了。

还是比较简单的……我们直接O(M^2)判断两两的交叉关系，

然后称交叉的连线（编号x，y）,x和y有冲突。

根据题意能够看出这必须是一个二分图。。

所以就是如何去判断它是不是的问题了……

有些大佬上并查集…………其实直接黑白染色就可以了。。

假设如果一个点没有颜色，就染成白色；然后根据一些关系延伸下去；

假设碰到一个点有颜色，而且这个颜色和它要染的冲突了，就是不合法的。。

大致吧。

问题 B: 都市环游

时间限制: 1 Sec  内存限制: 512 MB

提交: 261  解决: 92

[​​提交​​​][​​状态​​​][​​讨论版​​]

题目描述

因为SJY干的奇怪事情过多，SJY收到了休假的通知，于是他准备在都市间来回旅游。SJY有一辆车子，一开始行驶性能为0，每过1时间行驶性能就会提升1点。每个城市的道路都有性能要求。SJY一共有t时间休息，一开始他位于1号城市（保证1号城市道路要求为0），他希望在n号城市结束旅程。每次穿过一条城市间的路会花费1时间，当然他也可以停留在一个城市不动而花费1时间。当且仅当车子的行驶性能大于等于一个城市，我们才能到达那里。SJY希望知道，旅游的方案模10086后的答案。（只要在某一时刻通过的道路存在一条不相同，就算不同的方案）

输入

    第一行三个数n,m,t，表示有n个城市m条道路t时间。

    第二行n个数，hi表示第i个城市的道路性能要求。

第三到m+2行，每行两个数u,v，表示城市u与城市v之间有一条单向道路连接（可能有重边）。

输出

包括一个数字，表示旅游的方案模10086。

样例输入

5 17 7

0 2 4 5 3

1 2

2 1

1 3

3 1

1 4

4 1

4 5

5 4

5 3

4 1

2 1

5 3

2 1

2 1

1 2

2 1

1 3

样例输出

245

提示

【数据规模和约定】

    对于20%的数据，n<=10,t<=80；

    对于50%的数据，n<=30,t<=80；

    对于100%的数据，n<=70,m<=1000,t<=100000000,hi<=70。

~~：

A了。

首先很容易得到一个想法就是dp。。

dp[u][v]是时间u走到v位置的方案数目。

然后直接转移就好了。。很简单，，，但是只有50分。。

本来想着好像没什么花头了，，结果发现hi<=70？？

我们DP的念头起源于题目有hi这个限制条件……

但是只有就没了？

说明就是累计从u~n，时间刚好过(t-70)的方案数了嘛。。

不就是矩乘吗……

问题 C: 大水题

时间限制: 1 Sec  内存限制: 512 MB

提交: 202  解决: 27

[​​提交​​​][​​状态​​​][​​讨论版​​]

题目描述

    dzy 定义一个n^2 位的数的生成矩阵A 为一个大小为n*n 且Aij 为这个数的第i*n+j-n位的矩阵。

现在dzy 有一个数n^2 位的数k，他想知道所有小于等于k 的数的n*n 生成矩阵有多少种。（如果不足n^2 位则补前缀零）

输入

第一行一个数n，第二行一个n^2 位的数k

输出

仅一行表示答案，答案可能很大，你只需输出答案对10^9 + 7 取模后的结果。

样例输入

2

1000

样例输出

954

提示

【数据规模和约定】 

对于30% 的数据n<=2

对于100% 的数据n <=1000，且n为偶数

【提示】

    如果两个生成矩阵在其中一个旋转180 度后可以重叠，则称这两个矩阵是相同的。

~~：

50分。。

好难呀。。

一开始没什么思路就去刚扫雷……结果刚了好久还是没什么思路……

但是打了暴力的话肯定是个大众分数。。

后来考虑一下，

其实计算的就是满足x在K的范围内，然后x的反过来的串也在K的范围内的个数。

然后还有回文的要注意一下。

怎么搞呢……数位dp吧。。

考场上的想法是乱搞优化一下下，，骗些分数。。

结果它不让用srand？？？？？那我搞个J随机。。

然后就上了几个表吧，，在n=10附近暴力一小会儿，然后上表。。

接着n又加大了几个。。发现暴力优化一下下速度还可以？

交了暴力发现40。。。。

然后把表带上，就50了…………（好少……）

策略挺好的其实。。

正解的话是数位dp……说真的我不大会，

然后f[x][p][q]是前x位的匹配情况……

方程什么的都不会……不过百度上有QAQ..

！！：

总分250，

排名4，

人数50……

果然230是个大众分……幸亏了……

还行吧……

什么时候努努力……

AK一把把！！！……