200pt( 略)
500pt
Problem Statement
You are playing a game with a NxN grid of letters. The goal of the game is to spell out a N-letter word somewhere on the grid either horizontally from left to right or vertically from top to bottom. To achieve this, you will perform a series of moves. On each move, you can swap either two rows or two columns of the grid.
You are given a vector <string> grid containing the initial state of the grid. The j-th character of the i-th element of grid is the letter at row i, column j. The word you must spell is given to you in the string word. All letters in word are distinct. Note that lowercase and uppercase versions of the same letter are considered different in this problem, so 'A' and 'a' are distinct. Return the minimal number of moves required to spell the given word on the grid, or -1 if it is impossible.
Definition
Class:
WordsGame
Method:
minimumSwaps
Parameters:
vector <string>, string
Returns:
int
Method signature:
int minimumSwaps(vector <string> grid, string word)
(be sure your method is public)
Constraints
-
word will contain between 1 and 50 letters ('a'-'z', 'A'-'Z'), inclusive.
-
All characters in word will be distinct.
-
The number of elements in grid will be equal to the length of word.
-
The length of each element of grid will be equal to the length of word.
-
Each element of grid will contain only letters ('a'-'z', 'A'-'Z').
首先考虑到只有当前行或者列包含所有word中的char 才可能通过调换得到word ，而且调换并不影响各个行列的内容，因此首先排序判等。
问题转化为word的一个permutation 最少通过几次调换可以得到word
在permutation中，有cyclic representation的概念 ：
例如 word = “abcd” sword = “adbc”即 要将 1423 转换为 1234
那么1是一个cycle 423是一个cycle
要打破一个cycle 则需要元素- 1 次操作，我们要得到的即为所有cycle都为长度1
因此算法为：
#define REP(i,n) for(int (i)=0;i<n;i++)
template<class T> void getMin(T& a,T b){if(b<a)a=b;}
template<class T> void getMax(T& a,T b){if(b>a)a=b;}
int N ;
#define inf 99999999
string target;
int cacl2(string str){
vector<int> vec(N);
REP(i,N) vec[i] = target.find(str[i]);
int ans=0;
REP(i,N){
int cnt=0;
int next = i;
if(vec[next] != -1){
while(vec[next] != -1){
int tmp = next;
next = vec[next];
vec[tmp] = -1;
cnt ++;
}
cnt --;
}
ans+=cnt;
}
return ans;
}
int cacl(string str){
map<char,int> mp;
REP(i,N)mp[str[i]] = i;
bool flag = true;
int ans = 0 ;
while(true){
flag = true;
REP(i,N){
if(str[i] != target[i]){
str[mp[target[i]]] = str[i];
mp[str[i]] = mp[target[i]];
str[i] = target[i];
flag = false;
ans++;
}
}
if(flag) break;
}
return ans;
}
class WordsGame
{
public:
int minimumSwaps(vector <string> grid, string word)
{
N = word.size();
string sword = word;
target = word;
sort(sword.begin(),sword.end());
int ans = inf;
REP(i,N){
string str= grid[i];
string sstr = str;
sort(sstr.begin(),sstr.end());
if(sstr == sword)
getMin(ans,cacl2(str));
}
REP(i,N)
{
string str = "" ;
REP(j,N)str+= grid[j][i];
string sstr = str;
sort(sstr.begin(),sstr.end());
if(sstr == sword)
getMin(ans,cacl2(str));
}
if(ans==inf)return -1;
return ans;
}
1000pt
Problem Statement
You have a piece of paper with exactly D positions laid out in a horizontal row. Each position looks like the following:
_
|_|
|_|
There are 7 line segments in each position, and each line segment can hold exactly one match. Matches cannot be placed anywhere except on the line segments.
You are given an integer
N containing exactly D digits (with no leading zeroes). Spell out the number using matches on the paper. Each digit must occupy a single position. The following diagram shows how each digit should be formed:
_ _ _ _ _ _ _ _
0 - | | 1 - | 2 - _| 3 - _| 4 - |_| 5 - |_ 6 - |_ 7 - | 8 - |_| 9 - |_|
|_| _| |_ _| | _| |_| | |_| _|
After you lay out the initial arrangement, you are allowed to move up to
K matches. You cannot discard matches or add new matches. After you make all your moves, the final arrangement must be valid (as described above) and the integer formed by the arrangement must contain the same number of digits as the original integer. Leading zeroes are allowed. Return the number of distinct integers that can be formed in this manner. Note that the original integer counts toward the total because it always obtainable by making 0 moves.
Definition
Class:
NumbersAndMatches
Method:
differentNumbers
Parameters:
long long, int
Returns:
long long
Method signature:
long long differentNumbers(long long N, int K)
(be sure your method is public)
Constraints
-
N will be between 1 and 10^18 - 1, inclusive.
-
K will be between 1 and 126, inclusive.
Examples
0)
10
1
Returns: 4
Here you can compose numbers 10, 19, 16 and 70:
_ _
| | | -----> | | |
_| |_| _| |_|
_ _
| | | -----> | |_|
_| |_| _| _|
_ _
| | | -----> | |_
_| |_| _| |_|
_ _ _
| | | -----> | | |
_| |_| | |_|
1)
23
1
Returns: 4
This time it's possible to compose 22, 23, 25 and 33.
2)
66
2
Returns: 15
Here you can move up to 2 matches, so quite a lot of numbers can be composed. Note that you are allowed to move a match from one digit to another one, so, for example, it's possible to compose 38. However, you can't discard a match or add a new match, so, for example, you can't compose 55 or 88.
3)
888888888
100
Returns: 1
You are allowed to move a lot of matches, but still it's only possible to compose 888888888.
4)
444444444444444444
2
Returns: 1
Given that at most 2 matches can be moved, only the initial number can be composed.
7段码的题，首先用数组记录10个数字的七段码，这样比较两个数字需要移动的火柴个数只需要比较七个位子上两者的关系即可。而后考虑执行到第k个数字时候，已经添加了inc个火柴，减去了dec个火柴，那么要求这个数字的改变能得到的数字数目只需要枚举变成10个数字即可，最终如果inc和dec相等则满足题意。因此用dp备忘录或者使用递推来求解，显然递推的效率更高但不容易想到下面是代码
回朔+memo
Code Snippet
typedef long long int64;
typedef vector<int> VI;
typedef vector<string> VS;
#define REP(i, n) for (int i = 0; i < (n); ++i)
template<class T> inline void checkmin(T &a,const T &b) { if (b<a) a=b; }
template<class T> inline void checkmax(T &a,const T &b) { if (b>a) a=b; }
int dis[10][7]={
{1,1,1,0,1,1,1},{0,0,1,0,0,1,1},
{1,0,1,1,1,0,1},{1,0,1,1,0,1,1},
{0,1,1,1,0,1,0},{1,1,0,1,0,1,1},
{1,1,0,1,1,1,1},{1,0,1,0,0,1,0},
{1,1,1,1,1,1,1},{1,1,1,1,0,1,1}
};
int K,N,A[30];
int64 memo[30][128][128];
int64 solve(int depth,int inc,int dec){
if(depth == N)return inc==dec?1:0;
if(memo[depth][inc][dec] != -1)return memo[depth][inc][dec];
memo[depth][inc][dec]=0;
int64& ret=memo[depth][inc][dec];
REP(i,10){
int more=0,less=0;
REP(j,7){
if(dis[i][j] == 1 && dis[A[depth]][j] == 0)
more++;
if(dis[i][j] == 0 && dis[A[depth]][j] == 1)
less++;
}
if(more+inc>K||dec+less>K) continue;
ret += solve(depth+1,inc+more,less+dec);
}
return ret;
}
class NumbersAndMatches
{
public:
long long differentNumbers(long long _N, int _K)
{
K=_K;N=0;
memset(memo,-1,sizeof(memo));
while(_N>0){
A[N++]=_N%10;_N/=10;
}
return solve(0,0,0);
}
递推的：
typedef long long int64;
typedef vector<int> VI;
typedef vector<string> VS;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define two(X) (1<<(X))
#define contain(S,X) ((S&two(X))>0)
int dis[10][7]={
{1,1,1,0,1,1,1},{0,0,1,0,0,1,1},
{1,0,1,1,1,0,1},{1,0,1,1,0,1,1},
{0,1,1,1,0,1,0},{1,1,0,1,0,1,1},
{1,1,0,1,1,1,1},{1,0,1,0,0,1,0},
{1,1,1,1,1,1,1},{1,1,1,1,0,1,1}
};
int64 dp[128][128];
class NumbersAndMatches
{
public:
long long differentNumbers(long long N, int K)
{
REP(i,K+1)REP(j,K+1) dp[i][j] = !i && !j;
while(N>0){
int now = N%10;N/=10;
for(int i=K;i>=0;i—)//注意计算顺序要从大向小，因为从小向大会更新大的数组值~
for(int j=K;j>=0;j--){
if(dp[i][j]){
int64 x = dp[i][j];
dp[i][j] = 0;
REP(y,10){
int inc=0,dec=0;
REP(z,7) {
if(dis[y][z]==0 && dis[now][z]==1)
dec++;
if(dis[y][z]==1 && dis[now][z]==0)
inc++;
}
if(inc+i>K||dec+j>K)continue;
dp[i+inc][j+dec] += x;
}
}
}
}
int64 ret=0;
REP(i,K+1) ret+=dp[i][i];
return ret;
}