好想打游戏啊。。。
A. Add and Divide
给定a和b，有两种操作$$ a = lfloor frac{a}{b} floor或者b = b + 1$$ 问最少要多少步操作令a = 0
b至少为2，挨个枚举b，找到最小值即可
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
ll t;
ll n, m;
ll a,b;
string s;
ll dat[100000 + 5] = {};
vector<ll> pos[100000 + 5];
int main() {
ios::sync_with_stdio(0);
cin >> t;
while (t--)
{
ll ans = 100000000;
cin >> a >> b;
ll k = 0;
if (b == 1) {
k++;
}
while (1)
{
ll ta = a;
ll tmp = k;
while (ta)
{
ta /= k+b;
tmp++;
}
if (tmp <=ans)ans = tmp;
else break;
k++;
}
cout << ans << '
';
}
}
B. Replace and Keep Sorted
给定个数字k，称两个长度为k的数组k相似当且仅当：长度相同，都严格递增，只有一位数字不同，数字范围为1到k，给定k与一个严格递增的数组a，q次查询。每次给定l和r，问a的子串a[l]到a[r]的k相似数组有多少个
可以计算数组中每个数可以取的可能个数，用前缀和处理一下即可。
注意两端能够取得的上下限改变了，单独计算下
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
ll t;
ll n,q,k;
ll a,b;
string s;
ll dat[1000000 + 5] = {};
ll dat2[1000000 + 5] = {};
vector<ll> pos[100000 + 5];
int main() {
ios::sync_with_stdio(0);
cin >> n >> q >> k;
for (int i = 1; i <=n; i++) {
cin >> dat[i];
}
dat[n + 1] = k + 1;
for (int i = 1; i <= n; i++) {
dat2[i] = dat[i + 1] - dat[i-1] - 2;
}
for (int i = 1; i <= n; i++)dat2[i] += dat2[i - 1];
for (int i = 0; i < q; i++) {
ll l, r;
cin >> l >> r;
ll ans;
ans = dat[l+1] - 2 + k - dat[r-1]-1 + dat2[r - 1] - dat2[l];
cout << ans << '
';
}
}
C. Floor and Mod
如果两个数a和b满足$$lfloor frac{a}{b} floor = a mod b$$ 称之为特别，给定x，y，问在$$ 1leq a leq x 且 1leq b leq y $$ 条件下有多少对a和b
令$$lfloor frac{a}{b} floor = a mod b = K， 则 a = (b+1) imes K 且 K le b-1 ，所以bleq sqrt{(a+1)} 的时候，k能选1到b-1的任何值，b > sqrt{(a+1)} 时 K leq lfloor frac{a}{b} floor 都能选到。$$用整数分块即可。
关于整数分块：
我们只要知道，对于i和n，存在最大的x令$$lfloorfrac{n}{i} floor=lfloorfrac{n}{x} floor时，x=lfloorfrac{n}{lfloorfrac{n}{i} floor} floor$$
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
ll t;
ll n, q, k;
ll a, b;
string s;
ll dat[1000000 + 5] = {};
ll dat2[1000000 + 5] = {};
vector<ll> pos[100000 + 5];
int main() {
ios::sync_with_stdio(0);
cin >> t;
while (t--)
{
ll x, y, ans;
cin >> x >> y;
ll tmp1;
tmp1 = floor(sqrt(1.0 * x + 1)) - 1;
if (tmp1 >= y - 1) {
tmp1 = y - 1;
cout << tmp1 * (1 + tmp1) / 2 << '
';
continue;
}
ans = tmp1 * (1 + tmp1) / 2;
for (ll l = tmp1+3, r; l <= y+1; l = r + 1)
{
ll tmp = x / l;
if (!tmp)r = y + 2;
else
r = min(x / (x / l),y+1);
ans += (r - l + 1) * (tmp);
}
cout << ans << '
';
}
}
D. Multiples and Power Differences
给你个矩阵，叫你建立个新的矩阵，每个数都是原矩阵的倍数，且新矩阵中相邻的数之差的绝对值都是某个整数的四次方
原矩阵中的数范围为1到16
先构造个数为原矩阵中所有数的整数倍，即1到16求lcm，记为tmp，之后交替生成新矩阵，令每个tmp四周的数分别为tmp加上四周数自身的四次方，每个不是tmp的数四周都是tmp即可
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
ll n, m;
string s;
ll dat[1000 + 5][1000 + 5];
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
int main() {
ios::sync_with_stdio(0);
ll tmp = 1;
for (int i = 1; i <= 16; i++)
tmp = tmp * i / (gcd(tmp, i));
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> dat[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i % 2 ^ j % 2)cout << tmp;
else cout << tmp + dat[i][j] * dat[i][j] * dat[i][j] * dat[i][j];
cout << ' ';
}
cout << '
';
}
}
E. Move and Swap
给定一颗树，每个叶子节点的深度都相同。有红蓝两个硬币，从根部往下运动，每次红硬币可以选一个儿子节点走，蓝硬币可以在与红硬币相同深度任选个节点，随后红蓝硬币可以选择交换位置，答案加上红蓝硬币对应节点值之差的绝对值。走到叶子节点后答案最大值是多少。
好难啊。。看题解都看了半天，麻了
考虑dp，dp[i]为结束一轮操作后红硬币到达i时的最大值,j为蓝硬币位置
如果红硬币是从上面走下来的dp[i]=max(dp[fa[i]]+abs(dat[i]-dat[j])，dp[i])显然j为当前层最大或最小的节点
如果红硬币是已经交换过的，那么j才是从上面下来的位置dp[i]=max(dp[fa[j]]+abs(dat[i]-dat[j]),dp[i])=max(dp[fa[j]]+dat[j]-dat[i],dp[fa[j]]-dat[j]+dat[i],dp[i])
所以我们维护每层的最大最小dat[i]，以及dp[fa[j]]+dat[j]。dp[fa[j]]-dat[j]的最大值即可
注意初始化的时候最小值要足够小（
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
ll t,n,deep,ans;
vector<int> dep[200000+5],mp[200000+5];
ll maxi[200000 + 5], mini[200000 + 5],fa[200000+5],dat[200000+5];
vector<ll> dp;
void dfs(ll n,ll pos) {
dep[n].push_back(pos);
deep = max(deep, n);
maxi[n] = max(maxi[n], dat[pos]);
mini[n] = min(mini[n], dat[pos]);
for (int i = 0; i < mp[pos].size(); i++) {
dfs(n + 1, mp[pos][i]);
}
return;
}
int main() {
ios::sync_with_stdio(0);
cin >> t;
while (t--)
{
cin >> n;
deep = 0;
ans = 0;
dp = vector<ll>(n+1);
for (int i = 0; i <= n; i++) {
dep[i] = vector<int>(), mp[i] = vector<int>();
maxi[i] = -1;
mini[i] = 0x3f3f3f3f3f;
}
for (int i = 2; i <=n; i++) {
cin >> fa[i];
mp[fa[i]].push_back(i);
}
for (int i = 2; i <=n; i++)cin >> dat[i];
dfs(1, 1);
for (int i = 2; i <= deep; i++) {
ll max1 = -10000000000, max2 = -10000000000;
for (int j = 0; j < dep[i].size(); j++) {
ll tmp = dep[i][j];
max1 = max(max1, dp[fa[tmp]] - dat[tmp]);
max2 = max(max2, dp[fa[tmp]] + dat[tmp]);
}
for (int j = 0; j < dep[i].size(); j++) {
ll tmp = dep[i][j];
dp[tmp] = !dp[tmp]? dp[fa[tmp]] + abs(dat[tmp] - mini[i]) :max(dp[tmp], dp[fa[tmp]] + abs(dat[tmp] - mini[i]));
dp[tmp] = max(dp[tmp], dp[fa[tmp]] + abs(dat[tmp] - maxi[i]));
dp[tmp] = max(dp[tmp], dat[tmp] + max1);
dp[tmp] = max(dp[tmp], max2 - dat[tmp]);
ans = max(dp[tmp],ans);
}
}
cout << ans << '
';
}
}
F. Copy or Prefix Sum
给定数组b 问能构成多少个数组a 其中$$b_i=a_i或b_i = sum_{j=1}^{i} a_j$$ 答案按1e9+7取模
这个也是个离奇的dp
考虑dp[i][j]表示前i个数和为j的情况，显然dp[0][0]=1
又有以下转移
第一条式子相当于把所有的dp[i-1][j]右移了b[i]，第二个相当于把dp[i][j]加上了ans-dp[i-1][0]
维护一个偏移量res，每次更新先更新ans+=ans-dp[0-res],更新偏移量res+=b[i]，后更新新一层的dp[b[i]-res]即可
用map（
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
ll t,n;
ll mod = 1e9 + 7;
map<ll, ll> dp;
int main() {
ios::sync_with_stdio(0);
cin >> t;
while (t--)
{
cin >> n;
dp = map<ll, ll>();
ll res = 0, ans = 1,b;
dp[0] = 1;
for (int i = 0; i < n; i++) {
cin >> b;
ll pre = (mod + ans - dp[0 - res]) % mod;
res += b;
ans = (ans + pre) % mod;
dp[b - res] = (dp[b - res] + pre) % mod;
}
cout << ans << '
';
}
}