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+线段树优化
不会。。。待补