1004.Link with Equilateral Triangle

题意：
给出一个数字n,代表大等边三角形的边长，由n^2个边长为1的小等边三角形组成。需要将每个小三角的每个顶点用0，1，2填充。问是否能够满足下面所有条件：
（1）大三角形的左边不能有0，右边不能有1，下面不能有2.
（2）对于每个小三角形，它的所有顶点数字之和不能为3的倍数。

思路：
最开始看到两三分钟就有人过了，盲猜就是输出"No"。但是后面为了稳妥起见，还是先简单模拟了一下1，2，3，4的情况，发现都不行，于是猜测答案就是"No"；

代码：

#include 
using namespace std;
typedef long long ll;

inline void solve(){
    int n;
    cin>>n;
    cout<<"No"<>t;
	while(t--){
		solve();
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1006.BIT Subway

题意：
如果这个月花费的总票价x>=100,可以用8折再买一张票。
如果这个月花费的总票价x>=200,可以用5折再买一张票。

想象中的花x:
认为可以分段分区间购买

DLee thinks that he can buy only a part of the ticket instead of the whole ticket at a time. That is, for the ￥10 ticket, DLee thinks he can buy the ￥1.25 part of the ticket first and buy the ￥8.75 part of the ticket then. Under his misunderstanding, he needs to spend 199+1.25∗0.8+8.75∗0.5+8∗0.5=199+1.25*0.8+8.75*0.5+8*0.5=199+1.25∗0.8+8.75∗0.5+8∗0.5=￥208.375. Note that in this example, DLee has to spend ￥1.25 instead of only ￥1 to make x=200。
1

实际花费y：
The real billing method is that only if you have spent enough, you can get the discount, so it will be 199+10∗0.8+8∗0.5=￥211

给出n个票价ai,求出每个样例的理想花费和实际花费。

思路：
模拟，推公式。
y很好想也很好算，x可以模拟算，但是容易绕晕，也可以先计算出总票价x，推出关于ans的式子为：
0<=x<100 ans=x;
100<=x<225 ans=(x-100)*0.8+100;
x>=225 ans=(x-225)*0.5+200.

关于其中一个边界是225，那是因为如果凑出来之后是200的话，那中间的100是用8折得出来的，因此100/0.8=125，再加上原来的100，因此就是225

代码：

#include 
using namespace std;
typedef long long ll;
const int N = 1e5+10;
double a[N];
int n;

inline void solve(){
    scanf("%d",&n);
    double x=0.0,y=0.0;
    for(int i=1;i<=n;i++) {
    	scanf("%lf",&a[i]);
    	x+=a[i];
		//计算y 
    	if(y<100) y+=a[i];
    	else if(y>=100&&y<200) y+=0.8*a[i];
    	else  y+=0.5*a[i];
	}
    if(x>=100&&x<225) x=(x-100)*0.8+100;
	else if(x>=225) x=(x-225)*0.5+200; 
    
    printf("%.3lf %.3lf\n",x,y);
}

int main(){
	int t;
    scanf("%d",&t);
	while(t--){
		solve();
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

1007.Climb Stairs

题意：
在一个关卡中，DLee的初始攻击值为a0,有n层楼，每层都有一个生命值为ai的怪物，DLee只能打生命值要<=他自身攻击值a0的怪物并且打败之后自身攻击值a0+=ai。DLee初始在第0层，他每次可以选择往上跳x层（1<=x<=k），也可以选择下降一层，但是DLee不能去已经去过的楼层，也不能去ai>a0的楼层。问DLee能否打败所有层的怪物顺利通过关卡？

思路：
贪心，dp。
先预处理出dp数组，代表此层初始至少要多大。
从1-n枚举楼层，每次选最前面能吃的。

之前一直用的数组，于是一直T，我真的会谢，最后改成了vector，才过了。呜呜呜！
记住了，下次记住把数组换成vector!!! vector dp(n+1);

代码：

/*
要么最多跳k层，要么下降一层。
如果可以往上一层，那就向上一层。
否则，就必须往上跳，然后一层一层下来收集攻击力来打。 
*/
#include 
using namespace std;
typedef long long ll;
int a0,n,k;

inline void solve(){
    scanf("%d%d%d",&n,&a0,&k);//n层楼，初始攻击值为a0,最多向上跳k层楼  
    vector dp(n+1);
    vector a(n+1);
    dp[0]=0;
    for(int i=1;i<=n;i++){
    	//初始化dp数组
		/*
		如果这一层的怪生命值太高，根本打不过，那就需要先在高层打能打败的怪物获取足够
		的能量之后再一层一层回退过来打。
		如果是直接向上到达的第i层，那么至少需要的就是a[i],
		如果是会出现回退的情况，那么dp[i]=dp[i-1]-a[i] 
		*/ 
		scanf("%d",&a[i]);
    	dp[i]=max(a[i],dp[i-1]-a[i]);
	}
	int now=0,cnt=0;
	for(int i=1;i<=n;i++){//枚举楼层数 
		if(dp[i]<=a0&&now+k>=i){//如果能打并且能够从下面跳上来 
			for(int j=i;j>cnt;j--){//回退的楼层 
				a0+=a[j];//累计攻击值 
			}
			now=cnt+1;//now是打完之后在哪一层 
			cnt=i;//如果这层能打就更新cnt 
		}
	}
	if(cnt==n) cout<<"YES"<