欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷P1011 车站

程序员文章站 2022-11-08 22:45:38
题目 一直没有头绪的一道题 明明只有普及-难度 看了看题解用的大多是方程和Fibonacci 于是更加懵逼了。。。 今天立志AC此题 结果用大模拟还真过了 说一下思路 然而并没有思路 按照题意敲代码 不妨设第二站上下车了k人 分别统计每一站a和k的系数 1、2、n站特殊处理 然后求出k,代入x站中输 ......

题目


  • 一直没有头绪的一道题
  • 明明只有普及-难度
  • 看了看题解用的大多是方程和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 }