k倍区间
题目链接：6.k倍区间 - 蓝桥云课
求有多少个连续区间满足，所有数字的和模k=0，也就是k的倍数。
当我们遍历到元素nums[i]时，假设前i个元素的和为mask，我们知道mask-mask%k一定是k的倍数，那么我们只需知道前i个元素中，前缀和为mask%k的子数组出现了多少次，最后结果加上出现次数即可。为了快速算出前缀和对应的出现多少次，我们可以用哈希表来存储。注意：hash[0]表示前缀和为0的有多少个 ，那么说明前i个元素可以整除k，满足条件，需要加上1，所以hash[0]=1
//k倍区间
#include <iostream>
#include <unordered_map>
using namespace std;
int a[10010];
int main()
{int n, k;unordered_map<int, int> hash;hash[0] = 1;cin >> n >> k;for (int i = 1; i <= n; i++){cin >> a[i];}int ans = 0;int mask = 0;for (int i = 1; i <= n; i++){mask += a[i];ans += hash[mask % k];hash[mask%k]++;}cout << ans << endl;return 0;
}分巧克力
题目链接：8.分巧克力 - 蓝桥云课
//分巧克力
#include <iostream>
using namespace std;
int n, k;
const int N = 1e5 + 10;
int h[N], w[N];
//分成边成x的 可以分给几个人
bool check(int x)
{int sum = 0;for (int i = 0; i < n; i++){sum += (h[i] / x) * (w[i] / x);}if (sum >= k)return true;elsereturn false;
}
int main()
{cin >> n >> k;for (int i = 0; i < n; i++)cin >> h[i] >> w[i];int l = 1, r = 100000;int max = 0;while (l <= r){int mid = l + (r - l) / 2;if (check(mid)){max = mid;l = mid + 1;}else{r = mid - 1;}}cout << max << endl;return 0;
}青蛙跳杯子
对于初始字符串st_str，求最少步数变成目标字符串end_str。题目中说的是青蛙可以进行的操作，其实也就是空杯子的操作，我们让青蛙保持不动，尝试移动空杯子，变成 目标的字符串。
而对于空杯子，可以进行的操作有6步[-3,-2,-1,1,2,3]，我们可以用一个map来存储字符串str和它对应的操作次数。从初始字符串开始，每次经过一步，得到一个新字符串str，如果该字符串在map中不存在，那么就插入该字串，如果存在就跳过。然后判断变化后的字符串和目标字符串end_str是否相等，如果相等，直接返回map[str]即可。
具体细节看下面代码：
//青蛙跳杯子
#include <iostream>
#include <string>
#include <map>
#include <queue>
using namespace std;int d[6] = { -3,-2,-1,1,2,3 };//青蛙的步数int main()
{map<string, int> mp;//从str_end变到当前的步数string st_str, end_str;cin >> st_str >> end_str;int n = st_str.size();queue<string> q;q.push(st_str);mp[st_str] = 0;while (!q.empty()){string ss = q.front();q.pop();int cnt = mp[ss];int x = ss.find('*');//拓展6个方向for (int i = 0; i < 6; i++){int z = x + d[i];if (z >= 0 && z < n){swap(ss[x], ss[z]);if (!mp.count(ss)){mp[ss] = cnt + 1;if (ss == end_str){cout << mp[ss] << endl;return 0;}q.push(ss);}swap(ss[x], ss[z]);//还原现场}}}cout << -1 << endl;return 0;
}
