題目連結
題意:
給一超大整數 N，和幾個int
問這幾個int能不能全部都整除N
可以 -> Wonderful
不行 -> Simple
**************************************************
我的作法:
17 % 5 = ((1%5)*10+7)%5
不需要做大數運算...
小技巧:
[字元轉數字]
字元&15
ex: '8' & 15 = 8
因為數字0到9最多使用4個bit
剛好是字元後4個bit
要看最後4個bit是什麼就是做 &1111 也就是 &15
**************************************************
程式碼:
/* 題目: UVa 11344 - The Huge One
* Language: C++
* Created on: 2016年10月14日
* Author: hanting
*/
#include <iostream>
using namespace std;
string num;
int numMod(int k)
{
int remainder = 0;
for(int i = 0; i < num.size(); i++)
{
remainder *= 10;
remainder += (num[i]&15);
remainder %= k;
}
return remainder;
}
int main()
{
int testCase;
cin >> testCase;
while(testCase--)
{
cin >> num;
int n;
cin >> n;
bool wonderful = true;
for(int i = 0; i < n; i++)
{
int k;
cin >> k;
if(numMod(k) != 0)
{
wonderful = false;
}
}
if(wonderful)
{
cout << num << " - Wonderful." << endl;
}
else
{
cout << num << " - Simple." << endl;
}
}
return 0;
}
題目連結
題意:
給3個字串，分別為
字元表 (會出現的字元)
明文字串
加密的字串
加密的字串解密後一定要出現恰1個明碼字串，
如果 == 1 就是 unique
如果 > 1 就是 ambiguous
如果 == 0 就是 no solution
加密就是指將明文字串的每個字元變成字元表上的下n個字元，
例如:
字元表
uvanice
明文
ane
加密的明文可能是
niu (shift 1)
icv (shift 2)
cea (shift 3)
依此類推
題目就是要求 n 為多少時，可以在加密字串中恰找到1個加密的明文
**************************************************
我的作法:
在母字串中找子字串
在這邊我記錄兩種方法，兩種方法都可以AC
一種是以hash方式，一種是KMP。
hash方式是將子字串丟進hash function得到1個hash值，
再去刷母字串，每次抓連續長度 m 的字串，其中 m = 子字串長度
一樣丟進hash function看是否有等於子字串的hash function。
至於hash function神奇地使用質數次方
f(str) = str[0] * p + str[1] * p^2 + str[2] * p^3 ...
p為質數(但不能為2，測試過會錯，這裡我使用7、37可以過，其他沒有測過)。
這方法神奇就在於字串hash值相同但字串不同的機率非常非常小，
也就是說通常hash值相同都是相同字串！！
KMP的部分可以參考維基百科，
簡單說就是先建立failure function，
在比對過程如果不對的話，子字串的指標要回到fail[前一個字元] + 1的位置，
若子字串的指標到了子字串尾巴，就count++，表示在母字串找到一個子字串了，
接著指標回到fail[前一個字元]+1。
兩種效率都很高，時間複雜度都是(n+m) ，hash效率稍微高一點。
**************************************************
程式碼:
/* 題目: UVa 12604 - Caesar Cipher
* Language: C++
* Created on: 2016年10月12日
* Author: hanting
*/
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
unsigned Base = 7; // 任一質數 // 不能2
int countStr(char *str, char *pat)
{
int cnt = 0;
unsigned baseMax = 1;
unsigned strHash, patHash;
strHash = str[0];
patHash = pat[0];
for(int i = 1; pat[i]; i++)
{
patHash = patHash*Base + pat[i];
strHash = strHash*Base + str[i];
baseMax *= Base;
}
if(patHash == strHash) cnt++;
for(int i = strlen(pat), j = 0; str[i]; i++, j++)
{
strHash = (strHash - baseMax*str[j]) * Base + str[i];
if(strHash == patHash) cnt++;
}
return cnt;
}
int fail[50005];
int KMP(char *str, char *pat)
{
/*build failure function*/
fail[0] = -1;
int j;
for(int i = 1; pat[i]; i++)
{
j = fail[i-1];
while(j >= 0 && pat[i] != pat[j+1])
{
j = fail[j];
}
if(pat[i] == pat[j+1])
{
fail[i] = j+1;
}
else
{
fail[i] = -1;
}
}
/*KMP*/
int cnt = 0;
j = 0;
for(int i = 0; str[i]; i++)
{
while(j >= 1 && str[i] != pat[j])
{
j = fail[j-1] + 1;
}
if(str[i] == pat[j])
{
j++;
}
if(!pat[j])
{
cnt++;
j = fail[j-1]+1;
}
}
return cnt ;
}
char Alphabet[65], plainText[50005], encryptedText[500005];
int ans[50005];
int main()
{
int testCase;
scanf("%d", &testCase);
while(testCase--)
{
int pos[128]; // pos['a'] = 0; pos['w'] = 1;// 表上'a'在第0個位置，下一個是'w'
scanf("%s%s%s", Alphabet, plainText, encryptedText);
for(int i = 0; Alphabet[i]; i++)
{
pos[Alphabet[i]] = i;
}
int AlphaL = strlen(Alphabet);
Alphabet[AlphaL] = Alphabet[0];
Alphabet[AlphaL+1] = 0;
int ansi = 0;
for(int i = 0; i < AlphaL; i++)
{
if(countStr(encryptedText, plainText) == 1)
//if(KMP(encryptedText, plainText) == 1)
{
ans[ansi++] = i;
}
for(int j = 0; plainText[j]; j++)
{
int k = pos[plainText[j]]; // k在table中第幾個
plainText[j] = Alphabet[k+1];
}
}
if(ansi == 0)
{
puts("no solution");
}
else if(ansi == 1)
{
printf("unique: %d\n", ans[0]);
}
else
{
printf("ambiguous: ");
for(int i = 0; i < ansi-1; i++)
{
printf("%d ", ans[i]);
}
printf("%d\n", ans[ansi-1]);
}
}
return 0;
}
題目連結
須注意的是距離 = 0 時直接return
*********************************************
程式碼:
/* 題目: UVa 10245 - The Closest Pair Problem
* Language: C++
* Created on: 2016年10月07日
* Author: hanting
*/
#include <iostream>
#include <vector>
#include <algorithm> //sort, lower_bound
#include <cmath> // sqrt
#include <iomanip> // setprecision
using namespace std;
struct Point
{
double x, y;
Point(double _x = 0, double _y = 0)
{
x = _x;
y = _y;
}
bool operator < (const Point &p)const
{
return x < p.x || (x == p.x && y < p.y);
}
friend istream& operator >> (istream& in, Point &p)
{
in >> p.x >> p.y;
return in;
}
};
bool checkInRange(Point &a, Point &b, double &d) // 判斷是否在需要判斷範圍
{
return a.y + d >= b.y && a.y - d <= b.y;
}
double dis(Point &a, Point &b)
{
double x, y;
x = a.x - b.x;
y = a.y - b.y;
return sqrt(x*x + y*y);
}
double ClosestPair(vector<Point>::iterator Begin, vector<Point>::iterator End)
{
double closest = 0x3fffffff;
if(Begin+1 == End)
{
return closest;
}
else if(Begin + 2 == End)
{
return dis(*Begin, *(Begin+1));
}
double SL, SR;
SL = ClosestPair(Begin, Begin+(End-Begin)/2);
SR = ClosestPair(Begin+(End-Begin)/2, End);
double d, L;
d = min(SL, SR);
if(!d) return 0;
L = (Begin+(End-Begin)/2)->x;
closest = d;
for(vector<Point>::iterator it = lower_bound(Begin, End, L-d);
it != (Begin+(End-Begin)/2); ++it)
{
for(vector<Point>::iterator j = (Begin+(End-Begin)/2), jEnd = lower_bound(Begin, End, L+d);
j != jEnd; j++)
{
if(checkInRange(*it, *j, d))
{
closest = min(closest, dis(*it, *j));
}
}
}
return closest;
}
int main()
{
int pointN;
while(cin >> pointN && pointN)
{
vector<Point> vec;
for(int i = 0; i < pointN; i++)
{
Point tmp;
cin >> tmp;
vec.push_back(tmp);
}
sort(vec.begin(), vec.end());
double ans = ClosestPair(vec.begin(), vec.end());
if(ans < 10000.0)
cout << fixed << setprecision(4) << ans << endl;
else
cout << "INFINITY" << endl;
}
return 0;
}
**************************************************
不用Vector且以scanf, printf輸入輸出，時間較快
/* 題目: UVa 10245 - The Closest Pair Problem
* Language: C++
* Created on: 2016年10月07日
* Author: hanting
*/
#include <iostream>
#include <cstdio>
#include <algorithm> //sort, lower_bound
#include <cmath> // sqrt
#include <iomanip> // setprecision
using namespace std;
struct Point
{
double x, y;
Point(double _x = 0, double _y = 0)
{
x = _x;
y = _y;
}
bool operator < (const Point &p)const
{
return x < p.x || (x == p.x && y < p.y);
}
};
bool checkInRange(Point &a, Point &b, double &d) // 判斷是否在需要判斷範圍
{
return a.y + d >= b.y && a.y - d <= b.y;
}
double dis(Point &a, Point &b)
{
double x, y;
x = a.x - b.x;
y = a.y - b.y;
return sqrt(x*x + y*y);
}
double ClosestPair(Point *Begin, Point *End)
{
double closest = 0x3fffffff;
if(Begin+1 == End)
{
return closest;
}
else if(Begin + 2 == End)
{
return dis(*Begin, *(Begin+1));
}
double SL, SR;
SL = ClosestPair(Begin, Begin+(End-Begin)/2);
SR = ClosestPair(Begin+(End-Begin)/2, End);
double d, L;
d = min(SL, SR);
if(!d) return 0;
L = (Begin+(End-Begin)/2)->x;
closest = d;
for(Point *it = lower_bound(Begin, End, L-d);
it != (Begin+(End-Begin)/2); ++it)
{
for(Point *j = (Begin+(End-Begin)/2), *jEnd = lower_bound(Begin, End, L+d);
j != jEnd; j++)
{
if(checkInRange(*it, *j, d))
{
closest = min(closest, dis(*it, *j));
}
}
}
return closest;
}
int main()
{
int pointN;
Point arr[10005];
while(cin >> pointN && pointN)
{
int arri = 0;
for(int i = 0; i < pointN; i++)
{
double a, b;
scanf("%lf%lf", &a, &b);
arr[arri++] = Point(a, b);
}
sort(arr, arr+arri);
double ans = ClosestPair(arr, arr+arri);
if(ans < 10000.0)
printf("%.4lf\n",ans);
else
puts("INFINITY");
}
return 0;
}
題目連結
作法:
做BFS，紀錄每個點火與人分別要走幾步才能到達該點，
若火走 3 步到(i, j)，人需走4步才到(i, j)，
則該點人不能走，也就是不能加進BFS的queue。
須注意的點是:
1.人與火分開做BFS，即火全部BFS完後，再對人做BFS。
在另一篇前輩的文章說，同時做BFS會讓記憶體跳來跳去，可能造成TLE。
2.火不一定會擴散到整張地圖，
例如:
3 3
J..
###
F..
該點若火沒擴散到，人是可以走的(可以加進人的BFS qeuue中)。
**************************************************
程式碼:
/* 題目: UVa 11624 - Fire!
* Language: C++
* Created on: 2016年10月05日
* Author: hanting
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Coor
{
int i, j;
Coor(int a = 0, int b = 0)
{
i = a;
j = b;
}
};
int main()
{
int testCase;
cin >> testCase;
while(testCase--)
{
int r, c;
cin >> r >> c;
cin.get();
vector<vector<char> > vec(r+2, vector<char>(c+2, 0));
vector<vector<int> > fire(r+2, vector<int>(c+2, -1));
vector<vector<int> > joe(r+2, vector<int>(c+2, -1));
queue<Coor> J, F;
for(int i = 1; i <= r; i++)
{
for(int j = 1; j <= c; j++)
{
cin >> vec[i][j];
if(vec[i][j] == 'J')
{
joe[i][j] = 0;
J.push(Coor(i, j));
}
else if (vec[i][j] == 'F')
{
fire[i][j] = 0;
F.push(Coor(i, j));
}
}
}
Coor pos[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
bool escape = false;
int cnt = 0;
while(F.size())
{
Coor tmp = F.front();
F.pop();
int num = fire[tmp.i][tmp.j];
for(int i = 0; i < 4; i++)
{
int x, y;
x = tmp.i+pos[i].i;
y = tmp.j+pos[i].j;
if(fire[x][y]!=-1) continue;
if(vec[x][y] == '.'|| vec[x][y] == 'J')
{
F.push(Coor(x, y));
fire[x][y] = num+1;
}
}
}
while(J.size() && !escape)
{
Coor tmp = J.front();
J.pop();
int num = joe[tmp.i][tmp.j];
for(int i = 0; i < 4; i++)
{
int x, y;
x = tmp.i+pos[i].i;
y = tmp.j+pos[i].j;
if(vec[x][y] == 0)
{
escape = true;
cnt = num+1;
break;
}
if(joe[x][y]!=-1) continue;
if(vec[x][y] == '.' && (fire[x][y] == -1 || fire[x][y] > num+1))
{
J.push(Coor(x, y));
joe[x][y] = num+1;
}
}
}
if(escape)
{
cout << cnt << endl;
}
else
{
cout << "IMPOSSIBLE" << endl;
}
}
return 0;
}
題目連結
TLE 幾百次後 才發現原因在 board[0][k] 居然不等於 board[k/4][k%4]，
改一下就AC了...害我一直對ida*優化到0秒
/* 題目: UVa 10181 - 15-Puzzle Problem
* Language: C++
* Created on: 2016年10月02日
* Author: hanting
*/
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
int board[4][4];
int table[16][2];
inline bool canSolve(int x)
{
int result = 0;
for(int i = 0; i < 16; i++)
{
for(int j = i+1; j < 16; j++)
{
if(board[j/4][j%4] and board[i/4][i%4] and board[j/4][j%4] < board[i/4][i%4]) result++;
}
}
return (result+x)&1;
}
inline int getStatus()
{
int cnt = 0;
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
if(board[i][j]) cnt += abs(table[board[i][j]][0] - i) + abs(table[board[i][j]][1] - j);
}
}
return cnt;
}
char ansStk[100];
char stk[100];
int stki;
enum
{
UP, DOWN, LEFT, RIGHT
};
int maxd;
int tmpMaxd;
int Htable[4][4][16]; // Htable[i][j][num] // num在[i][j]的cost
bool no;
bool dfs(int depth, int i, int j, int prePos, int status)
{
if(depth > 50)
{
no = true;
return false;
}
if(depth + status*4/3 > maxd)
{
tmpMaxd = min(tmpMaxd, depth + status*4/3);
if(depth == 0) maxd = tmpMaxd;
return false;
}
if(status == 0)
{
stk[stki] = 0;
cout << stk;
return true;
}
if(prePos != UP and i+1 < 4)
{
swap(board[i][j], board[i+1][j]);
stk[stki++] = 'D';
int nextStatus = status;
nextStatus -= Htable[i+1][j][board[i][j]];
nextStatus += Htable[i][j][board[i][j]];
if(dfs(depth+1 , i+1, j, DOWN, nextStatus) ) return true;
stki--;
swap(board[i][j], board[i+1][j]);
}
if(prePos != LEFT and j+1 < 4)
{
swap(board[i][j], board[i][j+1]);
stk[stki++] = 'R';
int nextStatus = status;
nextStatus -= Htable[i][j+1][board[i][j]];
nextStatus += Htable[i][j][board[i][j]];
if(dfs(depth+1 , i, j+1, RIGHT, nextStatus) ) return true;
stki--;
swap(board[i][j], board[i][j+1]);
}
if(prePos != DOWN and i-1 >= 0)
{
swap(board[i][j], board[i-1][j]);
stk[stki++] = 'U';
int nextStatus = status;
nextStatus -= Htable[i-1][j][board[i][j]];
nextStatus += Htable[i][j][board[i][j]];
if(dfs(depth+1, i-1, j, UP, nextStatus) ) return true;
stki--;
swap(board[i][j], board[i-1][j]);
}
if(prePos != RIGHT and j-1 >= 0)
{
swap(board[i][j], board[i][j-1]);
stk[stki++] = 'L';
int nextStatus = status;
nextStatus -= Htable[i][j-1][board[i][j]];
nextStatus += Htable[i][j][board[i][j]];
if(dfs(depth+1 , i, j-1, LEFT, nextStatus) ) return true;
stki--;
swap(board[i][j], board[i][j-1]);
}
maxd = tmpMaxd;
return false;
}
int main()
{
for(int i = 1; i < 16; i++)
{
table[i][0] = (i-1) / 4;
table[i][1] = (i-1) % 4 ;
}
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
for(int k = 1; k < 16; k++)
{
Htable[i][j][k] = abs(table[k][0] - i) + abs(table[k][1] -j);
}
}
}
int n;
cin >> n;
while(n--)
{
int x0, y0;
memset(ansStk, 0, sizeof(ansStk));
int ti = 0;
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 4; j++)
{
cin >> board[i][j];
if(board[i][j] == 0)
{
x0 = i;
y0 = j;
}
}
}
if(!canSolve(x0))
{
cout << "This puzzle is not solvable." << endl;
continue;
}
int status = getStatus();
maxd = status;
no = false;
for(;;)
{
tmpMaxd = 0x3fffffff;
stki = 0;;
if(dfs(0, x0, y0, -1, status))
{
break;
}
if(no)
{
cout << "This puzzle is not solvable." ;
break;
}
}
cout << endl;
}
return 0;
}
