BZOJ 刷题记录 PART 6 - c++编程基础

TOP

BZOJ 刷题记录 PART 6

2015-11-21 01:58:01 来源: 作者: 【大中小】浏览:5次

【BZOJ2709】水的二分加验证。但是好像被读入萎到了。。。

【BZOJ3229】强大的算法见此。被机房的一堆大神“推荐”，于是被坑了。。。写了一个下午。。。

【BZOJ3631】这道题给我的启示是：要多想想算法。开始一直在打树链剖分，打到一半忽然在众神?的提（bi）示（shi）下，发现有O(N)的方法。试想：如果要支持区间修改（加减），最后再查询，可以用什么方法？固然，线段树和树状数组等等都可以，但是最好的显然是类似于前缀和的思想。比如在L~R加上一个数，可以再L处+K，在R+1处-K。然后最后的时候从头到尾扫过去、累加即可。

那么这道题实际上是在树上做这个类似的操作。当然，求LCA的时候要用tarjan，否则效率又变回去了。

以下是代码。wri是为了调整，最后输出的是wri和sum的和。

void bfs(int k)
{
  for (int i=1;i
  
   

   【BZOJ3609】打表找规律。据说是版权问题？就不说了。

   【BZOJ1212】啊哈哈哈，又被我DP使过去啦！

   【BZOJ2823&1666&1667】以前查来的题解。。。好像是谁的论文来着。

   


   初始圆为1,2作为直径的圆。


   For i=2 to n


   If i不在当前圆内 then


    
   把当前圆设为以1,i为直径的圆


    
   For j=2 to i-2 


    
   If j不在当前圆内 then


    
   把当前圆设为以j,i为直径的圆{确定初始圆}


    
   For k=1 to j-1 


    
   If k不在当前圆内 then 


    
   把当前圆设为I,j,k三点确定的圆。{确定三点确定的圆}


   输出当前圆

   

   【BZOJ1802】真的是好题。我们先来考虑在开头的时候放的尽量的少。

   ①如果有两个相邻的红格，那么我可以在放好后之后到达任何一个点！于是第一问就是0。至于第二问，找出所有相邻的红格，直接用DP往左右扫。

   
    for (int i=k-1;i;i--)
    f[i]=min(f[i],f[i+1]+f[i+2]);
   

   ②否则必须在偶数格放棋子，扫一遍即可。

   
   for (i=2;i
    
     

     【BZOJ3574】题解传送门（跪SYC大爷！）

     【BZOJ1873】写的天昏地暗！我觉得有必要贴一下代码。

     
     #include
      
       
#include
       
         #include
         #include
         
           #define N 20005 #define P 41 using namespace std; map
          
           pre; const char Num[11][P]={"","","","killing spree","dominating","mega kill", "unstoppable","wicked sick","monster kill","godlike","beyond godlike"}; const char Wri[11][P]={"","","","is on a killing spree!","is dominating!", "has a mega kill!","is unstoppable!","is wicked sick!","has a monster kill!", "is godlike!","is beyond godlike. someone kill him!"}; char a[P],b[P],Time[P],ch[P]; int belong[N],num[N],kill[N],last[N],death[2]; int A,B,now_Time,ok_kill,ALL,n,i,Q; bool check() { A=pre[a];B=pre[b]; return A&&B&&A!=B; } void get_Time(){now_Time=(Time[0]*10+Time[1])*60+Time[3]*10+Time[4];} void First() { if (A==B) {printf("%s has killed himself.\n",a);return;} if (!ok_kill) {printf("%s has been killed by %s.\n",b,a);return;} if (num[B]>=3) {printf("%s has just ended %s's %s.\n",a,b,Num[num[B]<=10?num[B]:10]);num[B]=0;return;} printf("%s pawned %s's head.\n",a,b);num[B]=0; if (ok_kill&&!ALL) ALL=1,printf("%s just drew first blood.\n",a); } void Second() { if (!ok_kill) return; num[A]++; if (num[A]>=3) { if (num[A]<=10) printf("%s %s\n",a,Wri[num[A]]); else printf("%s %s\n",a,Wri[10]); } } void Third() { if (!ok_kill) return; if (kill[A]&&now_Time<=last[A]+10) { if (kill[A]==1) printf("%s just got a Double Kill!\n",a); else printf("%s just got a Triple Kill!\n",a); } else kill[A]=0; kill[A]++;last[A]=now_Time; } void Fourth() { if (!ok_kill) return; int now=belong[B];death[now]++;death[now^1]=0; if (death[now]>=5) printf("The %s is OWNING!\n",!now?"Scourge":"Sentinel"); } int main() { freopen("1873.out","w",stdout); scanf("%d",&n); for (i=1;i<=n;i++) scanf("%s%d",a,&belong[i]),pre[a]=i; scanf("%d",&Q);ALL=0; while (Q--) { scanf("%s%s%s%s%s%s",Time,b,ch,ch,ch,a); ok_kill=check();get_Time(); First();Second();Third();Fourth(); } return 0; }
          
         
       
      
     

     【BZOJ1925*】至今还觉得奇怪的DP（递推、组合数）。有空去看看。

     【BZOJ1819】好题目！用dfs序的性质，树状数组维护，还要求LCA。开始忘了怎么在dfs序的树状数组中维护某个点的子树的信息，去问了RZZ，后来发现根本就是傻X问题啊。


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：编程算法 - 数组中的逆序对代码(..	下一篇：Effective C++：条款37：绝不重新..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: