ZOJ Problem Set - 3717 Balloon
飞机票: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5040
从这一题我对2-sat有更深的了解了。。。起先以为2-sat要添加一定可行的边。。。其实不然。。。要求添加可能可以的边。。。意思就是说两个组每个组2个人A1 A2,B1,B2 如果A1选了不能选B1,那么不管A2选了能不能选B1。。。都添加A2 B1这条边搞了一天2-sat 什么鬼~~~反正现在深入了解了。。。好了。。直接正题~~~
分析。。这题就是说给你n个组。每个组有两个球。。每个球有坐标。。从每个组里选择一个球。。且所有球不重叠。。。球最大球径是多少。。。其实就是2-sat问题。。。怎么搞呢??先求出每队之间的距离。。。即一共有四个距离。。。即(A1,B1),(A1,B2),(A2,B1),(A2,B2) 三维距离很简单。。。((x1-x2)^2+(y1-y2)^2+(z1-z2)^2)^0.5即可。。搜噶然后二分球径。。。这里可以剪下枝。。。怎么搞呢。。。先从上面的距离选出最大的距离作为r,l为0。。。然后在循环里面可以判断下那四个距离是否都小于R,如果小于R。。则不符合条件。。直接继续二分。。。如果有一个可以则。。。根据2-sat建边。。。这里得知道要添加可能的边(起先不知道。。Wa到死)一共有四种可能。。所以有4种添边方案。。。然后每次二分跑一下tarjan。。。如果符合条件。。则l变为mid+e...这里e是定义的精度。。。如果不可以。。那r就要变为mid-e...当可行的时候。。。可以定义一个double记录最大符合条件的球径。。。其实起先我还卡了一下为什么距离要跟球径的两倍比较。。。后来想了一下球可以转的啊。。。太菜了。。。最后精度又是个问题。。。但是只要保留4位小数就可以了。。。因为是spj。。。然后啪啪啪!!!AC!!!
/* Author:Chieh Grow up happy */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <map> #include <queue> #include <stack> #include <vector> #define LL long long using namespace std; const int maxn=456; const double e=0.0001; struct he { int a,b,c; } JLJ[maxn]; vector<int> V[maxn]; double dist[maxn][maxn]; int n; void init() { for(int i=0; i<n; i++) { scanf("%d%d%d",&JLJ[i*2].a,&JLJ[i*2].b,&JLJ[i*2].c); scanf("%d%d%d",&JLJ[i*2+1].a,&JLJ[i*2+1].b,&JLJ[i*2+1].c); } } bool instack[maxn]; int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum; void tarjan(int u) { dfn[u]=low[u]=indexx++; instack[u]=1; sta[++scnt]=u; for(int i=0; i<V[u].size(); i++) { int v=V[u][i]; if(dfn[v]==-1) { tarjan(v); low[u]=min(low[u],low[v]); } else if(instack[v])low[u]=min(dfn[v],low[u]); } if(dfn[u]==low[u]) { for(int v=-1; v!=u; scnt--) { v=sta[scnt]; instack[v]=0; belong[v]=cntnum; } cntnum++; } } double cal(double a,double b,double c,double d,double e,double f) { return sqrt((a-d)*(a-d)+(b-e)*(b-e)+(c-f)*(c-f)); } void play() { double MAX=0; for(int i=0; i<n; i++) { for(int j=i+1; j<n; j++) { dist[i*2][j*2]=cal(JLJ[i*2].a,JLJ[i*2].b,JLJ[i*2].c,JLJ[j*2].a,JLJ[j*2].b,JLJ[j*2].c); dist[i*2][j*2+1]=cal(JLJ[i*2].a,JLJ[i*2].b,JLJ[i*2].c,JLJ[j*2+1].a,JLJ[j*2+1].b,JLJ[j*2+1].c); dist[i*2+1][j*2]=cal(JLJ[i*2+1].a,JLJ[i*2+1].b,JLJ[i*2+1].c,JLJ[j*2].a,JLJ[j*2].b,JLJ[j*2].c); dist[i*2+1][j*2+1]=cal(JLJ[i*2+1].a,JLJ[i*2+1].b,JLJ[i*2+1].c,JLJ[j*2+1].a,JLJ[j*2+1].b,JLJ[j*2+1].c); MAX=max(MAX,dist[i*2][j*2]); MAX=max(MAX,dist[i*2][j*2+1]); MAX=max(MAX,dist[i*2+1][j*2]); MAX=max(MAX,dist[i*2+1][j*2+1]); } } double l=0; double r=MAX; double over=0; while(l<=r) { double mid=(l+r)/2; double d=mid*2; bool flag=1; for(int i=0; i<=2*n; i++)V[i].clear(); for(int i=0; i<n; i++) { if(!flag)break; for(int j=i+1; j<n; j++) { if(dist[i*2][j*2]<d&&dist[i*2+1][j*2]<d&&dist[i*2][j*2+1]<d&&dist[i*2+1][j*2+1]<d) { flag=0; break; } if(dist[i*2][j*2+1]<d) { V[i*2].push_back(j*2); V[j*2+1].push_back(i*2+1); } if(dist[i*2][j*2]<d) { V[i*2].push_back(j*2+1); V[j*2].push_back(i*2+1); } if(dist[i*2+1][j*2+1]<d) { V[i*2+1].push_back(j*2); V[j*2+1].push_back(i*2); } if(dist[i*2+1][j*2]<d) { V[i*2+1].push_back(j*2+1); V[j*2].push_back(i*2); } } } if(!flag){ r=mid-e; continue; } indexx=cntnum=0; scnt=-1; memset(dfn,-1,sizeof(dfn)); memset(instack,0,sizeof(instack)); for(int i=0; i<2*n; i++) { if(dfn[i]==-1)tarjan(i); } for(int i=0; i<n; i++) { if(belong[i*2]==belong[i*2+1]) { flag=0; break; } } if(!flag) { r=mid-e; continue; } over=max(over,l); l=mid+e; } printf("%.4lf\n",over); } int main() { while(scanf("%d",&n)!=EOF) { init(); play(); } // cout << "Hello world!" << endl; return 0; }
ZOJ Problem Set - 3656 Bit Magic
飞机票: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4879
分析:搞了一天的2-sat了。。。感觉还是迷迷糊糊真是菜比~~~好了。。。不扯了。。。直接正题:
题意:题意就是给你个矩阵。。。然后求是否有数组满足那段程序的。。。程序自己看啊。。。请点击飞机票。。。这种题怎么变成2-sat。。。烧脑烧力啊。。。,先预处理对角线是否为0和对称点是否一样。。然后只要把每个位单独处理即可~~~。。。坦白地说:对于矩阵的一个元素b[i][j]。。。如果i%2==0&&j%2==0则a[i]&a[j]=b[i][j]。。。这里就可以用到前面文章的内容了。。。就是说a[i]的第k为&a[j]的第k位=b[i][j]的第k位(注:2进制下)然后运用前面文章的信息。不妨设当前点i为1则是i*2,为0则是i*2+1那么就可以建图了
AND 结果为1:建边 x*2+1->x*2,y*2+1->y*2 (两个数必须全为1)
AND 结果为0:建边 y*2->x*2+1,x*2->y*2+1 (两个数至少有一个为0)
OR 结果为1:建边 x*2+1->y*2,2*y+1->x*2 (两个数至少有一个为1)
OR 结果为0:建边 x*2->x*2+1,y*2->y*2+1 (两个数必须全为0)
XOR 结果为1:建边 x*2->y*2+1,y*2->x*2+1,y*2+1->x*2,x*2+1->y*2 (两个数必须不同)
XOR 结果为0:建边 x*2->y*2,y*2->x*2,x*2+1->y*2+1,y*2+1->x*2+1 (两个数必须相同)
这样要处理最多30次。。。因为b[i][j]有范围限制,然后每一次都跑一遍。。。只要有不符合就直接啪啦:NO,如果都想。。YES!啪啪啪~但是速度不快啊。。。不过AC还是轻轻松松的~~~
/* Author:Chieh Grow up happy */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <map> #include <queue> #include <stack> #include <vector> #define LL long long using namespace std; const int maxn=1234; vector<int> V[maxn]; int ai[567][567]; int n; void init() { for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { scanf("%d",&ai[i][j]); } } } bool instack[maxn]; int dfn[maxn],low[maxn],sta[maxn],belong[maxn],indexx,scnt,cntnum; void tarjan(int u) { dfn[u]=low[u]=indexx++; instack[u]=1; sta[++scnt]=u; for(int i=0; i<V[u].size(); i++) { int v=V[u][i]; if(dfn[v]==-1) { tarjan(v); low[u]=min(low[u],low[v]); } else if(instack[v])low[u]=min(dfn[v],low[u]); } if(dfn[u]==low[u]) { for(int v=-1; v!=u; scnt--) { v=sta[scnt]; instack[v]=0; belong[v]=cntnum; } cntnum++; } } void play() { for(int i=0; i<n; i++) { if(ai[i][i]!=0) { printf("NO\n"); return; } } int MAX=0; for(int i=0; i<n; i++) { for(int j=i+1; j<n; j++) { MAX=max(MAX,ai[i][j]); if(ai[i][j]!=ai[j][i]) { printf("NO\n"); return; } } } int o=(1<<30); while(o>MAX){ o=o>>1; } for(int i=1; i<=100; i++) { if(o==0)break; for(int j=0; j<2*n; j++)V[j].clear(); bool ju=0; for(int j=0; j<n; j++) { for(int k=0; k<n; k++) { if(j==k)continue; int u=(j)*2; int v=(k)*2; int c=0; if(ai[j][k]-o>=0) { ju=1; ai[j][k]-=o; c=1; } if(j%2==0&&k%2==0) { if(c==0) { V[u].push_back(v^1); V[v].push_back(u^1); } else { V[u^1].push_back(u); V[v^1].push_back(v); } } else if(j%2==1&&k%2==1) { if(c==0) { V[u].push_back(u^1); V[v].push_back(v^1); } else { V[u^1].push_back(v); V[v^1].push_back(u); } } else { if(c==0) { V[u].push_back(v); V[v].push_back(u); V[u^1].push_back(v^1); V[v^1].push_back(u^1); } else { V[u].push_back(v^1); V[v].push_back(u^1); V[v^1].push_back(u); V[u^1].push_back(v); } } } } o=o>>1; if(!ju) { continue; } indexx=cntnum=0; scnt=-1; memset(dfn,-1,sizeof(dfn)); memset(instack,0,sizeof(instack)); for(int j=0; j<2*n; j++) { if(dfn[j]==-1)tarjan(j); } for(int j=0; j<n; j++) { if(belong[j*2]==belong[j*2+1]) { printf("NO\n"); return; } } } printf("YES\n"); } int main() { while(scanf("%d",&n)!=EOF) { init(); play(); } // cout << "Hello world!" << endl; return 0; }
ZOJ Problem Set - 3183 Counting Binary Trees
题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3273
自从湖南旅游回来之后整个人真的是不佳啊~~~一天就做了这么一个题。。。感觉自己的越来越弱了。。。好了进入正题
分析:首先,这种题先找规律
当n=1时,只有1个根节点,则只能组成1种形态的二叉树,令n个节点可组成的二叉树数量表示为h(n),
则h(1)=1;
当n=2时,1个根节点固定,还有n-1个节点,可以作为左子树,也可以作为右子树, 即:h(2)=h(0)*h(1)+h(1)*h(0)=2,则能组成2种形态的二叉树。这里h(0)表示空,所以只能算一种形态,即h(0)=1;
当n=3时,1个根节点固定,还有n-1=2个节点,可以在左子树或右子树, 即:h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=5,则能组成5种形态的二叉树。
以此类推,当n>=2时,可组成的二叉树数量为h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)种。
即符合Catalan数的定义,可直接利用通项公式得出结果。 递归式:
h(n)=h(n-1)*(4*n-2)/(n+1); 该递推关系的解为:
h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
然后就啪啪啪、、、Wa了尼玛。。。作为弱者的我不知道怎么错了。。。后来看看递推里面带了除法。。。我去。。。我不会带除法的取余果断百度了一下。。。soga。。看了下要变乘法。。。ok直接套取余模版。。。然后就AC了
/* Author:Chieh Grow up happy */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <vector> #include <map> #include <stack> #define LL long long using namespace std; const int maxn=123456; int n,m; //LL ai[maxn]; int sm[1000],p;//将m分解质因数 int sa[1000];//4*i-2 和 i+1 分解质因数 //素数筛选 int flag[50000],pri[50000],pl; void prime() { for(int i=2; i<50000; i++) { if(flag[i]==0) pri[pl++]=i; for(int j=0; j<pl&&i*pri[j]<50000; j++) { flag[i*pri[j]]=1; if(i%pri[j]==0) break; } } } int extgcd(int a,int b,int &x,int &y) { if(b==0) { x=1,y=0; return a; } int r=extgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return r; } LL over; void init() { over=1%m; LL res=1;//n=1时 sum=1 后面从2开始 p=0; int tm=m;//将m分解质因数 for(int i=0; pri[i]*pri[i]<=tm; i++) { if(tm%pri[i]==0) { sm[p++]=pri[i]; while(tm%pri[i]==0) tm/=pri[i]; } } if(tm>1) sm[p++]=tm;//important memset(sa,0,sizeof(sa)); for(int i=2; i<=n; i++) { int t; t=4*i-2; for(int j=0; j<p; j++) { while(t%sm[j]==0) { sa[j]++,t/=sm[j]; } } res=res*t%m; t=i+1; for(int j=0; j<p; j++) { while(t%sm[j]==0) { sa[j]--,t/=sm[j]; } } if(t>1) { int x,y; int r=extgcd(t,m,x,y); x=(x%m+m)%m; res=res*x%m; } LL tmp=res; for(int j=0; j<p; j++) { for(int k=0; k<sa[j]; k++) { tmp=tmp*sm[j]%m; } } over=(over+tmp)%m; } } void play() { printf("%lld\n",over); } int main() { prime(); while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0)break; init(); play(); } return 0; }
ZOJ Problem Set - 3211 Dream City
题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3374
题意就是说有n棵树,每棵树有个初始值a个金币,而且每过一天会增加b个金币,求m天最多可以得到金币,而且必须每天都要砍一棵树
刚开始以为是贪心。。。Wa,后来举了个反例才发现自己的贪心是错的。。。那么应该怎么做这道题呢??DP。。。除了贪心我只能想到DP,该怎么DP呢。。。后来想到来个数组dp[i][j]表示前i棵树在j天最大可以产生多少。。。但是有个特别的值。。就是b。。。好像又把我卡住了。。。想一下,就是怎么来确定顺序呢。。。根据b排序。。。把b最小的放前面。。。这样到后面的时候,b已经是最优的了。。。所以这道题的大致感觉就是。当前要放那个哪个地方的话。。。前面的得先放好而且是最优的
ai[i][j]=max(ai[i-1][j],ai[i-1][j-1]+JLJ[i].b*(j-1)+JLJ[i].a);
这样答案就出来了
/* Author:Chieh Grow up happy */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <map> #include <stack> #include <vector> #define LL long long using namespace std; const int maxn=250+10; struct he { int a,b; } JLJ[maxn]; int ai[maxn][maxn]; int n,m; int T; bool cmp(he a,he b) { return a.b<b.b; } void init() { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) { scanf("%d",&JLJ[i].a); } for(int i=1; i<=n; i++) { scanf("%d",&JLJ[i].b); } } void play() { sort(JLJ+1,JLJ+1+n,cmp); memset(ai,0,sizeof(ai)); for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(j<=i) ai[i][j]=max(ai[i-1][j],ai[i-1][j-1]+JLJ[i].b*(j-1)+JLJ[i].a); else break; } } printf("%d\n",ai[n][m]); } int main() { scanf("%d",&T); while(T--) { init(); play(); } //cout << "Hello world!" << endl; return 0; }
ZOJ Problem Set - 2505 Sticks
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1505
题目大意:就是有最多1024个魔法棒放在一排,按照时间顺序对第i个魔法棒改变状态,问最长的连续子序列且都是奇数次改变多长。
题目分析:网上说是暴力。。。我暴力了一发。。。过了。。。但是这题明显是线段树啊,虽然暴力出奇迹。
怎么个线段法??就是每个区间记录最大值和是否是连续的区间。。怎么定义??一个节点定义lval,rval,link,max,l,r 其中l,r不用说了,lval就是左边的长度,val同理,max最大值,link是否连续,如果连续,那么lva=rval;如果不连续当然也可能相等,但是不可能是区间的长度,这样我们就好搞了,每次更新子节点,则父节点判断是否连续,如果两个子节点都连续,则父节点lval=左节点的lva+右节点的rval,且max就是当前区间长~~~link当然是连接的啊~~不想等呢》》
那好办了,如果左节点是连得,那父节点lval=左节点lval+右节点lval,且rval=右节点rval,link当然为false了,max就是lmax+rmax
如果右节点是连得,同理哈。。。最后一种情况左右都不连。。。那父节点lval=左节点lval,父节点rval=右节点val,max还是lmax+rmax,link必然false,OK了,讨论完毕。。。AC啦
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn=4097; struct he { int l,r,MAX; int lval,rval; int link; } JLJ[maxn*2]; void BuildTree(int l,int r,int now) { JLJ[now].l=l; JLJ[now].r=r; JLJ[now].link=0; JLJ[now].MAX=0; JLJ[now].lval=0; JLJ[now].rval=0; if(l==r)return; int mid=(l+r)/2; BuildTree(l,mid,now*2); BuildTree(mid+1,r,now*2+1); } void Update(int l,int now) { if(JLJ[now].l==l&&JLJ[now].r==l) { if(JLJ[now].MAX==0)JLJ[now].MAX=1; else JLJ[now].MAX=0; JLJ[now].lval=JLJ[now].rval=JLJ[now].MAX; if(JLJ[now].MAX==1) JLJ[now].link=1; else JLJ[now].link=0; return; } int mid=(JLJ[now].l+JLJ[now].r)/2; if(l<=mid) { Update(l,now*2); } else { Update(l,now*2+1); } int j1=JLJ[now*2].link; int j2=JLJ[now*2+1].link; if(j1&&j2) { JLJ[now].link=1; JLJ[now].lval=JLJ[now].rval= JLJ[now].MAX=JLJ[now*2].MAX+JLJ[now*2+1].MAX; } else if(j1) { JLJ[now].link=0; JLJ[now].lval=JLJ[now*2].MAX+JLJ[now*2+1].lval; JLJ[now].rval=JLJ[now*2+1].rval; JLJ[now].MAX=max(JLJ[now].lval,max(JLJ[now*2+1].MAX,JLJ[now*2].MAX)); } else if(j2) { JLJ[now].link=0; JLJ[now].lval=JLJ[now*2].lval; JLJ[now].rval=JLJ[now*2].rval+JLJ[now*2+1].MAX; JLJ[now].MAX=max(JLJ[now*2].MAX,max(JLJ[now].rval,JLJ[now*2+1].MAX)); } else { JLJ[now].link=0; JLJ[now].lval=JLJ[now*2].lval; JLJ[now].rval=JLJ[now*2+1].rval; JLJ[now].MAX=max(JLJ[now*2].MAX,max(JLJ[now*2+1].MAX,JLJ[now*2].rval+JLJ[now*2+1].lval)); } } int T,n; int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); BuildTree(1,4096,1); int l; int MAX=0; for(int i=1; i<=n; i++) { scanf("%d",&l); Update(l,1); MAX=max(MAX,JLJ[1].MAX); } printf("%d\n",MAX); } //cout << "Hello world!" << endl; return 0; }
ZOJ Problem Set - 3626 Treasure Hunt I
问题地址:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4772
题目大意:有一个勇者要去挖宝藏,但是有吸血鬼,且吸血鬼会在m天后出现。。。(就是说勇者最多只能走m步,且最后要在k结束),
k 是勇者的家。
分析:因为只有n-1条边且连通,所以原图必然是一棵树,所以很典型的想到树形DP
假设从k点到当前点J的深度,既路径长度为len,建立一个数组存放J的子节点的信息。如果J的子节点到J的长度*2+len*2>m直接就跳过。
这里用到背包的思想,因为J可能有很多子节点,所以要选取最优的子节点。。
/* Author:Chieh Grow up happy */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <map> #include <stack> #include <vector> using namespace std; const int maxn=123; int n,m,k; int val[maxn]; int dp[maxn][maxn*2]; vector<pair<int,int> > V[maxn]; void DFS(int now,int len,int fa) { dp[now][0]=val[now]; for(int i=0; i<V[now].size(); i++) { int v=V[now][i].first; if(v==fa)continue; DFS(v,len+V[now][i].second,now); int cd=V[now][i].second*2; for(int j=m; j>=0; j--) { for(int k=0; k<=m; k++) { if(j+k+cd+len*2>m)break; if(dp[v][k]==0)continue; dp[now][j+k+cd]=max(dp[now][j]+dp[v][k],dp[now][j+k+cd]); } } } } void init() { memset(dp,0,sizeof(dp)); for(int i=1; i<=n; i++)V[i].clear(); for(int i=1; i<=n; i++)scanf("%d",&val[i]); int u,v,w; for(int i=1; i<n; i++) { scanf("%d%d%d",&u,&v,&w); V[u].push_back(make_pair(v,w)); V[v].push_back(make_pair(u,w)); } scanf("%d%d",&k,&m); } void play() { DFS(k,0,0); int MAX=0; for(int i=0; i<=m; i++) { MAX=max(MAX,dp[k][i]); } printf("%d\n",MAX); } int main() { while(scanf("%d",&n)!=EOF) { init(); play(); } return 0; }