洛谷P1011 车站

题目

---

• 一直没有头绪的一道题
• 明明只有普及-难度
• 看了看题解用的大多是方程和fibonacci
• 于是更加懵逼了。。。
• 今天立志ac此题

---

 

• 说一下思路
• 然而并没有思路
• 按照题意敲代码
• 不妨设第二站上下车了k人
• 分别统计每一站a和k的系数
• 1、2、n站特殊处理
• 然后求出k，代入x站中输出即可

---

 

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int a,n,m,x,k,on[25][2],off[25][2],tot[25][2]; 
 6 
 7 inline int read(void){
 8     int x=0,f=1;char ch=getchar();
 9     while(ch<'0'||ch>'9'){
10         if(ch=='-') f=-1;
11         ch=getchar();
12     }
13     while(ch>='0'&&ch<='9'){
14         x=(x<<1)+(x<<3)+ch-'0';
15         ch=getchar();
16     }
17     return x*f;
18 }
19 
20 int main(){
21     a=read();n=read();m=read();x=read();
22     on[1][0]=1;on[1][1]=0;off[1][0]=0;off[1][1]=0;
23     on[2][0]=0;on[2][1]=1;off[2][0]=0;off[2][1]=1; 
24     tot[1][0]=(on[1][0]-off[1][0]),tot[1][1]=(on[1][1]-off[1][1]);
25     tot[2][0]=tot[1][0]+(on[2][0]-off[2][0]),tot[2][1]=tot[1][1]+(on[2][1]-off[2][1]);
26     for(register int i=3;i<n;i++){
27         on[i][0]=on[i-1][0]+on[i-2][0];
28         on[i][1]=on[i-1][1]+on[i-2][1];
29         off[i][0]=on[i-1][0];off[i][1]=on[i-1][1];
30         tot[i][0]=tot[i-1][0]+(on[i][0]-off[i][0]),tot[i][1]=tot[i-1][1]+(on[i][1]-off[i][1]);
31     }
32     k=(m-(tot[n-1][0]*a))/tot[n-1][1];
33     printf("%d\n",tot[x][0]*a+tot[x][1]*k);
34     return 0;
35 }