E
贪心
易知场上原有的怪物不论先后都会攻击一次，最终结果为差，因此只用考虑亡语召唤造成的伤害
最小伤害
z为0的怪物留到最后再攻击，之前让他们一直占着坑，可直接从怪物数量上限中减去。剩下的z大于0的怪物依次攻击一遍，剩下召唤出的怪物，若理论上召唤的怪物数量 > 容量(减小后)，则伤害为容量，反之为召唤的怪物数量。(即二者取较小值)
最大伤害
让怪物攻击的次数尽可能多，及让亡语召唤尽可能多。先让最小的怪物攻击，再让亡语召唤的怪物去攻击，及时腾出空间。
造成伤害连续
在求最小伤害时，的怪物攻击顺序任意。若按递增的顺序进行攻击，当亡语溢出时，先让一个的怪物去攻击，腾出一个空间，这样可使造成伤害多1。以此类推，当清理掉两个的怪物时，造成伤害多2……直到把所有的怪物清理完，就变成了造成最大伤害的方案。
时间复杂度
int limit, x, n;
ll y;
int z, num;
struct Node {
int z, num;
} s[1000010];
bool cmp(Node& a, Node& b) {
return a.z < b.z;
}
signed main() {
jiasu;
int t;
cin >> t;
while (t--) {
cin >> limit >> n >> x >> y;
rep(i, 1, n) cin >> s[i].z >> s[i].num;
if (x == 0) {
cout << 1 << endl;
continue;
}
ll maxn = 0, minx = limit, sum = 0;
ll temp = limit;
// 造成最小伤害
rep(i, 1, n) {
if (s[i].z)
sum += (ll)s[i].z * s[i].num; // 注意开ll
else
minx -= s[i].num;
temp -= s[i].num; // 计算初始剩余空位
}
minx = min(minx, sum);
// 造成最大伤害
sort(s + 1, s + 1 + n, cmp);
rep(i, 1, n) {
if (s[i].z <= temp + 1) // 该类怪物第一个就不会溢出
maxn += s[i].z * s[i].num;
else if (temp + s[i].num <= s[i].z) // 该类怪物到最后一个还会溢出
maxn += (temp + 1 + temp + s[i].num) * s[i].num / 2;
else { // 从中间开始不会溢出
ll cnt = s[i].z - temp;
maxn += (temp + 1 + temp + cnt) * cnt / 2; // 前半部分
maxn += (s[i].num - cnt) * s[i].z;
}
temp += s[i].num;
}
cout << maxn - minx + 1 << endl;
}
return 0;
}
F 玩游戏
思维题
① 第轮手牌为或的人将退出
② 当只剩一个人的时候他将退出(终止循环的条件)
③ 场上人数与剩余范围内的数相同时所有人都能判断(终止循环的条件)
方法：按手牌大小排序(注意保存序号)，双指针扫描。
时间复杂度
int n, m;
pii s[100010];
signed main() {
jiasu;
int t;
cin >> t;
while (t--) {
cin >> n >> m;
rep(i, 1, n) {
cin >> s[i].first;
s[i].second = i;
}
sort(s + 1, s + 1 + n);
int l = 1, r = n; // 双指针
int minx = 1, maxn = m; // 范围
int k = 1; // 记录第几轮游戏
while (l < r) {
if (maxn - minx == r - l)
break;
if (s[l].first == minx) {
if (s[l].second == 1)
break;
l++;
}
if (s[r].first == maxn) {
if (s[r].second == 1)
break;
r--;
}
k++, maxn--, minx++;
}
cout << k << endl;
}
return 0;
}
G 生蚝接柿子
数据结构优化DP（可用线段树或单调队列 维护区间最大值）（这里用单调队列）
分两步, 先继承上一阶段的状态, 再接柿子。
当左手在位置时能接到第 个柿子，该位置的个数
时间复杂度
const int N = 3010, M = 3000;
int n, v, x, len;
pii a[N];
int f[N], g[N], q[N];
signed main() {
jiasu;
cin >> n >> v >> x >> len;
len--;
rep(i, 1, n) { cin >> a[i].second >> a[i].first; }
sort(a + 1, a + 1 + n); // 按纵坐标排序
memset(f, 0xcf, sizeof f);
f[x] = 0;
rep(i, 1, n) { // 柿子
int temp = (a[i].first - a[i - 1].first) * v;
memcpy(g, f, sizeof g);
memset(f, 0xcf, sizeof f);
int hh = 1, tt = 0;
// 第一步DP
for (int i = 1, j = 1; i <= M; i++) {
while (j <= M && j <= i + temp) {
while (hh <= tt && g[j] >= g[q[tt]])
tt--;
q[++tt] = j;
j++;
}
while (hh <= tt && q[hh] < i - temp)
hh++;
f[i] = g[q[hh]];
}
// 第二步DP
rep(j, 1, M) { // 左手位置
if (j <= a[i].second && j + len >= a[i].second)
f[j]++;
}
}
int ans = 0;
rep(i, 1, M) ans = max(ans, f[i]);
cout << ans << endl;
return 0;
}
H 和生蚝一起做乘法吧
统计每个二进制位上为1的数的个数，找到除了位以外的位上1最多的个数k，先分出个，剩下的个数尽量取最大。
贪心策略证明
将每个数的二进制位分开，即，这样最后所有数相乘得到的式子的每一项都是在每个数的二进制位中选一位得到的，贪心策略是每个数都尽量取最大，这使得后面的数能选的二进制位最少，因此按照该策略得出的式子的所有项的多重集是其他任何可能式子的子集，则最小.
时间复杂度
const int mod = 1e9 + 7;
ll l, r, cnt[64], f[64];
pair<ll, int> p[64];
ll qmi(ll a, ll k) {
ll res = 1;
while (k) {
if (k & 1)
res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}
signed main() {
int t;
scanf("%d", &t);
f[0] = 1;
rep(i, 1, 60) f[i] = (f[i - 1] << 1) % mod;
while (t--) {
scanf("%lld %lld", &l, &r);
// l~r中每个二进制位上1的个数
rep(i, 0, 60) {
cnt[i] = 0;
if((r >> i) == (l >> i )){
if((l >> i) & 1)
cnt[i] = r - l + 1;
continue;
}
ll x = (r >> i) - (l >> i) + 1;
if((l >> i) & 1)
cnt[i] += (x >> 1) * (1ll << i);
else
cnt[i] += (x + 1 >> 1) * (1ll << i);
if((l >> i) & 1)
cnt[i] += (1ll << i) + (l & ((1ll << i) - 1))
if((r >> i) & 1)
cnt[i] += (r & ((1ll << i) - 1)) + 1;
}
ll maxn = 0;
rep(i, 1, 60) maxn = max(maxn, cnt[i]);
ll fr = r - l + 1 - maxn; // 先选出fr个1
cnt[0] -= fr; // 可证明cnt[0] >= fr
int idx = 0;
rep(i, 0, 60) if (cnt[i])
p[idx++] = {cnt[i], i}; // 由于要排序,先保存序号
sort(p, p + idx, greater<pair<ll, int>>());
ll ans = 1, temp = 0;
p[idx].first = 0;
rep(i, 0, idx - 1) {
temp = (temp + f[p[i].second]) % mod;
if (p[i].first != p[i + 1].first) {
ans = ans * qmi(temp, p[i].first - p[i + 1].first) % mod;
}
}
printf("%d\n", ans);
}
return 0;
}
I 突破模式
每个节点所需士兵数量与其到根节点的路径上所有节点都有关，因此从根向下遍历，并向下传递本节点的信息。
const int N = 1e5 + 10;
int n, m;
vector<int> mp[N];
int a[N], b[N], din[N], dist[N], ans, temp;
// dist[] 该节点到达根节点路径上原有士兵的和
void dfs(int id, int val) { // 节点编号，该节点走到根节点至少累积多少士兵
int num = val - dist[id]; // 减去原有士兵即为新增士兵
temp = min(temp, num); // 不断更新最小值
for (auto x : mp[id]) {
dist[x] = dist[id] + a[x];
dfs(x, max(val, b[x] + dist[id]));
}
}
signed main() {
jiasu;
cin >> n >> m;
rep(i, 1, n) cin >> a[i] >> b[i];
rep(i, 1, n - m) {
int x, y;
cin >> x >> y;
mp[y].push_back(x);
din[x]++;
}
rep(i, 1, n) {
if (!din[i]) {
temp = 0x7fffffff;
dist[i] = a[i];
dfs(i, b[i]);
ans += temp;
}
}
cout << ans << endl;
return 0;
}
J Awa不会打音游
状压DP + 滚动数组
最左边的手指只能按1/2道，第二根只能按2/3道，第三根只能按3/4道，第四根只能按4/5道
用一个四位二进制数表示手指的状态，空闲的手指为0
很大，需要用滚动数组
按住
松开
int n, idx;
int f[2][20]; // 第二维是每个手指的状态，空闲时为0
struct Node {
int Time, type, road; // type 为1 表示出现，type为0表示消失
bool operator<(const Node& temp) const {
if (this->Time != temp.Time)
return Time < temp.Time;
return this->type == 0 && temp.type != 0;
} // 先出现的在前，时间相同时先消失后出现
} s[2000010];
signed main() {
jiasu;
cin >> n;
rep(i, 1, n) {
int x, y, z;
cin >> x >> y >> z; // 将每个长条拆成两个点
s[idx++] = {x, 1, z}, s[idx++] = {y, 0, z};
}
sort(s, s + idx);
f[1][0] = 1;
for (int i = 0; i < idx; i++) {
rep(j, 0, 15) f[i & 1][j] = 0; // 先把该层清空
if (s[i].type == 1) { // 需要按住,该类状态至少为1
if (s[i].road == 1) {
rep(j, 1, 15) {
if (j & 8)
f[i & 1][j] |= f[i & 1 ^ 1][j - 8];
}
} else if (s[i].road == 5) {
rep(j, 1, 15) {
if (j & 1)
f[i & 1][j] |= f[i & 1 ^ 1][j - 1];
}
} else if (s[i].road == 2) {
rep(j, 1, 15) {
if (j & 8)
f[i & 1][j] |= f[i & 1 ^ 1][j - 8];
if (j & 4)
f[i & 1][j] |= f[i & 1 ^ 1][j - 4];
}
} else if (s[i].road == 4) {
rep(j, 1, 15) {
if (j & 1)
f[i & 1][j] |= f[i & 1 ^ 1][j - 1];
if (j & 2)
f[i & 1][j] |= f[i & 1 ^ 1][j - 2];
}
} else if (s[i].road == 3) {
rep(j, 1, 15) {
if (j & 2)
f[i & 1][j] |= f[i & 1 ^ 1][j - 2];
if (j & 4)
f[i & 1][j] |= f[i & 1 ^ 1][j - 4];
}
}
} else { // 需要松开,该类状态至多为14
if (s[i].road == 1) {
rep(j, 0, 14) {
if ((j & 8) == 0)
f[i & 1][j] |= f[i & 1 ^ 1][j + 8];
}
} else if (s[i].road == 5) {
rep(j, 0, 14) {
if ((j & 1) == 0)
f[i & 1][j] |= f[i & 1 ^ 1][j + 1];
}
} else if (s[i].road == 2) {
rep(j, 0, 14) {
if ((j & 8) == 0)
f[i & 1][j] |= f[i & 1 ^ 1][j + 8];
if ((j & 4) == 0)
f[i & 1][j] |= f[i & 1 ^ 1][j + 4];
}
} else if (s[i].road == 4) {
rep(j, 0, 14) {
if ((j & 1) == 0)
f[i & 1][j] |= f[i & 1 ^ 1][j + 1];
if ((j & 2) == 0)
f[i & 1][j] |= f[i & 1 ^ 1][j + 2];
}
} else if (s[i].road == 3) {
rep(j, 0, 14) {
if ((j & 2) == 0)
f[i & 1][j] |= f[i & 1 ^ 1][j + 2];
if ((j & 4) == 0)
f[i & 1][j] |= f[i & 1 ^ 1][j + 4];
}
}
}
}
if (f[1][0])
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
K 新生训练
数据范围很小，直接暴力即可。比较分子分母同除以，与删去相同数字是否相等。将符合条件的存入结构体，最后排序输出。
时间复杂度
bool st[6], ed[6];
struct Node {
int x, y, a, b;
};
vector<Node> ans;
bool cmp(Node& j, Node& k) {
if (j.x * k.y != k.x * j.y)
return j.x * k.y < k.x * j.y;
return j.x < k.x;
}
void itoa(int n, char* str) {
int idx = 0;
while (n) {
str[idx++] = n % 10 + '0';
n /= 10;
}
reverse(str, str + idx);
str[idx] = '\0';
}
signed main() {
jiasu;
int x, y, a, b;
cin >> x >> y >> a >> b;
for (int i = x; i <= y; i++) {
for (int j = a; j <= b; j++) {
mem(st);
mem(ed);
int gcd = __gcd(i, j);
int fenzi = i / gcd;
int fenmu = j / gcd;
char s1[6], s2[6];
itoa(i, s1);
itoa(j, s2);
for (int k = 0; s1[k]; k++) {
for (int l = 0; s2[l]; l++) {
if (ed[l])
continue;
if (s1[k] == s2[l]) {
st[k] = ed[l] = 1;
break;
}
}
}
int zi = 0, mu = 0;
for (int k = 0; s1[k]; k++) {
if (st[k])
continue;
zi = zi * 10 + s1[k] - '0';
}
for (int l = 0; s2[l]; l++) {
if (ed[l])
continue;
mu = mu * 10 + s2[l] - '0';
}
if (fenzi == zi && fenmu == mu) {
Node v = {i, j, fenzi, fenmu};
ans.push_back(v);
}
}
}
sort(ans.begin(), ans.end(), cmp);
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++) {
cout << ans[i].x << '/' << ans[i].y << '=' << ans[i].a << '/'
<< ans[i].b << endl;
}
return 0;
}
L 美少女的预言
DP 暴搜显然会超时
用map将预言中的单词进行离散化，并记录每个位置对应的值。只需在预言中进行DP，数组f[ ]只用10个。接下来是教义，每读入一个单词扫一遍f[ ]，如果该单词对应的离散值等于语言中对应位置上的离散值，进行状态转移，;
时间复杂度O(nm)
const int mod = 1919810;
int n, m;
int f[20];
map<string, int> mp;
int idx;
int v[20];
int h(string s) {
if (!mp[s])
return mp[s] = ++idx;
return mp[s];
}
signed main() {
jiasu;
cin >> n >> m;
rep(i, 1, n) {
string s;
cin >> s;
v[i] = h(s);
}
f[0] = 1;
rep(i, 1, m) {
string s;
cin >> s;
if (!mp[s])
continue;
int id = mp[s];
for (int i = n; i >= 1; i--) {
if (id == v[i]) {
f[i] = (f[i] + f[i - 1]) % mod;
}
}
}
cout << f[n] << endl;
return 0;
}
京公网安备 11010502036488号