【蓝桥杯每日一题】3.28_画雪花蓝桥杯
🏝️专栏： 【蓝桥杯备篇】
🌅主页： f狐o狸x
\"今天熬的夜，会变成明天奖状的闪光点！\"
目录
一、唯一的雪花
题目链接
题目描述
解题思路
解题代码
二、逛画展
题目链接
题目描述
解题思路
解题代码
三、字符串
题目链接
题目描述
解题思路
解题代码
四、丢手绢
题目链接
题目描述
解题思路
解题代码
喵~ 今天要学习的算法是双指针，也被称为滑动窗口是⼀种优化暴⼒枚举策略的⼿段：
• 当我们发现在两层 for 循环的暴⼒枚举过程中，两个指针是可以不回退的，此时我们就可以利⽤两个指针不回退的性质来优化时间复杂度。
一、唯一的雪花
题目链接
UVA11572 唯一的雪花 Unique Snowflakes
题目描述
解题思路
例如题目中给的输入样例，我们可以按照以下方法来搞定此题：
第一步：先初始化左右指针
第二步：通过右指针向前走开始进窗口
第三步：通过题意判断出窗口
第四部：更新结果，重复上述步骤，直到遍历完全部数组
解题代码
#include #include using namespace std;typedef long long LL;const int N = 1e6 + 10;int n;LL a[N];int main(){int T; cin >> T;while (T--){cin >> n;for (int i = 1; i > a[i];// 初始化int left = 1, right = 1, ret = 0;unordered_map mp;while (right 1){mp[a[left]]--;left++;}// 更新结果ret = max(ret, right - left + 1);right++;}cout << ret << endl;}return 0;}二、逛画展
题目链接
P1638 逛画展 - 洛谷
题目描述
解题思路
这题其实就是给你一串数字，让你找到包括所有数字种类的最小子串
解题代码
#include using namespace std;const int N = 1e6 + 10;int a[N], mp[N];int n, m;int kind;int main(){cin >> n >> m;for (int i = 1; i > a[i];// 初始化int left = 1, right = 1,begin = 1 , ret = n;while (right <= n){// 进窗口if (mp[a[right++]]++ == 0) kind++;// 判断while (kind == m){// 更新结果int len = right - left ;if (len < ret){ret = len;begin = left;}// 出窗口if (mp[a[left++]]-- == 1) kind--;}}cout << begin << \" \" << begin + ret - 1 << endl;return 0;}三、字符串
题目链接
字符串
题目描述
解题思路
这题和上一题是一样的，只是把数字改成字符串了
解题代码
#include using namespace std;const int N = 30;int mp[N];int kind;int main(){ string s; cin >> s; int n = s.size(); // 初始化 int left = 0, right = 0, ret = n; while(right < n) { // 进窗口 if(mp[s[right++] - \'a\']++ == 0) kind++; // 判断 while(kind == 26) { // 更新结果 int len = right - left; ret = min(ret, len); // 出窗口 if(mp[s[left++] - \'a\']-- == 1) kind--; } } cout << ret << endl; return 0;}四、丢手绢
题目链接
丢手绢
题目描述
解题思路
这个题依然可以用双指针来解决，只不过是从一条直线变成了一个环而已
解题代码
#include using namespace std;typedef long long LL;const int N = 1e5 + 10;LL a[N];int n;int main(){ cin >> n; LL sum; for(int i = 1; i > a[i]; sum += a[i]; } LL mid = sum / 2; // 初始化 LL left = 1, right = 1, ret = 0, len = 0; while(right <= n) { // 进窗口 if(len mid) { // 更新结果 ret = max(sum - len, ret); // 出窗口 len -= a[left++]; } if(ret > mid) ret = sum - ret; ret = max(ret, len); } cout << ret << endl; return 0;}总之，对于双指针这类型的题目就四步：1. 初始化 2. 进窗口 3. 判断出窗口 4. 更新结果
明天我们将学习二分算法，感兴趣的朋友记得关注我哟~
886~
\"今天的bug是明天的经验值\"
