#
摘要: 发现对汇编还是非常的生疏，可能平时程序写少了吧，尤其是对那些寄存器可以间接寻址记的不牢，BIOS调用什么基本是现学现卖。原来这个BIOS调用比DOS调用还要底层，连输出字符串的功能都没有，输入字符串要要用键盘中断，显示汉字要用字模，所谓字模就是一个点阵，用整数表示，用位运算去判断是否在此处输出点，很傻×的方法。为了能...
阅读全文
##Update 2010-4-16
这里稍微证明一下:
给定方程
x = c1 (mod b1) ……………………(1)
x = c2(mod b2) ………………………(2)
(b1,b2)可以不为1
于是通过取mod 定义，我们得到
x = k1 * b1 + c1………………(3)
(3) 带入(2)
k1 * b1 + c1 = c2 (mod b2)…………(4)
化简
k1 * b1 = c2 - c1 (mod b2)…………(5)
于是可以解得到
令G = gcd(b1,b2),C = c2 - c1 (mod b2)
那么由(5)得到
k1 * b1 = W * b2 + C
---->>>>>
k1 * b1 / G = W * b2 / G + C / G
令C' = C/G
k1 * b1 / G = W * b2 / G + C '
k1 * b1 / G = C' (mod b2 / G)
--->
k1 = K (mod b2/G)………………(6)
那么有
k1 = k' * b2/G + K………………(7)
(7)带入(3)
x = k' * b2 * b1/G + K * b1 + c1………………(8)
x = K*b1 + c1 (mod b1 * b2/G)
通过合并方程的方法成功AC下面此题
题目地址
#include<iostream>
#include<cmath>
using namespace std;
//x = c1 ( mod b1)
//x = c2 ( mod b2)
//若可以可并，则返回合并结果，否则返回-1
可以处理gcd(b1,b2)!=1的情况
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int ext_gcd(int a,int b,int& x,int& y){
int t,ret;
if (!b){
x=1,y=0;
return a;
}
ret=ext_gcd(b,a%b,x,y);
t=x,x=y,y=t-a/b*y;
return ret;
}
//求a对n的乘法逆元，若不存在返回-1
int Invmod(int a,int n){
int x,y;
if (ext_gcd(a,n,x,y)!=1)return -1;
return (x%n+n)%n;
}
int mergef(int b1,int c1,int b2,int c2,int &b,int &c)
{
int tb1=b1,tb2=b2;
c=((c2-c1)%b2+b2)%b2;
int G=gcd(b1,b2);
if(c%G)return 0;
c/=G;
b1/=G;
b2/=G;
c*=Invmod(b1,b2);
c%=b2;
c*=tb1;
c+=c1;
b=tb1*tb2/G;
c%=b;
return 1;
}
int main()
{
int b1,b2,c1,c2,b,c;
while(cin>>b1>>c1>>b2>>c2)
{
if(mergef(b1,c1,b2,c2,b,c))
cout<<"X = "<<c<<' '<<"(mod "<<b<<')'<<endl;
}
return 0;
}扩充了算法导论中中国剩余定理部分的内容，使得它可以处理更一般的情况了，这个模板具有通用性。
转自：
http://hi.baidu.com/aekdycoin/blog/item/71d7a842b93f611b73f05da4.html顺便提一下，除了整理模板之外，要开始网络流部分的强化训练了，强化构图能力。
摘要: 所谓0->n-1路径上一定要经过的割边，就是0->n-1任意一条路径上的割边，因为割边是必经之路。其实这题跟ZOJ 2588是同一个题，稍微变化就可以得到答案了，不过这题我当时的模板貌似写挫了，对边进行判重的时候进行了暴力，其实可以用set存一下，那么查找的复杂度可以降到log(n). 具体求割边的方法可以看这个：http://www.cp...
阅读全文
//数学建模
//2010年8月21日21:55:29
#include<iostream>
#include<algorithm>
#include<vector>
#include<sstream>
#include<string>
using namespace std;
int const maxn=10000;
char in[100000];
vector<string>mm[maxn];
int cnt=0;
bool isdigt(char a)
{
if(a>='0'&&a<='9')
return true;
else
return false;
}
void predo()
{
int len=strlen(in);
for(int i=0;i<len;i++)
{
if(!isdigt(in[i]))
in[i]=' ';
}
}
string ans;
void dfs(int k,string str)
{
if(k==cnt)
{
cout<<str<<endl;
return;
}
int n=mm[k].size();
for(int i=0;i<n;i++)
{
if(k!=0)
//cout<<"-"<<mm[k][i];
{
str+="-";
str+=mm[k][i];
}
else
//cout<<mm[k][i];
str+=mm[k][i];
dfs(k+1,str);
if(k!=0)
//cout<<"-"<<mm[k][i];
{
str=str.substr(0,str.length()-mm[k][i].length()-1);
}
else
//cout<<mm[k][i];
str=str.substr(0,str.length()-mm[k][i].length());
}
}
int main()
{
freopen("IN.txt","r",stdin);
freopen("OUT.txt","w",stdout);
cnt=0;
ans="";
while(cin.getline(in,100000))
{
predo();
//debug
//printf("%s\n",in);
//system("pause");
//
istringstream t(in);
string tem;
while(t>>tem)
{
mm[cnt].push_back(tem);
}
cnt++;
}
//debug
/**//*
printf("cnt = %d\n",cnt);
for(int i=0;i<cnt;i++)
{
for(int j=0;j<mm[i].size();j++)
{
cout<<mm[i][j]<<' ';
}
cout<<endl;
}
system("pause");
*/
dfs(0,ans);
return 0;
}
第一组
0567， 0042， 0025
1487
0303， 0302
0566
0436， 0438， 0437， 0435
0392， 0394， 0393， 0391
0386， 0388， 0387， 0385
3068， 0617， 0619， 0618， 0616
1279
2057， 0721， 0722， 0720
0070， 2361， 3721
0609， 0608
2633， 0399， 0401， 0400
3321， 2535， 2464
3329， 2534
3506， 0167， 0168
0237， 0239， 0238， 0236， 0540
0668
0180， 0181
2079， 2933， 1919， 1921， 1920
0465， 0467， 0466， 0464
3457
第二组
0537， 3580
0526， 0528， 0527， 0525
3045， 0605， 0607
0609， 0608
0087， 0088， 0086
0855， 0856， 0854， 0857
0631， 0632， 0630
3874， 1426， 1427
0211， 0539， 0541， 0540
0978， 0497， 0498
0668
1894， 1896， 1895
1104， 0576， 0578， 0577
3010， 0583， 0582
3676， 0427， 0061， 0060
1961， 2817， 0455， 0456
3262， 0622
1956， 0289， 0291
如果说《青花瓷》是江南古巷中的一位美人，那《蜀绣》便是巫山奇峡间的一卷流云。
一、词
虽然不太关注郭敬明，不可否认的是，这首词作得是不错的。尤有几句点睛之笔，让我喜爱不已。
最喜爱的一句首推“羽毛扇遥指千军阵 锦缎裁几寸”。这一句可说已道尽整首《蜀绣》的精髓所在。和人聊天时曾说，如果这首歌只留一句词，那留这句便可。“羽毛扇”三字道出蜀地，“锦缎”则是绣布，以“遥指千军阵”呼应“裁几寸”，似乎看到绣娘以柔荑素腕绣出万马奔腾，又似乎暗喻蜀绣丝线细密，用针如用兵。
而“绕指柔破锦千万针 杜鹃啼血声 芙蓉花蜀国尽缤纷 转眼尘归尘”两句也甚得我心。
“绕指柔破锦千万针 杜鹃啼血声” 刺绣原是无声的，但这句写来，隐隐有“听雪落”的感觉。一针针破锦似有声，针针都是漏夜无眠子规啼血声。整首词说的是绣娘等征人的故事，而这句既有刺绣之劳，亦有等人之苦，可谓一语双关。
“芙蓉花蜀国尽缤纷 转眼尘归尘” 有种道尽人间是沧桑的味道，配合李宇春柔和的嗓音唱出，尤其有一种淡淡愁绪，但又不是绝望，只是举首凝望，浅吟轻唱。让我想到以前和人戏作的一副对联：“沧桑世间应无恙 聚散浮云不问情”。
絮叨得有些支离破碎。下来不得不提的是整首词的韵脚。
整首词主要以“ㄣ（en）”“ㄥ（eng）”为韵脚（纷、针、村、分、春等韵脚是en，灯、疼、声、等、成等韵脚是eng），个人感觉这个韵脚特别适合李宇春这种中音且清糯的嗓音。咬在齿间，在口中鼻间绕个圈，再轻轻吐出，别有一种挠人心底的韵味。这种发音，唯有此等中音才能唱出最别致的滋味，若是高音，则高亢有余，以这种韵脚收尾，怕是发散了出去收不回来了；或是声音再厚重点，怕是鼻音有余，余韵不足。唯有李宇春这等清糯淡雅的中音，才能把这种韵脚诠释得恰到好处，有点小性感的滋味十足。
二、曲
这支曲很有高唐流云感，听在耳间，似见云卷云舒流于巫山，又似霓裳羽衣翻转旋舞，仿佛一副华美绣卷缓缓舒展于眼前。
作为一支中国风的曲，民乐元素是不可或缺的。
我耳拙，听不出太多，只在乐间听出了扬琴、二胡和笛子声，也不知听得对不对。（扬琴是在朋友的帮助下确认的，细辨了一番是琵琶还是扬琴 囧）
在开始时，似不经意地点缀一些清脆的扬琴声，清越而灵动；随着曲子展开，二胡这种很抒情乐器插入，曲中多出现在绣娘思征人处，柔肠千转；到“君可见刺绣又一针 有人为你疼”始，笛声也开始出现，华卷渐渐展开，流云变幻万千。
用李宇春淡雅干净的嗓音来诠释这支有些华丽的曲子，有意料不到的好效果，一种繁花开尽显霜华的舒畅感。历尽一季繁华后的霜枝，别有一番肆意舒展的感动。她淡吟唱的华曲，简繁结合得极致完美。中国画讲究的是写意，中华一脉相随的文化讲究的也是写意，随意泼墨点缀的梅枝可以绽出最生动的花瓣，轻松流畅的干净嗓音可以歌出最生动的画卷。
三、唱
整支曲唱下来，如水银泻地。
那个小韵脚形成的小性感不再赘述，中国画般的写意流畅也不重复了。特别想说的是她对一些小细节的处理。
“君可见刺绣又一针 有人为你疼 君可见牡丹开一生 有人为你等
……
君可见刺绣又一针 有人为你疼 君可见夏雨秋风有人 为你等”
此二句，若是一般人处理，怕会有一种“啊啊啊，俺等嫩那么久，嫩咋滴还不回来”的感觉。但李宇春处理下来，却是一种冷眼观世间、心痛却无奈的感觉，似手扶锦缎，观古人之悲，娓娓向今人道来。用一个朋友的话说就是：她的歌声里，有一种“悲天悯人”。
王国维说诗词有有我之境，有无我之境。这首词无疑是“有我”的，但这两句李宇春隐隐唱出一丝“无我”的意味——皆非我所愿，世事本如是。
“浓情蜜意此话当真”一句，在词来说，于我而言是整支词中较弱的部分，但却被她唱成了最有韵味的一句。“浓情蜜意”嚼在口中，听来淡淡的，“此话”后却是一顿，之后慢慢吟出比别句多几份沉凝和不确定的“当真”，突然让人心痛起来，让人突然看到绣娘的悲哀——山盟尚在，良人何在？细密的悲伤悄悄漾起，替古人悲伤起来。
起首的“芙蓉城三月雨纷纷 四月绣花针 羽毛扇遥指千军阵 锦缎裁几寸”及曲中的“绕指柔破锦千万针 杜鹃啼血声 芙蓉花蜀国尽缤纷 转眼尘归尘”两句，曲几至无声，所以几乎可以说是清唱。李宇春的声音本就很适合清唱，她的歌声里有一种磁糯的黏性，有曲声时易被盖住，清唱时——尤其是抒情慢歌，这种黏性便破阵而出，可以把人深深地吸进去。
“江河向海奔，万物为谁春”同样是一种超脱大度的感觉，似乎小心翼翼地吐出的十个字，有一种为伤心人吟怀的体贴。
李宇春曾说过，“中国风”久已有之，其实《中华民谣》之类也是中国风的——那种风格，类似民谣戏曲。
查百科，对“中国风”有严格的定义。但也许我听歌不多，一直觉得听到的“中国风”不是江南般婉约，就是战场上缠绵。
这一支，却是中国画般，舒展开来，如云蔚山间，没有刻意的缠绵和故作的沉吟，不是落寞的冷月或壮志的战士，她只是淡淡地、缓缓地，为你展开图画—— 一副历经沧桑的绣品，绣的也许是盛唐牡丹，也许是敦煌飞天，也许是明月小桥，也或许是万马奔腾，各种图画变幻着扑面而来，聚成“蜀绣”两字。
附《蜀绣》歌词
作词：郭敬明
芙蓉城/三月雨纷纷/四月绣花针
羽毛扇遥指千军阵/锦缎裁几寸
看铁马踏冰河/丝线缝韶华/红尘千帐灯
山水一程/风雪再一程
红烛枕/五月花叶深/六月杏花村
红酥手/青丝万千根/姻缘多一分
等残阳照孤影/牡丹染铜樽/满城牧笛声
伊人倚门/望君踏归程
君可见/刺绣每一针/有人为你疼
君可见/牡丹开一生/有人为你等
江河入海奔/万物为谁春
明月照不尽离别人
君可见/刺绣又一针/有人为你疼
君可见/夏雨秋风/有人为你等
翠竹泣墨痕/锦书画不成
情针意线/绣不尽鸳鸯枕
此生笑傲/风月瘦如刀/催人老
来世与君暮暮又朝朝/多逍遥
——摘自豆瓣
7月13号 FZU（周二，福大OJ)
7月15号 BUPT（周四）
7月20号 WHU（周二）
7月22号 UESTC（周四）
7月27号 BJTU（周二）
7月29号 NUDT（周四）
8月3号 HIT（周二，哈工大OJ）
8月5号 ECNU（周四，HDOJ）
8月7号 HDU（周六，联合训练 暨 HDOJ Monthly Contest，HDOJ）
8月10号 HNU（周二）
8月12号 TJU （周四）
8月17号 BUPT（周二）
8月19号 WHU（周四）
8月24号 UESTC（周二）
8月26号 BJTU（周四）
8月31号 NUDT（周二）
9月2号 BIT（周四，HDOJ）
9月7号 ZSTU（周二）
9月9号 HRBEU（周四）
100除以7的余数是2，意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义：假如被除数是a，除数是b（假设它们均为正整数），那么我们总能够找到一个小于b的自然数r和一个整数m，使得a=bm+r。这个r就是a除以b的余数，m被称作商。我们经常用mod来表示取余，a除以b余r就写成a mod b = r。
如果两个数a和b之差能被m整除，那么我们就说a和b对模数m同余（关于m同余）。比如，100-60除以8正好除尽，我们就说100和60对于模数8同余。它的另一层含义就是说，100和60除以8的余数相同。a和b对m同余，我们记作a≡b(mod m)。比如，刚才的例子可以写成100≡60(mod 8)。你会发现这种记号到处都在用，比如和数论相关的书中就经常把a mod 3 = 1写作a≡1(mod 3)。
之所以把同余当作一种运算，是因为同余满足运算的诸多性质。比如，同余满足等价关系。具体地说，它满足自反性（一个数永远和自己同余）、对称性（a和b同余，b和a也就同余）和传递性（a和b同余，b和c同余可以推出a和c同余）。这三个性质都是显然的。
同余运算里还有稍微复杂一些的性质。比如，同余运算和整数加减法一样满足“等量加等量，其和不变”。小学我们就知道，等式两边可以同时加上一个相等的数。例如，a=b可以推出a+100=b+100。这样的性质在同余运算中也有：对于同一个模数m，如果a和b同余，x和y同余，那么a+x和b+y也同余。在我看来，这个结论几乎是显然的。当然，我们也可以严格证明这个定理。这个定理对减法同样有效。
性质：如果a≡b(mod m)，x≡y(mod m)，则a+x≡b+y(mod m)。 证明：条件告诉我们，可以找到p和q使得a-mp = b-mq，也存在r和s使得x-mr = y-ms。于是a-mp + x-mr = b-mq + y-ms，即a+x-m(p+r) = b+y-m(q+s)，这就告诉我们a+x和b+y除以m的余数相同。
容易想到，两个同余式对应相乘，同余式两边仍然相等：
如果a≡b(mod m)，x≡y(mod m)，则ax≡by(mod m)。 证明：条件告诉我们，a-mp = b-mq，x-mr = y-ms。于是(a-mp)(x-mr) = (b-mq)(y-ms)，等式两边分别展开后必然是ax-m(...) = by-m(...)的形式，这就说明ax≡by(mod m)。
现在你知道为什么
有的题要叫你“输出答案mod xxxxx的结果”了吧，那是为了避免高精度运算，因为这里的结论告诉我们在运算过程中边算边mod和算完后再mod的结果一样。假如a是一个很大的数，令b=a mod m，那么(a * 100) mod m和(b * 100) mod m的结果是完全一样的，这相当于是在a≡b (mod m)的两边同时乘以100。这些结论其实都很显然，因为同余运算只关心余数（不关心“整的部分”），完全可以每一次运算后都只保留余数。因此，整个运算过程中参与运算的数都不超过m，避免了高精度的出现。
在证明
Fermat小定理时，我们用到了这样一个定理：
如果ac≡bc(mod m)，且c和m互质，则a≡b(mod m) （就是说同余式两边可以同时除以一个和模数互质的数）。
证明：条件告诉我们，ac-mp = bc-mq，移项可得ac-bc = mp-mq，也就是说(a-b)c = m(p-q)。这表明，(a-b)c里需要含有因子m，但c和m互质，因此只有可能是a-b被m整除，也即a≡b(mod m
http://www.matrix67.com/blog/archives/236保存一下，以备今后学习:-)
记得当时做高斯消元那个题的时候，嘉龙的代码死活过不了，后来发现是在航电long long 要用%I64d ,看来我没吸取这个教训啊，今天做昨天第七场的题目的时候，又犯了同样的错误，浪费了一个下午，从Dij+heap到SPFA,能换的最短路算法都用了，就是过不了航电，还以为加了什么数据，原来是judge的问题，BS!
线段树 经典的题目，以前曾经做过一遍，现在为了练手在做一次，刚学了splay树，反倒是加深了对线段树的理解，就是那个延迟标记（也就是懒操作）。虽然线段树已经写过多次，但是这题仍然不能1A,Query函数中有个地方应该是mid=(ST[i].l+ST[i].r)>>1写成了(l+r)>>1,导致wa了几次，今后要注意啊。
#include<iostream>
using namespace std;
int const maxn=100010;
int n,t,q;
struct node
{
int l,r;
int col;//用位来存储颜色
int cover;//延迟标记
}ST[maxn*4];
void Build(int l,int r,int i)
{
ST[i].l=l;
ST[i].r=r;
ST[i].col=0;
ST[i].cover=0;
if(l==r)
return;
int mid=(l+r)>>1;
Build(l,mid,i*2);
Build(mid+1,r,i*2+1);
}
void push_down(int i)
{
ST[i*2].col=ST[i].col;
ST[i*2+1].col=ST[i].col;
ST[i].cover=0;
ST[i*2].cover=1;
ST[i*2+1].cover=1;
}
void insert(int l,int r,int col,int i)
{
if(ST[i].l==l&&ST[i].r==r)
{
ST[i].cover=1;
ST[i].col=(1<<(col-1));
return ;
}
if(ST[i].cover)//如果当前区间有效，下沿延迟标记
push_down(i);
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)
insert(l,r,col,i*2);
else if(l>mid)
insert(l,r,col,i*2+1);
else
{
insert(l,mid,col,i*2);
insert(mid+1,r,col,i*2+1);
}
ST[i].col=ST[i*2].col|ST[i*2+1].col;
}
int fun(int num)//检查最后返回的整数中有多少颜色
{
int ans=0;
int i;
for(i=0;i<t;i++)
if(num&(1<<i))
ans++;
return ans;
}
int Que(int l,int r,int i)
{
if( (ST[i].l==l&&ST[i].r==r)||ST[i].cover==1)
return ST[i].col;
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)
return Que(l,r,i*2);
else if(l>mid)
return Que(l,r,i*2+1);
else
return Que(l,mid,i*2)|Que(mid+1,r,i*2+1);
}
int main()
{
while(scanf("%d%d%d",&n,&t,&q)!=EOF)
{
Build(1,n,1);
ST[1].cover=1;
ST[1].col=1;
char op[20];
int a,b,c;
for(int i=1;i<=q;i++)
{
scanf("%s",op);
if(op[0]=='C')
{
scanf("%d%d%d",&a,&b,&c);
if(a>b)
swap(a,b);
insert(a,b,c,1);
}
else
{
scanf("%d%d",&a,&b);
if(a>b)
swap(a,b);
printf("%d\n",fun(Que(a,b,1)));
}
}
}
return 0;
}