久久视频免费,97人人精品,亚洲精品一区二区三区中文字幕

sweetsc — Thu, 26 Jan 2012 14:42:00 GMT

应刁哥多�q�前的约�E�，外加�l�合�~�译原理�p�d��q�蝲�Q�整理一下上一��文章，写一个简易的汇编教程……

��管谬误�Q�疏漏若�qԌ��但是本文的目的不在于培养学霸�Q�而在于让不会汇编的�h��单看看就能写��Z��基本能用的汇�~�程�?#8230;…

在程序设计中�Q�我们知道一��基本原理：语言��高�U�，一般来讲容易编写，形式��z�，可移植性强�Q�效率低……

反过来，语言��低�U�，��难�~�写�Q�代码越�Ҏ��是又臭又长还看不懂，��难�U�L��Q�但是效率会很高……

汇编��是比较低��的语�a�了，�׃��其不太好�U�L��Q�汇�~�版本又多种多样

因此�Q�本着�z�d��zȝ��Q�到时候不会就查手册的原则�Q�本文不会太着重强调语法，语法以intel语法��Z��……

Chapter1�Q�一些基本知�?/div>

首先�Q�CPU有若�q�寄存器�Q�在32位CPU中，形如eax�Q�ebx�Q�ecx�Q�edx……64位CPU则�ؓrax�Q�rbx……

虽然寄存器这个名字很NB�Q�其实它的本质上��是int�Q��ؓ了向下兼容的需要，一些老的�E�序�Q�也有可能能在新型的CPU上运行（详见DOS老游戏，有的能玩�Q�有的不能玩�Q?/div>

�?4位�D例：

64位寄存器rax�Q�低32位是eax�Q�eax�?6位是ax�Q�ax�?位叫ah�Q�低8位叫al……

CPU只能直接对寄存器�q�行�q�算……因�ؓ电�\�l�构��是那样�?#8230;…因此�Q�所有的操作�Q�都需要经�q�寄存器

譬如赋��|��A = 1�Q�实际上�?AX = 1; A = AX; 譬如 A = A + B�Q�应该是 AX = A; AX += B; A = AX; �q�样

我是比较不求甚解的，99%功能�Q�运��，判断�Q�指针）�{�，使用eax�Q�ebx�Q�ecx�Q�edx都能搞定……于是�׃��也就不说别的�?#8230;…

Chapter2�Q�汇�~�的基本语法�Q?/div>

汇编语言大概分�ؓ四个�D�，其中比较需要记住的��是代码�D�和数据�D?#8230;…

用类似高�U�语�a�的思�\来讲�Q�数据段用于定义一些全局变量�Q�代码段用于写程�?#8230;…

来看一个简单的 Hello World�Q�环境：yasm�Q?4位）

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

其中�Q�刚开始global main 表示�E�序入口�Q�由于这里直接调用了Linux的函数printf�Q�之后需要gcc�~�译�Q�所以叫做main�Q�如果只使用中断输出的话�Q�可以搞成_start

之后extern意义和C++�c�M��Q�表�C��个函数在别处�Q�叫�~�译器以��Z��有就�?#8230;…

section .data 表示数据�D�，后面是一些定义，以及初始�?/div>

注意�q�里定义的东西类型都像是指针一��P��ctrlout�Q�hw 实际上是地址……

初始化必��L��的干净一点，有一�ơ调了半天不对，��是因�ؓ一�?4位int�Q�前4位没有初始化�?……

之后 section .text 表示代码�D�，�q�里调用C语言函数�Q�网上说�Q?4位汇�~�中�Q�参��C��递方式有了修改，大概是有4~5个寄存器专门保存参数�Q�如果参数过多，再放入栈�Q�rax存放栈中的参��C��?#8230;…我们想printf("%s","Hello World")�Q�就要调用两个参敎ͼ�于是�Q�我们把�W�一个参敎ͼ�字符串ctrlout的指针mov�q�rdi�Q�hw mov�q�rsi�Q�rax赋��gؓ0 �Q�然后，调用……

�Q�实现时�Q�需要手册自行查阅一下本机怎么搞）

函数的返回值在rax�Q�于是return 0

然后 yasm -f elf64 XXX.asm

gcc -o XXX XXX.o

./XXX

一个崭新的hello world 出现�?#8230;…

Chapter3�Q�汇�~�的一些简单指令：

�׃��q�是速成教程�Q�选取一部分指��o……要记住，CPU只能直接对寄存器�q�行�q�算……

mov�Q�相当于赋��|�� mov eax�Q�b 相当于eax = b�Q?/div>

注意�Q�mov 后面的两个东西至��要有一个是寄存�?#8230;…

同时�Q�和高��语言一��P��不能搞什�?mov 10�Q�eax……

add�Q�add eax�Q�b 相当于eax+=b

sub�Q�基本同�?#8230;…

mul || imul�Q�前面是无符��L��乘，后面是有�W�号的乘�Q�默认被乘数在AX�Q�于是指令�Ş如：mul BX�Q�如果有溢出�Q�则高位溢出到DX�Q�记得备份DX的东�?#8230;…

div || idiv�Q�前面是无符��h��除，后面是有�W�号整除�Q�默认被除数是DX�Q�高16位）和AX�Q�低16位）�Q�因此，除法之前记得把DX清零�Q�否则数会不�?#8230;…

之后商在AX�Q�余数在DX

指��o形如�Q�div BX

push/pop�Q�每个程序都有栈�Q�或者是在程序中定义堆栈�D�，或者��用默认栈

push eax�Q�表�C�把eax放进栈里�Q�pop ebx�Q�表�C�取出栈��Ӟ��攑֜�ebx�?#8230;…

push和pop异常重要�Q�一个重要作用就是保护寄存器�Q�譬如DX中有内容�Q�但是现在要做乘法，没准会破坏DX�Q�见上）�Q�于是，先PUSH DX�Q�然后，乘法�Q�然后POP DX�Q�又好比你要调用一个函敎ͼ�但是寄存器里有有用的信息�Q�不保证�q�个函数不会破坏�Q�于是，把所有寄存器先push�q�去�Q�运行函敎ͼ�然后再pop出来�Q�这是常用技�?#8230;…

另外也可以用来给函数传参敎ͼ�传时倒序压入�Q�用旉��序取出，栈，先进后出�Q�你们懂�?#8230;…

Chapter4�Q�if以及循环

首先我们要记得，被Dijkstra老爷子骂的一文不值的goto……

jmp语法和C++里的goto基本一�?/div>

start�Q?/div>

XXX

jmp start

然后�Q�汇�~�没有if then�Q�但是有条�ggoto

有个语句叫做cmp

cmp X�Q�Y �Q�老原则，�q�两个得有一个寄存器……如果和常数比较，常数必须在后面）

传说中具体实现是减法……

�q�个的效果是可能改变若干标识位的�?#8230;…譬如�Q?标识�Q�进位标识，溢出标识……�{�等……

然后�Q�有若干指��o

jl XX�Q�l==less�Q?相当�?if (x

jg XX�Q�g==greater�Q?/div>

jle XX�Q�ne==less or equal�Q?/div>

jge XX�Q�ge==greter or equal�Q?/div>

jnle XX�Q�n==no->nle==g�Q?/div>

jnge XX�Q�n==no->nge==l�Q?/div>

有了if then�Q�各�U�运��，我们��p��做出�?amp;&,||的逻辑

有了if then�Q�我们也能做出��@�?#8230;…

很多的功能就有了……

Chapter5�Q�实�?/div>

看看

int main() {

int a,b,c;

input(a);

input(b);

if (a < b) {

c = a;

} else {

c = b;

}

print(c);

}

用汇�~�翻译出来啥��P��

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�Q�其�?/div>

�׃��现实生活中，我需要写汇编时候实在是��，因此也没啥经�?#8230;…��管借助手册�Q�可以对付着写一�Ҏ��~�代码，但是那是不科学的……�Ҏ��来讲�Q�汇�~�告诉我们的一些底层的东西更有价��|��可以在高�U�语�a�中有所体现�Q�譬如一些表辑ּ�的写法，可以考虑写的更科学一些，譬如 c = a / b, q = a % b�Q�记得写�?c = a / b; q = a - c * b�Q�譬如灵�z�M��用switch�Q�等�{?#8230;…

sweetsc 2012-01-26 22:42 发表评论

define 学习体会

sweetsc — Thu, 01 Dec 2011 17:59:00 GMT

最�q�，做OS大作业，�~�译大作业，和进行实验室工作�Q�强烈认识到了自己对C语言的了解不�?#8230;…
于是今天老图借了本书�Q�学习一�?#8230;…
来看一下我最头疼的define……
define的作用：
一是直接定义一个东�?#8230;…�c�M��标记
譬如�Q?br />

1 #ifndef test
2 #define test
3 /*
4 balabalabala.
5 */
6 #endif

刘JX老师在大一C�Q�＋课上教育我们�Q�写头文件一定要加上�q�么个东�?#8230;…��Z��么呢……
再提一下include的事�?#8230;… #include�Q�实际上是直接把XXXX整个文�gCOPY了进�?#8230;…
如果出现�q�样的情况：

1 #include <set>
2 #include

我们知道�Q�Cpp�?map 实际上是�?set 做的�Q�map的头文�g里肯定有一�?#include �Q�那么，相当于set�q�个文�g在这�D늨�序里面出��C��两次……
如果没有ifndef�q�套的话�Q�相当于��set中的代码重复贴了两次�Q�就�_�大事了……
代码�W�一�D�ifndef test 代表�Q�如果没有define test�Q�则执行下面的那�D�，�?nbsp;define test�Q�然后balabala�Q�最后endif�Q�下�ơ再看到�q�段代码的时候，ifndef test �Q�此时会发现test已经define�q�了�Q�直接endif�Q�中间balabala的代码不会重复两��?#8230;…

二是直接定义一�?#8230;…怎么说呢�Q�类似替换规则的东西……

譬如�Q�直接定义常量：
1 #define MAXN 10000
�q�个实际上就是直接在�E�序�~�译之前�Q�将里面的MAXN都替换成10000
预先定义一些常量，好处大家都懂�Q�避免程序内部太多的“magic number”�Q�增强可��L��，也便于修�?#8230;…�q�里相当于直接替换，貌似C的数�l�，定义的时候不能用int做下标，const int也不行，只能通过�q�个�Ҏ��Q�用立即�?#8230;…

譬如�Q�给一些东西改个名字：

  1 #include
  2 #define Q scanf
  3
  4 int main() {
  5     int a;
  6     Q("%d",&a);
  7     printf("%d\n",a);
  8     return 0;
  9 }

�q�里有一些玄机：
1�Q?��g��是因为没有�{义？所以不能胡�?#8230;…
譬如�Q?define USEMATH #include 是不能达到预期效果的……
2�Q�如果这一行太长，可以用\表示和下一行连��h��…… 貌似�q�个'\'也没转义�Q?#define BACKSLASH \ 也是不行�?#8230;…

譬如�Q�可以定义一些简单的函数�Q?br />#define max(a,b) ((a) > (b) ? (a) : (b))
某种意义上这比template NB...
�q�样�Q�int c �Q?max(a,b); ��p��动替换成 int c �Q?(a) > (b) ? (a) : (b)); �?br />此处有一个技巧：有的时候，�׃��需要用大括��h��实现�q�个"函数"�Q�但是，由define直接替换知道�Q�这个替换出来，相当于{/*balabala*/};�q�样�Q�语法是错的……
于是怎么办呢……�׃��可以�?do {/*balabala*/} while(0) �q�样的�Ş式，�l�开�q�个问题…… 在上�ơOS大作业上�׃��都见��C��……
此处�q�有两个玄机�Q�一是千万记得要加括�?#8230;…��Z��么呢……
譬如�Q?br />#define mul(a,b) a * b
看着挺好�Q�mul(1,2 + 3)��出事了…… 直接替换出来�Q�是 1 * 2 + 3�Q�就错了……
正确�Ҏ��是：#define mul(a,b) ((a) * (b))�Q�万无一�?#8230;…
另一个玄机是避免++,--之类的，譬如

#define sqr(a) ((a) * (a))

sqr(a++)�Q�如果sqr是真的函数的话，计算出没有问�?#8230;…但是define会忠实的�l�你替换�?(a++) * (a++))……怎么加的不重要，�l�果��׃��是你想的�?#8230;…

最后有两个用法�Q�一个是#�Q?会将你作�?#8220;函数”�?#8220;参数”传入的东西�{化�ؓ字符�Ԍ��一个是...�Q�作用一看便知：

1 #include
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 }

sweetsc 2011-12-02 01:59 发表评论

2011ACM��州�|�络预选赛 F HDU4068 三国杀

sweetsc — Fri, 07 Oct 2011 12:15:00 GMT

题意很简�?#8230;…双方�l�N个�h�Q�N<=6�Q�打三国杀1V1�Q�你知道�Ҏ��每个��克制你哪些�h�Q�我们认��Z��个�h�Ҏ��Q�他能克你则他胜利，否则你胜利；某�h的N个�h��d��p��?#8230;…你需要组�l�阵�Ҏ��照顺序对抗对�?#8230;…求有没有一个顺序，无论�Ҏ��序如何�Q�你都能�?#8230;…
N�Q�枚举自��q��序�Q�然后N�Q�枚丑֯�方的��序�Q�O�Q�N�Q�验证即�?#8230;…
注意字典序最��?#8230;…

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 }

sweetsc 2011-10-07 20:15 发表评论

2011ACM北京�|�络预选赛 F Machine scheduling (BUPT 216)

sweetsc — Sun, 18 Sep 2011 14:56:00 GMT

�q�题比赛时候过得很�U�结……最后还是学长过�?#8230;…比赛时候脑子可能不够清楚，一直WA……
首先�Q�这个题要分成两个部分解冻I��
�W�一部分�Q�从n个东襉K��面取出r个，每个间距臛_��?k �Q?～K不行�Q?～K �Q?1行）
�W�二部分�Q�将�q�r个东西分成至多m�l�，可以有空�l?br /> �W�二部分貌似好久之前搞OI的时候干�q?#8230;…贴过来：

N球放在M个盒子里�Q�求共有多少�U�放�?br />

但是�?个不同的条�g �Q�N个球是否相同�Q�M个盒子是否相同，是否允许有盒子空着

球和�?/span>	盒和�?span>	�I�盒	情况�?span>
有区�?span>	有区�?span>	有空�?span>	mⁿ
有区�?span>	有区�?span>	无空�?span>	M�Q?span>s�Q?span>n,m�Q?span>
有区�?span>	无区�?span>	有空�?span>	S(n,1)+s(n,2)+…+s(n,m),n>=m S(n,1)+s(n,2)+…+s(n,n),n<=m
有区�?span>	无区�?span>	无空�?span>	S(n,m)
无区�?span>	有区�?span>	有空�?span>	C(n+m-1,n)
无区�?span>	有区�?span>	无空�?span>	C(n-1,m-1)
无区�?span>	无区�?span>	有空�?span>	F(m,n)
无区�?span>	无区�?span>	无空�?span>	F(m,n-m)

然后�Q�其中的F(m,n)貌似是当时写�q�的一个DP�Q�S(M,N)是第二类stirling�?#8230;…
递推公式�Q?br />

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 }

�W�一部分�Q�可以看作这么一个生成函数的相关问题�Q�由于每个东西之间都隔了>=K�Q?的一�D�距��，因此一个可行解可以看作�Q�长度�ؓK�Q�K + 1�Q�K + 2的棍子r �Q?1个（我们认�ؓ每个��子的头是我们取的点�Q�，拼接成长度�ؓLen的一个大�D�，之后再堵上一个，��是一个Len �Q�１的可行解……
而r - 1�Ҏ��子，拼成长度为Len 的可行解数目�Q�就�?X^K + X^(K + 1) + X^(K + 2) + .....) ^ (r - 1)�Q�这个多��式�Q�展开之后�Q�X^Len��前面的�p�L��……
不过……�׃��数据范围�Q�直接搞是不成的……
于是提取�Q�变形：X^(K * (r - 1)) * (1 + X + X^2 + X ^3 +....)^(r - 1)
然后再变形：X^(K * (r - 1)) * (1/(1 - x))^(r - 1)……
然后参照Matrix67大神的日志，展开后面那项�Q?br />

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+...

我们知道�Q�要求长度�ؓlen的可行数目，也就是要X^Len��前面的�p�L��Q�然后，�׃��前面提取出来了一个K * (r - 1)�Q�也��是��d��面找len - K * (r - 1) ��的�p�L��……
也就是说�Q��opow = len - K * (r - 1)�Q�答案就是C(r - 1 + pow - 1, pow)……
不过�q�还没完�Q�因为咱们要拼成的长度是len�Q�而�ȝ��长度是N�Q�需要乘上这个长度len的开头位�|�的可能�?#8230;…
另外�q�需要特�D�处理：�׃��在处理的时候，是先用r - 1个拼接成长度为Len的一个大�D�，再堵上最后一�?#8230;…当r == 1需要特�?#8230;…
代码�Q?br />

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 }

sweetsc 2011-09-18 22:56 发表评论

2011ACM北京�|�络预选赛G Panda (BUPT 217)

sweetsc — Sun, 18 Sep 2011 12:44:00 GMT

思�\是维护每个字母开��_��长度�?的串是不是wbw……
�q�样相当于将长度为N的字�W�串变成长度为N�Q?的序列，然后一�p�d��修改��是��序列中1�?�Q?�?�Q�查询就是求一�D늚��?br />BIT�Q�大安��懂的……

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 }

sweetsc 2011-09-18 20:44 发表评论

2011ACM北京�|�络预选赛D题： FXTZ II (BUPT 235)

sweetsc — Sun, 18 Sep 2011 12:40:00 GMT

数学苦手……一通推�Q�无法可�?#8230;…
于是只能��x��有办法的办法�Q�打�?#8230;…

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 }

输出�Q?br />1 2
3 8
15 48
105 384
945 3840
10395 46080
135135 645120
2027025 10321920
34459425 185794560
654729075 3715891200
然后大家都懂�?#8230;…

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 }

sweetsc 2011-09-18 20:40 发表评论

1006 Can you answer these queries The 36th ACM/ICPC Asia Regional Shanghai Site —�?Online Contest

sweetsc — Sat, 10 Sep 2011 12:19:00 GMT

题意�Q�给一个序列，要求�l�护两个操作
1�Q�将区间[L,R]里面的数开方下取整
2�Q�求区间[L,R]里面元素的和
�W�一反应是线�D�|��Q�但是这里面有个矛盾�Q�开方不好处理，如果��序列表�C�成�Ҏ��Q�求和又不好处理……
�q�运的是�Q�开�Ҏ��作收敛的很快�Q�从long long �?1�Q�只�?�ơ，于是每次对区间操作，我们在线�D�|��基础上进行改动：�U�段树最后将待查询区间会分成Log�Q�N�Q�个区间�Q�绝对不能将操作区间分成��段……但是现在要这么做�Q�因为每个点最多被覆盖8�ơ之后就�?�?#8230;…于是�Ҏ��个节点维护一个isone标记�Q�标记这一�D�|��不是1�Q�每�ơ修攚w��递归下去直接修改�?的点�Q��ƈ且维护isone标记……�q�样均摊下来�Q�每个点最多被�?��?#8230;…

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 }

sweetsc 2011-09-10 20:19 发表评论

1002 Bombing The 36th ACM/ICPC Asia Regional Shanghai Site —�?Online Contest

sweetsc — Sat, 10 Sep 2011 09:46:00 GMT

题意�Q�给一个方格的1E9*1E9的地图，以及若干炸弹�Q�每个炸弹的功能是将某行�Q�某列的所有东西消灭，求若�q�炸弹依�ơ下去，每次消灭了多��东�?#8230;…
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 }

sweetsc 2011-09-10 17:46 发表评论

sweetsc — Mon, 23 May 2011 15:55:00 GMT

  1 /*
  2     Author: Sweetsc 寂寞之余所�?br />  3
  4     讑֮��?br />  5         �y�的累：http://baike.baidu.com/view/2213196.htm
  6         比利�Q?/span>http://baike.baidu.com/view/2280157.htm
  7         Yoooooooooo�Q?/span>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         "看电�?/span>",
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         "�y�的�?/span>",
31         "天然�?/span>",
32         "普�?/span>",
33         "软妹�?/span>",
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 "闭嘴�Q�基佬！";
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("不好意思，我那天有�?img src="http://www.aygfsteel.com/Images/dot.gif" alt="" />.");
70             }
71         } else {
72             if (type == 0) {
73                 System.out.println("偶尔和你�?/span>" + 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("�Ҏ��默了�怹��Q��{�w�离开");
84             System.out.println("然后��没有然后了……");
85             System.err.println("�pȝ��提示�Q�好感度不��Q?/span>");
86             friendship = 0x80000000;
87             return;
88         } else {
89             switch (type) {
90                 case 0 :
91                     System.out.println("仑家可不是因为喜�Ƣ才�{�应的哦�Q?/span>");
92                     break;
93                 case 4 :
94                     System.out.println("Yoooooooooooooooooo!!!!");
95                     System.out.println("你从此，跟随比利�Q�走向了�q�求人生哲学的道�?/span>");
96                     System.err.println("�pȝ��提示�Q�你求交往的对象是伪娘�Q?/span>");
97                     break;
98                 case 6 :
99                     System.out.println("�Ҏ��怀�ƣ喜的答应了");
100                     System.out.println("�q�了几天�Q�她介绍了个男友�l�你");
101                     System.out.println("Yoooooooooooooooooo!!!!");
102                     System.out.println("你从此，跟随比利�Q�走向了�q�求人生哲学的道�?/span>");
103                     System.err.println("�pȝ��提示�Q�你求交往的对象是腐女�Q?/span>");
104                     break;
105                 case 7 :
106                     System.out.println("奚w��无表情的��_��我喜�Ƣ的是女生！");
107                     System.out.println("然后��没有然后了……");
108                     friendship = 0x80000000;
109                     break;
110                 default :
111                     System.out.println("�Ҏ��脔R��红,沉默了许久，之后��ӆ的说道：好吧");
112                     System.out.println("从此�Q�你�?/span>" + character[type] + name + "�q�上了幸��的生活");
113                     System.err.println("�l�于Goodend了，可喜可贺可喜可贺");
114             }
115         }
116     }
117
118 }

sweetsc 2011-05-23 23:55 发表评论

sweetsc — Wed, 06 Apr 2011 04:36:00 GMT

原文�Q? Java�U�程�Q�新特征-障碍器，�q�是该作者的原创作品�Q�允许�{载，转蝲时请务必以超链接形式标明文章原始出处、作者信息和本声明。否则他��追�I�法律责�?#8230;…

Hmm……好怕怕，转个日志都会被追�I�法律责�?#8230;…

不过要感谢原文的兰州�Q�在兰州的文章帮助下�Q�今天突然发��C��灉|��Q�改造了攚w��兰州的代码……
在ACM中的作用�Q�我觉得可以�q�样�Q?br /> 1�Q�对于单文�g多case的题�Q�开多线�E�，每个�U�程跑一个case�Q�之后再调用收尾的�Q务输�?br /> 2�Q�对于单case且可以�ƈ行的情况�Q�开若干�U�程处理之后�Q�调用收��և��C��最后处理、输�?br />
以下是一个简单的求和代码�Q�实际效果，在我的双核CPU上用时大概减��了一�?br />

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 }

sweetsc 2011-04-06 12:36 发表评论

久久视频免费,97人人精品,亚洲精品一区二区三区中文字幕

define 学习体会

2011ACM���州�|�络预选赛 F HDU4068 三国杀

2011ACM北京�|�络预选赛 F Machine scheduling (BUPT 216)

2011ACM北京�|�络预选赛G Panda (BUPT 217)

2011ACM北京�|�络预选赛D题： FXTZ II (BUPT 235)

1006 Can you answer these queries The 36th ACM/ICPC Asia Regional Shanghai Site —�?Online Contest

1002 Bombing The 36th ACM/ICPC Asia Regional Shanghai Site —�?Online Contest

2011ACM��州�|�络预选赛 F HDU4068 三国杀