2023年第十四届蓝桥杯大赛软件类省赛C/C++大学A组真题

2023年第十四届蓝桥杯大赛软件类省赛C/C++大学A组部分真题和题解分享

文章目录

• 蓝桥杯2023年第十四届省赛真题-平方差
• • 思路题解
  • 蓝桥杯2023年第十四届省赛真题-更小的数
  • • 思路题解
    • 蓝桥杯2023年第十四届省赛真题-颜色平衡树
    • • 思路题解
      • 蓝桥杯2023年第十四届省赛真题-买瓜
      • • 思路题解

          蓝桥杯2023年第十四届省赛真题-平方差

          题目描述

          给定 L, R，问 L ≤ x ≤ R 中有多少个数 x 满足存在整数 y,z 使得 x = y2 − z2。

          输入格式

          输入一行包含两个整数 L, R，用一个空格分隔。

          输出格式

          输出一行包含一个整数满足题目给定条件的 x 的数量。

          样例输入

          1 5

          样例输出

          4

          提示

          1 = 12 − 02 ；

          3 = 22 − 12 ；

          4 = 22 − 02 ；

          5 = 32 − 22 。

          对于 40% 的评测用例，LR ≤ 5000 ；

          对于所有评测用例，1 ≤ L ≤ R ≤ 109 。

          思路题解

          解题思路:

          • 规律：只有当x为奇数或4的倍数时才能拆分为两个数的平方差。

            注意事项:

          • 刚开始用c++写循环的时候，有一个样例会超时，故进一步寻找规律：F(X)=x/4+(x+1)/2，该式代表不大于x的满足条件的数的个数，用F®-F(L-1)即为L-R之间（大于等于L，小于等于R）满足条件的数的个数。

            #include
            using namespace std;
            int F(int x) {
                return x / 4 + (x + 1) / 2;//不大于x的满足条件的数的个数
            }
            int main() {
                int l = 0, r = 0;
                cin >> l >> r;
                cout  s[r]则满足条件，答案的个数+1。 
            详细解释：考虑s的所有子串[l,r], l即left，是子串的起始下标，r即right是子串的末尾下标，判断s[l] 和 s[r]的大小关系:
             
            

            • 若s[l] > s[r]则该子串反转后，新串原串，不满足条件。

              注意事项:

              • 注意l和r的取值范围（详见代码注释）。

                #include
                #include
                using namespace std;
                string s;
                int F(int l, int r) {
                    while (l  s[r])return 1;//如果s[l] > s[r]，反转后满足条件 新字符串 l++;r--; }//如果s[l] == s[r]，两边同时缩小区间。
                        else break;//如果s[l]  s;
                    int n = s.length();//n是字符串长度
                    int ans = 0;//记录答案
                    for (int l = 0;l //l即left是子串的起始下标，从0开始到n-2（子串长度至少为2，最右侧的最小子串下标为[n-2,n-1],故l最多到n-2）
                        for (int r = n - 1;r  l;r--) {//r即right是子串的末尾下标，从s的最末下标n-1到l+1。
                            if(F(l,r))ans++;
                        }
                    }
                    cout 
                    for(auto entry:cnt_nb){
                        int c=entry.first,count = entry.second;
                        cnt[c] += count;
                    }
                }
                /*
                对树进行dfs搜索，树的根节点为i，并返回该子树的各节点颜色计数结果
                */
                map
                    int sz = g[i].size();
                    map 
                        cnt[c[i]] = 1; 
                        ans++; 
                        return cnt;
                    }
                    /*如果不是叶子节点*/
                    //将根节点的颜色加入cnt
                    cnt[c[i]]=1;
                    //遍历根节点的所有子树，并将子树的计数结果累加到cnt中
                    for(int j=0;j
                        int nb = g[i][j];
                        map
                        //存在一种颜色数量不等，直接返回
                        if(entry.second != count) return cnt; 
                    }
                    //各颜色的数量相等，结果+1
                    ans++;
                    //返回计数结果
                    return cnt;
                }
                int main()
                {
                    int n;
                    cinn;
                    vector g[N]; 
                    int c[N]; //每个节点的颜色
                    for(int i=0;i
                        int f;
                        cin>c[i]>>f;
                        if(f>=1){
                            g[f-1].push_back(i); //记录节点f的子节点i（节点编号从0开始）
                        }
                    }
                    dfs(g,c,0);
                    coutm 
                但是这样仍然会超时，还可以将重量数组降序排列，使得更快剪枝。还可以创建一个重量数组的后缀数组suf，这样在搜索时可以利用其剪枝：若当前重量加上剩余的所有瓜重量之和小于要求的重量，剪枝。
                 
                #include
                #include
                using namespace std;
                const int N = 30; 
                int INF = 100;
                int n,m;
                int v[N]; //重量数组
                long suf[N+1]; //重量数组的后缀数组
                int ans = INF; //将结果初始化为INF
                /*
                dfs搜索,参数分别表示当前层数,当前重量之和,切瓜的次数
                */
                void dfs(int pos,long sum,int cnt){
                    if(sum==m){ //找到了一个结果
                        ans = min(ans,cnt);
                        return;
                    }
                    //剪枝
                    if(pos>=n || cnt>=ans || sum>m || sum+suf[pos]
                    ios::sync_with_stdio(false);
                    cin.tie(0),cout.tie(0);
                    cin>n>>m;
                    m*=2; //总重量乘2
                    for(int i=0;i>v[i],v[i]*=2;
                    sort(v,v+n,greater());
                    for(int i=n-1;i>=0;i--) suf[i] = suf[i+1]+v[i];
                    dfs(0,0,0);
                    if(ans==INF) cout