@RabbitHu 2017-02-24T21:33:02.000000Z 字数 44127 阅读 2521

胡小兔的OI日志

日记

查看最新

2016-12-16 线段覆盖

给定x轴上的N（0 < N < 100）条线段，每个线段由它的二个端点a_I和b_I确定，I=1,2,……N.这些坐标都是区间（－999，999）的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部（即除去端点的部分）。
输入第一行是一个整数N。接下来有N行，每行有二个空格隔开的整数，表示一条线段的二个端点的坐标。

输出第一行是一个整数表示最多剩下的线段数。

AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
struct span{
    int left,right;
};
bool cmp (const span a,const span b){
    return a.right==b.left ? a.left < b.left : a.right < b.right;
}
span s[105];
int n;
int main(){
    scanf("%d",&n);
    int a,b;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a,&b);
        s[i].left=min(a,b);
        s[i].right=max(a,b);
    }
    sort(s+1,s+n+1,cmp);
    int pos=s[1].right,ans=0,next=s[1].right;
    for(int i=2;i<=n;i++){
        if(s[i].left<next){
            ans++;
        }
        else{
            next=s[i].right;
        }
    }
    cout << n-ans << endl;
    return 0;
}

@ 之前错了几次……是因为……不会。现在会啦。

2016-12-17 线段树练习

一行N个方格，开始每个格子里都有一个整数。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1 ≤ N < 100000, 提问和修改的总数m < 10000条。
输入文件第一行为一个整数N，接下来是n行n个整数，表示格子中原来的整数。接下一个正整数m，再接下来有m行，表示m个询问，第一个整数表示询问代号，询问代号1表示增加，后面的两个数x和A表示给位置X上的数值增加A，询问代号2表示区间求和，后面两个整数表示a和b，表示要求[a,b]之间的区间和。
输出共m行，每个整数。

AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
struct ls{
    int l,r,data;
};
ls tree[500005];
int ori[100005];
void build_tree(int l,int r,int k){
    tree[k].l = l;
    tree[k].r = r;
    if(l==r){
        tree[k].data=ori[l];
        return;
    }
    int mid=(l + r) / 2;
    build_tree(l, mid,2 * k);
    build_tree(mid + 1, r, 2 * k + 1);
    tree[k].data = tree[2 * k].data + tree[2 * k + 1].data;
}
int tree_query(int l,int r,int k){
    if(l == tree[k].l && r == tree[k].r){
        return tree[k].data;
    }
    int mid=(tree[k].l + tree[k].r)/2;
    if(r <= mid) return tree_query(l, r, 2 * k);
    if(l > mid) return tree_query(l, r, 2 * k + 1);
    return tree_query(l, mid, 2*k) + tree_query(mid + 1, r, 2 * k + 1);
}
void single_change(int k, int n,int change){
    if(tree[k].l < tree[k].r){
        int mid = (tree[k].l + tree[k].r)/2;
        if(n <= mid) single_change(2 * k, n, change);
        else single_change(2 * k + 1, n, change); 
    }
    if(tree[k].l == tree[k].r){
        tree[k].data += change;
        return;
    }
    else{
        tree[k].data = tree[2 * k].data + tree[2 * k + 1].data;
        return;
    }
}
int main(){
    int n, left, right, m;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%d",&ori[i]);
    }
    build_tree(1, n, 1);
    scanf("%d",&m);
    for(int i = 1;i <= m;i++){
        int op, a, b;
        scanf("%d%d%d", &op, &a, &b);
        if(op==1) single_change(1, a, b);
        else printf("%d\n", tree_query(a, b, 1));
    }
    return 0;
}
// 妈呀这么长。但是一次AC啦

2016-12-18 垂直直方图

输入4行全部由大写字母组成的文本，输出一个垂直直方图，给出每个字符出现的次数。注意：只用输出字符的出现次数，不用输出空白字符，数字或者标点符号的输出次数。
输入包括4行由大写字母组成的文本，每行上字符的数目不超过80个。
输出包括若干行。其中最后一行给出26个大写英文字母，这些字母之间用一个空格隔开。前面的几行包括空格和星号，每个字母出现几次，就在这个字母的上方输出一个星号。注意：输出的第一行不能是空行。

AC代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int a[27];
int main(){
    char c;
    while(cin >> c){
        if(isalpha(c)){
            a[c - 'A']++;
        }
    }
    int maxn = 0 ;
    for(int i = 0; i < 26 ; i++){
        maxn = max(maxn, a[i]);
    }
    for(int i = maxn; i > 0; i--){
        for(int j = 0; j < 26; j++){
            if(a[j] >= i) printf("* ");
            else printf("  ");
        }
        printf("\n");
    }
    for(int i = 'A' ; i <= 'Z'; i++){
        printf("%c ",i);
    }
    printf("\n");
    return 0;
}
//昨天调了一晚上bug未果，自信心直线下滑，做道水题，没啥可说的

2016-12-18 乌龟棋

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘是一行N个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一的起点，第N格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中M张爬行卡片，分成4种不同的类型（M张卡片中不一定包含所有4种类型的卡片，见样例），每种类型的卡片上分别标有1、2、3、4四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。
游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？
输入文件的每行中两个数之间用一个空格隔开。
第1行2个正整数N和M，分别表示棋盘格子数和爬行卡片数。
第2行N个非负整数，a1a2……aN，其中ai表示棋盘第i个格子上的分数。
第3行M个整数，b1b2……bM，表示M张爬行卡片上的数字。
输入数据保证到达终点时刚好用光M张爬行卡片。
输出只有1行，1个整数，表示小明最多能得到的分数。

AC代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int dp[42][42][42][42], map[360], chess[6], N, M;
void in(){
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= N; i++){
        scanf("%d", &map[i]);
    }
    for(int i = 1; i <= M; i++){
        int t;
        scanf("%d", &t);
        chess[t]++;
    }
}
void dping(){
    //dp[0][0][0][0]=map[1];
    for(int one = 0; one <= chess[1]; one++)
        for(int two = 0; two <= chess[2]; two++)
            for(int three = 0; three <= chess[3]; three++)
                for(int four = 0; four <= chess[4]; four++){
                    int maxn = 0, now = map[one + two*2 + three*3 + four*4 + 1];
                    if(one >= 1) maxn = max(maxn, now + dp[one-1][two][three][four]);
                    if(two >= 1) maxn = max(maxn, now + dp[one][two-1][three][four]);
                    if(three >= 1) maxn = max(maxn, now + dp[one][two][three-1][four]);
                    if(four >= 1) maxn = max(maxn, now + dp[one][two][three][four-1]);
                    dp[one][two][three][four] = maxn;
                }
}
int main(){
    in();
    dping();
    printf("%d",dp[chess[1]][chess[2]][chess[3]][chess[4]] + map[1]);
    return 0;
}

@ 第一次没AC 是因为复制粘贴的时候忘把一个3改成4了 TAT
注：感觉DP我可能还理解得不够好，要加油了

2017-01-19 公共子序列

描述
我们称序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列当且仅当存在严格上升的序列< i1, i2, ..., ik >，使得对j = 1, 2, ... ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b, c >的子序列。
现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。
输入
输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串之间由若干个空格隔开。
输出
对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
char a[205], b[205];
int dp[205][205];
int main(){
    while(scanf("%s%s", a+1, b+1) != EOF){
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= strlen(a+1); i++){
            for(int j = 1; j <= strlen(b+1); j++){
                if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        printf("%d\n", dp[strlen(a+1)][strlen(b+1)]);
    }
    return 0;
}

@ 我……一开始把dp数组定义成了char…………WA QAQ

2017-01-19 摘花生

描述
Hello Kitty 想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。Hello Kitty只能向东或向南走，不能向西或向北走。问Hello Kitty 最多能够摘到多少颗花生。
输入
第一行是一个整数T，代表一共有多少组数据。1<=T <= 100
接下来是T组数据。
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C ( 1<= R,C <=100)
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有 C 个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目 M ( 0<= M <= 1000)。
输出
对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。

思路：

一道简单的动态规划题~

自左上至右下遍历每棵花生，我们需要求出到达这棵花生(i,j)的路上（包括这棵）能摘到的最大的花生数，存储在数组dp[i][j]中，这样最后右下角的格子的dp值就是能达到的最大值。

如何求出到达这棵花生(i,j)的路上（包括这棵）能摘到的最大的花生数呢？

我们走到一棵花生处，要么是从左边走过来的，要么是从上面走过来的。那么左边花生的dp值和右边花生的dp值中，最大的那个，加上这棵花生上的花生数量，就是这棵花生的dp值。

即：

$dp[i][j] = max(dp[i-1][j], dp[i][j-1])+map[i][j]$
其中map保存的是每棵花生自己的花生数量。

要注意， i-1 和 j-1 都有可能越界，需要加以判断。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int dp[105][105], map[105][105], cases, r, c;
int main(){
    scanf("%d", &cases);
    while(cases--){
        memset(dp, 0, sizeof(dp));
        //初始化 
        scanf("%d%d", &r, &c);
        for(int i = 1; i <= r; i++){
            for(int j = 1; j <= c; j++){
                scanf("%d", &map[i][j]);
            }
        }
        dp[1][1] = map[1][1];
        //输入 
        for(int i = 1; i <= r; i++){
            for(int j = 1; j <= c; j++){
                if(i - 1) dp[i][j] = max(dp[i][j], dp[i-1][j] + map[i][j]);
                if(j - 1) dp[i][j] = max(dp[i][j], dp[i][j-1] + map[i][j]);
            }
        }
        //DP
        printf("%d\n", dp[r][c]);
    }
    return 0;
}

2017-01-20 有趣的跳跃

描述
一个长度为n（n>0）的序列中存在“有趣的跳跃”当前仅当相邻元素的差的绝对值经过排序后正好是从1到(n-1)。例如，1 4 2 3存在“有趣的跳跃”，因为差的绝对值分别为3,2,1。当然，任何只包含单个元素的序列一定存在“有趣的跳跃”。你需要写一个程序判定给定序列是否存在“有趣的跳跃”。
输入
一行，第一个数是n（0 < n < 3000），为序列长度，接下来有n个整数，依次为序列中各元素，各元素的绝对值均不超过1,000,000,000。
输出
一行，若该序列存在“有趣的跳跃”，输出"Jolly"，否则输出"Not jolly"。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int a[3010], n, last = 0, temp, ok = 1;
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &temp);
        a[i] = abs(temp - last);
        last = temp;
    }
    //for(int i = 2; i <= n; i++) printf("%d ", a[i]);
    //printf("\n");
    sort(a + 2, a + n + 1);
    //for(int i = 2; i <= n; i++) printf("%d ", a[i]);
    last = 0;
    for(int i = 2; i <= n; i++){
        if(a[i] - last != 1){
            ok = 0;
            printf("Not jolly\n");
            break;
        }
        last = a[i];
    }
    if(ok) printf("Jolly\n");
    return 0;
}

@ 啊啊啊啊啊啊忘删注释……………………………………

2017-01-20 滑雪

描述
Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
输入
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
输出
输出最长区域的长度。

思路：

这道题可以用记忆化搜索，即用一个数组（就叫dp吧，我起名废）记录每个点可以滑的最大距离，这样下次计算临近点，需要用到这个点的时候，就可以直接使用已经记录的值了，而不用重新计算。

是不是非常的妙~啊？
——金企鹅学长

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int map[105][105], dp[105][105], r, c, maxn = 0;
void in(){
    scanf("%d %d", &r, &c);
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            scanf("%d", &map[i][j]);
        }
    }
}
int islegal(int m, int n, int x, int y){
    return x > 0 && y > 0 && x <= r && y <= c && map[m][n] > map[x][y];
}
int ski(int x, int y){
    if(dp[x][y] > 0) return dp[x][y];
    int a = islegal(x, y, x - 1, y)? ski(x - 1, y) + 1 : 1;
    int b = islegal(x, y, x + 1, y)? ski(x + 1, y) + 1 : 1;
    int c = islegal(x, y, x, y - 1)? ski(x, y - 1) + 1 : 1;
    int d = islegal(x, y, x, y + 1)? ski(x, y + 1) + 1 : 1;
    dp[x][y] = max(max(a, b), max(c, d));
    return dp[x][y];
}
int main(){
    in();
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            maxn = max(maxn, ski(i, j));
            //printf("(%d, %d) = %d\n", i, j, ski(i, j));
        }
    }
    printf("%d\n", maxn);
    return 0;
}

@ 复制一时爽，提交火葬场

2017-01-21 手写一个堆

AC代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
// I'm making a heap!
int hp[100005], num; 
// hp == the heap, num == the number of members in the heap
/*
     [n]
    /   \
 [2*n] [2*n+1]
*/
void checkup(int i){
    while(i >= 1 && hp[i/2] > hp[i]){
        swap(hp[i/2], hp[i]);
        //if father(i/2) is larger than son(i), then swap
        i /= 2;
        //now the member is moved to the father's position
    }
}
void checkdown(int i){
    while(i <= num){
        int j = (i*2+1 <= num && hp[i*2+1] < hp[i*2]) ? i*2+1 : i*2;
        //choose the smaller (and legal, of course) son to use
        if(hp[i] > hp[j]){ 
            //if father(i) is larger than son(j), then swap
            swap(hp[j], hp[i]);
            i = j;
        }
        else break;
    }
}
int push(int x){
    hp[++num] = x;
    checkup(num);
}
void pop(){
    hp[1] = hp[num--];
    checkdown(1);
}
int top(){
    return hp[1];
}
int main(){
    // nothing...
    return 0;
}

@ 大于号打成小于号x_x

2017-01-21 家族

题目描述
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
输入描述
第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有亲戚关系。接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。
输出描述
P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

思路：

这是一道传说中的 并查集 的裸题。

这个并查集是用f[i]数组存储i号人所属家庭的……代表元，就是用来代表一个家族的那个人。如果两个人的f相同，那么这俩人就是一家子。

一个比较重要的东西是这个find()函数。

一开始最简单的find()函数是这样的:

int find(){
    if(f[x] == x) return x;
    else return find(f[x]);
}

此时假设我们要查找的是下图中的7对应的f[7]：

[2]
 | \
[3] [4] - [5]
 |
[6]
 |
[7]

查找[7]需要走过[7]→[6]→[3]→[2], 然后再查找[6]时仍需要走过[6]→[3]→[2]。

但是通过一个“压缩路径”的find()函数，我们走完[7]→[6]→[3]→[2]就可以把图改造成：

    [ 2 ]
  /  | |  \ 
[3] [6][7] [4]
             \
             [5]

这样再查找[6]时，f[6]已经被修改成了2，可以一步到位。

是不是非常的妙~啊？
——金企鹅学长

AC代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int f[5005], n, m, p; //f[i] is i's family's root
int find(int x){
    if(x != f[x]){
        f[x] = find(f[x]);
    }
    return f[x];
}
int main(){
    scanf("%d%d%d", &n, &m, &p);
    for(int i = 1; i <= n; i++){
        f[i] = i;
    }
    for(int i = 1; i <= m; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        // a & b : We belong to the same family! :)
        int fa = find(a), fb = find(b);
        if(fa == fb) continue;
        else{
            f[fa] = fb;
        }
    }
    for(int i = 1; i <= p; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        int fa = find(a), fb = find(b);
        if(fa == fb) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}
//一次AC的畅快

2017-01-22 最小生成树

题目描述
农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了使花费最少，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000
输入描述
第一行：农场的个数，N（3<=N<=100）。
接下来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们每行限制在80个字符以内，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为线路从第i个农场到它本身的距离在本题中没有意义。
输出描述
只有一个输出，是连接到每个农场的光纤的最小长度和。

思路：

这道题是最小生成树，用到Kruskal(这玩意怎么念啊……）算法。

Kruskal算法的步骤：

将每条边编号并按长度（即权值、成本什么的）从小到大排序。
按这个从小到大的顺序遍历每条边，如果一条边r加入后不成环，那么加入r一定是最好哒。（为什么？反证法：如果加入r后不是最优解，那么不加入这条边可以得到一个最优解。则在这个最优解中再加入r后会得到一个环，那么这个环中至少有一条边r'比r长。再删除r'后，新树一定会更好。所以最后还是加入r最好。）

这道题用到了特别的排序方法，它叫做间接排序。它用一个数组r[i]表示第i小的边的编号，将编号根据对应的权值w[r[i]]来排序。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int w[10005], u[10005], v[10005], r[10005], p[105], n, num = 0, ans = 0;
int cmp(const int i, const int j){
    return w[i] < w[j];
}
int find(int x){
    return p[x] == x ? x : p[x] = find(p[x]);
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%d", &w[num]);
            u[num] = i;
            v[num] = j;
            num++;
        }
    }
    for(int i = 0; i < n*n ; i++){
        r[i] = i;
    }
    for(int i = 0; i < n; i++){
        p[i] = i;
    }
    sort(r, r + n*n, cmp);
    for(int i = 0; i < n*n; i++){
        int e = r[i];
        int x = find(u[e]);
        int y = find(v[e]);
        if(x != y) {
            ans += w[e];
            p[x] = y;
        }
    }
    printf("%d\n", ans);
    return 0;
}
//AC!

2017-01-22 糖果

描述
由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。在这一天，Dzx可以从糖果公司的N件产品中任意选择若干件带回家享用。糖果公司的N件产品每件都包含数量不同的糖果。Dzx希望他选择的产品包含的糖果总数是K的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。当然，在满足这一条件的基础上，糖果总数越多越好。Dzx最多能带走多少糖果呢？
注意：Dzx只能将糖果公司的产品整件带走。
输入
第一行包含两个整数N(1<=N<=100)和K(1<=K<=100)
以下N行每行1个整数，表示糖果公司该件产品中包含的糖果数目，不超过1000000
输出
符合要求的最多能达到的糖果总数，如果不能达到K的倍数这一要求，输出0

思路：

其实这题似乎很水……然而……唉……

有n包糖果，对于每包——就像01背包一样——有两种可能，选和不选。用数组dp[i][j]表示从1~i号产品中选择，余数为j时，能获取的最大糖果数。最终答案表示为dp[n][0](1~n号产品即所有产品，k的倍数即余数为0）。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n, k, dp[105][105], tp;
int main(){
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++){
        scanf("%d", &tp);
        dp[i][tp % k] = tp;
        for(int j = 0; j < k; j++){
            if(dp[i-1][j]) dp[i][(j + tp)%k] = dp[i-1][j] + tp;
        }
        for(int j = 0; j < k; j++){
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
    }
    printf("%d\n",dp[n][0]);
    return 0;
}

@ 也不知道怎么想的……余数枚举居然从1开始……WA*2……

2017-01-23 多源最短路

题目描述
已知n个点(n<=100)，给你n*n的方阵，a[i,j]表示从第i个点到第j个点的直接距离。现在有Q个询问，每个询问两个正整数，a和b，让你求a到b之间的最短路程。
满足a[i,j]=a[j,i]。
输入描述
第一行一个正整数n，接下来n行每行n个正整数，满足a[i,i]=0,再一行一个Q，接下来Q行，每行两个正整数a和b。
输出描述
一共Q行，每行一个整数。

思路：

Floyd的非常简单非常简单的一个例子。也是DP的非常简单非常简单的例子。

主体就中间那四行代码。第一行枚举“借路”的点k，第二行第三行枚举起始点i、j，第四行dp，比较借路和不借路的路径长度，取最小的。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define INF 2000000000
int d[105][105], n, q;
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &d[i][j]);
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    scanf("%d", &q);
    while(q--){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", d[a][b]);
    }
    return 0;
}
//一次AC！

2017-01-23 手写快排

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
void mysort(int a[], int st, int ed){
    int t;
    if(st >= ed) return;
    int k = st, i = st, j = ed;
    while(i < j){
        while(i < j && a[j] >= a[k]) j--;
        swap(a[j], a[k]);
        k = j;
        while(i < j && a[i] <= a[k]) i++;
        swap(a[i], a[k]);
        k = i;
    }
    mysort(a, st, k-1);
    mysort(a, k+1, ed);
}
int main(){
    int a[100], n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    mysort(a, 0, n-1);
    for(int i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}

2017-01-24 谁是你的潜在朋友

今天gg组织了竞赛小组ACM……刷个水题增强信心……

描述
“臭味相投”——这是我们描述朋友时喜欢用的词汇。两个人是朋友通常意味着他们存在着许多共同的兴趣。然而作为一个宅男，你发现自己与他人相互了解的机会并不太多。幸运的是，你意外得到了一份北大图书馆的图书借阅记录，于是你挑灯熬夜地编程，想从中发现潜在的朋友。
首先你对借阅记录进行了一番整理，把N个读者依次编号为1,2,…,N，把M本书依次编号为1,2,…,M。同时，按照“臭味相投”的原则，和你喜欢读同一本书的人，就是你的潜在朋友。你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。
输入
第一行两个整数N,M，2 <= N ，M<= 200。接下来有N行，第i(i = 1,2,…,N)行每一行有一个数，表示读者i-1最喜欢的图书的编号P(1<=P<=M)
输出
包括N行，每行一个数，第i行的数表示读者i有几个潜在朋友。如果i和任何人都没有共同喜欢的书，则输出“BeiJu”（即悲剧，^ ^）

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int book[205], guy[205];
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%d", &guy[i]);
        book[guy[i]]++;
    }
    for(int i = 0; i < n; i++){
        int ans = book[guy[i]] - 1;
        if(ans) printf("%d\n", ans);
        else printf("BeiJu\n"); 
    }
    return 0;
}

@ 当年啊……Naive……数组没初始化……

2017-01-24 和数

描述
给定一个正整数序列，判断其中有多少个数，等于数列中其他两个数的和。比如，对于数列1 2 3 4, 这个问题的答案就是2, 因为3 = 2 + 1, 4 = 1 + 3。
输入
共两行，第一行是数列中数的个数n ( 1 <= n <= 100)，第二行是由n个不大于10000的正整数组成的数列，相邻两个整数之间用单个空格隔开。
输出
一个整数，即数列中等于其他两个数之和的数的个数。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n, a[105], ans = 0, vis[105];
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a+n);
    for(int i = 2; i < n; i++){
        for(int m = 0; m < i - 1; m++){
            for(int b = m + 1; b < i; b++){
                if(a[i] == a[m] + a[b] && !vis[i]){
                    ans++;
                    vis[i] = 1;
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

@ 是……和数的个数……不是组数……所以5=1+4和5=2+3是一个……哎

2017-01-31 高精度阶乘

描述
求10000以内n的阶乘。
输入
只有一行输入，整数n（0<=n<=10000）。
输出
一行，即n!的值。

AC代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int a[100000]={0, 1}, n, len = 1;
//a存储结果,a[1]表示个位，以此类推，n是输入的数，len是结果的长度（位数）
int main(){
    scanf("%d", &n);
    for(int i = 2; i <= n; i++){
        //枚举 2~n 的每个乘数
        int j = 1, add = 0;
        for(; j <= len; j++){
            //用已经得到的结果的每一位与i相乘，j表示位数，add表示进位的数
            a[j] = a[j] * i + add;
            add = a[j] / 10;
            a[j] %= 10;
        }
        while(add > 0){
            //每一位都乘完了以后，进位还剩
            a[j] = add % 10;
            add /= 10;
            j++;
        }
        len = j - 1;  //保存结果的长度（位数）
    }
    //输出
    for(int i = len; i >= 1; i--){ //从最高位开始输出
        printf("%d", a[i]);
    }
    printf("\n");
    return 0;
}

@ 输出的时候 i-- 习惯性打成 i++ ，所幸及时发现……

2017-02-01 高精度加减乘模

AC代码：

加法：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAX 250
char sa[MAX], sb[MAX];
int a[MAX], b[MAX], c[MAX];
int main(){
    scanf("%s%s", sa, sb);
    int la = strlen(sa), lb = strlen(sb);
    for(int i = la- 1, j = 0; i >= 0; i--)
        a[j++] = sa[i] - '0';
    for(int i = lb - 1, j = 0; i >= 0; i--)
        b[j++] = sb[i] - '0';
    for(int i = 0; i < max(la, lb); i++){
        c[i] += a[i] + b[i];
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    int p = max(la, lb) + 1;
    while(c[p] == 0) p--;
    for(int i = p; i >= 0; i--)
        printf("%d", c[i]);
    printf("\n");
    return 0;
}

减法：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAX 250
char sa[MAX], sb[MAX], st[MAX];
int a[MAX], b[MAX], c[MAX];
int main(){
    scanf("%s%s", sa, sb);
    int la = strlen(sa), lb = strlen(sb);
    int ok = 1;
    if(la < lb || (la == lb) && strcmp(sa, sb) < 0){
        for(int i = 0; i < 250; i++) swap(sa[i], sb[i]);
        swap(la, lb);
        printf("-");
    }
    for(int i = la- 1, j = 0; i >= 0; i--)
        a[j++] = sa[i] - '0';
    for(int i = lb - 1, j = 0; i >= 0; i--)
        b[j++] = sb[i] - '0';
    for(int i = 0; i < la; i++){
        a[i] -= b[i];
        if(a[i] < 0){
            a[i] += 10;
            a[i+1]--;
        }
    }
    int p = la;
    while(a[p] == 0 && p) p--;
    for(int i = p; i >= 0; i--)
        printf("%d", a[i]);
    printf("\n");
    return 0;
}

乘法：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAX 505
char sa[MAX], sb[MAX];
int a[MAX], b[MAX], c[MAX];
int main(){
    scanf("%s%s", sa, sb);
    int la = strlen(sa), lb = strlen(sb);
    for(int i = la- 1, j = 0; i >= 0; i--)
        a[j++] = sa[i] - '0';
    for(int i = lb - 1, j = 0; i >= 0; i--)
        b[j++] = sb[i] - '0';
    for(int i = 0; i < la; i++){
        for(int j = 0; j < lb; j++){
            c[i + j] += a[i] * b[j];
            c[i + j + 1] += c[i + j] / 10;
            c[i + j] %= 10;
        }
    }
    int p = la + lb -1;
    if(c[p] == 0) p--;
    for(int i = p; i >= 0; i--)
        printf("%d", c[i]);
    printf("\n");
    return 0;
}

膜法取模：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
//precise_mod
char a[200];
int n; 
int main(){
    scanf("%s%d", a, &n);
    int len = strlen(a);
    int ans = 0;
    for(int i = 0; i < len; i++){
        ans = (int)(((long long)ans * 10 + a[i] - '0') % n);
    }
    printf("%d\n", ans);
    return 0;
}

2017-02-01 扩展GCD

AC代码：

void gcd(int a, int b, int & d, int & x, int & y){
    if(!b){
        d = a;
        x = 1;
        y = 0;
    }
    else{
        gcd(b, a%b, d, y, x);
        y -= x*(a/b);
    }
}

2017-02-01 麻烦的字符串

麻烦的字符串
羊神总是想方设法为难自己，今天他给自己出了几个字符串，并且这个字符串中有数字字母和加减乘三个运算符号中的一个（例如1as2sdf3dfg4dfg5asd6*45asdf45sd8）且‘+ - *’只会出现一次。看着这么复杂的式子羊神并不满足，他想给自己出道题！第一题：输入一个数字k 并使字符串中所有字母都”变大”k个，然后输出改变后的式子（例如字符串abcz输入k为3 那么结果就是defc）；第二题羊神把式子里的字母全都去掉并计算该式子的结果。羊神出完题特别高兴，于是就把题目给了你！
【输入】
2 行。
第一行是一个字符串
（不包含空格，均为小写字母，去掉字母后算式合法，数字没有前导零）。
第二行是一个数字k。
【输出】
2 行
第一行是改变后的字符串。
第二行是去掉字母后式子的结果
【样例】
    【输入】
    abc123*456xyz
    1
    【输出】
    bcd123*456yza
    56088
【数据】
20%的数据无字母，字符串长度小于10
40%的数据字符串长度小于30
100%的数据字符串长度小于255，k<255

AC代码:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cctype>
using namespace std;
char sa[300], sb[300], c, op;
int a[300], b[300], ans[1000], d[300], e[300], k, la = 0, lb = 0;
int main(){
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);
    for(int i = 0; ; i++){
        scanf("%c", &c);
        if(c == '+' || c == '-' || c == '*'){
            op = c;
            break;
        }
        sa[i] = c;
        la++;
    }
    for(int i = 0; ; i++){
        scanf("%c", &c);
        if(c == '\n') break;
        sb[i] = c;
        lb++;
    }
    sa[la] = sb[lb] = '\0';
    scanf("%d", &k);
    for(int i = 0; i < la; i++){
        if(isalpha(sa[i])){
            sa[i] += k % 26 - 26;
            while(sa[i] < 'a'){
                sa[i] += 26;
            }
        }
    }
    for(int i = 0; i < lb; i++){
        if(isalpha(sb[i])){
            sb[i] += k % 26 - 26;
            while(sb[i] < 'a') {
                sb[i] += 26;
            }
        }
    }
    printf("%s%c%s\n", sa, op, sb);
    int m = 0, n = 0;
    for(int i = 0; i < la; i++)
        if(isdigit(sa[i])){
            d[m] = sa[i] - '0';
            m++;    
        }
    for(int i = 0; i < lb; i++)
        if(isdigit(sb[i])){
            e[n] = sb[i] - '0';
            n++;    
        }
    for(int i = 0; i < m; i++) 
        a[i] = d[m - i - 1];
    for(int i = 0; i < n; i++) 
        b[i] = e[n - i - 1];
    if(op == '+')
        for(int i = 0; i < max(m, n); i++){
            ans[i] += a[i] + b[i];
            ans[i + 1] += ans[i] / 10;
            ans[i] %= 10;
        }
    else if(op == '-'){
        int ok = 1;
        if(m < n) ok = 0;
        if(m == n)
            for(int i = m - 1; i >= 0; i--)
                if(a[i] < b[i]){
                    ok = 0;
                    break;
                }
        if(!ok){
            for(int i = 0; i < max(m, n); i++) swap(a[i], b[i]);
            swap(m, n);
            printf("-");
        }
        for(int i = 0; i < m; i++){
            ans[i] = a[i];
        }
        for(int i = 0; i < m; i++){
            ans[i] -= b[i];
            if(ans[i] < 0){
                ans[i] += 10;
                ans[i+1]--;
            }
        }
    }
    else{
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                ans[i + j] += a[i] * b[j];
                ans[i + j + 1] += ans[i + j] / 10;
                ans[i + j] %= 10;
            }
        }
    }
    int p = 599;
    while(ans[p] == 0 && p) p--;
    for(int i = p; i >= 0; i--) printf("%d", ans[i]);
    printf("\n");
    return 0;
}

@ 没有注意k的取值范围
@ 复制乘法部分的时候有一处……打错了……

2017-02-01 调皮的水

水是很调皮的，今天许多的水分子(H-O-H)聚集在一起，想要构成一个水立方(就是类似于正方形)！但是水分子还特别奇特= =，O 与O 不能直接靠近，H 与H也不能直接靠近。而且水立方最外围的氢原子必须在左右两侧，不允许在顶部和底部凸出。
但是水分子又不想就这样暴露出自己，就把自己的状态
变成数字：
横着的 H-O-H 是1，
          H
           |
竖着的 O 是-1，
           |
          H
其它的都是0。
现在告诉你一个数字化的水立方，请你写出他原来的样子。
【输入】
第一行：正整数n(n<=11)
接下来n 行，每行n 个数字。
保证：每行每列的数字和为1，每个行和每个列中的非零
项不能连续出现，且输入数据能构成唯一的正常的水立方。
【输出】
你不仅要输入水立方的样子，还要在外围打出“*”作为
边框。
【样例】
【输入】
4
0 1 0 0
1 -1 0 1
0 0 1 0
0 1 0 0
【输出】

*******************
*H-O H-O-H O-H O-H*
*  |       |   |  *
*  H   H   H   H  *
*      |          *
*H-O-H O H-O H-O-H*
*      |   |      *
*  H   H   H   H  *
*  |           |  *
*H-O H-O H-O-H O-H*
*      |          *
*  H   H   H   H  *
*  |       |   |  *
*H-O H-O-H O-H O-H*
*******************

AC代码：

#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
//I have to write the notes in my broken English
//otherwise they'll turn to messy codes for some reasons
char map[50][50];//map is what to print at last
int n, done[50][50], t; 
//if done[i][j]==2 then the 'O' at map[i][j] is connected to two 'H'
//t is short for temporary
void init(){
    scanf("%d", &n);
    memset(map, ' ', sizeof(map));
    for(int i = 0; i <= 4*n+2; i++){
        map[0][i] = '*';
    }
    for(int i = 0; i <= 4*n+2; i++){
        map[4*n - 2][i] = '*';
    }
    for(int i = 1; i <= 4*n - 3; i++){
        map[i][0] = map[i][4*n+2] = '*';
        if(i % 4 == 1){
            map[i][2] = map[i][4*n] = '-';
            done[i][1] = done[i][3] = done[i][4*n-1] = done[i][4*n+1] = 1;
            for(int j = 1; j <= 4*n + 1; j += 4){
                map[i][j] = 'H';
            }
            for(int j = 3; j <= 4*n + 1; j += 4){
                map[i][j] = 'O';
            }
        }
        if(i%4 == 3){
            for(int j = 3; j <= 4*n + 1; j += 4){
                map[i][j] = 'H';
            }
        }
    }
}
void in(){
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++){
            scanf("%d", &t);
            if(t == 1){
                map[4 * i + 1][4 * j + 2] = map[4 * i + 1][4 * j + 4] = '-';
                done[4 * i + 1][4 * j + 3] = 2;
                done[4 * i + 1][4 * j + 1] = done[4 * i + 1][4 * j + 5] = 1;
            }
            else if(t == -1){
                map[4 * i][4 * j + 3] = map[4 * i + 2][4 * j + 3] = '|';
                done[4 * i + 1][4 * j + 3] = 2;
                done[4 * i - 1][4 * j + 3] = done[4 * i + 3][4 * j + 3] = 1;
            }
        }
}
void guess(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(done[4 * i + 1][4 * j + 3]<2){
                int left = 0;
                if(!done[4 * i - 1][4 * j + 3]){
                    map[4 * i][4 * j + 3] = '|';
                    done[4 * i - 1][4 * j + 3]++;
                    if(++done[4 * i + 1][4 * j + 3] >= 2)continue;
                }
                if(!done[4 * i + 1][4 * j + 1]){
                    map[4 * i + 1][4 * j + 2] = '-';
                    done[4 * i + 1][4 * j + 1]++;
                    left = 1;
                    if(++done[4 * i + 1][4 * j + 3] >= 2)continue;
                }
                if(!done[4 * i + 1][4 * j + 5]&& !left){
                    map[4 * i + 1][4 * j + 4] = '-';
                    done[4 * i + 1][4 * j + 5]++;
                    if(++done[4 * i + 1][4 * j + 3] >= 2)continue;
                }
                if(!done[4 * i + 3][4 * j + 3]){
                    done[4 * i + 3][4 * j + 3]++;
                    map[4 * i + 2][4 * j + 3] = '|';
                }
            }
        }
    }
}
void out(){
    for(int i = 0; i <= 4*n - 2; i++){
        for(int j = 0; j <= 4*n + 2; j++)
            printf("%c", map[i][j]);
        printf("\n");
    }
}
int main(){
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
    init();
    in();
    guess();
    out();
    return 0;
}

@ 没有意识到‘0’代表不是竖的也不是横的，所以不能有相对而立的俩键……

2017-02-02 一元三次方程

(pdf忘拷回来了，根据记忆编一个题目）
有一元三次方程 $ax^3+bx^2+cx+d=0$ ，已知它有三个实根，均在[-100,100]区间内，且每两个实根的差的绝对值 >= 1，从小到大输出这三个实根（保留两位小数）。
输入：实数a, b, c, d。
输出：三个实根。

AC代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
using namespace std;
double a, b, c, d;
double f(double x){
    return a * x * x * x + b * x * x + c * x + d;
}
double search(double l, double r, int k){
    while(1){
        double mid = (l + r)/2;
        if(r - l < 0.0001 || f(mid)== 0) return mid;
        if(f(mid) * k > 0) r = mid;
        else l = mid;
    }
}
int main(){
    freopen("answer.in", "r", stdin);
    freopen("answer.out", "w", stdout);
    scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
    double last = f(-100), j = -100;
    for(double i = -99; i <= 100; i++){
        double cur = f(i);
        if(cur == 0) printf("%.2lf ", i);
        else if(cur < 0 && last > 0) printf("%.2lf ", search(j, i, -1));
        else if(cur > 0 && last < 0) printf("%.2lf ", search(j, i, 1));
        j = i;
        last = cur;
    }
    printf("\n");
    return 0;
}

笔记：

其实这个单纯用枚举仅需两万次，并且十分保险，并不用二分。

2017-02-02 邱神看电视

邱神居然没写代码，在家看电视！
邱神有强迫症，每个节目必须完整地看完，不然不如不看！
为了看更多节目，邱神还练就了极快的手速，这样在前一个节目结束时可以立刻切换到同一时刻开始的节目！
邱神已知n个节目的开始时间和结束时间，希望完整地看越多节目越好！
请求出邱神最多能完整地看完几个节目！
输入：
第一行一个整数n，
接下来n行，每行两个数字，表示一个节目的起始时间和结束时间。
输出：
一个整数，表示最多看多少个节目。

AC代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
using namespace std;
struct pgm{
    int l, r;
};
int cmp(pgm x, pgm y){
    if(x.r == y.r) return x.l < y.l;
    return x.r < y.r;
}
pgm a[100005];
int n, ans = 0;
int main(){
    freopen("tv.in", "r", stdin);
    freopen("tv.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d%d", &a[i].l, &a[i].r);
    }
    sort(a, a+n, cmp);
    int last = 0;
    for(int i = 1; i < n; i++){
        if(a[i].l >= a[last].r){
            ans++;
            last = i;
        }
    }
    printf("%d\n", ans + 1);
    return 0;
}

笔记：

这题……完全是Codevs上【线段覆盖】那道题啊！

还恰好是我Markdown笔记的第一篇！

2017-02-03 线段覆盖2

题目描述 Description
数轴上有n条线段，线段的两端都是整数坐标，坐标范围在0~1000000，每条线段有一个价值，请从n条线段中挑出若干条线段，使得这些线段两两不覆盖（端点可以重合）且线段价值之和最大。
输入描述 Input Description
第一行一个整数n(n <= 1000)，表示有多少条线段。
接下来n行每行三个整数, ai bi ci，分别代表第i条线段的左端点ai，右端点bi（保证左端点<右端点）和价值ci。
输出描述 Output Description
输出能够获得的最大价值.

AC代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
struct line{
    int a, b, c;
}s[1005];
int n;
bool cmp(line x, line y){
    return x.b < y.b;
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d%d%d", &s[i].a, &s[i].b, &s[i].c);
    sort(s, s + n, cmp);
    for(int i = 1; i < n; i++){
        int maxc = 0;
        for(int j = 0; j < i; j++)
            if(s[i].a >= s[j].b)
                maxc = max(maxc, s[j].c);
        s[i].c += maxc;
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        ans = max(ans, s[i].c);
    }
    printf("%d\n", ans);
    return 0;
}

思路：

$dp[i].c = max(dp[j])+dp[i].c$
其中 i = 0 ... n, j = 0 ... i - 1, 需满足 i、j 不重叠。

2017-02-03 括号配对

定义满足以下规则字符串为规则序列，否则不是规则序列：
1．空序列是规则序列；
2．如果S是规则序列，那么(S),[S],{S}和也是规则序列；
3．如果A和B都是规则序列，那么AB也是规则序列。
例如，下面的字符串都是规则序列：
()，[]，(())，([])，()[]，()[()]，{{}}<>，([]<>{{}})，<<{}>>
而以下几个则不是：
(，[，]，)(，())，([()，<<，{(})，<{}>)
现在，给你一些由"("、")"、"["、"]"、"{"、"}"、"<"、">"构成的字符串，请判断该字符串是否为规则序列。
输入描述 Input Description
第一行：一个正整数N，表示测试数据组数；
接下来N行：每行一个括号序列(长度不超过L)。
输出描述 Output Description
共N行：对于每一个括号序列，判断其是否规则。
规则输出TRUE，否则输出FALSE。

AC代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
char stk[2000005], t, a[2000005];
int top = 0, n, m[256];
int main(){
    m['('] = m[')'] = 1;
    m['<'] = m['>'] = 2;
    m['['] = m[']'] = 3;
    m['{'] = m['}'] = 4;
    scanf("%d", &n);
    while(n--){
        top = 0;
        scanf("%s", a);
        int ok = 1, l = strlen(a);
        if(l % 2){
            printf("FALSE\n");
            continue;
        }
        for(int i = 0; i < l; i++){
            if(a[i]=='('||a[i]=='<'||a[i]=='{'||a[i]=='[')
                stk[++top] = a[i];
            else if(!top || m[a[i]] != m[stk[top]]){
                ok = 0;
                break;
            }
            else top--;
        }
        if(top) ok = 0;
        if(ok) printf("TRUE\n");
        else printf("FALSE\n");
    }
    return 0;
}

@ 用手动判断是否换行（'\n'）来判断一个字符串是否输入完成。然而评测机的换行符似乎不太一样，遂跪。

@ 每次循环都使用一次strlen(a)，结果超时……

2017-02-03 变换之美

【问题描述】
有一个长度为N 的整数数列（A1, A2…Ai…An-1, An），现在可以对该数
列进行一种变换，即选择数列中的一个数字Ai(1 换成Ai-1 + Ai , -Ai , Ai+1 + Ai。这种变换操作可以进行多次。现在于队长想
知道一个数列能否变换成另一个数列。
【输入格式】
从文件transform.in 中读入数据。
第一行一个整数t，表示有t 组数据
接下来对于每组数据，
第1 行：一个正整数N，表示数列的长度。
第2 行：N 个整数，表示数列A。
第3 行：N 个整数，表示数列B。
【输出格式】
输出到文件transform.out 中。
每组数据输出一行，
如果数列A 能变换成数列B，输出YES，否则，输出NO。
【输入样例】
3
3
1 2 3
1 2 3
5
1 2 3 4 5
5 4 3 2 1
5
1 2 3 4 5
6 -5 9 -7 12
【输入样例】
YES
NO
YES

思路：

对于三个元素

$A[i - 1], A[i], A[i + 1]$
设前缀和分别为

$S[i - 1], S[i], S[i + 1]$
对 A[i] 进行变换后，三个元素变为

$A[i - 1] + A[i], -A[i], A[i + 1] + A[i]$
则前缀和变为

$S[i], S[i - 1], S[i + 1]$
即前两个元素前缀和调换位置。

因此，将A数列和B数列前缀和分别排序后是相同的。

AC代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cctype>
#include<stack>
#include<queue>
using namespace std;
int a[5005], b[5005], t, n, tp;
int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        int ok = 1;
        for(int i = 1; i <= n; i++){
            scanf("%d", &tp);
            a[i] = a[i-1] + tp;
        }
        for(int i = 1; i <= n; i++){
            scanf("%d", &tp);
            b[i] = b[i-1] + tp;
        }
        sort(a + 1, a + n + 1);
        sort(b + 1, b + n + 1);
        for(int i = 1; i <= n; i++){
            if(a[i] != b[i]){
                ok = 0;
                break;
            }
        }
        if(ok) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

@ 没想到前缀和……

2017-02-03 括号的匹配

题目描述 Description
在算术表达式中，除了加、减、乘、除等运算外，往往还有括号。包括有大括号{}，中括号[]，小括号()，尖括号<>等。对于每一对括号，必须先左边括号，然后右边括号；如果有多个括号，则每种类型的左括号和右括号的个数必须相等；对于多重括号的情形，按运算规则，从外到内的括号嵌套顺序为：大括号->中括号->小括号->尖括号。例如，{[()]}，{()},{{}}为一个合法的表达式，而([{}])，{([])},[{<>}]都是非法的。
输入描述 Input Description
第一行为一个整数n（1≤n≤100），接下来有n行仅由上述四类括号组成的括号表达式。第i+1行表示第i个表达式。每个括号表达式的长度不超过255。
输出描述 Output Description
输出共N行，对应于i行输入，合法则输出YES，非法则输出NO。

AC代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cctype>
#include<stack>
#include<queue>
using namespace std;
char a[300], stk[600];
int n, top = 0, m[256], h;
int main(){
    freopen("match.in","r",stdin);
    freopen("match.ans","w",stdout);
    m['<'] = m['>'] = 1;
    m['('] = m[')'] = 2;
    m['['] = m[']'] = 3;
    m['{'] = m['}'] = 4;
    scanf("%d", &n);
    while(n--){
        int ok = 1;
        top = 0;
        h = '<';
        scanf("%s", a);
        int len = strlen(a);
        if(len % 2){
            printf("NO\n");
            continue;
        }
        for(int i = 0; i < len; i++){
            char t = a[i];
            if(t == '<' || t == '(' || t == '[' || t == '{'){
                if(top && m[stk[top]] < m[t]){
                    ok = 0;
                    break;
                }
                stk[++top] = t;
            }
            else if(!top || m[t] != m[stk[top]]){
                ok = 0;
                break;
            }
            else{
                top--;
            }
        }
        if(top) ok = 0;
        if(ok) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

2017-02-06 简单的树学题

【问题描述】
简单的树学问题
给一个树，树有 N 个节点，每条边长度为 1，求经过任意 K 个不相同点的最短路径(可以选择 K 个点中任意一个作为起点)。
【输入格式】
输入文件 tree.in 包含 N+M 行;
第一行两个个数 N，M;表示树的节点个数和共有 M 次询问。接下来的 N-1 行每行两个数 s,t;表示 s 到 t 有一条边。再接下来 M 行，每行一个数 K;保证 1 【输出格式】
输出文件 tree.out 包含 M 行对于输入中的每个询问操作，给出答案。
【输入样例】
31 12 13 2
【输入样例】
1
【数据范围】
N,M<=5; 对于另 20%的数据 N, M<=30;
对于 20%的数据
对于 100%的数据 2<=N<=100000 ，1<=M<=100000，1< K<=N，1<=s,t<=N。

AC代码：

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
#define LIM  200005
int N, M, K, cnt = 1, head[LIM], d, end, vis[LIM]; // d: zhi jing
struct line{
    int to, next;
}edge[LIM];
void enter(){
    int s, t;
    scanf("%d%d", &s, &t);
    edge[cnt].to = t;
    edge[cnt].next = head[s];
    head[s] = cnt++;
    //printf("%d %d\n",s, edge[cnt - 1].next);
    edge[cnt].to = s;
    edge[cnt].next = head[t];
    head[t] = cnt++;
    //printf("%d %d\n",t, edge[cnt - 1].next);
}
queue <int> q, time;
void bfs(int x){
    for(int i = 1; i <= N; i++) vis[i] = 0;
    q.push(x);
    time.push(1);
    while(!q.empty()){
        int curn = q.front(); // current node number
        int curt = time.front(); // current time(number of nodes)
        q.pop();
        time.pop();
        vis[curn] = 1;
        int ok = 0;
        for(int i = head[curn]; i; i = edge[i].next){ // try all the edges!
            if(!vis[edge[i].to]){
                ok = 1;
                q.push(edge[i].to);
                time.push(curt + 1);
            }   
        }
        //printf("%d", curn);
        //printf("!");
        if(!ok){
            if(curt > d){
                d = curt;
                end = curn;
            }
        } // end of the road...
    }
}
int main(){
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    scanf("%d%d", &N, &M);
    for(int i = 1; i < N; i++) enter();
    bfs(1);
    bfs(end);
    //printf("%d\n", d);
    for(int i = 1; i <= M; i++){ // answer the questions
        scanf("%d", &K);
        if(K <= d) printf("%d\n", K - 1);
        else printf("%d\n", 2*K - d - 1);
    }
    return 0;
}

@ 数据范围是 $10^5$ ，然而无向图每条边要存两遍，所以数组应该开到 $2×10^5$ ……

2017-02-15 过河卒

如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C 点上的马可以控制 9 个点（图中的P1，P2 … P8 和 C）。卒不能通过对方马的控制点。
棋盘用坐标表示，A 点（0，0）、B 点（n,m）(n,m 为不超过 20 的整数，并由键盘输入)，同样马的位置坐标是需要给出的（约定: C不等于A，同时C不等于B）。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。

输入描述 Input Description
　键盘输入
　　　B点的坐标（n,m）以及对方马的坐标（X,Y）{不用判错}
输出描述 Output Description
　　屏幕输出
　　　　一个整数（路径的条数）。
样例输入 Sample Input
　6 6 3 2
样例输出 Sample Output
　17

水题，没啥可说的……

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
int bx, by, hx, hy;
long long ans[25][25];
//B(x,y), Horse(x, y)
int main(){
    scanf("%d%d%d%d", &bx, &by, &hx, &hy);
    ans[0][0] = 1;
    ans[hx][hy] = -1;
    if(hy - 1 >= 0) ans[hx + 2][hy - 1] = -1;
    if(hy - 2 >= 0) ans[hx + 1][hy - 2] = -1;
    ans[hx + 2][hy + 1] = -1;
    ans[hx + 1][hy + 2] = -1;
    if(hy - 1 >= 0 && hx - 2 >= 0) ans[hx - 2][hy - 1] = -1;
    if(hy - 2 >= 0 && hx - 1 >= 0) ans[hx - 1][hy - 2] = -1;
    if(hx - 2 >= 0) ans[hx - 2][hy + 1] = -1;
    if(hx - 1 >= 0) ans[hx - 1][hy + 2] = -1;
    for(int i = 0; i <= bx; i++){
        for(int j = 0; j <= by; j++){
            if(ans[i][j] == -1) continue;
            if(i - 1 >= 0 && ans[i - 1][j] > 0) ans[i][j] += ans[i - 1][j];
            if(j - 1 >= 0 && ans[i][j - 1] > 0) ans[i][j] += ans[i][j - 1];
        }
    }
    printf("%lld\n", ans[bx][by]);
    return 0;
}

@ 我以为负数是假………………

2017-02-15 骑士游历

题目描述 Description
设有一个n*m的棋盘（2≤n≤50，2≤m≤50），如下图，在棋盘上有一个中国象棋马。
规定：
1)马只能走日字
2)马只能向右跳
问给定起点x1,y1和终点x2,y2，求出马从x1,y1出发到x2,y2的合法路径条数。
输入描述 Input Description
第一行2个整数n和m
第二行4个整数x1,y1,x2,y2
输出描述 Output Description
输出方案数
样例输入 Sample Input
30 30
1 15 3 15
样例输出 Sample Output
2

水题*2

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
long long ans[55][55];
int n, m, xs, ys, xe, ye;//start, end
int main(){
    scanf("%d%d%d%d%d%d", &n, &m, &xs, &ys, &xe, &ye);
    ans[xs][ys] = 1;
    for(int i = xs + 1; i <= xe; i++){
        for(int j = 1; j <= max(n, m); j++){
            if(j > 2) ans[i][j] += ans[i - 1][j - 2];
            if(j > 1) ans[i][j] += ans[i - 2][j - 1];
            ans[i][j] += ans[i - 1][j + 2] + ans[i - 2][j + 1];
        }
    }
    printf("%lld\n", ans[xe][ye]);
    return 0;
}

2017-02-15 乘积最大

题目描述 Description
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：
设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312，当N=3，K=1时会有以下两种分法：
1) 3*12=36
2) 31*2=62
这时，符合题目要求的结果是：31*2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
输入描述 Input Description
程序的输入共有两行：
第一行共有2个自然数N，K（6≤N≤40，1≤K≤6）
第二行是一个长度为N的数字串。
输出描述 Output Description
结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。
样例输入 Sample Input
4 2
1231
样例输出 Sample Output
62
数据范围及提示 Data Size & Hint
本题由于比较老，数据实际也比较小，用long long 即可通过

dp[i][j][k]表示区间[i,j]中放k个乘号的最大乘积。

$dp[i][j][k] = max(dp[i][m][0] * dp[m+1][j][k-1])$
(i<=m<=j-k)

AC代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
char s[50];
int a[50], N, K;
long long dp[50][50][50];
long long cvt(int i, int j){ //convert [i,j] to a number
    long long ans = 0;
    for(int m = i; m <= j; m++)
        ans = ans * 10 + a[m];
    return ans;
}
int main(){
    scanf("%d%d", &N, &K);
    scanf("%s", s);
    for(int i = 0; i < N; i++)
        a[i + 1] = s[i] - '0';
    for(int k = 0; k <= K; k++)
        for(int l = 0; l < N; l++)
            for(int i = 1; i + l <= N; i++){
                int j = i + l;
                if(k == 0){
                    dp[i][j][k] = cvt(i, j);
                    continue;
                }
                for(int m = i; m <= j-k; m++)
                    dp[i][j][k] = max(dp[i][j][k], dp[i][m][0]*dp[m+1][j][k-1]);
            }
    printf("%lld\n", dp[1][N][K]);
    return 0;
}

2017-02-16 统计单词个数

题目描述 Description
给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份(1 单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。
输入描述 Input Description
第一行为一个正整数(0 每组的第一行有二个正整数(p，k)
p表示字串的行数;
k表示分为k个部分。
接下来的p行，每行均有20个字符。
再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6)
接下来的s行，每行均有一个单词。
输出描述 Output Description
每行一个整数，分别对应每组测试数据的相应结果。
样例输入 Sample Input
1
1 3
thisisabookyouareaoh
4
is
a
ok
sab
样例输出 Sample Output
7
数据范围及提示 Data Size & Hint
this/isabookyoua/reaoh

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
int N, P, K, S, L, dp[205][45], wd[205][205], len[8];
char str[205], dic[8][205];
int main(){
    scanf("%d", &N);
    while(N--){
        scanf("%d%d", &P, &K);
        for(int i = 0; i < P; i++)
            scanf("%s", str + i * 20 + 1);
        L = P * 20;
        scanf("%d", &S);
        for(int i = 1; i <= S; i++){
            scanf("%s", dic[i] + 1);
            len[i] = strlen(dic[i] + 1);
        }
/*INPUT***************************************/
        for(int i = L; i > 0; i--)
            for(int j = L; j >= i; j--){
                wd[i][j] = wd[i+1][j];
                for(int k = 1; k <= S; k++){
                    if(len[k] > j - i + 1) continue;
                    int yes = 1;
                    for(int p = 1; p <= len[k]; p++)
                        if(dic[k][p] != str[i + p - 1]){
                            yes = 0;
                            break;
                        }
                    if(yes) wd[i][j] = max(wd[i][j], wd[i+1][j] + 1);
                }
            }
/*CACULATE*WORDS******************************/
        for(int i = 1; i <= L; i++){
            dp[i][1] = wd[1][i];
            for(int j = 2; j <= K; j++){
                for(int k = j; k < i; k++){
                    dp[i][j] = max(dp[i][j], dp[k][j-1] + wd[k+1][i]);
                }
            }
        }
        printf("%d\n", dp[L][K]);
    }
    return 0;
}

@ 忽略了dp[i][j]中i < j时不成立的情况，使这种情况参与了计算。

2017-02-17 四子连棋

题目描述 Description
在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。

●	○	●
○	●	○	●
●	○	●	○
○	●	○

输入描述 Input Description
从文件中读入一个4*4的初始棋局，黑棋子用B表示，白棋子用W表示，空格地带用O表示。
输出描述 Output Description
用最少的步数移动到目标棋局的步数。
样例输入 Sample Input
BWBO
WBWB
BWBW
WBWO
样例输出 Sample Output
5

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
struct node{
    int t, last;
    int a[4][4];
};
char start[5][5];
node st;
queue <node> q;
int biao[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721};
bool vis[50000000];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
//up down left right
int legal(int x, int y){ return (x >= 0 && y >= 0 && x < 4 && y < 4);}
int ten(node cur){
    int ans = 0, pos = 15;
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            ans += cur.a[i][j] * biao[pos];
            pos--;
        }
    }
    return ans;
}
int main(){
    scanf("%s%s%s%s", start[0], start[1], start[2], start[3]);
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++){
            if(start[i][j] == 'B') st.a[i][j] = 1;
            else if(start[i][j] == 'W') st.a[i][j] = 2;
            else st.a[i][j] = 0;
            st.t = 0;
            st.last = 0;
        }
    q.push(st);
    while(!q.empty()){
        node cur = q.front();
        q.pop();
        if(vis[ten(cur)])continue;
        vis[ten(cur)] = 1;
        int ok = 0;
        for(int i = 0; i < 4; i++)
            if(cur.a[i][0]==cur.a[i][1]&&cur.a[i][0]==cur.a[i][2]&&cur.a[i][0]==cur.a[i][3])
                ok = 1;
        for(int j = 0; !ok && j < 4; j++)
            if(cur.a[0][j]==cur.a[1][j]&&cur.a[0][j]==cur.a[2][j]&&cur.a[0][j]==cur.a[3][j])
                ok = 1;
        if(!ok && cur.a[0][0]==cur.a[1][1]&&cur.a[0][0]==cur.a[2][2]&&cur.a[0][0]==cur.a[3][3])
            ok = 1;
        if(!ok && cur.a[3][0]==cur.a[2][1]&&cur.a[3][0]==cur.a[1][2]&&cur.a[3][0]==cur.a[0][3])
            ok = 1;
        if(ok){
            printf("%d\n", cur.t);
            break;
        }
        /*****check*finished******/
        for(int i = 0; i < 4; i++)
            for(int j = 0; j < 4; j++)
                if(cur.a[i][j] == 0)
                    for(int m = 0; m < 4; m++)
                        if(legal(i + dx[m], j + dy[m])&&cur.last != cur.a[i + dx[m]][j + dy[m]]){
                            node tp = cur;
                            tp.t++;
                            tp.a[i][j] = tp.a[i + dx[m]][j + dy[m]];
                            tp.a[i + dx[m]][j + dy[m]] = 0;
                            tp.last = tp.a[i][j];
                            q.push(tp);
                        }
    }
    return 0;
}

@ 有个 m<4 打成了 m<3……(t* *)

2017-02-19 单词接龙

题目描述 Description
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。
输入描述 Input Description
输入的第一行为一个单独的整数n(n<=20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
输出描述 Output Description
只需输出以此字母开头的最长的“龙”的长度
样例输入 Sample Input
5
at
touch
cheat
choose
tact
a
样例输出 Sample Output
23
数据范围及提示 Data Size & Hint
（连成的“龙”为atoucheatactactouchoose)

不知道为什么就AC了……XD

AC代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
string wd[22];
int n, vis[22];
string head;
int dfs(string last, int length){
    int nowl = length;
    for(int w = 0; w < n; w++){
        if(vis[w] == 2) continue;
        int lastl = last.size();
        int thisl = wd[w].size();
        for(int l = 1; l <= min(lastl, thisl); l++){
            if(last.substr(lastl - l, l) == wd[w].substr(0, l)){
            vis[w]++;
            nowl = max(nowl, dfs(wd[w].substr(l, thisl-l), length + thisl - l));
            vis[w]--;
            }
        }
    }
    return nowl;
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    cin >> wd[i];
    cin >> head;
    cout << dfs(head, 1) << endl;
    return 0;
}

2017-02-23 食物链

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。　　
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。　　
有人用两种说法对这N个动物所构成的食物链关系进行描述：　　
第一种说法是“1 X Y”，表示X和Y是同类。　　
第二种说法是“2 X Y”，表示X吃Y。　　
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1）当前的话与前面的某些真的话冲突，就是假话；　　
2）当前的话中X或Y比N大，就是假话；　　
3）当前的话表示X吃X，就是假话。　　
你的任务是根据给定的N（1<=N<=50,000）和K句话（0<=K<=100,000），输出假话的总数。
输入描述 Input Description
第一行是两个整数N和K，以一个空格分隔。　　
以下K行每行是三个正整数D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。　　
若D=1，则表示X和Y是同类。　　
若D=2，则表示X吃Y。
输出描述 Output Description
只有一个整数，表示假话的数目。

思路：

一道高端的并查集！

用 x + n 表示 x 吃的东西，用 x + 2*n 表示吃 x 的东西。
这里的 x + n 和 x + 2*n 都只是个编号，接下来根据输入数据，把编号和实际的东西划为一类即可。(“实际的东西”处在[1, n]范围内。）

初始化：
正常的并查集初始化，每个 fa[i] 都 = i。

并：
每个“并”操作都要进行三次。
1. 当输入指令为 1 x y 时，将x和y合并，将吃x的和吃y的合并，将x吃的和y吃的合并。
2. 当输入指令为 2 x y 时，将x吃的和y合并，将x和吃y的合并，将吃x的和y吃的合并（因为食物链中三个物种呈环形）。

判断合法：
只有对x和y的操作合法时才能进行合并操作。对于两种操作，x和y都要在[0,n]范围内。
另外：
1. 当输入指令为 1 x y 时，x吃的和y不能重合，吃x的和y不能重合。
2. 当输入指令为 2 x y 时，x和y不能重合，吃x的和y不能重合。

AC代码:

#include <cstdio>
using namespace std;
int fa[200005], fake = 0, n, k;
int findfa(int x){
    if(fa[x] == x) return x;
    fa[x] = findfa(fa[x]);
    return fa[x];
} 
bool legal1(int x, int y){
    if(x > n || y > n || x <= 0 || y <= 0) return 0;
    if(findfa(x + n) == findfa(y) || findfa(x + 2*n) == findfa(y))
        return 0;
    return 1;
}
bool legal2(int x, int y){
    if(x > n || y > n || x <= 0 || y <= 0) return 0;
    if(findfa(x) == findfa(y) || findfa(x + 2*n) == findfa(y)) 
        return 0;
    return 1;
}
void join(int x, int y){
    int u = findfa(x);
    int v = findfa(y);
    fa[u] = v;
}
int main(){
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= 3*n; i++)
        fa[i] = i;
    for(int i = 1; i <= k; i++){
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if(op == 1){
            if(legal1(x, y)){
                join(x, y);
                join(x + n, y + n);
                join(x + 2*n, y + 2*n);
            }
            else fake++;
        }
        else{
            if(legal2(x, y)){
                join(x + n, y);
                join(x, y + 2*n);
                join(x + 2*n, y + n);
            }
            else fake++;
        }
    }
    printf("%d\n", fake);
    return 0;
}

@ 把 findfa() 函数定义成了……bool……………………-_-|||

2017-02-23 约瑟夫问题

题目描述 Description
有编号从1到N的N个小朋友在玩一种出圈的游戏。开始时N个小朋友围成一圈，编号为I+1的小朋友站在编号为I小朋友左边。编号为1的小朋友站在编号为N的小朋友左边。首先编号为1的小朋友开始报数，接着站在左边的小朋友顺序报数，直到数到某个数字M时就出圈。直到只剩下1个小朋友，则游戏完毕。
现在给定N,M，求N个小朋友的出圈顺序。
输入描述 Input Description
唯一的一行包含两个整数N,M。（1<=N,M<=30000）
输出描述 Output Description
唯一的一行包含N个整数，每两个整数中间用空格隔开，第I个整数表示第I个出圈的小朋友的编号。
样例输入 Sample Input
5 3
样例输出 Sample Output
3 1 5 2 4

思路

一般的约瑟夫问题解法（暴力模拟）的复杂度是 O(mn)，非常慢，像这道题一定会爆掉的！

但是有了线段树以后我们可以得到一个非常妙~~~ 的解法，它的复杂度是 O(nlogn)。

首先我们考虑，现在有一排圆滚滚的熊孩子

OOOOOOOOO

把他们从0开始编号：

OOOOOOOOO
012345678

假设我们让数到3的熊孩子退出，那么第一个退出的是当前队伍里的第三个——也就是2号熊孩子，队伍变成这样：

OOOOOOOO
01345678

第二个退出的熊孩子是当前队伍里往下数三个——也就是5号熊孩子。

以此类推（当然，数到队伍末尾的时候要模当前队伍的长度），显然我们每次都知道当前队伍中第几个会退出。

那么问题来了：我们需要知道当前队伍中的第p个人在初始队伍中的编号，并输出。

这时候我们就可以用线段树了。

这棵线段树非常简单：一个节点存储的是它所代表的区间[i,j]中，还没退出的人数。这里的i，j都是初始队伍中的编号。

那么：

   [N]
    |\
[2*N][2*N+1]

我们要找N代表的区间中第p个还在队伍中的熊孩子（从0开始数），要判断一下：
1.如果 p < data[2*N], 就在左儿子里找第p个；
2.如果 p >= data[2*N], 就在右儿子里找第 p-data[2*N] 个。

这样就可以找到啦。

AC代码

#include <cstdio>
using namespace std;
int data[120005], n, m;
void build(int i, int l, int r){
    if(l == r){
        data[i] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(i<<1, l, mid);
    build(i<<1|1, mid+1, r);
    data[i] = data[i<<1] + data[i<<1|1];
}
void dlt(int i, int p, int l, int r){
    if(l == r){
        printf("%d ", l+1);
        data[i] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    if(data[i << 1] > p) dlt(i << 1, p, l, mid);
    else dlt(i << 1 | 1, p - data[i << 1], mid + 1, r);
    data[i] = data[i<<1] + data[i<<1|1];
}
int main() {
    scanf("%d%d", &n, &m);
    int p = 0;
    build(1, 0, n-1);
    for(int q = 1; q <= n; q++){
        p = (p + m - 1) % (n - q + 1);
        dlt(1, p, 0, n - 1);
    }
    return 0;
}

2017-02-23 元素查找

题目描述 Description
给出n个正整数，然后有m个询问，每个询问一个整数，询问该整数是否在n个正整数中出现过。
输入描述 Input Description
第一行两个整数 n 和m。
第二行n个正整数（1<=n<= 100000）
第三行m个整数(1<=m<=100000)
输出描述 Output Description
一共m行，若出现则输出YES，否则输出NO
样例输入 Sample Input
4 2
2 1 3 4
1 9

只是那这道题试试 STL 的 set...

Set 小总结：

set <int> s;
set <int> :: iterator it;
//定义一个迭代器it

it = s.find(a);
//在集合s中找a，
//找到了返回该元素位置，没找到返回集合末位置s.end()
if(it != s.end()) printf("YES\n");
else printf("NO\n");

AC代码：

#include <cstdio>
#include <set>
using namespace std;
int n, m, t;
set <int> s;
set <int> :: iterator it;
int main(){
    scanf("%d%d", &n, &m);
        for(int i = 0; i < n; i++){
        scanf("%d", &t);
        s.insert(t);
    }
    for(int i = 0; i < m; i++){
        scanf("%d", &t);
        it = s.find(t);
        if(it != s.end())
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

2017-02-24 Counterfeit Dollar

描述
Sally Jones has a dozen Voyageur silver dollars. However, only eleven of the coins are true silver dollars; one coin is counterfeit even though its color and size make it indistinguishable from the real silver dollars. The counterfeit coin has a different weight from the other coins but Sally does not know if it is heavier or lighter than the real coins.
Happily, Sally has a friend who loans her a very accurate balance scale. The friend will permit Sally three weighings to find the counterfeit coin. For instance, if Sally weighs two coins against each other and the scales balance then she knows these two coins are true. Now if Sally weighs
one of the true coins against a third coin and the scales do not balance then Sally knows the third coin is counterfeit and she can tell whether it is light or heavy depending on whether the balance on which it is placed goes up or down, respectively.
By choosing her weighings carefully, Sally is able to ensure that she will find the counterfeit coin with exactly three weighings.
输入
The first line of input is an integer n (n > 0) specifying the number of cases to follow. Each case consists of three lines of input, one for each weighing. Sally has identified each of the coins with the letters A--L. Information on a weighing will be given by two strings of letters and then one of the words "up", "down", or "even". The first string of letters will represent the coins on the left balance; the second string, the coins on the right balance. (Sally will always place the same number of coins on the right balance as on the left balance.) The word in the third position will tell whether the right side of the balance goes up, down, or remains even.
输出
For each case, the output will identify the counterfeit coin by its letter and tell whether it is heavy or light. The solution will always be uniquely determined.
样例输入
1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even
样例输出
K is the counterfeit coin and it is light.

AC代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
int T;
char a[4][14], b[4][14], c[4][14];
int main(){
    scanf("%d", &T);
    while(T--){
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        for(int j = 0; j < 3; j++){
            scanf("%s%s%s", a[j], b[j], c[j]);
        }
        for(int p = 0; p < 2; p++)
            for(int i = 0; i < 12; i++){
                int ok = 1;
                for(int j = 0; j < 3; j++){
                    if(c[j][0] == 'e'){
                        for(int k = 0; k < 12; k++){
                            if(a[j][k] == i+'A' || b[j][k] == i+'A'){
                                ok = 0;
                                break;
                            }
                        }
                    }
                    else if(c[j][0] == 'u'&&p==1||c[j][0]=='d'&&p==0){
                        int found = 0;
                        for(int k = 0; k < 12; k++){
                            if(a[j][k]==i+'A') found = 1;
                            if(b[j][k]==i+'A') {
                                ok = 0;
                                break;
                            }
                        }
                        if(!found) ok = 0;
                    }
                    else if(c[j][0] == 'd' && p == 1 || c[j][0] == 'u' && p == 0){
                        int found = 0;
                        for(int k = 0; k < 12; k++){
                            if(b[j][k]==i+'A') found = 1;
                            if(a[j][k]==i+'A'){
                                ok = 0;
                                break;
                            }
                        }
                        if(!found) ok = 0;
                    }
                }
                if(ok){
                    if(p) printf("%c is the counterfeit coin and it is heavy.\n", i+'A');
                    else printf("%c is the counterfeit coin and it is light.\n", i+'A');
                    break;
                }
            }
    }
    return 0;
}

@ 一条“称重”不一定是四个四个比较
@ 二维数组输入字符串的时候还是大一点开吧不然特别鬼畜

//获得成就【人体翻译机】

2017-02-24 Bomb Game

描述
Bosko and Susko are playing an interesting game on a board made of rectangular fields arranged in A rows and B columns.
When the game starts, Susko puts its virtual pillbox in one field one the board. Then Bosko selects fields on which he will throw his virtual bombs. After each bomb, Susko will tell Bosko whether his pillbox is in the range of this bomb or not.
The range of a bomb with diameter P (P is always odd), which is thrown in field (R, S), is a square area. The center of the square is in the field (R, S), and the side of the square is parallel to the sides of the board and with length P.
After some bombs have been thrown, Bosko should find out the position of Susko's pillbox. However, the position may be not unique, and your job is to help Bosko to calculate the number of possible positions.
输入
First line of input contains three integers: A, B and K, 1 <= A, B, K <=100. A represents the number of rows, B the number of columns and K the number of thrown bombs.
Each of the next K lines contains integers R, S, P and T, describing a bomb thrown in the field at R-th row and S-th column with diameter P, 1 <= R <= A, 1 <= S <= B, 1 <= P <= 99, P is odd. If the pillbox is in the range of this bomb, T equals to 1; otherwise it is 0.
输出
Output the number of possible fields, which Susko's pillbox may stay in.
样例输入
5 5 3
3 3 3 1
3 4 1 0
3 4 3 1
样例输出
5

又一锻炼英语阅读理解的题……

#include <cstdio>
#include <iostream>
using namespace std;
int range[105][105];
int n, m, q, x, y, z, p, f;
// range[i][j] = 1: (i,j) deleted
bool inside(int i, int j, int x, int y, int z){
    int k = z / 2;
    if(i > x + k || i < x - k || j > y + k || j < y - k)
        return 0;
    return 1;
}
int main(){
    scanf("%d%d%d", &n, &m, &q);
    while(q--){
        scanf("%d%d%d%d", &x, &y, &z, &f);
        if(f == 1){
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= m; j++)
                    range[i][j] = range[i][j] || !inside(i, j, x, y, z);
        }
        else{
            for(int i = max(x-z/2,1);i <= x+z/2 && i <= n;i++)
                for(int j=max(y-z/2,1);j<=y+z/2&&j<=m;j++)
                    range[i][j] = 1;      
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(!range[i][j]) ans++;
    printf("%d\n", ans);
    return 0;
}

@ p打成z（将错就错），1打成0（自己规定的01含义自己都没记住）
记得多用 -Wall

胡小兔的OI日志

查看最新

2016-12-16 线段覆盖

AC代码：

2016-12-17 线段树练习

AC代码：

2016-12-18 垂直直方图

AC代码：

2016-12-18 乌龟棋

AC代码：

2017-01-19 公共子序列

AC代码：

2017-01-19 摘花生

思路：

AC代码：

2017-01-20 有趣的跳跃

AC代码：

2017-01-20 滑雪

思路：

AC代码：

2017-01-21 手写一个堆

AC代码：

2017-01-21 家族

思路：

AC代码：

2017-01-22 最小生成树

思路：

AC代码：

2017-01-22 糖果

思路：

AC代码：

2017-01-23 多源最短路

思路：

AC代码：

2017-01-23 手写快排

AC代码：

2017-01-24 谁是你的潜在朋友

AC代码：

2017-01-24 和数

AC代码：

2017-01-31 高精度阶乘

AC代码：

2017-02-01 高精度加减乘模

AC代码：

加法：

减法：

乘法：

膜法 取模：

2017-02-01 扩展GCD

AC代码：

2017-02-01 麻烦的字符串

AC代码:

2017-02-01 调皮的水

AC代码：

2017-02-02 一元三次方程

AC代码：

笔记：

2017-02-02 邱神看电视

AC代码：

笔记：

2017-02-03 线段覆盖2

AC代码：

思路：

2017-02-03 括号配对

AC代码：

2017-02-03 变换之美

思路：

AC代码：

2017-02-03 括号的匹配

AC代码：

2017-02-06 简单的树学题

AC代码：

2017-02-15 过河卒

AC代码：

2017-02-15 骑士游历

AC代码：

2017-02-15 乘积最大

AC代码：

2017-02-16 统计单词个数

AC代码：

膜法取模：