P8772 求和 P8716 回文日期

文章目录

[蓝桥杯 2022 省 A] 求和
[蓝桥杯 2020 省 AB2] 回文日期

[蓝桥杯 2022 省 A] 求和

题目描述

给定 $n$ 个整数 $a_{1}, a_{2}, \cdots, a_{n}$ , 求它们两两相乘再相加的和，即

$S=a_{1} \cdot a_{2}+a_{1} \cdot a_{3}+\cdots+a_{1} \cdot a_{n}+a_{2} \cdot a_{3}+\cdots+a_{n-2} \cdot a_{n-1}+a_{n-2} \cdot a_{n}+a_{n-1} \cdot a_{n}$

输入格式

输入的第一行包含一个整数 $n$ 。

第二行包含 $n$ 个整数 $a_{1}, a_{2}, \cdots a_{n}$ 。

输出格式

输出一个整数 $S$ ，表示所求的和。请使用合适的数据类型进行运算。

样例 #1

样例输入 #1

4
1 3 6 9

样例输出 #1

提示

对于 $\%$ 的数据, $\leq n \leq 1000,1 \leq a_{i} \leq 100$ 。

对于所有评测用例, $\leq n \leq 2\times10^5,1 \leq a_{i} \leq 1000$ 。

蓝桥杯 2022 省赛 A 组 C 题。

解题思路

我们将公因数提取出来后，就可以转换成 $a_{i}$ 与 $a_{i+1}, a_{i+2}, \cdots, a_{n}$ 的和的乘积，利用前缀和 && 差分就可以解决了。

具体操作就是将 $a_{1}, a_{2}, \cdots, a_{n}$ 的和 $s u m$ 计算出来，每次与 $a_{i}$ 相乘之前减去 $a_{i}$ ，将得到的数累加起来就可以得到答案。

#include <bits/stdc++.h>
using namespace std;
long long sum,ans,nums[200005],n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> nums[i];
        sum += nums[i];
    }
    
    for(int i = 1; i <= n; ++i)
    {
        sum -= nums[i];
        ans += nums[i] * sum;
    }
    cout << ans << endl;
    
    return 0;
}

在这里插入图片描述

[蓝桥杯 2020 省 AB2] 回文日期

题目描述

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 yyyymmdd 的格式写成一个 $8$ 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。

有人表示 20200202 是“千年一遇” 的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期：20211202 即 2021 年 12 月 2 日。

也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。对此小明也不认同，因为大约 $100$ 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即 2121 年12 月12 日。算不上“千年一遇”，顶多算“千年两遇”。

给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。

输入格式

输入包含一个八位整数 $N$ ，表示日期。

输出格式

输出两行，每行 $1$ 个八位数。第一行表示下一个回文日期，第二行表示下
一个 ABABBABA 型的回文日期。

样例 #1

样例输入 #1

20200202

样例输出 #1

20211202
21211212

提示

对于所有评测用例， $\le N \le 92200229$ ，保证 $N$ 是一个合法日期的 $8$ 位数表示。

蓝桥杯 2020 第二轮省赛 A 组 G 题（B 组 G 题）。

解题思路

我们直接从输入的日期 $d a t e$ 开始枚举，检查该日期是否合法，在合法的情况下判断日期是否为回文日期，输出第一个回文日期和第一个 ABABBABA 型日期。

所以我们需要实现3个函数，检查日期是否合法check_date、判断日期是否是回文日期check1、判断日期是否是 ABABBABA 型回文日期check2。

#include<bits/stdc++.h>
using namespace std;
int months[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};

//检查日期是否合法
bool check_date(int date)
{
	//分离年月日
    int d = date % 100;
    int m = date / 100 % 100;
    int y = date / 10000;
    //显而易见的不合法天数和月份
    if(d == 0 || m == 0 || m > 12) return false;
    //当月份不是2月时
    if(m != 2 && d > months[m]) return false;
    //月份是2月时要分是否是闰年来判断
    if(m == 2)
    {
        if((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0)) if(d > 29) return false;
        else if(d > 28) return false;
    }
    return true;
}

//检查是否是回文日期
bool check1(string s)
{
    int i = 0, j = s.size() - 1;
    while(i < j)
    {
        if(s[i++] != s[j--]) return false;
    }
    return true;
}

//检查日期是否是 ABABBABA`型回文日期
bool check2(string s)
{
    if(check1(s))
    {
        if(s[0] != s[2] || s[1] != s[3] || s[0] == s[1]) return false;
        return true;
    }
    return false;
}

int main()
{
    int date = 0;
    cin >> date;
    int cnt = 1;
    for(int i = date + 1; ;++i)
    {
        //在日期合法的情况下寻找回文日期
        if(check_date(i))
        {
            //将日期转换成字符串来判断
            string s = to_string(i);
            //输出第一个回文日期
            if(cnt && check1(s))
            {
                cout << i << endl;
                cnt--;
            }
            
            //在输出完第一个回文日期后，再去寻找ABABBABA型日期
            if(!cnt && check2(s))
            {
                cout << i << endl;
                break;
            }
        }
    }
    
    return 0;
}