魔法机器二,魔法机器2

补题补题

牛客网给出的题解:https://www.nowcoder.com/discuss/39219
小编要好眼下唯有前 7题,前面一题先放着。小编要好的分析也发在牛客网的标题下了。。不知能或不能够骗骗赞
23③

补题补题

牛客网给出的题解:https://www.nowcoder.com/discuss/39219
本身要好眼下唯有前 7题,前边一题先放着。笔者自身的剖析也发在牛客网的难题下了。。不知能否骗骗赞
23三

魔法币

魔法币

Description

小易准备去魔法王国购买销售魔法神器,购买魔法神器须要采纳魔法币,可是小易未来一枚魔法币都未曾,可是小易有两台魔法机器能够透过投入x(x可以为0)个魔法币发生越多的魔法币。
魔法机器一:如若投入x个魔法币,魔法机器会将其成为二x+二个魔法币
魔法机器二:假如投入x个魔法币,魔法机器会将其成为贰x+一个魔法币
小易购买销售魔法神器总共须要n个魔法币,所以小易只可以通过两台魔法机器发出恰好n个魔法币,小易必要您帮他布署贰个投入方案使她最终恰好拥有n个魔法币。

Description

小易准备去魔法王国购销魔法神器,购买魔法神器需求动用魔法币,不过小易现在壹枚魔法币都不曾,可是小易有两台魔法机器能够通过投入x(x能够为0)个魔法币发生越来越多的魔法币。
魔法机器一:假若投入x个魔法币,魔法机器会将其变为二x+3个魔法币
魔法机器2:借使投入x个魔法币,魔法机器会将其改为2x+一个魔法币
小易购买销售魔法神器总共要求n个魔法币,所以小易只可以通过两台魔法机器发出恰好n个魔法币,小易须求您帮她安插3个投入方案使她最终恰好拥有n个魔法币。

Input

输入包罗一行,包罗1个正整数n(一 ≤ n ≤ 十^九),表示小易供给的魔法币数量。

Input

输入包涵1行,包涵3个正整数n(1 ≤ n ≤ 10^九),表示小易必要的魔法币数量。

Output

输出3个字符串,每一种字符表示该次小易选用投入的魔法机器。个中只含有字符’1’和’二’。

Output

输出2个字符串,每一个字符表示该次小易选择投入的魔法机器。个中只包涵字符’一’和’二’。

Sample Input

10

Sample Input

10

Sample Output

122

Sample Output

122

解题思路

水题,求 x 经过若干次 \(f(x)=2x+c\)
的变换恰好到 n ,明显次数不超过 \(log(n)+1=32\) 次,而 \(c=1 || 2\) 使得每一次 n’
具有奇偶特征,直接递归出来。

解题思路

水题,求 x 经过若干次 \(f(x)=2x+c\)
的转换恰好到 n ,明显次数不当先 \(log(n)+1=32\) 次,而 \(c=1 || 2\) 使得每一次 n’
具有奇偶特征,直接递归出来。

AC 代码

#include <stdio.h>

int n;

void read() {
    scanf("%d", &n);
}

void magic(int n) {
    if (n <= 0) return;
    if (n & 1) {
        magic((n - 1) / 2);
        putchar('1');
    } else {
        magic((n - 2) / 2);
        putchar('2');
    }
}

void work() {
    magic(n);
    putchar('\n');
}

int main() {
    read();
    work();
    return 0;
}

AC 代码

#include <stdio.h>

int n;

void read() {
    scanf("%d", &n);
}

void magic(int n) {
    if (n <= 0) return;
    if (n & 1) {
        magic((n - 1) / 2);
        putchar('1');
    } else {
        magic((n - 2) / 2);
        putchar('2');
    }
}

void work() {
    magic(n);
    putchar('\n');
}

int main() {
    read();
    work();
    return 0;
}

相反数

相反数

Description

为了赢得二个数的”相反数”,我们将那么些数的数字顺序颠倒,然后再添加原来的数到手”相反数”。例如,为了拿走13贰伍的”相反数”,首先我们将该数的数字顺序颠倒,大家得到523一,之后再添加原来的数,大家赢得523一+13二伍=655六.倘若颠倒之后的数字有前缀零,前缀零将会被忽视。例如n
= 100, 颠倒之后是1.

Description

为了获取三个数的”相反数”,大家将以此数的数字顺序颠倒,然后再添加原来的数到手”相反数”。例如,为了取得132五的”相反数”,首先大家将该数的数字顺序颠倒,大家获取5231,之后再添加原来的数,大家收获523一+13二5=655陆.假若颠倒之后的数字有前缀零,前缀零将会被忽略。例如n
= 100, 颠倒之后是壹.

Input

输入包含二个整数n,(一 ≤ n ≤ 十^5)

Input

输入包含3个平头n,(一 ≤ n ≤ 10^伍)

Output

出口二个整数,表示n的相反数

Output

输出一个整数,表示n的相反数

Sample Input

1325

Sample Input

1325

Sample Output

6556

Sample Output

6556

解题思路

水题,能够算程序设计入门课作业题。

解题思路

水题,能够算程序设计入门课作业题。

AC 代码

#include <stdio.h>

int n;

void read() {
    scanf("%d", &n);
}

int reverse(int n) {
    int res = 0;
    while (n) {
        res = res * 10 + n % 10;
        n /= 10;
    }
    return res;
}

void work() {
    printf("%d\n", n + reverse(n));
}

int main() {
    read();
    work();
    return 0;
}

AC 代码

#include <stdio.h>

int n;

void read() {
    scanf("%d", &n);
}

int reverse(int n) {
    int res = 0;
    while (n) {
        res = res * 10 + n % 10;
        n /= 10;
    }
    return res;
}

void work() {
    printf("%d\n", n + reverse(n));
}

int main() {
    read();
    work();
    return 0;
}

字符串碎片

字符串碎片

Description

三个由小写字母组成的字符串可以当作1些同一字母的最大碎片组成的。例如,”aaabbaaac”是由下边碎片组成的:’aaa’,’bb’,’c’。牛牛今后加以多个字符串,请您扶助总结这一个字符串的有所碎片的平均长度是有些。

Description

1个由小写字母组成的字符串能够看成1些同一字母的最大碎片组成的。例如,”aaabbaaac”是由下边碎片组成的:’aaa’,’bb’,’c’。牛牛以往加以3个字符串,请你帮忙总括这么些字符串的具备碎片的平均长度是稍稍。

Input

输入包蕴1个字符串s,字符串s的长短length(一 ≤ length ≤
50),s只含小写字母(‘a’-‘z’)

Input

输入包含叁个字符串s,字符串s的尺寸length(壹 ≤ length ≤
50),s只含小写字母(‘a’-‘z’)

Output

出口2个整数,表示拥有碎片的平分长度,四舍伍入保留两位小数。

如样例所示: s = “aaabbaaac”
负有碎片的平均长度 = (三 + 2 + 3 + 一) / 四 = 二.25

Output

出口三个平头,表示拥有碎片的平分长度,四舍5入保留两位小数。

如样例所示: s = “aaabbaaac”
具有碎片的平分长度 = (3 + 二 + 三 + 一) / 4 = 贰.25

Sample Input

aaabbaaac

Sample Input

aaabbaaac

Sample Output

2.25

Sample Output

2.25

解题思路

水题,全部块的总司长度正是字符串的尺寸,数1晃有稍许块。

解题思路

水题,全数块的总厅长度正是字符串的长度,数一眨眼有微微块。

AC 代码

#include <stdio.h>

char str[55];

void read() {
    scanf("%s", str);
}

void work() {
    int cnt = 1, i;
    for (i = 1; str[i]; ++i) {
        if (str[i] != str[i-1]) {
            ++cnt;
        }
    }
    double res = (double)(i) / cnt;
    printf("%.2lf\n", res);
}

int main() {
    read();
    work();
    return 0;
}

AC 代码

#include <stdio.h>

char str[55];

void read() {
    scanf("%s", str);
}

void work() {
    int cnt = 1, i;
    for (i = 1; str[i]; ++i) {
        if (str[i] != str[i-1]) {
            ++cnt;
        }
    }
    double res = (double)(i) / cnt;
    printf("%.2lf\n", res);
}

int main() {
    read();
    work();
    return 0;
}

骑行魔法王国

漫游魔法王国

Description

魔法王国壹共有n个城市,编号为0~n-壹号,n个城市里面的道路连接起来恰好构成壹棵树。
小易现在在0号都市,每便行动小易会从近来所在的都会走到与其隔壁的多少个都市,小易最多能行动L次。
若是小易到达过有个别城市就视为小易游历过那么些城市了,小易以往要制定好的畅游安排使她能旅游最多的都市,请您帮他盘算一下他最多能游历过些微个城市(注意0号都市已经游历了,游历过的都会不另行总结)。

Description

魔法王国1共有n个城市,编号为0~n-一号,n个城市之间的征程连接起来恰好构成1棵树。
小易未来在0号都市,每便行动小易会从如今所在的都会走到与其相邻的三个都市,小易最多能行动L次。
若果小易到达过有些城市就视为小易游历过这一个城池了,小易今后要制定好的畅游布署使她能旅游最多的都市,请你帮他盘算一下他最多能游历过些微个城市(注意0号都市已经游历了,游历过的都会不另行总计)。

Input

输入包涵两行,第三行李包裹含七个正整数n(2 ≤ n ≤ 50)和L(一 ≤ L ≤
100),表示城市个数和小易能走路的次数。
其次行李包裹罗n-一个整数parenti,
对于各种合法的i(0 ≤ i ≤ n –
二),在(i+一)号都市和parent[i]间有一条道路连接。

Input

输入包含两行,第三行包罗四个正整数n(二 ≤ n ≤ 50)和L(一 ≤ L ≤
十0),表示城市个数和小易能走路的次数。
第1行李包裹罗n-一个整数parenti,
对于每一个合法的i(0 ≤ i ≤ n –
二),在(i+一)号都市和parent[i]间有一条道路连接。

Output

输出3个整数,表示小易最多能游历的都市数据。

Output

输出一个整数,表示小易最多能游历的都会数据。

Sample Input

5 2
0 1 2 3

Sample Input

5 2
0 1 2 3

Sample Output

3

Sample Output

3

解题思路

本来觉得是树上 dp ,其实是名缰利锁。

画个图能够通晓,可把 parent[i] 当作 (i+1) 的阿爹节点(因为
parent[i] 是能够另行的)。在此以前看漏了 parent[i]
的范围限制了父节点标号比子节点小 这么些规格,作者用了 链式前向星 来建图。

建好图之后,就足以从树根扩散出每一种节点所在最长树链的长度,选出最长的一条树链,记其尺寸为
maxLen 。

分拣研商:

  • 若 L ≤ maxLen ,综上可得得结果;
  • 若 L > maxLen
    ,意味着可未来回走,要精晓越短的树链往回走的代价越低。借使从前边往回走,消耗的代价十一分高,最坏意况是较短的树链都接连在最远的根须上,整条最长链都要回走;倘诺已经理解最终步数会有剩余,则足以先开销富余的步数走短链,最终才走最长链;
  • 此起彼伏对 rest = L – maxLen 实行座谈:
    • 若树链上设有有些节点有所另一条子链,其长度 x
      必定小于或等于该祖先到原链末端的长短,旁观树链上各样节点到叶子的一条最短子链

      • 当 x > rest/2 可以在半路预先用掉 rest 步而不影响要走的
        maxLen 最长链,可达城市扩展 rest/二 个;
      • 当 x ≤ rest/贰 能够在中途预先用掉 2x 步而不影响要走的 maxLen
        最长链,可达城市扩张 x 个;
      • 当所有的 x 总和 sum(x) ≤ rest/贰表达富余的步数丰富把最短链到次最长链都走2遍,可达城市为一体
        n 个。
    • 本小节研究可见 rest/2 决定了能多走的城市数目,总共能走 min(n,
      1 + rest/二 + maxLen) 个城市。

解题思路

原来认为是树上 dp ,其实是贪心。

画个图能够领略,可把 parent[i] 当作 (i+1) 的爹爹节点(因为
parent[i] 是能够再度的)。从前看漏了 parent[i]
的限量限定了父节点标号比子节点小 这一个条件,笔者用了 链式前向星 来建图。

建好图之后,就能够从树根扩散出每种节点所在最长树链的尺寸,选出最长的一条树链,记其尺寸为
maxLen 。

分拣探讨:

  • 若 L ≤ maxLen ,综上可得得结果;
  • 若 L > maxLen
    ,意味着可以后回走,要明白越短的树链往回走的代价越低。假诺从后边往回走,消耗的代价十二分高,最坏意况是较短的树链都一而再在最远的树根上,整条最长链都要回走;假诺已经知晓最终步数会有剩余,则能够先花费富余的步数走短链,最终才走最长链;
  • 三番五次对 rest = L – maxLen 进行座谈:
    • 若树链上存在某些节点有所另一条子链,其尺寸 x
      必定小于或等于该祖先到原链末端的长度,考查树链上各样节点到叶子的一条最短子链

      • 当 x > rest/2 能够在半路预先用掉 rest 步而不影响要走的
        maxLen 最长链,可达城市增添 rest/二 个;
      • 当 x ≤ rest/二 能够在半路预先用掉 二x 步而不影响要走的 maxLen
        最长链,可达城市增添 x 个;
      • 当全部的 x 总和 sum(x) ≤ rest/2表明富余的步数丰盛把最短链到次最长链都走贰次,可达城市为任何
        n 个。
    • 本小节议论可见 rest/2 决定了能多走的都会数据,总共能走 min(n,
      壹 + rest/2 + maxLen) 个都市。

AC 代码

#include <stdio.h>
#include <string.h>

#define MAXN 55
#define MAXM 55

inline void getMax(int& n, int x) {
    n < x && (n = x);
}

inline void getMin(int& n, int x) {
    n > x && (n = x);
}

struct Edge {
    int to;
    int next;
} edge[MAXM];

int cnt;
int head[MAXN], len[MAXN];

void init() {
    memset(head, 0xff, sizeof(head));
}

void addEdge(int u, int v) {
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

int n, L;

void read() {
    int parent;
    scanf("%d%d", &n, &L);
    for (int i = 1; i < n; ++i) {
        scanf("%d", &parent);
        addEdge(parent, i);
    }
}

void walk(int u) {
    for (int i = head[u]; ~i; i = edge[i].next) {
        len[edge[i].to] = len[u] + 1;
        walk(edge[i].to);
    }
}

void work() {
    walk(0);
    int maxLen = 0;
    for (int i = 0; i < n; ++i) {
        getMax(maxLen, len[i]);
    }
    if (L <= maxLen) {
        printf("%d\n", L + 1);
    } else {
        int res = n;
        getMin(res, maxLen + (L - maxLen) / 2 + 1);
        printf("%d\n", res);
    }
}

int main() {
    init();
    read();
    work();
    return 0;
}

AC 代码

#include <stdio.h>
#include <string.h>

#define MAXN 55
#define MAXM 55

inline void getMax(int& n, int x) {
    n < x && (n = x);
}

inline void getMin(int& n, int x) {
    n > x && (n = x);
}

struct Edge {
    int to;
    int next;
} edge[MAXM];

int cnt;
int head[MAXN], len[MAXN];

void init() {
    memset(head, 0xff, sizeof(head));
}

void addEdge(int u, int v) {
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

int n, L;

void read() {
    int parent;
    scanf("%d%d", &n, &L);
    for (int i = 1; i < n; ++i) {
        scanf("%d", &parent);
        addEdge(parent, i);
    }
}

void walk(int u) {
    for (int i = head[u]; ~i; i = edge[i].next) {
        len[edge[i].to] = len[u] + 1;
        walk(edge[i].to);
    }
}

void work() {
    walk(0);
    int maxLen = 0;
    for (int i = 0; i < n; ++i) {
        getMax(maxLen, len[i]);
    }
    if (L <= maxLen) {
        printf("%d\n", L + 1);
    } else {
        int res = n;
        getMin(res, maxLen + (L - maxLen) / 2 + 1);
        printf("%d\n", res);
    }
}

int main() {
    init();
    read();
    work();
    return 0;
}

重排数列

重排数列

Description

小易有1个长短为N的正整数数列A = {A[1], A[2], A[3]…, A[N]}。
牛硕士给小易出了二个难点:
对数列A进行重新排列,使数列A满足全数的A[i] * A[i + 1] (1 ≤ i ≤ N –
1)都是4的倍数。
小易今后亟待判定贰个数列是还是不是足以重排之后满意牛博士的渴求。

Description

小易有一个长短为N的正整数数列A = {A[1], A[2], A[3]…, A[N]}。
牛大学生给小易出了多少个难题:
对数列A举办重新排列,使数列A满足全体的A[i] * A[i + 1] (1 ≤ i ≤ N –
1)都是4的倍数。
小易将来须求看清叁个数列是不是能够重排之后满足牛学士的渴求。

Input

输入的率先作为数列的个数t(壹 ≤ t ≤ 10),
接下去每两行描述2个数列A,第贰行为数列长度n(一 ≤ n ≤ 十^五)
其次行事n个正整数Ai

Input

输入的率先表现数列的个数t(一 ≤ t ≤ 10),
接下去每两行描述三个数列A,第二作为数列长度n(一 ≤ n ≤ 十^伍)
其次表现n个正整数Ai

Output

对此每种数列输出一行表示是还是不是足以满意牛大学生要求,如若能够输出Yes,否则输出No。

Output

对于各种数列输出1行表示是不是足以满意牛硕士须要,假若得以输出Yes,不然输出No。

Sample Input

2
3
1 10 100
4
1 2 3 4

Sample Input

2
3
1 10 100
4
1 2 3 4

Sample Output

Yes
No

Sample Output

Yes
No

解题思路

分拣探讨下。

  • 有目共睹,任意数和 四 的倍数相乘,其结果仍是 4 的翻番;
  • 众人,若存在任意数量 2 的翻番,两两中间乘起来正是 四 的翻番;
  • 只要存在一个数不是 二 的翻番,即它是七个奇数:
    • 身处 二 的倍数旁边,一定不符合供给;
    • 置身 肆 的翻番旁边,相乘结果仍是 四 的倍数。

故而符合需求的排列分三种情况:

  1. 存在 二 的翻番,全数 二 的倍数相邻排列,须要三个 四的翻番连接剩下的数,奇数最多和 四 的翻番数量相等,供给countMod四 >= countOdd
  2. 并未有 二 的倍数,原本放 二 的翻番一端能够改放3个奇数,countMod4 >=
    countOdd – 一

解题思路

分拣研商下。

  • 举世闻名,任意数和 四 的翻番相乘,其结果仍是 肆 的翻番;
  • 芸芸众生,若存在任意数量 2 的倍数,两两里边乘起来就是 四 的翻番;
  • 如若存在三个数不是 2 的翻番,即它是1个奇数:
    • 位于 2 的倍数旁边,一定不符合要求;
    • 位居 四 的翻番旁边,相乘结果仍是 四 的倍数。

故而符合要求的排列分三种情况:

  1. 存在 2 的翻番,全数 2 的翻番相邻排列,供给三个 四的倍数连接剩下的数,奇数最多和 四 的翻番数量格外,要求countMod4 >= countOdd
  2. 从未有过 贰 的倍数,原本放 二 的翻番一端能够改放三个奇数,countMod四 >=
    countOdd – 1

AC 代码

#include <stdio.h>

int n;
int arr[100100];

int countMod4, countMod2;

void read() {
    countMod4 = 0;
    countMod2 = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", arr + i);
        if (arr[i] % 4 == 0) {
            ++countMod4;
        } else if (arr[i] % 2 == 0) {
            ++countMod2;
        }
    }
}

void work() {
    int countOdd = n - countMod4 - countMod2;
    if ((n == 1 && countMod4) || countMod4 >= countOdd - !countMod2) {
        puts("Yes");
    } else {
        puts("No");
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        read();
        work();
    }
    return 0;
}

AC 代码

#include <stdio.h>

int n;
int arr[100100];

int countMod4, countMod2;

void read() {
    countMod4 = 0;
    countMod2 = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", arr + i);
        if (arr[i] % 4 == 0) {
            ++countMod4;
        } else if (arr[i] % 2 == 0) {
            ++countMod2;
        }
    }
}

void work() {
    int countOdd = n - countMod4 - countMod2;
    if ((n == 1 && countMod4) || countMod4 >= countOdd - !countMod2) {
        puts("Yes");
    } else {
        puts("No");
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        read();
        work();
    }
    return 0;
}

最长公共子括号体系

最长公共子括号体系

Description

3个官方的括号相配种类被定义为:

  1. 空白””是官方的括号种类
  2. 比方”X”和”Y”是官方的体系,那么”XY”也是一个合法的括号连串
  3. 只要”X”是2个法定的队列,那么”(X)”也是一个官方的括号系列
  4. 每一个合法的括号连串都足以由地点的规则变更
    比如””, “()”, “()()()”, “(()())”, “(((()))”都是合法的。
    从1个字符串S中移除零个依旧多个字符获得的队列称为S的子连串。
    比如说”abcde”的子系列有”abe”,””,”abcde”等。
    定义LCS(S,T)为字符串S和字符串T最长公共子类别的尺寸,即二个最长的队列W既是S的子系列也是T的子体系的长短。
    小易给出一个合法的括号相配类别s,小易希望您能找出全体以下特征的括号种类t:
    一、t跟s不一致,不过长度相同
    2、t也是1个法定的括号匹配系列
    3、LCS(s, t)是满意上述八个条件的t中最大的
    因为那样的t大概存在三个,小易需求您计算出知足条件的t有多少个。

如样例所示: s = “(())()”,跟字符串s长度相同的合法括号相称种类有:
“()(())”, “((()))”, “()()()”, “(()())”,个中LCS( “(())()”, “()(())”
)为4,其余八个都为伍,所以输出叁.

Description

三个官方的括号相称种类被定义为:

  1. 空白””是官方的括号种类
  2. 就算”X”和”Y”是官方的行列,那么”XY”也是一个法定的括号连串
  3. 假定”X”是一个法定的连串,那么”(X)”也是三个合法的括号种类
  4. 各样合法的括号体系都得以由地点的平整变更
    比如说””, “()”, “()()()”, “(()())”, “(((()))”都以法定的。
    从叁个字符串S中移除零个依旧八个字符得到的队列称为S的子种类。
    比如”abcde”的子类别有”abe”,””,”abcde”等。
    定义LCS(S,T)为字符串S和字符串T最长公共子种类的长度,即2个最长的队列W既是S的子体系也是T的子类别的长短。
    小易给出一个官方的括号相配种类s,小易希望你能找出富有以下特点的括号连串t:
    一、t跟s不一致,不过长度相同
    2、t也是1个法定的括号相称连串
    叁、LCS(s, t)是满意上述四个标准的t中最大的
    因为如此的t恐怕存在三个,小易需求您总计出知足条件的t有多少个。

如样例所示: s = “(())()”,跟字符串s长度相同的法定括号相称连串有:
“()(())”, “((()))”, “()()()”, “(()())”,个中LCS( “(())()”, “()(())”
)为四,其余多个都为5,所以输出叁.

Input

输入包蕴字符串s(4 ≤ |s| ≤
50,|s|表示字符串长度),保障s是叁个官方的括号相配系列。

Input

输入包蕴字符串s(四 ≤ |s| ≤
50,|s|表示字符串长度),有限协理s是贰个法定的括号相称类别。

Output

出口3个正整数,满意条件的t的个数。

Output

出口多个正整数,满足条件的t的个数。

Sample Input

(())()

Sample Input

(())()

Sample Output

3

Sample Output

3

解题思路

依据题意,当且仅当修改距离为 1 时 LCS 最大。很不难证明对于二种为主体系(()) 和 ()() 都有距离为 一 的合法修改。
原先想的是对各样左括号,跟每种右括号轮换,判断合法后共计。
后来发觉会挂一漏万1些状态,那就武力得干脆一点,把各种符号插入到自由地点,判合法,去重,累计。

解题思路

依据题意,当且仅当修改距离为 1 时 LCS 最大。很简单注脚对于三种为主类别(()) 和 ()() 都有距离为 一 的官方修改。
原先想的是对各类左括号,跟每种右括号轮换,判断合法后共计。
新生察觉会挂壹漏万一些情景,那就武力得干脆一点,把各样符号插入到自由位置,判合法,去重,累计。

AC 代码

#include <stdio.h>
#include <algorithm>
#include <string>
#include <set>

using namespace std;

char str[55];

void read() {
    scanf("%s", str);
}

bool test(const string& s) {
    int cnt = 0;
    for (int i = 0; s[i]; ++i) {
        s[i] == '(' ? ++cnt : --cnt;
        if (cnt < 0) {
            return false;
        }
    }
    return true;
}

void work() {
    set<string> record;
    for (int i = 1; str[i+1]; ++i) {
        string tmp(str);
        tmp.erase(i, 1);
        for (int j = 1; str[j]; ++j) {
            if (str[i] == str[j]) continue;
            string s(tmp);
            s.insert(j, 1, str[i]);
            if (test(s)) {
                record.insert(s);
            }
        }
    }
    printf("%lu\n", record.size());
}

int main() {
    read();
    work();
    return 0;
}

AC 代码

#include <stdio.h>
#include <algorithm>
#include <string>
#include <set>

using namespace std;

char str[55];

void read() {
    scanf("%s", str);
}

bool test(const string& s) {
    int cnt = 0;
    for (int i = 0; s[i]; ++i) {
        s[i] == '(' ? ++cnt : --cnt;
        if (cnt < 0) {
            return false;
        }
    }
    return true;
}

void work() {
    set<string> record;
    for (int i = 1; str[i+1]; ++i) {
        string tmp(str);
        tmp.erase(i, 1);
        for (int j = 1; str[j]; ++j) {
            if (str[i] == str[j]) continue;
            string s(tmp);
            s.insert(j, 1, str[i]);
            if (test(s)) {
                record.insert(s);
            }
        }
    }
    printf("%lu\n", record.size());
}

int main() {
    read();
    work();
    return 0;
}

合唱

合唱

Description

小Q和牛博士合唱壹首歌曲,那首歌曲由n个音调组成,每一种音调由1个正整数表示。
对此每种音调要么由小Q演唱要么由牛博士演唱,对于一雨后苦笋音调集会演唱的难度非常全体相邻音调变化幅度之和,
例如二个调子种类是八, 八, 13, 1二, 那么它的难度格外|八 – 8| + |1叁 – 八| + |1二

  • 1三| = 陆(在那之中||表示绝对值)。
    于今要对把那n个调子分配给小Q或牛大学生,让她们演唱的难度之和微小,请你算算最小的难度和是某些。
    如样例所示: 小Q选择演唱{5, 陆}难度为一, 牛大学生采用演唱{1, 二,
    一}难度为二,难度之和为三,那1个是纤维难度和的方案了。

Description

小Q和牛大学生合唱一首歌曲,那首歌曲由n个音调组成,每一种音调由1个正整数表示。
对此各个音调要么由小Q演唱要么由牛博士演唱,对于壹多级音调集会演唱的难度1二分全部相邻音调变化幅度之和,
例如一个调子类别是八, 八, 一三, 1二, 那么它的难度卓殊|8 – 8| + |壹三 – 8| + |1贰

  • 壹叁| = 陆(个中||表示相对值)。
    方今要对把这n个调子分配给小Q或牛博士,让他们演唱的难度之和微小,请您算算最小的难度和是稍稍。
    如样例所示: 小Q选用演唱{伍, 陆}难度为一, 牛大学生采纳演唱{一, 2,
    1}难度为二,难度之和为3,那2个是纤维难度和的方案了。

Input

输入包含两行,第3行三个正整数n(一 ≤ n ≤ 两千)
第一行n个整数vi,
表示每种音调。

Input

输入包含两行,第3行贰个正整数n(1 ≤ n ≤ 三千)
第3行n个整数vi,
表示各个音调。

Output

输出1个平头,表示小Q和牛大学生演唱最小的难度和是多少。

Output

输出2个平头,表示小Q和牛硕士演唱最小的难度和是有点。

Sample Input

5
1 5 6 2 1

Sample Input

5
1 5 6 2 1

Sample Output

3

Sample Output

3

解题思路

正推的话,不难想到一位一连演唱或换人演唱的时候发出事态转移:

  • 设 dp[i][j] 表示如今小Q唱到第 i 个调子,牛大学生唱到第 j
    个调子的难度和;
  • 无妨设当前 i > j :
    • 若 i – 一 == j 则发出换人,由于不明了上二遍 i 唱到哪个地方,状态由
      min{ dp[k][j] + abs(v[i] – v[k]) }, k < j 转移来;
    • 若 i – 壹 > j 则意味如今是从 i – 一 唱到 i 的,未有换人,状态由
      dp[i-1][j] + abs(v[i] – v[i-1]) 累加;
  • 不妨设 dp[i][j] 表示近年来演唱到第 i 个,上1位演唱到第 j
    个,则状态转移方程为
    dp[i][j] = dp[i-1][j] + abs(v[i] – v[i-1]), j < i –
    1
    dp[i][i -1] = min{ dp[i-1][k] + abs(v[i] – v[k]) }, k
    < i – 1
  • 边界景况是1个人唱第二个,前面全部音调让另一人唱
    dp[i][0] = dp[i-1][0] + abs(v[i] – v[i-1]), i ≥ 2
    可能一个人唱前边全数音调,最终三个调子让另一个人唱
    dp[i][i-1] = dp[i-1][i-2] + abs(v[i-1] – v[i-2]), i ≥ 2

反推:

  • 设 dp[i][j] 表示从脚下小Q唱到第 i + 一 个调子,牛硕士唱到第 j + 3个调子开始,直到全部音调集会演唱完的难度和;边界情形 i = 0 或 j = 0
    表示一位还没开端唱;
  • 简单理解下二个音调 next = max{ i, j } ,若让小Q唱下1个调子,会取得
    abs(v[next] – v[i]) 的孝敬;若让牛学士唱会赢得 abs(v[next] –
    v[j]) 的贡献;
  • 情景转移方程
    dp[i][j] = min{ dp[next][j] + abs(v[next] – v[i]),
    dp[i][next] + abs(v[next] – v[j]) }, i ≠ j < n

解题思路

正推的话,不难想到1位一而再演唱或换人演唱的时候产生景况转移:

  • 设 dp[i][j] 表示方今小Q唱到第 i 个调子,牛博士唱到第 j
    个调子的难度和;
  • 无妨设当前 i > j :
    • 若 i – 一 == j 则发出换人,由于不知晓上三次 i 唱到何地,状态由
      min{ dp[k][j] + abs(v[i] – v[k]) }, k < j 转移来;
    • 若 i – 一 > j 则表示近期是从 i – 一 唱到 i 的,未有换人,状态由
      dp[i-1][j] + abs(v[i] – v[i-1]) 累加;
  • 不妨设 dp[i][j] 表示最近演唱到第 i 个,上一位演唱到第 j
    个,则状态转移方程为
    dp[i][j] = dp[i-1][j] + abs(v[i] – v[i-1]), j < i –
    1
    dp[i][i -1] = min{ dp[i-1][k] + abs(v[i] – v[k]) }, k
    < i – 1
  • 分界意况是一人唱第贰个,后边全数音调让另1个人唱
    dp[i][0] = dp[i-1][0] + abs(v[i] – v[i-1]), i ≥ 2
    照旧一人唱前面全数音调,最终2个调子让另1位唱
    dp[i][i-1] = dp[i-1][i-2] + abs(v[i-1] – v[i-2]), i ≥ 2

反推:

  • 设 dp[i][j] 表示从当下小Q唱到第 i + 一 个调子,牛博士唱到第 j + 三个调子早先,直到全部音调集会演唱完的难度和;边界景况 i = 0 或 j = 0
    表示一人还没起来唱;
  • 不难精晓下四个音调 next = max{ i, j } ,若让小Q唱下2个调子,会赢得
    abs(v[next]365体育官网, – v[i]) 的贡献;若让牛博士唱会取得 abs(v[next] –
    v[j]) 的贡献;
  • 状态转移方程
    dp[i][j] = min{ dp[next][j] + abs(v[next] – v[i]),
    dp[i][next] + abs(v[next] – v[j]) }, i ≠ j < n

AC 代码

正推:

#include <stdio.h>
#include <stdlib.h>

typedef long long llong;

inline void getMin(llong& n, llong x) {
    n > x && (n = x);
}

#define MAXN 2020

int n;
int v[MAXN], cost[MAXN];

void read() {
    scanf("%d%d", &n, v);
    for (int i = 1; i < n; ++i) {
        scanf("%d", v + i);
        cost[i] = abs(v[i] - v[i - 1]);
    }
}

llong dp[MAXN][MAXN];

void work() {
    llong res = (1ll << 63) - 1;
    for (int i = 2; i < n; ++i) {
    //    dp[i][0] = dp[i - 1][0] + cost[i];
        dp[i][i - 1] = dp[i - 1][i - 2] + cost[i - 1];
    }
    for (int i = 2; i < n; ++i) {
        for (int j = 0; j < i - 1; ++j) {
            dp[i][j] = dp[i - 1][j] + cost[i];
            getMin(dp[i][i - 1], dp[i - 1][j] + abs(v[i] - v[j]));
        }
    }
    for (int i = 0; i < n - 1; ++i) {
        getMin(res, dp[n - 1][i]);
    }
    printf("%lld\n", res);
}

int main() {
    read();
    work();
    return 0;
}

反推要做1些改观:

using std::max;
using std::min;

int n, v[MAXN];

void read() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", v + i);
    }
}

int cost(int a, int b) {
    return a && b ? abs(v[a] - v[b]) : 0;
}

纪念化递归搜索:

llong solve(int i, int j) {
    int next = max(i, j) + 1;
    if (next == n + 1) {
        return 0;
    }
    if (!~dp[i][j]) {
        dp[i][j] = min(solve(next, j) + cost(next, i), solve(i, next) + cost(next, j));
    }
    return dp[i][j];
}

void work() {
    memset(dp, 0xff, sizeof(dp));
    llong res = solve(0, 0);
    printf("%lld\n", res);
}

用循环更简单:

void work() {
    for (int i = n - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 0; --j) {
            int next = max(i, j) + 1;
            dp[i][j] = min(dp[next][j] + cost(next, i), dp[i][next] + cost(next, j));
        }
    }
    printf("%lld\n", dp[0][0]);
}

正文基于
365体育官网 1文化共享署名-非商业性利用-相同方法共享
4.0 国际许可协议

宣布,欢迎引用、转发或演绎,然而必须保留本文的签字
BlackStorm
以及本文链接 http://www.cnblogs.com/BlackStorm/p/7499974.html
,且未经许可不能够用于生意指标。如有疑问或授权协商请
与本人联系

AC 代码

正推:

#include <stdio.h>
#include <stdlib.h>

typedef long long llong;

inline void getMin(llong& n, llong x) {
    n > x && (n = x);
}

#define MAXN 2020

int n;
int v[MAXN], cost[MAXN];

void read() {
    scanf("%d%d", &n, v);
    for (int i = 1; i < n; ++i) {
        scanf("%d", v + i);
        cost[i] = abs(v[i] - v[i - 1]);
    }
}

llong dp[MAXN][MAXN];

void work() {
    llong res = (1ll << 63) - 1;
    for (int i = 2; i < n; ++i) {
    //    dp[i][0] = dp[i - 1][0] + cost[i];
        dp[i][i - 1] = dp[i - 1][i - 2] + cost[i - 1];
    }
    for (int i = 2; i < n; ++i) {
        for (int j = 0; j < i - 1; ++j) {
            dp[i][j] = dp[i - 1][j] + cost[i];
            getMin(dp[i][i - 1], dp[i - 1][j] + abs(v[i] - v[j]));
        }
    }
    for (int i = 0; i < n - 1; ++i) {
        getMin(res, dp[n - 1][i]);
    }
    printf("%lld\n", res);
}

int main() {
    read();
    work();
    return 0;
}

反推要做一些改成:

using std::max;
using std::min;

int n, v[MAXN];

void read() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", v + i);
    }
}

int cost(int a, int b) {
    return a && b ? abs(v[a] - v[b]) : 0;
}

回忆化递归搜索:

llong solve(int i, int j) {
    int next = max(i, j) + 1;
    if (next == n + 1) {
        return 0;
    }
    if (!~dp[i][j]) {
        dp[i][j] = min(solve(next, j) + cost(next, i), solve(i, next) + cost(next, j));
    }
    return dp[i][j];
}

void work() {
    memset(dp, 0xff, sizeof(dp));
    llong res = solve(0, 0);
    printf("%lld\n", res);
}

用循环更简便:

void work() {
    for (int i = n - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 0; --j) {
            int next = max(i, j) + 1;
            dp[i][j] = min(dp[next][j] + cost(next, i), dp[i][next] + cost(next, j));
        }
    }
    printf("%lld\n", dp[0][0]);
}

本文基于
365体育官网 2文化共享署名-非商业性利用-相同方式共享
4.0 国际许可协议

发表,欢迎引用、转载或演绎,可是必须保留本文的签字
BlackStorm
以及本文链接 http://www.cnblogs.com/BlackStorm/p/7499974.html
,且未经许可无法用来生意目的。如有疑问或授权协商请
与自小编关系

相关文章