题目大意是有很多字符串s[],每个字符串对应一个分值。然后由若干询问，每个询问会给出一个前缀，让你把满足前缀的字符串都找出来，按照分值从大到小顺序输出，如果有很多的话，输出前10个

10 是这题的关键，于是我们可以把字符串按字典顺序sort一下，搞一棵线段树，每条线段保存该段中从大到小的十个元素。然后就询问线段树该前缀对应的区间好了。

编程上利用下STL的两个函数 merge() 归并两个有序的数组，然后copy()把一个数组的一部分复制到另一个一个数组。写下来就会很容易

//URAL_1542_Autocompletion
//By xt3000 Used G++

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

struct WORD{
 string s;
 int v;
 friend bool operator < (const WORD& l,const WORD& r){
  return l.s<r.s; 
 };
};

WORD a[100010];

bool cmp(const int &l,const int &r){
 if (a[l].v==a[r].v)
  return l<r;
 else
  return a[l].v>a[r].v;
};

struct STree{
 int v[10];
};

int n,m;
STree s[400001];
int as[400001][10],as1[400001][10];
int temp[20],temp1[20];

void build(int p,int l,int r){
 if (r-l<=9) {
  for (int i=0;i<=r-l;i++) s[p].v[i]=l+i;
  sort(s[p].v,s[p].v+10,cmp);
 }else{
  int mid=(l+r)/2;
  build(p*2,l,mid);build(p*2+1,mid+1,r);
  merge(s[p*2].v,s[p*2].v+10,s[p*2+1].v,s[p*2+1].v+10,temp,cmp);
  copy(temp,temp+10,s[p].v);
 };
};

void ask(int p,int l,int r,int st,int en,int ans[]){
 if (l==st && r==en) {
  merge(ans,ans+10,s[p].v,s[p].v+10,temp,cmp);
  copy(temp,temp+10,ans);
 }else if (en-st<=9) {
  for (int i=0;i<=en-st;i++) temp1[i]=st+i;
  sort(temp1,temp1+en-st+1,cmp);
  merge(ans,ans+10,temp1,temp1+en-st+1,temp,cmp);
  copy(temp,temp+10,ans);
 }else{
  int mid=(l+r)/2;
  if (en<=mid) ask(p*2,l,mid,st,en,ans);
  else if (st>mid) ask(p*2+1,mid+1,r,st,en,ans);
  else {
   fill(as[p],as[p]+10,0);fill(as1[p],as1[p]+10,0);
   ask(p*2,l,mid,st,mid,as[p]);
   ask(p*2+1,mid+1,r,mid+1,en,as1[p]);
   merge(as[p],as[p]+10,as1[p],as1[p]+10,temp1,cmp);
   merge(temp1,temp1+10,ans,ans+10,temp,cmp);
   copy(temp,temp+10,ans);
  };
 };
};

int main(){
 int i,j,k;
 int ans[10];
 string s;
 WORD w;
 cin>>n;
 for (i=1;i<=n;i++) {
  cin>>a[i].s>>a[i].v;
 };
 sort(a+1,a+1+n);
 build(1,1,n);
 cin>>m;
 for (i=1;i<=m;i++) {
  if (i>1) cout<<endl;
  cin>>s;w.s=s;
  j=lower_bound(a+1,a+1+n,w)-a;
  if (j>n || a[j].s.length()<s.length() || a[j].s.substr(0,s.length())!=s) continue;
  w.s+=char(255);
  k=lower_bound(a+1,a+1+n,w)-a;k–;
  fill(ans,ans+10,0);
  ask(1,1,n,j,k,ans);
  j=0;
  while (j<10 && ans[j]>0) {
   cout<<a[ans[j]].s<<endl;
   j++;
  };
 };
 
 return 0;
};

嘛，这题做上去觉得很难，后来被septem神搭救了。

这里附上自己随便翻译的和这题有关的一篇论文

原文：http://www.cs.princeton.edu/courses/archive/spr03/cs226/assignments/burrows.html

 

COS 226 Programming Assignment
Burrows-Wheeler Data Compression Algorithm
Implement the Burrows-Wheeler data compression algorithm. This revolutionary algorithm outcompresses gzip and PKZIP, is relatively easy to implement, and is not protected by any patents. It forms the basis of the Unix compression utililty bzip2. The Burrows-Wheeler compression algorithm consists of three different algorithmic components, which are applied in succession:

实现 Burrows-Wheeler data compression algorithm 。 这个革命性的算法用来解码gzip 和 PKZIP，它非常容易实现，  而且他不受任何专利保护。它来源于基础的Unix压缩技术 bzip2模块。 Burrows-Wheeler data compression algorithm由三个不同的算法组成：

Burrows-Wheeler transform. Given a normal English text file, transform it into a text file in which series of the same letter occur near each other many times.

Burrows-Wheeler 转换。 给出一个一般的英文文本， 把它转换成一个同样的字母会出现在相邻位置很多次的文本。

Move-to-front encoding. Given a text file in which series of the same letter occur near each other many times, convert it into a text file in which small integers appear more frequently than large ones.

Move-to-front encoding。 给出一个文本，这个文本符合一个同样的字母会出现在相邻位置很多次的特征，
把这个文本转换成小数字比大数字出现更频繁的文本。

Huffman encoding. Given a text file in which certain symbols appear  more frequently than others, compress it by encoding common letters with short codewords and rare letters with long codewords.
The only step that compresses the message is the final step. It is particularly effective because the first two steps result in a message in which certain symbols appear more frequently than others. To decode a message, apply the inverse operations in reverse order: first apply the Huffman decoding, then the move-to-front decoding, and finally the inverse Burrows-Wheeler transform.
Huffman encoding. We implemented the Huffman encoding algorithm in class, so we’ll provide this part for you.

Huffman encoding。给出一个文本，这个文本符合小数字比大数字出现更频繁的特征，运用常见字母使用短编码，不常见字母使用长编码的方法压缩它。
只有最后一步是压缩了这个文本。 前两个步骤显著的导致了这个文本中确定的某个字符出现了的频率比别的方法更高。 为了解码这个信息， 需应用相反的顺序和相反的操作：首先应用 the Huffman decoding, 然后 the move-to-front decoding, 以及最后 逆 Burrows-Wheeler transform.

有关Huffman encoding。大家比较熟悉，资料比较多，这里不再说明。

Huffman decoding. You did this in COS 126, so we’ll provide the decoder for you too.

Move-to-front encoding. Initialize an ordered list of 256 characters, where extended ASCII character i appears ith in the list. Read in each character c from standard input one at a time, output the index in the array where c appears, and move c to the front of the list. As an example, the move-to-front encoding of

Move-to-front encoding。 初始给出一个256字符的顺序表， 如扩展ASCII码中字符i出现在列表的第i个位置。 从标准输入中读取每个字符c，输出一个数组表示c出现的索引值， 和移动c到列表的前端。 下面是一个例子：

a b b b a a b b b b a c c a b b a a a b c
is given by the following sequence of integers:
97 98 0 0 1 0 1 0 0 0 1 99 0 1 2 0 1 0 0 1 2
Note that ‘a’ is 97 in ASCII and that we have printed out the indices as type int with separating whitespace (for debugging only) rather than as type char without separating whitespace (for the version to submit). Name your program mtfe.c.
Move-to-front decoding. Initialize an ordered list of 256 characters, where extended ASCII character i appears ith in the list. Read in each character i (but think of it as an integer between 0 and 255) from standard input one at a time, print the ith character in the list, and move that character to the front of the list. Name your program mtfd.c and check that it recovers any message encoded with mtde.c.

注意到’a'在ASCLII表中是97，然后我们运用int类型并用空格隔开（只是为了debug）来打印它们。

Burrows-Wheeler transform. The goal of the Burrows-Wheeler transform is not to compress a message, but rather to transform it into a form that is more amenable to compression. The transform rearranges the characters in the input so that that there are lots of clusters with repeated characters, but in such a way that it is still possible to recover the original input. It relies on the following intuition: if you see the letters hen in English text, then most of the time the letter preceding it is t or w. If you could somehow group all such preceding letters together (mostly t’s and some w’s), then you would have an easy opportunity for data compression.

Burrows-Wheeler transform。 Burrows-Wheeler transform的目标不是为了压缩一个信息，是为了转换它成为一种形式更好的被压缩。 这个转换重新排列输入中的字符，使得成群的出现重复的字符， 同时用这种变换后，仍然可以恢复原始的输入。 这个方法依赖于以下的直觉：如果你看到英文单词hen， 在绝大部分时间里，它前面的字符是t或者w。 如果你在某种方法下把这些前面的字符一起组合起来， 然后你将有一个容易的机会来数据压缩。

First treat the input string as a cyclic string and sort the N suffixes of length N. Here is how it works for the text message “abracadabra”. Ignore the next column for now – you will need it for decoding only.

首先把输入字符串看作一个循环字符串，然后长度为N的字符串把它的N个suffixes排序。 下面是一个范例使用“abracadabra”字符串。现在先忽略最后一列， 你只需要用到它来解码。

 i     Original Suffixes          Sorted Suffixes   t     next
–    ———————     ———————     —-
 0    a b r a c a d a b r a     a a b r a c a d a b r        2
 1    b r a c a d a b r a a     a b r a a b r a c a d        5
*2    r a c a d a b r a a b     a b r a c a d a b r a        6
 3    a c a d a b r a a b r     a c a d a b r a a b r        7
 4    c a d a b r a a b r a     a d a b r a a b r a c        8
 5    a d a b r a a b r a c     b r a a b r a c a d a        9
 6    d a b r a a b r a c a     b r a c a d a b r a a       10
 7    a b r a a b r a c a d     c a d a b r a a b r a        4
 8    b r a a b r a c a d a     d a b r a a b r a c a        1
 9    r a a b r a c a d a b     r a a b r a c a d a b        0
10    a a b r a c a d a b r     r a c a d a b r a a b        3

The Burrows Wheeler transform t[] is the last column in the suffix sorted list, preceded by the the index into the suffix sorted row in which the original string appears.
2
rdarcaaaabb

The Burrows Wheeler 转换 t[]到最后一列在 suffix排序后的列表中， 按照原始字符串出现的顺序给出排序列表的下一行的索引值。
2
rdarcaaaabb

Notice how there are 4 a’s in a row and 2 consecutive b’s – this makes the file easier to compress. Write a program bwte.c to read in a text string and output the Burrows-Wheeler transform.
Inverting the Burrows-Wheeler transform. Now we describe how to undo the Burrows-Wheeler transform and recover the original message. If the jth suffix appears in row i above, then next[i] records the row where the j+1st suffix (jth suffix, shifted one character to the right) appears. Knowing the array next[] makes decoding easy, as with the following C code:

注意到这里有4个a两个b连续的在一起，这使得文件更容易的被压缩。
逆Burrows-Wheeler transform。 现在我们讨论怎么去撤销Burrows-Wheeler transform以及恢复原始信息， 如果第j个suffix出现在上面第i行， 那么next[i]记录着第j+1个suffix在哪一行（第j个suffix表示移动一个字符去右边）出现。 我们知道next[]使得解码很容易，如同下面的c代码：

int x = 2;
int next[11] = { 2, 5, 6, 7, 8, 9, 10, 4, 1, 0, 3 };
char t[11] = “rdarcaaaabb”;
for (i = 0; i < 11; i++)
   putchar(t[x = next[x]]);

Amazingly, the information contained in the Burrows-Wheeler transform is enough to reconstruct next[], and hence the original message! First, we know all of the characters in the original message, even if they’re permuted in the wrong order. This enables us to reconstruct the first column in the suffix sorted list by sorting the characters. Since c only occurs once in the message and the suffixes are formed using cyclic wrap-around, we can deduce that next[7] = 4. Similarly, d only occurs once, so we can deduce that next[8] = 1.

我们惊讶的发现，当我们能够创建出next[]也就有了Burrows-Wheeler transform包含的所有信息， 因此也包含原始消息。首先，我们知道原始字符串中的所有字符， 尽管他们在一个错误的排列顺序， 这使得我们可以重新创建第一列通过把全部字符排序的方法。 由于c只出现在消息中一次， 而且suffix是用循环环绕的方法构造出来，我们可以推断得出next[7]=4 ， 同样的，d只出现了一次， 所以我们可以推断出next[8]=1。

 i      Sorted Suffixes   t      next
–    ———————      —-
 0    a ? ? ? ? ? ? ? ? ? r
 1    a ? ? ? ? ? ? ? ? ? d
*2    a ? ? ? ? ? ? ? ? ? a
 3    a ? ? ? ? ? ? ? ? ? r
 4    a ? ? ? ? ? ? ? ? ? c
 5    b ? ? ? ? ? ? ? ? ? a
 6    b ? ? ? ? ? ? ? ? ? a
 7    c ? ? ? ? ? ? ? ? ? a        4
 8    d ? ? ? ? ? ? ? ? ? a        1
 9    r ? ? ? ? ? ? ? ? ? b
10    r ? ? ? ? ? ? ? ? ? b

However, since r appears twice, it may seem ambiguous whether next[9] = 0 and next[10] = 3, or whether next[9] = 3 and next[10] = 0. Here’s the key rule that resolves the ambiguity:
If row i and j both start with the same letter and i < j, then next[i] < next[j].
This rule implies next[9] = 0 and next[10] = 3. But why is this rule valid? The rows are sorted so row 9 is lexicographically less than row 10. Thus the nine unknown characters in row 9 must be less than the the nine unknown characters in row 10 (since both start with r). We also know that between the two rows that end with r, row 0 is less than row 3. But, the nine unknown characters in row 9 and 10 are precisely the first nine characters in rows 0 and 3. Thus, next[9] = 0 and next[10] = 3 or this would contradict the fact that the suffixes were sorted.
Name your program bwtd.c and check that it recovers any message encoded with bwte.c.

但是， 由于r出现了两次， 这似乎不确定是next[9]=0和next[10]=3 还是 next[9]=3和next[10]=0。 这里是一个解决这种不明确的关键点：
如果第i行和第j行同时从同一个字符开始，当i<j，那么next[i]<next[j]。
这条惯例使得next[9]=0和next[10]=3。但是为什么这条惯例是成立的？由于行是被排序过的，所以第9行是字典序小于第10行，所以第9行剩下9个字符必须小于第10行的9个（由于两行都是r开头）。我们同样知道以r结尾两行，第0行是小于第3行的。那么，在第9第10行的9个未知的字符确认的是第0第3行中的前9个字符。 所以next[9]=0和next[10]=3 , 不然这将会得到一个事实suffix没有被排序。

Analysis. Once you have all 6 programs working, compress some of these text files. Calculate the compression ratio achieved for each file. Also, report the time to compress and decompress each file.

近来有些题目

c++ double写了交上去wa…pascal extended重写后AC…

原因大概是extended=80位的double… orz

————————-

不过比赛都用c++,
所以要输出保留小数的一般我都用printf(”.5lf”,n)这样的格式,不过自从某些oj换了新版本的G++后,我wa了

改成 STL iomanip的保留小数方法,又AC

格式

cout <<setiosflags(ios::fixed);
cout <<setprecision(5) <<n<<endl;

好久没做DP,已经到了基本写不出的地步了

昨天见到这道题,以为是水题[事实也是],切之.

题意是给两个串s1 s2,求一个最短串s3,使得s1,s2都是s3的子序列,现在问s3共有多少种情况

一看便知道是二段DP,先求一次LCS最长公共子序列,因为最短的s3必然构建在s1,s2的LCS之上.得到一个问题b[x][y]的答案.b[x][y]表示从串s1的x位置s2的y位置开始,最大可以得到的LCS的长度

然后我们求s3的个数,设为问题c[x][y],即从串s1的x位置s2的y位置开始可以得到的答案的个数

于是有两种情况

1 s1[x]=s2[y]

此时我们需要取s1,s2中连续相同的最长一段即

c[x][y]=c[i][j]      (s1[x]=s2[y], s1[x+1]=s2[y+1],…..s1[i]=s2[j], x<=i<=len(s1) y<=j<=len(s2))

关于这个问题,我思考了1天,可见我已经不会DP了orz

2 s1[x]<>s2[y]

一开始c[x][y]=0

if b[x+1][y]=b[x][y] then c[x][y]=c[x][y]+c[x+1][y] //也就是说从s1取一个不会导致不出现LCS

if b[x][y+1]=b[x][y] then c[x][y]=c[x][y]+c[x][y+1] //同理

由于一开始没想到这么做经过多次wa,泪流满面

于是再放三个结论

2588356	18:13:15 1 May 2009	xt3000	1577	C++	Accepted		0.14	31 757 KB
2588348	18:08:43 1 May 2009	xt3000	1577	C++	Accepted		0.156	31 757 KB
2588328	17:59:43 1 May 2009	xt3000	1577	C++	Accepted		0.312	47 445 KB

第三个是使用int64
第二个是使用long
第一个是使用long,并把%运算换成-运算做了

//URAL_1577_E-mail
//By xt3000 Used VC08

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

char s1[2001],s2[2001];
long b[2001][2001];
unsigned long c[2001][2001];

long n,m;
const unsigned long M=1000000007;

long check(long x,long y){
if (b[x][y]==-1) {
if (x==n || y==m) {b[x][y]=0;return 0;};
b[x][y]=max(check(x+1,y),check(x,y+1));
if (s1[x]==s2[y]) b[x][y]=1+check(x+1,y+1);
};
return b[x][y];
};

void check2(long x,long y) {
if (c[x][y]==0) {
if (x==n || y==m)
c[x][y]=1;
else {
if (s1[x]==s2[y]) {
long i=x,j=y;
while (i<n && j<m && s1[i]==s2[j]) {i++;j++;};
check2(i,j);
c[x][y]=c[i][j];
}else{
if (b[x+1][y]==b[x][y]) {check2(x+1,y);c[x][y]=c[x][y]+c[x+1][y]; while (c[x][y]>=M) c[x][y]-=M;};
if (b[x][y+1]==b[x][y]) {check2(x,y+1);c[x][y]=c[x][y]+c[x][y+1]; while (c[x][y]>=M) c[x][y]-=M;};
};
};
};
};

int main(){
long i,j;
cin>>s1>>s2;
n=strlen(s1);m=strlen(s2);
for (i=0;i<n;i++)
for (j=0;j<m;j++) {
b[i][j]=-1;
};
j=check(0,0);
check2(0,0);
cout<<c[0][0]<<endl;
return 0;
};

xt3000

---

Rank	187
Problems submitted	306
Problems solved	300
Submissions	1141
Accepted	326
Wrong answer	526
Compilation error	66
Time limit	127
Output limit	1
Memory limit	22
Crash	73

Recent submissions
Recent accepted submissions

---

The list of solved problems:

1000 1/3, 1001 1/3, 1002 1/17, 1003 1/16, 1004 2/5, 1005 1/1, 1006 1/10, 1007 1/4, 1008 1/2, 1009 1/1, 1010 1/1, 1011 1/9, 1012 1/4, 1013 1/2, 1014 1/3, 1015 1/2, 1016 1/1, 1017 1/2, 1018 1/1, 1019 2/8, 1020 1/3, 1021 1/3, 1022 1/1, 1023 1/3, 1024 1/13, 1025 1/1, 1026 1/1, 1027 1/3, 1028 4/12, 1029 1/4, 1030 1/6, 1031 1/12, 1032 1/1, 1033 1/3, 1034 1/3, 1035 1/21, 1036 2/4, 1037 2/3, 1038 1/4, 1039 1/3, 1040 12/34, 1042 2/2, 1044 1/1, 1045 1/1, 1047 1/1, 1048 1/3, 1049 1/3, 1050 1/3, 1051 2/6, 1052 1/2, 1053 1/4, 1054 1/3, 1055 1/7, 1056 1/4, 1057 1/5, 1059 1/4, 1060 1/3, 1061 1/1, 1064 1/1, 1066 1/1, 1067 1/6, 1068 1/1, 1069 1/3, 1070 1/11, 1071 1/11, 1072 1/1, 1073 1/7, 1074 1/13, 1075 1/1, 1076 2/2, 1078 1/4, 1079 1/3, 1080 1/9, 1081 1/3, 1082 1/1, 1083 1/1, 1084 1/1, 1086 1/1, 1087 2/7, 1089 1/3, 1090 1/2, 1093 1/2, 1094 1/4, 1095 1/1, 1096 1/1, 1098 1/4, 1100 1/3, 1101 1/1, 1102 1/7, 1104 1/4, 1106 1/1, 1108 1/1, 1110 1/2, 1111 1/7, 1112 1/3, 1113 1/1, 1114 1/1, 1115 1/5, 1116 1/1, 1117 1/1, 1118 1/1, 1119 1/1, 1120 1/3, 1122 1/1, 1123 1/3, 1125 1/1, 1126 1/1, 1127 1/1, 1128 1/11, 1129 1/29, 1130 1/12, 1131 1/3, 1132 1/19, 1133 1/54, 1134 1/2, 1135 1/1, 1136 1/1, 1137 1/1, 1138 1/4, 1139 1/4, 1140 1/3, 1142 1/1, 1143 1/1, 1144 1/2, 1146 1/3, 1147 2/2, 1149 1/1, 1150 1/6, 1152 1/4, 1153 1/1, 1155 1/1, 1156 1/1, 1157 1/1, 1158 1/2, 1161 1/1, 1164 1/5, 1165 1/1, 1167 1/1, 1170 1/5, 1172 1/1, 1176 1/1, 1178 1/1, 1179 1/7, 1180 1/1, 1181 1/1, 1183 1/1, 1184 1/1, 1186 1/1, 1189 1/3, 1190 1/2, 1191 1/1, 1192 1/1, 1193 1/2, 1194 1/1, 1195 1/2, 1196 1/1, 1197 1/1, 1200 1/1, 1201 1/1, 1203 1/1, 1205 2/3, 1206 1/3, 1207 1/1, 1208 1/1, 1209 1/1, 1210 1/1, 1211 1/2, 1213 1/3, 1214 1/2, 1215 1/1, 1218 1/1, 1219 1/1, 1220 1/17, 1222 1/1, 1223 1/2, 1224 1/2, 1225 1/3, 1226 1/1, 1227 1/3, 1228 1/1, 1230 1/7, 1236 1/1, 1242 1/1, 1243 1/1, 1244 1/6, 1245 1/5, 1246 1/4, 1247 1/4, 1248 1/1, 1249 1/10, 1252 1/4, 1255 1/1, 1260 1/1, 1263 1/4, 1264 1/1, 1269 2/12, 1272 1/1, 1273 1/1, 1274 1/4, 1277 1/1, 1280 1/1, 1282 1/1, 1283 1/6, 1287 1/3, 1289 1/1, 1290 1/1, 1293 1/1, 1294 1/1, 1295 1/1, 1296 1/1, 1297 1/1, 1298 1/2, 1302 1/1, 1303 1/2, 1306 1/8, 1313 1/1, 1319 1/1, 1320 1/1, 1327 1/1, 1330 1/1, 1333 1/1, 1335 1/1, 1336 1/1, 1345 1/3, 1346 1/1, 1347 1/1, 1349 1/1, 1350 1/1, 1352 1/1, 1353 1/1, 1370 1/1, 1409 1/1, 1413 1/1, 1431 1/2, 1433 1/2, 1436 1/11, 1437 1/1, 1446 1/1, 1457 1/1, 1470 1/5, 1471 1/8, 1496 1/1, 1501 1/1, 1502 1/1, 1506 1/1, 1507 1/19, 1510 1/16, 1515 1/7, 1525 1/1, 1528 1/5, 1534 1/2, 1535 1/2, 1537 1/6, 1538 1/3, 1541 1/17, 1545 1/1, 1550 1/1, 1551 1/2, 1562 1/5, 1563 1/1, 1567 1/6, 1573 1/3, 1576 1/1, 1581 1/1, 1582 2/6, 1585 1/3, 1592 1/23, 1600 1/8, 1601 1/1, 1603 1/1, 1604 1/1, 1606 1/14, 1607 1/3, 1612 1/2, 1613 1/4, 1617 1/1, 1628 1/1, 1629 1/12, 1631 1/1, 1633 1/1, 1635 1/3, 1636 1/1, 1638 1/1, 1639 1/1, 1651 1/3, 1654 1/3, 1656 1/1, 1665 1/17, 1680 1/1, 1683 1/1, 1684 1/2, 1685 1/1, 1687 1/1, 1688 1/5, 1689 1/8, 1690 1/4, 1692 1/3, 1698 1/2, 1700 1/4, 1709 1/3

The list of unsolved problems:

1099 0/7, 1322 0/1, 1438 0/13, 1517 0/2, 1521 0/9, 1605 0/1

纪念一下

距离目标还有点距离的…

题目看上去很水,给定数字1..n,要求用它们组成合法的n节点最小堆…问有多少种

易得出递推公式  B(n)=C(n-1,L)*B(L)*B(n-1-L)        其中 B(x)为x个节点的问题答案, L 是根的左子树所含节点数

由于答案过大,自然题目要求%m

于是想着可以AC了,有如下求组合C(a,b)片断

for (i=1;i<=b;i++) k=k*(a-i+1)/i%m;

边乘边除,一看毫无问题,然后WA

以上做法问题是%m的操作可能把以后要/的某个i用掉了…举个例子 C(6,2)%2=1  but 6/1%2*5/2%2=0

于是我们为了解决这个决定不用乘法…自然是递推公式

C(a,b) = 1                                                   a=0 or b=0 or a=b
C(a,b) = a                                                   b=1
C(a,b) = C(a-1,b) + C(a-1,b-1)            b!=a 当然a>b

由于加法的原因,想怎么%就怎么%

再次想着可以AC了,于是有了如下C(a,b)片断 ，CC[i][j]保存组合数C[i][j]的结果

long long CC[N][N];

void C(long a,long b){
if (CC[a][b]==0) {
if (a==0 || b==0 ||a==b)
CC[a][b]=1;
else if (b==1)
CC[a][b]=a%m;
else {
CC[a][b] = (C(a-1,b)+C(a-1,b-1))%m;
};
};
return CC[a][b];
};

一看就是DP的组合数求解，怎么看速度都是平方级，对于N=1k来说，no prob!! 然后TLE

自己测试了一下m=100000000的时候，C(1000,500)是瞬间的，但是，当我把m=99999时，慢到吐血了

What the XXX!!!!

难道%m的速度是如此飘渺的东西么！！！！！

于是作了如下测试

for (i=1;i<=1000;i++)

for (j=1;j<=i;j++)

arr[i][j]=(arr[i-1][j-1]+arr[i-1][j])%m;

上面片断居然是瞬间！！！！

于是我整个人都肉牛满面了

原来递归程序的时间性能和%m是有关系的！！！！Who the hell did you think I am? 我怎么能知道如此神棍的事情

于是又有了如下打表片断
void C2(){
long i,j;
for (i=0;i<=n;i++) {
CC[i][0]=1;CC[0][i]=1;CC[i][i]=1;CC[i][1]=i;CC[i][1]%=m;
}; CC[0][1]=1;
for (i=1;i<=n;i++)
for (j=2;j<=i;j++) {
CC[i][j]=(CC[i-1][j]+CC[i-1][j-1])%m;
};
};

交上去

605324

2009-03-30 02:27:55

Accepted

3216

C++

1.2K

0′00.04″

9036K

xt3000

我什么都不想说了

#include <iostream>
#include <algorithm>

using namespace std;

long n;
long long m;
long long b[1001],CC[1001][1001];

//打?表?大?法?....
void C2(){
    long i,j;
    for (i=0;i<=n;i++) {
        CC[i][0]=1;CC[0][i]=1;CC[i][i]=1;CC[i][1]=i;CC[i][1]%=m;
    };CC[0][1]=1;
    for (i=1;i<=n;i++)
        for (j=2;j<=i;j++) {
            CC[i][j]=(CC[i-1][j]+CC[i-1][j-1])%m;
        };
};

long find_l(long ori)
{
    long ans=0,i,j,tt;
    for(i=1,j=1;;j<<=1,i++)
    {
        ans+=j;
        if(ans>ori)
            break;
    }
    ans-=j;
    tt=ans;
    ans=ori-ans;
    i--;
    j>>=1;
    if(ans<=j)
    {
        return tt/2+ans;
    }
    else
        return tt/2+j;
}

long long check(long n){
    if (b[n]==-1) {
        long p=find_l(n);
        b[n]=CC[n-1][p]*check(p)%m*check(n-p-1)%m;
    };
    return b[n];
};

int main(){
    long test,i,j;
    cin>>test;
    while (test--) {
        cin>>n>>m;
        fill(b,b+n+1,-1);
        C2();
        b[0]=1;b[1]=1;
        cout<<check(n)<<endl;
    };
    return 0;
};

dijk通常不是最快的最短路方法，不过感觉上性能比较稳定就是了，而且该过的题都能过，以前都是写O(n^2)，今天写了下O(mlogm)版，感觉上用stl写还是比较快的，另外据说用STL_heap封装的stl priority_queue速度不是很好，估计是内部使用vector的原因，那干脆直接用STL_heap算了，速度最有保证，写起来区别也不大

//URAL_1205_Underground

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;

struct point{
    double d;
    long from,check;
};

double s[203][203];  //邻?接?矩?阵?
point a[201];
long n;
double feet,underground;

double dis(double x1,double y1,double x2,double y2){
    return sqrt(pow(x1-x2,2)+pow(y1-y2,2));
};

void input(){
    long i,j,k;
    double pos[203][2];
    cin>>feet>>underground>>n;
    for (i=1;i<=n;i++) cin>>pos[i][0]>>pos[i][1];
    while (cin>>j>>k) {
        if (j==0 && k==0) break;
        s[j][k]=dis(pos[j][0],pos[j][1],pos[k][0],pos[k][1])/underground;
        s[k][j]=s[j][k];
    };
    cin>>pos[n+1][0]>>pos[n+1][1]>>pos[n+2][0]>>pos[n+2][1];
    for (i=1;i<n+2;i++)
        for (j=i+1;j<=n+2;j++)
            if (s[i][j]==0) {
                s[i][j]=dis(pos[i][0],pos[i][1],pos[j][0],pos[j][1])/feet;
                s[j][i]=s[i][j];
            };
};

/*普?通?dijk
void check(long st){
    long i,j,p;
    double m;
    for (i=1;i<=n+2;i++) a[i].d=999999999;
    p=st;a[p].d=0;
    for (i=1;i<n+2;i++) {
        a[p].check=1;
        for (j=1;j<=n+2;j++)
            if (a[j].check==0 && s[p][j]+a[p].d<a[j].d) {
                a[j].d=a[p].d+s[p][j];
                a[j].from=p;
            };
        m=999999999;
        for (j=1;j<=n+2;j++)
            if (a[j].check==0 && a[j].d<m) {m=a[j].d;p=j;};
    };
};
*/

//堆?dijk

struct node_pq{
    long id;  //节?点?编?号?
    double d;  //目?前?最?短?路?值?
    friend bool operator < (const node_pq &k1,const node_pq &k2){
        return k1.d>k2.d;
    };//根?据?点?的?距?离?的?最?小?堆?比?较?函?数?
};

void check(long st){
    long i,j,p;
    node_pq pq[203*203];//优?先?队?列?
    long n_pq=0;  //优?先?队?列?长?度?
    for (i=1;i<=n+2;i++) a[i].d=999999999;
    p=st;a[p].d=0;
    for (i=1;i<=n+2;i++) {pq[n_pq].d=a[i].d;pq[n_pq].id=i;n_pq++;}; //把?点?加?入?优?先?队?列?
    make_heap(pq,pq+n_pq);
    for (i=1;i<n+2;i++) {
        p=pq[0].id;
        a[p].check=1;
        for (j=1;j<=n+2;j++)
            if (a[j].check==0 && s[p][j]+a[p].d<a[j].d) {
                a[j].d=a[p].d+s[p][j];
                a[j].from=p;
                pq[n_pq].id=j;pq[n_pq].d=a[j].d;n_pq++;
                push_heap(pq,pq+n_pq);
            };
        while (a[pq[0].id].check==1) {
            pop_heap(pq,pq+n_pq);
            n_pq--;
        };
    };
};

void print(){
    long i,j,r[203];
    r[0]=0;
    j=n+2;
    while (j!=0) {
        r[++r[0]]=j;
        j=a[j].from;
    };
    printf("%.7lf\n%ld ",a[n+2].d,r[0]-2);
    for (i=r[0];i>2;i--) {
        printf("%ld ",r[i-1]);
    };
};

int main(){
    input();
    check(n+1);
    print();
    return 0;
};

这题水题,给n个点,叫你找出两个连一线,使平面上的点分为两等份

找出左下的点,以该点对其他点做极角排序,排序的中点及左下点连线即可

嘛,重点是math库有个美好的函数atan2(double y,double x),可以处理x=0及正负的情况,太美好了…

//URAL_1207_Median
//By xt3000 Used VC08

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

struct point {
    long x,y;
    long id;
    double angle;
    friend bool operator < (const point &a, const point &b) {
        return a.angle<b.angle;
    };
};

long n;
point a[10001];

int main(){
    long i,m=1;
    cin>>n;
    for (i=1;i<=n;i++) {
        cin>>a[i].x>>a[i].y;a[i].id=i;
        if (a[i].y<a[m].y || (a[i].y==a[m].y && a[i].x<a[m].x)) m=i;
    };
    if (m!=1) swap(a[1],a[m]);
    for (i=2;i<=n;i++) a[i].angle=atan2(double(a[i].y-a[1].y),double(a[i].x-a[1].x));
    sort(a+2,a+n+1);
    cout<<a[1].id<<" "<<a[n/2+1].id<<endl;
    return 0;
};

在线多询问题,1改变<x,y,z>的值,2询问x1<x<x2,y1<y<y2,z1<z<z2内的值的和

据说这道题可以用树状数组+容斥原理做,那是大牛算法,我不会

好吧,这只是一个垃圾的三维线段树.

一直crash,数组开到500w,ac了

#include <stdio.h>

struct node{
    long l,r;
    long value;
};

struct STree{
    void buildST(long l,long r,node *arr,long *N,long level=0){
        a=arr;N_a=N;
        root=++(*N_a);
        L=l;R=r;
        level=1;
    };
    long *N_a;
    node *a;
    long L,R,root;
}; 

long n;
node a[5500000];
long an=0;
STree s[2000000];
long N_STree=0;
long x1,x2,y1,y2,z1,z2;

    long add() {
        return ++(an);
    };

    long ask(long p,long left,long right,long st,long en,long level=0) {
        if (p==0) return 0;
        if (left==st && right==en) {
            switch (level) {
                case 0:    return ask(s[a[p].value].root,s[a[p].value].L,s[a[p].value].R,y1,y2,1); break;
                case 1:    return ask(s[a[p].value].root,s[a[p].value].L,s[a[p].value].R,z1,z2,2); break;
                case 2: return a[p].value;
            };
        }else{
            long mid=(left+right)/2;
            if (en<mid) return ask(a[p].l,left,mid,st,en,level);
            else if (st>mid) return ask(a[p].r,mid+1,right,st,en,level);
            else return ask(a[p].l,left,mid,st,mid,level)+ask(a[p].r,mid+1,right,mid+1,en,level);
        };
    };
    void update(long p,long left,long right,long st,long en,long &k,long level=0){
        if (left==st && right==en) {
            switch (level) {
                case 0:
                    if (a[p].value==0) {a[p].value=++N_STree; s[N_STree].buildST(0,n-1,a,&an,1);};
                    update(s[a[p].value].root,s[a[p].value].L,s[a[p].value].R,y1,y2,k,1); break;
                case 1:
                    if (a[p].value==0) {a[p].value=++N_STree; s[N_STree].buildST(0,n-1,a,&an,2);};
                    update(s[a[p].value].root,s[a[p].value].L,s[a[p].value].R,z1,z2,k,2); break;
                case 2:
                    a[p].value+=k; break;
            };
        }else{
            long mid=(left+right)/2;
            if (en<=mid) {if (a[p].l==0) a[p].l=add(); update(a[p].l,left,mid,st,en,k,level);}
            else if (st>mid) {if (a[p].r==0) a[p].r=add(); update(a[p].r,mid+1,right,st,en,k,level);}
            else {
                if (a[p].l==0) a[p].l=add(); if (a[p].r==0) a[p].r=add();
                update(a[p].l,left,mid,st,mid,k,level);
                update(a[p].r,mid+1,right,mid+1,en,k,level);
            };
            switch (level) {
                case 0:
                    if (a[p].value==0) {a[p].value=++N_STree; s[N_STree].buildST(0,n-1,a,&an,1);};
                    update(s[a[p].value].root,s[a[p].value].L,s[a[p].value].R,y1,y2,k,1); break;
                case 1:
                    if (a[p].value==0) {a[p].value=++N_STree; s[N_STree].buildST(0,n-1,a,&an,2);};
                    update(s[a[p].value].root,s[a[p].value].L,s[a[p].value].R,z1,z2,k,2); break;
                case 2:
                    a[p].value=a[a[p].l].value+a[a[p].r].value;
                    break;
            };
        };
    };

int main(){
    long i,p;
    scanf("%ld",&n);
    s[++N_STree].buildST(0,n-1,a,&an);
    scanf("%ld",&i);
    while (i!=3) {
        if (i==1) {
            scanf("%ld%ld%ld%ld",&x1,&y1,&z1,&p);
            x2=x1;y2=y1;z2=z1;
            update(1,0,n-1,x1,x2,p,0);
        }else{
            scanf("%ld%ld%ld%ld%ld%ld",&x1,&y1,&z1,&x2,&y2,&z2);
            printf("%ld\n",ask(1,0,n-1,x1,x2,0));
        };
        scanf("%ld",&i);
    };
    return 0;
};

先吐槽,万恶的10w*10w,刚好超过了long的范围,为了这个(long long)的问题,贡献了多少次WA!!!啊啊啊啊啊

该题通过蛤蟆牛和DQUERY的启发,决定采用离线处理,先把询问[x,y]全部读入,按照y为关键字,从小到大排序,依次处理

设原序列每一项为a[i]

i从小到大扫描每一项a[]

于是当扫描到a[i]时,我们想象这样一个序列b[],b[j](j<=i)表示从a[j]加到a[i]的不重复元素和的大小

同时维护一个b[].value,b[k].value表示b[k]曾经出现的最大值

若此时有询问[x,i],实际上就是求b.value[]在[x,i]项内的最大值

那么如何维护b[]呢,显然,一开始b[]都为0,然后每次扫描到一个a[i],把a[i]加到b中[pre[a[i]]+1,i]的这个范围就好，其中pre[k],表示k上一次出现在原序列的位置

现在的问题便是给定一个序列b[]，要求种操作：1往b[]的[x,y]范围的数同时增加k    2询问b[]中[x,y]范围中找出b[p].value最大的一项，返回b[p].value

我们分析1操作。该问题如果只是往b[]中的一项增加k,那么（logn）线段树解法是显而易见的，但是要往一个区间[x,y]内增加k，最直观的想法是每一项分别增加，复杂度((y-x+1)logn)最坏情况(nlongn)显然是TLE。

怎么办呢,换一个想法,对于10w的询问来说,若一次询问要访问线段树上log(n)个节点,那么一共也只需要用10w*log(n)个节点,其他访问不到的节点,你维护了它也没用,于是有了这样一个想法

当维护到一个线段树节点[x1,y1]的时候,若整个叶子都增加k,好的,我们把这点最值求完,然后就不再处理他的左右儿子,只在左右儿子上做一个标记,表明他们应该要被修改,且把修改量k传递下去,完毕,不管了

当未来我们进行询问操作时,若用到[x1,y1]这点的左右儿子时,我们再根据传递下来的k修改之,若不用到,自然不修改,继续放着

这样,维护操作和询问操作复杂度依然是(logn)

ps,把修改量k传递下去也不是仅仅save那么简单,事实上跟区间最值有关的因素有,未修改前区间最大值nowmax,区间的历史最大值value(即nowmax曾经最大的值),从上次修改到现在为止的修改量nowchg,从上次到现在为止修改量的历史最大值maxchg(即nowchg曾经最大的值).维护的时候,value=max(value,nowmax+maxchg)  nowmax=nowmax+nowchg

//SPOJ 1557 Can you answer these queries II

//By xt3000 Used VC08

#include <stdio.h>

#include <algorithm>

using namespace std;

struct Que{

long begin,end;

long long ans;

long num;

friend bool operator < (const Que &a,const Que &b) {

return a.end<b.end;

};

};

struct STree{

long l,r;

bool modify; //该区间是否需要修改

long long maxchg; //该区间历史上需要修改最大的增加的数量

long long value; //该区间历史的最大值

long long nowchg; //该区间现在需要修改增加的数量

long long nowmax; //该区间在目前的最大值

};

long n,m;

long a[100010];

long t[200010]; //t[i+10W]表示i的上一次出现在什么位置

Que q[100010];

long q_index[100010];

STree b[300010];

void build(long p,long left,long right){

b[p].modify=false;

b[p].nowmax=0;

b[p].value=0;

b[p].maxchg=0;

b[p].nowchg=0;

if (left==right) {

b[p].l=0;b[p].r=0;

}else{

long mid=(left+right)/2;

b[p].l=p*2;b[p].r=p*2+1;

build(b[p].l,left,mid);build(b[p].r,mid+1,right);

};

};

void updateOnce(long &p){ //对p节点进行一次修改,并把需要修改的信息传递到子节点

if (b[p].modify==true) {

//修改该点的数值

if (b[p].nowmax+b[p].maxchg>b[p].value) b[p].value=b[p].nowmax+b[p].maxchg;

b[p].nowmax+=b[p].nowchg;

if (b[p].l!=0) {

//把儿子设置成需要修改

b[b[p].l].modify=true;

b[b[p].r].modify=true;

if (b[b[p].l].nowchg+b[p].maxchg>b[b[p].l].maxchg) b[b[p].l].maxchg=b[b[p].l].nowchg+b[p].maxchg;

b[b[p].l].nowchg+=b[p].nowchg;

if (b[b[p].r].nowchg+b[p].maxchg>b[b[p].r].maxchg) b[b[p].r].maxchg=b[b[p].r].nowchg+b[p].maxchg;

b[b[p].r].nowchg+=b[p].nowchg;

};

//设置该点不再需要修改

b[p].modify=false;

b[p].nowchg=0;b[p].maxchg=0;

};

};

void update(long p,long left,long right,long st,long en,long &k){ //把线段树中[st,en]段上的数全部加k

updateOnce(p);

if (left==st && en==right) {

b[p].nowchg=(long long)k;b[p].maxchg=(long long)k;

b[p].modify=true;

}else{

long mid=(left+right)/2;

if (en<=mid) update(b[p].l,left,mid,st,en,k);

else if (st>mid) update(b[p].r,mid+1,right,st,en,k);

else {

update(b[p].l,left,mid,st,mid,k);

update(b[p].r,mid+1,right,mid+1,en,k);

};

updateOnce(b[p].l);updateOnce(b[p].r);

b[p].nowmax=max(b[b[p].l].nowmax,b[b[p].r].nowmax);

b[p].value=max(b[p].value,max(b[b[p].l].value,b[b[p].r].value));

};

};

long long ask(long p,long left,long right,long st,long en){ //求线段树中[st,en]段上最大的数值

updateOnce(p);

if (st==left && en==right) {

return b[p].value;

}else{

long mid=(left+right)/2;

if (en<=mid) return ask(b[p].l,left,mid,st,en);

else if (st>mid) return ask(b[p].r,mid+1,right,st,en);

else return max(ask(b[p].l,left,mid,st,mid),ask(b[p].r,mid+1,right,mid+1,en));

};

};

int main(){

long i,j;

scanf(“%ld”,&n);

for (i=1;i<=n;i++) {

scanf(“%ld”,&a[i]);

};

scanf(“%ld”,&m);

for (i=0;i<m;i++) {

scanf(“%ld%ld”,&q[i].begin,&q[i].end);

q[i].num=i;

};

sort(q,q+m);

for (i=0;i<m;i++) q_index[q[i].num]=i;

build(1,1,n);

j=0;

for (i=1;i<=n;i++) {

update(1,1,n,t[a[i]+100000]+1,i,a[i]);

while (q[j].end<=i) {

q[j].ans=ask(1,1,n,q[j].begin,q[j].end);

if (q[j].ans<0) q[j].ans=0;

j++;

if (j==m) {

for (i=0;i<m;i++) printf(“%lld\n”,q[q_index[i]].ans);

return 0;

};

};

t[a[i]+100000]=i;

};

return 0;

};