ICPC 山东省省赛刷题 第十一届山东省大学生程序设计竞赛 ACM省赛 牛客 DGHM题

D Dyson Box

题意：有n步，每一步都会出现一个方块，求重力向下和重力向左的方块掉下去的结果图形的周长。

分析：考虑到每个方块周长为4，如果这个方向下有方块的话，就会-2（因为上下两个方块有一个边重合），如果相邻的左右有比他高的方块，就也会产生重合的边就结果-2。

题解：

#include<bits/stdc  .h>
using namespace std;
int a[200010], b[200010];
int a0[200010], b0[200010];
int ans1=0,ans2=0;
int main()
{
	int n;
	cin >> n;
	for(int i=1;i<=n;i  )
	{
		cin >> a[i] >> b[i];
		a0[a[i]]  ;
		b0[b[i]]  ;
		ans1 =4;
		ans2 =4;
		if(a0[a[i]]>1)
		ans1-=2;
		if(b0[b[i]]>1)
		ans2-=2;
		if(a0[a[i]-1]>=a0[a[i]])
		ans1-=2;
		if(a0[a[i] 1]>=a0[a[i]])
		ans1-=2;
		if(b0[b[i]-1]>=b0[b[i]])
		ans2-=2;
		if(b0[b[i] 1]>=b0[b[i]])
		ans2-=2;
		cout << ans1 << " " << ans2 << endl;
	}
	return 0;
}

G Grade Point Average

题意：给你n个数，求保留k位小数的n个数的平均值，k≤1e5。

分析：使用while循环，数学处理得出小数位数。

题解：

#include<bits/stdc  .h>
using namespace std;
int ar[100010];
int main()
{
	int n;
	int k;
	cin >> n >> k;
	int sum=0.;
	int a;
	for(int i=0;i<n;i  ) 
	{
		cin >> a;
		sum  = a;
	}
	cout << sum/n;
	cout << ".";
	sum%=n;
	while(k--)
	{
		sum*=10;
		cout << sum/n;
		sum%=n;
	}
	return 0;
}

H Adventurer’s Guild

题意：n个怪物，h，s分别是勇士的生命值和耐力值，下面n行分别是怪物能损耗的生命值和能损耗的耐力值还有击败怪物得到的金币。勇士的耐力值可以使用生命值替代，但生命值不可以使用耐力替代，求勇士不被杀死，击败怪物得到的金币最多是多少？

分析：dp存勇士的生命值和耐力值，根据题意，使用dp递推得出答案。

题解：

#include<bits/stdc  .h>
using namespace std;
long long n,dp[350][350];
int ho,so;
int h[1010],s[1010];
long long w[1010];
int main()
{
	cin >> n;
	cin >> ho >> so;
	for(int i=1;i<=n;i  )
	{
		cin >> h[i] >> s[i] >> w[i];
	}
	for(int i=1;i<=n;i  )
	{
		for(int j=ho;j>0;j--)
		{
			for(int k=so;k>=0;k--)
			{
				if(j>h[i]&&j k>h[i] s[i])
				{
					if(k>=s[i])
						dp[j][k] = max(dp[j][k], dp[j-h[i]][k-s[i]] w[i]);
					else 
						dp[j][k] = max(dp[j][k], dp[j-h[i]-(s[i]-k)][0] w[i]);
				}
			}
		}
	}
	cout << dp[ho][so];
	return 0;
}

M Matrix Problem

题意：给你一个矩阵C，C矩阵边界都是0，求矩阵A和矩阵B，要求矩阵A和矩阵B中的1是连通的，且A中每一个数&B中每一个数能得到C矩阵。

分析：一个思维很奇妙的构造题，由于C矩阵的边界是0，可以让A矩阵的最左边一排是1，然后每个奇数行都是1，B矩阵的最右边一排是1，然后每个偶数行都是1，这样再把C矩阵中的1加入A和B中，得出答案。

题解：

#include<bits/stdc  .h>
using namespace std;
char p[510][510];
int a[510][510],b[510][510],c[510][510];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i=1;i<=n;i  )
    {
        for(int j=1;j<=m;j  )
        {
            cin >> p[i][j];
            c[i][j] = p[i][j]-'0';
        }
    }
 
    for(int i=1;i<=n;i  )
    {
        a[i][1] = 1;
    }
    for(int i=1;i<=m;i  )
    {
        b[i][n] = 1;
    }
    for(int i=1;i<=n;i  )
    {
        for(int j=2;j<=m-1;j  )
        {
            if(i%2==1)
            a[i][j] = 1;
            else
            a[i][j] = 0;
        }
    }
    for(int i=1;i<=n;i  )
    {
        for(int j=2;j<=m-1;j  )
        {
            if(i%2==0)
            b[i][j]=1;
            else
            b[i][j]=0;
        }
    }
    for(int i=1;i<=n;i  )
    {
        for(int j=1;j<=m;j  )
        {
            if(c[i][j]==1)
            {
                a[i][j]=1;
                b[i][j]=1;
            }
        }
    }
    for(int i=1;i<=n;i  )
    {
        for(int j=1;j<=m;j  )
        cout << a[i][j];
        cout << endl;
    }
    for(int i=1;i<=n;i  )
    {
        for(int j=1;j<=m;j  )
        cout << b[i][j];
        cout << endl;
    }
    return 0;
}

这篇好文章是转载于：学新通技术网