【复盘】8.3训练：Nordic Collegiate Programming Contest 2020

2023-12-26 16:02:45

A-Array of Discord

题意：
输入一排数字升序排列，是否可以改变其中一个数字的任意一位数字使之不是有顺序的？

正确代码请见官方代码或最后的代码

一开始的思路：

若存在两个相同的数，则第一个加一后输出
若是每个数的位数递增，则输出“impossible”
若存在位数相同的数，讲前面的数字变最大或后面的数字变最小（如1111，1112变为9111，1112 即为变最大）

WA了，因为分类太复杂而不全，代码也无可避免的复杂。
而且：
题目中的sort并未指从小到大或从大到小，即sort是从小到大或从大到小都可以的。
只要存在小，大，小或大，小，大这样的排列，就是不sort的，符合题意。

正确思路：把一个数字变为最大后整体判断一遍是否符合标准，都不符合就把第二数字变为最小判断。

注意：用函数实现不同的功能，方便纠错，且代码简洁清晰。 思路不要太复杂。

官方答案：

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long LL;
const int N=2;
int n, m;
LL w[N];
void out()
{
	for (int i = 1; i <= n; ++i) {
		printf("%lld ", w[i]);
	}
}
LL to_number(string s)
{
	LL res = 0;
	for (int i = 0; i < s.size(); ++i) {
		res = res * 10 + s[i] - '0';
	}
	return res;
}
void to_big(int u)
{
	string s = to_string(w[u]);
	for (int i = 0; i < s.size(); ++i) {
		if (s[i] != '9') {
			s[i] = '9';
			break;
		}
	}
	w[u] = to_number(s);
	return;
}
void to_small(int u)
{
	string s = to_string(w[u]);
	if (s.size() == 1) {
		w[u] = 0;
		return;
	}
	else {
		if (s[0] != '1') {
			s[0] = '1';
		}
		else {
			for (int i = 1; i < s.size(); ++i) {
				if (s[i] != '0') {
					s[i] = 0;
					break;
				}
			}
		}
	}
	w[u] = to_number(s);
}
bool is_sort()
{
	int flag = 1;
	for (int i = 1; i <= n - 1; ++i) {//全都一样也是sort的 
		if (w[i] != w[i + 1]) {
			flag = 0;
			break;
		}
	}
	if (flag) return false;
	flag = 1;
	for (int i = 1; i <= n - 1; ++i) {
		if (w[i] > w[i + 1]) {
			flag = 0;
			break;
		}
	}
	if (flag) return false;
	return true;
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &w[i]);
	}
	for (int i = 1; i <= n; ++i) {
		LL t = w[i];
		to_big(i);
		if (t != w[i] && is_sort()) {
			out();
			return 0;
		}
		w[i] = t;
		to_small(i);
		if (t != w[i] && is_sort()) {
			out();
			return 0;
		}
		w[i] = t;
	}
	puts("impossible");
	return 0;
}

自己按照这个思路写，只过了86%，然后转变了思路，试了试字符串的做法：

字符串长度相同的有可能可改
改完之后判断

代码如下（通过97.73%）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=115;
string a[N];
int n;

string to_big(string str)
{
	for(int i=0;str[i];i++)
	{
		if(str[i]!='9')
		{
			str[i]='9';break;
		}
	}
	return str;
}

string to_small(string str)
{
	if(str.size()==1) str='0';
	else
	{
		if(str[0]!='1') str[0]='1';
		else
		{
			for(int i=1;str[i];i++)
			{
				if(str[i]!='0')
				{
					str[i]='0';break;
				}
			}
		}
	}
	return str;
}

bool is_sort()
{	
	for(int i=0;i<n-1;i++)
	{
		if(a[i].size()==a[i+1].size())
		{
			for(int j=0;a[i][j];j++)
			{				
				if(a[i][j]>a[i+1][j])//出现大的 
				{
					flag=0;break;
				}				
			}
		}
		else if(a[i].size()>a[i+1].size()) 
		{
			flag=1;break;
		}
	}
	if(flag) return 0;
	return 1;
}

void out()
{
	for(int i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	
	//big
	for(int i=0;i<n-1;i++)
	{
		if(a[i].size()==a[i+1].size())
		{
			string t=a[i];//存a[i] 
			a[i]=to_big(a[i]);
			if(is_sort())
			{
				out();return 0;
			}
			a[i]=t;
		}
	}
	
	//small
	for(int i=1;i<n;i++)
	{
		if(a[i].size()==a[i-1].size())
		{
			string t=a[i];
			a[i]=to_small(a[i]);
			if(is_sort())
			{
				out();return 0;
			}
			a[i]=t;
		}
	}
	
	cout<<"impossible"<<endl;
}

但它还是太复杂了。对于本题，只要字符串符合可改的条件，改了是一定符合题意的，即：字符串a，b，若它们：

长度为1，且a不为0，b不为9，则它们可改且符合题意
长度不为1，a第一位不为1，b第一位不为9，可改且符合题意

因此可以简化代码：
~~终于过了~~

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
int n;
string a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	
	int q=0,w=0;
	for(int i=1;i<n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(a[i].size()==a[j].size())
			{
				if(a[i].size()==1&&a[i][0]=='0'&&a[j][0]=='9') continue;
				if(a[i].size()>1&&a[i][0]=='1'&&a[j][0]=='9') continue;
				//可以变化	
				q=i;w=j;break;
				
			}
		}
		if(q!=0) break;
	}
	
	if(q!=0)
	{
		if((a[q][0]!='1'||a[q].size()==1)&&a[q][0]!='0')//后面的可以减 
		{
			a[w][0]=a[q][0]-1;
		}
		else a[q][0]=a[w][0]+1;
		
		for(int i=1;i<=n;i++) cout<<a[i]<<" ";
		
	}
	else cout<<"impossible"<<endl;
	return 0;
}

小总结：

多写函数，分功能
10¹⁵可以用string或long long
理解题意sort，出现拐点才算（所以n==2的永远impossible）

C-Coin Stacks

原题
一个水题。

题意：n堆硬币，每堆a[i]个，能否一次选两堆各拿一个，使之拿完？
如果能就输出yes和拿出的顺序。

思路：

总和为奇数的no
最大的比剩下的所有之和要大的no
其他yes 输出顺序为：每次输出最大的两个的编号，再排序

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=70;
struct node
{
	int num,val;
};
int cmp(node a,node b)
{
	if(a.val!=b.val) return a.val>b.val;//从大到小 
	else return a.num<b.num;
}
node a[N];
int n;
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	int sum=0,maxn=-1;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].val;
		a[i].num=i;
		sum+=a[i].val;
		maxn=max(maxn,a[i].val);
	}
	if(sum%2==1) 
	{
		cout<<"no";
		return 0;
	}
	if(maxn>sum-maxn) 
	{
		cout<<"no";
		return 0;
	}
	cout<<"yes"<<endl;
	while(sum)
	{
		sort(a+1,a+n+1,cmp);
		cout<<a[1].num<<" "<<a[2].num<<endl;
		a[1].val--;
		a[2].val--;
		sum-=2;
	}
	return 0;
}

码农公寓

A-Array of Discord

C-Coin Stacks

相关文章