想想接觸ACM已經一年了，參加ACM也半年了。大四隻有少量的課程，一般都準備考研、找工作、實習了。想想我的大學生活俨然已經走過了一半，一年半以來，不說自己大學過得如何，至少做的還不算太差，時間過的真是快啊！想想就算在學校整天玩耍、也沒有多少青春可以揮霍了。是以2017年一定要比2016年付出更多的努力才行，任何東西隻要肯投入，沒有學不會或者做不到的，除非你是無法企及的事。
2017年，相信我會做的更好！
之前隊内打算利用空餘的時間刷網上的poj分類，是以漫漫的求索路又開始了。
初期的題目做得總是很快的，一下就刷完了，在此做個總結….
(1)、枚舉
1、 poj1753Flip Game
題意：一個4*4的方格，每個方格中有一粒棋子，這個棋子一面是白色，一面是黑色。遊戲規則為每次任選16顆中的一顆，把選中的這顆以及它四周的棋子一并反過來，當所有的棋子都是同一個顔色朝上時，遊戲就完成了。現在給定一個初始狀态，要求輸出能夠完成遊戲所需翻轉的最小次數，如果初始狀态已經達到要求輸出0。如果不可能完成遊戲，輸出Impossible。
分析：方法實在太多，随便暴力都能過，利用位運算枚舉16個格子的所有翻轉情況，複雜度為O(16*2^16)。高效一點的辦法就是BFS求取最小的次數，不過這裡可以采用部分枚舉的政策。我們的目标是使得所有格子都相同，隻要枚舉第一行的所有翻轉情況，然後依次判斷第1行至第3行的每個格子，如果要翻轉的話隻能通過下面那個格子來解決，最後判斷第4行格子是否要翻轉即可。當然可以翻轉為白色的和黑色的，是以枚舉兩次就夠了。題目還可以采用高斯消元的辦法，然而這個不會，從書本上了解到的。。。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 6;
const int INF = 0x3f3f3f3f;
int dx[] = {1, 0, 0, 0}, dy[] = {0, 1, -1, 0};
int tmp[N][N], filed[N][N];
void change(int x, int y) {
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
tmp[nx][ny] = !tmp[nx][ny];
}
}
int cal(int f) {
int cnt = 0;
for (int i = 1; i < 4; i++) {
for (int j = 1; j <= 4; j++) {
if (f) {
if (tmp[i][j]) change(i+1, j), cnt++;
}
else {
if (!tmp[i][j]) change(i+1, j), cnt++;
}
}
}
for (int i = 1; i <= 4; i++) {
if (f) {
if (tmp[4][i]) return INF;
}
else {
if (!tmp[4][i]) return INF;
}
}
return cnt;
}
int main() {
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
char c = getchar();
filed[i][j] = c == 'b' ? 1 : 0;
}
getchar();
}
int ans = INF;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 16; j++) {
memcpy(tmp, filed, sizeof(filed));
int t = 0;
for (int k = 0; k < 4; k++)
if (j & (1 << k)) change(1, k+1), t++;
ans = min(ans, t + cal(i));
}
}
ans == INF ? puts("Impossible") : printf("%d\n", ans);
return 0;
}
2、poj2965The Pilots Brothers' refrigerator
題意：一個冰箱上有4*4共16個開關，改變任意一個開關的狀态（即開變成關，關變成開）時，此開關的同一行、同一列所有的開關都會自動改變狀态。要想打開冰箱，要所有開關全部打開才行。求使得冰箱打開至少要改變開關狀态的次數，以及改變哪幾個格子。
分析：不是和上題一樣了，這次有變化了，沒多想，直接暴力過的，利用位運算按次數從小到大枚舉翻轉的子集。當然還是可以BFS求最小次數。
還有很巧妙的方法，從網上了解到的，如果一個格子為+，那麼我們對該格子所在行和列的所有7個格子全部操作一遍，開關本身狀态改變了7次，開關同一行、同一列的開關狀态改變了4次，其他開關狀态改變了2次。(其實也相當于隻改變了這一個格子的狀态)最後統計所有格子的翻轉次數、如果翻轉次數為奇數，那麼相當于操作一次，翻轉偶數次相當于沒翻轉。這樣肯定可以保證次數是最少的。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
using namespace std;
const int N = 4;
int handle[N][N], cntx[N], cnty[N], vis[N][N];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
typedef pair<int, int> p;
vector<p> vec;
bool check(int s) {
for (int i = 0; i < 4; i++) cntx[i] = cnty[i] = 0;
memcpy(vis, handle, sizeof(handle));
vec.clear();
for (int i = 0; i < 16; i++)
if (s & (1 << i)) vec.push_back(p(i/4, i%4));
for (int i = 0; i < vec.size(); i++) {
int x = vec[i].first, y = vec[i].second;
cntx[x]++; cnty[y]++;
vis[x][y] = !vis[x][y];
}
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if ((vis[i][j] + cntx[i] + cnty[j]) & 1) return 0;
printf("%d\n", vec.size());
for (int i = 0; i < vec.size(); i++) printf("%d %d\n", vec[i].first+1, vec[i].second+1);
return 1;
}
int main() {
//freopen("in.txt", "r", stdin);
for (int i = 0; i < 4; i++) {
char s[10];
scanf("%s", s);
for (int j = 0; j < 4; j++) handle[i][j] = s[j] == '+' ? 1 : 0;
}
if (!check(0)) {
int flag = 1, up = 1 << 16;
for (int i = 1; i <= 16 && flag; i++) {
int t = (1 << i) - 1;
while (t < up && flag) {
if (check(t)) flag = 0;
int x = t & -t, y = t + x;
t = ((t & ~y) / x >> 1) | y;
}
}
}
return 0;
}
(2)、貪心
1、poj1328
題意：海岸線是一條無限延伸的直線。陸地在海岸線的一側，而海洋在另一側。每一個小的島嶼是海洋上的一個點。雷達坐落于海岸線上，隻能覆寫d距離，是以如果小島能夠被覆寫到的話，它們之間的距離最多為d。題目要求計算出能夠覆寫給出的所有島嶼的最少雷達數目。
分析：首先按坐标排序，然後我們按照從左至右依次覆寫的順序來求解答案。如何求取最小數目呢?假設從某個小島開始覆寫、要使得數目最小，當然是要使得一個雷達覆寫盡量多的點，覆寫一個小島的話，雷達的橫坐标隻能在x + sqrt(d*d-y*y)的範圍内，是以我們采取貪心的政策、盡量地往右移動雷達坐标以覆寫後面的點，是以假設目前的坐标為x + sqrt(d*d-y*y)，那麼不斷地比較，如果x + sqrt(d*d-y*y) > xi - sqrt(d*d-yi*yi)的話證明可以覆寫到它，但是需要注意的一點是目前的坐标要選取到所有島嶼的x + sqrt(d*d-y*y)最小值，這樣才不會保證往右移動導緻之前的點不在目前的範圍内了。采取這樣的貪心政策可以保證每次覆寫地點最大化。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1010;
struct po{
double x, y;
bool operator < (const po& a)const {
return x == a.x ? y < a.y : x < a.x;
}
}p[N];
int main() {
int ca = 0, n;
double d;
while (scanf("%d %lf", &n, &d), n) {
for (int i = 0; i < n; i++) scanf("%lf %lf", &p[i].x, &p[i].y);
sort(p, p+n);
int ans = 1;
double s = d * d;
if (p[0].y > d) ans = -1;
else {
double t = sqrt(s - p[0].y * p[0].y) + p[0].x;
for (int i = 1; i < n; i++) {
if (p[i].y > d) { ans = -1; break; }
double tmp = sqrt(s - p[i].y * p[i].y), sum = p[i].x + tmp;
if (p[i].x - tmp > t) ans++, t = sum;
else t = min(sum, t);
}
}
printf("Case %d: %d\n", ++ca, ans);
}
return 0;
}
2、 poj2109
題意：給定p和n，求出p^（1/n）。
分析：說實話、不知道這題為什麼被歸到貪心中來了。。。明顯的高精度，直接拿kuangbin的模闆二分求取p的n次方根就行了。但是這題簡直神坑、double可以過，記得在書上看到double的範圍最大到10^308，題目中p最大才10^101而且又是整數，是以不會有精度誤差。直接利用pow(p, 1/n)求就好了。
不過做了這題才知bin神的高精度模闆有多厲害！
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int MAXN = 9999;
const int MAXSIZE = 10;
const int DLEN = 4;
const int INF = 1000000001;
class BigNum
{
public:
BigNum(){ len = 1; memset(a, 0, sizeof(a)); } //構造函數
BigNum(const int); //将一個int類型的變量轉化為大數
BigNum(const char*); //将一個字元串類型的變量轉化為大數
BigNum(const BigNum &); //拷貝構造函數
BigNum &operator=(const BigNum &); //重載指派運算符，大數之間進行指派運算
friend istream& operator>>(istream&, BigNum&); //重載輸入運算符
friend ostream& operator<<(ostream&, BigNum&); //重載輸出運算符
BigNum operator+(const BigNum &) const; //重載加法運算符，兩個大數之間的相加運算
BigNum operator-(const BigNum &) const; //重載減法運算符，兩個大數之間的相減運算
BigNum operator*(const BigNum &) const; //重載乘法運算符，兩個大數之間的相乘運算
BigNum operator/(const int &) const; //重載除法運算符，大數對一個整數進行相除運算
BigNum operator^(const int &) const; //大數的n次方運算
int operator%(const int &) const; //大數對一個int類型的變量進行取模運算
bool operator>(const BigNum & T)const; //大數和另一個大數的大小比較
bool operator>(const int & t)const; //大數和一個int類型的變量的大小比較
void print(); //輸出大數
int a[500]; //可以控制大數的位數
int len; //大數長度
};
//将一個int類型的變量轉化為大數
BigNum::BigNum(const int b) {
int c, d = b;
len = 0;
memset(a, 0, sizeof(a));
while (d > MAXN) {
c = d - (d / (MAXN + 1)) * (MAXN + 1);
d = d / (MAXN + 1);
a[len++] = c;
}
a[len++] = d;
}
//将一個字元串類型的變量轉化為大數
BigNum::BigNum(const char* s) {
int t, k, index, l;
memset(a, 0, sizeof(a));
l = strlen(s);
len = l / DLEN;
if (l % DLEN) len++;
index = 0;
for (int i = l-1; i >= 0; i -= DLEN) {
t = 0;
k = i-DLEN+1;
if (k < 0) k = 0;
for (int j = k; j <= i; j++) t = t * 10 + s[j] - '0';
a[index++] = t;
}
}
//拷貝構造函數
BigNum::BigNum(const BigNum & T) : len(T.len) {
memset(a, 0, sizeof(a));
for (int i = 0; i < len; i++) a[i] = T.a[i];
}
//重載指派運算符，大數之間進行指派運算
BigNum & BigNum::operator = (const BigNum & n) {
len = n.len;
memset(a, 0, sizeof(a));
for (int i = 0; i < len; i++) a[i] = n.a[i];
return *this;
}
//重載輸入運算符
istream& operator >> (istream & in, BigNum & b) {
char ch[MAXSIZE * 4];
in >> ch;
int l = strlen(ch);
int cnt = 0, sum = 0;
for (int i = l-1; i >= 0;) {
sum = 0;
int t = 1;
for (int j = 0; j < 4 && i >= 0; j++, i--, t *= 10) sum += (ch[i] - '0') * t;
b.a[cnt++] = sum;
}
b.len = cnt++;
return in;
}
//重載輸出運算符
ostream& operator << (ostream& out, BigNum& b) {
cout << b.a[b.len - 1];
for (int i = b.len - 2 ; i >= 0 ; i--) {
cout.width(DLEN);
cout.fill('0');
cout << b.a[i];
}
return out;
}
//兩個大數之間的相加運算
BigNum BigNum::operator + (const BigNum & T) const {
BigNum t(*this);
int big= T.len > len ? T.len : len; //位數
for (int i = 0 ; i < big ; i++) {
t.a[i] += T.a[i];
if (t.a[i] > MAXN){
t.a[i + 1]++;
t.a[i] -= MAXN + 1;
}
}
t.a[big] ? t.len = big + 1 : t.len = big;
return t;
}
//兩個大數之間的相減運算
BigNum BigNum::operator - (const BigNum & T) const {
int big;
bool flag;
BigNum t1, t2;
if (*this > T) {
t1 = *this;
t2 = T;
flag = 0;
}
else {
t1 = T;
t2 = *this;
flag = 1;
}
big = t1.len;
for (int i = 0 ; i < big ; i++) {
if(t1.a[i] < t2.a[i]) {
int j = i + 1;
while (t1.a[j] == 0) j++;
t1.a[j--]--;
while(j > i) t1.a[j--] += MAXN;
t1.a[i] += MAXN + 1 - t2.a[i];
}
else t1.a[i] -= t2.a[i];
}
t1.len = big;
while (t1.a[len - 1] == 0 && t1.len > 1) t1.len--, big--;
if (flag) t1.a[big-1] = 0 - t1.a[big-1];
return t1;
}
//兩個大數之間的相乘運算
BigNum BigNum::operator * (const BigNum & T) const {
BigNum ret;
int up, i, j;
int temp, temp1;
for (i = 0 ; i < len ; i++) {
up = 0;
for (j = 0 ; j < T.len ; j++) {
temp = a[i] * T.a[j] + ret.a[i + j] + up;
if (temp > MAXN) {
temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
up = temp / (MAXN + 1);
ret.a[i + j] = temp1;
}
else {
up = 0;
ret.a[i + j] = temp;
}
}
if(up != 0) ret.a[i + j] = up;
}
ret.len = i + j;
while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
return ret;
}
//大數對一個整數進行相除運算
BigNum BigNum::operator / (const int & b) const {
BigNum ret;
int down = 0;
for(int i = len - 1; i >= 0 ; i--) {
ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
}
ret.len = len;
while (ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
return ret;
}
//大數對一個int類型的變量進行取模運算
int BigNum::operator % (const int & b) const {
int d = 0;
for (int i = len-1; i >= 0; i--) d = ((d * (MAXN+1)) % b + a[i]) % b;
return d;
}
//大數的n次方運算
BigNum BigNum::operator ^ (const int & n) const {
BigNum t, ret(1);
if (n < 0) exit(-1);
if (n == 0) return 1;
if (n == 1) return *this;
int m = n, i;
while (m > 1) {
t = *this;
for (i = 1; i << 1 <= m; i <<= 1) t = t * t;
m -= i;
ret = ret * t;
if (m == 1) ret = ret * (*this);
}
return ret;
}
//大數和另一個大數的大小比較
bool BigNum::operator > (const BigNum & T) const {
int ln;
if (len > T.len) return true;
else if (len == T.len) {
ln = len - 1;
while (a[ln] == T.a[ln] && ln >= 0) ln--;
if (ln >= 0 && a[ln] > T.a[ln]) return true;
else return false;
}
return false;
}
//大數和一個int類型的變量的大小比較
bool BigNum::operator > (const int & t) const {
BigNum b(t);
return *this > b;
}
//輸出大數
void BigNum::print() {
cout << a[len - 1];
for(int i = len - 2 ; i >= 0 ; i--) {
cout.width(DLEN);
cout.fill('0');
cout << a[i];
}
cout << endl;
}
int n;
BigNum p;
int cal(int s) {
BigNum t(s), tmp = t ^ n;
return tmp > p ? 0 : 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
while (cin >> n >> p) {
if (p.len == 1 && p.a[0] == 1) { puts("1"); continue; }
int l = 1, r = INF;
while (r - l > 1) {
int m = (r + l) / 2;
if (cal(m)) l = m;
else r = m;
}
printf("%d\n", l);
}
return 0;
}
3、 poj2586
題意：一個公司在12個月中，或固定盈餘s，或固定虧損d.但記不得哪些月盈餘，哪些月虧損，隻能記得連續5個月的代數和總是虧損(<0為虧損)，而一年中隻有8個連續的5個月，分别為1~5，2~6，…，8~12
問全年是否可能盈利？若可能，輸出可能最大盈利金額，否則輸出“Deficit".。
分析：一看12個月，每個月或盈餘s，或虧損d，直接暴力了。。。複雜度才O(2^12*12)。當然是貪心的題，當然要知道采取什麼樣的貪心政策了。首先每個月或虧或損、要使得盈餘最大化，當然虧損的月數盡量少就行了，那麼怎麼處理呢。。其實和第一題有點神似、使得一個虧損月覆寫盡量多的大小為5的連續區間就行了。這樣我們隻需要将虧損月以5為機關盡量安排在右端就行了。這樣隻需要安排兩次就夠了。一次安排幾個月虧損根據s和d來确定，原則是保證這個月是虧損的。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 15;
int sum[N];
int main() {
int s, d;
while (~scanf("%d %d", &s, &d)) {
int up = 1 << 12, ans = -1;
for (int i = 0; i < up; i++) {
for (int j = 1; j <= 12; j++) sum[j] = sum[j-1] + (i & (1 << (j-1)) ? s : -d);
int flag = 1;
for (int j = 5; j <= 12 && flag; j++)
if (sum[j] - sum[j-5] >= 0) flag = 0;
if (flag) ans = max(ans, sum[12]);
}
ans == -1 ? puts("Deficit") : printf("%d\n", ans);
}
return 0;
}
貪心算法的如下：
#include <cstdio>
using namespace std;
int main() {
int s, d;
while (~scanf("%d %d", &s, &d)) {
int cnt = 0;
while (cnt * s - (5 - cnt) * d < 0) cnt++;
cnt--;
int ans = cnt * 2 * s - (5 - cnt) * 2 * d;
if (cnt >= 2) ans += 2 * s;
else ans += cnt * s - (2 - cnt) * d;
ans > 0 ? printf("%d\n", ans) : puts("Deficit");
}
return 0;
}
(3)、遞歸和分治法
這裡分類上面沒給題，自己找了兩個題做做。
1、 poj3768
題意：題目意思就不多說了，根據給定的小圖遞歸地構造大圖。現在給定這個構造地次數，輸出大圖。
分析：遞歸求解，把圖形列印到二維數組中，一行一行輸出，這樣效率最高。主要是要搞清楚遞歸時的坐标變化，以及遞歸求解開始的坐标。卡了我好久，坐标一直沒搞對，其實仔細想想就清楚了。小圖一次構造大圖時，假設此時小圖寬x，那麼大圖中原來坐标差1的現在就差x了。。。
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
struct dir{ int x, y; };
const int N = 3005;
char ans[N][N], tem[7][7];
vector<dir> d;
vector<int> w;
char c;
void dfs(int x, int y, int n) {
if (n == 1) { ans[x][y] = c; return ; }
dfs(x, y, n-1);
for (int i = 0; i < d.size(); i++) dfs(x + d[i].x * w[n-1], y + d[i].y * w[n-1], n-1);
}
int main() {
int n;
while (scanf("%d", &n), n) {
getchar();
for (int i = 1; i <= n; i++) gets(tem[i]+1);
d.clear();
int x, y, flag = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (tem[i][j] != ' ') {
c = tem[i][j];
if (flag) x = i, y = j, flag = 0;
else d.push_back((dir){i-x, j-y});
}
}
}
int q;
scanf("%d", &q);
w.clear();
w.push_back(0); w.push_back(1);
int t = 1;
for (int i = 1; i <= q; i++) t *= n, w.push_back(t);
int a = w[q+1];
for (int i = 1; i <= a; i++) memset(ans[i]+1, ' ', a);
int sx = x, sy = y;
for (int i = 2; i < w.size()-1; i++) sx += (x-1) * w[i];
for (int i = 2; i < w.size()-1; i++) sy += (y-1) * w[i];
dfs(sx, sy, q+1);
for (int i = 1; i <= a; i++) ans[i][a+1] = 0, puts(ans[i]+1);
}
return 0;
}
看到分治法無疑想到了最近點對和逆序數的求解。這裡找了最近點對。
2、 uva10245
題意：題目想必不用多說了，找出n個點中距離最小的兩個點。
分析：分治法的套路都一樣，首先将問題一分為二遞歸求解，之後合并兩個子問題。首先将坐标排序，這個問題中主要是合并。左右各n/2個點，難道需要n*n/4次枚舉求出點對在兩邊時的最小值嗎？剛開始一直在糾結怎麼合并，難道還有什麼沒學過的高效的合并知識？其實沒有。任何高效的算法都是不斷地進行算法優化得來的，即使是新的方法也是這樣。仔細一想我們可以從減少枚舉量出發，既然我們已經求出了使得兩邊的點對最小值d，那麼我們的枚舉量顯然大大減少，對于左端的每個點，我們隻需要考慮離他距離不超過d的點就行了。也許你會想，這樣的優化是不是沒什麼用，但是效率很高，因為要計算的點可以變得很少了，網上有證明，合并的效率可以達到O(n)，不過那樣的話需要對y坐标排序。即使不處理y坐标，效率也很高。
#include <bits/stdc++.h>
using namespace std;
typedef pair<double, double> p;
const int N = 10010;
const double INF = 10010;
const double EPS = 1e-5;
p a[N];
double solve(p* a, int n) {
if (n <= 1) return INF;
int m = n/2;
double d = min(solve(a, m), solve(a+m, n-m));
for (int i = 0; i < m; i++) {
for (int j = m; j < n; j++) {
double dx = a[j].first - a[i].first;
if (dx - d > EPS) break;
double dy = a[j].second - a[i].second;
if (abs(dy) + dx - d > EPS) continue;
d = min(d, sqrt(dx * dx + dy * dy));
}
}
return d;
}
int main() {
int n;
while (scanf("%d", &n), n) {
for (int i = 0; i < n; i++) scanf("%lf %lf", &a[i].first, &a[i].second);
sort(a, a+n);
double ans = solve(a, n);
ans - 10000 > EPS ? puts("INFINITY") : printf("%.4f\n", ans);
}
return 0;
}
(4)、遞推
直接在紫書上面找了兩個簡單題….
1、 uva580
題意：一個序列中每個位置隻包含L和U，如果3個U連續出現就非法，求給定長度的非法串的數量。
分析：這題可以從正反兩面考慮：
① 正面考慮：
設長度為i的序列非法的數目為dp[i],首先，隻要連續出現3個U就非法，我們可以從此處下手。從最特殊的出發，假設一個序列中最左端的三個u的位置為i，i+1，i+2。既然我們已經保證了連續3個U的位置是最左端的，那麼第i-1個位置上面不能出現U，隻能為L了。這樣i-1左邊的序列必然是合法的，數目為2^(i-2) – dp[i-1]，i+2右邊的序列可以随便取，數目為2^(n-i-2)。然後這是乘法原理，數目就是兩個相乘。然後我們隻需要對i進行分類，把全部相加就得到了不合法的數目。
②、反面考慮
長度為i的序列個數為2^i,知道了合法的數目就可以了，直接相減就可以了。
設長度為i的序列合法的數目為dp[i]，有以下三種情況：
1、長度為i-1的合法序列加上字尾L。2、長度為i-2的合法序列加上LU，長度為i-3的合法序列加上LUU。
是以dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
typedef long long LL;
LL dp[N+5];
void predeal() {
for (int i = 3; i <= N; i++) {
dp[i] += 1LL << (i-3);
for (int j = 2; j <= i-2; j++) dp[i] += ((1LL << (j-2)) - dp[j-2]) * (1LL << (i-j-2));
}
}
int main() {
predeal();
int n;
while (scanf("%d", &n) && n) printf("%lld\n", dp[n]);
return 0;
}
總結：從這題可以看出來在動态規劃的遞推過程中，如果設計好了狀态，那麼在遞推時要使得該狀态成立肯定會有一些限制條件的，我們需要細心發掘，第二就是問題的考慮可以從正反面下手，正難則反，正易則正，這大概就是數學思維的美吧。
2、 uva12034
題意：求n個人賽馬時最終名次的種類數%10056，比如說，兩個人賽馬，有三種情況：A第一，B第二；A第二，B第一；AB第一。
分析：很明顯的遞推，設n個人賽馬時的可能性有dp[n]種，那麼第一名有i個人，這時候的方案數就是剩下的n-i個人的方案數即dp[n-i]。則答案為C(n,i)*dp[n-1]，全部相加就好了。
一個題目狀态的定義可能有多種，這題還可以按如下的方式：
n匹馬會排成m排，其實就是求這個可能的排列的數目，定義dp[i][j]表示i匹馬排成j排的數目，那麼第i匹馬可以有j+1種選擇，即目前j排中任意一排，或者i單獨為第一排。
則dp[i][j] = j * dp[i-1][j] + dp[i-1][j-1]。
總結：利用dp解題時，最重要的一步就是找到決策的可能性，即上一階段向這一階段的過渡。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int mod = 10056;
int c[N][N], dp[N];
void predeal() {
dp[0] = dp[1] = 1;
for (int i = 0; i <= 1000; i++) c[i][0] = c[i][i] = 1;
for (int i = 2; i <= 1000; i++)
for (int j = 1; j < i; j++) c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
for (int i = 2; i <= 1000; i++) {
for (int j = 1; j <= i; j++) dp[i] += c[i][j] * dp[i-j], dp[i] %= mod;
}
}
int main() {
predeal();
int t, ca = 0;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
printf("Case %d: %d\n", ++ca, dp[n]);
}
return 0;
}
(5)構造法
1、poj3295
題意：輸入由p、q、r、s、t、K、A、N、C、E共10個字母組成的邏輯表達式，其中p、q、r、s、t的值為1（true）或0（false），即邏輯變量；K、A、N、C、E為邏輯運算符，
K --> and: x && y
A --> or: x || y
N --> not : !x
C --> implies : (!x)||y
E --> equals : x==y
求這個邏輯表達式是否為永真式。
分析：變量最多才5個，暴力枚舉2^5中取值，把輸入的表達式計算出來即可。
其實我也不知道這題為什麼歸類到構造法中了，應該是我對構造法的真正内涵了解不深刻吧…..
#include <cstdio>
#include <utility>
#include <set>
#include <map>
#include <cstring>
using namespace std;
const int N = 1010;
map<char, int> mp;
set<char> a, tmp;
typedef pair<int, int> p;
char s[N];
void init() {
a.clear(); mp.clear();
}
p cal(int i) {
if (a.count(s[i])) return p(mp[s[i]], i+1);
p t = cal(i+1);
if (s[i] == 'N') return p(!t.first, t.second);
p tmp = cal(t.second);
if (s[i] == 'K') return p(t.first && tmp.first, tmp.second);
if (s[i] == 'A') return p(t.first || tmp.first, tmp.second);
if (s[i] == 'C') return p(!t.first || tmp.first, tmp.second);
if (s[i] == 'E') return p(t.first == tmp.first, tmp.second);
}
int main() {
tmp.insert('p'); tmp.insert('q');
tmp.insert('r'); tmp.insert('s');
tmp.insert('t');
while (scanf("%s", s), s[0] != '0') {
init();
int len = strlen(s);
for (int i = 0; i < len; i++)
if (tmp.count(s[i])) a.insert(s[i]);
int flag = 1;
for (int i = 0; i < 1 << a.size() && flag; i++) {
int cnt = 0;
for (set<char>::iterator j = a.begin(); j != a.end(); j++, cnt++) mp[*j] = (i & (1 << cnt)) > 0;
if (!cal(0).first) flag = 0;
}
puts(flag ? "tautology" : "not");
}
return 0;
}
(6)模拟法
模拟題雖然看似簡單，但有時候動則幾百行，那種題完全是鍛煉代碼能力和debug能力的題….簡單的模拟題當然就很水了。。。
這些模拟題都很簡單，就不多說了，随便怎麼來，能A就行。。。
1、 poj1068
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1010;
int a[N], s[N], vis[N];
vector<int> vec, ans;
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
vec.clear(); ans.clear();
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++) {
for (int j = 0; j < a[i] - a[i-1]; j++) vec.push_back(0);
vec.push_back(1);
}
for (int i = 0; i < vec.size(); i++) {
if (vec[i]) {
int cnt = 0;
for (int j = i-1; j >= 0; j--) {
if (!vec[j]) {
cnt++;
if (!vis[j]) { vis[j] = 1; break; }
}
}
ans.push_back(cnt);
}
}
for (int i = 0; i < ans.size(); i++) printf("%d%c", ans[i], i == ans.size()-1 ? '\n' : ' ');
}
return 0;
}
2、 poj2632
#include <cstdio>
#include <utility>
using namespace std;
pair<pair<int, int>, char> robot[110];
char dir[4] = {'E', 'N', 'W', 'S'};
struct instructions {
int order;
char action;
int times;
}ins[110];
int main() {
int t;
scanf("%d", &t);
while (t--) {
int len, wid, n, m;
scanf("%d %d %d %d", &len, &wid, &n, &m);
for (int i = 1; i <= n; i++) scanf("%d %d %c", &robot[i].first.first, &robot[i].first.second, &robot[i].second);
for (int i = 0; i < m; i++) scanf("%d %c %d", &ins[i].order, &ins[i].action, &ins[i].times);
int flag = 1;
for (int i = 0; i < m && flag; i++) {
int a = ins[i].order, b;
if (ins[i].action == 'L') {
for (int x = 0; x < 4; x++)
if (robot[a].second == dir[x]) b = x;
for (int j = 1; j <= ins[i].times % 4; j++)
if (++b > 3) b = 0;
robot[a].second = dir[b];
continue;
}
if (ins[i].action == 'R') {
for (int x = 0; x < 4; x++)
if (robot[a].second == dir[x]) b = x;
for (int j = 1; j <= ins[i].times%4; j++)
if (--b < 0) b = 3;
robot[a].second = dir[b];
continue;
}
if (ins[i].action == 'F') {
for (int j = 1; j <= ins[i].times && flag; j++) {
if (robot[a].second == 'W')
if (--robot[a].first.first < 1) flag = 0;
if (robot[a].second == 'E')
if (++robot[a].first.first > len) flag = 0;
if (robot[a].second == 'S')
if (--robot[a].first.second < 1) flag = 0;
if (robot[a].second == 'N')
if (++robot[a].first.second > wid) flag = 0;
if (! flag) printf("Robot %d crashes into the wall\n", a);
for (int x = 1; x <= n && flag; x++)
if (a != x && robot[a].first == robot[x].first) {
printf("Robot %d crashes into robot %d\n", a, x);
flag = 0;
}
}
}
}
if (flag) puts("OK");
}
return 0;
}
3、1573
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 110;
int vis[N][N];
char mat[N][N];
int n, m;
void init() {
for (int i = 0; i < n; i++) memset(vis[i], 0, 4*m);
}
void dfs(int x, int y, int cnt) {
vis[x][y] = cnt;
int nx = x, ny = y;
if (mat[x][y] == 'E') ny++;
else if (mat[x][y] == 'W') ny--;
else if (mat[x][y] == 'N') nx--;
else nx++;
if (nx < 0 || nx >= n || ny < 0 || ny >= m) printf("%d step(s) to exit\n", cnt);
else if (vis[nx][ny]) printf("%d step(s) before a loop of %d step(s)\n", vis[nx][ny]-1, cnt - vis[nx][ny] + 1);
else dfs(nx, ny, cnt+1);
}
int main() {
int s;
while (scanf("%d %d %d", &n, &m, &s), n) {
init();
for (int i = 0; i < n; i++) scanf("%s", mat[i]);
dfs(0, s-1, 1);
}
return 0;
}
4、2993
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
const int N = 60;
string ans[N];
char s[N];
int main() {
for (int i = 1; i <= 8; i++) {
ans[i] += ' '; ans[i] += '|';
for (int j = 0; j < 8; j++) ans[i] += i & 1 ? (j & 1 ? "...|" : ":::|") : (j & 1 ? ":::|" : "...|");
}
for (int i = 0; i < 2; i++) {
gets(s);
int k, len = strlen(s);
for (int j = 0; j < len; j++)
if (s[j] == ',' && islower(s[j+1])) { k = j+1; break; }
for (int j = 7; j < k; j += 4) ans[s[j+2]-'0'][(s[j+1]-'a'+1)*4-1] = i & 1 ? tolower(s[j]) : s[j];
for (int j = k; j < len; j += 3) ans[s[j+1]-'0'][(s[j]-'a'+1)*4-1] = i & 1 ? 'p' : 'P';
}
puts("+---+---+---+---+---+---+---+---+");
for (int i = 8; i; i--) printf("%s\n+---+---+---+---+---+---+---+---+\n", ans[i].c_str()+1);
return 0;
}
5、2996
這題多說一句，原因是因為做這題時被卡了半個小時。。最後居然是排序函數寫錯了。。感覺我是個腦殘。。都沒往那仔細檢查。。然後在那各種修改還是樣例過不了，其實就隻有排序部分寫錯了。。代碼的bug可能出在任何地方，哪怕是一個變量的定義。。
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
using namespace std;
const int N = 60;
map<char, int> mp;
struct piece{
int r, c, f;
char val;
piece(int r, int c, int f, char v) : r(r), c(c), f(f), val(v) {}
piece() {}
bool operator < (const piece& x) const{
if (f != x.f) return f > x.f;
if (val != x.val) return mp[val] < mp[x.val];
if (f) return r == x.r ? c < x.c : r < x.r;
return r == x.r ? c < x.c : r > x.r;
}
};
char chess[N][N];
vector<piece> ans;
int main() {
mp['K'] = 1; mp['Q'] = 2; mp['R'] = 3; mp['B'] = 4; mp['N'] = 5; mp['P'] = 6;
mp['k'] = 1; mp['q'] = 2; mp['r'] = 3; mp['b'] = 4; mp['n'] = 5; mp['p'] = 6;
gets(chess[0]);
for (int i = 8; i > 0; i--) gets(chess[i]), gets(chess[0]);
for (int i = 1; i <= 8; i++) {
int cnt = 0;
char *p = strtok(chess[i]+1, "|");
while (p) {
++cnt;
if (isalpha(p[1])) ans.push_back(piece(i, cnt, isupper(p[1]) , p[1]));
p = strtok(NULL, "|");
}
}
sort(ans.begin(), ans.end());
int k, cnt = 0;
for (int i = 0; i < ans.size(); i++)
if (!ans[i].f) { k = i; break; }
for (int i = 0; i < k; i++) {
if (cnt++) putchar(',');
else printf("White: ");
if (ans[i].val != 'P') printf("%c", ans[i].val);
printf("%c%d", ans[i].c-1 + 'a', ans[i].r);
}
putchar('\n');
cnt = 0;
for (int i = k; i < ans.size(); i++) {
if (cnt++) putchar(',');
else printf("Black: ");
if (ans[i].val != 'p') printf("%c", toupper(ans[i].val));
printf("%c%d", ans[i].c-1 + 'a', ans[i].r);
}
return 0;
}
我感覺以上的基本算法更多的是一些解題時的基本技巧，比如說遞推、遞歸、構造、模拟，當然也有些算法或者思想，比如說貪心、分治、枚舉。每個部分都有其精華所在，這些東西在競賽中是最常用的。
![DTOJ3312 行走題目題解[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)