2012长春市网络赛赛后【缺D】
2012长春网络赛赛后【缺D】
DP什么的最坑最烦了
H Spy’s Work (HDU
4274)
A A Simple Problem with Integers (HDU 4267)
树状树组维护arr[i]-arr[i-1]，实现成段更新单点查询。
#include<cstdio>
#include<cstring>
const int N=55555;
struct TreeArr
{
int arr[N],n;
void init(int n){memset(arr,0,4*n+4);this->n=n;}
void update(int k,int v){while(k<=n) arr[k]+=v,k+=k&-k;}
void update(int a,int b,int v){update(a,v);update(b+1,-v);}
int query(int k){int ans=0;while(k) ans+=arr[k],k-=k&-k;return ans;}
}ta[12][12];
int val[N];
int main()
{
int n,q;freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++) for(int j=0;j<i;j++) ta[i][j].init(n);
for(int i=1;i<=n;i++) scanf("%d",val+i);
scanf("%d",&q);
int op,a,b,k,c;
while(q--)
{
scanf("%d%d",&op,&a);
if(op==1) scanf("%d%d%d",&b,&k,&c),ta[k][a%k].update(a,b,c);
else
{
int ans=val[a];
for(int i=1;i<=n;i++) ans+=ta[i][a%i].query(a);
printf("%d\n",ans);
}
}
}
return 0;
}
B Alice and Bob (HDU 4268)
贪心，每次从剩余的所有不大于a.x的数中选择一个不大于a.y且y最大的删去
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef pair<int,int>tp;
const int N=100010;
tp a[N],b[N];
int main()
{
int t;//freopen("in.txt","r",stdin);
scanf("%d",&t);
while(t--)
{
int x,y,n,ans=0;
multiset<int>s;
multiset<int>::iterator it;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d%d",&a[i].first,&a[i].second);
for(int i=0;i<n;i++) scanf("%d%d",&b[i].first,&b[i].second);
sort(a,a+n);
sort(b,b+n);
for(int i=0,j=0;i<n;i++)
{
while(j<n&&b[j]<=a[i]) s.insert(b[j++].second);
it=s.upper_bound(a[i].second);
if(it!=s.begin()) ans++,s.erase(--it);
}
printf("%d\n",ans);
}
return 0;
}
C Defend Jian Ge (HDU 4269)
这个把细节解释地很详细了：http://lujunda.tk/2012/09/09/hdu4269%E6%A8%A1%E6%8B%9F-defend-jian-ge/
不过我测过了HDOJ数据里没有将消耗型装备作为合成装备的材料的数据存在
#include<map>
#include<vector>
#include<sstream>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<string,int> tp;
#define pb push_back
struct Nod
{
string s,ss[6];
int val,cnt,c[6],kind,totval;
Nod(){cnt=0;}
Nod(string s,int v,int kind):s(s),val(v),kind(kind){cnt=0;}
};
map<string,int>si;
vector<Nod>eq;
int cal(int i)
{
int ans=eq[i].val;
for(int j=0;j<eq[i].cnt;j++) ans+=cal(si[eq[i].ss[j]])*eq[i].c[j];
return ans;
}
int main()
{
int n1,n2,n3,m,val,tmp,cas=1;
while(cin>>n1)
{
string s;si.clear();eq.clear();
for(int i=0;i<n1;i++) cin>>s>>val,eq.pb(Nod(s,val,1));
cin>>n2;cin.ignore();
for(int i=0;i<n2;i++)
{
getline(cin,s);istringstream iss(s);
Nod tmp;iss>>tmp.s>>tmp.val;tmp.kind=2;
while(iss>>s>>tmp.ss[tmp.cnt]>>tmp.c[tmp.cnt]) tmp.cnt++;
eq.pb(tmp);
}
cin>>n3;
for(int i=0;i<n3;i++) cin>>s>>val,eq.pb(Nod(s,val,3));
for(int i=0;i<eq.size();i++) si[eq[i].s]=i;
for(int i=0;i<eq.size();i++) eq[i].totval=cal(i);
vector<tp>bag,bag2;
vector<tp>::iterator it;
#define myfind(a,s) for(it=a.begin();it!=a.end()&&it->first!=s;it++)
int gold=0;cin>>m;
while(m--)
{
cin>>s;
if(s[0]=='+')
{
s.erase(0,1);
if(si.find(s)==si.end())
{
int tmp=0;
for(int i=0;s[i];i++) tmp=tmp*10+s[i]-48;
gold+=tmp;
}
else
{
int i=si[s],fg=1;
if(gold<eq[i].val) continue;
if(eq[i].kind!=3)
{
bag2=bag;
for(int j=0;j<eq[i].cnt;j++) for(int k=0;k<eq[i].c[j];k++)
{
myfind(bag2,eq[i].ss[j]);
if(it==bag2.end()) fg=0;
else bag2.erase(it);
}
bag2.pb(tp(s,1));
if(!fg||bag2.size()>6) continue;
bag=bag2;gold-=eq[i].val;
}
else
{
if(bag.size()==6) continue;
myfind(bag,s);
if(it==bag.end()) bag.pb(tp(s,1));
else it->second++;
gold-=eq[i].val;
}
}
}
else
{
s.erase(0,1);myfind(bag,s);
if(it==bag.end()) continue;
gold+=eq[si[s]].totval*it->second;
bag.erase(it);
}
}
cout<<"Case "<<cas++<<":"<<endl<<gold<<endl<<bag.size()<<endl;
sort(bag.begin(),bag.end());
for(int i=0;i<bag.size();i++) cout<<bag[i].first<<": "<<bag[i].second<<endl;
cout<<endl;
}
return 0;
}
D Dynamic Lover (HDU
4270)
E Find Black Hand (HDU 4271)
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int,string>tp;
#define _min(a,b,c) min(a,min(b,c))
int n,dp[111111][11];
char s[111111],ss[11][11];
tp a[11];
int cal(char *a,char *b,int la,int lb)
{
int ans=1e8;
for(int i=0;i<=lb;i++) dp[0][i]=i;
for(int i=0;i<la;i++)
{
for(int j=0;j<lb;j++)
dp[i+1][j+1]=_min(dp[i][j]+(a[i]!=b[j]),dp[i+1][j]+1,dp[i][j+1]+1);
ans=min(ans,dp[i+1][lb]);
}
return ans;
}
void solve()
{
int len=strlen(s),lim=min(len,20);
for(int i=0;i<lim;i++) s[len+i]=s[i];s[len+lim]=0;
if(len<20)
{
for(int i=0;i<n;i++)
{
int tmp=1e8;
for(int j=0;j<len;j++) tmp=min(tmp,cal(s+j,ss[i],len,strlen(ss[i])));
a[i]=tp(tmp,ss[i]);
}
}
else
{
for(int i=0;i<n;i++) a[i]=tp(cal(s,ss[i],len+20,strlen(ss[i])),ss[i]);
}
}
int main()
{
while(scanf("%s%d",s,&n)!=EOF)
{
for(int i=0;i<n;i++) scanf("%s",ss[i]);
solve();sort(a,a+n);
printf("%s %d\n",a[0].second.c_str(),a[0].first);
}
return 0;
}
F LianLianKan (HDU 4272)
状态压缩DP。对于当前的i位置的元素，最多与a[i+9]位置的消去。a[i+1]、a[i+2]、a[i+3]、a[i+4]分别与a[i-4]、a[i-3]、a[i-2]、a[i-1]对应，则a[i]可能与a[i+5]、a[i+6]、a[i+7]、a[i+8]、a[i+9]对应。状态st用2进制10位表示i到i+9的10位是否被选
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1111;
int n,a[N],dp[N][N];
//0:未被选 1：已被选
int dfs(int i,int st)
{
if(i==n) return st==0;
if(~dp[i][n]) return dp[i][n];
if(st&1) return dp[i][n]=dfs(i+1,st>>1);
for(int j=1;j<=9&&i+j<n;j++)
if(((1<<j)&st)==0&&a[i]==a[i+j])
if(dfs(i+1,st>>1|(1<<j-1))) return dp[i][st]=1;
return dp[i][st]=0;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=n-1;~i;--i) scanf("%d",a+i);
memset(dp,255,sizeof(dp));
printf("%d\n",dfs(0,0));
}
return 0;
}
G Rescue (HDU 4273)
三维凸包模板题，代码无限长
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-8;
const int maxv=305;
typedef double db;
struct pt
{
db x,y,z;
pt(){}
pt(db x,db y,db z):x(x),y(y),z(z){}
pt operator - (const pt p){return pt(x-p.x,y-p.y,z-p.z);}
pt operator + (const pt p){return pt(x+p.x,y+p.y,z+p.z);}
pt operator * (pt p){return pt(y*p.z-z*p.y,z*p.x-x*p.z,x*p.y-y*p.x);}
pt operator / (double k){return pt(x/k,y/k,z/k);}
pt operator * (double k){return pt(x*k,y*k,z*k);}
double operator ^ (pt p){return (x*p.x+y*p.y+z*p.z);}
};
struct _3DCH
{
struct fac{int a,b,c;bool ok;};
int n,cnt,to[maxv][maxv];
pt P[maxv];
fac F[maxv*8];
double vlen(pt a){return sqrt(a.x*a.x+a.y*a.y+a.z*a.z);}
double volume(pt a,pt b,pt c,pt d){return (b-a)*(c-a)^(d-a);}
double ptof(pt &p,fac &f)
{
pt m=P[f.b]-P[f.a],n=P[f.c]-P[f.a],t=p-P[f.a];
return (m*n)^t;
}
void deal(int p,int a,int b)
{
int f=to[a][b];
fac add;
if(F[f].ok)
{
if(ptof(P[p],F[f])>eps) dfs(p,f);
else
{
add.a=b,add.b=a,add.c=p,add.ok=1;
to[p][b]=to[a][p]=to[b][a]=cnt;
F[cnt++]=add;
}
}
}
void dfs(int p,int cur)
{
F[cur].ok=0;
deal(p,F[cur].b,F[cur].a);
deal(p,F[cur].c,F[cur].b);
deal(p,F[cur].a,F[cur].c);
}
bool same(int s,int t)
{
pt &a=P[F[s].a],&b=P[F[s].b],&c=P[F[s].c];
return fabs(volume(a,b,c,P[F[t].a]))<eps&&fabs(volume(a,b,c,P[F[t].b]))<eps&&fabs(volume(a,b,c,P[F[t].c]))<eps;
}
void construct()
{
cnt=0;
if(n<4) return;
bool sb=1;
for(int i=1;i<n;i++) if(vlen(P[0]-P[i])>eps)
{
swap(P[1],P[i]);
sb=0;break;
}
if(sb) return;
sb=1;
for(int i=3;i<n;i++) if(fabs((P[0]-P[1])*(P[1]-P[2])^(P[0]-P[i]))>eps)
{
swap(P[3],P[i]);sb=0;break;
}
if(sb) return;
fac add;
for(int i=0;i<4;i++)
{
add.a=(i+1)%4,add.b=(i+2)%4,add.c=(i+3)%4,add.ok=1;
if(ptof(P[i],add)>0) swap(add.b,add.c);
to[add.a][add.b]=to[add.b][add.c]=to[add.c][add.a]=cnt;
F[cnt++]=add;
}
for(int i=4;i<n;i++) for(int j=0;j<cnt;j++) if(F[j].ok&&ptof(P[i],F[j])>eps)
{
dfs(i,j);break;
}
int tmp=cnt;cnt=0;
for(int i=0;i<tmp;i++) if(F[i].ok) F[cnt++]=F[i];
}
pt center()
{
pt ans(0,0,0),o(0,0,0);
double tot=0;
for(int i=0;i<cnt;i++)
{
double vol=volume(o,P[F[i].a],P[F[i].b],P[F[i].c]);
ans=ans+(o+P[F[i].a]+P[F[i].b]+P[F[i].c])/4*vol;
tot+=vol;
}
return ans/tot;
}
double dis(pt p,int i)
{
double vol=volume(P[F[i].a],P[F[i].b],P[F[i].c],p);
double s=vlen((P[F[i].b]-P[F[i].a])*(P[F[i].c]-P[F[i].a]));
return fabs(vol/s);
}
}hull;
int main()
{
while(scanf("%d",&hull.n)!=EOF)
{
for(int i=0;i<hull.n;i++) scanf("%lf%lf%lf",&hull.P[i].x,&hull.P[i].y,&hull.P[i].z);
hull.construct();
pt p=hull.center();
double ans=1e10;
for(int i=0;i<hull.cnt;i++) ans=min(ans,hull.dis(p,i));
printf("%.3f\n",ans);
}
return 0;
}
H Spy’s Work (HDU
4274)
每个结点初始化为[1,inf]，dfs更新每个结点的[low,up]，如果某个结点low>up即为lie，否则为true
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=22222;
int head[N],nxt[N],ev[N],e;
int low[N],up[N],fg;
void dfs(int u,int p)
{
int lim=1;
for(int i=head[u];~i;i=nxt[i])
{
if(ev[i]==p) continue;
dfs(ev[i],u);
lim+=low[ev[i]];
}
if(low[u]<lim) low[u]=lim;
if(low[u]>up[u]) fg=0;
}
int main()
{
int n,m,x,y;
while(scanf("%d",&n)!=EOF)
{
e=0;
for(int i=1;i<=n;i++) head[i]=-1,low[i]=1,up[i]=0x3f3f3f3f;
for(int i=2;i<=n;i++)
{
scanf("%d",&x);
ev[e]=x,nxt[e]=head[i],head[i]=e++;
ev[e]=i,nxt[e]=head[x],head[x]=e++;
}
char op[2];fg=1;
for(scanf("%d",&m);m;m--)
{
scanf("%d%s%d",&x,op,&y);
if(op[0]=='<') up[x]=min(up[x],y-1);
if(op[0]=='>') low[x]=max(low[x],y+1);
if(op[0]=='=') low[x]=max(low[x],y),up[x]=min(up[x],y);
}
if(fg) dfs(1,1);
puts(fg?"True":"Lie");
}
return 0;
}
I Color the Tree (HDU 4275)
组合数学+树的同构（HASH）
- 先找树的重心，若存在两个重心，则分别以两个重心为根，拆成两个子树，最后合并计算。
- 对一个以u为根的子树，将u的所有儿子v1,v2,……,vn按hash[v1],hash[v2],……,hash[vn]的值分组（值相同的认为是同构的树），每一种情况都是有n个相同子树，每个子树有m种染色方案，求子树染色的不同情况为，此模型等价于将n个相同的球放入m个盒子的情况数。
- n个相同的球放入m个盒子又等价于：n+m-1的空位中选择m-1个位子插板形成m个区间（盒子），其它位置放小球ans=C(n+m-1,m-1)。又因为m-1可能很大，计算时用ans=C(n+m-1,m-1)=C(n+m-1,n)来算，即对n个子树根结点计算的复杂度是O(n)，每个结点O(1)，总共O(n).
-
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>tp;
#define clr(a,x) memset(a,x,sizeof(a))
const int BASE=35127,MUL=913121;
const int N=111111,mod=1e9+7;
int n,m;
int head[N],nxt[N],ev[N],e;
int lev[N],deg[N],que[N];
bool vis[N];
ll hash[N],ans[N];
tp arr[N];
ll pow(ll a,int n)//快速幂
{
ll b;
for(b=1;n;a=a*a%mod,n/=2) if(n&1) b=b*a%mod;
return b;
}
ll com(ll n,int m)//组合数
{
ll x=1,y=1;
for(int i=1;i<=m;i++) x=x*(n-i+1)%mod,y=y*i%mod;
return x*pow(y,mod-2)%mod;
}
void findRoot(int &a,int &b)//求重心
{
if(n==1){a=0,b=-1;return;}
clr(vis,0);clr(deg,0);
int st=0,ed=-1;
for(int i=0;i<n;i++)
{
for(int j=head[i];~j;j=nxt[j]) deg[i]++;
if(deg[i]<=1) vis[que[++ed]=i]=1,lev[i]=0;
}
while(st<=ed)
{
int u=que[st++];
for(int i=head[u];~i;i=nxt[i])
{
int v=ev[i];
if(!vis[v]&&--deg[v]<=1) vis[que[++ed]=v]=1,lev[v]=lev[u]+1;
}
}
a=que[ed];
b=lev[a]==lev[que[ed-1]]?que[ed-1]:-1;
}
void dfs(int u,int p)//求每个子树hash值并算出每个子树的ans
{
for(int i=head[u];~i;i=nxt[i])
{
if(ev[i]==p) continue;
dfs(ev[i],u);
}
ans[u]=m;hash[u]=BASE;int cnt=0;
for(int i=head[u];~i;i=nxt[i])
{
if(ev[i]==p) continue;
arr[cnt++]=tp(hash[ev[i]],ans[ev[i]]);
}
sort(arr,arr+cnt);
for(int j,i=0;i<cnt;i=j)
{
for(j=i;j<cnt&&arr[i].first==arr[j].first;j++)
hash[u]=((hash[u]*MUL)^arr[j].first)%mod;
ans[u]=ans[u]*com(arr[i].second+j-i-1,j-i)%mod;
}
}
ll solve()
{
int a,b;
findRoot(a,b);
dfs(a,b);
if(b==-1) return ans[a];//只有一个重心
dfs(b,a);
return hash[b]==hash[a]?ans[a]*(ans[a]+1)%mod*pow(2,mod-2)%mod:ans[a]*ans[b]%mod;
//两个重心对应子树是否同构。
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(head,-1,sizeof(head));e=0;
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);--u,--v;
ev[e]=v,nxt[e]=head[u];head[u]=e++;
ev[e]=u,nxt[e]=head[v];head[v]=e++;
}
printf("%I64d\n",solve());
}
return 0;
}
J The Ghost Blows Light (HDU 4276)
树形DP 先dfs求出1与n的最近距离，并将路径上的边权值改为0并更新剩余可用时间t=t-dis，若t小于0，则无解。
然后就随便从最短路径上选一个点（一般就选1或n了）作为树的根进行dfs，dp[i][t]表示i节点花费时间不超过t能获得的最大价值。
因为存在w=0的边，所以dp[u][j]=max(dp[u][j],dp[u][j-w]+dp[v][0])一定要最先更新，否则当w=0更新dp[u][j]的值时用的dp[u][j-w]不是最初的dp[u][j-w]了。
#include<cstdio>
#include<cstring>
#define max(a,b) ((a)>(b)?(a):(b))
int n,t,dp[111][555],val[111];
int head[111],nxt[222],ev[222],ew[222],e;
int dis(int u,int p)
{
if(u==n) return 0;
for(int i=head[u];~i;i=nxt[i])
{
if(ev[i]==p) continue;
int tmp=dis(ev[i],u)+ew[i];
if(tmp<ew[i]) continue;
else ew[i]=0;return tmp;
}
return -1;
}
void dfs(int u,int p)
{
for(int i=0;i<=t;i++) dp[u][i]=val[u];
for(int i=head[u];~i;i=nxt[i])
{
int v=ev[i],w=ew[i]*2;
if(v==p) continue;
dfs(v,u);
for(int j=t;j>=w;j--)
for(int k=0;k<=j-w;k++)
dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-w-k]);
}
}
int main()
{
while(scanf("%d%d",&n,&t)!=EOF)
{
memset(head,255,sizeof(head));e=0;
for(int i=1;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
ev[e]=v,ew[e]=w,nxt[e]=head[u];head[u]=e++;
ev[e]=u,ew[e]=w,nxt[e]=head[v];head[v]=e++;
}
for(int i=1;i<=n;i++) scanf("%d",val+i);
t-=dis(1,1);
if(t<0){puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");continue;}
dfs(1,1);
printf("%d\n",dp[1][t]);
}
return 0;
}
K USACO ORZ (HDU 4277)
dfs复杂度为3^n，插入set时剪枝。x>y与x<y的情况等价出现，所以可以只考虑x<=y<=z
#include<set>
#include<iostream>
using namespace std;
long t,n,a[20],sum,x,y,z;
set<long>s;
void dfs(int i)
{
if(i==n)
{
if(x&&x<=y&&x<=z&&y<=z&&x+y>z) s.insert(x<<16|y);
return;
}
x+=a[i];dfs(i+1);x-=a[i];
y+=a[i];dfs(i+1);y-=a[i];
z+=a[i];dfs(i+1);z-=a[i];
}
int main()
{
for(cin>>t;t;t--)
{
cin>>n;sum=x=y=z=0;s.clear();
for(int i=0;i<n;i++) cin>>a[i],sum+=a[i];
dfs(0);
cout<<s.size()<<endl;
}
return 0;
}