最難解的數學題，PA 2011 Round 3 prz題解-函數-匯編語言學習筆記

最難解的數學題，PA 2011 Round 3 prz題解

2023-12-06 阅读 28 评论 0

摘要：題目大意，現在要走過一條斑馬線，斑馬線是由n條交替的黑條和白條構成的，第一條是黑條。腳的長度是s。要求在走的過程中，他腳的任何一部分都不能碰到象征邪惡的黑條。第一條之前和第n條之后的部分都是白色的，可以任意選擇第一條之前的位置出

題目大意，現在要走過一條斑馬線，斑馬線是由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

View Code

轉載于:https://www.cnblogs.com/sillygirl/p/3915033.html

原文链接：https://hbdhgg.com/3/192692.html

发表评论: