1065: Operations on Grids
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 17 Solved: 4
[Submit][Status][Web
Board]
Description
你有一个 9 位数字串,现在你把这个数字的每一位填到 3 × 3 格子上。如果数
字是 123456789,那么填到 3 × 3 格子上会得到:
123
456
789
现在你可以对这 3 × 3 格子做四种操作:
现在给你这个 9 位数字串,你需要做 a 次左旋转操作, b 次右旋转操作, c 次
横向翻转操作,d 次纵向翻转操作,这些操作之间的先后顺序随便你定。
问最终能得到多少种不同的 3 × 3 格子。两个 3 × 3 格子视为不同,当且仅当
格子中存在至少有一个位置上的数字不同。
Input
输入第一行是一个整数 T,表示有 T 组数据。
每组数据有两行。第一行为一个 9 位的数字串。第二行包含 4 个整数 a, b, c 和
d (0 <= a, b, c, d <= 2)。
Output
对于每组测试数据,输出一个整数表示最终能得到多少种不同的 3 × 3 格子。
Sample Input
1
000000000
1 2 1 2
Sample Output
1
这题开始想了很久——在不知道有几层循环的条件下如何进行暴力?后来发现用字母来代表操作可以比较方便。比如例子1 2 1 2那么每一个数字代表有几次操作,化为字符串就是abbcdd。那么还有一个问题:如何枚举所有情况?用next_permutation即可。忘记把转化的字符串要初始化,WA一次+TLE两次....还有最后改为do-while才AC,while是WA,因为next会直接跳到第二种情况,因此用do-while
代码:
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
inline string zuo(const string &s)
{
string t="";
t=t+s[2]+s[5]+s[8]+s[1]+s[4]+s[7]+s[0]+s[3]+s[6];
return t;
}
inline string you(const string &s)
{
string t="";
t=t+s[6]+s[3]+s[0]+s[7]+s[4]+s[1]+s[8]+s[5]+s[2];
return t;
}
inline string heng(const string &s)
{
string t="";
t=t+s[2]+s[1]+s[0]+s[5]+s[4]+s[3]+s[8]+s[7]+s[6];
return t;
}
inline string zong(const string &s)
{
string t="";
t=t+s[6]+s[7]+s[8]+s[3]+s[4]+s[5]+s[0]+s[1]+s[2];
return t;
}
inline string fx(const string &s,string p)//按照字符串进行操作
{
int len=(int)s.size();
for (int i=0; i<len; i++)
{
switch(s[i])
{
case 'a':p=zuo(p);break;
case 'b':p=you(p);break;
case 'c':p=heng(p);break;
case 'd':p=zong(p);break;
}
}
return p;
}
int main(void)
{
ios::sync_with_stdio(false);
string s,t;
int i,T,a,b,c,d;
cin>>T;
while (T--)
{
cin>>s;
cin>>a>>b>>c>>d;
t="";
for (i=0; i<a; i++)//四个for来转化字符串
{
t=t+'a';
}
for (i=0; i<b; i++)
{
t=t+'b';
}
for (i=0; i<c; i++)
{
t=t+'c';
}
for (i=0; i<d; i++)
{
t=t+'d';
}
set<string>sist;
do
{
sist.insert(fx(t,s));
}while (next_permutation(t.begin(),t.end()));
cout<<sist.size()<<endl;
}
return 0;
}