week 13 程序设计 必做题

A - TT 的神秘任务1（必做）

Example
Input
8
10 3
100 4
8 7
97 2
8 8
3 10
5 3
1000000000 9
Output
YES
4 2 4
YES
55 5 5 35
NO
NO
YES
1 1 1 1 1 1 1 1
NO
YES
3 1 1
YES
111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111120

解题思路

由于题目多解，所以我们可以用 1 代替奇数， 2代替偶数
分别看看选k-1个奇数和选k-1个偶数后，剩下的是奇数还是偶数
就可以得出解

代码

#include <iostream>
using namespace std;
int T,n,k;
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>k; int t = n;
		if(n<k)
		{
			cout<<"NO"<<endl;
			continue;
		}
		//选奇数  1
		t = n-k+1;
		if(t%2==1 && t>0) {
			cout<<"YES"<<endl;
			for(int i=0;i<k-1;i++) cout<<1<<" ";
			cout<<t<<endl;
			continue;
		}
		t =n - 2*(k-1);
		if(t%2==0 && t>0)
		{
			cout<<"YES"<<endl;
			for(int i=0;i<k-1;i++) cout<<2<<" ";
			cout<<t<<endl;
			continue;
		}
		cout<<"NO"<<endl;
	}
	return 0;
}

B - TT 的神秘任务2（必做）

Example
Input
6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1
Output
10
15
1999999999
113
1000000001
1

解题思路

可知道 1 ---  n中间都是不能整除n的
所以一组的个数为 t=n-1

我们要求第k个不能整除n的
则 a= k / t算出在哪一组
再通过求余数判断他是哪一个

代码

#include <iostream>
using namespace std;
int T,n,k;

int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>k;
		int t= n-1;
		int a= k/t;
		int b= k%t;
		if(b == 0) 
		{
			cout<<a*n-1<<endl;
		}
		else
		{
			cout<<a*n+b<<endl;
		}
	}
 } 

C - TT 的奖励（必做） 动态规划

Sample Input
6
5 1
4 1
6 1
7 2
7 2
8 3
0
Sample Output
4

解题思路

状态 f[b][a] ,表示第b秒第a个位置的拿到的最大猫咪取值
状态转移方程 :  f[b][a] += max(f[b-1][a],f[b-1][a+1],f[b-1][a-1])
但是这题需要从后面往前推得到 f[0][5],表示起始点为5时的最优解
所以 f[b][a] +=max(f[b+1][a],f[b+1][a-1],f[b+1][a+1]);

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int bmax = 1e5+50;
int m,a,b;
int t_end,f[bmax][15];

int main()
{
	while(1)
	{
		cin>>m;
		if(m==0) break;
		memset(f,0,sizeof(f));
		t_end = 0;
		for(int i=1;i<=m;i++)
		{
			cin>>a>>b;
			f[b][a] ++;
			t_end = max(b,t_end);
		}
		for(int i=t_end-1;i>=0;i--)
			for(int j=0;j<=10;j++)
				f[i][j]+=max(f[i+1][j+1],max(f[i+1][j],f[i+1][j-1]));
		cout<<f[0][5]<<endl;
	}
	return 0;
}