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').
首先考慮到只有當(dāng)前行或者列包含所有word中的char 才可能通過調(diào)換得到word ，而且調(diào)換并不影響各個行列的內(nèi)容，因此首先排序判等。
問題轉(zhuǎn)化為word的一個permutation 最少通過幾次調(diào)換可以得到word
在permutation中，有cyclic representation的概念 ：
例如 word = “abcd” sword = “adbc”即 要將 1423 轉(zhuǎn)換為 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段碼的題，首先用數(shù)組記錄10個數(shù)字的七段碼，這樣比較兩個數(shù)字需要移動的火柴個數(shù)只需要比較七個位子上兩者的關(guān)系即可。而后考慮執(zhí)行到第k個數(shù)字時候，已經(jīng)添加了inc個火柴，減去了dec個火柴，那么要求這個數(shù)字的改變能得到的數(shù)字?jǐn)?shù)目只需要枚舉變成10個數(shù)字即可，最終如果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—)//注意計算順序要從大向小，因為從小向大會更新大的數(shù)組值~
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;
}