2016-2017 ACM-ICPC, NEERC, Northern Subregional Contest Problem F. Format

题目来源：http://codeforces.com/group/aUVPeyEnI2/contest/229510

时间限制：1s

空间限制：512MB

题目大意：

给定一个字符串，使用%[...]形式将字符串中出现的字符整理到最短和最小(ASCII范围为32~126)，可使用的字符有 '-' '^'

题目解法：模拟整理正的和使用 '^' 取反的两个字符串，输出较短较小的那个（注意当所有字符都存在时，输出%[^!]最小）

样例：

代码：

#include <algorithm>

#include <iostream>

#include <cstring>

#include <vector>

#include <cstdio>

#include <string>

#include <cmath>

#include <queue>

#include <set>

#include <map>

#include <complex>

using namespace std;

typedef long long ll;

typedef long double db;

typedef pair<int,int> pii;

typedef vector<int> vi;

#define de(x) cout << #x << "=" << x << endl

#define rep(i,a,b) for(int i=a;i<(b);i++)

#define all(x) (x).begin(),(x).end()

#define sz(x) (int)(x).size()

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define pi acos(-1.0)

#define mem0(a) memset(a,0,sizeof(a))

#define memf(b) memset(b,false,sizeof(b))

#define ll long long

#define eps 1e-10

#define inf 1e17

#define maxn 101010

int main()

{

	string str;

	bool a[200];

	int b[200];

	//mem0(str);'

	mem0(b);

	int tot=0;

	for(int i=32;i<=126;i++)

	{

		char z=(char)i;

		if(z==' '||z>='0'&&z<='9'||z>='A'&&z<='Z'||z>='a'&&z<='z')

		b[tot++]=i;

	}

	memf(a);

	getline(cin,str);

	//cout<<str;

	int num=0,num1=0,num2=0,num3=0;

	for(int i=0;i<str.size();i++)

	{

		a[(int)str[i]]=true;

//		if(str[i]==' ')num=1;

//		if(str[i]>='0'&&str[i]<='9')num1++;

//		if(str[i]>='A'&&str[i]<='Z')num2++;

//		if(str[i]>='a'&&str[i]<='z')num3++;

	}

//	for(int i=32;i<=126;i++)

//	{

//		printf("%c ",i);

//		cout<<a[i]<<" ";

//	}

	int flag=0;

	for(int i=0;i<tot;i++)

	{

		if(a[b[i]]==false)

		{

			flag=1;

			break;

		}

	}

	if(!flag)

	{

		cout<<"%[^!]"<<endl;

		return 0;

	}

	string ans1="";

	for(int i=0;i<tot;i++)

	{

		int t=i;

		while(a[b[t]])

		{

			t++;

		}

		if(t-i>=3)

		{

			ans1+=(char)(b[i]);

			ans1+="-";

			ans1+=(char)(b[t-1]);

			i=t-1;

		}

		else if(t-i==2)

		{

			ans1+=(char)(b[i]);

			ans1+=(char)(b[i+1]);

			i++;

		}

		else if(t-i==1)

		ans1+=(char)b[i];

	}

	for(int i=0;i<ans1.size();i++)

	{

		if(ans1[i]=='a'&&ans1[i+1]=='-')

		{

			ans1[i]='[';

		}

		if(ans1[i]=='A'&&ans1[i+1]=='-')

		{

			ans1[i]=':';

		}

		if(ans1[i]=='0'&&ans1[i+1]=='-')

		{

			ans1[i]='!';

		}

	}

//	for(int i=0;i<tot;i++)

//	cout<<b[i]<<" ";

	string ans2="^";

	for(int i=0;i<tot;i++)

	{

		int t=i;

		while(a[b[t]]==false&&t<tot)

		{

			t++;

		}

		if(t-i>=3)

		{

			ans2+=(char)(b[i]);

			ans2+="-";

			ans2+=(char)(b[t-1]);

			i=t-1;

		}

		else if(t-i==2)

		{

			ans2+=(char)(b[i]);

			ans2+=(char)(b[i+1]);

			i++;

		}

		else if(t-i==1)

		ans2+=(char)b[i];

	}

	for(int i=0;i<ans2.size();i++)

	{

		if(ans2[i]=='a'&&ans2[i+1]=='-')

		{

			ans2[i]='[';

		}

		if(ans2[i]=='A'&&ans2[i+1]=='-')

		{

			ans2[i]=':';

		}

		if(ans2[i]=='0'&&ans2[i+1]=='-')

		{

			ans2[i]='!';

		}

	}

	if(ans1.length()==ans2.length())

	{

		if(ans1<ans2)

		{

			cout<<"%["<<ans1<<"]"<<endl;

		}

		else

		cout<<"%["<<ans2<<"]"<<endl;

	}

	else

	{

		if(ans1.length()<ans2.length())

		cout<<"%["<<ans1<<"]"<<endl;

		else cout<<"%["<<ans2<<"]"<<endl;

	}

	return 0;

}

巴特西

2016-2017 ACM-ICPC, NEERC, Northern Subregional Contest Problem F. Format

最新文章

热门文章