(POJ) Find them, Catch them

http://poj.org/problem?id=1703

先開一個2*MAX_N的disjoint set，其中1~MAX_N是在第一個幫派的可能，MAN_N + 1 ~ MAX_N + MAX_N 是第二個幫派的可能，那麼，當做到D操作時，可以合併[A],[B] + MAX_N和 [A] + MAX_N, [B]，那查詢的時候，可以依照這個樣子去查，就okay囉！

時間複雜度：O(alpha(N))

#include <iostream>
#include <stdio.h>
using namespace std;

const int MAX_N = 1e5 + 3;

struct DisjointSet {
 int p[2 * MAX_N];
 void init(int i){
  for (int x=0;2*MAX_N>x;x++) {
   p[x]=x;
  }
 }
 int Find(int x) {
  return p[x]==x?x:p[x]=Find(p[x]);
 }
 void Union(int x,int y) {
  p[Find(x)]=Find(y);
 }
} djs;

int main() {
 int T;
 scanf("%d",&T);
 while (T--) {
  int n,m;
  scanf("%d %d",&n,&m);
  djs.init(n);
  for (int x=0;m>x;x++) {
   char a;
   int b,c;
   scanf("\n%c %d %d",&a,&b,&c);
   if (a=='A') {
    if (djs.Find(b) == djs.Find(c)) {
     puts("In the same gang.");
    }
    else if (djs.Find(b) == djs.Find(c+MAX_N)) {
     puts("In different gangs.");
    }
    else {
     puts("Not sure yet.");
    }
   }
   else {
    djs.Union(b,c+MAX_N);
    djs.Union(c,b+MAX_N);
   }
  }
 }
}

(TIOJ) 1160 . 3.動態眾數問題

http://tioj.ck.tp.edu.tw/problems/1160

我是用數值線段樹下去硬做XDDD

我想應該還有更好的方法

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

const int MAX_N = 1e5+5;

struct Node {
 Node* lc;
 Node* rc;
 pair<int,int> val;
 Node() {
  lc=rc=NULL;
  val=make_pair(-1,-1);
 }
 void pull() {
  val=max(lc->val,rc->val);
 }
};

Node* Build(int L,int R) {
 Node* node=new Node();
 if (L==R) {
  return node;
 }
 int mid=(L+R)>>1;
 node->lc=Build(L,mid);
 node->rc=Build(mid+1,R);
 node->pull();
 return node;
}

void modify(Node* node,int L,int R,int pos,int Val) {
 if (L==R) {
  if (node->val.first==-1) node->val=make_pair(1,-Val);
  else node->val.first+=1;
  return;
 }
 int mid=(L+R)>>1;
 if (pos<=mid) modify(node->lc,L,mid,pos,Val);
 else modify(node->rc,mid+1,R,pos,Val);
 node->pull();
 return;
}

int num[MAX_N];
int pos[MAX_N];
vector<int> vec;

int main () {
 int i=0;
 while (scanf("%d",&num[i]) != EOF) {
  if (num[i]==0) break;
  vec.push_back(num[i]);
  i++;
 }
 sort(vec.begin(),vec.end());
 vec.resize(unique(vec.begin(),vec.end()) - vec.begin());
 for (int x=0;i>x;x++) {
  int tmp=num[x];
  pos[x] = lower_bound(vec.begin(),vec.end(),tmp) - vec.begin() + 1;
 }
 Node* root = Build(1,MAX_N);
 for (int x=0;i>x;x++) {
  modify(root,1,MAX_N,pos[x],num[x]);
  printf("%d %d\n",root->val.first,-root->val.second);
 }
}

(chicken) 158A. Next Round

http://codeforces.com/contest/158/submission/18616128

http://codeforces.com/contest/158/problem/A

#include <iostream>
using namespace std;

#define CHICKEN int main()
#define CHICKEn int
#define CHICKeN(chicken) cin>>chicken;
#define CHICKen(chicken) for(int chiCKEN=0;chicken>chiCKEN;chiCKEN++)
#define CHICkEN 0
#define CHIcken if
#define chIckEN 1
#define CHIckeN and
#define chICKEN(chicken) cout<<chicken<<endl;


CHICKEN {
 CHICKEn chicken,chickeN;
 CHICKeN(chicken)
 CHICKeN(chickeN)
 CHICKEn chickEn[chicken];
 CHICKen(chicken) CHICKeN(chickEn[chiCKEN]);
 CHICKEn chickEN = CHICkEN;
 CHICKen(chicken) {
  CHIcken(chickEn[chiCKEN] >= chickEn[chickeN-chIckEN] CHIckeN chickEn[chiCKEN]!=CHICkEN) chickEN += chIckEN;
 }
 chICKEN(chickEN)
}

Codeforces Round #355 (Div. 2)

((好久沒po題解了，最近在忙 2016延平電資營YPCS 的題目，到時候我也會一併把題目&祥解放在這裡喔。幫忙按個讚吧！

到時候 pE 的詳解 會在放上去，現在沒空寫 pE

題目：

pA : http://codeforces.com/contest/677/problem/A
pB : http://codeforces.com/contest/677/problem/B
pC : http://codeforces.com/contest/677/problem/C
pD : http://codeforces.com/contest/677/problem/D

我AC的code :

pA : http://codeforces.com/contest/677/submission/18186305
pB : http://codeforces.com/contest/677/submission/18215807
pC : http://codeforces.com/contest/677/submission/18195576
pD : http://codeforces.com/contest/677/submission/18452316

題解：

pA :
這題只要把輸入的n個數字，只要<=h，ans+=1；>h，ans+=2。就okay了。

pB :
題目大意：給你n個長度ai(1<=i<=n)個馬鈴薯，一個長度h的垂直食物處理器，保證h>=所有ai。現在，你要依序把馬鈴薯放到處理器裡面，直到再放入一個高度會超過h，或者是沒有馬鈴薯。而這個食物處理器每次會切到k長度的馬鈴薯。如果長度不到k，那就會全部切掉。問說，最少需要幾次，才可以把馬鈴薯切完。

要小心。。。這題要開long long(要不然會被hacked !!!)
就是呢，先給一個想法：假設你現在有長度和x個馬鈴薯，你可以把這些馬鈴薯切完後，再把後面的放進去(想想看，可以這樣的!!!)！於是乎，按照這個邏輯下去greedy : 如果現在的長度加上新的長度會>h，就先把這些長度切到<k，如果加了還是>h，就把剩下切完，要不然就把k 加進去，如果<=h，就加進去!

這樣子greedy，複雜度O(n)：陣列掃過一遍就okay了。

pC :
題目大意：我們現在定義：A-Z代表10~35, a~z代表36~61，-是62，_是63。現在給你一個長度s的字串，包含0~9, A~Z, a~z, - , _ ，請你把它視為一個64進位的數字。現在，問你說，有多少個對數字，他們彼此做&運算後，會剛好等於題目給的字串！

仔細想想，如果題目給的字串換成二進位後有m個0，n個1，那麼，0一定要0 & 0，沒有甚麼好討論的，但是，1就可以0 & 1 , 1 & 1 , 1 & 0三種。所以，對於每個1，都有三種作法，於是乎，輸出3 ^ n就好了！

pD :
待補，有點累了~~

Codeforces Round #356 (Div. 2)

((好久沒po題解了，最近在忙 2016延平電資營YPCS 的題目，到時候我也會一併把題目&祥解放在這裡喔。幫忙按個讚吧！

到時候 pE 的詳解 會在放上去，現在沒空寫 pE

pA : http://codeforces.com/contest/680/problem/A
pB : http://codeforces.com/contest/680/problem/B
pC : http://codeforces.com/contest/680/problem/C
pD : http://codeforces.com/contest/680/problem/D

我AC的code :

pA : http://codeforces.com/contest/680/submission/18303002
pB : http://codeforces.com/contest/680/submission/18310104
pC : http://codeforces.com/contest/680/submission/18308741
pD : http://codeforces.com/contest/680/submission/18450161

題解：

pA :
題意：你有五張已知牌，你想要最小化總和。你可以拿走一次牌，而拿走一次牌中，你只能拿三張or兩張一樣的牌。

那你就維護說可以拿三張最大的是多少，拿兩張最大的是多少，在比較誰可以扣掉得比較多，就好了(感覺這題滿好hack的)

pB :
題意：(簡化過後的)每個點的value=0 or 1，你有一個機器，可以告訴你由你這個點到固定距離的兩個or一個點的value和是多少，問說你可以確定有多少個點value是1

那就從中心擴散，慢慢實作就好了！小心邊界問題就是了

pC :
題意：謎底是一個[2,100]間的數字，你需要判斷這個數字是不是質數！你最多可以問20次，問說這個數字可不可以被你提供的數字整除。

一開始我想說就[2,100]間的25個質數，後來想想：如果是合數，那一定有兩個質因數，只有2^2,3^2,5^2,7^2 < 100 (11^2 = 121 > 100)，那麼，只需要在判斷[10,50]之間的質數就好。如果是>50的合數，那一定有<50之間的兩個質數相乘。

所以，這樣剛好問19次

((不信邪的話，就2 ~ 100每個試過一遍嘛！

pD :
題意：(簡化過後的)
定義一個演算法f(x) ： if (x<=7) return x; else return f(x-a*a*a) + 1，其中a是最大的數字，符合a*a*a<=f。
現在，給你一個數字X，請求出所有範圍[1,X]的整數中的f(x)的最大值，如果有多個，那請輸出最大的

(看官方題解的作法) ：
分兩種case : 用a跟用a-1，下去dfs，就okay了。
詳細的話看我的code吧！

pE : Unsolved

TOI 五月份練習賽 懶人包

題目：
Pencil : https://www.dropbox.com/s/ug80z73gink518a/Pencil.pdf?dl=0
Base Conversion : https://www.dropbox.com/s/dlja1czffsnuamo/Base%20Conversion.pdf?dl=0

我AC的Code：
Pencil : http://codepad.org/3FY0uRhl
Base Conversion : http://codepad.org/xbtXbiLz

題解：

Pencil :
先有個greedy個概念：如果這個三角形的最大值已經確定，那麼如果要造成最大面積，那一定是選擇剩下的數值中最大的兩個。

那麼，基於這個greedy概念，我可以先sort所有的數值，再從大的往小的看，這樣就okay了。

複雜度：P(n lg n + n)

Base Conversion :
認真做就好了XDDD，開個long long 比較保險