C.刷题统计
分析
假设刷的题数为x, 可以知道,刷的题数 = n周 + m天
一周做的题数 = 5 * a + 2 * b
,那么,n周 = x/(一周做的题数)。
m天需要从余数里判断,分为下面两种情况
- x <= 5*a: 5天内就能够写完,需要的时间 = x/a (上取整)
- x > 5a: 5天内不能够写完,需要的时间 = (x-5a)/b (下取整)。
实现
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
int32_t main()
{
int a, b, n;
cin >> a >> b >> n;
int week = n / (5 * a + 2 * b);
int rem = n % (5 * a + 2 * b);
int day = 0;
if (rem <= 5 * a) {
day += (rem - 1 + a) / a; //上取整
}
else {
day = 5;
rem -= 5 * a;
day += (rem - 1 + b) / b;
}
cout << week * 7 + day;
return 0;
}
D.修建灌木
分析
画图模拟一下就会发现,每颗灌木的最大距离 = 离左边界的距离的两倍
和 离右边界的距离的两倍
的最大值
实现
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int maxh[N];
int main()
{
int n;
cin >> n;
int left = 1, right = n;
for (int i = 1;i <= n;i++)
{
int ld = (i - 1) * 2;
int rd = (n - i) * 2;
maxh[i] = max(ld, rd);
cout << maxh[i] << '\n';
}
return 0;
}
E.X进制减法(贪心)
一道很简单的贪心题,我看错题了想得有点复杂…
分析
关键: 做出贪心决策需要高位从低位开始做,因为高位的A[i] > B[i]
给差值带来的增加远大于A[i] < B[i]
给差值带来的增加,如果从低位到高位开始扫描,做出的贪心决策是局部的,而从高位到低位开始扫描,可以扩展到全局。
首先需要做出一个贪心决策(下面分为多情况讨论,不过这里A默认>=B)
-
A>=B: 根据关键给出的解释,如果A>=B,低位如果在
A[i] < B[i]
选出n,这很显然是错误的,由于A>=B,最前面的高位一定有A[i]>b[i],为了让差值最小,i及i后面(比i低的位)都要选择最小进制。 -
A<B: 与上面相反,由于A<B,最前面的高位一定有A[i]<b[i],为了让差值最小,i及i后面的所有位都要选择最大进制。
那么,从低位到高位把A,B累加起来就可以了,这里取模卡的很恶心,一定要写成a[i]-b[i]
的形式,如果写成res + a[i]
再res - b[i]
就会报错
实现
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
const int mod = 1000000007;
const int N = 1e5 + 10;
int32_t main()
{
int n;
int la, lb;
vector<int> a(N);
vector<int> b(N);
vector<int> bit(N);
cin >> n
>> la;
for (int i = 0;i < la;i++)
cin >> a[i];
cin >> lb;
for (int i = 0;i < lb;i++)
cin >> b[i];
reverse(a.begin(), a.begin() + la);
reverse(b.begin(), b.begin() + lb);
for (int i = 0;i < la;i++)
bit[i] = max(2ll, max(a[i], b[i]) + 1);
//由于这里默认是A>=B,所以不用判断了
int res = 0;
for (int i = 0,j=1;i < la;i++)
{
res = (res + j * (a[i] - b[i]))% mod;
res = (res%mod + mod) % mod;
j = j * bit[i] % mod;
}
cout << res << endl;
return 0;
}
F.统计子矩阵(二分优化,尺取优化)
前缀和+二分/双指针
分析
关键: 注意到有一个关键的性质,即0<=aij<=1000
,由于子矩阵扩大只增加不减少,因此可以使用二分和双指针来优化
实现
二分(超时了)
怎么会有人喜欢卡二分啊!
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
const int mod = 1000000007;
const int N = 510;
vector<vector<int>> a(N, vector<int>(N));
vector<vector<int>> s(N, vector<int>(N));
int n, m, k;
int sum(int x1, int y1, int x2, int y2)
{
return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}
bool check(int x1, int y1, int x2, int y2)
{
int s = sum(x1, y1, x2, y2);
if (s <= k)return true;
return false;
}
int32_t main()
{
cin >> n >> m >> k;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
cin >> a[i][j];
//前缀和
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
int res = 0;
for(int x1=1;x1<=n;x1++)
for(int y1=1;y1<=m;y1++)
for (int x2 = x1;x2 <= n;x2++)
{//枚举左上角顶点,和右下角的横坐标
//二分找到最后一个<k的纵坐标,右侧边界模板
int l = y1, r = m;
while (l < r)
{
int mid = l + r + 1>> 1;
if (check(x1, y1, x2, mid))
l = mid;
else r = mid - 1;
}
if (check(x1, y1, x2, l))
res += (l - y1) + 1;
}
cout << res << endl;
return 0;
}
双指针
如果是右移右端点的双指针常数比较大,while循环需要左移左端点,否则容易被卡常
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(fast)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
const int N = 510;
int a[N][N];
int s[N][N];
int n, m, k;
int sum(int x1, int y1, int x2, int y2)
{
return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}
bool check(int x1, int y1, int x2, int y2)
{
int s = sum(x1, y1, x2, y2);
if (s <= k)return true;
return false;
}
int32_t main()
{
cin >> n >> m >> k;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
scanf("%d",&s[i][j]);
//前缀和
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
s[i][j] = s[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
int res = 0;
for (int x1 = 1;x1 <= n;x1++)
for (int x2 = x1;x2 <= n;x2++)
{//尺取纵坐标
for (int l = 1, r = 1;l <= m;l++)
{
//右移右指针到满足条件位置
while (r <= m && check(x1, l, x2, r))
r++;
res += (r - l);
}
}
cout << res << endl;
return 0;
}
H.积木画(状态机dp)
首先自己手画一下2x4有多少个方案,只要你画对了这题就能ac了(
分析
关键: 这题的关键在于画图,定义状态
首先,有两种方块,摆放的方式如下
定义dp状态:dp[i][j],摆放完前i行,且此时摆放的状态为j的所有集合
由于dp需要无后效性,因此第i行时,摆放为这样子是认为不合法的
经过画图,可以发现dp的五种状态,其他状态都可以由这五个状态导出
状态表示: dp[i][j]:摆放完前i行,且此时摆放的状态为j的所有集合
状态计算:
- dp[i][0]:
- dp[i-1][0]: 再放一个积木1
- dp[i-2][0]: 再放两个积木1
- dp[i][1],dp[i][2]: 再放一个积木2
- dp[i][1],dp[i][2]:
- dp[i-1][3],dp[i-1][4]: 什么也不放
- dp[i][3],dp[i][4]:
- dp[i-2][0]: 再放一个积木2
- dp[i][1],dp[i][2]: 再放一个积木1 (这个很容易漏掉)
状态转移:
dp[i][1] = dp[i - 1][3];
dp[i][2] = dp[i - 1][4];
dp[i][3] = (dp[i - 2][0] + dp[i][1])%mod;
dp[i][4] = (dp[i - 2][0] + dp[i][2])%mod;
dp[i][0] = (0ll + dp[i - 2][0] + dp[i - 1][0] + dp[i][1] + dp[i][2]) % mod;
实现
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e7 + 10;
const int mod = 1e9 + 7;
int dp[N][6];
int main()
{
int n;
cin >> n;
dp[1][0] = 1;
dp[2][0] = 2;
dp[2][3] = 1;
dp[2][4] = 1;
for (int i = 3;i <= n;i++)
{
dp[i][1] = dp[i - 1][3];
dp[i][2] = dp[i - 1][4];
dp[i][3] = (dp[i - 2][0] + dp[i][1])%mod;
dp[i][4] = (dp[i - 2][0] + dp[i][2])%mod;
dp[i][0] = (0ll + dp[i - 2][0] + dp[i - 1][0] + dp[i][1] + dp[i][2]) % mod;
}
cout << dp[n][0] << endl;
return 0;
}
I.扫雷(bfs,离散化)
我写的写法会超时…
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <unordered_map>
using namespace std;
const int N = 2e5 + 10;
struct node
{
int x, y, r;
};
int n, m;
typedef pair<int, int> PII;
map<PII, int> is_boom; //该点是否爆炸
map<PII, vector<int>> mp; //在坐标上的地雷的编号
bool st[N];
bool check(int sx, int sy, int ex, int ey, int r)
{//判断(sx,sy)能否引爆(ex,ey)
int dx = (ex - sx) * (ex - sx);
int dy = (ey - sy) * (ey - sy);
if (dx + dy <= r * r)
return true;
return false;
}
void bfs(vector<node>& a, vector<node>& b)
{
queue<node> q;
for (int i = 1;i <= m;i++)
{
is_boom[{b[i].x, b[i].y}]++; //排雷火箭爆炸
q.push(b[i]);
}
int res = 0;
while (q.size())
{
auto v = q.front();
q.pop();
int x = v.x, y = v.y;
int r = v.r;
for (int i = x - r;i <= x + r;i++)
for (int j = y - r;j <= y + r;j++)
{
if (i < 0 || j < 0 || is_boom.count({ i,j })) continue;
if (!check(x, y, i, j, r)) continue;
is_boom[{i, j}]++;
vector<int>& arr = mp[{i, j}];
for (auto& t : arr)
{
q.push(a[t]);
st[t] = true;
}
}
}
}
void solve()
{
cin >> n >> m;
vector<node> a(n + 10);
vector<node> b(m + 10);
for (int i = 1;i <= n;i++)
{
cin >> a[i].x >> a[i].y >> a[i].r;
mp[{a[i].x, a[i].y}].push_back(i);
}
for (int i = 1;i <= m;i++)
cin >> b[i].x >> b[i].y >> b[i].r;
int res = 0;
for (int i = 1;i <= n;i++)
res += st[i];
bfs(a,b);
cout << res << endl;
}
int32_t main()
{
cin.tie(0), cout.tie(0);
ios::sync_with_stdio(false);
int t;
t = 1;
while (t--)
solve();
return 0;
}
J.李白打酒(状态机dp,记忆化搜索)
分析
性质:
- 刚开始只有2斗
- 遇到花一定-1,遇到店一定*2
- 最后一次一定是花,并且一定要恰好喝完
根据这上面三个性质,可以发现,我们的酒一定不会超过 N次(1<=N<=100),因为要恰好喝完,如果超过一百就不合法可以直接退出
暴力的做法,需要维护三个状态: 当前坐标i
,遇到第几个花
,当前的酒
。
由于三个变量的范围都是100,可以用记忆化搜索存下来,也可以改写为dp
状态表示: dp[i][j][k]: 当前走了i次,且遇到j次花,酒还剩下k的所有集合
状态计算: 划分依据为,这次遇到的是啥,然后转移到下一个状态
这里使用的是转移到哪些状态,而不是由哪些状态转移而来
- 遇到的是花, –>dp[i+1][j+1][k-1]
- 遇到的是店, –>dp[i+1][j][k<<1] (注意判断k)
实现
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <unordered_map>
#define int long long
using namespace std;
const int N = 2e2 + 10;
const int mod = 1e9 + 7;
int dp[N][N][N];
void solve()
{
int n, m;
cin >> n >> m;
dp[0][0][2] = 1;
for (int i = 0;i <= n + m;i++)
for (int j = 0;j <= m;j++)
for (int k = 0;k < N;k++)
{
if(k>=1)
dp[i + 1][j + 1][k - 1] = (dp[i + 1][j + 1][k - 1] + dp[i][j][k]) % mod;
if (k * 2 < N)
dp[i + 1][j][k * 2] = (dp[i + 1][j][k * 2] + dp[i][j][k]) % mod;
}
//由于最后一次一定遇到的是花
dp[n + m][m][0] = dp[n + m - 1][m - 1][1] % mod;
cout << dp[n + m][m][0] << endl;
}
int32_t main()
{
cin.tie(0), cout.tie(0);
ios::sync_with_stdio(false);
int t;
t = 1;
while (t--)
solve();
return 0;
}
K.砍竹子(贪心,优先队列,区间合并)
分析
根据样例可以做出一个贪心假设
贪心假设: 每次都砍最高的连续的一段,知道所有竹子都是1
可以用暴力的做法进行枚举,但是O(n^2)会超时
由于每次都砍连续的一段 + 最高的一段,可以用优先队列O(logn)找到,而连续需要用区间合并的思想
由于每次堆顶的高度都相同,因此可以用下面进行判断
bool check(node x, node y)
{
int lx = x.st, rx = x.st + x.len - 1;
int ly = y.st, ry = y.st + y.len - 1;
if (lx <= ly && ly <= rx)
return true;
if (ly == rx + 1)
return true;
return false;
}
如果return true,说明两段可以区间合并,合并在一起一起操作,因此需要一个while循环找到所有堆顶可以区间合并的段
实现
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <unordered_map>
#define int long long
using namespace std;
typedef pair<int, int> PII;
struct node
{
int val;
int st, len;
bool operator < (const node b)const
{
if (val != b.val)
return val < b.val;
if (st != b.st)
return st > b.st;
}
};
bool check(node x, node y)
{
int lx = x.st, rx = x.st + x.len - 1;
int ly = y.st, ry = y.st + y.len - 1;
if (lx <= ly && ly <= rx)
return true;
if (ly == rx + 1)
return true;
return false;
}
void solve()
{
int n;
cin >> n;
vector<int> h(n + 10);
int last = -1;
int len = 0;
priority_queue<node, vector<node>> heap;
for (int i = 1;i <= n;i++)
{
cin >> h[i];
heap.push({h[i],i,1});
}
int res = 0;
while (heap.size())
{
auto v = heap.top();
heap.pop();
if(v.val == 1) break;
while (heap.size() && heap.top().val == v.val && (check(v, heap.top()) || check(heap.top(),v)))
{
node x = v, y = heap.top();
int lx = x.st, rx = x.st + x.len - 1;
int ly = y.st, ry = y.st + y.len - 1;
lx = min(lx, ly);
ly = max(ly, ry);
v.len = ly - lx + 1;v.st = lx;
heap.pop();
}
int val = sqrt((v.val >> 1) + 1);
if (val != 1)
heap.push({ val,v.st,v.len });
res++;
}
cout << res << endl;
}
int32_t main()
{
cin.tie(0), cout.tie(0);
ios::sync_with_stdio(false);
int t;
t = 1;
while (t--)
solve();
return 0;
}