头像

自律

吹灭读书灯 一身都是月




离线:19小时前


最近来访(468)
用户头像
向北
用户头像
Martito
用户头像
juanxincai
用户头像
Koma
用户头像
acwing_0161
用户头像
静鸥
用户头像
Bear_King
用户头像
挪开暖瓶
用户头像
Rezarc
用户头像
风遥
用户头像
AcWing2AK
用户头像
whale77
用户头像
青葱岁月
用户头像
易碎TT
用户头像
ziuch
用户头像
Loki
用户头像
ヅ天使ぺ嫙嵂
用户头像
夜消梦未消
用户头像
mmmmm
用户头像
冷轩


自律
19天前

题目链接 蓝桥杯2021年第十二届国赛真题-123

显而易见,二分范围在int内,但如果把二分模板中的l,r,mid从long long改为int就会出错。
我感觉是int和longlong运算出的错,但是也只是感觉,真是莫名其妙的。

错误的代码:

#include<iostream>
using namespace std;

long long sum(long long x)
{
    if(x == 0) return 0;
    int l = 1,r = 2e6;  //改longlong
    while(l < r)
    {
        int mid = l + r + 1 >> 1;   //改longlong
        if(x >= mid * (mid + 1) / 2) l = mid;
        else r = mid - 1;
    }

    long long a = l * (l + 1) / 2 * (l + 1) - l * (l + 1) * (2 * l + 1) / 6;
    x -= l * (l + 1) / 2;
    a += x * (x + 1) / 2;
    return a;
}

int main()
{
    int t = 0;
    scanf("%d",&t);
    while(t--)
    {
        long long l = 0,r = 0;
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",sum(r) - sum(l - 1));
    }
    return 0;
}





自律
20天前

第十二届蓝桥杯国赛C++大学B组


一、带宽

问题描述

小蓝家的网络带宽是200Mbps,请问,使用小蓝家的网络理论上每秒钟最多可以从网上下载多少MB的内容。

1MB = 8Mbps

答案

25


二、纯质数

问题描述

如果一个正整数只有 1 11 和它本身两个约数,则称为一个质数(又称素数)。

前几个质数是:2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , . . .

如果一个质数的所有十进制数位都是质数,我们称它为纯质数。例如:2 , 3 , 5 , 7 , 23 , 37都是纯质数,而 11 , 13 , 17 , 19 , 29 , 31 不是纯质数。当然 1 , 4 , 35 也不是纯质数。

请问,在1 到 20210605 中,有多少个纯质数?

答案

1903

Code

#include<iostream>
using namespace std;

bool check(int x)
{
    while(x)
    {
        if(x % 10 == 0 || x % 10 == 1 || x % 10 == 4 || x % 10 == 6 || x % 10 == 8 || x % 10 == 9) return false;
        x /= 10;
    }
    return true;
}

bool is_prime(int x)
{
    for(int i = 2;i <= x / i;i ++)
    {
        if(x % i == 0) return false;
    }
    return true;
}

int ans;

int main()
{
    for(int i = 2;i <= 20210605;i ++)
        if(check(i))
            if(is_prime(i))
                ans ++;

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

三、完全日期

问题描述

如果一个日期中年月日的各位数字之和是完全平方数,则称为一个完全日期。

例如:2021年6 月5 日的各位数字之和为2 + 0 + 2 + 1 + 6 + 5 = 16,而 16 是一个完全平方数,它是 4 的平方。所以2021 年 6 月 5 日是一个完全日期。

例如:2021年6 月23 日的各位数字之和为2 + 0 + 2 + 1 + 6 + 2 + 3 = 16 ,是一个完全平方数。所以2021 年6 月23 日也是一个完全日期。

请问,从2001 年1 月1 日到2021 年12 月31 日中,一共有多少个完全日期?

答案

977

Code

#include<iostream>
#include<cmath>
using namespace std;

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

bool check(int i,int j,int k)
{
    int x = 0;
    while(i){
        x += i % 10;
        i /= 10;
    }
    while(j){
        x += j % 10;
        j /= 10;
    }
    while(k){
        x += k % 10;
        k /= 10;
    }

    int y = sqrt(x);
    if(y * y == x) return true;
    else return false;
}

int main()
{
    for(int i = 2001;i <= 2021;i ++)
        for(int j = 1;j <= 12;j ++)
        {
            int x = month[j];
            if(((i % 4 == 0 || i % 100 == 0) && i % 400 != 0) && j == 2)
                x = month[j] + 1;

            for(int k = 1;k <= x;k ++)
                if(check(i,j,k))
                    ans ++;
        }

    cout<<ans<<endl;
}

四、最小权值

问题描述

对于一棵有根二叉树 T,小蓝定义这棵树中结点的权值 W(T) 如下:
空子树的权值为 0。
如果一个结点 v 有左子树 L, 右子树 R,分别有 C(L) 和 C(R) 个结点,则:
$W(v) = 1 + 2W(L) + 3W(R) + (C(L)) ^ 2 C(R)$。树的权值定义为树的根结点的权值。
小蓝想知道,对于一棵有 2021 个结点的二叉树,树的权值最小可能是多少?

答案

2653631372

Code

#include<iostream>
#include<cstring>
using namespace std;

long long f[2022];  //f[i]表示权值为i的二叉树的最小权值

int main()
{
    memset(f, 0x3f, sizeof f);
    f[0] = 0;

    for(int i = 1;i <= 2021;i ++)
    {
        for(int j = 0;j < i;j ++)
            f[i] = min(f[i],1 + 2 * f[j] + 3 * f[i - 1 - j] + j * j * (i - 1 - j));
    }

    cout<<f[2021]<<endl;
    return 0;
}


五、大写

问题描述

给定一个只包含大写字母和小写字母的字符串,请将其中所有的小写字母 转换成大写字母后将字符串输出。

Code

#include<iostream>
using namespace std;

int main()
{
    char ch;
    while(~scanf("%c",&ch))
    {
        if(ch <= 'z' && ch >= 'a')
            printf("%c",ch - 32);
        else printf("%c",ch);
    }
    return 0;
}

六、123

问题描述

小蓝发现了一个有趣的数列,这个数列的前几项如下:
1, 1, 2, 1, 2, 3, 1, 2, 3, 4, …
小蓝发现,这个数列前 1 项是整数 1,接下来 2 项是整数 1 至 2,接下来3 项是整数 1 至 3,接下来 4 项是整数 1 至 4,依次类推。
小蓝想知道,这个数列中,连续一段的和是多少?

输入格式

输入的第一行包含一个整数 T,表示询问的个数。
接下来 T 行,每行包含一组询问,其中第 i 行包含两个整数 li 和 ri,表示询问数列中第 li 个数到第 ri 个数的和。

输出格式

输出 T 行,每行包含一个整数表示对应询问的答案。

评测用例规模与约定

对于 10% 的评测用例, 1 ≤ T ≤ 30, 1 ≤ li ≤ ri ≤ 100。
对于 20% 的评测用例, 1 ≤ T ≤ 100, 1 ≤ li ≤ ri ≤ 1000。
对于 40% 的评测用例, 1 ≤ T ≤ 1000, 1 ≤ li ≤ ri ≤ 10 ^ 6。
对于 70% 的评测用例, 1 ≤ T ≤ 10000, 1 ≤ li ≤ ri ≤ 10 ^ 9。
对于 80% 的评测用例, 1 ≤ T ≤ 1000, 1 ≤ li ≤ ri ≤ 10 ^ 12。
对于 90% 的评测用例, 1 ≤ T ≤ 10000, 1 ≤ li ≤ ri ≤ 10 ^ 12。
对于所有评测用例, 1 ≤ T ≤ 100000, 1 ≤ li ≤ ri ≤ 10 ^ 12。

Code

用scanf读入比cin快很多

#include<iostream>
using namespace std;

long long sum(long long x)
{
    if(x == 0) return 0;
    long long l = 1,r = 2e6;
    while(l < r)
    {
        long long mid = l + r + 1 >> 1;
        if(x >= mid * (mid + 1) / 2) l = mid;
        else r = mid - 1;
    }

    long long a = l * (l + 1) / 2 * (l + 1) - l * (l + 1) * (2 * l + 1) / 6;
    x -= l * (l + 1) / 2;
    a += x * (x + 1) / 2;
    return a;
}

int main()
{
    int t = 0;
    scanf("%d",&t);
    while(t--)
    {
        long long l = 0,r = 0;
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",sum(r) - sum(l - 1));
    }
    return 0;
}


七、异或变换

问题描述

小蓝有一个 01 串 s = s1 s2 s3 · · · sn。
以后每个时刻,小蓝要对这个 01 串进行一次变换。每次变换的规则相同。
对于 01 串 s = s1 s2 s3 · · · sn,变换后的 01 串 s′ = s′1 s′2 s′3· · · s′n 为:
s′1 = s1;
s′i = si-1 ⊕ si。
其中 a ⊕ b 表示两个二进制的异或,当 a 和 b 相同时结果为 0,当 a 和 b不同时结果为 1。
请问,经过 t 次变换后的 01 串是什么?

Code



八、

问题描述

Code





自律
25天前

贪心+二分

#include<iostream>
using namespace std;

const int N = 1e6 + 10;
int a[N];
int q[N];   //存储长度为i的上升子序列结尾的最小值

int main()
{
    int n;
    cin>>n;
    for(int i = 0;i < n;i ++) cin>>a[i];

    int len = 0;    //长度的最大值
    q[0] = -2e9;    //处理二分边界
    for(int i = 0;i < n;i ++)
    {
        int l = 0,r = len;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len,r + 1);
        q[r + 1] = a[i];
    }

    cout<<len<<endl;
    return 0;
}


分享 DP

自律
28天前

刷题随笔

$DP$

动态规划

对于动态规划从玄学到科学的认识,是对它掌握的过程。


数字三角形模型


最长上升子序列模型


背包问题


状态机模型


状态压缩DP


区间DP


树形DP


数位DP


单调队列优化DP


斜率优化DP



活动打卡代码 AcWing 870. 约数个数

自律
29天前
#include<iostream>
#include <unordered_map>
using namespace std;

const int MOD = 1e9 + 7;
unordered_map<int,int> primes;

int main()
{
    int n;
    cin>>n;
    for(int i = 0;i < n;i ++)
    {
        int x;
        cin>>x;
        for(int j = 2;j <= x / j;j ++)
            while(x % j == 0)   //while不要错写为if
            {
                primes[j] ++;
                x /= j;
            }
        if(x > 1) primes[x] ++;
    }

    long long cnt = 1;
    for(auto q : primes) cnt = cnt * (q.second + 1) % MOD;  //cnt *= (q.second + 1) % MOD错误,注意运算符优先级

    cout<<cnt<<endl;
    return 0;
}



自律
30天前

第十一届蓝桥杯国赛C++大学B组


一、美丽的2

问题描述

小蓝特别喜欢2,今年是2020年,他特别高兴。
他很好奇,在公元1年到公元2020年(包含)中,有多少年份的位数中包含数字2?

答案

563

Code

#include<iostream>
using namespace std;

bool check(int x)
{
    while(x)
    {
        if(x % 10 == 2) return true;
        x /= 10;
    }
    return false;
}

int main()
{
    int ans = 0;
    for(int i = 1;i <= 2020;i ++)
        ans += check(i);

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

二、扩散

问题描述

小蓝在一张 无限大 的特殊画布上作画。

这张画布可以看成一个方格图,每个格子可以用一个二维的整数坐标表示。

小蓝在画布上首先点了一下几个点:(0, 0),(2020, 11),(11, 14),(2000, 2000)

只有这几个格子上有黑色,其它位置都是白色的,每过一分钟,黑色就会扩散一点。

具体的,如果一个格子里面是黑色,它就会扩散到上、下、左、右四个相邻的格子中,使得这四个格子也变成黑色(如果原来就是黑色,则还是黑色)。

请问,经过 2020 分钟后,画布上有多少个格子是黑色的。

答案

20312088

Code

#include<iostream>
#include<queue>
#include<cstring>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
const int N = 6500;
const int M = 2020; //偏移量 
int dist[N][N];
bool st[N][N];
int ans = 4;    //初始时有4个黑点 

void bfs()
{
    int cnt = 0;
    q.push({0 + M,0 + M});
    q.push({2020 + M,11 + M});
    q.push({11 + M,14 + M});
    q.push({2000 + M,2000 + M});
    st[0 + M][0 + M] = true;
    st[2020 + M][11 + M] = true;
    st[11 + M][14 + M] = true;
    st[2000 + M][2000 + M] = true;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while(q.size())
    {
        PII t = q.front();
        q.pop();

        if(dist[t.x][t.y] >= 2020) return;

        for(int i = 0;i < 4;i ++)
        {
            int a = t.x + dx[i],b = t.y + dy[i];
            if(a < 0 || a > 6100 || b < 0 || b > 6100) continue;
            if(st[a][b]) continue;
            if(dist[a][b] != -1) continue;

            dist[a][b] = dist[t.x][t.y] + 1;
            st[a][b] = true;
            q.push({a,b});
            ans ++;
        }
    }
}

int main()
{
    memset(dist,-1,sizeof dist);
    dist[0 + M][0 + M] = 0;
    dist[2020 + M][11 + M] = 0;
    dist[11 + M][14 + M] = 0;
    dist[2000 + M][2000 + M] = 0;

    bfs();
    cout<<ans<<endl;
    return 0;
}


三、阶乘约数

相同题目: 约数个数

问题描述

定义阶乘 n! = 1 × 2 × 3 × ··· × n。

请问 100! (100 的阶乘)有多少个正约数。

数论

任意一个正整数 X 都可以表示成若干个质数乘积的形式,即 $X = p_1^a1 * p_2^a2 * …… *p_k^ak $

约数个数 = $(a1 + 1)(a2 + 1)……(ak + 1)$

答案

39001250856960000

Code

#include<iostream>
#include <unordered_map>
using namespace std;

unordered_map<int,int> primes;

int main()
{
    for(int i = 1;i <= 100;i ++)
    {
        int x = i;
        for(int j = 2;j <= x / j;j ++)
            while(x % j == 0)   //while不要错写为if
            {
                primes[j] ++;
                x /= j;
            }
        if(x > 1) primes[x] ++;
    }

    long long cnt = 1;
    for(auto q : primes) cnt = cnt * (q.second + 1);  

    cout<<cnt<<endl;
    return 0;
}

四、本质上升序列

问题描述

小蓝特别喜欢单调递增的事物。

在一个字符串中,如果取出若干个字符,将这些字符按照在字符串中的顺序排列后是单调递增的,则成为这个字符串中的一个单调递增子序列。

例如,在字符串 lanqiao 中,如果取出字符 n 和 q,则 nq 组成一个单调递增子序列,类似的单调递增子序列还有 lnq、i、ano。

小蓝发现,有些子序列虽然位置不同,但是字符序列是一样的,

例如取第二个字符和最后一个字符可以取到 ao,取最后两个字符也可以取到 ao,小蓝认为他们并没有本质不同。

对于一个字符串,小蓝想知道,本质不同的递增子序列有多少个?

例如,对于字符串 lanqiao,本质不同的递增子序列有 21 个。

它们分别是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、anq、lno、ano、aio。

请问对于以下字符串(共 200 个小写英文字母,分两行显示):

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

本质不同的递增子序列有多少个?

答案

3616159

68254F2C2F52813E9F226F4BAF9E0E18.png

Code

#include<iostream>
#include<iostream>
using namespace std;

int f[210];

int main()
{
    string s = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";

    for(int i = 0;i < 200;i ++) f[i] = 1;

    for(int i = 0;i < 200;i ++)
        for(int j = 0;j < i;j ++)
        {
            if(s[i] > s[j]) f[i] += f[j];
            if(s[i] == s[j]) f[i] -= f[j];
        }

    int ans = 0;    
    for(int i = 0;i < 200;i ++) ans += f[i];

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

五、玩具蛇

问题描述

小蓝有一条玩具蛇,一共有 16 节,上面标着数字 1 至 16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 90 度角。

小蓝还有一个 4 × 4 的方格盒子,用于存放玩具蛇,盒子的方格上依次标着字母 A 到 P 共 16 个字母。

小蓝可以折叠自己的玩具蛇放到盒子里面。他发现,有很多种方案可以将玩具蛇放进去。

下图给出了两种方案:
courses_2786_attachments_1621305634127_6.png

请帮小蓝计算一下,总共有多少种不同的方案。如果两个方案中,存在玩具蛇的某一节放在了盒子的不同格子里,则认为时不同的方案。

答案

552

Code

#include<iostream>
#include<cstring>
using namespace std;

int g[5][5];
int st[5][5];
int ans = 0;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x,int y,int u)
{
    if(u == 15)
    {
        ans ++;
        return;
    }

    for(int i = 0;i < 4;i ++)
    {
        int a = x + dx[i],b = y + dy[i];
        if(a < 0 || a >= 4 || b < 0 || b >= 4) continue;
        if(st[a][b]) continue;

        st[a][b] = 1;
        dfs(a,b,u + 1);
        st[a][b] = 0;
    }


}

int main()
{
    for(int i = 0;i < 4;i ++)
        for(int j = 0;j < 4;j ++)
        {
            st[i][j] = 1;
            dfs(i,j,0);
            memset(st, 0, sizeof st);
        }   

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

六、皮亚诺曲线距离


七、游园安排

问题描述

L 星球游乐园非常有趣,吸引着各个星球的游客前来游玩。

小蓝是 L 星球游乐园的管理员,为了更好的管理游乐园,游乐园要求所有的游客提前预约,小蓝能看到系统上所有预约游客的名字。

每个游客的名字由一个大写英文字母开始,后面跟 0个或多个小写英文字母,游客可能重名。

小蓝特别喜欢递增的事物。今天,他决定在所有预约的游客中,选择一部分游客在上午游玩,其他的游客都在下午游玩,

在上午游玩的游客要求按照预约的顺序排列后,名字是单调递增的,即排在前面的名字严格小于排在后面的名字。

一个名字 A 小于另一个名字 B 是指:

存在一个整数 i ,使得 A 的前 i 个字母与 B 的前 i 个字母相同,且 A 的第 i + 1个字母小于 B 的第 i + 1 个字母
如果 A 不存在第 i + 1 个字母且 B 存在第 i + 1 个字母,也视为 A AA 的第 i + 1 个字母小于 B 的第 i + 1 个字母
作为小蓝的助手,你要按照小蓝的想法安排游客,同时你又希望上午有尽量多的游客游玩,请告诉小蓝让哪些游客上午游玩。

如果方案有多种,请输出上午游玩的第一个游客名字最小的方案。

如果此时还有多种方案,请输出第一个游客名字最小的前提下第二个游客名字最小的方案。

如果仍然有多种,依此类推选择第三个、第四个……游客名字最小的方案。

输入格式

输入包含一个字符串,按预约的顺序给出所有游客的名字,相邻的游客名字之间没有字符分隔。

输出格式

按预约顺序输出上午游玩的游客名单,中间不加任何分隔字符。

样例输入

WoAiLanQiaoBei

样例输出

AiLanQiao

数据范围

对于 20% 的评测数据,输入的总长度不超过 20 个字母。
对于 50% 的评测数据,输入的总长度不超过 300 个字母。
对于 70% 的评测数据,输入的总长度不超过 10000 个字母。
对于所有评测数据,每个名字的长度不超过 10 个字母,输入的总长度不超过 1000000 个字母。

Code(过70%数据)

#include<iostream>
#include<vector>
#include<string>
using namespace std;

const int N = 1e5 + 10;
vector<string> q;
int len[N];
string f[N];

int main()
{
    string s;
    cin>>s;

    for(int i = 0;i < s.size();i ++)
        if(s[i] >= 'A' && s[i] <= 'Z')
        {
            int j = i + 1;
            while(s[j] >= 'a' && s[i] <= 'z') j ++;
            q.push_back(s.substr(i,j - i ));
        }

    for(int i = 0;i < q.size();i ++)    //初始化
    {
        len[i] = 1;
        f[i] = q[i];
    }

    for(int i = 0;i < q.size();i ++)
        for(int j = 0;j < i;j ++)
            if(q[i] > q[j])
                if(len[j] + 1 > len[i])
                {
                    len[i] = len[j] + 1;
                    f[i] = f[j] + q[i];
                }
                else if(len[j] + 1 == len[i])   //注意else if不能写成if
                {
                    len[i] = len[j];
                    f[i] = min(f[i],f[j] + q[i]);
                }

    string ans;
    int maxv = 0;
    for(int i = 0;i < q.size();i ++)
        if(maxv <= len[i]) maxv = len[i],ans = f[i];    //长度相同时后者为答案

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

八、答疑

问题描述

有 n位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。

老师可以安排答疑的顺序,同学们要依次进入老师办公室答疑。

一位同学答疑的过程如下:

  1. 首先进入办公室,编号为 i的同学需要 si毫秒的时间。
  2. 然后同学问问题老师解答,编号为 i的同学需要 ai毫秒的时间。
  3. 答疑完成后,同学很高兴,会在课程群里面发一条消息,需要的时间可以忽略。
  4. 最后同学收拾东西离开办公室,需要 ei毫秒的时间。一般需要 10秒、20秒或 30秒,即 ei取值为 10000,20000 或 30000 。

一位同学离开办公室后,紧接着下一位同学就可以进入办公室了。

答疑从 0 时刻开始。老师想合理的安排答疑的顺序,使得同学们在课程群里面发消息的时刻之和最小。

输入格式

输入第一行包含一个整数 n,表示同学的数量。
接下来 n行,描述每位同学的时间,其中第 i 行包含三个整数 s i , a i , e i ,意义如上所述。

输出格式

输出一个整数,表示同学们在课程群里面发消息的时刻之和最小是多少。

样例输入

3
10000 10000 10000
20000 50000 20000
30000 20000 30000

样例输出

280000

样例说明

按照 1 , 3 , 2 的顺序答疑,发消息的时间分别是 20000 , 80000 , 180000

Code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int,int> PII;
int q[1010][5];
vector<PII> p;
long long ans;

int main()
{
    int n;
    cin>>n;
    for(int i = 0;i < n;i ++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        q[i][0] = a,q[i][1] = b,q[i][2] = c;
        p.push_back({a + b + c,i});
    }

    sort(p.begin(),p.end());

    int res = 0;
    for(int i = 0;i < p.size();i ++)
    {
        int cnt = 0;
        cnt = q[p[i].second][0] + q[p[i].second][1];
        ans += res + cnt;
        res += cnt + q[p[i].second][2];
    }

    cout<<ans<<endl;

    return 0;
}



自律
1个月前

第十届蓝桥杯国赛C++大学B组


一、平方序列

题目描述

小明想找到两个正整数$X$和$Y$,满足

  • $2019 < X < Y$
  • $2019^2,X^2,Y^2$组成等差序列

请你求出在所有可能的解中,$X+Y$的最小值是多少?

答案

7020

Code

#include<iostream>
using namespace std;

int main()
{
    for(int i = 2020;i < 10000;i ++)
        for(int j = i + 1;j < 10000;j ++)
            if(i * i * 2 == 2019 * 2019 + j * j)
            {
                cout<<i + j<<endl;
                return 0;
            }
}

二、质数拆分

问题描述

将2019拆分为若干个两两不同的质数之和,一共有多少种不同的方法?
注意交换顺序视为同一种方法,例如2 + 2017 = 2019与2017 + 2 = 2019视为同一种方法。

答案

55965365465060

Code

#include<iostream>
#include<algorithm>
using namespace std;

long long f[2020][2020];
int q[2020];
int x = 0;

bool check(int x)   //判断素数
{
    for(int i = 2;i <= x / i;i ++)
        if(x % i == 0)
            return false;
    return true;
}

int main()
{
    for(int i = 2;i <= 2019;i ++)
        if(check(i))
            q[++ x] = i;

    f[0][0] = 1;
    for(int i = 1;i <= x;i ++)  //DP
        for(int j = 0;j <= 2019;j ++)
        {
            if(j < q[i]) 
                f[i][j] = f[i - 1][j];
            else
                f[i][j] = f[i - 1][j] + f[i - 1][j - q[i]];
        }

    cout<<f[x][2019]<<endl;
    return 0;
}

三、拼接

问题描述

小明要把一根木头切成两段,然后拼接成一个直角。

如下图所示,他把中间部分分成了 n × n 的小正方形,他标记了每个小正方形属于左边还是右边。

然后沿两边的分界线将木头切断,将右边旋转向上后拼接在一起。

4.png
要求每个小正方形都正好属于左边或右边,而且同一边的必须是连通的。

在拼接时,拼接的部位必须保持在原来大正方形里面。

请问,对于 7 × 7 的小正方形,有多少种合法的划分小正方形的方式

  • 以对角线上的每一个点为起点,在搜索的过程中同时标记搜索点和其关于$y=x$对称点(将右边旋转向上后拼接在一起),当触及边界时,就完成了一次分割。

答案

2444

Code

#include<iostream>
#include<cstring>
using namespace std;

int st[100][100];
int ans;

void dfs(int x,int y)
{
    if(x == 0 || y == 7)
    {
        ans ++;
        return;
    }

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    for(int i = 0;i < 4;i ++)
    {
        int a = x + dx[i],b = y + dy[i];
        if(a < 0 || a > 7 || b < 0 || b > 7 || a == b) continue;
        if(st[a][b]) continue;

        st[a][b] = 1;
        dfs(a,b);
        st[a][b] = 0;
    }
}

int main()
{
    for(int i = 0;i <= 7;i ++)
    {
        memset(st, 0, sizeof st);
        st[i][i] = 1;
        dfs(i,i);
    }

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

四、求值

问题描述

学习了约数后,小明对于约数很好奇,他发现,给定一个正整数t,总是可以找到含有t个约数的整数。小明对于含有t个约数的最小数非常感兴趣,并把它定义为$S_t$.

例如$S_ = 1,S_2 = 2,S_3 = 4,S_4 = 6,…$
现在小明想知道,当t = 100时,$S_t$是多少?

答案 45360

Code

#include<iostream>
#include<cmath>
using namespace std;

int main()
{
    for(int i = 1;i < 100000;i ++)
    {
        int cnt = 0;
        for(int j = 1;j <= i / j;j ++)
        {
            if(i % j == 0)
                cnt ++;
            if(cnt == 50)
            {
                cout<<i<<endl;
                return 0;
            }
        }
    }
    return 0;
}

五、路径计数

问题描述

从一个 5 x 5 的方格矩阵的左上角出发,沿着方格的边走,满足以下条件的路线有多少种?

  • 总长度不超过 12;
  • 最后回到左上角;
  • 路线不自交;
  • 不走出 5 x 5 的方格矩阵范围之外。

如下图所示,ABC 是三种合法的路线。注意 B 和 C 由于方向不同,所以视为不同的路线。

6.png

  • 注意格子为 5 X 5 时格点为 6 X 6
  • 注意特判步数为2时不符合条件

答案

206

Code

#include<iostream>
using namespace std;

int st[10][10];
int ans;

void dfs(int x,int y,int u)
{
    if(u > 12) return;
    if(x == 0 && y == 0 && st[x][y] == 1 && u > 2)  //特别注意 u > 2
    {
        ans ++;
        return;
    }

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    for(int i = 0;i < 4;i ++)
    {
        int a = x + dx[i],b = y + dy[i];

        if(a < 0 || a > 5 || b < 0 || b > 5) continue;
        if(st[a][b]) continue;

        st[a][b] = 1;
        dfs(a,b,u + 1);
        st[a][b] = 0;
    }
}

int main()
{
    dfs(0,0,0);
    cout<<ans<<endl;
    return 0;
}

六、最优包含

问题描述

我们称一个字符串$S$包含字符串$T$是指$T$是$S$的一个子序列,即可以从字符串$S$中抽出若干个字符,他们按原来的顺序组合成一个新的字符串与$T$完全一样。

给定两个字符串$S$和$T$,请问最小修改$S$中的多少个字符串,能使$S$包含$T$?

输入两行,每行一个字符串。第一行的字符串为$S$,第二行的字符串为$T$。两个字符串均非空而且只包含大写英文字母。
输出一个整数,表示答案。

S和T的长度小于等于1000。

1C697C4F7C57AFCCC9B972A2A1AA591D.png

Code

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int f[1010][1010];

int main()
{
    string a,b;
    cin>>a>>b;
    a = "0" + a;
    b = "0" + b;

    int n = a.size() - 1;
    int m = b.size() - 1;

    memset(f,0x3f,sizeof f);    //初始化
    f[0][0] = 0;
    for(int i = 1;i <= n;i ++) f[i][0] = 0; //S[1~i]中一定包含空串(T[1 ~ 0])

    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            if(a[i] == b[j]) 
                f[i][j] = min(f[i][j],f[i - 1][j - 1]);
            else
                f[i][j] = min(f[i - 1][j - 1] + 1,f[i - 1][j]);

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

    return 0;
}

七、排列数

问题描述

暴力代码

#include<iostream>
#include<algorithm>
using namespace std;

int q[510];
int n,k;

int main()
{
    cin>>n>>k;
    for(int i = 0;i < n;i ++) q[i] = i + 1;

    int ans = 0;
    do{
        int cnt = 0;
        for(int i = 0;i < n;i ++)
        {
            if(i == 0 || i == n - 1) continue;
            if(q[i] > q[i - 1] && q[i] > q[i + 1]) cnt ++;
            if(q[i] < q[i - 1] && q[i] < q[i + 1]) cnt ++;
        }
        if(cnt == k - 1) ans ++;
    }while(next_permutation(q,q + n));

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



自律
1个月前

字串变换

BFS — 双向广搜

刷题随笔–$BFS$


题目描述


  • 同时从起点和终点开始一层一层搜索,直到两端相遇,从而达到优化效果。
    例如两个五层的完全二叉树结点数量远远低于一个十层的完全二叉树。

  • substr()用法
    字符串.substr(参数1,参数2)
    参数一如果是0或正整数,则代表字符串截取的起始下标
    参数二字符串截取字符的个数(正整数)
    字符串.substr(参数);
    参数如果是0或正整数:字符串截取的起始下标,默认截取至字符串结尾



Code(TLE了)

#include<iostream>
#include <queue>
#include<unordered_map>
using namespace std;

string a[10],b[10];
int n;

int extend(queue<string> &qfirst,unordered_map<string,int> &dfirst,unordered_map<string,int> &dsecond,string a[],string b[])
{
    while(qfirst.size())
    {
        string t = qfirst.front();
        qfirst.pop();

        for(int i = 0;i < t.size();i ++)        //遍历所有变换规则
            for(int j = 0;j < n;j ++)
                if(t.substr(i,a[j].size()) == a[j])
                {
                    string s = t.substr(0,i) + b[j] + t.substr(i + a[j].size());
                    if(dsecond.count(s)) return dfirst[t] + 1 + dsecond[s];
                    if(dfirst.count(s)) continue;
                    dfirst[s] = dfirst[t] + 1;
                    qfirst.push(s);
                }
    }       
    return 11;
}

int bfs(string A,string B)
{
    queue<string> qfront,qback;
    unordered_map<string,int> dfront,dback;

    qfront.push(A),dfront[A] = 0;
    qback.push(B),dback[B] = 0;

    while(!qfront.empty() || !qback.empty())    //若其中一个搜索完(队列为空)时,则首尾路线不相交。
    {
        int t = 0;
        if(qfront.size() <= qback.size())       //均衡首位的搜索层数
            t = extend(qfront,dfront,dback,a,b);
        else 
            t = extend(qback,dback,dfront,b,a);

        if(t <= 10) return t;
    }
    return 11;
}

int main()
{
    string A,B;
    cin>>A>>B;
    while(cin>>a[n]>>b[n]) n ++;

    int t = bfs(A,B);
    if(t <= 10) cout<<t<<endl;
    else cout<<"NO ANSWER!"<<endl;
    return 0;
}


分享 DFS

自律
1个月前



自律
1个月前

电路维修

BFS — 双端队列广搜

刷题随笔–$BFS$


题目描述


  • 格点的横纵坐标之和为奇数的点无法到达
    因为起点从(0,0)开始而且横坐标变化1纵坐标对应变化1(电线只能斜着联通),变化之和为偶数。

  • 注意格点的坐标系和格子的坐标系不同,要关联起来就要做一个映射(引入ix[],iy[])。

  • 从左上角 格子外 开始搜索,若改变原本格子中的状态对应边权为1,若不改变原本格子的状态对应边权为0,搜索到电线联通右下角的(n,m)位置,就可以得到最小边权即最小步数。


Code

#include<iostream>
#include<cstring>
#include<deque>
#define x first
#define y second
using namespace std;

typedef pair<int, int> PII;
const int N = 510;
bool st[N][N];      //判断到达该格点的最小步数是否确定
int dist[N][N];     //记录到达该格点的最小步数
char g[N][N];       //记录格子中电线的状态

int n,m;

int bfs()
{
    deque<PII> q;
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);

    q.push_front({0,0});
    dist[0][0] = 0;     //从左上角格子外开始扩展

    int dx[] = {-1,-1,1,1},dy[] = {-1,1,1,-1};
    int ix[] = {-1,-1,0,0},iy[] = {-1,0,0,-1};      //注意格点与格子的区别
    char ch[5] = {"\\/\\/"};

    while(!q.empty())
    {
        PII t = q.front();
        q.pop_front();

        if(t.x == n && t.y == m) return dist[n][m];

        if(st[t.x][t.y]) continue; 
        st[t.x][t.y] = true;    //出队时确定最小步数

        for(int i = 0;i < 4;i ++)
        {
            int a = t.x + dx[i],b = t.y + dy[i];
            int ga = t.x + ix[i],gb = t.y + iy[i];
            if(a < 0 || a > n || b < 0 || b > m) continue;  //最终电线要联通(n,m)点

            int w = (g[ga][gb] != ch[i]);
            int d = dist[t.x][t.y] + w;

            if(d < dist[a][b])      //用已经确定最小步数的节点更新未确定最小步数的节点
            {
                dist[a][b] = d;
                if(!w) q.push_front({a,b});     //边权为0加入队首
                else q.push_back({a,b});        //边权为1加入队尾
            }
        }
    }
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i = 0;i < n;i ++) cin>>g[i];

        if(n + m & 1) cout<<"NO SOLUTION"<<endl;    //终点横纵坐标之和为奇数时不可到达
        else cout<<bfs()<<endl;
    }
    return 0;
}