AC » Archive » contest zju Monthly August 2010

contest zju Monthly August 2010

八月 23rd, 2010 › ZJU, acm › ben1222 ›

昨天是ZOJ Monthly, August 2010
好久没做题了…N天前就看到这次月赛是东方专场…于是想着一定要去凑凑热闹…
不过最后还是只做了4个小时…最后一小时忙别的事情去了…

一看题数…居然有13题…
题号也变成了各种人物的名字了…

一上来是第阿求题…禁语吗……glob和regex的转换…看了下样例感觉不难…但是害怕有一堆要考虑的东西…

然后是第⑨题…算术教室…n个人围成一圈随机选取m个人,其中有9人是连着坐的概率是多少呢?…第一反应就是感觉是组合数方面的于是无视中…

然后看到已经有人过题了…第妖梦题…为大胃王幽幽子准备食物…第i天能准备bi份食物,但是要吃掉ai份食物…希望食物越新鲜越好…求各天准备多少食物…果然很水呢…从后往前扫一遍就可以了…
本想就看看题目娱乐下…结果一不小心手痒了…
于是敲了下…过了…

接着发现又一题有人过了…第四季题…黑白分明呢…用了Bad Apple影绘的图…
把24位点阵图转换成灰度然后再根据公式二值化…也很水…看到那句”All divisions are truncated divisions.”后就想…会有人栽在这里吧…后来真发现有个id是”一句All divisions are truncated divisions. 让我wa了10次，杯具了整个下午！！！”
但是敲了一下…在本地测试的时候用scanf(“#%2lx%2lx%2lx”,&r,&g,&b);来读入,结果本地测试死循环了…难道#也是特殊字符?于是改成了scanf(“%#%2lx%2lx%2lx”,&r,&g,&b);在本地测试通过了…可是交上去OLE了…难道编译器不同吗…
于是很郁闷的改成了scanf(“%s”,str);sscanf(str+1,”%2lX%2lX%2lX”,&r,&g,&b);
题目描述里面没说输出的9或者空格之间需要空格隔开…但是sample output里面却隔开了…于是改成没有空格隔开结果wa了…
最后再改回来有空格隔开的才AC…

接着看到第灵梦题有人过了…塞钱箱…说是第i天请人赛钱可以得到si元,但是如果这么做了,下一次请人赛钱的时间必须在xi天后,yi天前…求如果第一天请人赛钱的话,最多能得到多少钱…
稍微想了下,一个简单的dp而已…dp[i]表示第i天请人赛钱的话,从第i天开始最多能得到多少钱…转移时只要找xi天后,yi天前这段区间的dp值最大的即可…
然后一看规模…5万天…囧了…不过求区间最大值而已…解题报告虽然说用线段树…可当时我想到的却是rmq…
但是rmq是一次性的预处理的…于是就YY着改造了一下,依然沿袭rmq那种思路:分成logN层,每层有N个数,第i层的第j个数表示在[j,j+2^i-1]的范围内最大值是多少
然后从后往前边dp边insert,对于第i天来说,这天之后的每一天的dp值和rmq数组值都是已经得到了的,于是就能得到第i天的dp值,然后将这个值插入进rmq数组,更新第i个数的那logN层数字,总复杂度O(nlogn)
很快写好了…提交却下标越界…然后发现数组开小了- -|||…改后AC
在看解题报告的时候发现评论里有说Sparse Table什么的…原来我那方法叫这个名字啊…

接下来看到第辉夜题有人过…妹红要埋伏辉夜吗…题目是求一张图上从起点到终点之间的必经之路…也就是桥?…模板题吗…可惜我只有割点的模板…于是忽略了这题…

接下来看到第芙兰题有人过了…永夜抄吗……看到迷途竹林以为又是图论有关的…结果却不是这样…
一共有n个房间,第i个房间有xi个ITEM,每个是ai点,有yi个TIME,每个是bi点,每次去一个房间把所有这个房间的ITEM和TIME收完回到入口,直到所有房间的ITEM和TIME都收完…
拿一个点数是a的ITEM的时候可以得到IV分,并且TV增加a
拿一个点数是b的TIME的时候可以得到TV分,并且IV增加b
一开始IV和TV值为0,求最多能得到多少分
因为进一个房间后,该房间所有的ITEM和TIME都要收完,所以先考虑在一个房间内的情况,该按什么顺序收最好
小数据手动演算了一下,发现分数会增加IV*xi+TV*yi+u*ai+v*bi,并且u+v=xi*yi,并且对任何正整数的u,v搭配都总有一种顺序可以满足
于是得到了在第i个房间内最多分数会增加IV*xi+TV*yi+max{ai,bi}*xi*yi的结论,可见ai,bi和IV,TV是分离的,因此外面用一层状态压缩dp计算2^15个状态就可以了
dp[state]表示state的位为1的对应的房间已经去过的情况下,所得到的最大分数
并且这个情况下的IV和TV值是固定的,轻轻松松的上吧…

又看到第因幡题有人过…腹黑兔啊…看似公平的游戏却把规则定的自己总有必胜策略…想到东方夜神雪里面那个取硬币小游戏…轮流取1~3枚,取走最后一枚的人输…可是起始的硬币数量并不是随机的…而是4k+1…太囧了…玩了好几盘才发现原来这游戏是必输的…
回到这里…这次是类似孔明棋的小游戏…每次可以选一个棋子往4个方向之一跳,但是必须跳过别的棋子并且最终落在某个空格上,中间可以跳过连续多个棋子,被跳过的棋子都会被拿走…
给定初始棋局,问让铃仙和因幡谁先走可以使得因幡有必胜策略…
一看规模才5*5…想想2^25也不是什么大数字…加上有一句”It’s guaranteed that no more than 61.8% of them are ‘e’s.”…感觉状态会很少…于是直接暴力记录博弈状态…
第一次交忘记处理了选取的棋子是一排棋子中间的某个棋子的情况…改后AC

然后…第魔里沙题有人过…魔炮啊…是个计算几何…求往什么方向射可以打中最多点,魔炮的范围是个顶点为原点的抛物线
抛物线啊…想到每个点有个可被命中的角度范围,也就是魔炮的方向在这个范围内,这个点可以被打中,但是对不同距离的点而言,这个范围的大小是不一样的…
计算了下,二次系数是a的抛物线和半径为r的圆的交点

y坐标是: y=(sqrt(1+4*a*a*r*r)-1)/(2*a)

设上图中P点对应的极角为alpha,那么当魔炮中轴对着[alpha-theta, alpha+theta]区间中任意的极角时,P点就能被打中

这个theta值为: theta=atan(x/y) =atan(sqrt(y/a)/y)=atan(sqrt(1/y*a))

于是问题转换成了,找一个极角,使得它被最多的区间覆盖…而数据规模有3万个点…
脑中第一个闪现的是离散化+线段树…显然太麻烦了…
然后想起以前某些题…比如矩形求并之类的…貌似只要看左右边界判断出入就行…
于是想到了用这个方法就好,将区间变成端点,左端点标记为入,右端点标记为出,然后将所有端点按大小(这里是极角)排序
然后从前往后扫描,遇到标记为入的端点就当前覆盖区间数加一,遇到标记为出的端点就当前覆盖区间数减一,扫描一遍下来,取当前覆盖区间数的最大值…就是所需的答案daze
另外处理下跨边界相邻的情况,就是当区间在[0,2pi]的两边时,就多插入个小于0的那个入端点和大于2pi的那个出端点

然后…有别的事情…于是就看看题目然后不继续做了…
第极题…姬海棠也有啊…貌似是找最安全点…话说游戏里寅丸星的香蕉激光实在是太恶心了…但是这题目里面是射线…而且是曼哈顿距离?…直接傻眼了…点和线的曼哈顿距离?那是什么?怎么求?

第图书题…不动的大图书馆…题目是一共m种元素卡,一共有n种符文,每种元素卡上等概率出现这n种符文中的一种,求m种元素卡各取一张的话,有多少概率可以使得这些卡上的符文至少有l个是相同的…输出成既约分数…
又是组合数类的题目吗…

第咲夜题…时间的操作…哦不…这题是求表达式结果是某个类型的可能性个数?
题目很长呢…

第幽幽子题…赏花会啊…真好呢…
又是做食物…这次是第i天幽幽子会吃掉ai份食物…妖梦每天可以做L份食物,或者花一天时间锻炼自己使得L值增加1…求N天过后剩下的食物最多还有多少份…

这里或者这里是官方解题报告吧…

下面是我灵梦,芙兰,魔里沙题的代码…

第灵梦题的代码:

#include<stdio.h>
/*
ZOJ monthly 201008
红白
*/
#define N 50010
long dp[N];
//dp[i]=max_money get if ask for money at day i
long rmq[18][N],bi[19];
long n;
long money[N],begin[N],end[N];
long query(long pa,long pb){
 long j,d;
 if(pa>pb){j=pa;pa=pb;pb=j;}
 if(pa>=n||pa<0)return 0;
 if(pb>=n)pb=n-1;
 d=pb-pa+1;
 for(j=0;bi[j]<=d;j++);
 j--;
 pa=rmq[j][pa];
 pb=rmq[j][pb-bi[j]+1];
 if(pa<pb)pa=pb;
 return pa;
}
void insert(long p,long val){
 long j;
 for(j=0;j<18;j++){
  rmq[j][p]=val;
  long next=bi[j]+p;
  if(next<n){
   if(rmq[j][next]>val)val=rmq[j][next];
  }
 }
}
int main(){
 long i;
 for(i=0;i<19;i++)bi[i]=((long)1)<<i;
 while(scanf("%ld",&n)!=EOF){
  for(i=0;i<n;i++)scanf("%ld%ld%ld",money+i,begin+i,end+i);
  long j;
  for(j=0;j<18;j++)for(i=0;i<n;i++)rmq[j][i]=-1;
  for(i=n-1;i>=0;i--){
   dp[i]=money[i]+query(i+begin[i],i+end[i]-1);
   insert(i,dp[i]);
  }
  printf("%ld\n",dp[0]);
 }
 return 0;
}

第芙兰题的代码:

#include<stdio.h>
#include<memory.h>
/*
ZOJ monthly 201008
二小姐

in part_i:
 point+=IV*xi+TV*yi+max{ai,bi}*xi*yi
 IV+=yi*bi
 TV+=xi*ai
dp[state(1<<n)]=max_point when collected in parts[state.bits]
*/
#define N 32768
long bi[17];
long dp[N],s_iv[N],s_tv[N];
long n;
long xi[15],yi[15],a[15],b[15];
long add_point[15];
long fun(long state){
 if(dp[state]!=-1)return dp[state];
 long i;
 long best=0;
 for(i=0;i<n;i++)if(state&bi[i]){
  long prev=state^bi[i];
  long iv=s_iv[prev],tv=s_tv[prev];
  long val=fun(prev)+iv*xi[i]+tv*yi[i]+add_point[i];
  if(val>best)best=val;
 }
 return dp[state]=best;
}
int main(){
 long i;
 for(i=0;i<17;i++)bi[i]=((long)1)<<i;
 while(scanf("%ld",&n)!=EOF){
  for(i=0;i<n;i++){
   scanf("%ld%ld%ld%ld",a+i,b+i,xi+i,yi+i);
   if(a[i]>b[i])add_point[i]=a[i]*xi[i]*yi[i];
   else add_point[i]=b[i]*xi[i]*yi[i];
  }
  memset(dp,-1,sizeof(dp));
  long j;
  for(i=0;i<bi[n];i++){
   long iv=0,tv=0;
   for(j=0;j<n;j++)if(i&bi[j]){
    iv+=yi[j]*b[j];
    tv+=xi[j]*a[j];
   }
   s_iv[i]=iv;
   s_tv[i]=tv;
  }
  printf("%ld\n",fun(bi[n]-1));
 }
 return 0;
}

第魔里沙题的代码:

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
/*
ZOJ monthly 201008
黑白

y=a*x^2
x*x+y*y=r*r
y=a*(r^2-y^2)
y=a*r*r-a*y*y
a*y^2+y-a*r*r=0
y=(sqrt(1+4*a*a*r*r)-1)/(2*a)
theta=atan(x/y) =atan(sqrt(y/a)/y)=atan(sqrt(1/y*a))
*/
typedef struct{
 double rad;
 char out;
}point;
bool operator<(const point&a,const point&b){
 return a.rad<b.rad||(a.rad==b.rad&&a.out<b.out);
}
#define N 30010
#define PI 3.14159265358979
point seg[N*3];
double xi[N],yi[N];
long nseg;
#define ENSEG(r,o) {seg[nseg].rad=r;seg[nseg].out=o;nseg++;}
int main(){
 long n;
 double a;
 while(scanf("%ld%lf",&n,&a)!=EOF){
  long i;
  for(i=0;i<n;i++)scanf("%lf",xi+i);
  for(i=0;i<n;i++)scanf("%lf",yi+i);
  long addition=0;
  nseg=0;
  for(i=0;i<n;i++){
   double r2=xi[i]*xi[i]+yi[i]*yi[i];
   double dy=(sqrt(1.0+4*a*a*r2)-1)/(2*a);
   if(dy<=0){addition++;continue;}
   double theta=atan(sqrt(1.0/(dy*a)));
   double t0=atan2(yi[i],xi[i]);
   if(t0<0)t0+=PI*2;

   double in=t0-theta,out=t0+theta;
   ENSEG(in,0)
   ENSEG(out,1)
   if(in<0){
    ENSEG(in+PI*2,0)
    ENSEG(out+PI*2,1)
   }
   if(out>=PI*2){
    ENSEG(in-PI*2,0)
    ENSEG(out-PI*2,1)
   }
  }
  sort(seg,seg+nseg);
  long ans=0,now=0;
  for(i=0;i<nseg;i++){
   if(seg[i].out)now--;
   else now++;
   if(now>ans)ans=now;
  }
  printf("%ld daze\n",ans+addition);
 }
 return 0;
}

Tags: accept, code, contest, dp, rmq, 东方, 博弈, 圆, 状态压缩, 计算几何, 贪心