Rank 379/3037. AC 7/12.
A. 小沙の好客
题意
给定 \(n\) 个商品，对于 \(Q\) 个询问，挑选最多 \(k\) 个价值不大于 \(x\) 的商品，输出价值和的最大值。
思路
二分前缀和。
或者使用 \(stl\) 里的 \(upperbound\)。
时间复杂度：\(O(n+\log n)\)
对应AC代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), q = scanner.nextInt();
long[] a = new long[n + 1];
for(int i=1;i<=n;i++) a[i] = scanner.nextInt();
Arrays.sort(a);
long[] sum = new long[n + 1];
for(int i=1;i<=n;i++) sum[i] = sum[i - 1] + a[i];
while(q -- > 0){
int k = scanner.nextInt(), x = scanner.nextInt();
int l = 1, r = n, mid;
while (l <= r) {
mid = (l + r) >> 1;
if (a[mid] <= x) l = mid + 1;
else r = mid - 1;
}
if(r >= k) System.out.println(sum[r] - sum[r - k]);
else System.out.println(sum[r]);
}
}
}二分别忘了咋写啊草
B. 小沙の博弈
题意
两个很聪明的人进行博弈，每个人面前有无数多个格子，每个格子可以放无限个石子。给定 \(n\) 个石子，两个人交替操作，每次操作可以从这对石子里拿出任意数量的石子并放入第一个没有石子的格子里。
胜负取决于两人面前格子的字典序大小，字典序小的人获胜。
思路
显然，要让字典序小，聪明的人绝对会只拿 \(1\) 个，那么整个问题就简化为对 \(n\) 的奇偶性判断了。
\(n\) 为奇数的时候，后手赢，\(n\) 为偶数的时候，平局。
先手没有必胜策略。
时间复杂度：\(O(1)\)
对应AC代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(n % 2 == 0 ? "win-win!" : "Yaya-win!");
}
}你这先手怎么这么菜啊.jpg
C. 小沙の不懂
题意
对于两个可能含有前导 \(0\) 的数字 \(a,b\)，以及一个长度为 \(10\) 且从 \(0\) 开始的排列 \(p\)，给定 \(a,b\) 按照排列 \(p\) 进行映射操作后的数，数字可能也有前导 \(0\)，判断能否确定原数 \(a,b\) 的大小关系。
注：映射操作指 \(t_i=p_{a_i}\)
思路
分类讨论题。
我们设给定的数为 \(n,m\)，对应于 \(a,b\)。
若 \(n\) 和 \(m\) 的长度相同：若它们完全一致，那么 \(a\) 和 \(b\) 相等；否则无法判断。
若 \(n\) 的长度大于 \(m\)，那么我们先考虑将 \(n\) 和 \(m\) 右对齐后多出来的部分 \(t\)，因为考虑到前导 \(0\)，若 \(t\) 中有至少两个不同的数字，那么 \(t\) 对应的原数部分一定有一个数不是 \(0\)，那么 \(n\) 的位数一定比 \(m\) 多，\(n>m\)；否则，我们设 \(t\) 中唯一出现的数为 \(x\) ，那么我们只要判断 \(n\) 剩下部分的最高位和 \(m\) 的最高位是否都是 \(x\) 即可，如果是的话就无法判断，否则 \(n\) 依旧大于 \(m\)。
反之同理。
时间复杂度：懒得分析
对应AC代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String a = scanner.next(), b = scanner.next();
int la = a.length(), lb = b.length();
if(a.equals(b)) System.out.println("=");
else if(la > lb){
char p = a.charAt(0);
boolean f = false;
for(int i=1;i<la-lb;i++) {
if(a.charAt(i) != p){
f = true;
break;
}
}
if(f) System.out.println(">");
else{
if(b.charAt(0) == p && a.charAt(la - lb) != p) System.out.println(">");
else System.out.println("!");
}
}
else if(lb > la){
char p = b.charAt(0);
boolean f = false;
for(int i=1;i<lb-la;i++) {
if(b.charAt(i) != p){
f = true;
break;
}
}
if(f) System.out.println("<");
else{
if(a.charAt(0) == p && b.charAt(lb - la) != p) System.out.println("<");
else System.out.println("!");
}
}else System.out.println("!");
}
}题目太阅读理解了
D. 小沙の赌气
题意
两个人打游戏，打下一关需要满足前一关通关。对于每一个人，每轮会给定 \(1\) 个 \([l,r]\) 区间，只要 \(l-1\) 关已通关，那么 \([l,r]\) 内的所有关都瞬间通关，区间可保留到后面使用。输出每一轮的领先情况以及领先数量。
思路
对于一个人的通关情况，我们可以用一个数 \(num\) 来表示，对于每一个区间，我们可以判断它的左边界和 \(num+1\) 的大小关系，若大于，那么无法合并区间，我们将其存下来，否则，我们用右边界更新 \(num\)。
在每次 \(num\) 更新后，因为我们有区间存下来，所以我们需要判断是否可以继续合并。于是，我们可以维护一个左边界的小根堆，将所有左边界 \(\leq num+1\) 的区间全都更新一遍即可。
于是乎，我们比较 \(num\) 即可。
时间复杂度：\(O(n \log k)\)
对应AC代码
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] x = new int[n][2], y = new int[n][2];
for(int i=0;i<n;i++) x[i] = new int[]{scanner.nextInt(), scanner.nextInt()};
for(int i=0;i<n;i++) y[i] = new int[]{scanner.nextInt(), scanner.nextInt()};
AtomicInteger num1 = new AtomicInteger(0), num2 = new AtomicInteger(0);
PriorityQueue<int[]> q1 = new PriorityQueue<>(Comparator.comparingInt(o -> o[0])),
q2 = new PriorityQueue<>(Comparator.comparingInt(o -> o[0]));
for(int i=0;i<n;i++){
work(x[i], num1, q1);
work(y[i], num2, q2);
System.out.println(num1.get() == num2.get() ? "win_win!" : (num1.get() > num2.get() ? "sa_win!" : "ya_win!"));
System.out.println(Math.abs(num1.get() - num2.get()));
}
}
private static void work(int[] now, AtomicInteger num, PriorityQueue<int[]> q){
if(now[0] > num.get() + 1){
q.offer(now);
}else{
int r = Math.max(num.get(), now[1]);
while(!q.isEmpty()){
int[] c = q.peek();
if(c[0] <= r + 1){
q.poll();
r = Math.max(r, c[1]);
}else break;
}
num.set(r);
}
}
}woc怎么这么简单
E. 小沙の印章
待补充
F. 小沙の串串
题意
给定一个字符串 \(n\)，定义一次操作为任意选择一个字符并将其移到最后，输出 \(k\) 次操作后字典序最大的字符串。
思路
因为考虑到字典序的贪心性：只要比较第一个不相同的字符即可判断字典序的大小。
也就是说，我们只需让前几位尽可能大即可。
那么，若两个字母之间存在比他们小的数，我们就可以考虑维护一个 \(l\)，将 \(l+k\) 内的所有元素都移到后面。
对于字符串的输出，我们可以用三个字符串分开存储，最后拼接在一起。
更具体地说，我们可以从大到小枚举所有字母，并从前往后枚举 \([l,l+k]\) 内的该字母，将这些字母全都移到后面，并更新 \(l,k\)。更新之后，可能存在剩余未移到后面的字母，因而在上一个操作前，我们可以直接把 \(l\) 之前的字母删除。
时间复杂度：\(O(n)?\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100010;
queue<int> q[30];
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, k;
cin >> n >> k;
string s, s1, s2, s3;
cin >> s;
for(int i=0;i<n;i++){
q[s[i] - 'a'].emplace(i);
}
int l = 0, l1 = 0;
while(k){
for(int i=25;i>=0;i--){
while(!q[i].empty() && q[i].front() < l) q[i].pop();
if(!q[i].empty() && q[i].front() <= l + k){
int t = q[i].front();
q[i].pop();
k -= t - l;
while(l < t) s2 += s[l ++];
s1 += s[l ++];
l1 ++;
break;
}
}
if(l == n) break;
}
for(int i=l;i<n;i++) s3 += s[i];
while(!s1.empty() && k){
s2 += s1[l1 -- - 1];
s1.pop_back();
k --;
}
sort(s2.rbegin(), s2.rend());
cout << (s1 + s3 + s2);
}
草，这题很好听懂但很难说明白思路
G. 小沙の编码
待补充
H. 小沙の店铺
题意
给定初始价格 \(x\)，每卖出去 \(k\) 件，单价上涨 \(y\) 元。给定 \(n\) 个客户，第 \(i\) 个客户的购买 \(n - i + 1\) 个商品，单价在每一个客户买完后才会变化。若接待完 \(n\) 个客户都没有卖出去至少 \(T\) 元货物，输出 \(-1\)，否则输出卖出的价钱。
思路
纯模拟打卡题
时间复杂度：\(O(n)?\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
#define int long long
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int x, y, k, n, t;
cin >> x >> y >> k >> n >> t;
int cnt = 0, tot = 0, now = 0;
while("If the world love me"){
cnt ++;
tot += n * (x + now / k * y);
now += n;
if(tot >= t) {
break;
}
if(n - 1 <= 0){
cnt = -1;
break;
}
n --;
}
cout << cnt;
}差点打卡题卡了一会儿
I. 小沙の金银阁
题意
给定 \(m\) 个灵石，在 \(n\) 次猜测中，给出灵石数量的猜测，猜错会扣除相同数量的灵石，规定只有一次会猜对，输出猜测的最优方案。
思路
乱猜，从 \(m\) 开始除 \(2\) 向上取整，剩余数放到第一位。
时间复杂度：\(O(\log_2 m)?\)
对应AC代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long n = scanner.nextLong(), m = scanner.nextLong();
//1e15约2e50
if(n > 51 || m < (1L << (n - 1))) System.out.println(-1);
else{
long[] out = new long[60];
for(int i=1;i<n;i++){
out[i] = m / 2 + m % 2;
m /= 2;
}
System.out.printf("%d ", m);
for(int i=(int)n-1;i>0;i--) System.out.printf("%d ", out[i]);
}
}
}正常一点的题解
乱猜就完事了（（
J. 小沙の最短路
待补充
K. 小沙の抱团 easy
题意
给定 \(n\) 个人，定义一个指令为要求以 \(x\) 人为单位抱团，落单的人淘汰，在所有操作都能被所有抱团的人认可的情况下，输出最少操作数。
思路
要让操作被所有人认可，那么应该满足少数服从多数的原则，因而我们可以以 $ + 1$ 为一组，让这样可以让留下的人最少。
暴力模拟求操作数即可
时间复杂度：\(O(\log_2 n)\)
对应AC代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long n = scanner.nextLong();
long cnt = 0;
while(n > 2){
cnt ++;
n = n / 2 + 1;
}
System.out.println(cnt);
}
}怎么感觉还是乱猜（（
L. 小沙の抱团 hard
题意
在上一题的基础上，指令是给定的，且每个指令有对应的代价，但每个指令可以被重复使用。输出让剩余人数最少的最小代价。
思路
考虑到代价以及重复使用，我们可以用类似于完全背包的写法。
当剩余 \(2\) 人时，一定无法让人数继续减少，所以我们可以从 \(n\) 个人的状态枚举到 \(2\) 个人的状态。
对于当前剩余 \(i\) 个人的情况下，我们枚举所有指令 \((b,x)\)，每个指令执行后剩余的人数即为 \(i - i \% x\)，因而我们可以得到下面的状态转移方程：
\(dp[i - i \% x[i]] = min(dp[i - i \% x[i]], dp[i] + b[i])\)
当没有一个指令可行的时候，或者剩余 \(2\) 人时，输出结果。
时间复杂度：\(O(nm)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100010, M = 510, inf = 10000000000ll;
struct sb{
int b, x;
}o[M];
int dp[N];
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for(int i=0;i<m;i++) cin >> o[i].b >> o[i].x;
for(int i=2;i<n;i++) dp[i] = inf;
bool ok = false;
for(int i=n;i>2;i--){
if(dp[i] == inf) continue;
bool f = true;
for(int j=0;j<m;j++){
int mod = i % o[j].x;
if(mod == 0 || i <= o[j].x) continue;
dp[i - mod] = min(dp[i - mod], dp[i] + o[j].b);
f = false;
}
if(f) {
cout << dp[i];
ok = true;
break;
}
}
if(!ok) cout << dp[2];
}简单的dp