PKU演習問メモ(4/5 part2) - simezi

解説をだらだら書きすぎて（？）記事が長くなってしまったので分割。

No.	Title	分類・解法
1321	棋盘问题	Counting up,DFS
3749	破译密码	String manipulation
3751	时间日期格式转换	String manipulation
1951	Extra Krunch	String manipulation

以下問題概要や解説など。

1321 棋盘问题

問題概要

nxnマスのボードの#の印のついているマスに駒をk個置く。この時どの二つの駒も同じ列または行にないようにする。このような置き方の場合の数を求めよ。

解法

深さ優先探索で一行ずつ置き方を調べていって間に合う。

ソースコード

int n,k,ans;
char bd[8][9];
bool use[8];

void rec(int c,int m)
{
	if(m==k)
	{
		ans++; return;
	}
	if(c==n)return;
	
	rep(i,n)if(!use[i]&&bd[c][i]=='#')
	{
		use[i]=1;
		rec(c+1,m+1);
		use[i]=0;
	}
	rec(c+1,m);
}

int main()
{
	while(cin>>n>>k,~n)
	{
		rep(i,n)cin>>bd[i];
		
		ans=0; fill(use,use+n,0);
		rec(0,0);
		
		cout<<ans<<endl;
	}
	return 0;
}

3749 破译密码

問題概要

シーザー式置換暗号の暗号文が与えられる。これを復号せよ。

解法

5つ前のアルファベットにずらす。

3751 时间日期格式转换

問題概要

yyyy/mm/dd-hh:mn:ssで表された日付時刻をmm/dd/yyyy-hh(0＜h≦12):mn:ss(am|pm)の形式に変換せよ。

解法

無理矢理0を使わない所為で24時間形式で12:30は12時間形式の午後12:30に……
午前11:59→午後12:00→午後12:59→午後01:00ってなるの違和感ありすぎるｗ

パディングの0にも注意。（全然解法を説明していない）

ソースコード

int main()
{
	int cs; cin>>cs;
	while(cs--)
	{
		string buf; cin>>buf;
		
		stringstream ss(buf.substr(11,2));
		int h; ss>>h;
		bool am=1;
		if(h>=12)am=0;
		
		h%=12; if(h==0)h=12;
		cout<<buf.substr(5,5)<<"/"<<buf.substr(0,4)<<"-"
		<<(h<=9?"0":"")<<h<<buf.substr(13)<<(am?"am":"pm")<<endl;
	}
	return 0;
}

一発ACだったんだから、勘違いしないでよね！

1951 Extra Krunch

問題概要

"krunched word"とは母音字が含まれず、かつ同じアルファベットが二度現れない文字列のことである。
一行で与えられた、アルファベット大文字、スペース、区切り文字からなる文字列を"krunched"に変換せよ。ただしスペースに関しては以下の規則を満たす必要がある。

行の最初と最後にスペースは現れない。
区切り文字の直前にスペースは現れない。
スペースは連続しない。

解法

規則にしたがって実装する。区切り文字は複数あることに注意。

ソースコード

int main()
{
	string str,ans;
	getline(cin,str);
	
	bool use[256]={0};
	use['A']=use['E']=use['U']=use['I']=use['O']=1;
	
	fr(i,str)
	{
		if(*i==' ')
		{
			if(!ans.empty()&&*ans.rbegin()!=' ')ans.pb(*i);
		}
		else if(!('A'<=*i&&*i<='Z'))
		{
			if(!ans.empty()&&*ans.rbegin()==' ')*ans.rbegin()=*i;
			else ans.pb(*i);
		}
		else if(!use[*i])
		{
			ans.pb(*i);
			use[*i]=1;
		}
	}
	while(!ans.empty()&&*ans.rbegin()==' ')
	{
		ans.erase(ans.end()-1,ans.end());
	}
	cout<<ans<<endl;
	
	return 0;
}