|
2011年9月10日
#
应刁哥多年前的约稿，外加结合编译原理系列连载，整理一下上一篇文章，写一个简易的汇编教程…… 尽管谬误，疏漏若干，但是本文的目的不在于培养学霸，而在于让不会汇编的人简单看看就能写出个基本能用的汇编程序…… 在程序设计中，我们知道一项基本原理：语言越高级，一般来讲容易编写，形式简洁，可移植性强，效率低…… 反过来，语言越低级，越难编写，代码越容易是又臭又长还看不懂，越难移植，但是效率会很高…… 汇编就是比较低级的语言了，由于其不太好移植，汇编版本又多种多样 因此，本着活学活用，到时候不会就查手册的原则，本文不会太着重强调语法，语法以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，等等……
最近，做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 }
题意很简单……双方给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 }
这题比赛时候过得很纠结……最后还是学长过的……比赛时候脑子可能不够清楚，一直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 }
题意：给一个序列，要求维护两个操作
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 }
|