A
Source
hdu 5432
題意
給你幾個底面是正方形的錐體（金字塔），平放于地面，水準切一刀，問切在多高的位置可以使得分離開的兩部分體積之和相同。
分析
顯然是有單調性的，直接二分高度就好了。
其他人求體積的做法好像很厲害，待會研究下。。
代碼
/*************************************************************************
> File Name: a.cpp
> Author: james47
> Mail:
> Created Time: Sat Sep 12 19:15:02 2015
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps = ;
int T, n;
int a[], b[];
int main()
{
scanf("%d", &T);
while(T--){
scanf("%d", &n);
int mx = ;
for (int i = ; i < n; i++){
scanf("%d", &a[i]);
mx = max(a[i], mx);
}
for (int i = ; i < n; i++) scanf("%d", &b[i]);
long long tot = ; // /3
for (int i = ; i < n; i++) tot += (long long)b[i] * b[i] * a[i];
double l = , r = mx, need = (double)tot/;
while(fabs(r - l) >= eps){
double mid = (l + r) / ;
double sum = ;
for (int i = ; i < n; i++){
if (mid < a[i]){
double h = (double)a[i] - mid;
double w = b[i] * h / a[i];
sum += h * w * w / ;
}
}
if (fabs(sum - need) < eps){ l = mid; break; }
if (sum < need) r = mid;
else l = mid;
}
printf("%d\n", (int)l);
}
return ;
}
B
Source
hdu 5433
題意
直接看題吧。。
分析
沒什麼好說的。。dp[x][y][k]表示走到(x, y)，剩餘k鬥志的最小花費體力，然後相當于求最短路咯。trick在于初始鬥志為0一律無解，即使起終點重合。
代碼
/*************************************************************************
> File Name: b.cpp
> Author: james47
> Mail:
> Created Time: Sat Sep ::
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps = e-;
int dx[] = {, -, , };
int dy[] = {, , , -};
struct node{
int x, y, k;
node(){}
node(int x, int y, int k): x(x), y(y), k(k){}
};
const int mod = *55*55*4;
int T;
char mp[][];
int n, m, tot;
int stx, sty, edx, edy;
double dp[][][];
bool inq[55][][];
node q[mod+5];
int main()
{
scanf("%d", &T);
while(T--){
scanf("%d %d %d", &n, &m, &tot);
for (int i = ; i < n; i ++) scanf("%s", mp[i]);
scanf("%d %d %d %d", &stx, &sty, &edx, &edy);
if (tot == ){
puts("No Answer");
continue;
}
stx --, sty --, edx --, edy --;
for (int i = ; i < n; i++)
for (int j = ; j < m; j++)
for (int k = ; k <= tot; k++){
dp[i][j][k] = e1;
inq[i][j][k] = false;
}
int head = , tail = ;
dp[stx][sty][tot] = .; inq[stx][sty][tot] = true;
q[tail++] = node(stx, sty, tot);
while(head != tail){
node u = q[head++]; if (head == mod) head = ;
for (int i = ; i < ; i++){
int x = u.x + dx[i], y = u.y + dy[i];
if (x < || y < || x >= n || y >= m) continue;
if (mp[x][y] == '#') continue;
// printf("%d\n", u.k);
// printf("%.2f\n", (double)abs(mp[x][y] - mp[u.x][u.y])/u.k);
double tmp = dp[u.x][u.y][u.k] + (double)abs(mp[x][y] - mp[u.x][u.y])/u.k;
if (tmp + eps < dp[x][y][u.k-]){
dp[x][y][u.k-] = tmp;
if (x != edx || y != edy){
if (u.k- != && !inq[x][y][u.k-]){
inq[x][y][u.k-] = true;
q[tail++] = node(x, y, u.k-);
if (tail == mod) tail = ;
}
}
}
}
inq[u.x][u.y][u.k] = false;
}
double ans = e1;
for (int i = ; i <= tot; i++)
ans = min(ans, dp[edx][edy][i]);
if (fabs(ans - e1) < eps) puts("No Answer");
else printf("%.2f\n", ans);
}
return ;
}
C
Source
hdu 5434
題意
出題事故！是以後面的題意沒有卵用：在n*m的棋盤上放小象，小象可以攻擊四個斜方向的位置。如果有公共邊，可以變為合體象，相當于攻擊範圍變小。合法方案要求擺放的象不會互相攻擊，求方案數。n很大，m<=7。
分析
說了一堆實際上都是扯淡。。
因為按照題意這種是合法的，P為象，S不放：
PPP
PSP
PPS
按照資料範圍肯定是狀壓dp然後矩陣快速幂，但是如果這種擺放合法，狀态就比較麻煩，還得記錄連通性。
但實際上不用。。兩行之間隻要考慮斜對着的位置。。(i, j)和(i+1, j+1)同時放，必須有(i+1, j)或者(i, j+1)。大概就是這樣。。題目出得不太對。。
代碼
/*************************************************************************
> File Name: hdu_5434.cpp
> Author: james47
> Mail:
> Created Time: Mon Sep 14 23:00:50 2015
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int mod = ;
const int MAXN = ;
int N;
struct matrix{
int a[MAXN][MAXN];
friend matrix operator *(const matrix& a, const matrix& b){
matrix ret;
for (int i = ; i < N; i++)
for (int j = ; j < N; j++) ret.a[i][j] = ;
for (int i = ; i < N; i++)
for (int j = ; j < N; j++){
for (int k = ; k < N; k++){
ret.a[i][k] = ((long long)a.a[i][j] * b.a[j][k] + ret.a[i][k]) % mod;
}
}
return ret;
}
matrix pow(int exp){
matrix ret, tmp = *this;
for (int i = ; i < N; i++)
for (int j = ; j < N; j++) ret.a[i][j] = i==j;
for (; exp; exp >>= ){
if (exp&) ret = ret * tmp;
tmp = tmp * tmp;
}
return ret;
}
} mat;
int n, m;
bool ok(int x, int y){
for (int i = ; i < m; i++){
if (x&(<<i)){
if (i != ){
if ((y&(<<i-)) && !(y&(<<i)) && !(x&(<<i-))) return ;
}
if (i != m-){
if ((y&(<<i+)) && !(y&(<<i)) && !(x&(<<i+))) return ;
}
}
}
return ;
}
int main()
{
while(scanf("%d %d", &n, &m) != EOF){
N = << m;
for (int i = ; i < N; i++)
for (int j = ; j < N; j++){
if (ok(i, j)) mat.a[i][j] = ;
else mat.a[i][j] = ;
}
mat = mat.pow(n);
int ans = ;
for (int i = ; i < N; i++){
ans += mat.a[i][];
if (ans >= mod) ans -= mod;
}
printf("%d\n", ans);
}
return ;
}
D
Source
hdu 5435
題意
對整數x，定義F(x)為其十進制各位的異或和。給a和b，求a到b所有數的F(x)的和。a和b長度小于100000。
分析
首先容易發現 0 <= F(x) <= 15。然後我們統計[0, A]每個F(x)的值各有多少個x就好了。
做法一：
dp[len][pre]表示[0, 10^len)的數，之前高位異或和為pre，最後得到的異或和為[0..15]的數有多少個。也就是說每個dp[i][j]是一個int數組。時間複雜度O(10^5 * 16 * 9)。然後MLE。。
做法二：
dp[len][pre]表示[0, 10^len)的數，之前高位異或和為pre，最後得到異或和為0的數有多少個。相當于調用16次dfs函數，每次不同的初始pre。時間複雜度相同，記憶體除以16。感覺很對，結果系統測試TLE。。T.T。。出題人太坑爹，case數也需要算到複雜度裡。。
做法三：
可以感覺到上面的做法都不太優。
放棄統計F(x) = [0..15]的數分别有多少個。直接算[0, A]的F(x)的和。
dp[len][pre]表示[0, 10^len)的數，之前高位異或和為pre，最後對答案的貢獻的和。時間複雜度O(10^5*9)，算上25組case也沒有問題。。
然後發現這題的資料有字首0，可能有人會因為這個導緻錯，提醒一下。。
代碼
/*************************************************************************
> File Name: d.cpp
> Author: james47
> Mail:
> Created Time: Sat Sep 12 20:15:56 2015
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = ;
const int mod = +;
int d[maxn];
char sa[maxn], sb[maxn];
int dp[maxn][];
int dfs(int pos, int pre, bool bound){
if (pos == ){ return pre; }
if (!bound && dp[pos][pre] != -) return dp[pos][pre];
int ret = ;
int lim = bound? d[pos]: ;
for (int i = ; i <= lim; i++){
int tmp = dfs(pos-, pre^i, bound&&i==lim);
ret += tmp;
if (ret >= mod) ret -= mod;
}
if (!bound){ dp[pos][pre] = ret; }
return ret;
}
int solve(char* s){
int p = ;
while(s[p] == '0') p++;
int len = strlen(s);
if (p == len) return ;
int i, j;
for (i = len-, j = ; i >= p; i--, j++)
d[j] = s[i] - '0';
j--;
return dfs(j, , true);
}
int cal(char *s){
int len = strlen(s);
int ret = ;
for (int i = ; i < len; i++)
ret ^= s[i] - '0';
return ret;
}
int T;
int main()
{
memset(dp, -, sizeof(dp));
scanf("%d", &T); int cas = ;
while(T--){
scanf("%s %s", sa, sb);
printf("Case #%d: ", ++cas);
int res = (solve(sb) - solve(sa) + cal(sa) + mod) % mod;
printf("%d\n", res);
}
return ;
}
E
Source
hdu 5436
題意
一棵樹，點有權值，葉子和根連通。每次詢問兩個點u和v，問u到v的路徑，路徑上點權和最小，順帶求上面的最大點權。多個最小時，讓路徑上最大點權最大。
分析
可以直接看官方題解。。
最基本的路徑就是走到lca，沒有修改啥的，可以倍增。。
然後可能是u走到葉子，然後從根走到v。
還有一種容易被忘記。。u走到葉子到根，再到另一個葉子，通過這個葉子到v。。
是以我們先dfs一遍，求出每個點到根的距離和，路徑上最大點權等等，并求出到子樹哪個葉子最近，第二次dfs要用。
然後還得再dfs一遍，求每個點離哪個葉子最近，簡單的樹形dp。
也可以直接用Dijkstra。。
代碼很醜。。不推薦看。。
代碼
/*************************************************************************
> File Name: hdu_5436.cpp
> Author: james47
> Mail:
> Created Time: Fri Sep ::
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = ;
const int inf = e9;
struct node{
int w, fa, dep, s, ma, s1, ma1;
} a[maxn];
struct edge{
int v, n;
};
int n, q;
inline void chkmax(int& a, int b){ if (b > a) a = b; }
int o[maxn][];
int p[maxn][];
void work(){
for (int i = ; i <= n; i++){
p[i][] = a[i].fa;
o[i][] = a[a[i].fa].w;
}
//突然發現這裡寫反了。。不過剛好這題不會影響。。
//u的祖先标号都比它小。。
for (int i = ; i <= n; i++)
for (int j = ; j <= ; j++){
p[i][j] = p[p[i][j-]][j-];
o[i][j] = max(o[i][j-], o[p[i][j-]][j-]);
}
}
int esize;
int en[maxn];
edge e[maxn*2];
void addedge(int u, int v){
e[esize].v = v;
e[esize].n = en[u];
en[u] = esize ++;
}
void dfs(int u){
a[u].dep = a[a[u].fa].dep + ;
a[u].s = inf, a[u].ma = ;
a[u].s1 = a[a[u].fa].s1 + a[u].w;
a[u].ma1 = max(a[u].w, a[a[u].fa].ma1);
for (int t = en[u]; t != -; t = e[t].n){
int v = e[t].v;
dfs(v);
if (a[v].s < a[u].s || (a[v].s == a[u].s && a[u].ma < a[v].ma)){
a[u].s = a[v].s; a[u].ma = a[v].ma;
}
}
if (a[u].s == inf) a[u].s = ;
a[u].s += a[u].w;
chkmax(a[u].ma, a[u].w);
}
void dfs1(int u){
int s, ma;
for (int t = en[u]; t != -; t = e[t].n){
int v = e[t].v;
s = a[u].s + a[v].w;
ma = max(a[u].ma, a[v].w);
if (s < a[v].s || (s == a[v].s && ma > a[v].ma)){
a[v].s = s; a[v].ma = ma;
}
dfs1(v);
}
}
inline void update(int &a, int &b, int c, int d){
// printf("%d %d\n", c, d);
if (a > c || (a == c && b < d)) a = c, b = d;
}
int cal(int x, int y, int& t){
t = max(a[x].w, a[y].w);
if (a[x].dep < a[y].dep) swap(x, y);
for (int i = ; i >= ; i--){
if (a[x].dep - (<<i) >= a[y].dep){
chkmax(t, o[x][i]);
x = p[x][i];
}
}
if (x == y) return x;
for (int i = ; i >= ; i--){
if (a[x].dep - (<<i) >= && p[x][i] != p[y][i]){
chkmax(t, o[x][i]);
chkmax(t, o[y][i]);
x = p[x][i]; y = p[y][i];
}
}
chkmax(t, a[a[x].fa].w);
return a[x].fa;
}
int T;
int main()
{
a[].dep = -; a[].fa = ; a[].w = ;
a[].s = a[].s1 = a[].ma1 = ;
scanf("%d", &T);
while(T--){
scanf("%d %d", &n, &q);
a[].fa = ;
esize = ;
memset(en, -, sizeof(int)*(n+));
for (int i = ; i <= n; i++){
scanf("%d", &a[i].fa);
addedge(a[i].fa, i);
// addedge(i, a[i].fa);
}
for (int i = ; i <= n; i++){
scanf("%d", &a[i].w);
}
work(); dfs(); dfs1();
// for (int i = ; i <= n; i++)
// printf("%d %d %d %d\n", a[i].s, a[i].ma, a[i].s1, a[i].ma1);
while(q--){
int u, v;
scanf("%d %d", &u, &v);
int t, t1, lca;
lca = cal(u, v, t1);
t = a[u].s1 + a[v].s1 - a[lca].s1 * + a[lca].w;
// printf("%d %d %d\n", lca, t, t1);
update(t, t1, a[u].s + a[v].s + a[].w, max(a[].w, max(a[u].ma, a[v].ma)));
update(t, t1, a[u].s + a[v].s1, max(a[u].ma, a[v].ma1));
update(t, t1, a[u].s1 + a[v].s, max(a[u].ma1, a[v].ma));
printf("%d %d\n", t, t1);
}
}
return ;
}