11730 - Number Transformation
此題可採用 shortest paths, BFS
shortest paths => 建圖 => 找最短路徑
BFS => 從起點作 BFS 擴張 => 到達終點即為解答
以下為 BFS 程式碼
//11730 - Number Transformation (by ms0472904) BFS
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
bool isp[1001]; // isp(rime)
int p[168]={2}, k=1; // p(rime) k=> p 個數
int pf[1001][12]; // p(rime) f(actor) pf[n][0] 放個數
struct data {
int n, s; // n(um) s(tep)
} d;
void make_p() { // 建立質數表(線性篩法)
int i, j;
for (i=3; i<32; i+=2) {
if (!isp[i]) {
for (j=i*i; j<1001; j+=i+i)
isp[j] = true;
p[k++] = i;
}
}
for (; i<1001; i+=2)
if (!isp[i])
p[k++] = i;
}
void make_pf() { // 建立質因數表
int i, j;
for (i=3; i<1001; i++) {
int n = i, N=(int)(sqrt((double)i)+0.00001);
for (j=0; p[j]<=N && j<k && n!=1; j++) {
bool ck=0;
while (n % p[j] == 0)
n /= p[j], ck=1;
if (ck)
pf[i][++pf[i][0]] = p[j];
}
if (n != 1 && n != i)
pf[i][++pf[i][0]] = n;
}
}
int main() {
int n, m, c=1, ans[1001];
make_p();
make_pf();
while (~scanf("%d%d", &n, &m), n) {
memset(ans, 127, sizeof(ans)); // initialize
queue <data> q;
d.s = 0;
d.n = n;
q.push(d);
ans[n] = 0;
while (!q.empty()) { // BFS
data f = q.front();
q.pop();
if (f.n == m)
break;
for (int i=1; i<=pf[f.n][0]; i++) {
if (f.n + pf[f.n][i] > m || f.s + 1 >= ans[f.n + pf[f.n][i]])
continue;
ans[f.n + pf[f.n][i]] = f.s + 1;
d.n = f.n + pf[f.n][i];
d.s = f.s + 1;
q.push(d);
}
}
if (ans[m]>1000) // >1000 代表數字沒變過(當然只要比最大值大的數都可以)
printf("Case %d: -1\n", c++);
else
printf("Case %d: %d\n", c++, ans[m]);
}
}
11725 - Colorful Board
作法 : 可採用 DP + bitmask(inker 學長的專長)
遞迴方式大概是：
- 先用 dfs 搜出狀態
- 再用另一個 dfs 搜出轉移狀態
- 最後將方法數加過去
實作方法：用 bitmask 省記憶體
//11725 - Colorful Board (by ms0472904) DP + bitmask
#include <iostream>
using namespace std;
#define MOD 1000000007
bool cant[7][7];
int n, m, dp[7][1<<14 + 1], ans, nowm, bitmask, transfer_add, bm2;
int even[7] = {0, 2, 4, 6, 8, 10, 12};
void dfs_transfer(int k) {
if (k>n)
dp[nowm+1][bm2] = (dp[nowm+1][bm2] + transfer_add) % MOD;
else if (cant[nowm+1][k]) {
bm2 &= ~(3 << even[k]);
dfs_transfer(k+1);
} else {
bool status[4] = {1, 1, 1, 1};
if (k && !cant[nowm+1][k-1])
status[(bm2 >> even[k-1]) & 3] = false;
if (!cant[nowm][k])
status[(bitmask >> even[k]) & 3] = false;
for (int i=0; i<4; i++)
if (status[i]) {
bm2 &= ~(3 << even[k]);
bm2 |= (i << even[k]);
dfs_transfer(k+1);
}
}
}
void dfs_n(int k) {
if (k>n) {
if (!nowm)
dp[nowm][bitmask] = 1;
if (nowm == m)
ans = (ans + dp[nowm][bitmask]) % MOD;
else if (transfer_add = dp[nowm][bitmask])
dfs_transfer(0);
}
else if (cant[nowm][k]) {
bitmask &= ~(3 << even[k]);
dfs_n(k+1);
} else {
bool status[4] = {1, 1, 1, 1};
if (k && !cant[nowm][k-1])
status[(bitmask >> even[k-1]) & 3] = false;
for (int i=0; i<4; i++)
if (status[i]) {
bitmask &= ~(3 << even[k]);
bitmask |= (i << even[k]);
dfs_n(k+1);
}
}
}
int main() {
int t, c=1, k, a, b;
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &m, &n, &k);
memset(cant, ans=bitmask=bm2=0, sizeof(cant));
memset(dp, 0, sizeof(dp));
bool ngm = (n>m);
while (k--) {
scanf("%d%d", &a, &b);
(ngm ? cant[b-1][a-1] : cant[a-1][b-1]) = true;
}
if (ngm)
swap(n, m);
for (nowm=0; nowm<=m; nowm++)
dfs_n(0);
printf("Case %d: %d\n", c++, ans);
}
}
d665. 數字合併
只能說 nanj 太威了
詳細證明目前無法得知
//d665. 數字合併 (by nanj0178)
#include <iostream>
using namespace std ;
int main() {
long long total, i, n, a, b;
cin >> n >> a;
total=0;
for (i=2; i<=n; i++) {
cin >> b;
if (a > b)
total += a;
else
total += b;
a = b;
}
cout << total << endl;
}
763 - Fibonacci numbers
用大數可以 AC 但太麻煩
在此提供一種作法
先推出運算通則
假如有 11 將它變成 100
假如有 2 將它變成 10 (2 * 1 = 2 = 1 * 2)
假如有 20 將它變成 101 (20 => 12 (利用 2 反推) => 101 (利用 1))
假如有 200 將它變成 1001 (200 => 111 (利用 1 反推) => 1001 (利用 1))
用這 4 通則不斷更新，直到無法再更新即得解答
//763 - Fibonacci numbers (by ms0472904)
#include <iostream>
#include <string>
using namespace std;
int main() {
string s1, s2;
int i, j, c=1;
while (cin >> s1 >> s2) {
if (c>1)
putchar(10);
c++;
int a[200] = {0};
for (i=0; i<s1.size(); i++)
a[s1.size()-i-1] = s1[i]-48;
for (i=0; i<s2.size(); i++)
a[s2.size()-i-1] += s2[i]-48;
int size = max(s1.size(), s2.size());
while (1) {
bool ck=0;
for (i=size-1; i>=0; i--) {
if (a[i] >= 2) {
if (!i) // 2
a[i+1] ++;
else if (i == 1) // 3
a[i+1] ++, a[i-1]++;
else // 4
a[i+1] ++, a[i-2]++;
if (i == size-1)
size ++;
a[i] -= 2;
ck = true;
} else if (i && a[i]==1 && a[i-1]==1) { // 1
a[i+1] ++;
a[i]--;
a[i-1]--;
if (i==size-1)
size ++;
ck = true;
}
}
if (!ck) // 發現無法再更新就跳出
break;
}
for (i=size-1; i>=0; i--)
putchar(a[i]+48);
putchar(10);
}
}
820 - Internet Bandwidth
典型的 max flow 問題 只是單純考演算法 在此用的是 adjacency lists
//820 - Internet Bandwidth (by ms0472904) max flow
#include <iostream> // adjacency lists
#include <list>
#include <queue>
#define MAX 101
using namespace std ;
inline void getd (int &d) { // 輸入優化
char ch;
while (!isdigit(ch=getchar()));
d = 0;
do {
(d *= 10) += ch - '0';
} while (isdigit(ch=getchar()));
}
struct edge {
int to, cap ;
list <edge> ::iterator cdir; // 指向反向邊
} et;
int s, e;
int cap[MAX][MAX]; // 記算容量和
bool visited[MAX];
list <edge> em[MAX];
list <edge> ::iterator from[MAX];
bool BFS() { // BFS 擴張樹
memset(visited, 0, sizeof(visited));
queue <int> q;
q.push(s);
visited[s] = true;
while (!q.empty() && !visited[e]) {
for (list <edge> ::iterator i = em[q.front()].begin(); i != em[q.front()].end(); i++) {
if (!visited[i -> to] && i -> cap > 0) {
visited[i -> to] = true;
q.push(i -> to);
from[i->to] = i;
}
}
q.pop();
}
return visited[e];
}
int main() {
int n, m, a, b, w, i, j, c=1;
while (getd(n), n) {
getd(s);
getd(e);
getd(m);
for (i=1; i<=n; em[i++].clear()); // initialize
memset(cap, 0, sizeof(cap));
while (m--) {
getd(a);
getd(b);
getd(w);
if (a > b)
swap(a, b);
cap[a][b] += w; // 可能有很多邊
}
for (i=1; i<=n; i++) // 建邊
for (j=i+1; j<=n; j++)
if (cap[i][j]) { // 邊存在
a = i;
et.cap = cap[i][j];
et.to = j;
em[a].push_back(et);
list <edge> ::iterator ti = --em[a].end();
swap(a, et.to);
et.cdir = ti;
em[a].push_back(et);
ti -> cdir = --em[a].end();
}
int ans = 0;
while (BFS()) { // Edmond-Karp Algorithm
list <edge> ::iterator tb = from[e];
int mn = min(1000000, tb->cap);
while (tb -> cdir -> to != s) {
tb = from[tb -> cdir -> to];
mn=min(mn, tb->cap);
}
tb = from[e];
while (1) {
tb -> cdir -> cap += mn;
tb -> cap -= mn;
if (tb -> cdir -> to == s)
break;
tb = from[tb -> cdir -> to];
}
ans += mn;
}
printf("Network %d\nThe bandwidth is %d.\n\n", c++, ans);
}
}
d668. 奇怪的老闆
這題是典型的區間極值問題
解法是必須建表
當然不能建 O(n^2) 的表 => 會 TLE
據我所知作法有 2 種 => RMQ, 線段樹
事實上 2 個做法有異曲同工之妙
差別在於
RMQ => 迴圈建表
線段樹 => 遞迴建表
RMQ : 建一個表(數字代表第幾項)
1~1+1, 1~1+2, 1~1+4, 1~1+8 ....
2~2+1, 2~2+2, 2~2+4, 2~2+8 ....
.
.
.
例如要找 1~5 那就查 1~3, 4~ 5
線段樹：大致做法如圖
//d668. 奇怪的老闆 (by ms0472904) 線段樹
#include <iostream>
using namespace std;
int a[50001];
struct trees {
int mx, mn;
} tree[150000];
inline void set_tree(int left, int right, int k) { // 建樹
if (left == right)
tree[k].mn = tree[k].mx = a[left];
else {
int middle = (left + right) >> 1;
set_tree(left, middle, k*2);
set_tree(middle+1, right, k*2+1);
tree[k].mx = max(tree[2*k].mx, tree[2*k+1].mx);
tree[k].mn = min(tree[2*k].mn, tree[2*k+1].mn);
}
}
inline trees inquire(int left, int right, int k, int miniq, int maxiq) { // 查詢
if (left==miniq && right==maxiq)
return tree[k];
int middle = (left + right) >> 1;
if (middle >= maxiq)
return inquire(left, middle, k*2, miniq, maxiq);
else if (middle < miniq)
return inquire(middle+1, right, k*2+1, miniq, maxiq);
else {
trees q = inquire(left, middle, 2*k, miniq, middle);
trees w = inquire(middle+1, right, 2*k+1, middle+1, maxiq);
q.mx = max(q.mx, w.mx);
q.mn = min(q.mn, w.mn);
return q;
}
}
int main() {
int n, m, q, w;
while (~scanf("%d", &n)) {
getd(m);
for (int i=1; i<=n; i++)
scanf("%d", &a[i]);
set_tree(1, n, 1);
while (m--) {
scanf("%d%d", &q, &w);
if (q>w)
swap(q, w);
trees ans = inquire(1, n, 1, q, w);
printf("%d\n", ans.mx - ans.mn);
}
}
}