月度归档：2009年11月

采药

发表回复

问题描述
【描述 Description 】
　　辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
　　如果你是辰辰，你能完成这个任务吗？

【输入格式 Input Format 】
　　输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。 【输出格式 Output Format】 输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。 【样例输入 Sample Input】 70 3 71 100 69 1 1 2 【样例输出 Sample Output 】 3 【算法分析】 0/1背包 【代码】 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <stdio.h>
#include <string.h>
int main()
{
       int T, M, i, j;
 
       int time[102], value[102], a[102][1002];
 
       scanf("%d%d", &T, &M);
       for (i = 1; i <= M; i++)
              scanf("%d%d", &time[i], &value[i]);
       memset(a, 0, sizeof(int)*102*1002);
 
       for (i = 0; i <= M; i++)
              a[i][0] = 0;
 
       for (i = 0; i <= T; i++)
              a[0][i] = 0;
 
       for (i = 1; i <= M; i++)
       {
              for (j = 1; j <= T; j++)
              {
                     if ( j < time[i] )
                            a[i][j] = a[i - 1][j];
                     else
                     {
                            if (a[i - 1][j] > a[i - 1][j - time[i]] + value[i])
                                   a[i][j] = a[i - 1][j];
                            else
                                   a[i][j] = a[i - 1][j - time[i]] + value[i];
                     }
              }
       }
 
       printf("%d\n", a[M][T]);
       return 0;
}

mysql数据表之间数据相互传递的问题

发表回复

mysql数据表之间数据相互传递的问题

近日，某操作需要从一个表（表A）读取一些数据，然后直接写入另外一个表（表B）（相当于一个备份）
平时没啥问题，某天测试MM将一些乱七八糟的数据写入后就出问题了，这些数据从页面提交到表A时没有问题，
但是从表A读取后写入表B确实有问题，将错误的SQL输出，发现其中包含单引号等一些在SQL中特殊的字符，
此时，需要将这些数据过滤，简单处理：使用addslashes函数，

string addslashes ( string str )

返回字符串，该字符串为了数据库查询语句等的需要在某些字符前加上了反斜线。这些字符是单引号（’）、双引号（”）、反斜线（\）与 NUL（NULL 字符）。

在官方手册中也有提到使用这个函数作为数据写入数据库的一个示例

结论：写入数据表之前需要将所有的数据过滤，以防SQL注入或其它特殊字符的写入错误！

另外，addslashes对于防止SQL注入有一些用处，但是对于引号，可以用0xbf27来代替单引号，而addslashes只是将0xbf27修改为0xbf5c27，成为一个有效的多字节字符，其中的0xbf5c仍会被看作是单引号，所以addslashes此时无法防止SQL注入。此函数的用于单字节字符串的处理会比较有用。然而多字节字符还是用mysql_real_escape_string好些。

mysql 中子查询的3个问题

发表回复

【准备】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

CREATE TABLE `ticket_reply` (
  `reply_id` INT(11) NOT NULL AUTO_INCREMENT,
  `ticket_id` INT(11) NOT NULL,
  `reply_created` datetime DEFAULT NULL,
  `reply_content` text,
  PRIMARY KEY  (`reply_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
 
-- ----------------------------
-- Records 
-- ----------------------------
INSERT INTO `ticket_reply` VALUES ('1', '2', '2009-11-04 20:17:59', '11111');
INSERT INTO `ticket_reply` VALUES ('2', '2', '2009-11-04 20:22:09', '22222');
INSERT INTO `ticket_reply` VALUES ('3', '1', '2009-11-04 20:22:19', '33333');
INSERT INTO `ticket_reply` VALUES ('4', '3', '2009-11-04 20:22:28', '4444');
INSERT INTO `ticket_reply` VALUES ('5', '4', '2009-11-04 20:22:38', '5555');
INSERT INTO `ticket_reply` VALUES ('6', '1', '2009-11-04 20:22:49', '32');
INSERT INTO `ticket_reply` VALUES ('7', '1', '2009-11-04 20:23:18', '11');
INSERT INTO `ticket_reply` VALUES ('8', '1', '2009-11-04 20:23:26', '43');
INSERT INTO `ticket_reply` VALUES ('9', '2', '2009-11-04 20:23:41', '3');
INSERT INTO `ticket_reply` VALUES ('10', '3', '2009-11-04 20:23:50', '1');
INSERT INTO `ticket_reply` VALUES ('11', '3', '2009-11-04 20:24:02', '11');
INSERT INTO `ticket_reply` VALUES ('12', '4', '2009-11-04 20:24:12', 'f');
INSERT INTO `ticket_reply` VALUES ('13', '4', '2009-11-04 20:24:24', 'a');

【问题一】

在在In/all/any/sime等子查询里使用limit时会报错：
如下所示SQL
SELECT * FROM `ticket_reply` WHERE reply_id IN (SELECT reply_id * FROM `ticket_reply` LIMIT 3);
报错如下：
#1235 – This version of MySQL doesn’t yet support ‘LIMIT & IN/ALL/ANY/SOME subquery’

解决方案，添加一层查询，
SELECT * FROM `ticket_reply` WHERE reply_id IN (SELECT reply_id FROM (SELECT * FROM `ticket_reply` LIMIT 3) tb )
如果不加别名，则会显示
#1248 – Every derived table must have its own alias

【问题二】
mysql中分组后取各分组的最新的两组数据

1
2
3
4
5
6
7
8
9

SELECT s1. * 
FROM ticket_reply AS s1
WHERE (
SELECT COUNT( 1 ) 
FROM ticket_reply AS s2
WHERE s2.reply_created >= s1.reply_created
AND s2.ticket_id = s1.ticket_id
) <= 2
ORDER BY ticket_id, reply_created DESC

【问题三】
取每个帖子的最新回复

1
2
3
4
5
6
7
8

SELECT * 
FROM (
SELECT * 
FROM ticket_reply
ORDER BY reply_created DESC
) newtb
GROUP BY ticket_id
ORDER BY reply_created DESC