2010 校慶盃甲組參考解答
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 但太麻煩
再此提供一種作法
先推出運算通則
1. 假如有 11 將它變成 100
2. 假如有 2 將它變成 10 (2 * 1 = 2 = 1 * 2)
3. 假如有 20 將它變成 101 (20 => 12 (利用2反推) => 101 (利用1))
4. 假如有 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);
}
}
}