JZOJ1758. 過河

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

題目

Description

  在BYTELAND的許多市民極喜愛那些邏輯思考與物理技巧同樣重要的運動。有一種運動是過HEX河——BYTELAND中最寬的河流。有n根柱子,從1到n進行編號(從左至右),跨過這條河流。市民過河不得不如此:從河的左岸走至一根柱上,可能再走到下一根柱上,如此下去,最後到達河右岸。左岸有一根柱子設定在柱子1的左側,右岸有一根柱子設定在柱子n的右側。
  在0時刻,有一市民站在左岸,他想盡快到達河的右岸。任意時刻,每一根柱子或者浮上來或者沉下去,市民或者站在某根柱上或者站在河岸。一個市民只有當柱子浮上時方能站在柱上,這樣的柱子才是可靠的,。
  每根柱在0時刻沉下去,然後有a個時間單元浮上來,b個時間單元沉下去,再有a個時間單元浮上來,b個時間單元沉下去,等等。常數a和b對每根柱分別進行定義。例如,對a=2,b=3的某根柱,他在0時刻沉下去,在1,2時刻浮上來;3,4,5時刻沉下去,等等。
  在t 1時刻,市民可以選擇距離t時刻所在位置5根柱子之內的可靠的柱子上﹑岸上,或者站在當前的柱子上(如果可靠)或岸上。例如,從柱子5,你能到達下列的任意一根柱子1,2,3,4,5,6,7,8,9,10或者左岸。
寫一個程式:從檔案RIV.IN中讀取資料的組數(每組包括對該題目的一套資料);對每一組
  ﹡讀取柱子的數目和對他們的描述;
  ﹡計算出市民首先到達河右岸的時刻,如果它能夠到達;
  ﹡將結果寫至檔案RIV.OUT上。

Input

  檔案RIV.IN的第一行包含資料的組數x(1≦x≦5),接下來的許多行組成了這x組數。第一組從輸入檔案的第二行開始,,接下來的每個組直接接在上一組之後。
  每組的第一行包括一個整數N,5

分析

看到1≦a,b≦5 感覺狀態可能不是很多,好似可以暴力。

其實也有其他方法。

我們考慮一下在某個時刻,這個村民可以到達哪些地方。

設fi,jf_{i,j} 表示在第i個時刻,第j個柱子能否到達。

轉移顯然:

fi,j=fi−1,j−5orfi−1,j−4orfi−1,j−3…f_{i,j}=f_{i-1,j-5}or f_{i-1,j-4}or f_{i-1,j-3}…

因為我們不知道時間到底有多大,可以開滾動陣列,

其實因為布林型別空間非常小,不用滾動陣列也是可以通過的。

對於左岸和右岸的柱子,就把它們當作0,n 1 就可以了。

  • 但是時間需要列舉多少呢?

這個有點困難,不過我們可以用一些玄學的方法解決。

先來分析一下時間複雜度:

資料組數t × 列舉時間ans × 柱子數量n

正常情況下c 在評測機上面,每秒可以跑100000000次,

那麼為了保證不超時,我們就使:資料組數t × 列舉時間ans × 柱子數量n≤100000000

這樣答案的錯誤率比較低,

所以,這種方法在隨機資料下表現優良。

Code(c )

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <stdlib.h>
#include <math.h>
#define N 800
using namespace std;
int t,n,ans,a[1300][2],p;
bool bz[2][1300],pd;
int main()
{
scanf("%d",&t);
for(;t;t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i  )
scanf("%d%d",&a[i][0],&a[i][1]);
memset(bz,0,sizeof(bz));
bz[p][0]=1;
for(ans=1;ans<=N;ans  )
{
p=1-p;
memset(bz[p],0,sizeof(bz[p]));
bz[1-p][0]=1;
for(int i=1;i<=5;i  )
if((ans-1)%(a[i][0] a[i][1]) 1>a[i][0])bz[p][i]=0;
else
{
for(int j=0;j<=i 5;j  )
bz[p][i]=bz[p][i]||bz[1-p][j];
}
for(int i=6;i<=n;i  )
if((ans-1)%(a[i][0] a[i][1]) 1>a[i][0])bz[p][i]=0;
else
{
for(int j=i-5;j<=i 5;j  )
bz[p][i]=bz[p][i]||bz[1-p][j];
}
pd=0;
for(int i=1;i<=5;i  )
pd=pd||bz[p][n-i 1];
if(pd)break;
}
if(pd)printf("%d\n",ans 1);
else printf("No\n");
}
}

相關文章

程式語言 最新文章