題目大意,現在要走過一條斑馬線,斑馬線是由n條交替的黑條和白條構成的,第一條是黑條。腳的長度是s。要求在走的過程中,他腳的任何一部分都不能碰到象征邪惡的黑條。第一條之前和第n條之后的部分都是白色的,可以任意選擇第一條之前的位置出發。但出發位置一旦選定,之后每一步的長度都必須是k。請你判斷有沒有可能在不碰到黑條的情況下通過斑馬線,即走到第n條之后。
最難解的數學題,?
此題同樣是模擬賽題!!!
我現在已經非常質疑自己的智商了,為什么每次都是離正解只差一步呢,每次都不能換一個思路去想一想。
先說說我的錯誤解法:我列了n個不等式,判斷它能不能踩到黑塊,i*k-x>=a[i],i*k-x+s<=a[i+1]-kuan[i+1],i為黑塊,但是走幾步是一個問題,還有這一個白塊可不可以走到也是一個問題,所以正確的處理方法應該是。。。。。。。
?
正解:因為白塊不一定要走到,所以我們枚舉只要判斷能不能不走到黑塊就行了,我們首先將每一個黑塊的起始位置和結束位置mod k,并將它對應到(0,k-1)的一塊區間內,如果x>y,則對應到(x,k-1),(0,y)中,判斷有沒有屬于(0,k-1)中的點沒有被覆蓋到的情況。
但還要注意一個問題,如果一個黑塊長度大于k-s+1,那么是怎么也不行的,因為它怎么也跨不過去。
這道題很多人說用開區間好處理,其實閉區間也很好處理。
?
本題總結:現在經常忘了一樣東西就是mod,每次都是利用i來控制范圍,卻忘記了i這個變量的不確定性,對于不確定問題,mod是一個很好的武器,因為它和i沒有關系,利用mod可以大大減小程序復雜度和思維復雜度。以后不能忘了
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 long long p[500005]; 6 struct node 7 { 8 int from,to; 9 }a[500005]; 10 int n; 11 int s,k; 12 int T; 13 int m; 14 long long len; 15 void read(int &x){ 16 char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); 17 for (x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = x*10+ch-48; 18 } 19 bool cmp(node u,node v) 20 { 21 if(u.from!=v.from)return u.from<v.from; 22 return u.to>v.to; 23 } 24 bool rt; 25 int l,r; 26 int main() 27 { 28 read(T); 29 while(T--) 30 { 31 len=0; 32 rt=false; 33 read(s); 34 s--; 35 read(k); 36 read(n); 37 for(int i=1;i<=n;i++) 38 { 39 int x; 40 read(x); 41 len+=x; 42 p[i]=len; 43 } 44 m=0; 45 for(int i=1;i<=n;i+=2) 46 { 47 if(p[i]-p[i-1]>=k-s) 48 { 49 // cout<<p[i]-p[i-1]<<endl; 50 puts("NIE"); 51 rt=true; 52 break; 53 } 54 long long x=p[i-1]-s,y=p[i]-1; 55 x=(x%k+k)%k; 56 y=y%k; 57 // cout<<x<<" "<<y<<endl; 58 if(x<=y){ 59 a[++m].from=x; 60 a[m].to=y; 61 } 62 else 63 { 64 a[++m].from=x; 65 a[m].to=k-1; 66 a[++m].from=0; 67 a[m].to=y; 68 } 69 } 70 if(rt)continue; 71 // cout<<"find"; 72 sort(a+1,a+m+1,cmp); 73 if(a[1].from>0) 74 { 75 puts("TAK"); 76 continue; 77 } 78 l=a[1].from;r=a[1].to; 79 /*for(int i=1;i<=m;i++) 80 printf("%d %d\n",a[i].from,a[i].to);*/ 81 for(int i=2;i<=m;i++) 82 { 83 // cout<<a[i].from<<" "<<r<<endl; 84 if(a[i].from>r+1) 85 { 86 //cout<<i<<r<<endl; 87 rt=true; 88 puts("TAK"); 89 break; 90 } 91 if(a[i].from<=r+1 && a[i].to>=r) 92 { 93 r=a[i].to; 94 } 95 } 96 if(rt)continue; 97 if(r<k-1) 98 { 99 puts("TAK"); 100 } 101 else 102 { 103 puts("NIE"); 104 } 105 } 106 return 0; 107 } 108 109
?