| 日历 |
|
|
| 网志分类 |
|
| 最新的评论 |
|
|
|
| 站内搜索 |
|
| 友情链接 |
|
0027546
|
|
 |
芹菜地
lovely *,* {07/04/30/00:44}
|
DownThemAll(dTa)是目前firefox下用得最多的下载插件，它支持多线程下载，断点续传等，使用很方便。美中不足的是，dTa对http协议下载支持很好，但对ftp协议下载却几乎没有做任何扩展，跟firefox自带的下载工具功能上几乎没有什么区别，不能暂停，不能断点续传，不支持多线程下载等。但实际上,xunlrunner库里对ftp的实现是完全的，只是因为dTa没有利用到而已。要用到这些功能也很简单，下面就介绍如何更改dTa，使它对ftp的支持更好一些。
首先到dTa这个扩展的目录下，通常是~user/.mozilla/****.default/extensions/{DDC359D1-844A-42a7-9AA1-88A850A938A8} /chrome下，{}中包含的是dTa的当前uuid.
把chrome.jar解压到当前目录, linux下是unzip chrome.jar就行了;再将chrome.jar复制为chrome.orig.jar，以便后面操作失误时可以恢复。
再到当前目录下的content/dta目录下，这里有一个manager.js，它是dta文件下载的核心模块，也是我们要更改的地方。
打开manager.js文件，跳到1693行左右，这里有一个try catch语句块。try部分主要是为了从某一部分开始请求http文件，catch部分为空。在整个catch语句里，我们加上自己对ftp协议的处理，它也是一个try catch语句块:
try {
let rc = this._chan.QueryInterface(Ci.nsIResumableChannel);
rc.resumeAt(c.start+c.written, null);
} catch(ex) {
}
这个语句块判断下载的文件是否可以续传，如果可以，就跳到它要续传的位置。
再在文件中跳到2038行左右，这里有一个单独的语句d.resumable=false; 我们要把这句话替换成一个如下的try catch语句块:
try {
let rc = this._chan.QueryInterface(Ci.nsIResumableChannel);
d.resumable = true;
} catch(ex) {
d.resumable = false;
}
它也是判断当前下载文件的可续传性。
保存文件manager.js，退出。我们再回到chrome.jar所在的目录中去，把更新后的manager.js文件加进去. zip -r chrome.jar content/dta/manager.js。
重新启动firefox，这下dta管理器中的ftp文件就可以被暂停了。由于ftp站点通常限制了同ip的访问数，多线程下载通常用不上。这没关系，反正修改后的dta现在是支持多线程下载和续传了。
|
2166.cpp
#include<iostream>
using namespace std;
int P, Q, A, N;
int gcd(int a, int b){
int t;
if(a < b){
t = a, a = b, b = t;
}
while(b!=0){
t = a % b;
a = b;
b = t;
}
return a;
}
int count(int v, int p, int q, int a, int n){
int ret = 0;
if(p == 1 && q >= v){
ret++;
}
if(n<=1) return ret;
int t, r, s;
int np, nq;
for(s = v; s*s<=a; s++){
np = p*s-q;
nq = q*s;
t = gcd(nq, np);
nq /= t;
if(np < 0 || s*nq>a){
continue;
}
np /= t;
ret += count(s, np, nq, a/s, n-1);
}
return ret;
}
void fun(){
int t = gcd(P, Q);
P /= t;
Q /= t;
int ret = count(1, P, Q, A, N);
printf("%d\n", ret);
}
int readIn(){
scanf("%d%d%d%d",&P,&Q,&A,&N);
return P + Q + A + N;
}
int main(){
while(readIn() > 0){
fun();
}
return 0;
}
|
使用两个二维数组就可以，设二维数组cur[M][M], nex[M][M], 其中M<=5，
cur[i][j]表示对于当前的串，从现在向前数，0比1多i个，1比0多j个。比如说
串"00110"，它的i为1，"00110"，j为2, "110"。因此，对于cur[i][j]，如果对它后面加上一个"1"，则将cur[i][j]加到nex[m][n]上，其中m,n的计算如下
m = i-1, n = j +1. 如果m<0，将m设为0；如果n>M,则放弃计算。
如果对它后面加个一个"0"，计算也类似。
代码如下:
#include<iostream>
using namespace std;
enum {
SIZ = 6,
};
typedef long long (*D2)[SIZ];
long long tab[2][SIZ][SIZ];
int N, K, lim;
void fun(){
if(N <= K){
printf("%d\n", 1<<N);
return ;
}
D2 pre, cur, tmp;
pre = tab[0], cur = tab[1];
memset(pre, 0, sizeof(tab[0]));
pre[0][0] = 1;
int i, a, b, m, n;
for(i=0; i<N; i++){
memset(cur, 0, sizeof(tab[0]));
for(a=0; a<= K; a++){ // count zero
for(b=0; b<= K; b++){ // count one
// append zero
m = a + 1, n = b - 1;
if(n < 0) n = 0;
if(m <= K)
cur[m][n] += pre[a][b];
// append one
m = a - 1, n = b + 1;
if(m < 0) m = 0;
if(n <= K)
cur[m][n] += pre[a][b];
}
}
tmp = pre, pre = cur, cur = tmp;
}
long long ret = 0;
for(a=0; a<= K; a++){
for(b=0; b<=K; b++){
ret += pre[a][b];
}
}
printf("%lld\n", ret);
}
int main(){
while(scanf("%d%d", &N, &K) > 0){
fun();
}
return 0;
}
|
上了一个新台阶，以后再接再励，登上800题，900题，1000题...
|
计算prior时，要考虑的东西比较多，也不是很明白。
prior[i][j] = max {
same[i][k] + opt[k+1][j], if (i==0||chr[i-1]!=chr[k+1]) //因为左边可以绑定，右边的就是自由计算了
same[i][k] + prior[k+1][j], if (chr[i-1]==chr[k+1]) // 左边不可绑定，先算右边的
} 其中 chr[i]==chr[k]
|
inner[i][j]是指求当color[i-1]==color[j+1]时内部各色球从i到j计算所得的值，它可能被以下三种值所更新:
1. same[i][j]，当color[i] == color[j]时;
2. same[i][k] + opt[k+1][j]，当color[i]==color[k]&&(i==0||color[i-1]!=color[k+1]);
3. same[i][k] + prior[k+1][j]，当color[i]==color[k]&&color[i-1]==color[k+1].
在计算inner[i][j]的值，必须确保它们的外围球i-1,j+1不受影响，即每次计算后，边界球都不能与i-1的颜色相同。
|
推导式part的计算与same比较类似，估计它们可能可以合并。part[i][j]也与两个条件有关：
1. part[i][j] = inner[i][j-1];
2. part[i][j] = inner[i][k-1] + inner[k+1][j-1], color[k]==color[j]&&len[k]==1&&len[j]==1
注意的是，这里color[i]与color[j]未必同色。
|
当chr[i]==chr[j]时，计算same[i][j],
分两种情况，1)当len[i]==1，且存在k<=j&&k>=i&&chr[k]==chr[i]&&len[k]==1时
更新val为消去i,k,j的值
更新same[i][j]为val+inner[i+1][k-1]+part[k+1][j]
2)当len[i]>=2时,
更新val为消去i,j的值
更新same[i][j]为val+part[k+1][j]
注意这里没有考虑len[i]>2&&len[j]==1&&len[k]==1时消去的值，是因为在part[][]中会考虑这种情况。
|
在对opt进行计算时，使用的opt推导式如下:
1.opt[i][j] = same[i][j] 当chr[i] == chr[j]时
2.opt[i][j] = same[i][k] + opt[k][j] 当i<=k && k<j &&chr[i]==chr[k]时
opt[i][j]取1,2中的最大值。
opt使用的是从左到右的消去法，假定每次消去的都是最左边的段。
因此，opt的计算又转化成求same的计算了。
|
2127.cpp
#include <stdio.h>
#include <string.h>
#include <assert.h>
inline int sqr(int x){ return x*x ; }
inline int max(int x, int y) { return x>y?x:y; }
inline int min(int x, int y) { return x<y?x:y; }
inline void update(int &v, int nv){
if(v < nv) v = nv;
}
int opt[200][200];
int inner[200][200];
int prior[200][200];
int same[200][200];
int part[200][200];
char chr[200];
int len[200];
int n;
int main() {
int l, i, k, j;
char cmd[201];
int ncmd;
while(scanf("%s", cmd) != EOF) {
ncmd = static_cast<int> ( strlen(cmd) );
n = 0;
for(i = 0; i < ncmd; ++i) {
if(cmd[i] == 0 || cmd[i] != cmd[i - 1]) {
k = i;
}
if(i == ncmd - 1 || cmd[i] != cmd[i + 1]) {
chr[n] = cmd[i];
len[n] = i - k + 1;
++n;
}
}
for(i = 0; i < n; ++i) {
opt[i][i] = sqr(max(len[i], 2) + 1);
inner[i][i] = sqr(max(len[i], 2) + 1);
prior[i][i] = -1;
same[i][i] = sqr(max(len[i], 2) + 1);
part[i][i] = -1;
}
for(l = 2; l <= n; ++l) for(i = 0; i + l <= n; ++i){
j = i + l - 1;
same[i][j] = -1;
if(chr[i] == chr[j]) {
if(len[i] >= 2) {
update(same[i][j], sqr(len[i] + max(len[j], 2)) + part[i + 1][j]);
} else {
for(k = i; k < j; ++k) {
if(chr[k] != chr[i] || len[k] != 1)
continue;
if(k == i) {
update(same[i][j], sqr(2 + max(len[j], 2)) + part[k + 1][j]);
} else {
update(same[i][j], sqr(2 + max(len[j], 2)) + inner[i + 1][k - 1] + part[k + 1][j]);
}
}
}
}
part[i][j] = -1;
if(i != 0 && chr[i - 1] == chr[j]) {
if(len[j] >= 2) {
update(part[i][j], inner[i][j-1]);
} else {
for(k = j; k > i; --k) {
if(chr[k] != chr[j] || len[k] != 1)
continue;
if(k == j) {
update(part[i][j], inner[i][k-1]);
} else {
update(part[i][j], inner[i][k-1] + inner[k+1][j-1]);
}
}
}
}
opt[i][j] = inner[i][j] = prior[i][j] = -1;
for(k = i; k <= j; ++k) {
if(chr[k] != chr[i])
continue;
if(k == j) {
update(opt[i][j], same[i][j]);
update(inner[i][j], same[i][j]);
continue;
}
update(opt[i][j], same[i][k]+opt[k+1][j]);
if(i == 0 || chr[i - 1] != chr[k + 1]) {
update(inner[i][j], same[i][k] +opt[k+1][j]);
update(prior[i][j], same[i][k] +opt[k+1][j]);
} else {
if(prior[k + 1][j] != -1) {
update(inner[i][j], same[i][k] + prior[k+1][j]);
update(prior[i][j], same[i][k] + prior[k+1][j]);
}
}
}
}
printf("%d\n", opt[0][n - 1]);
}
return 0;
}
|
orignal.cpp
#include <stdio.h>
#include <string.h>
#include <assert.h>
#define sqr(x) ((x) * (x))
#define max(x, y) ((x) > (y) ? (x):(y))
#define min(x, y) ((x) < (y) ? (x):(y))
int delta[200][200][3];
int xxx[200][200];
int yyy[200][200];
char chr[200];
int len[200];
int n;
int main() {
int l, i, i1, j, k;
char cmd[201];
int ncmd;
while(scanf("%s", cmd) != EOF) {
ncmd = strlen(cmd);
n = 0;
for(i = 0; i < ncmd; ++i) {
if(cmd[i] == 0 || cmd[i] != cmd[i - 1]) {
i1 = i;
}
if(i == ncmd - 1 || cmd[i] != cmd[i + 1]) {
chr[n] = cmd[i];
len[n] = i - i1 + 1;
++n;
}
}
assert(n >= 1);
for(i = 0; i < n; ++i) {
delta[i][i][0] = sqr(max(len[i], 2) + 1);
delta[i][i][1] = sqr(max(len[i], 2) + 1);
delta[i][i][2] = -1;
xxx[i][i] = sqr(max(len[i], 2) + 1);
yyy[i][i] = -1;
}
for(l = 2; l <= n; ++l) for(i = 0; i + l <= n; ++i){
j = i + l - 1;
xxx[i][j] = -1;
if(chr[i] == chr[j]) {
if(len[i] >= 2) {
if(xxx[i][j] == -1 || sqr(len[i] + max(len[j], 2)) + yyy[i + 1][j] > xxx[i][j])
xxx[i][j] = sqr(len[i] + max(len[j], 2)) + yyy[i + 1][j];
} else {
for(i1 = i; i1 < j; ++i1) {
if(chr[i1] != chr[i])
continue;
if(len[i1] != 1)
continue;
if(i1 == i) {
if(xxx[i][j] == -1 || sqr(2 + max(len[j], 2)) + yyy[i1 + 1][j] > xxx[i][j]) {
xxx[i][j] = sqr(2 + max(len[j], 2)) + yyy[i1 + 1][j];
}
} else {
assert(delta[i + 1][i1 - 1][1] != -1);
if(xxx[i][j] == -1 || sqr(2 + max(len[j], 2)) + delta[i + 1][i1 - 1][1] + yyy[i1 + 1][j] > xxx[i][j]) {
xxx[i][j] = sqr(2 + max(len[j], 2)) + delta[i + 1][i1 - 1][1] + yyy[i1 + 1][j];
}
}
}
}
assert(xxx[i][j] != -1);
}
yyy[i][j] = -1;
if(i != 0 && chr[i - 1] == chr[j]) {
if(len[j] >= 2) {
assert(delta[i][j - 1][1] != -1);
if(yyy[i][j] == -1 || delta[i][j - 1][1] > yyy[i][j])
yyy[i][j] = delta[i][j - 1][1];
} else {
for(i1 = j; i1 > i; --i1) {
if(chr[i1] != chr[j])
continue;
if(len[i1] != 1)
continue;
if(i1 == j) {
assert(delta[i][i1 - 1][1] != -1);
if(yyy[i][j] == -1 || delta[i][i1 - 1][1] > yyy[i][j])
yyy[i][j] = delta[i][i1 - 1][1];
} else {
assert(delta[i][i1 - 1][1] != -1);
assert(delta[i1 + 1][j - 1][1] != -1);
if(yyy[i][j] == -1 || delta[i][i1 - 1][1] + delta[i1 + 1][j - 1][1] > yyy[i][j])
yyy[i][j] = delta[i][i1 - 1][1] + delta[i1 + 1][j - 1][1];
}
}
}
assert(yyy[i][j] != -1);
}
delta[i][j][0] = delta[i][j][1] = delta[i][j][2] = -1;
for(i1 = i; i1 <= j; ++i1) {
if(chr[i1] != chr[i])
continue;
if(i1 == j) {
for(k = 0; k <= 1; ++k) {
if(delta[i][j][k] == -1 || delta[i][j][k] < xxx[i][j])
delta[i][j][k] = xxx[i][j];
}
continue;
}
if(delta[i][j][0] == -1 || delta[i][j][0] < xxx[i][i1] + delta[i1 + 1][j][0])
delta[i][j][0] = xxx[i][i1] + delta[i1 + 1][j][0];
for(k = 1; k <= 2; ++k) {
if(i == 0 || chr[i - 1] != chr[i1 + 1]) {
if(delta[i][j][k] == -1 || delta[i][j][k] < xxx[i][i1] + delta[i1 + 1][j][0])
delta[i][j][k] = xxx[i][i1] + delta[i1 + 1][j][0];
} else {
if(delta[i1 + 1][j][2] != -1)
if(delta[i][j][k] == -1 || delta[i][j][k] < xxx[i][i1] + delta[i1 + 1][j][2])
delta[i][j][k] = xxx[i][i1] + delta[i1 + 1][j][2];
}
}
}
assert(delta[i][j][0] != -1);
}
printf("%d\n", delta[0][n - 1][0]);
}
return 0;
}
|
这个题目是百度之星第二度复赛时所用，难度之大从zju和pku中通过的人数就可以看出。一年多时间里，虽想独立解决它，但一直没有找到头绪，从网上搜索时，也得不到任何帮助。
在独立解决时，主要有两个问题，
1 我有一个想当认同的做法，即如果有球不足两个，则补足它对结果只有好处。
2 同色球被消去，要么是跟另处同色球一起，要么是自己独立消去，但两处同色球消时，里面的球怎么达到最大值
拿到标准代码后，证明第1点是错的，第2点也得到解决。
|
|
|
|
|