暑假測試 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一把把！！！……