A. 放置石子
我们设第一格的东西为 \(x\) ，则接下来的格数为
\[2：1+x\\
3：2x+1\\
4：3x+2\\
5：5x+3\\
...
\]
易得x的系数就是原来的斐波那契额数列，而后面加上来的也是！我们可以打表
左边为系数表，右边为加的数表
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll xs[21] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765};
ll k[21] = {1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181};
int main()
{
freopen("kela.in", "r", stdin);
freopen("kela.out", "w", stdout);
long long a, x, b;
while (cin >> a >> x >> b)
{
if ((x - k[a]) % xs[a] == 0)
printf("%lld\n", (x - k[a]) / xs[a] * xs[b] + k[b]);
else
puts("-1");
}
return 0;
}
B.连通块数
暴力进行dfs即可，这里注意，每次进行dfs的时候都要扩展完毕，然后后面一遇到没扩展的就扩展
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int l, w, h, m;
int dx[7] = {0, 0, 0, 0, 0, 1, -1};
int dy[7] = {0, 0, 0, -1, 1, 0, 0};
int dz[7] = {0, 1, -1, 0, 0, 0, 0};
int a[N][N][N];
bool vis[N][N][N];
int ans = 0;
void dfs(int x, int y, int z)
{
for (int i = 1; i <= 6; i++)
{
int tx = x + dx[i], ty = y + dy[i], tz = z + dz[i];
if (tx < 1 || tx > l || ty < 1 || ty > w || tz < 1 || tz > h || vis[tx][ty][tz])
continue;
if (abs(a[x][y][z] - a[tx][ty][tz]) <= m)
{
vis[tx][ty][tz] = 1;
dfs(tx, ty, tz);
}
}
}
int main()
{
freopen("engineer.in", "r", stdin);
freopen("engineer.out", "w", stdout);
cin >> l >> w >> h;
cin >> m;
for (int i = 1; i <= l; i++)
for (int j = 1; j <= w; j++)
for (int k = 1; k <= h; k++)
cin >> a[i][j][k];
for (int i = 1; i <= l; i++)
for (int j = 1; j <= w; j++)
for (int k = 1; k <= h; k++)
{
if (!vis[i][j][k])//就是这里
{
ans++;
vis[i][j][k] = 1;
dfs(i, j, k);
}
}
cout << ans << endl;
return 0;
}
C.股票问题
反悔贪心模板题目
#include <bits/stdc++.h>
using namespace std;
int n;
priority_queue<int, vector<int>, greater<int>> q;
int main()
{
freopen("b.in", "r", stdin);
freopen("b.out", "w", stdout);
long long ans = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
int k;
cin >> k;
if (!q.empty() && q.top() < k)////如果今天的卖出股票比之前的某一天卖出股票更优的话，就买回之前的股票，然后再卖出今天的股票
ans += k - q.top(), q.pop(), q.push(k);
q.push(k);
}
cout << ans << endl;
return 0;
}
D.灯泡开关
考虑加上一个等差数列。
怎么维护呢？先差分这个数组，举个例子，如果要在0 0 0 0 0 0 0 0 0 0 0中的3-7加一个从1开始的等差数列，
0 0 1 2 3 4 5 0 0 0 0差分后变成0 0 1 1 1 1 1 -5 0 0 0，就是一个区间+1后在末尾减掉最后一个数，
再差分一次，0 0 1 1 1 1 1 -5 0 0 0就变成了0 0 1 0 0 0 0 -6 5 0 0，发现等差数列差分两次后的数组只涉及三个数的修改。
所以我们每次更新原来的答案数组的差分再差分数组，最后前缀和还原差分数组以及还原原数组即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int n, m;
ll a[N];
ll cnt[N][2];//cnt[i]表示以i为舒适值最多少走多少
//0,1分别是因为这是一个环差分。
ll check()
{
ll res = 0;
for (int i = 2; i <= n; i++)
{
if (a[i] > a[i - 1])
res += a[i] - a[i - 1];
else
res += a[i] + m - a[i - 1];
}
return res;
}
void change(int l, int r, int s)
{
// cout << l << ' ' << r << ' ' << s << endl;
cnt[l][0] += s;
cnt[r + 1][0] -= s;
cnt[l + 1][1] += 1;
cnt[r + 1][1] -= (r - l + 1);
cnt[r + 2][1] += (r - l);
}
int main()
{
freopen("light.in", "r", stdin);
freopen("light.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 2; i <= n; i++)
{
if (a[i] > a[i - 1])
{
if (a[i] - a[i - 1] >= 2)
change(a[i - 1] + 2, a[i], 1);
}
else
{
if (m - a[i - 1] >= 2)
change(a[i - 1] + 2, m, 1), change(1, a[i], m - a[i - 1]);
if (m - a[i - 1] == 1)
change(1, a[i], 1);
if (m == a[i - 1])
{
if (a[i] >= 2)
change(2, a[i], 1);
}
}
}
for (int i = 2; i <= m + 1; i++)
cnt[i][0] += cnt[i - 1][0], cnt[i][1] += cnt[i - 1][1];
for (int i = 2; i <= m + 1; i++)
cnt[i][1] += cnt[i - 1][1];
ll ans = 0;
for (int i = 1; i <= m; i++)
ans = max(ans, cnt[i][0] + cnt[i][1]);
cout << check() - ans << endl;
return 0;
}