Contestant. Rank 530. Rating +127.代码略去了快读模板
A1. Non-alternating Deck (easy version)
题意
给定 \(n\) 个颜色相同的卡片，取卡片顺序为 \(A,B,B,A,A,B,B,A,A,B,B,...\)，每次取卡片的数量依次递增，当无法继续取的时候，按照正常顺序，下一个取卡片的人取完所有卡片。输出 \(A,B\) 各取了多少卡片。
思路
暴力模拟。
时间复杂度：\(O(\sqrt n)?\)
对应AC代码
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;
public class Main{
public static void main(String[] args) throws Exception{
Console console = new Console();
int t = console.nextInt();
nxt:
while(t -- > 0){
int n = console.nextInt() - 1;
int w = 2;
boolean who = false;
int a = 1, b = 0, cnt = 0;
while(n >= w){
if(who) a += w;
else b += w;
n -= w;
w ++;
cnt ++;
if(cnt == 2) {
who = !who;
cnt = 0;
}
}
if(who) a += n;
else b += n;
console.print(a + " " + b + "\n");
}
console.close();
}
}快速打卡
A2. Alternating Deck (hard version)
题意
给定 \(n\) 个颜色相间的卡片，第一个为白色，取卡片顺序为 \(A,B,B,A,A,B,B,A,A,B,B,...\)，每次取卡片的数量依次递增，当无法继续取的时候，按照正常顺序，下一个取卡片的人取完所有卡片。输出 \(A,B\) 各取了多少白色卡片和多少黑色卡片。
思路
暴力模拟。
多加几个变量标记即可。
时间复杂度：\(O(\sqrt n)?\)
对应AC代码
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;
public class Main{
public static void main(String[] args) throws Exception{
Console console = new Console();
int t = console.nextInt();
nxt:
while(t -- > 0){
int n = console.nextInt() - 1;
int w = 2;
boolean who = false;
int a1 = 1, b1 = 0, a2 = 0, b2 = 0, cnt = 0;
while(n >= w){
if(who) {
a1 += w / 2 + w % 2;
a2 += w / 2;
}
else {
b1 += w / 2;
b2 += w / 2 + w % 2;
}
n -= w;
w ++;
cnt ++;
if(cnt == 2) {
who = !who;
cnt = 0;
}
}
if(who) {
a1 += n / 2 + n % 2;
a2 += n / 2;
}
else {
b1 += n / 2;
b2 += n / 2 + n % 2;
}
console.print(a1 + " " + a2 + " " + b1 + " " + b2 + "\n");
}
console.close();
}
}依然是快速打卡
B. Cake Assembly Line
题意
给定 \(n\) 个蛋糕的中心点 \(a\) 以及 \(n\) 个巧克力酱的固定涂抹范围的中心点 \(b\)，蛋糕的大小为 \([a_i - w, a_i + w]\)，巧克力酱的涂抹范围为 \([b_i - h, b_i + h]\)。所有蛋糕均在传送带上，且相对位置不变。输出是否可以移动传送带，让所有的巧克力酱都涂在蛋糕上。
思路
我们设 \(a_l = a[i] - w, a_r = a[i] + w, b_l = b[i] - h, b_r = b[i] + h\)。
显然，我们不可能模拟移动，因为数据范围太大了。
考虑到每一个蛋糕都有对应的最小和最大移动距离，那么我们只需枚举所有蛋糕，更新最小移动距离的最大值和最大移动距离的最小值即可，这样操作之后，\([\min,\max]\) 内的所有移动距离都可以满足条件了。
我们以左边界为参考点，那么对于一个蛋糕，移动距离的最小值为 \(br - ar\)，最大值为 \(bl - al\)。
时间复杂度：\(O(n)\)
对应AC代码
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;
public class Main{
public static void main(String[] args) throws Exception{
Console console = new Console();
int t = console.nextInt();
nxt:
while(t -- > 0){
int n = console.nextInt(), w = console.nextInt(), h = console.nextInt();
long[] a = new long[n], b = new long[n];
for(int i=0;i<n;i++) a[i] = console.nextInt();
for(int i=0;i<n;i++) b[i] = console.nextInt();
long min = Long.MIN_VALUE, max = Long.MAX_VALUE;
for(int i=0;i<n;i++){
long al = a[i] - w, ar = a[i] + w, bl = b[i] - h, br = b[i] + h;
min = Math.max(min, br - ar);
max = Math.min(max, bl - al);
}
console.println(min <= max ? "YES" : "NO");
}
console.close();
}
}只要一个参考点就够了
C. Monsters (easy version)
题意
给定一个序列 \(a\)，定义两种操作为：
- 选择任意一个非 \(0\) 数，将其减 \(1\)；
- 将整个序列所有非 \(0\) 数减 \(1\)，若减完后出现至少一个数为 \(0\)，那么本操作循环执行。
输出让整个序列为 \(0\) 的操作 \(1\) 的最小数量。
思路
显然，我们只需升序排序序列，然后构造一个不递减，相邻数之差 \(\leq 1\) 的序列即可。
如 \(1,1,1,4,4,5\)，将其构造为 \(1,1,1,2,2,3\)。
答案即为原序列和该序列的差。
时间复杂度：\(O(n)\)
对应AC代码
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;
public class Main{
public static void main(String[] args) throws Exception{
Console console = new Console();
int t = console.nextInt();
nxt:
while(t -- > 0){
int n = console.nextInt();
int[] a = new int[n];
for(int i=0;i<n;i++) a[i] = console.nextInt();
Arrays.sort(a);
long cnt = 0, w = 0;
for(int i=0;i<n;i++){
if(a[i] != w){
w ++;
cnt += a[i] - w;
}
}
console.println(cnt);
}
console.close();
}
}逾越丁真，鉴定为不开long long
D. Letter Exchange
题意
给定 \(m\) 个由 \(w,i,n\) 构成的长度为 \(3\) 的字符串，定义一次操作为指定两个人互换他们的任意一个字符。输出操作数的最小值以及对应的操作方案。
思路
思维+模拟。
首先，由于题给限制，方案一定是存在的，那么互换字符会出现两种可能：
- \(A\) 缺了 \(a\)，但多了 \(b\)；\(B\) 缺了 \(b\)，但多了 \(a\)；那么 \(A,B\) 交换一下；
- \(A\) 缺了 \(a\)，但多了 \(c\)；\(B\) 缺了 \(c\)，但多了 \(b\)；\(C\) 缺了 \(b\)，但多了 \(a\)；那么三者互换一下。
对于上述操作，操作 \(1\) 的交换次数是 \(1\)，操作 \(2\) 的交换次数是 \(2\)。
显然，若只执行上面的两个操作，只要不出现无意义操作，操作数一定是最小的。
那么，我们可以执行完所有操作 \(1\) 后再执行操作 \(2\)，因为配对是最容易的，而且配对结束后，剩下的字符一定是满足操作 \(2\) 的条件的。
那么我们可以用数组存储所有 多 \(a\) 少 \(b\) 的数量，然后略微暴力模拟一下即可。
时间复杂度：懒得分析
对应AC代码
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;
public class Main{
public static void main(String[] args) throws Exception{
Console console = new Console();
int t = console.nextInt();
nxt:
while(t -- > 0){
int n = console.nextInt();
List<List<Integer>> a = new ArrayList<>();
for(int i=0;i<6;i++) a.add(new ArrayList<>()); //0 wi, 1 wn, 2 iw, 3 in, 4 nw, 5 ni
for(int i=1;i<=n;i++){
String now = console.next();
int[] cnt = new int[3];
for(int j=0;j<3;j++){
char e = now.charAt(j);
if(e == 'w') cnt[0] ++;
else if(e == 'i') cnt[1] ++;
else cnt[2] ++;
}
if(cnt[0] == 1 && cnt[1] == 1 && cnt[2] == 1) continue;
if(cnt[0] == 3) {
a.get(0).add(i);
a.get(1).add(i);
}else if(cnt[1] == 3){
a.get(2).add(i);
a.get(3).add(i);
}else if(cnt[2] == 3){
a.get(4).add(i);
a.get(5).add(i);
}else if(cnt[0] == 2 && cnt[1] == 0){
a.get(0).add(i);
}else if(cnt[0] == 2 && cnt[2] == 0){
a.get(1).add(i);
}else if(cnt[1] == 2 && cnt[0] == 0){
a.get(2).add(i);
}else if(cnt[1] == 2 && cnt[2] == 0){
a.get(3).add(i);
}else if(cnt[2] == 2 && cnt[0] == 0){
a.get(4).add(i);
}else if(cnt[2] == 2 && cnt[1] == 0){
a.get(5).add(i);
}
}
int cnt = Math.min(a.get(0).size(), a.get(2).size()) + Math.min(a.get(1).size(), a.get(4).size()) + Math.min(a.get(3).size(), a.get(5).size());
int left = Math.max(a.get(0).size(), a.get(2).size()) + Math.max(a.get(1).size(), a.get(4).size()) + Math.max(a.get(3).size(), a.get(5).size()) - cnt;
cnt += left / 3 * 2;
console.println(cnt);
for(int i=0;i<Math.min(a.get(0).size(), a.get(2).size());i++){
console.println(a.get(0).get(i) + " w " + a.get(2).get(i) + " i");
}
for(int i=0;i<Math.min(a.get(1).size(), a.get(4).size());i++){
console.println(a.get(1).get(i) + " w " + a.get(4).get(i) + " n");
}
for(int i=0;i<Math.min(a.get(3).size(), a.get(5).size());i++){
console.println(a.get(3).get(i) + " i " + a.get(5).get(i) + " n");
}
if(left > 0) {
boolean b1 = a.get(0).size() > a.get(2).size(), b2 = a.get(1).size() > a.get(4).size(), b3 = a.get(3).size() > a.get(5).size();
for (int i = 0; i < left / 3; i++) {
if(b1 && !b2 && b3){
console.println(a.get(0).get(a.get(2).size() + i) + " w " + a.get(3).get(a.get(5).size() + i) + " i");
console.println(a.get(4).get(a.get(1).size() + i) + " n " + a.get(3).get(a.get(5).size() + i) + " w");
}else{
console.println(a.get(2).get(a.get(0).size() + i) + " i " + a.get(1).get(a.get(4).size() + i) + " w");
console.println(a.get(5).get(a.get(3).size() + i) + " n " + a.get(1).get(a.get(4).size() + i) + " i");
}
}
}
}
console.close();
}
}依托答辩，但是Accepted.
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Blog - Floating Ocean！
评论