独木桥
题目背景
战争已经进入到紧要时间。你是运输小队长,正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激,于是命令你的士兵们到前方的一座独木桥上欣赏风景,而你留在桥下欣赏士兵们。士兵们十分愤怒,因为这座独木桥十分狭窄,只能容纳 11 个人通过。假如有 2 个人相向而行在桥上相遇,那么他们 22 个人将无法绕过对方,只能有 11 个人回头下桥,让另一个人先通过。但是,可以有多个人同时呆在同一个位置。
题目描述
突然,你收到从指挥部发来的信息,敌军的轰炸机正朝着你所在的独木桥飞来!为了安全,你的部队必须撤下独木桥。独木桥的长度为 LL,士兵们只能呆在坐标为整数的地方。所有士兵的速度都为 1,但一个士兵某一时刻来到了坐标为 0 或 L+1 的位置,他就离开了独木桥。
每个士兵都有一个初始面对的方向,他们会以匀速朝着这个方向行走,中途不会自己改变方向。但是,如果两个士兵面对面相遇,他们无法彼此通过对方,于是就分别转身,继续行走。转身不需要任何的时间。
由于先前的愤怒,你已不能控制你的士兵。甚至,你连每个士兵初始面对的方向都不知道。因此,你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外,总部也在安排阻拦敌人的进攻,因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。
输入格式
第一行共一个整数 L,表示独木桥的长度。桥上的坐标为 1,2,⋯,L。
第二行共一个整数 N,表示初始时留在桥上的士兵数目。
第三行共有 N 个整数,分别表示每个士兵的初始坐标。
输出格式
共一行,输出 22个整数,分别表示部队撤离独木桥的最小时间和最大时间。2 个整数由一个空格符分开。
输入输出样例
输入 #1复制
4
2
1 3
输出 #1复制
2 4
说明/提示
对于 100% 的数据,满足初始时,没有两个士兵同在一个坐标,1\1≤L≤5×103,0≤N≤5×103,且数据保证 N≤L。
#include <iostream> #include <algorithm> using namespace std; int l,n; int a[5005]; int ansx,ansd; int xiao,da; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>l>>n; if(l==0 || n==0){ cout<<0<<' '<<0; return 0; } xiao=1e8; for(int i=1;i<=n;i++){ cin>>a[i]; int y=max(a[i]-1,l-a[i]); ansd=max(ansd,y); int x=min(a[i]-1,l-a[i]); ansx=max(ansx,x); } cout<<ansx+1<<' '<<ansd+1; return 0; }
幂次方:
题目描述
任何一个正整数都可以用 22 的幂次方表示。例如 137=2^7+2^3+2^0137=27+23+20。
同时约定方次用括号来表示,即 ab 可表示为a(b)。
由此可知,137137 可表示为 2(7)+2(3)+2(0)2(7)+2(3)+2(0)
进一步:
7= 2+2+20 ( 2 用 2 表示),并且 3=2+20。
所以最后 137137 可表示为 2(2(2)+2+2(0))+2(2+2(0))+2(0)。
又如 1315=210+28+25+2+1
所以 13151315 最后可表示为 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)。
输入格式
一行一个正整数 n。
输出格式
符合约定的 n 的 0,2 表示(在表示中不能有空格)。
输入输出样例
输入
1315
输出
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
说明/提示
【数据范围】
对于 100% 的数据,1≤n≤2×104。
#include <iostream> using namespace std; int a[16]; int n; void dayin(int x){ int k=0; for(k=14;k>=0;k--){ if(a[k]<=x){ break; } } if(k==0){ cout<<"2(0)"; }else if(k==1){ cout<<"2"; }else{ cout<<"2("; dayin(k); cout<<")"; } if(a[k]<x){ cout<<"+"; dayin(x-a[k]); } } int main(){ cin>>n; a[0]=1; for(int i=1;i<=14;i++){ a[i]=2*a[i-1]; } dayin(n); return 0; }
车站:
题目描述
火车从始发站(称为第 1 站)开出,在始发站上车的人数为 a,然后到达第 2 站,在第 2 站有人上、下车,但上、下车的人数相同,因此在第 2 站开出时(即在到达第 3 站之前)车上的人数保持为 a 人。从第 3 站起(包括第 3 站)上、下车的人数有一定规律:上车的人数都是前两站上车人数之和,而下车人数等于上一站上车人数,一直到终点站的前一站(第 (n−1) 站),都满足此规律。现给出的条件是:共有 n个车站,始发站上车的人数为 a ,最后一站下车的人数是 m(全部下车)。试问 x 站开出时车上的人数是多少?
输入格式
输入只有一行四个整数,分别表示始发站上车人数 a,车站数 n,终点站下车人数 m 和所求的站点编号 x。
输出格式
输出一行一个整数表示答案:从 x 站开出时车上的人数。
输入输出样例
输入
5 7 32 4
输出
13
说明/提示
对于全部的测试点,保证1≤a≤20,1≤x≤n≤20,1≤m≤2×104。
#include <iostream> using namespace std; int a,n,m,x; int as[25]; int bs[25]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>a>>n>>m>>x; //起始a,n个车站,m下车 as[1]=as[2]=1; as[3]=2; for(int i=4;i<=20;i++){ as[i]=as[i-1]+as[i-2]-1; } bs[1]=bs[2]=bs[3]=0; bs[4]=1; for(int i=4;i<=20;i++){ bs[i]=bs[i-1]+bs[i-2]+1; } int b=0; for(int i=1;i<=20;i++){ if(as[n-1]*a+bs[n-1]*i==m){ b=i; break; } } cout<<as[x]*a+bs[x]*b; return 0; }