1.密密摆放

题目描述

小蓝有一个大箱子，内部的长宽高分别是 $200$、$250$、$240$（单位：毫米），他要用这个大箱子来放一些同样大小的小盒子，小盒子的外部长宽高分别是 $30$、$40$、$50$（单位：毫米）。小盒子允许从各个方向旋转（包括可以平放和倒放）。

请问小蓝最多可以在一个大箱子里面放多少个小盒子。

思路

观察题目，可以发现200是40、50的倍数，250是50的倍数，240是30、40的倍数。因为空间使用率和最终放下的小盒子数量有关，所以要让空间尽量被使用，我们要优先考虑大盒子的边被除尽的情况。又因为小盒子可以平放和倒放，200、250、240和30、40、50可以自由组合，我们可以考虑大小盒子边长的关系。首先，250是50的倍数，是唯一能够一一对应的，先取。之后，50那条边不能用了，200是40的倍数，再取。240是30的倍数，最后取。
250/50*200/40*240/30 = 200

#include <bits/stdc++.h>
using namespace std;
//IOS
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//长整型
#define int long long

signed main(){
    IOS;
    cout << 200 << endl;
    return 0;
}

2.脉冲强度之和

题目描述

在蓝桥电子工坊，工程师小蓝正在设计一款智能脉冲生成器，用于驱动一种新型设备。该设备的运行依赖于特定的脉冲强度，用正整数 p表示，其必须满足以下三个条件：

数值不超过20255202：即 1≤ p≤20255202。
通过计算所有符合条件的脉冲强度之和，小蓝能够优化设备运行模式。对
此，请帮助他计算这一总和。

可由连续10 个正整数之和组成：即存在一个正整数k，使得脉冲强度
p =k+(k+1)+(k+2)+···+(k+9) 。

各个数位上的数字都相同：例如1111、22222 、333333 等。

思路

推公式
p =k+(k+1)+(k+2)+···+(k+9) = 10*k + (1+2+3+···+9) = 10*k + (0+9)*10/2 = 10*k + 45(k > 0)
根据以上关系可以得出p > 45，p%10 = 5。各位数字都要相同，所以p应该是55，555，5555，55555，555555···
又因为 1≤ p≤20255202，p = 55,555,5555,55555,555555,5555555
全部加起来得出 6172830

#include <bits/stdc++.h>
using namespace std;
//IOS
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//长整型
#define int long long

signed main(){
    IOS;
    cout << 6172830 << endl;
    return 0;
}

3.25 之和

题目描述

小蓝最近对求和很着迷，给定一个正整数n，他想求从n开始的连续25个整数的和，即n+(n+1)+(n+2)+···+(n+24) ，请帮帮他吧。

思路

推公式
n+(n+1)+(n+2)+···+(n+24) = 25*n + (0+1+2+3+···+24) = 25*n + (0+24)*25/2 = 25*n + 300(n > 0)

#include <bits/stdc++.h>
using namespace std;
//IOS
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//长整型
#define int long long
int n;
signed main(){
    IOS;
    cin >> n;
    cout << n*25 + 300 << endl;
    return 0;
}

4.旗帜

问题描述

小蓝要画一个LANQIAO 图形，并把这个图形做成一个旗帜。图形的形状
为一个h×w的矩形，其中h表示图形的高，w表示图形的宽。当h=5,w=10
时，图形如下所示：
LANQIAOLAN
ANQIAOLANQ
NQIAOLANQI
QIAOLANQIA
IAOLANQIAO
图形的规律是：第一行用LANQIAO 重复填入，第二行开始，每行向左移
动一个字符，用LANQIAO重复填入。
小蓝需要把图形中的每个字母都剪出来，以粘贴到旗帜上，他想知道，给
定图形的高和宽，图形中有多少个A。

思路

LANQIAOLAN
ANQIAOLANQ
NQIAOLANQI
QIAOLANQIA
IAOLANQIAO
高亮部分通过组合可以变成LANQIAO图形，剩下的字母开头是LANQIAO图形中随次数循环滚动+1的，长度为w%7，找一下字符A就行了，然后再进行相加。

#include <bits/stdc++.h>
using namespace std;
//IOS
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//长整型
#define int long long
int h, w;
string a = "LANQIAOLANQIAO";
int count(int pos, int len){
    int sum = 0;
    for(int i = pos;i < pos + len; i++){
        if(a[i] == 'A') sum ++;
    }
    return sum;
}
signed main(){
    IOS;
    cin >> h >> w;
    int res = 0;
    for(int i = 0; i < h; i ++){
        res += w/7*2 + count(i%7, w%7);
    }
    cout << res << endl;
    return 0;
}

5.数列差分

问题描述

小蓝有两个长度均为n的数列A={a1,a2,··· ,an}和B={b1,b2,··· ,bn}，
将两个数列作差定义为C=A−B={c1=a1−b1,c2=a2−b2,··· ,cn=an−bn}。
小蓝将对数列B进行若干次操作，每次操作可以将数列B中的任意一个数更改
为任意一个整数。在进行完所有操作后，小蓝可以按任意顺序将数列B重排，
之后再计算数列C。小蓝想知道，最少操作多少次可以使得数列C中的所有数
都为正整数。

思路

可以按任意顺序将数列B重排说明：AB数列的顺序不重要，重要的是如何匹配的问题
如何匹配？首先，使用贪心的想法，ai-bj要为正整数，所以我们改最大的bj。然后，如何判断这个bj是否需要更改呢？往数列A中找最大的ai来对比。
所以得出：数列A排序，数列B排序。i指向数列A，j指向数列B倒着遍历，尽量匹配数列A中的数字。
当ai>bj，ai与aj匹配，i与j递减。否则，ai与aj不匹配，j递减。

#include <bits/stdc++.h>
using namespace std;
//IOS
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//长整型
#define int long long
const int N = 100010;
int n;
int a[N], b[N];
signed main(){
    IOS;
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int i = 0; i < n; i ++) cin >> b[i];
    sort(a, a + n);
    sort(b, b + n);
    int cnt = n;
    for(int i = n - 1, j = n - 1; j >= 0;j --){
        if(a[i] > b[j]){
            i--;
            cnt --;
        }
    }
    cout << cnt << endl;
    return 0;
}

6.树上寻宝

问题描述

小蓝正在一棵含有n个结点的树的根结点1上，他准备在这棵树上寻宝。
结点i上有一个物品，价值为wi。然而，小蓝每次寻宝只能从根节点出发走不超过k步，每步只能选择走1条边或者2条边，之后会自动拾取最终停留的结点上的物品并被传送回根结点。请求出小蓝最终能获得的物品的总价值。

思路

小蓝每次寻宝只能从根节点出发走不超过k步：一共可以走k步。
每步只能选择走1条边或者2条边：可以走一步或者两步，说明深度不超过 2×k+1 的点都能在k步内到达。
题目转换为：求深度不超过 2×k 的点的所有价值之和

#include <bits/stdc++.h>
using namespace std;
//IOS
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//长整型
#define int long long
int n,k;
int w[100005],deep[100005],vis[100005];
vector<int> tr[100005];//邻接表
void dfs(int id,int fa,int dep){
	if(vis[id]==1) return;
	vis[id]=1;
	deep[id]=dep;
	for(int i=0;i<tr[id].size();i++){
		if(tr[id][i]!=fa) dfs(tr[id][i],id,dep+1);//tr[id][i]是下一个要访问的子节点
	}
}
signed main(){
    IOS;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<n;i++){
    	int u,v;
    	cin>>u>>v;
    	//无向图
    	tr[u].push_back(v);
    	tr[v].push_back(u);
	}
	dfs(1,0,0);
	long long ans=0;
	for(int i=1;i<=n;i++){
		if(deep[i]<=2*k) ans+=w[i];
	}
	cout<<ans;
	return 0;
}

7.翻转硬币

问题描述

给定n行m列共n×m个硬币，对于任意一个硬币，我们将其价值视为与
其相邻（指上、下、左、右相邻）的硬币中与其正反相同的硬币数的平方。
你可以进行任意次操作，每次可以选择任意一行并将该行的硬币全部翻转。
求所有硬币的价值之和最大可能是多少。

思路

考虑动态规划
题目中说上下左右相邻的硬币，但是我们实际只能把任意一行的硬币给翻转过来，所以硬币是否翻转和左右无关，与上下行有关。通过局部最优，可以获得全局最优。
动态规划（闫氏dp分析法）
状态表示
要知道i行贡献，必须要确定 i + 1 行才能知道，所以要枚举到第 i + 1 行后，才能求出第 i 行的最大贡献。下一步，如何确定第 i – 1 行、第 i 行、第 i + 1 行的状态呢？
dp[i + 1][j][k] 表示 i 行的最大值，i + 1 表示前 i 行，j 表示 i + 1 行翻不翻，k 表示第 i 行翻不翻
j  即是第 i + 1 行的状态，k 即是第 i 行的状态
dp[i][j][k] 表示 i – 1 行的最大值，i 表示前 i – 1 行，j 表示 i 行翻不翻，k 表示第 i – 1 行翻不翻
k 即是 i − 1 行的状态
集合：所有考虑前 i 行且第 i 行是否翻转状态为 j 且第i – 1行是否翻转状态为 k 的贡献集合
属性：MAX（最大值）
状态计算：dp[i][0][0] = max{dp[i – 1][0][1] + val, dp[i – 1][0][0] + val(i – 1, 0, 0, 0)}

#include <bits/stdc++.h>
using namespace std;
//IOS
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//长整型
#define int long long
int n, m;
int graph[1010][1010], dp[1010][2][2];
//四种状态
int dx[4] = {0, 0, 1, 1}, dy[4] = {0, 1, 0, 1};
//计算在状态约束下行的贡献，pre 表示前行约束，now 表示当前行，nex 表示下一行。
int com(int x, int pre, int now, int nex){
    int res = 0;
    for(int r = 1; r <= m; r++){
        int t = 0;
        if(graph[x][r] == graph[x][r - 1]) t++;
        if(graph[x][r] == graph[x][r + 1]) t++;
        //当满足以下两种情形之一时，条件成立
        //1.状态一致且元素一致
        //2.状态不一致且元素不一致
        //now == nex检查状态一致性，graph[x][r] == graph[x - 1][r]检查元素翻转一致性
        if(x - 1 > 0 && !(now == pre ^ graph[x][r] == graph[x-1][r])) t++;//!(A ^ B) 等价于 A == B
        if(x + 1 <= n && !(now == nex ^ graph[x][r] == graph[x+1][r])) t++;
        res += t * t;
    }
    return res;
}
signed main(){
    IOS;
    cin >> n >> m;
    memset(graph, -1, sizeof(graph));
    for(int i = 1; i <= n; i++){
        string t;
        cin >>t;
        for(int j = 1; j <= m; j++)
            graph[i][j] = t[j - 1] - '0';
    }
    //初始化，第一行前面没有行，要单独拎出来
    //特殊边界（无前一行约束）
    for(int i = 0; i < 4; i++)
        dp[2][dx[i]][dy[i]] = com(1, 0, dy[i], dx[i]);
    //枚举每一行
    for(int i = 3; i <= n + 1; i++){
        //枚举四种状态
        for(int j = 0; j < 4; j++)
            dp[i][dx[j]][dy[j]] = max(dp[i - 1][dy[j]][0] + com(i-1,0,dy[j],dx[j]),dp[i - 1][dy[j]][1] + com(i-1,1,dy[j],dx[j]));
    }
    cout << max({dp[n + 1][0][0], dp[n + 1][0][1],dp[n + 1][1][0],dp[n + 1][1][1]});
    return 0;
}

8.破解信息

问题描述

在遥远的未来，星际旅行已经成为常态。宇航员小蓝在一次探险任务中，
意外发现了一个古老的太空遗迹。遗迹中存放着一个数据存储器，里面记录着
一段加密的信息。经过初步分析，小蓝发现这段信息可以被表示为一个字符串
S，而解密的关键，在于找出S 中字典序最大的回文子序列。

• 子序列：指从原字符串中抽取若干个字符（可以不连续），按照它们在原
  字符串中的相对顺序排列所形成的新序列。例如，对于字符串“abc”，其
  子序列包括“a”、“b”、“c”、“ab”、“ac”、“bc” 和 “abc”。
• 字典序：指字符串按照字典中的排序规则比较大小的方式。对于两个字符
  串，从左到右逐字符比较，先出现较大字符的字符串字典序更大；若比较
  到某个字符串结束仍未找到不同的字符，则较短的字符串字典序较小。例
  如，“abc” < “abd”，而 “ab” < “abc”。

现在，请你从字符串S 中，找出字典序最大的回文子序列，帮助小蓝解开
这段来自星际文明的信息。

思路

此题关键在于：理解字典序
字典序：
1.从左到右，先出现较大字符的字符串字典序更大。
2.字符串结束仍未找到不同的字符（前面都一样），则较长的字符串字典序更大。
回文字符串dcbabcd
我们考虑最重要的规则一，前面字符越大越好，所以就直接找最大的字符，全部接起来。
考虑规则二，我们要让这个字符串更大，就得给它加长。
尝试用其它字符加长
加中间，例如：zzzazzz，显然比zzzzzz字典序要小
加两边，例如：zazzzzaz，显然字典序也小了
所以规则二我们不用考虑
题目就变成了：找出最大字符z，统计其出现次数k，输出k个字符z

#include <bits/stdc++.h>
using namespace std;
//IOS
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
//长整型
#define int long long
string s;
signed main(){
    IOS;
    cin >> s;
    char maxc = *max_element(s.begin(), s.end());
    int cnt = 0;
    for(char c : s) if(c == maxc) cnt ++;
    cout << string(cnt,maxc) << endl;
    return 0;
}