头像

以梦为马


访客:6929

离线:11小时前



以梦为马
2个月前

题目描述

X星球的考古学家发现了一批古代留下来的密码。

这些密码是由A、B、C、D 四种植物的种子串成的序列。

仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的镜像串)。

由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。

你的任务是:

给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。

输入格式

共一行,包含一个由大写字母ABCD构成的字符串,表示现在看到的密码串。

输出格式

输出一个整数,表示至少脱落了多少个种子。

数据范围

输入字符串长度不超过1000

输入样例1:

ABCBA

输出样例1:

0

输入样例2:

ABDCDCBABC

输出样例2:

3

解题思路

动态规划            ------ 闫氏dp分析法

状态表示: f[l][r]
           集合:区间 [l, r] 所有子序列的长度的集合
           属性:最大值

状态计算:         ------- 集合的划分
           根据l, r 与区间 [l, r] 的位置关系进行划分
           1. l, r 均在区间 [l, r] 之中 if s[l] = = s[r] f[l][r] = f[l + 1][r - 1] + 2;
           2. l在区间 [l, r] 之中, f[l][r] = f[l, r - 1]
           3. r在区间 [l, r] 之中, f[l][r] = f[l + 1, r]
           4. l, r均不在区间 [l, r] 之中, f[l][r] = f[l + 1][r - 1]



C ++ 代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

char s[N];
int f[N][N];//区间 [l, r] 中所有子序列的最大长度

int main(){
    scanf("%s", s);

    int n = strlen(s);

    for(int len = 1; len <= n; len ++){
        for(int l = 0; l + len - 1 < n; l ++){
            int r = l + len - 1;
            if(len == 1) f[l][r] = 1;
            else{
                if(s[l] == s[r]) f[l][r] = f[l + 1][r - 1] + 2;
                f[l][r] = max(f[l][r], f[l][r - 1]);
                f[l][r] = max(f[l][r], f[l + 1][r]);
            }
        }
    }

    printf("%d\n", n - f[0][n - 1]);

    return 0;
}



以梦为马
2个月前

题目描述

由于在维护世界和平的事务中做出巨大贡献,Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。

在这一天,Dzx可以从糖果公司的 N 件产品中任意选择若干件带回家享用。

糖果公司的 N 件产品每件都包含数量不同的糖果。

Dzx希望他选择的产品包含的糖果总数是 K 的整数倍,这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。

当然,在满足这一条件的基础上,糖果总数越多越好。

Dzx最多能带走多少糖果呢?

注意:Dzx只能将糖果公司的产品整件带走。

输入格式

第一行包含两个整数 N 和 K。

以下 N 行每行 1 个整数,表示糖果公司该件产品中包含的糖果数目,不超过 1000000。

输出格式

符合要求的最多能达到的糖果总数,如果不能达到 K 的倍数这一要求,输出 0。

数据范围

1≤N≤100,
1≤K≤100,

输入样例:

5 7
1
2
3
4
5

输出样例:

14

样例解释

Dzx的选择是2+3+4+5=14,这样糖果总数是7的倍数,并且是总数最多的选择。

解题思路

动态规划     ---- 闫式DP分析法

状态表示: f[i][j] 
           集合:从i个数中选总和模k为j的方案
           属性:最大值

状态计算:   ---- 集合的划分
           划分依据:是否包含第i个数
           1.包含第i个数        ---- f[i - 1, j - w % k] + w
           2.不包含第i个数      ---- f[i - 1][j]

C++ 代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, k;
int f[N][N];//从i个数中选总数模k为j的方案中的最大值

int main(){
    scanf("%d%d", &n, &k);

    memset(f, -0x3f, sizeof f);//f[0][1]、f[0][2]···无意义
    f[0][0] = 0;
    for(int i = 1; i <= n; i ++){
        int w;
        scanf("%d", &w);
        for(int j = 0; j <= k; j ++){
            f[i][j] = f[i - 1][j];
            f[i][j] = max(f[i][j], f[i - 1][(j - w % k + k ) % k] + w);
        }
    }

    printf("%d\n", f[n][0]);

    return 0;
}



以梦为马
2个月前

题目描述

在火影忍者的世界里,令敌人捉摸不透是非常关键的。

我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。

影分身是由鸣人身体的查克拉能量制造的,使用的查克拉越多,制造出的影分身越强。

针对不同的作战情况,鸣人可以选择制造出各种强度的影分身,有的用来佯攻,有的用来发起致命一击。

那么问题来了,假设鸣人的查克拉能量为 M,他影分身的个数最多为 N,那么制造影分身时有多少种不同的分配方法?

注意:

影分身可以分配0点能量。
分配方案不考虑顺序,例如:M=7,N=3,那么 (2,2,3) 和 (2,3,2) 被视为同一种方案。
输入格式
第一行是测试数据的数目 t。

以下每行均包含二个整数 M 和 N,以空格分开。

输出格式

对输入的每组数据 M 和 N,用一行输出分配的方法数。

数据范围

0≤t≤20,
1≤M,N≤10

输入样例:

1
7 3

输出样例:

8

解题思路

采用动态规划           ------- 闫氏分析法

状态表示:f[i][j] 
        集合:总和为i,且可以分j个的方案
        属性:方案的个数
状态计算:             --------集合的划分
        划分依据:方案中的数是否含0,分为两类
        第一类:含0方案. 表示为 f[i][j - 1]
        第二类:不含0方案. 将方案中的所有数减1,方案数与原方案等价, 表示为 f[i - j][j].

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 11;

int main(){
    int T;
    cin >> T;

    //f[i][j]表示总和为i,且分的个数为j所有的方案的个数。
    int f[N][N] = {0};
    f[0][0] = 1;

    int m, n;
    while(T --){
        cin >> m >> n;

        for(int i = 0; i <= m; i ++){
            for(int j = 1; j <= n; j ++){
                f[i][j] = f[i][j - 1];
                if(i >= j) f[i][j] += f[i - j][j];
            }
        }

        cout << f[m][n] << endl;
    }

    return 0;
}



以梦为马
2个月前

求n的第k位数字

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){
    int n, k;
    cin >> n >> k;

    cout << (n >> k & 1) << endl;//输出n对应的二进制数的第k位

    //将n对应的二进制数,从第k位~第0位依次输出
    for(int j = k; j >= 0; j --) cout << (n >> j & 1) << ' ';

    return 0;
}



以梦为马
2个月前

题目描述

n 个小朋友站成一排。

现在要把他们按身高从低到高的顺序排列,但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。

开始的时候,所有小朋友的不高兴程度都是 0。

如果某个小朋友第一次被要求交换,则他的不高兴程度增加 1,如果第二次要求他交换,则他的不高兴程度增加 2(即不高兴程度为 3),依次类推。当要求某个小朋友第 k 次交换时,他的不高兴程度增加 k。

请问,要让所有小朋友按从低到高排队,他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样,则他们谁站在谁前面是没有关系的。

输入格式

输入的第一行包含一个整数 n,表示小朋友的个数。

第二行包含 n 个整数 H1,H2,…,Hn,分别表示每个小朋友的身高。

输出格式

输出一行,包含一个整数,表示小朋友的不高兴程度和的最小值。

数据范围

1≤n≤100000,
0≤Hi≤1000000

输入样例:

3
3 2 1

输出样例:

9

样例解释
首先交换身高为3和2的小朋友,再交换身高为3和1的小朋友,再交换身高为2和1的小朋友,每个小朋友的不高兴程度都是3,总和为9。


C++代码 ---- 线段树求逆序对

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1000010;

int n;
int h[N];//记录小朋友身高
int tr[N];//下标为h[i]的值,用于记录每个该身高小朋友的个数
int sum[N];//记录每个小朋友对应的逆序对数

int lowbit(int x){
    return x & -x;
}

void add(int x, int v){
    for(int i = x; i < N; i += lowbit(i)) tr[i] += v;
}

int query(int x){
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main(){
    cin >> n;

    //h[i] ++ 是因为线段树小标要从1开始,因为tr[i] = (x - lowbit(x), x].
    for(int i = 1; i <= n; i ++) scanf("%d", &h[i]), h[i] ++;

    //求每个数前面有多少个数比他大
    for(int i = 1; i <= n; i ++){
        sum[i] = query(N - 1) - query(h[i]);
        add(h[i], 1);
    }

    //求每个数后面有多少个数比他小
    memset(tr, 0, sizeof tr);
    for(int i = n; i >= 1; i --){
        sum[i] += query(h[i] - 1);
        add(h[i], 1);
    }

    long long res = 0;
    for(int i = 1; i <= n; i ++) res += (1LL) * sum[i] * (sum[i] + 1) / 2;

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 604. 圆的面积

以梦为马
2个月前
#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

const double PI = 3.14159;

int main(){
    double r;
    scanf("%lf", &r);

    printf("A=%.4lf\n", PI * r * r);

    return 0;
}



以梦为马
2个月前

题目描述

小 h 前往美国参加了蓝桥杯国际赛。

小 h 的女朋友发现小 h 上午十点出发,上午十二点到达美国,于是感叹到“现在飞机飞得真快,两小时就能到美国了”。

小 h 对超音速飞行感到十分恐惧。

仔细观察后发现飞机的起降时间都是当地时间。

由于北京和美国东部有 12 小时时差,故飞机总共需要 14 小时的飞行时间。

不久后小 h 的女朋友去中东交换。

小 h 并不知道中东与北京的时差。

但是小 h 得到了女朋友来回航班的起降时间。

小 h 想知道女朋友的航班飞行时间是多少。

对于一个可能跨时区的航班,给定来回程的起降时间。

假设飞机来回飞行时间相同,求飞机的飞行时间。

输入格式

一个输入包含多组数据。

输入第一行为一个正整数 T,表示输入数据组数。

每组数据包含两行,第一行为去程的起降时间,第二行为回程的起降时间。

起降时间的格式如下:

h1:m1:s1 h2:m2:s2
h1:m1:s1 h3:m3:s3 (+1)
h1:m1:s1 h4:m4:s4 (+2)
第一种格式表示该航班在当地时间h1时m1分s1秒起飞,在当地时间当日h2时m2分s2秒降落。

第二种格式表示该航班在当地时间h1时m1分s1秒起飞,在当地时间次日h2时m2分s2秒降落。

第三种格式表示该航班在当地时间h1时m1分s1秒起飞,在当地时间第三日h2时m2分s2秒降落。

输出格式

对于每一组数据输出一行一个时间hh:mm:ss,表示飞行时间为hh小时mm分ss秒。

注意,当时间为一位数时,要补齐前导零,如三小时四分五秒应写为03:04:05。

数据范围

保证输入时间合法(0≤h≤23,0≤m,s≤59),飞行时间不超过24小时。

输入样例:

3
17:48:19 21:57:24
11:05:18 15:14:23
17:21:07 00:31:46 (+1)
23:02:41 16:13:20 (+1)
10:19:19 20:41:24
22:19:04 16:41:09 (+1)

输出样例:

04:09:05
12:10:39
14:22:05

解题思路

时差由东向西为减,由西向东为加
由于飞机往返飞行时间相同,所以可以列个飞机往返时间的等式
t2 - t1 - td = t4 - t3 + td
可以得到:时差td = ((t2 - t1) + (t4 - t3)) / 2

C++代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//将时间转化为秒
int get_seconds(int h, int m, int s){
    return h * 3600 + m * 60 + s;
}

//读取航班起降时间
int get_time(){
    string line;
    getline(cin, line);
    if(line.back() != ')') line += "(+0)";//便于统一处理时间
    int h1, m1, s1, h2, m2, s2, d;
    sscanf(line.c_str(), "%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &d);

    return get_seconds(h2, m2, s2) - get_seconds(h1, m1, s1) + d * 24 * 3600;
}

int main(){
    int n;
    cin >> n;
    cin.get();//滤去上次的回车键
    while(n --){
        int time = (get_time() + get_time()) / 2;
        int hour = time / 3600, minute = time % 3600 / 60, second = time % 60;
        printf("%02d:%02d:%02d\n", hour, minute, second);
    }

    return 0;
}



以梦为马
2个月前

题目描述

小明正在整理一批历史文献。这些历史文献中出现了很多日期。

小明知道这些日期都在1960年1月1日至2059年12月31日。

令小明头疼的是,这些日期采用的格式非常不统一,有采用年/月/日的,有采用月/日/年的,还有采用日/月/年的。

更加麻烦的是,年份也都省略了前两位,使得文献上的一个日期,存在很多可能的日期与其对应。

比如02/03/04,可能是2002年03月04日、2004年02月03日或2004年03月02日。

给出一个文献上的日期,你能帮助小明判断有哪些可能的日期对其对应吗?

输入格式

一个日期,格式是”AA/BB/CC”。

即每个’/’隔开的部分由两个 0-9 之间的数字(不一定相同)组成。

输出格式

输出若干个不相同的日期,每个日期一行,格式是”yyyy-MM-dd”。

多个日期按从早到晚排列。

数据范围

0≤A,B,C≤9

输入样例:

02/03/04

输出样例:

2002-03-04
2004-02-03
2004-03-02

C++代码

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

//判断日期是否合法
bool check_valid(int year, int month, int day){
    if(month == 0 || month > 12) return false;
    if(day == 0 || month != 2 && day > days[month]) return false;
    if(month == 2){
        int leap = year % 4 == 0 && year % 100 || year % 400 == 0;
        if(day > leap + 28) return false;
    }
    return true;
}

int main(){
    int a, b, c;
    scanf("%d/%d/%d", &a, &b, &c);

    for(int i = 19600101; i <= 20591231; i ++){//枚举所有日期
        int year = i / 10000, month = i % 10000 / 100, day = i % 100;
        if(check_valid(year, month, day)){//判断日期是否合法
            if(a == (year % 100) && b == month &&  c == day ||//年月日
            a == month && b == day && c == (year % 100)  || //月日年
            a == day && b == month && c == (year % 100) //日月年
            )
            printf("%d-%02d-%02d\n",year, month, day);
        }
    }

    return 0;
}



以梦为马
2个月前

题目描述

X星球居民小区的楼房全是一样的,并且按矩阵样式排列。

其楼房的编号为 1,2,3…
当排满一行时,从下一行相邻的楼往反方向排号。

比如:当小区排号宽度为 6 时,开始情形如下:

1 2 3 4 5 6
12 11 10 9 8 7
13 14 15 .....
我们的问题是:已知了两个楼号 m 和 n,需要求出它们之间的最短移动距离(不能斜线方向移动)。

输入格式

输入共一行,包含三个整数 w,m,n,w 为排号宽度,m,n 为待计算的楼号。

输出格式

输出一个整数,表示 m,n 两楼间最短移动距离。

数据范围

1≤w,m,n≤10000,

输入样例:

6 8 2

输出样例:

4

C++代码

#include <bits/stdc++.h>

using namespace std;

int main(){
    int w, m, n;
    cin >> w >> m >> n;
    m --, n --;//序号减1,便于利用公式求行号和列号

    int x1 = m / w, x2 = n / w;//行号
    int y1 = m % w, y2 = n % w;//求列号
    if(x1 & 1) y1 = w - 1 - y1;//特判,是否为奇数行
    if(x2 & 1) y2 = w - 1 - y2;

    //哈弗曼顿距离
    cout << abs(x1 - x2) +abs(y1 - y2) << endl;
    return 0;
}



以梦为马
3个月前

题目描述

在日常生活中,通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用 8 位数字表示一个日期,其中,前 4 位代表年份,接下来 2 位代表月份,最后 2 位代表日期。

显然:一个日期只有一种表示方法,而两个不同的日期的表示方法不会相同。

牛牛认为,一个日期是回文的,当且仅当表示这个日期的8位数字是回文的。

现在,牛牛想知道:在他指定的两个日期之间(包含这两个日期本身),有多少个真实存在的日期是回文的。

一个 8 位数字是回文的,当且仅当对于所有的 i(1≤i≤8) 从左向右数的第i个数字和第 9−i 个数字(即从右向左数的第 i 个数字)是相同的。

例如:

•对于2016年11月19日,用 8 位数字 20161119 表示,它不是回文的。

•对于2010年1月2日,用 8 位数字 20100102 表示,它是回文的。

•对于2010年10月2日,用 8 位数字 20101002 表示,它不是回文的。

输入格式

输入包括两行,每行包括一个8位数字。

第一行表示牛牛指定的起始日期date1,第二行表示牛牛指定的终止日期date2。保证date1和date2都是真实存在的日期,且年份部分一定为4位数字,且首位数字不为0。

保证date1一定不晚于date2。

输出格式

输出共一行,包含一个整数,表示在date1和date2之间,有多少个日期是回文的。

输入样例:

20110101
20111231

输出样例:

1

解题思路:

  1. 枚举回文数
  2. 判断是否在范围内
  3. 判断日期是否合法

C++ 代码

#include <bits/stdc++.h>

using namespace std;

//各月天数
int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

//判断日期是否合法
bool check_valid(int date){
    int year = date / 10000;
    int month = date % 10000 /100;
    int day = date % 100;

    if(month == 0 || month > 12) return false;
    if(day == 0 || month != 2 && day > days[month]) return false;

    if(month == 2){
        int leap = year % 100 && year % 4 == 0 || year % 400 == 0;
        if(day > 28 + leap) return false;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int date1, date2;
    cin >> date1 >> date2;

    int ans = 0;

    //枚举回文日期
    for(int i = 1000; i < 10000; i ++){
        int date = i, x = i;
        for(int j = 0; j < 4; j ++) date = date * 10 + x % 10, x /= 10; //转化为八位正常日期
        if(date1 <= date && date <= date2 && check_valid(date)) ans ++;//判断回文日期范围是否合法,判断回文日期是否合法
    }

    cout << ans << endl;
    return 0;
}