|
置頂隨筆
#
諸位，Welcome～
前一陣一直在用人人……后來感覺還是要有個技術Blog……于是決定把這里復活……
我會主要在這里寫一些關于ACM/ICPC、Topcoder、以及其它競賽的文章
競賽不是全部，我也會寫一些感興趣的相關技術……
盡管是在javablog，而且我本意很想寫成java的，但是有時還是難免使用C++，因為在競賽中使用java，有利也有弊……
從ACM界退休之后，更多的是認識到自己的不足：ACM競賽盡管很有意義，但是也有其局限性……解題或者說解決問題固然重要，找到問題才是最重要的； 而且有好多問題，是在競賽中遇不到的。 于是我表示，為了快點跟上實驗室主流的步伐，爭取每天在Days的基礎上，再寫一篇技術Blog……好吧，這每天一篇壓力太大了……外加近日壓力很大，主要是受到外界的壓力，一個月一篇都無法保證……不過無論如何，我還是會刷題，繼續學點算法知識，為人生第10個賽季，NKU -> HOT ENCORE做準備，在有參賽資格的情況下，我永遠是NKU的ACM/ICPC contestant，會向著Au或許緩慢但是堅定的邁進……
近況神馬的詳見人人吧…… 好好寫日志，爭取讓讀者們有所收獲……
2012年1月26日
#
應刁哥多年前的約稿，外加結合編譯原理系列連載，整理一下上一篇文章，寫一個簡易的匯編教程…… 盡管謬誤，疏漏若干，但是本文的目的不在于培養學霸，而在于讓不會匯編的人簡單看看就能寫出個基本能用的匯編程序…… 在程序設計中，我們知道一項基本原理：語言越高級，一般來講容易編寫，形式簡潔，可移植性強，效率低…… 反過來，語言越低級，越難編寫，代碼越容易是又臭又長還看不懂，越難移植，但是效率會很高…… 匯編就是比較低級的語言了，由于其不太好移植，匯編版本又多種多樣 因此，本著活學活用，到時候不會就查手冊的原則，本文不會太著重強調語法，語法以intel語法為主…… Chapter1：一些基本知識 首先，CPU有若干寄存器，在32位CPU中，形如eax，ebx，ecx，edx……64位CPU則為rax，rbx…… 雖然寄存器這個名字很NB，其實它的本質上就是int，為了向下兼容的需要，一些老的程序，也有可能能在新型的CPU上運行（詳見DOS老游戲，有的能玩，有的不能玩） 以64位舉例： 64位寄存器rax，低32位是eax，eax低16位是ax，ax高8位叫ah，低8位叫al…… CPU只能直接對寄存器進行運算……因為電路結構就是那樣的……因此，所有的操作，都需要經過寄存器 譬如賦值：A = 1，實際上是 AX = 1; A = AX; 譬如 A = A + B，應該是 AX = A; AX += B; A = AX; 這樣 我是比較不求甚解的，99%功能（運算，判斷，指針）等，使用eax，ebx，ecx，edx都能搞定……于是咱們也就不說別的了…… Chapter2：匯編的基本語法： 匯編語言大概分為四個段，其中比較需要記住的就是代碼段和數據段…… 用類似高級語言的思路來講，數據段用于定義一些全局變量，代碼段用于寫程序…… 來看一個簡單的 Hello World（環境：yasm，64位） global main extern printf section .data ctrlout db '%s', 10, 0 hw db 'Hello World', 0 ; this is a comment section .text main: mov rax, 0 mov rdi, ctrlout mov rsi, hw call printf mov rax, 0 ret 其中，剛開始global main 表示程序入口，由于這里直接調用了Linux的函數printf，之后需要gcc編譯，所以叫做main，如果只使用中斷輸出的話，可以搞成_start 之后extern意義和C++類似，表示這個函數在別處，叫編譯器以為他有就行…… section .data 表示數據段，后面是一些定義，以及初始化 注意這里定義的東西類型都像是指針一樣，ctrlout，hw 實際上是地址…… 初始化必須搞的干凈一點，有一次調了半天不對，就是因為一個64位int，前4位沒有初始化成0…… 之后 section .text 表示代碼段，這里調用C語言函數，網上說，64位匯編中，參數傳遞方式有了修改，大概是有4~5個寄存器專門保存參數，如果參數過多，再放入棧，rax存放棧中的參數個數……我們想printf("%s","Hello World")，就要調用兩個參數，于是，我們把第一個參數，字符串ctrlout的指針mov進rdi，hw mov進rsi，rax賦值為0 ，然后，調用…… （實現時，需要手冊自行查閱一下本機怎么搞） 函數的返回值在rax，于是return 0 然后 yasm -f elf64 XXX.asm gcc -o XXX XXX.o ./XXX 一個嶄新的hello world 出現了…… Chapter3：匯編的一些簡單指令： 由于這是速成教程，選取一部分指令……要記住，CPU只能直接對寄存器進行運算…… mov：相當于賦值， mov eax，b 相當于eax = b； 注意：mov 后面的兩個東西至少要有一個是寄存器…… 同時，和高級語言一樣，不能搞什么 mov 10，eax…… add：add eax，b 相當于eax+=b sub：基本同上…… mul || imul：前面是無符號的乘，后面是有符號的乘，默認被乘數在AX，于是指令形如：mul BX，如果有溢出，則高位溢出到DX，記得備份DX的東西…… div || idiv：前面是無符號整除，后面是有符號整除，默認被除數是DX（高16位）和AX（低16位），因此，除法之前記得把DX清零，否則數會不對…… 之后商在AX，余數在DX 指令形如：div BX push/pop：每個程序都有棧，或者是在程序中定義堆棧段，或者使用默認棧 push eax，表示把eax放進棧里，pop ebx，表示取出棧頂，放在ebx中…… push和pop異常重要，一個重要作用就是保護寄存器，譬如DX中有內容，但是現在要做乘法，沒準會破壞DX（見上），于是，先PUSH DX，然后，乘法，然后POP DX，又好比你要調用一個函數，但是寄存器里有有用的信息，不保證這個函數不會破壞，于是，把所有寄存器先push進去，運行函數，然后再pop出來，這是常用技巧…… 另外也可以用來給函數傳參數，傳時倒序壓入，用時順序取出，棧，先進后出，你們懂的…… Chapter4：if以及循環 首先我們要記得，被Dijkstra老爺子罵的一文不值的goto…… jmp語法和C++里的goto基本一樣 start： XXX jmp start 然后，匯編沒有if then，但是有條件goto 有個語句叫做cmp cmp X，Y （老原則，這兩個得有一個寄存器……如果和常數比較，常數必須在后面） 傳說中具體實現是減法…… 這個的效果是可能改變若干標識位的值……譬如：0標識，進位標識，溢出標識……等等…… 然后，有若干指令 jl XX（l==less） 相當于 if (x<y) goto XX; 下同 jg XX（g==greater） jle XX（ne==less or equal） jge XX（ge==greter or equal） jnle XX（n==no->nle==g） jnge XX（n==no->nge==l） 有了if then，各種運算，我們就能做出來&&,||的邏輯 有了if then，我們也能做出循環…… 很多的功能就有了…… Chapter5：實戰 看看 int main() { int a,b,c; input(a); input(b); if (a < b) { c = a; } else { c = b; } print(c); } 用匯編翻譯出來啥樣： global main extern printf extern scanf section .data ctrlout db '%lld', 10, 0 ctrlin db '%lld', 0 _a db 0,0,0,0,0,0,0,0 _b db 0,0,0,0,0,0,0,0 _c db 0,0,0,0,0,0,0,0 section .text main: mov rax, 0 mov rdi, ctrlin mov rsi, _a call scanf mov rax, 0 mov rdi, ctrlin mov rsi, _b call scanf MOV rax, [_a] CMP rax, [_b] jl @0 jmp @2 @0: MOV rax, [_a] MOV [_c], rax jmp @1 @2: MOV rax, [_b] MOV [_c], rax @1: mov rax, 0 mov rdi, ctrlout mov rsi, [_c] call printf mov rax, 0 ret Chapter6：其它 由于現實生活中，我需要寫匯編時候實在是少，因此也沒啥經驗……盡管借助手冊，可以對付著寫一點匯編代碼，但是那是不科學的……對我來講，匯編告訴我們的一些底層的東西更有價值，可以在高級語言中有所體現：譬如一些表達式的寫法，可以考慮寫的更科學一些，譬如 c = a / b, q = a % b，記得寫成 c = a / b; q = a - c * b，譬如靈活使用switch，等等……
2011年12月2日
#
最近，做OS大作業，編譯大作業，和進行實驗室工作，強烈認識到了自己對C語言的了解不多……
于是今天老圖借了本書，學習一下……
來看一下我最頭疼的define……
define的作用：
一是直接定義一個東西……類似標記
譬如：
1 #ifndef test
2 #define test
3 /*
4 balabalabala .
5 */
6 #endif
劉JX老師在大一C＋＋課上教育我們，寫頭文件一定要加上這么個東西……為什么呢……
再提一下include的事情…… #include<XXXX>，實際上是直接把XXXX整個文件COPY了進來……
如果出現這樣的情況：
1 #include <set>
2 #include <map>
我們知道，Cpp的 map 實際上是用 set 做的，map的頭文件里肯定有一個 #include <set>，那么，相當于set這個文件在這段程序里面出現了兩次……
如果沒有ifndef這套的話，相當于將set中的代碼重復貼了兩次，就粗大事了……
代碼第一段ifndef test 代表：如果沒有define test，則執行下面的那段，先 define test，然后balabala，最后endif，下次再看到這段代碼的時候，ifndef test ，此時會發現test已經define過了，直接endif，中間balabala的代碼不會重復兩次……
二是直接定義一些……怎么說呢，類似替換規則的東西……
譬如：直接定義常量：
1 #define MAXN 10000
這個實際上就是直接在程序編譯之前，將里面的MAXN都替換成10000
預先定義一些常量，好處大家都懂：避免程序內部太多的“magic number”，增強可讀性，也便于修改……這里相當于直接替換，貌似C的數組，定義的時候不能用int做下標，const int也不行，只能通過這個方法，用立即數……
譬如：給一些東西改個名字：
1 #include <stdio.h>
2 #define Q scanf
3
4 int main() {
5 int a;
6 Q("%d",&a);
7 printf("%d\n",a);
8 return 0;
9 }
這里有一些玄機： 1：#似乎是因為沒有轉義？所以不能胡用…… 譬如：#define USEMATH #include <math.h> 是不能達到預期效果的…… 2：如果這一行太長，可以用\表示和下一行連起來…… 貌似這個'\'也沒轉義， #define BACKSLASH \ 也是不行的…… 譬如：可以定義一些簡單的函數： #define max(a,b) ((a) > (b) ? (a) : (b)) 某種意義上這比template NB... 這樣，int c ＝ max(a,b); 就自動替換成 int c ＝((a) > (b) ? (a) : (b)); 了 此處有一個技巧：有的時候，咱們需要用大括號來實現這個"函數"，但是，由define直接替換知道，這個替換出來，相當于{/*balabala*/};這樣，語法是錯的…… 于是怎么辦呢……咱們可以用 do {/*balabala*/} while(0) 這樣的形式，繞開這個問題…… 在上次OS大作業上咱們都見到了…… 此處還有兩個玄機：一是千萬記得要加括號……為什么呢…… 譬如： #define mul(a,b) a * b 看著挺好，mul(1,2 + 3)就出事了…… 直接替換出來，是 1 * 2 + 3，就錯了…… 正確方法是：#define mul(a,b) ((a) * (b))，萬無一失…… 另一個玄機是避免++,--之類的，譬如 #define sqr(a) ((a) * (a)) sqr(a++)，如果sqr是真的函數的話，計算出沒有問題……但是define會忠實的給你替換成((a++) * (a++))……怎么加的不重要，結果就不是你想的了…… 最后有兩個用法，一個是#，#會將你作為“函數”的“參數”傳入的東西轉化為字符串；一個是...，作用一看便知： 1 #include <stdio.h> 2 #define max(a,b) ((a) > (b) ? (a) : (b)) 3 #define PRINT( ) printf(__VA_ARGS__) 4 #define debug(x) do { \ 5 PRINT(#x); \ 6 PRINT(" = %d\n",(x)); \ 7 } while (0) 8 9 int main() { 10 int a,b; 11 scanf("%d%d",&a,&b); 12 debug(a); 13 debug(b); 14 debug(a + b); 15 debug(max(a,b)); 16 return 0; 17 }
2011年10月7日
#
題意很簡單……雙方給N個人（N<=6）打三國殺1V1，你知道對手每個人能克制你哪些人，我們認為兩個人對打，他能克你則他勝利，否則你勝利；某人的N個人死光就輸了……你需要組織陣容按照順序對抗對手……求有沒有一個順序，無論對手順序如何，你都能勝…… N！枚舉自己的順序，然后N！枚舉對方的順序，O（N）驗證即可…… 注意字典序最小…… 1 #include <cstdio>
2 #include <cstring>
3 #include <string>
4 #include <map>
5 #include <algorithm>
6 #include <iostream>
7
8 using namespace std;
9
10 map<string,int> mp;
11 int n;
12 int res[10];
13 int my[10];
14 char buf[50];
15 char name[10][50];
16 string ans;
17
18 void check() {
19 int enemy[] = {0,1,2,3,4,5,6,7,8,9};
20 do {
21 int i = 0;
22 int j = 0;
23 while (i < n && j < n) {
24 if ((1 << my[i]) & res[enemy[j]]) i ++; else j++;
25 }
26 if (i == n) return;
27 } while (next_permutation(enemy,enemy + n));
28 string tmp;
29 for (int i = 0; i < n; i++) {
30 if (i) tmp += " ";
31 tmp += name[my[i]];
32 }
33 if (ans == "" || ans > tmp) ans = tmp;
34 }
35
36 int main() {
37 int nn; scanf("%d",&nn);
38 for (int ii = 1; ii <= nn; ii++) {
39 mp.clear();
40 memset(res,0,sizeof(res));
41 scanf("%d",&n);
42 for (int i = 0; i < n; i++) {
43 scanf("%s",name[i]);
44 mp[string(name[i])] = i;
45 }
46 for (int i = 0; i < n; i++) {
47 int m; scanf("%d",&m);
48 for (int j = 0; j < m; j++) {
49 scanf("%s",buf);
50 int tmp = mp[string(buf)];
51 res[i] |= 1 << tmp;
52 }
53 }
54 for (int i = 0; i < n; i++) {
55 my[i] = i;
56 }
57 ans = "";
58 do {
59 check();
60 } while (next_permutation(my,my + n));
61 printf("Case %d: ",ii);
62 if (ans == "") {
63 puts("No");
64 } else {
65 puts("Yes");
66 for (int i = 0; i < ans.length(); i++) putchar(ans[i]);
67 putchar(10);
68 }
69 }
70 return 0;
71 }
2011年9月18日
#
這題比賽時候過得很糾結……最后還是學長過的……比賽時候腦子可能不夠清楚，一直WA……
首先，這個題要分成兩個部分解決：
第一部分：從n個東西里面取出r個，每個間距至少為 k （1～K不行，1～K ＋ 1行）
第二部分：將這r個東西分成至多m組，可以有空組
第二部分貌似好久之前搞OI的時候干過……貼過來：
N球放在M個盒子里，求共有多少種放法
但是有3個不同的條件 ：N個球是否相同，M個盒子是否相同，是否允許有盒子空著
|
球和球
|
盒和盒
|
空盒
|
情況數
|
|
有區別
|
有區別
|
有空盒
|
mn
|
|
有區別
|
有區別
|
無空盒
|
M！s（n,m）
|
|
有區別
|
無區別
|
有空盒
|
S(n,1)+s(n,2)+…+s(n,m),n>=m
S(n,1)+s(n,2)+…+s(n,n),n<=m
|
|
有區別
|
無區別
|
無空盒
|
S(n,m)
|
|
無區別
|
有區別
|
有空盒
|
C(n+m-1,n)
|
|
無區別
|
有區別
|
無空盒
|
C(n-1,m-1)
|
|
無區別
|
無區別
|
有空盒
|
F(m,n)
|
|
無區別
|
無區別
|
無空盒
|
F(m,n-m)
|
|
然后，其中的F(m,n)貌似是當時寫過的一個DP，S(M,N)是第二類stirling數…… 遞推公式： 1 int S(int n,int m) {
2 if (n == m || m == 1) return 1;
3 return m * S(n - 1, m) + S(n - 1, m - 1);
4 } 第一部分：可以看作這么一個生成函數的相關問題：由于每個東西之間都隔了>=K－1的一段距離，因此一個可行解可以看作，長度為K，K + 1，K + 2的棍子r － 1個（我們認為每個棍子的頭是我們取的點），拼接成長度為Len的一個大段，之后再堵上一個，就是一個Len ＋１的可行解…… 而r - 1根棍子，拼成長度為Len 的可行解數目，就是(X^K + X^(K + 1) + X^(K + 2) + .....) ^ (r - 1)，這個多項式，展開之后，X^Len項前面的系數…… 不過……由于數據范圍，直接搞是不成的…… 于是提取，變形：X^(K * (r - 1)) * (1 + X + X^2 + X ^3 +....)^(r - 1) 然后再變形：X^(K * (r - 1)) * (1/(1 - x))^(r - 1)…… 然后參照Matrix67大神的日志，展開后面那項：
1/(1-x)^n=1+C(n,1)x^1+C(n+1,2)x^2+C(n+2,3)x^3+...+C(n+k-1,k)x^k+... 我們知道，要求長度為len的可行數目，也就是要X^Len項前面的系數，然后，由于前面提取出來了一個K * (r - 1)，也就是去后面找len - K * (r - 1) 項的系數…… 也就是說，令pow = len - K * (r - 1)，答案就是C(r - 1 + pow - 1, pow)…… 不過這還沒完，因為咱們要拼成的長度是len，而總的長度是N，需要乘上這個長度len的開頭位置的可能數…… 另外還需要特殊處理：咱們在處理的時候，是先用r - 1個拼接成長度為Len的一個大段，再堵上最后一個……當r == 1需要特判…… 代碼： 1 #include <cstdio>
2 #include <cstring>
3
4 typedef long long Long;
5 const Long MOD = 1000000007;
6
7 Long F[1010][1010];
8 Long C[2010][2010];
9 Long S(int n,int m) {
10 if (n == m || m == 1) return 1LL;
11 if (F[n][m] > 0) return F[n][m];
12 return F[n][m] = (m * S(n - 1, m) % MOD + S(n - 1, m - 1)) % MOD;
13 }
14 void init() {
15 for (int i = 0; i <= 2000; i++) {
16 for (int j = 0; j <= i; j++) {
17 if (j == 0) C[i][j] = 1;
18 else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
19 }
20 }
21 }
22 int n,r,k,m;
23
24 int main() {
25 memset(F,0xff,sizeof(F));
26 init();
27 while (scanf("%d%d%d%d",&n,&r,&k,&m) > 0) {
28 if (r == 1) {printf("%d\n",n); continue;}
29 Long ans = 0;
30 for (int i = 1; i <= m && i <= r; i++) {
31 ans = (ans + S(r,i)) % MOD;
32 }
33 Long tmp = 0;
34 for (int len = k * (r - 1); len < n; len++) {
35 int left = n - len;
36 int pow = len - k * (r - 1);
37 // r > 1 !!
38 tmp = (tmp + left * C[r - 1 + pow - 1][pow]) % MOD;
39 }
40 ans = ans * tmp % MOD;
41 printf("%lld\n",ans);
42 }
43 return 0;
44 }
思路是維護每個字母開頭，長度為3的串是不是wbw…… 這樣相當于將長度為N的字符串變成長度為N－2的序列，然后一系列修改就是將序列中1變0，0變1，查詢就是求一段的和 BIT，大家都懂的…… 1 #include <cstdio>
2 #include <cstring>
3
4 int n,m;
5 char str[50010];
6 int arr[50010];
7
8 inline int lowbit(int x) {return x & -x;}
9
10 void update(int x,int delta) {
11 for (int i = x; i <= n; i += lowbit(i)) {
12 arr[i] += delta;
13 }
14 }
15
16 int sum(int x) {
17 int ret = 0;
18 while (x) {ret += arr[x]; x -= lowbit(x);}
19 return ret;
20 }
21
22 int sum(int l,int r) {
23 if (l > r) return 0;
24 if (l == 0) return sum(r);
25 return sum(r) - sum(l - 1);
26 }
27
28 int main() {
29 int nn; scanf("%d",&nn);
30 for (int ii = 1; ii <= nn; ii++) {
31 scanf("%d%d",&n,&m);
32 memset(str,0,sizeof(str));
33 memset(arr,0,sizeof(arr));
34 scanf("%s",str + 1);
35 for (int i = 1; i + 2 <= n; i++) {
36 if (str[i] == 'w' && str[i + 1] == 'b' && str[i + 2] == 'w') {
37 update(i,1);
38 }
39 }
40 printf("Case %d:\n",ii);
41 while (m--) {
42 int ctrl; scanf("%d",&ctrl);
43 if (ctrl == 0) {
44 int l,r; scanf("%d%d",&l,&r); printf("%d\n",sum(l + 1,r - 1));
45 } else {
46 int pos; char buf[10]; scanf("%d",&pos); scanf("%s",buf); pos ++;
47 for (int i = pos - 2; i <= pos && i + 2 <= n; i++) {
48 if (str[i] == 'w' && str[i + 1] == 'b' && str[i + 2] == 'w') {
49 update(i,-1);
50 }
51 }
52 str[pos] = buf[0];
53 for (int i = pos - 2; i <= pos && i + 2 <= n; i++) {
54 if (str[i] == 'w' && str[i + 1] == 'b' && str[i + 2] == 'w') {
55 update(i,1);
56 }
57 }
58 }
59 }
60 }
61 return 0;
62 }
數學苦手……一通推，無法可行…… 于是只能想沒有辦法的辦法：打表…… 1 #include <cstdio>
2 #include <algorithm>
3
4 using namespace std;
5 typedef long long Long;
6
7 int arr[20];
8 Long ans = 0;
9 int n;
10
11 void dfs(int now,int sum) {
12 if (sum < 0) return;
13 if (now == n) {ans ++; return;}
14 dfs (now + 1, sum + (1 << arr[now] ));
15 dfs (now + 1, sum - (1 << arr[now] ));
16 }
17
18 int main() {
19 for (n = 1; n <= 10; n++) {
20 for (int i = 0; i < n; i++) {
21 arr[i] = i;
22 }
23 Long cnt = 0;
24 ans = 0;
25 do {
26 dfs(0,0);
27 cnt ++;
28 } while (next_permutation(arr,arr + n));
29 printf("%lld ",ans);
30 printf("%lld\n",cnt << n);
31 }
32 return 0;
33 } 輸出： 1 2 3 8 15 48 105 384 945 3840 10395 46080 135135 645120 2027025 10321920 34459425 185794560 654729075 3715891200 然后大家都懂了…… 1 import java.util.*;
2 import java.io.*;
3 import java.math.BigInteger;
4
5
6 class Main {
7
8 BigInteger[] ans1 = new BigInteger [501];
9 BigInteger[] ans2 = new BigInteger [501];
10 final BigInteger TWO = BigInteger.valueOf(2);
11
12 void solve() throws Exception {
13 MyReader in = new MyReader();
14 int nn = in.nextInt();
15 ans1[1] = BigInteger.ONE;
16 ans2[1] = TWO;
17 for (int i = 2; i <= 500; i++) {
18 ans1[i] = ans1[i - 1].multiply(BigInteger.valueOf(i + i - 1));
19 ans2[i] = ans2[i - 1].multiply(BigInteger.valueOf(i)).multiply(TWO);
20 BigInteger gcd = ans1[i].gcd(ans2[i]);
21 ans1[i] = ans1[i].divide(gcd);
22 ans2[i] = ans2[i].divide(gcd);
23 }
24 PrintWriter out = new PrintWriter(System.out);
25 while (nn-- > 0) {
26 int n = in.nextInt();
27 out.print(ans1[n]);
28 out.print("/");
29 out.println(ans2[n]);
30 }
31 out.flush();
32 }
33
34 public static void main(String args[]) throws Exception {
35 new Main().solve();
36 }
37
38 void debug(Objectx) {
39 System.out.println(Arrays.deepToString(x));
40 }
41 }
42
43 class MyReader {
44 BufferedReader br = new BufferedReader (
45 new InputStreamReader (System.in));
46 StringTokenizer in;
47 String next() throws Exception {
48 if (in == null || !in.hasMoreTokens()) {
49 in = new StringTokenizer(br.readLine());
50 }
51 return in.nextToken();
52 }
53 int nextInt() throws Exception {
54 return Integer.parseInt(next());
55 }
56 }
2011年9月10日
#
題意：給一個序列，要求維護兩個操作
1：將區間[L,R]里面的數開方下取整
2：求區間[L,R]里面元素的和
第一反應是線段樹，但是這里面有個矛盾：開方不好處理，如果將序列表示成對數，求和又不好處理……
幸運的是，開方操作收斂的很快，從long long 到 1，只要8次，于是每次對區間操作，我們在線段樹基礎上進行改動：線段樹最后將待查詢區間會分成Log（N）個區間，絕對不能將操作區間分成小段……但是現在要這么做，因為每個點最多被覆蓋8次之后就是1了……于是對每個節點維護一個isone標記，標記這一段是不是1，每次修改都遞歸下去直接修改非1的點，并且維護isone標記……這樣均攤下來，每個點最多被改8次…… 1 #include <cstdio>
2 #include <cmath>
3 #include <cassert>
4
5 typedef long long Long;
6 Long sum[410000];
7 Long data[110000];
8 bool isone[410000];
9 int n;
10 const int root = 1;
11
12 void build(int now,int left,int right) {
13 if (left == right) {
14 sum[now] = data[left];
15 isone[now] = sum[now] == right - left + 1;
16 } else {
17 int mid = (left + right) >> 1;
18 build(now + now,left,mid);
19 build(now + now + 1,mid + 1,right);
20 sum[now] = sum[now + now] + sum[now + now + 1];
21 isone[now] = sum[now] == right - left + 1;
22 }
23 }
24
25 Long mySqrt(Long x) {
26 double tmp = x;
27 x = Long(sqrt(tmp) + 1e-8);
28 return x;
29 }
30
31 Long getSum(int now,int left,int right,int l,int r) {
32 if (left > r || right < l) return 0;
33 if (l <= left && right <= r) return sum[now];
34 int mid = (left + right) >> 1;
35 return getSum(now + now,left,mid,l,r)
36 + getSum(now + now + 1,mid + 1, right, l, r);
37 }
38
39 void change(int now,int left,int right,int l,int r) {
40 if (left > r || right < l) return;
41 if (isone[now]) return;
42 if (left == right) {
43 sum[now] = mySqrt(sum[now]);
44 isone[now] = sum[now] == right - left + 1;
45 } else {
46 int mid = (left + right) >> 1;
47 change(now + now,left,mid,l,r);
48 change(now + now + 1,mid + 1,right,l,r);
49 sum[now] = sum[now + now] + sum[now + now + 1];
50 isone[now] = sum[now] == right - left + 1;
51 }
52 }
53
54 int main() {
55 int nn = 0;
56 while (scanf("%d",&n) == 1) {
57 for (int i = 0; i < n; i++) {
58 scanf("%lld",data + i);
59 assert(data[i] > 0);
60 }
61 build(root,0,n-1);
62 int m;
63 scanf("%d",&m);
64 printf("Case #%d:\n", ++ nn);
65 while (m--) {
66 int ctrl,l,r;
67 scanf("%d%d%d",&ctrl,&l,&r);
68 l --; r --;
69 if (l > r) {int tmp = l; l = r; r = tmp;}
70 if (ctrl == 1) {
71 printf("%lld\n",getSum(root,0,n-1,l,r));
72 } else {
73 change(root,0,n-1,l,r);
74 }
75 }
76 printf("\n");
77 }
78 return 0;
79 }
題意：給一個方格的1E9*1E9的地圖，以及若干炸彈，每個炸彈的功能是將某行／某列的所有東西消滅，求若干炸彈依次下去，每次消滅了多少東西…… STL硬搞即可…… 1 #include <cstdio>
2 #include <set>
3 #include <map>
4
5 using namespace std;
6 typedef multiset<int> sint;
7 typedef map<int, multiset<int> > line;
8
9 line x;
10 line y;
11
12 int bomb(line &x, line &y, int pos) {
13 int ret = x[pos].size();
14 for (sint::iterator ii = x[pos].begin();
15 ii != x[pos].end();
16 ii++) {
17 y[*ii].erase(pos);
18 }
19 x[pos].clear();
20 return ret;
21 }
22
23 int main() {
24 for (;;) {
25 int n,m;
26 scanf("%d%d",&n,&m);
27 if (n + m == 0) break;
28 x.clear();
29 y.clear();
30 while (n--) {
31 int tx,ty;
32 scanf("%d%d",&tx,&ty);
33 x[tx].insert(ty);
34 y[ty].insert(tx);
35 }
36 while (m--) {
37 int ctrl,pos;
38 scanf("%d%d",&ctrl,&pos);
39 printf("%d\n",ctrl == 0 ? bomb(x,y,pos) : bomb(y,x,pos));
40 }
41 printf("\n");
42 }
43 return 0;
44 }
2011年5月23日
#
1 /*
2 Author: Sweetsc 寂寞之余所做
3
4 設定集
5 蹭的累：http://baike.baidu.com/view/2213196.htm
6 比利：http://baike.baidu.com/view/2280157.htm
7 Yoooooooooo：http://124.228.254.229/html/ent/20110421/192948.html
8 */
9
10
11 import java.util.*;
12
13 class Event {
14 static Random rand = new Random();
15 final static String[] eventlist = {
16 "散步",
17 "吃飯",
18 "看電影",
19 "購物",
20 "旅游"
21 };
22 int event = rand.nextInt() % eventlist.length;
23 String getEvent() {
24 return eventlist[event];
25 }
26 }
27
28 class Girl {
29 final static String[] character = {
30 "蹭的累",
31 "天然呆",
32 "普通",
33 "軟妹子",
34 "偽娘",
35 "宅女",
36 "腐女",
37 "百合"
38 };
39 static Random rand = new Random();
40
41 String name;
42 int type;
43 int friendship;
44
45 Girl(String name) {
46 this.name = name;
47 type = rand.nextInt() % character.length;
48 friendship = 0;
49 }
50
51 String getName() {
52 String ans = name;
53 if (friendship < 10) {
54 if (type == 0) return "閉嘴，基佬！";
55 return "";
56 }
57 return ans;
58 }
59
60 void meet() {
61 friendship ++;
62 }
63
64 void date(Event event) {
65 if (friendship < 20) {
66 if (type == 0) {
67 System.out.println("我為什么要和你" + event.getEvent() + "啊？");
68 } else {
69 System.out.println("不好意思，我那天有事.");
70 }
71 } else {
72 if (type == 0) {
73 System.out.println("偶爾和你去" + event.getEvent() + "也可以啊");
74 } else {
75 System.out.println("好啊");
76 }
77 friendship += rand.nextInt() % 10 + 5;
78 }
79 }
80
81 void lastJudgeMent() {
82 if (friendship < 80) {
83 System.out.println("她沉默了許久，轉身離開");
84 System.out.println("然后就沒有然后了……");
85 System.err.println("系統提示，好感度不足！");
86 friendship = 0x80000000;
87 return;
88 } else {
89 switch (type) {
90 case 0 :
91 System.out.println("侖家可不是因為喜歡才答應的哦！");
92 break;
93 case 4 :
94 System.out.println("Yoooooooooooooooooo!!!!");
95 System.out.println("你從此，跟隨比利，走向了追求人生哲學的道路");
96 System.err.println("系統提示，你求交往的對象是偽娘！");
97 break;
98 case 6 :
99 System.out.println("她滿懷欣喜的答應了");
100 System.out.println("過了幾天，她介紹了個男友給你");
101 System.out.println("Yoooooooooooooooooo!!!!");
102 System.out.println("你從此，跟隨比利，走向了追求人生哲學的道路");
103 System.err.println("系統提示，你求交往的對象是腐女！");
104 break;
105 case 7 :
106 System.out.println("她面無表情的說：我喜歡的是女生！");
107 System.out.println("然后就沒有然后了……");
108 friendship = 0x80000000;
109 break;
110 default :
111 System.out.println("她滿臉通紅,沉默了許久，之后羞澀的說道：好吧");
112 System.out.println("從此，你和" + character[type] + name + "過上了幸福的生活");
113 System.err.println("終于Goodend了，可喜可賀可喜可賀");
114 }
115 }
116 }
117
118 }
2011年4月6日
#
原文：
Java線程：新特征-障礙器，這是該作者的原創作品，允許轉載，轉載時請務必以超鏈接形式標明文章 原始出處 、作者信息和本聲明。否則他將追究法律責任……
Hmm……好怕怕，轉個日志都會被追究法律責任……
不過要感謝原文的蘭州，在蘭州的文章幫助下，今天突然發現了靈感，改造了改造蘭州的代碼……
在ACM中的作用，我覺得可以這樣：
1：對于單文件多case的題，開多線程，每個線程跑一個case，之后再調用收尾的任務輸出
2：對于單case且可以并行的情況，開若干線程處理之后，調用收尾函數來最后處理、輸出
以下是一個簡單的求和代碼，實際效果，在我的雙核CPU上用時大概減少了一半
1 import java.util.concurrent.BrokenBarrierException;
2 import java.util.concurrent.CyclicBarrier;
3
4 public class Test {
5 public static int[] ans;
6 void run() {
7 ans = new int[4];
8 int now = 0;
9 for (int i = 0; i < 400000000; i++) {
10 now = (now + i) % 9999997;
11 }
12 System.out.println(now);
13 CyclicBarrier cb = new CyclicBarrier(4, new MainTask());
14 new SubTask(0,0,100000000,cb).start();
15 new SubTask(1,100000000,200000000,cb).start();
16 new SubTask(2,200000000,300000000,cb).start();
17 new SubTask(3,300000000,400000000,cb).start();
18 }
19 public static void main(String[] args) {
20 new Test().run();
21 }
22 }
23
24 class MainTask implements Runnable {
25 public void run() {
26 int ans = 0;
27 for (int i = 0; i < 4; i++) {
28 ans = (ans + Test.ans[i]) % 9999997;
29 }
30 System.out.println(ans);
31 }
32 }
33
34 class SubTask extends Thread {
35 private int pos;
36 private int left;
37 private int right;
38 private CyclicBarrier cb;
39 final int mod = 9999997;
40
41 SubTask(int pos,int left,int right,CyclicBarrier cb) {
42 this.pos = pos;
43 this.left = left;
44 this.right = right;
45 this.cb = cb;
46 }
47
48 public void run() {
49 int ans = 0;
50 for (int i = left; i < right; i++) {
51 ans = (ans + i) % mod;
52 }
53 Test.ans[pos] = ans;
54
55 try {
56 cb.await();
57 } catch (InterruptedException e) {
58 e.printStackTrace();
59 } catch (BrokenBarrierException e) {
60 e.printStackTrace();
61 }
62 }
63 }
|