2024牛客暑期多校训练营9 - VP记录

A. Image Scaling

签到题，找出举行宽高以后直接除以它们的 \(\gcd\) 使它们互质即可。

（这道题居然会有人又 WA 又 RE，我不说是谁）

#include<cstdio>
#include<cstring>
using namespace std;

const int N=505;
int n,m,x1,y1,x2,y2;
char g[N][N];

int gcd(int x,int y){return y ? gcd(y,x%y) : x;}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%s",g[i]+1);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			if(g[i][j]=='x')
			{
				x1=i,y1=j;
				break;
			}
		if(x1) break;
	}
	for(int i=n;i>=1;i--)
	{
		for(int j=m;j>=1;j--)
			if(g[i][j]=='x')
			{
				x2=i,y2=j;
				break;
			}
		if(x2) break;
	}
	int h=x2-x1+1,w=y2-y1+1;
	int d=gcd(w,h);
	w/=d,h/=d;
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)
			putchar('x');
		putchar('\n');
	}
	return 0;
}

K. Kill The Monsters

贪心，每次一定优先对最大的那个进行操作二，而操作一的次数应当是剩下所有数的最大值。

所以模拟砍最大数的过程（可以用优先队列找最大数），然后统计操作次数并对所有的 \((\max a + alr)\) 取最小值（其中 \(alr\) 表示已经进行过的操作次数）。

因为没有判断全部进行操作二的可能性而 WA 了好多发，最后应当用最终的 \(alr\) 再更新一边答案。

每次操作都将其中一个除以 \(k\)，所以时间复杂度为 \(O(N \log_K \max a_i )\)

还要注意特判 \(k=1\) 的情况，此时无法进行操作二，只需取最大值即可。

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

const int N=1e5+5;
int n;
long long k,a[N];
priority_queue<long long> pq;

int main()
{
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		pq.push(a[i]);
	}
	if(k==1)
	{
		printf("%lld\n",pq.top());
		return 0;
	}
	long long ans=1e18,alr=0;
	while(!pq.empty())
	{
		long long x=pq.top(); pq.pop();
		ans=min(ans,x+alr);
		x/=k;
		if(x>0) pq.push(x);
		alr++;
	}
	printf("%lld\n",min(ans,alr));
	return 0;
}