事实上我也不知道发生了什么,大概是几天前插了“小度 Wifi”的缘故。没有任何征兆地,Wifi 就用不了了。其实我也不知道原理,大概是某个驱动被刷掉了。下面是从网上找来的答案:
sudo apt-get install wicd-daemon
做个记录。
事实上我也不知道发生了什么,大概是几天前插了“小度 Wifi”的缘故。没有任何征兆地,Wifi 就用不了了。其实我也不知道原理,大概是某个驱动被刷掉了。下面是从网上找来的答案:
sudo apt-get install wicd-daemon
做个记录。
链接:Link 耗时:0.586s
昨晚做的太急了,没时间写总结,正好下午有空,补上。
这是一道典型的树形动态规划,不是很难,但十分坑语言。思路大致如下:
对于第 $i$ 个节点,用 $d(i)$ 表示其上诉所需的最小工人数。若 $i$ 为叶节点,则 $d(i)=1$;否则,遍历求出 $i$ 的子节点所对应的 $d$ 值,并由小到大排序,取出最小的几个相加,即为 $d(i)$。
很容易想到用递归来实现。但对于“子节点的 d 值的排序”实现起来却十分困难:因为事先不知道有多少个数。当然啦,如果是 C++ 组,用 vector
可以轻松搞定,可至于 P 党,实现起来却难上加难。思来想去,决定试试 Pascal 的动态数组。磕磕碰碰调了近 1 个小时,终于 AC 了。
//Accepted
var
tree: array [0..100000] of array of int64;
T: Integer;
f: array [0..100000] of int64;
i,l,n,x:longint;
function min(x,y: int64): int64;
begin
if x<y then exit(x) else exit(y);
end;
procedure sort(var arr: array of int64;l,r:longint); overload;
var
i,j:longint;
m,t: int64;
begin
i := l;
j := r;
m := arr[(l+r) >> 1];
repeat
while arr[i]<m do inc(i);
while arr[j]>m do dec(j);
if i<=j then
begin
t := arr[i];
arr[i] := arr[j];
arr[j] := t;
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(arr, i, r);
if l<j then sort(arr, l, j);
end;
procedure sort(var arr: array of int64); overload;
begin
sort(arr, low(arr), high(arr));
end;
function dp(x: longint): int64;
var
arr: array of int64;
l,i, num: longint;
begin
if f[x] <> 0 then
begin
dp := f[x];
exit;
end;
if length(tree[x]) = 0 then
begin
dp := 1;
f[x] := 1;
exit;
end;
l := length(tree[x]);
SetLength(arr, l);
for i := Low(tree[x]) to High(Tree[x]) do
arr[i] := dp(tree[x][i]);
Sort(arr);
num := (l*T-1) div 100+1;
for i := Low(arr) to num-1 do
f[x] := f[x] + arr[i];
dp := f[x];
end;
begin
assign(input, 'main.in');reset(input);
assign(output,'main.out');rewrite(output);
readln(n, T);
while n>0 do
begin
fillchar(f, sizeof(f), 0);
fillchar(tree, sizeof(tree), 0);
for i := 1 to n do
begin
read(x);
SetLength(tree[x], length(tree[x])+1);
tree[x][high(tree[x])] := i;
end;
readln;
dp(0);
writeln(f[0]);
readln(n, T);
end;
close(input); close(output);
end.
这里,再总结一下动态数组的用法。
a: array of [type];
SetLength(a, 10);
SetLength(a, Length(a)+1);
High(a)
, Low(a)
事实上,从 1.1 版本开始 FPC 就支持 Dynamic Arrays 了。所以在 NOIP 竞赛中我们大可放心使用。
这是一道区间型 DP,转移方程很简单,但在实现的过程中却遇见了很多坑,在此记录一下。链接:Link 耗时:0.368s
容易想到,前 $i$ 个数的划分情况可以由 $1,2,3,\ldots,i-1$ 的划分情况来决定。因此很容易得到状态转移方程:
$$d[i] = min(d[i], d[j]+1)$$
其中 $j = 0, 1, 2,\ldots,n-1$ 并且 $s[j+1, i]$ 为回文串,初始条件:$d[i] = i$。$d[i]$ 表示前 i 项的最小划分。这样一来状态转移的复杂度就为 $O(n^2)$。
但状态转移的判断呢?“回文串”是一个复杂的条件,判断一个串是否为回文串需要将该串至少遍历一遍。这样一来时间复杂度就上升为 $O(n^3)$ 了。而事实上在这种算法中有许多无谓的计算,因此我们可以先对字符串进行预处理:用 huiwen[i,j]
表示 $s[i,j]$ 是否为回文串(奇怪的名字。。。)。如此一来,时间复杂度就降为 $O(n^2)$ 了。
var
s: AnsiString;
n, _, i, j, l: integer;
huiwen: array [1..1000, 1..1000] of boolean; //s[i,j]是否为回文串
dp: array [0..1000] of integer; //一定从0开始,否则当整串为回文串时就考虑不到了。
function min(x,y: integer): integer;
begin
if x<y then exit(x) else exit(y);
end;
procedure process(i,j: integer); //对回文串进行预处理
var
mid: Integer;
x,y: integer;
begin
if j = i then
begin
huiwen[i,j] := true;
exit;
end;
mid := i + (j-i+1) shr 1;
x := i;
y := j;
while (x <= mid) and (s[x] = s[y]) do
begin
inc(x);
dec(y);
end;
huiwen[i, j] := x > mid;
end;
begin
//assign(input, 'main.in'); reset(input);
//assign(output, 'main.out'); rewrite(output);
readln(n);
for _ := 1 to n do
begin
readln(s);
l := length(s);
//Pre-process
fillchar(huiwen, sizeof(huiwen), 0);
for i := 1 to l do
for j := i to l do //一定是从i开始,这个错卡了我很久。
process(i, j);
//DP
for i := 1 to l do
begin
dp[i] := i;
for j := 0 to i-1 do
if huiwen[j+1, i] then
dp[i] := min(dp[i], dp[j]+1);
end;
write(dp[l]);
{if _ <>n then }writeln; //吐槽一下:一开始我还谨慎地加上这句以避免行末回车,没想到UVa居然报错了。。看来UVa的比较算法还有待改进啊。
end;
//close(input);close(output);
end.
链接:The Tower of Babylon 耗时:0.015s
这是刘汝佳的紫书中”DAG 中的动态规划”中的习题,我拿它用来熟悉 DAG 中的动态规划。
我们不妨进行逆向考虑:现堆上面的方块,然后考虑在下面进行叠加。这样子一来,影响决策的就只是最下面方块的尺寸了。
对于这种出现了”大套小”这样的二元关系的题,我们可以将其视为一个有向无环图:其中每个节点为一个状态,状态的转移是有固定的方向的(在此题中,状态转移为从小的方块到大的方块)。
但是这道题又不同于平常的 DAG 动态规划:若将边长视为状态的话,则要开一个巨大的数组,这是不可以接受的。因此,我们要换一种思维方式:只记录方块的序号和摆放的方式(如现将边长从小到大进行排序,然后用一个标志 k 表示当前是以第 k 小的边长作为高)。
至此,思路已经清晰了。用 $dp(i, k)$ 表示 “第 i 个方块以第 k 条边为高进行摆放” ,以下给出状态转移方程:
$$dp(i, k) = max\{dp(i, k), dp(j, k_2)\}$$
其中 $j,k_2$ 遍历所有顶面矩形比 $dp(i, k)$ 小的状态。
代码实现首次尝试了 Pascal 中的 object 类型,使其更加工整,但不可避免地损耗了一些性能。
type
Cube = object
a: array [1..3] of longint;
procedure init(x,y,z: longint);
function height(k: integer): longint;
function low(k: integer): longint;
function high(k: integer): longint;
end;
function max(x,y: longint): longint;
begin
if x>y then max := x else max := y;
end;
procedure swap(var x,y: longint);
var
t: longint;
begin
t := x;
x := y;
y := t;
end;
function Cube.height(k: integer): longint;
begin
height := self.a[k];
end;
function Cube.high(k: integer): longint;
begin
case k of
1: high := a[3];
2: high := a[3];
3: high := a[2];
end;
end;
function Cube.low(k: integer): longint;
begin
case k of
1: low := a[2];
2,3: low := a[1];
end;
end;
procedure Cube.init(x, y, z: longint);
begin
if x>y then swap(x,y);
if y>z then swap(y,z);
if x>y then swap(x,y);
a[1] := x;
a[2] := y;
a[3] := z;
end;
var
f: array [1..30, 1..3] of longint;
i,j,m,n,x,y,z: longint;
cnt: longint;
cubes: array [1..30] of Cube;
function dp(id, k: integer): longint;
var
l, h, hi: longint;
i, j: integer;
begin
if f[id, k] > 0 then
exit(f[id, k]);
l := cubes[id].low(k);
hi := cubes[id].height(k);
h := cubes[id].high(k);
f[id, k] := hi;
for i := 1 to n do
begin
//if i = id then continue; //此处在一开始时忘记考虑了立方体有无穷多个这一条件。
for j := 1 to 3 do
begin
if not ((cubes[i].low(j) < l) and (cubes[i].high(j) < h)) then
continue;
f[id, k] := max(f[id, k], dp(i, j)+hi);
end;
end;
dp := f[id, k];
end;
begin
assign(input, 'main.in');reset(input);
assign(output, 'main.out');rewrite(output);
read(n);
cnt := 0;
while n > 0 do
begin
inc(cnt);
for i := 1 to n do
begin
read(x,y,z);
cubes[i].init(x,y,z);
end;
fillchar(f, sizeof(f), 0);
m := 0;
for i := 1 to n do
for j := 1 to 3 do
m := max(m, dp(i, j));
writeln('Case ', cnt, ': maximum height = ', m);
read(n);
end;
close(input);close(output);
end.
记得 11 年的时候,觉得这道题爆难,根本无从下手。三年后再次回顾,终于 AC 了,就当是对表达式求值和动态规划的复习吧。
题目:Link
// Accepted.
#include <iostream>
#define Mod 10007
using namespace std;
typedef struct {
long long v0; //当前值为 0 的个数
long long v1; //当前值为 1 的个数
char ch; //当前字符
} vertex;
vertex f[100000];
void merge_sum(int p) {
int w0 = f[p-1].v0 * f[p].v0;
int w1 = f[p-1].v0*f[p].v1+f[p-1].v1*f[p].v0+f[p-1].v1*f[p].v1;
f[p-1].v0 = w0 % Mod;
f[p-1].v1 = w1 % Mod;
}
inline void merge_product(int p) //处理当前的值和前一个值取'*'的操作
{
int w0=f[p-1].v0*f[p].v0+f[p-1].v0*f[p].v1+f[p-1].v1*f[p].v0;
int w1=f[p-1].v1*f[p].v1;
f[p-1].v0=w0%Mod;
f[p-1].v1=w1%Mod;
}
int main()
{
int n;
cin>>n;
f[0].v0=f[0].v1=1;
while (n--)
{
now++; //新建一个空位读入新符号
cin>>f[now].ch;
f[now].v0=f[now].v1=1; //初始化当前符号的前面的值 (虽然')'除外,但也不影响)
if (f[now].ch=='+')
{
if (f[now-1].ch=='*') //处理'*'
{
now--;
merge_product(now);
f[now]=f[now+1];
}
if (f[now-1].ch=='+') //处理'+'
{
now--;
merge_sum(now);
f[now]=f[now+1];
}
}
if (f[now].ch=='*')
if (f[now-1].ch=='*') //处理'*'
{
now--;
merge_product(now);
f[now]=f[now+1];
}
if (f[now].ch==')') //处理')'(比较麻烦)
{
now--;
if (f[now].ch=='*')
{
merge_product(now);
now--;
}
if (f[now].ch=='+')
{
merge_sum(now);
now--;
}
now--;
f[now].v0=f[now+1].v0;
f[now].v1=f[now+1].v1;
if (f[now].ch=='*')
{
merge_product(now);
now--;
}
}
}
if (f[now].ch=='*') //处理完了以后,可能还有残留的'*'和'+'
{
merge_product(now);
now--;
}
if (f[now].ch=='+')
{
merge_sum(now);
now--;
}
cout<<f[0].v0;
return 0;
}
最近在做一个项目,其中有一段判断一个 Extended
浮点数是否为整数的代码。我用如下方式实现:
function IsInt(F: Extended): Boolean;
begin
result := Trunc(F)-F = 0; //整数部分等于自身
end;
测试了许多样例都过了,唯独这个没过:
IsInt(4.000000002*1000000000); //False
调试时发现: Trunc(F)
居然等于 4000000001
!开始以为是精度的问题,找了许多资料也没能解决。后来将 Extended
换成了 Double
,就通过了。百思不得其解中。
在 SAE 上进行应用开发时,常常需要导入数据库,这时候就需要用 MySQLDump 工具进行本地数据库导出。
首先 MySQLDump 最基本的语法是这样的 mysqldump <database_name>
,执行之后可以在控制台上看到 SQL 源码。但我第一次尝试将导出的源码上传至 SAE 时 SAE 却报错,原因是 SAE 的数据库管理不支持 LOCK 和 UNLOCK 语句。曾有一段时间,我是手动一行行删除 LOCK 语句。。30 多张表那叫一个蛋疼。。后来,我翻阅了 mysqlDump 的 help 文档,发现可以添加这么一个参数--ADD-LOCKS=FALSE
。几经尝试后发现果然没有 LOCK 语句了。在此记录下整句命令:
mysqldump --add-locks=FALSE -uroot -p <database_name> > example.sql