zoj 3622、Magic Number  

水题

先找规律生成区间[1,1<<32-1]内的所有Magic Number，计算出来只有40多个，然后就随便YY了。

void init()
{
	int a[5] = {
		1,2,5,25,125
	};
	ll Max = (1ll<<32)-1;
	for(ll tmp =1; tmp<=Max; tmp *=10)
	{
		for(int i=0; i<5; ++i){
			ll t = tmp * a[i];
			if(t>Max) break;
			g.push_back(t);
		}
	}
	sort(g.begin(), g.end());
}

zoj 3623、Battle Ships  

完全背包

dp[i] 表示is时，能消耗防御塔的值。

状态转移方程：dp[j] = max(dp[j-t[i]] + l[i] * ( j – t[i]))

for(int i=0; i<N; ++i)
			for(int j=t[i]; j<=L+1; ++j)
				dp[j] = max(dp[j], dp[j-t[i]] + l[i]*(j-t[i]));

zoj 3624、Count Path Pair  

题意：从A到D与从B到C的路径中不相交的有多少条。

这题从反面考虑：

Answer   =   SUM(总的情况:C(m+n,m)*C(q+m-p,q) )  -  (A->D 与 B->C路径相交的情况)

然后重点分析：

(A->D 与 B->C路径相交的情况)

看下图：

发现：所有A->D 与B->C相交的情况都可以转化为A->C 与B->D的情况。

所以：Answer  = （ C(m + n, n) * C(m + q - p, q) - C(m + q, q) * C(n + m - p, n)） % 100000007。

注意：计算组合C(n,m)时，由于在计算阶乘的时候用了取模（不取模会溢出），在最后计算(n*...*n-m+1)/ m!时得到将非常不一定是正确结果，所以在这一步中我们可以采用 乘法逆

转化为  （n*..n-m+1） * inv(m!, mod).这样就不会出问题了。

void gcd(ll a, ll b, ll& d, ll& x, ll& y){
	if(!b){
		d = a; x = 1; y = 0;
	}
	else {
		gcd(b, a%b, d, y, x); y -= x*(a/b);
	}
}

ll inv(ll a, ll n){
	ll d, x, y;
	gcd(a, n, d, x, y);
	return d == 1 ? (x+n)%n : -1;	
}

ll C(ll n, ll m){
	ll t1 = 1, t2 = 1;
	for(ll i=1; i<=m; ++i){
		t1 =(t1*(n-i+1)) % mod;
		t2 = (t2*i)% mod;
	}
	return t1*inv(t2, mod) % mod;
}

zoj 3625、Geek‘s Collection  

不会....

zoj 3626、Treasure Hunt I  

树形DP

给定n个点的一棵树，点有点权，边有边权，要求从某点出发，再回到原点能获得的最多点权。

把点权作为价值，边权作为消耗，就是一个树形背包。

把总能量m /= 2 ，就不用考虑再回到原点的部分。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 300;

int dp[maxn+10][maxn+10];
struct node {
    int v,t;
    node(int v=0, int t=0):v(v),t(t) {}
};

vector<node> g[maxn];
int v[maxn];
int n, k , m;

int dfs(int u, int pre)
{
    dp[u][0] = v[u];
    for(int i=0; i<g[u].size(); ++i) {
        node &e = g[u][i];
        if(e.v==pre) continue;
        dfs(e.v, u);
        for(int j=m; j>=e.t; --j) {
            for(int p=j; p>=e.t; --p) {
                dp[u][j] = max(dp[u][j], dp[u][j-p]+dp[e.v][p-e.t]);
            }
        }
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    while(~scanf("%d", &n)) {
        for(int i=1; i<=n; ++i) {
            scanf("%d", &v[i]);
        }
        int x, y, z;
        for(int i=0; i<=n; ++i) g[i].clear();
        for(int i=1; i<n; ++i) {
            scanf("%d%d%d", &x, &y, &z);
            g[x].push_back(node(y,z));
            g[y].push_back(node(x,z));
        }
        scanf("%d%d", &k, &m);
        m /= 2;
        memset(dp, 0, sizeof dp );
        dfs(k, -1);
        int ans = 0;
        for(int i=0; i<=m; ++i) ans = max(ans, dp[k][i]);
        printf("%d\n", ans);
    }
    return 0;
}

zoj 3627、Treasure Hunt II 

贪心

因为每个点的黄金只能走一次，而且有有时间、距离限制，那么一开始的时候肯定可以一起往两边跑，看到黄金就抢，直到超过距离或者时间不够或者到边界不能跑为止。这时候是双核，这样跑肯定最优。然后开始要么往左边一直跑，右边的跟着一直跑，遇到左边界就往右跑，要么就往右边一直跑，左边的跟着一直跑，遇到右边界就往左跑。如此这般就过掉了这题。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>
using namespace std;
typedef long long ll;

const int maxn = 100010;
int n, m, t, p;

ll val[maxn];
ll sum[maxn];

ll func(ll *sum, int p)
{
    ll ans = val[p];
    for(int r=min(n, p+t); r >= p; --r) {
        int l = max(1, r- m);
        l = max(p - t, l);
        int res = t - max(p - l, (r - p));
        int l1 = max(1, l - res);
        int r1 = min(n, r + res);
        ans = max(ans, max(sum[r]-sum[l1-1], sum[r1]-sum[l-1]));
    }
    return ans;
}

int main()
{
    while(~scanf("%d%d", &n, &p)) {
        sum[0] = 0;
        for(int i=1; i<=n; ++i) {
            cin >> val[i];
            sum[i] = sum[i-1] + val[i];
        }
        scanf("%d%d", &m, &t);
        ll ans = func(sum, p);
        for(int i=1; i<=n/2; ++i)
            swap(val[i], val[n+1-i]);
        for(int i=1; i<=n; ++i)
            sum[i] = sum[i-1] + val[i];
        ans = max(ans, func(sum, n+1-p));
        cout<<ans<<endl;
    }
    return 0;
}

zoj 3628、Treasure Hunt III

DP

不会。。。待补

zoj 3629、Treasure Hunt IV

找规律

http://blog.csdn.net/u010304217/article/details/38903983

zoj 3630、Information 

Tarjan

一个有向图，求删除一个点后，是得所有联通分量中点的数量得最大值，最小。

//求图中去掉一个点，求剩余的最大的联通分量中的点的数量。
//删去某点后，最大点数 最小是多少
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;

const int maxn = 110;

vector<int> G[maxn];
int dfn[maxn], low[maxn], belong[maxn], dfs_clock, scc_cnt;
stack<int> S;
int n, m, ans, del, cnt, ct;

void dfs(int u){
    dfn[u] = low[u] = ++dfs_clock;
    S.push(u);
    for(int i=0; i<G[u].size(); ++i){
        int v = G[u][i];
        if(v == del) continue;
        if(!dfn[v]){
            dfs(v);
            low[u] = min(low[u], low[v]);
        }else if(!belong[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]){
        scc_cnt++;
        int s = 0;
        for(;;){
            int x = S.top(); S.pop();
            belong[x] = scc_cnt;
            s++;
            if(x == u) break;
        }
        if(s>1&&s>ct) ct = s;
    }
}

void find_scc(int n){
    dfs_clock = scc_cnt = 0;
    memset(belong, 0, sizeof belong );
    memset(dfn, 0, sizeof dfn );
    cnt = 0;
    for(int i=0; i<n; ++i){
        ct = 0;
        if(!dfn[i]&& i!=del) dfs(i);
        cnt = max(cnt, ct);
    }
}

int main()
{
      while(~scanf("%d%d", &n, &m))
      {
            for(int i=0; i<=n; ++i) G[i].clear();
            int x, y;
            for(int i=0; i<m; ++i){
                  scanf("%d%d", &x, &y);
                  G[x].push_back(y);
            }

            ans = 1e8;
            while(!S.empty()) S.pop();
            for(del = 0; del<n; ++del)
            {

                  find_scc(n);
                  ans = min(ans, cnt);
            }
            printf("%d\n", ans);
      }
      return 0;
}

zoj 3631、Watashi‘s BG  

搜索+剪枝

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m;
int a[35];
int s[360];
int Max;

void dfs(int x, int y) //dfs(i, money)
{
      if(y>m) return ;
      Max = max(y, Max);
      if(y+s[x]<=Max) return ; //剪纸
      if(y+a[x]<=m) dfs(x-1, y+a[x]);
      dfs(x-1, y);
}

int main()
{
    int i;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1;i<=n;i++)scanf("%d",a+i);
        sort(a+1,a+n+1);
        s[0]=0; Max=0;
        for(i=1;i<=n;i++)s[i]=s[i-1]+a[i];
        dfs(n,0);
        printf("%d\n",Max);
    }
    return 0;
}

zoj 3632、Watermelon Full of Water  

DP+线段树优化

不会。。。待补