程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 刷題記錄 PART 6

BZOJ 刷題記錄 PART 6

編輯：C++入門知識

【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;
mappre;
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問題啊。