hihocoder[Offer收割]编程练习赛6及参考

时间：2023-02-14 12:15:53

题目1 : Playfair密码表

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi和小Ho经常用Playfair密码表加密自己的代码。 密码表是按以下步骤生成的。

  1. 随机选择一个只包含大写字母的单词S作为密钥。

  2. 将S中的所有字母J替换为字母I。

  3. 将S中的字母依次填写进一个5x5的矩阵，按照从上到下、从左到右的顺序填充格子。填充过程中略过已经在密码表中的字母。

  4. 将’A’-‘I’, ‘K’-‘Z’(除去J之外的所有大写字母)中没有出现在密码表中的大写字母按照字母表顺序填入矩阵剩余的格子中。

举个例子：单词DIJSTRA，替换字母得到DIISTRA；将DIISTRA填入矩阵得到的密码表为(注意第二个I被略过了)：

DISTR
A….
…..
…..
…..
最后将剩余字母填入，得到密码表：

DISTR
ABCEF
GHKLM
NOPQU
VWXYZ
给定作为密钥的单词，你能求出密码表吗？

输入
第1行：一行字符串，只包含大写字母，长度不超过200

输出
共5行，每行5个字母，表示密码表。

样例输入
HIHOCODER
样例输出
HIOCD
ERABF
GKLMN
PQSTU
VWXYZ

#include<iostream>
#include<string>
#include<cstring>
using namespace std;

char Mat[5][5];
void key(string s){
bool tab[26];
int i;
memset(tab,0,26);
for(i = 0; i < s.length(); i++)
    {
if(s[i] == 'J')
        {
            s[i] = 'I';
        }
    }

int j = 0;
for(i = 0; i < s.length(); i++)
    {
if(tab[s[i]-'A'] == 0)
    {
        tab[s[i]-'A'] = 1;
        *((char*)Mat+j++) = s[i];
    }
else
    {
continue;
    }
  }
char c = ' ';
int index = 0;
while(index < 26)
  {
while(tab[index] == 1 && index < 26 || index == 'J'-'A')
    {
      index++;
    }    
    *((char*)Mat+j++) = 'A' + index++; 
  }
}

int main()
{
string k;
cin >> k;
memset(Mat,' ',25);
  key(k);
for(int i = 0;i < 5;i++)
  {
for(int j = 0;j < 5;j++)
cout << Mat[i][j];
cout << endl;
  }
}

题目2 : 修补木桶

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
一只木桶能盛多少水，并不取决于桶壁上最高的那块木板，而恰恰取决于桶壁上最短的那块。

已知一个木桶的桶壁由N块木板组成，第i块木板的长度为Ai。

现在小Hi有一个快捷修补工具，每次可以使用修补工具将连续的不超过L块木板提高至任意高度。

已知修补工具一共可以使用M次(M*L< N)，如何修补才能使最短的那块木板最高呢？

注意: 木板是环形排列的，第N-1块、第N块和第1块也被视为连续的。

输入
第1行：3个正整数，N, M, L。分别表示木板数量，修补工具使用次数，修补工具每次可以同时修补的木板数。 1≤N≤1,000，1≤L≤20，M*L< N

第2行：N个正整数，依次表示每一块木板的高度Ai，1≤Ai≤100,000,000

输出
第1行：1个整数。表示使用修补工具后，最短木块的所能达到的最高高度

样例说明
第一个修补工具覆盖[2 3 4]

第二个修补工具覆盖[5 8 1]

样例输入
8 2 3
8 1 9 2 3 4 7 5
样例输出
7

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define maxn 1005
int n,m,l;
int a[maxn];
int solve(int x)
{
int num=0;
for(int i=0;i<n;i++)
    {
if(a[i]<x)
        {
            num++;
            i+=l-1;
        }
    }
return num;
}
int main()
{
scanf("%d%d%d",&n,&m,&l);
int ans=1e9+7;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);

    }
int st=0,nd=1e9+7;
while(st<=nd)
    {
int mid=(st+nd)/2;
int num=100000;
for(int i=0;i<l;i++){
for(int j=0;j<n-1;j++) swap(a[j],a[j+1]);
            num=min(num,solve(mid));
        }
if(num<=m) st=mid+1;
else nd=mid-1;
    }
printf("%d\n",nd);
}

题目3 : 图像算子

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
在图像处理的技术中，经常会用到算子与图像进行卷积运算，从而达到平滑图像或是查找边界的效果。

假设原图为H × W的矩阵A，算子矩阵为D × D的矩阵Op，则处理后的矩阵B大小为(H-D+1) × (W-D+1)。其中：

B[i][j] = ∑(A[i-1+dx][j-1+dy]*Op[dx][dy]) | (dx = 1 .. D, dy = 1 .. D), 1 ≤ i ≤ H-D+1, 1 ≤ j ≤ W-D+1

给定矩阵A和B，以及算子矩阵的边长D。你能求出算子矩阵中每个元素的值吗？

输入
第1行：3个整数，H, W, D，分别表示原图的高度和宽度，以及算子矩阵的大小。5≤H,W≤60，1≤D≤5，D一定是奇数。

第2..H+1行：每行W个整数，第i+1行第j列表示A[i][j]，0≤A[i][j]≤255

接下来H-D+1行：每行W-D+1个整数，表示B[i][j]，B[i][j]在int范围内，可能为负数。

输入保证有唯一解，并且解矩阵的每个元素都是整数。

输出
第1..D行：每行D个整数，第i行第j列表示Op[i][j]。

样例输入
5 5 3
1 6 13 10 3
13 1 5 6 15
8 2 15 0 12
19 19 17 18 18
9 18 19 5 17
22 15 6
35 -36 51
-20 3 -32
样例输出
0 1 0
1 -4 1
0 1 0

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define maxN 105
#define maxn 5000
#define maxm 5000
int h,w,d;
int a[maxN][maxN];
int b[maxN][maxN];
int c[maxN][maxN];

#define eps 1e-9
double Mat[maxn][maxm];
double V[maxn];
void Gasse(int n,int m)
{
int k=0,i,j;
for(j=0;j<m;j++)
    {
for(i=k;i<n;i++){
if(fabs(Mat[i][j])>eps)
break;
        }
if(i==n) continue;

for(int p=0;p<m;p++) swap(Mat[i][p],Mat[k][p]);
        swap(V[i],V[k]);

double tem=Mat[k][j] ;
for(int p=j;p<m;p++) Mat[k][p]/=tem;
        V[k]/=tem;

for(int p=0;p<n;p++){
if(p!=k&&(fabs(Mat[p][j])>eps)){
                tem=Mat[p][j];
for(int q=0;q<m;q++)Mat[p][q]-=tem*Mat[k][q];
                V[p]-=tem*V[k];
            }
        }
        k++;
    }
}



int main()
{
scanf("%d%d%d",&h,&w,&d);
for(int i=0;i<h;i++)
for(int j=0;j<w;j++) scanf("%d",&a[i][j]);
for(int i=0;i<h-d+1;i++)
for(int j=0;j<w-d+1;j++) scanf("%d",&b[i][j]);
memset(c,0,sizeof(c));
int r=0;
for(int i=0;i<h-d+1;i++)
    {
for(int j=0;j<w-d+1;j++)
        {
for(int p=0;p<d;p++)
for(int q=0;q<d;q++)
                {
//c[i][j]+=a[i+p][j+q]*b[p][q];
                    Mat[r][p*d+q]=a[i+p][j+q];
                }
            V[r]=b[i][j];
            r++;
        }
    }
    Gasse(r,d*d);
for(int i=0;i<d*d;i++)
    {
if(i%d!=0) printf(" ");
if(V[i]>-1e-5) printf("%.0f",(V[i]+1e-6));
else printf("%.0f",(V[i]-1e-6));
if(i%d==d-1) printf("\n");
    }
}

题目4 : 奖券兑换

时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi在游乐园中获得了M张奖券，这些奖券可以用来兑换奖品。

可供兑换的奖品一共有N件。第i件奖品需要Wi张奖券才能兑换到，其价值是Pi。

小Hi使用不超过M张奖券所能兑换到的最大奖品总价值是多少？

输入
第一行两个整数N，M。

接下来N行，每行两个整数Wi，Pi。

对于 50%的数据： 1≤N,M≤1000

对于 100%的数据： 1≤N,M≤105,1≤Pi,Wi≤10。

输出
一行一个整数，表示最大的价值。

样例输入
3 10
2 3
8 8
10 10
样例输出
11 

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
#define maxn 105
int n,m;
int u[maxn][maxn];
int dp[100005];
void change(int w,int p)
{
for(int i=m;i>=w;i--)
    {
        dp[i]=max(dp[i],dp[i-w]+p);
    }
}
int main()
{
scanf("%d%d",&n,&m);
memset(u,0,sizeof(u));
for(int i=0;i<n;i++)
    {
int w,p;
scanf("%d%d",&w,&p);
        u[w][p]++;

    }
memset(dp,0,sizeof(dp));
for(int i=0;i<=10;i++)
    {
for(int j=0;j<=10;j++)
        {
int tem=1;
while(u[i][j]>0)
            {
int num;
if(u[i][j]>=tem) u[i][j]-=tem,num=tem;
else num=u[i][j],u[i][j]=0;
                tem*=2;
                change(i*num,j*num);
            }
        }
    }
printf("%d\n",dp[m]);
}

部分代码取自第三名SCUTE-ZZ
标签：

相关文章