游戲
【題目描述】
lxhgww最近迷上了一款游戲，在游戲里，他擁有很多的裝備，每種裝備都有2個(gè)屬性，這些屬性的值用[1,10000]之間的數(shù)表示。當(dāng)他使用某種裝備時(shí)，他只能使用該裝備的某一個(gè)屬性。并且每種裝備最多只能使用一次。
游戲進(jìn)行到最后，lxhgww遇到了終極boss，這個(gè)終極boss很奇怪，攻擊他的裝備所使用的屬性值必須從1開始連續(xù)遞增地攻擊，才能對(duì)boss產(chǎn)生傷害。也就是說一開始的時(shí)候，lxhgww只能使用某個(gè)屬性值為1的裝備攻擊boss，然后只能使用某個(gè)屬性值為2的裝備攻擊boss，然后只能使用某個(gè)屬性值為3的裝備攻擊boss……以此類推。
現(xiàn)在lxhgww想知道他最多能連續(xù)攻擊boss多少次？
【輸入】
輸入的第一行是一個(gè)整數(shù)N，表示lxhgww擁有N種裝備
接下來N行，是對(duì)這N種裝備的描述，每行2個(gè)數(shù)字，表示第i種裝備的2個(gè)屬性值
【輸出】
輸出一行，包括1個(gè)數(shù)字，表示lxhgww最多能連續(xù)攻擊的次數(shù)。
【樣例輸入】
3
1 2
3 2
4 5
【樣例輸出】
2
【數(shù)據(jù)范圍】
對(duì)于30%的數(shù)據(jù)，保證N<=1000
對(duì)于100%的數(shù)據(jù)，保證N<=1000000
===========================================================================
沒什么說的，匈牙利最壞10000^2過了。。其實(shí)對(duì)于這樣隨機(jī)的邊很多的圖。。匈牙利的實(shí)際運(yùn)行時(shí)間比O(n)多不了多少。。實(shí)際測(cè)試表明。。比用下面方法的要快。。囧。
官方題解是：10000個(gè)點(diǎn)，1000000條邊的一個(gè)圖。對(duì)于每個(gè)聯(lián)通塊如果是樹則只能選到n-1個(gè)，那么肯定是選最小的n-1個(gè)，如果有環(huán)則全部可以。最后for下從1開始哪些可以就行了。。
吐槽：。。。考完回來寫匈牙利，寫了兩遍都錯(cuò)了，而且錯(cuò)的一樣。。。調(diào)了很久才發(fā)現(xiàn)寫錯(cuò)的地方，杯具。。
1 #include <iostream>
2 #define MAXN 1000010
3 #define MAXM MAXN*2
4
5 using namespace std;
6
7 int Count = 0;
8 int begin[MAXN+1], end[MAXM+1], next[MAXM+1];
9 void AddEdge(int a, int b){
10 Count++;
11 next[Count] = begin[a];
12 begin[a] = Count;
13 end[Count] = b;
14 }
15
16 int n;
17 #define BUFSIZE 1000000*10
18 char buf[BUFSIZE], *pt = buf;
19 #define scan_int(x) \
20 { \
21 x = 0; \
22 while (!((*pt) >= '0' && (*pt) <= '9')) pt++; \
23 while (((*pt) >= '0' && (*pt) <= '9')) x = x * 10 + (*(pt++)) - '0'; \
24 }
25 void Init(){
26 scanf("%d",&n);
27 int a,b;
28 fread(pt, 1, BUFSIZE, stdin);
29 for (int i = 1; i<=n; i++){
30 //scanf("%d%d",&a,&b);
31 scan_int(a); scan_int(b);
32 AddEdge(a,i);
33 AddEdge(b,i);
34 }
35 }
36
37 int cnt;
38 int q[MAXN+1];
39 bool hash[MAXN+1];
40 int Link[MAXN+1];
41 bool dfs(int x){
42 for (int now = begin[x]; now; now = next[now])
43 if (!hash[end[now]]){
44 hash[end[now]] = true;
45 q[++cnt] = end[now];
46 if (!Link[end[now]] || dfs(Link[end[now]])){
47 Link[end[now]] = x;
48 return true;
49 }
50 }
51 return false;
52 }
53
54 void Solve(){
55 int Ans;
56 for (int i = 1; i<=10001; i++){
57 cnt = 0;
58 if (!dfs(i)){
59 Ans = i-1;
60 break;
61 }
62 for (int j = 1; j<=cnt; j++)
63 hash[q[j]] = false;
64 }
65 printf("%d\n",Ans);
66 }
67
68 int main(){
69 freopen("game.in","r",stdin);
70 freopen("game.out","w",stdout);
71 Init();
72 Solve();
73 return 0;
74 }
75
幸運(yùn)數(shù)字
【題目描述】
在中國，很多人都把6和8視為是幸運(yùn)數(shù)字！lxhgww也這樣認(rèn)為，于是他定義自己的“幸運(yùn)號(hào)碼”是十進(jìn)制表示中只包含數(shù)字6和8的那些號(hào)碼，比如68，666，888都是“幸運(yùn)號(hào)碼”！但是這種“幸運(yùn)號(hào)碼”總是太少了，比如在[1,100]的區(qū)間內(nèi)就只有6個(gè)（6，8，66，68，86，88），于是他又定義了一種“近似幸運(yùn)號(hào)碼”。lxhgww規(guī)定，凡是“幸運(yùn)號(hào)碼”的倍數(shù)都是“近似幸運(yùn)號(hào)碼”，當(dāng)然，任何的“幸運(yùn)號(hào)碼”也都是“近似幸運(yùn)號(hào)碼”，比如12，16，666都是“近似幸運(yùn)號(hào)碼”。
現(xiàn)在lxhgww想知道在一段閉區(qū)間[a, b]內(nèi)，“近似幸運(yùn)號(hào)碼”的個(gè)數(shù)。
【輸入】
輸入數(shù)據(jù)是一行，包括2個(gè)數(shù)字a和b
【輸出】
輸出數(shù)據(jù)是一行，包括1個(gè)數(shù)字，表示在閉區(qū)間[a, b]內(nèi)“近似幸運(yùn)號(hào)碼”的個(gè)數(shù)
【樣例輸入1】
1 10
【樣例輸出1】
2
【樣例輸入2】
1234 4321
【樣例輸出2】
809
【數(shù)據(jù)范圍】
對(duì)于30%的數(shù)據(jù)，保證1<=a<=b<=1000000
對(duì)于100%的數(shù)據(jù)，保證1<=a<=b<=10000000000
//================================================================
用容斥原理做。
先造出所有的幸運(yùn)號(hào)碼，然后對(duì)幸運(yùn)號(hào)碼的倍數(shù)容斥。
幸運(yùn)號(hào)碼有2000+個(gè)，為了盡快出解，要加幾個(gè)剪枝：
1. 如果A是B的倍數(shù)，直接去掉。剪掉了一大半。。。
2.從大到小排序，盡快容斥掉一些數(shù)。
寫的常數(shù)稍微少點(diǎn)能進(jìn)2s了。。
PS ：關(guān)于中間結(jié)果會(huì)爆long long的問題。。。從正的爆成負(fù)的容易，從正的爆成負(fù)的再爆成正的不容易。。。所以猥瑣的判大于0。。。
1
#include <iostream>
2#include <algorithm>
3#define NNUM 3000
4#define ll long long
5
6using namespace std;
7
8ll A,B;
9
void Init()
{
10
scanf("%I64d%I64d",&A,&B);
11
}
12
13int n = 0;
14ll a[NNUM+1];
15void dfsNum(ll num){
16 if (num > B) return;
17 if (num <= B)
18 a[++n] = num;
19 dfsNum(num * (ll)10 + (ll)6);
20 dfsNum(num * (ll)10 + (ll)8);
21}
22int cnt = 0;
23ll b[NNUM+1];
24
25ll Ans = 0, tmp;
26inline ll gcd(ll a, ll b){
27 while (b)
28 tmp = a, a = b, b = tmp % b;
29 return a;
30}
31
32
33int cmp(const void *a, const void *b){
34 return (*(ll *)b) > (*(ll *)a) ? 1 : -1;
35}
36
37ll dfs(int pos, ll num){
38 if (pos == n+1) return B/num - A/num;
39 ll ret = dfs(pos+1, num);
40 ll newnum = num / gcd(num, a[pos]) * a[pos];
41 if (newnum <= B && newnum >= 1)
42 ret -= dfs(pos+1, newnum);
43 return ret;
44}
45
46void Solve(){
47 dfsNum(6); dfsNum(8);
48 qsort(a+1, n, sizeof(a[0]), cmp);
49 //printf("%d\n",n);
50
for (int i = 1; i<=n; i++){
51 bool boo = true;
52 for (int j = 1; j<=n; j++)
53 if (i!=j && a[i] % a[j] == 0){
54 boo = false;
55 break;
56
}
57 if (boo){
58 a[++cnt] = a[i];
59 //printf("%d %I64d\n", cnt, a[cnt]);
60 }
61 }
62 n = cnt;
63 //printf("%d\n",n);
64 A--;
65 printf("%I64d\n", B - A - dfs(1,1));
66}
67
68int main(){
69 freopen("luckynumber.in","r",stdin);
70 freopen("luckynumber.out","w",stdout);
71 Init();
72 Solve();
73 return 0;
74}
75
timtopcoder.wep.dk
新開的網(wǎng)站，歡迎大家捧場~
摘要: 最開始寫費(fèi)用流的時(shí)候，有且只會(huì)SPFA版的費(fèi)用流，而且一直都?jí)蛴茫话銇碚f只要建出了圖就贏了，網(wǎng)絡(luò)流怎么都不會(huì)超時(shí)。。。。。這個(gè)情況到今天被終結(jié)了。。。終結(jié)者見下：--------------------------------------------------------------------------------------------------------
最優(yōu)圖像
【題目描述】...
閱讀全文
摘要: 題目敘述： 給出一個(gè)有n個(gè)節(jié)點(diǎn)的樹, 一個(gè)整數(shù)k. 定義dist(u, v)為節(jié)點(diǎn)u, v間的距離. 求這棵樹中有多少節(jié)點(diǎn)對(duì)(u, v)滿足dist(u, v)<=k. (n<=10000)-------------------------------------------對(duì)于這樣一個(gè)數(shù)據(jù)范圍，顯然O(n^2)的直接算是會(huì)超時(shí)的。大體的思路是：&n...
閱讀全文
This is a reminder of what I need to learn and need to do.
割點(diǎn)和橋
帶上下界的網(wǎng)絡(luò)流：可行流，最大流及其費(fèi)用流
polya定理
做道要用逆元的題
斯特靈數(shù)：第一類，第二類
NOIP2009最后一題。
看到題的時(shí)候直接就想到了DancingLinks，但是。。。很后悔是，原來想學(xué)的時(shí)候覺得難寫就沒寫了。
不過考試時(shí)裸搜加最優(yōu)性剪枝有95分，也很不錯(cuò)了。
DacingLinks其實(shí)就是十字鏈表，用于求解精確覆蓋問題：對(duì)于一個(gè)0-1矩陣，選取一些行使得每列有且只有一個(gè)1。
把數(shù)獨(dú)轉(zhuǎn)換為這樣一個(gè)模型以后就可以用DacingLinks快速的搜索了。
搜索時(shí)每次選擇1的個(gè)數(shù)最少的那列，枚舉那列上選取的某行，再把那行其他位置有1的列刪除，接著繼續(xù)搜索。回溯時(shí)再還原改動(dòng)。
對(duì)于數(shù)獨(dú)而言，一共有9*9個(gè)格子，每個(gè)格子可以填9個(gè)數(shù)，所以在0-1矩陣?yán)锞陀?*9*9=729行，表示在某個(gè)格子里填某個(gè)數(shù)。
同時(shí)在某個(gè)位置填了某個(gè)數(shù)后，那個(gè)數(shù)所在的列，行，9宮格也不能填那個(gè)數(shù)了，同時(shí)那個(gè)格子也不能填其他數(shù)了，所以某行填某個(gè)數(shù)有9*9，某列填某個(gè)數(shù)有9*9，某個(gè)9宮格填某個(gè)數(shù)9*9，某個(gè)位置填數(shù)9*9，一共就用324列。
建好這樣一個(gè)圖后，就直接用DancingLinks搜索，因?yàn)橄啾纫话愕穆闼讶哂嗪苌伲运俣确浅？臁?br>
/*
* $File: sudoku.cpp
* $Date: Sun Nov 29 20:22:32 2009 CST
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define LENGTH 9
#define SQRLEN 3
#define MAXN (LENGTH*LENGTH*LENGTH)
#define MAXM (4*LENGTH*LENGTH)
#define MAXNODE MAXN*MAXM
int max(int a,int b){
return a>b?a:b;
}
int map[MAXN][MAXM];
int U[MAXNODE],D[MAXNODE],L[MAXNODE],R[MAXNODE];
int S[MAXNODE],C[MAXNODE],ROW[MAXNODE];
int n,m;
int h = 0;//the Leftest and Upest node
int a[LENGTH][LENGTH];
void Init(){
freopen("sudoku.in","r",stdin);
freopen("sudoku.out","w",stdout);
for (int i = 0; i<LENGTH; i++)
for (int j = 0; j<LENGTH; j++)
scanf("%d",&a[i][j]);
}
int Row(int x,int y,int num){
return (x*LENGTH+y)*LENGTH+num-1;
}
#define SEC_POS 0
#define SEC_ROW 1
#define SEC_COL 2
#define SEC_SQR 3
#define PER_SEC LENGTH*LENGTH
void Fill(int x,int y,int num){
int row = Row(x,y,num);
map[row][SEC_POS*PER_SEC+x*LENGTH+y] = 1;
map[row][SEC_ROW*PER_SEC+x*LENGTH+num-1] = 1;
map[row][SEC_COL*PER_SEC+y*LENGTH+num-1] = 1;
map[row][SEC_SQR*PER_SEC+((x/SQRLEN)*SQRLEN+(y/SQRLEN))*LENGTH+num-1] = 1;
}
int cnt;
void BuildGraph(){
// Build The 0-1 Matrix
for (int i = 0; i<LENGTH; i++)
for (int j = 0; j<LENGTH; j++)
if (a[i][j])
Fill(i,j,a[i][j]);
else for (int k = 1; k<=LENGTH; k++)
Fill(i,j,k);
// Build Dacing Links
n = MAXN,m = MAXM;
for (int i = 0; i<n; i++)
for (int j = 0; j<m; j++)
if (map[i][j])
map[i][j] = ++cnt;
int tmp,s = 0,t = 0;
for (int i = 0; i<n; i++){
for (int j = 0; j<m; j++)
if (tmp=map[i][j])
L[tmp] = t, S[tmp] = i,t = tmp;
for (int j = m-1; j>=0; j--)
if (tmp=map[i][j])
R[tmp] = s, s =tmp;
R[t] = s,L[s] = t;
}
for (int j = 0; j<m; j++){
t = ++cnt;
for (int i = 0; i<n; i++)
if (tmp=map[i][j])
U[tmp] = t, t = tmp,C[tmp] = cnt, ++S[cnt];
s = cnt;
for (int i = n-1; i>=0; i--)
if (tmp=map[i][j])
D[tmp] = s, s = tmp;
D[cnt] = s,U[cnt] = t;
}
for (int i = cnt-m+1; i<=cnt; i++)
L[i] = i-1;
for (int i = cnt; i>cnt-m; i--)
R[i] = i+1;
R[h] = cnt-m+1,L[h] = cnt;
L[cnt-m+1] = R[cnt] = h;
}
int ans[MAXM+1];
void Cover(int c){
L[R[c]] = L[c],R[L[c]] = R[c];
for (int i = D[c];i!=c;i = D[i])
for (int j = R[i];j!=i;j = R[j])
U[D[j]] = U[j],D[U[j]] = D[j],S[C[j]]--;
}
void UnCover(int c){
for (int i = U[c];i!=c;i=U[i])
for (int j = L[i];j!=i;j = L[j])
S[C[j]]++,U[D[j]] = D[U[j]] = j;
L[R[c]] = R[L[c]] = c;
}
int Ans = -1;
int ScoreTable[LENGTH][LENGTH] = {
{6,6,6,6,6,6,6,6,6},
{6,7,7,7,7,7,7,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,9,10,9,8,7,6},
{6,7,8,9,9,9,8,7,6},
{6,7,8,8,8,8,8,7,6},
{6,7,7,7,7,7,7,7,6},
{6,6,6,6,6,6,6,6,6}
};
int score(int c){
int t = S[c];
int num = t%LENGTH+1;
int x = t/LENGTH/LENGTH%LENGTH;
int y = t/LENGTH%LENGTH;
return num*ScoreTable[x][y];
}
int ansmap[LENGTH][LENGTH];
//this function is not used in this program, but it gives out a solution of a sudoku
void GetAns(int step){
memset(ansmap,0,sizeof(ansmap));
for (int i = 0; i<step; i++){
int t = ans[i];
int x = t/LENGTH/LENGTH%LENGTH;
int y = t/LENGTH%LENGTH;
int num = t%LENGTH+1;
ansmap[x][y] = num;
}
}
void search(int step,int v){
if (R[h] == h){
Ans = max(Ans,v);
/* GetAns(step);
for (int i = 0; i<LENGTH; i++){
for (int j = 0; j<LENGTH; j++)
printf("%d ",ansmap[i][j]);
printf("\n");
}
printf("\n");*/
return;
}
int c,s = MAXNODE;
for (int i = R[h];i!=h; i=R[i])
if (S[i]<s)
s = S[i],c = i;
Cover(c);
for (int i = D[c];i!=c;i=D[i]){
ans[step] = S[i];
for (int j = R[i];j!=i;j = R[j])
Cover(C[j]);
search(step+1,v+score(i));
for (int j = L[i];j!=i;j = L[j])
UnCover(C[j]);
}
UnCover(c);
}
void DancingLinks(){
search(0,0);
printf("%d\n",Ans);
}
void Solve(){
BuildGraph();
DancingLinks();
}
int main(){
Init();
Solve();
return 0;
}
前兩天在yjw神牛和hyf神牛的共同努力下終于學(xué)會(huì)了后綴數(shù)組O(nlogn)倍增構(gòu)造方法。
構(gòu)造：
定義s[k][i]表示從s字符串的第i位開始的長度為k的一個(gè)字符串(后綴)，不夠的補(bǔ)零，sa[k][i]表示在所有長度為k的后綴中排序后大小為第i的后綴的位置。顯然sa[1]可以直接qsort得到。當(dāng)sa[k]求到過后，sa[2k]的每個(gè)元素都可以O(shè)(1)比較得出，這時(shí)用桶排，把sa[k]中排名相同的放在一起（放在一個(gè)桶里），那么對(duì)于每個(gè)不同的桶中的元素，他們之間的大小關(guān)系就已經(jīng)確定了，對(duì)于同一個(gè)桶中的元素，s[2k][i]的前k位是一樣的，可能不一樣只有后k位，而這個(gè)我們是已經(jīng)得到了的，所以通過sa[k][i]可以算出sa[2k][i-k]，桶排把排序過程復(fù)雜度降成了O(n)，總體構(gòu)造的復(fù)雜度就成了O(nlogn)。DC3算法貌似可以把復(fù)雜度降到O(n)...暫時(shí)只有膜拜的份了。
現(xiàn)在定義sa[i]為所有后綴排好序后的第i個(gè)后綴在原序列中的位置。
定義rank[i]為后綴s[i]在后綴排好序的序列中的排名。
當(dāng)sa數(shù)組求出來了過后，就可以構(gòu)造h和height數(shù)組了。
定義height數(shù)組為排好序的后綴中相鄰兩項(xiàng)的LCP(最常公共前綴)，即height[i] = LCP(sa[i],sa[i-1])。
定義h數(shù)組為原序列中的某個(gè)后綴與排好序的后綴中它的前一個(gè)的LCP，即h[i] = LCP(i,sa[rank[i]-1])。
然后有一個(gè)hyf和yjw神牛都不知道怎么來的很牛X的定理：h[i]>=h[i-1]-1。。。所以就可以在O(n)時(shí)間內(nèi)直接for出這個(gè)h數(shù)組來。。。（這步是最詭異也最精髓的，因?yàn)闆]有這個(gè)數(shù)組后綴數(shù)組就沒什么用了。。求神牛們講解下這個(gè)定理的證明。。）
求出了h數(shù)組后height數(shù)組也可以直接得到。
實(shí)現(xiàn)方式是用了兩個(gè)指針輪番上陣，看起來可能會(huì)有點(diǎn)糾結(jié)。。
應(yīng)用：
有了h和height數(shù)組后，我們就可以用它來做很多事情。但我還不是很熟，只會(huì)求一個(gè)字符串里面可以相交的最長重復(fù)字串的長度。。
cii(uva?)3901 Editor就是這樣一道題。
比如abcabcabc的最長重復(fù)字串就是abcabc。
其實(shí)求出了h和height數(shù)組后就變得很簡單，就是h或height數(shù)組中最大的一個(gè)。
歡迎大牛神牛們前來補(bǔ)充和指正！
1 /*
2 * $Date: Fri Nov 27 09:00:37 2009 CST
3 * $File: 3901.cpp
4 */
5 #include <iostream>
6 #include <cstdio>
7 #include <cstdlib>
8 #include <cstring>
9 #include <algorithm>
10 #define MAXLEN 50000
11
12 using namespace std;
13
14 char s[MAXLEN+1];
15 bool cmp(const int &a,const int &b){
16 return s[a]<s[b];
17 }
18
19 int sa[MAXLEN+1],rank[MAXLEN+1],tmp1[MAXLEN+1],tmp2[MAXLEN+1];
20 int h[MAXLEN+1],height[MAXLEN+1];
21
22 void Solve(){
23 scanf("%s",s);
24 int n = strlen(s);
25 s[n++] = 0;
26 for (int i = 0; i<n; i++)
27 sa[i] = i;
28 sort(sa,sa+n,cmp);
29
30 rank[sa[0]] = 0;
31 for (int i = 1; i<n; i++)
32 if (s[sa[i]]==s[sa[i-1]])
33 rank[sa[i]] = rank[sa[i-1]];
34 else
35 rank[sa[i]] = rank[sa[i-1]]+1;
36
37 int *s1 = sa,*s2 = tmp1,*b = tmp2, *r = rank;
38 for (int i = 1; i<n&&r[sa[n-1]]<n-1; i<<=1){
39 //b is the barrel
40 for (int j = 0; j<n; j++)
41 b[r[s1[j]]] = j;
42 for (int j = n-1; j>=0; j--)
43 if (s1[j]>=i)
44 s2[b[r[s1[j]-i]]--] = s1[j]-i;
45 for (int j = n-i; j<n; j++)
46 s2[b[r[j]]] = j;
47 swap(s1,s2);
48 b[s1[0]] = 0;//cause the barrel is now useless, use b as the new rank array
49 for (int j = 1; j<n; j++)
50 if (r[s1[j]]!=r[s1[j-1]]||r[s1[j]+i]!=r[s1[j-1]+i])
51 b[s1[j]] = b[s1[j-1]]+1;
52 else
53 b[s1[j]] = b[s1[j-1]];
54 swap(b,r);
55 }
56 //calc
57 for (int i = 0; i<n; i++){
58 if (r[i] == 0)
59 h[i] = 0;
60 else if (i == 0||h[i-1] == 0)
61 for (h[i] = 0; s[i+h[i]]==s[s1[r[i]-1]+h[i]];h[i]++);
62 else
63 for (h[i]=h[i-1]-1 ; s[i+h[i]]==s[s1[r[i]-1]+h[i]];h[i]++);
64 }
65 int Ans = 1;
66 for (int i = 0; i<n; i++)
67 Ans = max(Ans,h[i]);
68 printf("%d\n",Ans);
69 }
70 int main(){
71 int t;
72 scanf("%d",&t);
73 while (t--)
74 Solve();
75 return 0;
76 }
77
摘要: Dynamic Rankings
Time Limit: 10 Seconds
Memory Limit: 32768 KB
The Company Dynamic Rankings has developed a new kind of computer that is no
longer satisfied wit...
閱讀全文
學(xué)習(xí)某三位神牛。。在cppblog安個(gè)家，發(fā)點(diǎn)心得體會(huì)，一來作為自己的一個(gè)復(fù)習(xí)備忘錄，二來給更多的人分享知識(shí)～