[NKU]sweet @ Google && TopCoder && CodeForces

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks

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,等等……
posted @ 2012-01-26 22:42 sweetsc 阅读(659) | 评论 (0)编辑 收藏

最近,做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 }
posted @ 2011-12-02 01:59 sweetsc 阅读(303) | 评论 (0)编辑 收藏

题意很简单……双方给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 }
posted @ 2011-10-07 20:15 sweetsc 阅读(600) | 评论 (0)编辑 收藏

这题比赛时候过得很纠结……最后还是学长过的……比赛时候脑子可能不够清楚,一直WA……
首先,这个题要分成两个部分解决:
第一部分:从n个东西里面取出r个,每个间距至少为 k (1~K不行,1~K + 1行)
第二部分:将这r个东西分成至多m组,可以有空组
第二部分貌似好久之前搞OI的时候干过……贴过来:
N球放在M个盒子里,求共有多少种放法

但是有3个不同的条件 :N个球是否相同,M个盒子是否相同,是否允许有盒子空着

球和球

盒和盒

空盒

情况数

有区别

有区别

有空盒

mn

有区别

有区别

无空盒

Msn,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 == 1return 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 +1的可行解……
而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 == 1return 1LL;
11     if (F[n][m] > 0return 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 }
posted @ 2011-09-18 22:56 sweetsc 阅读(1919) | 评论 (3)编辑 收藏

思路是维护每个字母开头,长度为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 == 0return 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 }
posted @ 2011-09-18 20:44 sweetsc 阅读(726) | 评论 (3)编辑 收藏

数学苦手……一通推,无法可行……
于是只能想没有办法的办法:打表……

 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 < 0return;
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 }
posted @ 2011-09-18 20:40 sweetsc 阅读(774) | 评论 (1)编辑 收藏

题意:给一个序列,要求维护两个操作
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 }
posted @ 2011-09-10 20:19 sweetsc 阅读(1090) | 评论 (0)编辑 收藏

题意:给一个方格的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 == 0break;
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 }
posted @ 2011-09-10 17:46 sweetsc 阅读(948) | 评论 (0)编辑 收藏