【作业向】程序设计思维与实践 Week11作业

♔A 必做题11-1

♔Problem

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

♔Input

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

♔Output

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

♔Example

♔Input

50 10

♔Output

8

♔解题思路

计算题，单词别打错就行23333

♔代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#include<map>
#define ll long long
using namespace std;
double f=200.0,p,g,q;

int main()
{
        int i,a,b;
        scanf("%d%d",&a,&b);
        p=1.0+b/100.0;
        g=0.0+a;
        for(i=1;i<=20;i++,f*=p)
        {
                q+=g;
               if(q>=f)
               {printf("%d",i);
                return 0;}
        }
        printf("Impossible");
	return 0;
}

♔B 必做题11-2

♔Problem

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

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

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

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

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

1. 不需要旋转则输出 0
2. 顺时针旋转 90° 则输出 1
3. 顺时针旋转 180° 则输出 2
4. 顺时针旋转 270° 则输出 3

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

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

♔Input

第一行为一个整数 n

接下来的 n 行同学们已经列好的 01 方阵；

再接下来的 n 行表示老师希望的的 01 方阵。

♔Output

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

♔Example

♔Input

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

♔Output

1

♔解题思路

使用循环进行比较即可，注意循环条件的设置，详见代码。

♔代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#include<map>
#define ll long long
using namespace std;
ll a[25][25],b[25][25];
ll n;

int main()
{
	ll i,j;
	ll flag=0;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++) scanf("%lld",&a[i][j]);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++) scanf("%lld",&b[i][j]);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(b[i][j]!=a[i][j])
			{
				flag=1;
				break;
			}
		}
	if(!flag)
	{
		printf("0");
		return 0;
	}
	flag=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(b[i][j]!=a[n-j+1][i])
			{
				flag=1;
				break;
			}
		}
	if(!flag)
	{
		printf("1");
		return 0;
	}
	flag=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(b[i][j]!=a[n-i+1][n-j+1])
			{
				flag=1;
				break;
			}
		}
	if(!flag)
	{
		printf("2");
		return 0;
	}
	flag=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(b[i][j]!=a[j][n-i+1])
			{
				flag=1;
				break;
			}
		}
	if(!flag)
	{
		printf("3");
		return 0;
	}
	printf("-1");
	return 0;
}

♔C 必做题11-3

♔Problem

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

密文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

明文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

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

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

♔Input

一行，给出密文，密文不为空，而且其中的字符数不超过 200。

♔Output

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

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

♔Examples

♔Input

NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX

♔Output

IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES

♔解题思路

可以看到密文和明文的位移为5，以此规律对于大写字母进行变换，其他字符原样输出。

♔代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#include<map>
#define ll long long
using namespace std;
char c;
int a;
int main()
{
	c=getchar();
	while(c!='\n')
	{
		if(c<='Z' && c>='A') c='A'+(c-'A'-5+26)%26;
		printf("%c",c);
		c=getchar();
	}
	return 0;
}

♔D 必做题11-4

♔Problem

东东和他的女朋友(幻想的)去寿司店吃晚餐(在梦中)，他发现了一个有趣的事情，这家餐厅提供的 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

♔解题思路

使用sum1和sum2记录连续出现的1，2的个数，答案只能是min(sum1,sum2)*2，记录答案的最大值即可。

♔代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#include<map>
#define ll long long
using namespace std;
int no,pr,sum1,sum2,n,ans;

int main()
{
    int i;
    scanf("%d",&n);
    scanf("%d",&pr);
    if(pr==1) sum1++;
    else sum2++;
    for(i=2;i<=n;i++)
    {
        scanf("%d",&no);
        if(no==pr)
        {
             if(no==1) sum1++;
             else sum2++;
        }
        else
        {
            if(no==1) sum1=1;
             else sum2=1;
        }
        ans=max(ans,min(sum1,sum2)*2);
        pr=no;
    }
    printf("%d",ans);
    return 0;
}

♔E 选做题11-1 东东与ATM

♔Problem

一家银行计划安装一台用于提取现金的机器。
机器能够按要求的现金量发送适当的账单。
机器使用正好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

对于每组数据，程序将在下一行中将结果打印到单独一行上的标准输出中。

♔Examples

♔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

♔Output

735
630
0
0

♔解题思路

经典的背包问题，将每种金额按照二进制拆分，然后转化为0/1背包。

♔代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#include<map>
#define ll long long
using namespace std;
int f[100005],a[1000005];
int maxn,n,cnt;

int main()
{
	int i,j;
	int d,k;
	while(scanf("%d%d",&maxn,&n)!=EOF)
	{
		cnt=0;
		memset(f,0,sizeof(f));
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&k,&d);
			for(j=1;j<=k;j*=2)
			{
				a[++cnt]=d*j;
				k-=j;
			}
			if(k!=0) a[++cnt]=d*k;
		}
		for(i=1;i<=cnt;i++)
		{
			for(j=maxn;j>=a[i];j--)
			{
				f[j]=max(f[j],f[j-a[i]]+a[i]);
			}
		}
		printf("%d\n",f[maxn]);
	}
	return 0;
}

♔F 选做题11-2 东东开车了

♔Problem

东东开车出去泡妞(在梦中)，车内提供了 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

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

♔Examples

♔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

♔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

♔解题思路

本题需要在求解背包问题的过程中进行路径的记录，当f[j]<=f[ j-a[i] ]+a[i]时，pre[i] [j]置为1，在输出时逆序输出即可。

♔代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#include<map>
#define ll long long
using namespace std;
int f[100005],a[25],xu[25],pre[25][100005];
int maxn,n,cnt;


int main()
{
	int i,j;
	while(scanf("%d%d",&maxn,&n)!=EOF)
	{
		cnt=0;
		memset(f,0,sizeof(f));
		memset(pre,0,sizeof(pre));
		for(i=1;i<=n;i++) scanf("%d",&a[i]);
		for(i=1;i<=n;i++)
			for(j=maxn;j>=a[i];j--)
			{
				if(f[j]<=f[j-a[i]]+a[i])
				{
					f[j]=f[j-a[i]]+a[i];
					pre[i][j]=1;
				}
			}
		j=maxn,i=n;
		while(j && i>=1)
		{
			if(pre[i][j])
			{
				xu[++cnt]=a[i];
				//printf("%d ",a[i]);
				j-=a[i];
			}
			i--;
		} 
		for(i=cnt;i>=1;i--) printf("%d ",xu[i]);
		printf("sum:%d\n",f[maxn]);
	}
	return 0;
}