个人主页：NiKo
算法专栏：算法设计与分析
目录
题目 2680:纸张尺寸
题目 2664:求和
题目 2681: 矩形拼接
题目 2665: 选数异或
题目 2682: GCD
题目 2667: 青蛙过河
题目 2683: 因数平方和
题目 2668: 最长不下降子序列
题目 2680:纸张尺寸
题目描述
在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm × 841mm，将 A0 纸沿长边对折后为 A1 纸，大小为 841mm × 594mm，在对折的过程中长度直接取下整（实际裁剪时可能有损耗）。将 A1 纸沿长边对折后为 A2 纸，依此类推。 输入纸张的名称，请输出纸张的大小。
输入格式
输入一行包含一个字符串表示纸张的名称，该名称一定是 A0、A1、A2、A3、A4、A5、A6、A7、A8、A9 之一。
输出格式
输出两行，每行包含一个整数，依次表示长边和短边的长度。
样例输入
A0样例输出
1189841题解
#include<stdio.h>int main(){ char let; int num; int long_ = 1189,short_ = 841; int newlong = long_,newshort = short_; scanf("%c%d",&let,&num); int type = num; if(type==0){ printf("%d\n",1189); printf("%d",841); }else{ while(type){ // 长边对折 newlong = long_ / 2; if(newlong < short_){ int temp = short_; short_ = newlong; long_ = temp; } type--; } printf("%d\n",long_); printf("%d",short_); } return 0;}题目 2664:求和
题目描述
给定 n 个整数 a1, a2, · · · , an ，求它们两两相乘再相加的和，即 S = a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an-2 · an-1 + an-2 · an + an-1 · an.
输入格式
输入的第一行包含一个整数 n 。
第二行包含 n 个整数 a1, a2, · · · an。
输出格式
输出一个整数 S，表示所求的和。请使用合适的数据类型进行运算。
样例输入
41 3 6 9样例输出
117提示
对于 30% 的数据，1 ≤ n ≤ 1000，1 ≤ ai ≤ 100。
对于所有评测用例，1 ≤ n ≤ 200000，1 ≤ ai ≤ 1000。
题解
#include<bits/stdc++.h>using namespace std;int main(void){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; long long sum[200001]; long long ans=0; int a; cin>>a; sum[1]=a; for(int i=2;i<=n;++i){ cin>>a; sum[i]=sum[i-1]+a; ans+=a*sum[i-1]; } cout<<ans; return 0;}题目 2681: 矩形拼接
题目描述
已知 3 个矩形的大小依次是 a1 × b1, a2 × b2 和 a3 × b3。用这 3 个矩形能拼出的所有多边形中，边数最少可以是多少？例如用 3 × 2 的矩形（用 A 表示）、4 × 1 的矩形（用 B 表示）和 2 × 4 的矩形（用 C 表示）可以拼出如下 4 边形。
例如用 3 × 2 的矩形（用 A 表示）、3 × 1 的矩形（用 B 表示）和 1 × 1 的矩形（用 C 表示）可以拼出如下 6 边形。
输入格式
输入包含多组数据。
第一行包含一个整数 T，代表数据组数。
以下 T 行，每行包含 6 个整数 a1, b1, a2, b2, a3, b3，其中 a1, b1 是第一个矩形的边长，a2, b2 是第二个矩形的边长，a3, b3 是第三个矩形的边长。
输出格式
对于每组数据，输出一个整数代表答案。
样例输入
22 3 4 1 2 41 2 3 4 5 6样例输出
46提示
对于 10% 的评测用例，1 ≤ T ≤ 5，1 ≤ a1, b1, a2, b2, a3, b3 ≤ 10，a1 = a2 = a3。
对于 30% 的评测用例，1 ≤ T ≤ 5，1 ≤ a1, b1, a2, b2, a3, b3 ≤ 10。
对于 60% 的评测用例，1 ≤ T ≤ 10，1 ≤ a1, b1, a2, b2, a3, b3 ≤ 20。
对于所有评测用例，1 ≤ T ≤ 1000，1 ≤ a1, b1, a2, b2, a3, b3 ≤ 100。
题解
#include<bits/stdc++.h>using namespace std;int a[3][2];int main(){int T;cin >> T;while (T--){//输入三个矩形的长和宽for (int i = 0; i < 3; i++)cin >> a[i][0] >> a[i][1];int ans = 8;//完全不匹配时的答案为8for (int i = 0; i < 3; i++)//枚举第一个矩形for (int j = 0; j < 3; j++)if (i != j)//枚举第二个矩形for (int k = 0; k < 3; k++)if (i != k && j != k)//枚举第三个矩形for (int ii = 0; ii <= 1; ii++)//枚举第一个矩形的长宽for (int jj = 0; jj <= 1; jj++)//枚举第二个矩形的长宽for (int kk = 0; kk <= 1; kk++)//枚举第三个矩形的长宽{//第一个矩形的长等于后两个矩形的长之和if (a[i][ii] == a[j][jj] + a[k][kk]){ans = min(ans, 6);//后面两个矩形的宽相等if (a[j][1 - jj] == a[k][1 - kk])ans = min(ans, 4);}//至少有一个矩形的长和第一个矩形的长相等if (a[i][ii] == a[j][jj] || a[i][ii] == a[k][kk])ans = min(ans, 6);//三个矩形的长全部相等if (a[i][ii] == a[j][jj] && a[i][ii] == a[k][kk])ans = min(ans, 4);}cout << ans << endl;}return 0;}题目 2665: 选数异或
题目描述
给定一个长度为 n 的数列 A1, A2, · · · , An 和一个非负整数 x，给定 m 次查询, 每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。
输入格式
输入的第一行包含三个整数 n, m, x 。
第二行包含 n 个整数 A1, A2, · · · , An 。
接下来 m 行，每行包含两个整数 li ,ri 表示询问区间 [li ,ri ] 。
输出格式
对于每个询问, 如果该区间内存在两个数的异或为 x 则输出 yes, 否则输出 no。
样例输入
4 4 11 2 3 41 41 22 33 3样例输出
yesnoyesno提示
显然整个数列中只有 2, 3 的异或为 1。
对于 20% 的评测用例，1 ≤ n, m ≤ 100；
对于 40% 的评测用例，1 ≤ n, m ≤ 1000；
对于所有评测用例，1 ≤ n, m ≤ 100000 ，0 ≤ x < 2的20次方 ，1 ≤ li ≤ ri ≤ n ， 0 ≤ Ai < 2的20次方。
题解
#include<bits/stdc++.h>using namespace std;int main(void){ ios_base::sync_with_stdio(0);cin.tie(0); int n,m,x; cin>>n>>m>>x; int arry[100002]; unordered_map<int,vector<int>> Map; //记录值和所有下标 vector<vector<int>> ans; for(int i=1;i<=n;++i){//O(n) cin>>arry[i]; if(Map.find(arry[i])==Map.end()) Map[arry[i]]={i}; else Map[arry[i]].emplace_back(i); } for(int i=1;i<=n;++i){//O(n*pair) if(Map.find(arry[i]^x)!=Map.end()){ //i 与 Map[arry[i]^x] 这俩位置可以异或为x int temp=arry[i]^x; for(int j=0;j<Map[temp].size();++j){ //由于答案是成对出现的，这里肯定会出现重复，但是不一定对称 ans.push_back({min(i,Map[temp][j]),max(i,Map[temp][j])}); } } } while(m--){ int left,right; cin>>left>>right; bool flag=true; for(int j=0;j<ans.size();++j){//O(m*pair) if(left<=ans[j][0]&&right>=ans[j][1]){ cout<<"yes"<<'\n'; flag=false; break; } } if(flag) cout<<"no"<<'\n'; } return 0;}题目 2682: GCD
题目描述
给定两个不同的正整数 a, b，求一个正整数 k 使得 gcd(a + k, b + k) 尽可能大，其中 gcd(a, b) 表示 a 和 b 的最大公约数，如果存在多个 k，请输出所有满足条件的 k 中最小的那个。
输入格式
输入一行包含两个正整数 a, b，用一个空格分隔。
输出格式
输出一行包含一个正整数 k。
样例输入
5 7样例输出
1提示
对于 20% 的评测用例，a < b ≤ 10的5次方 ；
对于 40% 的评测用例，a < b ≤ 10的9次方 ；
对于所有评测用例，1 ≤ a < b ≤ 10的18次方 。
题解
#include<iostream>using namespace std; int main() { long long a,b,c,d; cin>>a>>b; if(a>b){ long long t=a; a=b; b=t; } c=b-a; d=a/c; if(a%c) d++; cout<<d*c-a<<endl; return 0;} 题目 2667: 青蛙过河
题目描述
小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。
河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 1，当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 0 是允许的）。
小青蛙一共需要去学校上 x 天课，所以它需要往返 2x 次。当小青蛙具有一个跳跃能力 y 时，它能跳不超过 y 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。
输入格式
输入的第一行包含两个整数 n, x，分别表示河的宽度和小青蛙需要去学校的天数。请注意 2x 才是实际过河的次数。
第二行包含 n − 1 个非负整数 H1, H2, · · · , Hn-1，其中 Hi > 0 表示在河中与小青蛙的家相距 i 的地方有一块高度为 Hi 的石头，Hi = 0 表示这个位置没有石头。
输出格式
输出一行，包含一个整数，表示小青蛙需要的最低跳跃能力。
样例输入
5 11 0 1 0样例输出
4提示
由于只有两块高度为 1 的石头，所以往返只能各用一块。第 1 块石头和对岸的距离为 4，如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少需要 4 的跳跃能力。
对于 30% 的评测用例，n ≤ 100；
对于 60% 的评测用例，n ≤ 1000；
对于所有评测用例，1 ≤ n ≤ 10的5次方 , 1 ≤ x ≤ 10的9次方 , 1 ≤ Hi ≤ 10的4次方。
题解
#include <iostream>#include <cstring>#include <algorithm>#include <stack>using namespace std;typedef long long LL;typedef pair<int,int>pii;const int mod = 1e9 + 7 , INF = 0x3f3f3f3f , N = 1e5 + 10; int n,m;int a[N]; bool check(int x){ // 如果所有长度为x的区间都大于等于m ，则true int s = 0; for (int i = 1 ; i <= min(n - 1,x) ; i ++) s += a[i]; if (s < m) return false; for (int i = x + 1; i <= n - 1; i ++) { s -= a[i - x]; s += a[i]; if (s < m) return false; } return s >= m;} int main(){ cin >> n >> m; m *= 2; for (int i = 1 ; i <= n - 1 ; i ++) cin >> a[i]; int l = 0,r = n; while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } cout << r << endl; }题目 2683: 因数平方和
题目
题解
import java.time.format.DateTimeFormatter;import java.time.LocalDateTime; public class Test { public static void main(String[] args) { new Test().run(); } void run() { DateTimeFormatter date = DateTimeFormatter.ofPattern("MMdd"); DateTimeFormatter time = DateTimeFormatter.ofPattern("HHmm"); LocalDateTime start = LocalDateTime.of(0000, 01, 01, 00, 00); LocalDateTime end = LocalDateTime.of(0000, 12, 31, 23, 59); int[] buff = new int[128]; int ans = 0; for (; start.compareTo(end) <= 0; start = start.plusMinutes(1)) { for (char i = '0'; i <= '9'; ++i) buff[i] = 0; for (byte b : start.format(date).getBytes()) ++buff[b]; boolean flag1 = true, flag3 = true; for (char i = '0'; i <= '9'; ++i) if (buff[i] == 1) flag1 = false; else if (buff[i] == 3) flag3 = false; if (flag1 || flag3) continue; for (byte b : start.format(time).getBytes()) --buff[b]; for (char i = '0'; i <= '9'; ++i) if (buff[i] != 0) flag1 = true; if (!flag1) ++ans; } System.out.println(4 * ans); }}题目 2668: 最长不下降子序列
题目
package leetcode板块;import java.util.Arrays;import java.util.Scanner;public class _题目2668蓝桥杯2022年第十三届省赛真题_最长不下降子序列 { /** * * @param args */ public static void main(String[] args) { // 现在你有一次机会，将其中【连续的 K 个数】 修改成 【任意一个相同值】。 // 请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。 // TODO 最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。 /* 对于所有评测用例，1 ≤ K ≤ N ≤ 10^5，1 ≤ Ai ≤ 10^6。 */ Scanner scanner = new Scanner(System.in); // 长度为 N , 将其中连续的 K 个数修改成任意一个相同值 int N = scanner.nextInt(); int K = scanner.nextInt(); int arrA [] = new int[N]; for (int i = 0; i<N;i++){ arrA[i] = scanner.nextInt(); } scanner.close(); // 重点 ： LNDS:longest non-decreasing subsequence int initLNDS = computeLNDS(arrA); int maxLNDS = initLNDS; // ---------------------------------------------- for (int i = 0; i <= N-K;i++){ int [] original = Arrays.copyOfRange(arrA,i,i+K); int uniqueVals [] = Arrays.stream(arrA).distinct().toArray(); for (int value : uniqueVals){ for (int j = i;j<i+K;j++){ arrA[j] = value; } int modifiedLNDS = computeLNDS(arrA); maxLNDS = Math.max(maxLNDS,modifiedLNDS); } System.arraycopy(original,0,arrA,i,K); } System.out.println(maxLNDS); } /** * * @param array * @return */ private static int computeLNDS(int[] array) { int [] dp_computeLNDS = new int[array.length]; int length = 0; for (int num : array){ int pos = Arrays.binarySearch(dp_computeLNDS,0,length,num); if (pos < 0){ pos = -(pos + 1); } dp_computeLNDS[pos] = num; if (pos == length){ length++; } } return length; }}