程序设计思维 week11 作业

A

题意

蒜头君从现在开始工作，年薪 NN 万。他希望在蒜厂附近买一套 6060 平米的房子，现在价格是 200200 万。假设房子价格以每年百分之 KK 增长，并且蒜头君未来年薪不变，且不吃不喝，不用交税，每年所得 NN 万全都积攒起来，问第几年能够买下这套房子？（第一年年薪 NN 万，房价 200200 万）

输入格式
一行，包含两个正整数 N(10 \le N \le 50)N(10≤N≤50)，K(1 \le K \le 20)K(1≤K≤20)，中间用单个空格隔开。

输出格式
如果在第 2020 年或者之前就能买下这套房子，则输出一个整数 MM，表示最早需要在第 MM 年能买下；否则输出"Impossible"。

输出时每行末尾的多余空格，不影响答案正确性

样例输入
50 10
样例输出
8

做法

计算二十年内的每一年的资产和房价。
公式如下
zc=NN*i
fj=(1+KK%)*fj
因此，判断20年内zc是否大于fj，输出年份即可。
否则输出不可能

代码

#include<iostream>
using namespace std;
const int N=1010;
int n,k;
int main()
{
	cin>>n>>k;
	double temp=200,zc=n;
	if(zc>=temp)
		{
			cout<<1<<endl;
			return 0;
		}
	for(int i=2;i<=20;i++)
	{
		temp*=(100+k)/100.0;
		zc+=n;
		//cout<<zc<<" "<<temp<<endl;
		if(zc>=temp)
		{
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<"Impossible"<<endl;	
}

B

题意

蒜头君的班级里有 n^2n
2
个同学，现在全班同学已经排列成一个 n * nn∗n 的方阵，但是老师却临时给出了一组新的列队方案

为了方便列队，所以老师只关注这个方阵中同学的性别，不看具体的人是谁

这里我们用 0 表示男生，用 1 表示女生

现在蒜头君告诉你同学们已经排好的方阵是什么样的，再告诉你老师希望的方阵是什么样的

他想知道同学们已经列好的方阵能否通过顺时针旋转变成老师希望的方阵

不需要旋转则输出 0

顺时针旋转 90° 则输出 1

顺时针旋转 180° 则输出 2

顺时针旋转 270° 则输出 3

若不满足以上四种情况则输出 −1

若满足多种情况，则输出较小的数字

输入格式
第一行为一个整数 nn

接下来的 nn 行同学们已经列好的 0101 方阵；

再接下来的 nn 行表示老师希望的的 0101 方阵。

输出格式
输出仅有一行，该行只有一个整数，如题所示。

数据范围
对于 100%100% 的数据中，1 \leq n \leq 201≤n≤20

输出时每行末尾的多余空格，不影响答案正确性

样例输入
4
0 0 0 0
0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0
样例输出
1

做法

做法非常容易，注意到
旋转90度，对应相应坐标变换为a[i][j]=b[j][n+1-i]；
迭代两次，即可得到分别180和270度时的坐标变换公式。
从上到下依次对应判断是否相应位置值相同即可。

代码

#include<iostream>
using namespace std;
const int N=1010;
int n,k;
int a[N][N],b[N][N];
bool bj;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	cin>>a[i][j];
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	cin>>b[i][j];
	bj=true;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(a[i][j]!=b[i][j])
	{
		bj=false;
		break;
	}
	if(bj==true)
	{
		cout<<0;
		return 0;
	}
	bj=true;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		if(a[i][j]!=b[j][n+1-i])
	{
		bj=false;
		break;
	}
	} 
	if(bj==true)
	{
		cout<<1;
		return 0;
	}
	bj=true;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		if(a[i][j]!=b[n+1-i][n+1-j])
	{
		bj=false;
		break;
	}
	} 
	if(bj==true)
	{
		cout<<2;
		return 0;
	}
	bj=true;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		if(a[i][j]!=b[n+1-j][i])
	{
		bj=false;
		break;
	}
	} 
	if(bj==true)
	{
		cout<<3;
		return 0;
	}
	cout<<-1<<endl;;
}

C

题意

Julius Caesar 曾经使用过一种很简单的密码。对于明文中的每个字符，将它用它字母表中后 55 位对应的字符来代替，这样就得到了密文。比如字符’A’用’F’来代替。如下是密文和明文中字符的对应关系。

密文\text{A B C D E F G H I J K L M N O P Q R S T U V W X Y Z}A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

明文\text{V W X Y Z A B C D E F G H I J K L M N O P Q R S T U}V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

你的任务是对给定的密文进行解密得到明文。

你需要注意的是，密文中出现的字母都是大写字母。密文中也包括非字母的字符，对这些字符不用进行解码。

输入格式
一行，给出密文，密文不为空，而且其中的字符数不超过 200200。

输出格式
输出一行，即密文对应的明文。

输出时每行末尾的多余空格，不影响答案正确性

样例输入
NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX
样例输出
IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES

做法

首先，getline不忽略空格读入。
对于大写字母，只需要-5即可，但由于c++负数取模还是负数，因此，考虑到等价条件，即为+21。

代码

#include<iostream>
using namespace std;
const int N=1010;
int n,k;

int main()
{
	string s;
	getline(cin,s);
	for(auto k:s)
	{
		if(k>='A'&&k<='Z')
		{
			printf("%c",(k-'A'+21)%26+'A');
		}
		else printf("%c",k);
	}
}

D

题意

东东和他的女朋友(幻想的)去寿司店吃晚餐(在梦中)，他发现了一个有趣的事情，这家餐厅提供的 n 个的寿司被连续的放置在桌子上 (有序)，东东可以选择一段连续的寿司来吃

东东想吃鳗鱼，但是东妹想吃金枪鱼。核 平 起 见，他们想选择一段连续的寿司（这段寿司必须满足金枪鱼的数量等于鳗鱼的数量，且前一半全是一种，后一半全是另外一种）我们用1代表鳗鱼，2代表金枪鱼。

比如，[2,2,2,1,1,1]这段序列是合法的，[1,2,1,2,1,2]是非法的。因为它不满足第二个要求。

东东希望你能帮助他找到最长的一段合法寿司，以便自己能吃饱。

Input
输入：
第一行：一个整数n（2≤n≤100000），寿司序列的长度。
第二行：n个整数（每个整数不是1就是2，意义如上所述）

Output
输出：一个整数（代表东东可以选择的最长的一段连续的且合法的寿司）

Examples
Input
7
2 2 2 1 1 2 2
Output
4
Input
6
1 2 1 2 1 2
Output
2
Input
9
2 2 1 1 1 2 2 2 2
Output
6

做法

遍历真个数组，每到一个数字，相应的个数加一。
在边界交换处，判断上一个边界的俩数的个数是否超过原ans。
并清空计数数组。
注意到，以上做法唯一没有考虑到是只要一次边界交换，且边界交换在末尾的情况，eg 1 1 1 1 2；可以发现，若末尾不同，答案至少为2,；
最后特判一下即可

代码

#include<iostream>
using namespace std;
const int N=100010;
int n,k,ans;
int a[N],count[3];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n-1;i++)
	{
		count[a[i]]++;
		if(a[i]!=a[i+1])
		{	
			ans=max(ans,2*min(count[1],count[2]));
			if(a[i]==2)count[1]=0;
			else count[2]=0;
		}
		else if(i==n-1)
		{
			count[a[i]]++;
			ans=max(ans,2*min(count[1],count[2]));
		}
	}
	if(a[n-1]!=a[n])ans=max(ans,2);
	cout<<ans<<endl;
}

E

题意

一家银行计划安装一台用于提取现金的机器。
机器能够按要求的现金量发送适当的账单。
机器使用正好N种不同的面额钞票，例如D_k，k = 1,2,…,N，并且对于每种面额D_k，机器都有n_k张钞票。
例如，
N = 3，
n_1 = 10，D_1 = 100，
n_2 = 4，D_2 = 50，
n_3 = 5，D_3 = 10
表示机器有10张面额为100的钞票、4张面额为50的钞票、5张面额为10的钞票。
东东在写一个 ATM 的程序，可根据具体金额请求机器交付现金。
注意，这个程序计算程序得出的最大现金少于或等于可以根据设备的可用票据供应有效交付的现金。

Input
程序输入来自标准输入。 输入中的每个数据集代表特定交易，其格式为：Cash N n1 D1 n2 D2 … nN DN其中0 <= Cash <= 100000是所请求的现金量，0 <= N <= 10是 纸币面额的数量，0 <= nk <= 1000是Dk面额的可用纸币的数量，1 <= Dk <= 1000，k = 1，N。 输入中的数字之间可以自由出现空格。 输入数据正确。
Output
对于每组数据，程序将在下一行中将结果打印到单独一行上的标准输出中。

Sample Input
735 3 4 125 6 5 3 350
633 4 500 30 6 100 1 5 0 1
735 0
0 3 10 100 10 50 10 10
Sample Output
735
630
0
0

做法

这是一个多重背包问题。
对于每一个现金。
找到不大于此现金的最大的现金组合。
每种支票数量，面额，面额分别对应多重背包问题的最大数量，空间，价值。
采用二进制遍历后即可ac。

代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N=100100;
int n,m,cash;
int f[N];
vector<int>goods;
int main()
{
	while(~scanf("%d",&cash))
	{	memset(f,0,sizeof(f));
		goods.clear();
		scanf("%d",&n);
		int s,v;
		for(int i=1;i<=n;i++)
		{
			scanf("%d %d",&s,&v);
			for(int j=1;j<=s;j*=2)
			{
				s-=j;
				goods.push_back(j*v);
				
			}
			if(s>0)goods.push_back(s*v);
		}
		for(int k=0;k<goods.size();k++)
		for(int j=cash;j>=goods[k];j--)
		{
			f[j]=max(f[j],f[j-goods[k]]+goods[k]);
		}
		cout<<f[cash]<<endl;
	}
}

F

题意

东东开车出去泡妞(在梦中)，车内提供了 n 张CD唱片，已知东东开车的时间是 n 分钟，他该如何去选择唱片去消磨这无聊的时间呢

假设:

CD数量不超过20张
没有一张CD唱片超过 N 分钟
每张唱片只能听一次
唱片的播放长度为整数
N 也是整数
我们需要找到最能消磨时间的唱片数量，并按使用顺序输出答案（必须是听完唱片，不能有唱片没听完却到了下车时间的情况发生）

本题是 Special Judge
Input
多组输入

每行输入第一个数字N, 代表总时间，第二个数字 M 代表有 M 张唱片，后面紧跟 M 个数字，代表每张唱片的时长 例如样例一: N=5, M=3, 第一张唱片为 1 分钟, 第二张唱片 3 分钟, 第三张 4 分钟

所有数据均满足以下条件:

N≤10000
M≤20

Output
输出所有唱片的时长和总时长，具体输出格式见样例

Sample Input
5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2
Sample Output
1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45

做法

0/1背包问题+路径输出。
这里用了一个vector记录路径。
当本次要选取这个物品时，说明背包容量在不大于这个情况下，
其路径为不大于不选这个物品时容量大小下的路径+这个物品。
简单记录后输出即可。

代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N=10010;
int n,m;
int f[N];
vector<int>bj[N];
int main()
{
	while(~scanf("%d",&n))
	{
		scanf("%d",&m);
		for(int i=0;i<=N;i++)bj[i].clear();
		memset(f,0,sizeof(f));
		for(int i=1;i<=m;i++)
		{	int v;
			scanf("%d",&v);
			for(int j=n;j>=v;j--)
			if(f[j-v]+v>=f[j])
			{
				f[j]=f[j-v]+v;
				bj[j]=bj[j-v];
				bj[j].push_back(v);
			}
		}
		for(auto k:bj[n])cout<<k<<" ";
		cout<<"sum:"<<f[n]<<endl;
	}
}