Rank 196/3562. AC 7/11.
这标题显然是参考了arcaea的final verdict包的剧情，对吧
A. 不断减损的时间
题意
给定一个数组，数值可以为负数。对于无限次的操作，你可以任选一个偶数并将其除以 \(2\)，输出最后总和的最大值。
思路
将所有正偶数暴力除到奇数为止，并求和即可。
时间复杂度：\(O(n)\)
对应AC代码
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
long ans = 0;
for(int i=0;i<n;i++){
int a = scanner.nextInt();
if(a <= 0) ans += a;
else{
while(a % 2 == 0) a /= 2;
ans += a;
}
}
System.out.println(ans);
}
}快速签到
B. 勉强拼凑的记忆
题意
给定 \(n\) 块矩形积木，积木的大小为 \(1 \times k\)，\(k\) 可在 \([1,\lceil \frac{n}{2} \rceil ]\) 内任意选择，若能使用所有积木搭成正方形，输出最大的边长，否则输出 \(-1\)。
思路
很难说思路，因为可以打表打出规律（（
前 \(30\) 个根据打表得到
\(1,-1,2,2,3,4,5,5,6,6,\)
\(7,8,9,9,10,10,11,12,13,13,\)
\(14,14,15,16,17,17,18,18,19,20\)
很容易就可以得到一个通式 \(ans=\frac{(q \times 2 + q \bmod 2)}{3}\)
至于为什么会这样，我们可以考虑 \(6\) 以上的数，因为横放几个最长的方块，然后再竖着放一个方块，最后在最后一行填满方块，即为 \(6 -11\) 之间的规律，而 \(12\) 以上，我们就可以发现最底下还可以再塞一行，然后在右边再放上一个方块依然是可行的，以此类推...
时间复杂度：\(O(1)\)
对应AC代码
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while(t -- > 0){
long q = scanner.nextLong();
if(q == 2) System.out.println(-1); //下面式子会算成0...
else System.out.println((q * 2 + q % 2) / 3);
}
}
}打表好累.jpg
C. 忽远忽近的距离
题意
构造一个排列，满足 \(2 \leq |a_i-i| \leq 3\)。
思路
打表，暴力找规律即可。
可以发现是 \(4\) 个为一块有规律输出的，处理结尾数字即可。
时间复杂度：\(O(1)\) （确信
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n;
cin >> n;
if(n < 4) cout << -1 << '\n';
else if(n == 4) cout << "3 4 1 2\n";
else if(n == 5) cout << "4 5 1 2 3\n";
else if(n == 6) cout << "4 5 6 1 2 3\n";
else if(n == 7) cout << -1 << '\n';
else if(n == 8) cout << "3 4 1 2 7 8 5 6\n";
else if(n == 9) cout << "3 4 1 2 7 8 9 5 6\n"; //狠狠地打表
else {
int i = 0;
if (n % 4 == 3)
for (; i < n / 4 - 2; i++)
cout << i * 4 + 3 << " " << i * 4 + 4 << " " << i * 4 + 1 << " " << i * 4 + 2 << " ";
else
for (; i < n / 4 - 1; i++)
cout << i * 4 + 3 << " " << i * 4 + 4 << " " << i * 4 + 1 << " " << i * 4 + 2 << " ";
if (n % 4 == 0) cout << i * 4 + 3 << " " << i * 4 + 4 << " " << i * 4 + 1 << " " << i * 4 + 2;
else if (n % 4 == 1) cout << i * 4 + 4 << " " << i * 4 + 5 << " " << i * 4 + 1 << " " << i * 4 + 2 << " " << i * 4 + 3;
else if (n % 4 == 2) cout << i * 4 + 4 << " " << i * 4 + 5 << " " << i * 4 + 6 << " " << i * 4 + 1 << " " << i * 4 + 2 << " " << i * 4 + 3;
else cout << i * 4 + 4 << " " << i * 4 + 5 << " " << i * 4 + 1 << " " << i * 4 + 2 << " " << i * 4 + 3 << " " << i * 4 + 9 << " " << i * 4 + 10 << " " << i * 4 + 11 << " " << i * 4 + 6 << " " << i * 4 + 7 << " " << i * 4 + 8;
}
}打表好累.jpeg
D. 宿命之间的对决
题意
给定一个正整数 \(n\)，小红和小紫轮流取当前数的因子 \(x\) ，使当前数减少 \(x\) 。如果小红获胜，则输出 "\(kou\)"，否则输出 "\(yukari\)"
思路
简单的博弈题。
我们先假设每个人都只拿 \(1\) 个，那么最后一定是第一次拿的时候当前数为偶数的一方获胜。
然而，输的一方肯定想要获胜，那么他一定要拿掉偶数个才行，而无论他怎么拿，获胜方都可以只拿掉奇数来使他只能从奇数的因数中取，从而不可能取到偶数，因而必输。
所以，判奇偶即可。
时间复杂度：\(O(1)\)
对应AC代码
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println(scanner.nextLong() % 2 == 1 ? "yukari" : "kou");
}
}次世代の宿命之红砍光光（？
E. 公平守望的灯塔
题意
给定在平面直角坐标系的整点 \(A(x_A,y_A)\) 和 \(B(x_B,y_B)\) ，输出一个整点 \(C\) ，使得 \(\Delta ABC\) 为以 \(AB\) 为斜边的 等腰\(Rt\Delta\)。
思路
"K型全等"，找出中点后用全等即可解出。
当 \(A\) 和 \(B\) 横坐标的差值和纵坐标的差值的奇偶性不一致时，\(C\) 点一定会有小数 \(0.5\) 存在，因此该条件无解。
时间复杂度：\(O(1)\)
对应AC代码
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long xa = scanner.nextLong(), ya = scanner.nextLong(), xb = scanner.nextLong(), yb = scanner.nextLong();
if(Math.abs(xa - xb) % 2 == Math.abs(ya - yb) % 2){ //初中数学？
long mid2x = xa + xb, mid2y = ya + yb;
System.out.printf("%d %d\n", (mid2x + mid2y) / 2 - ya, (mid2y - mid2x) / 2 + xa);
}else System.out.println("No Answer!\n");
}
}画个图，不就是个初中数学题嘛
F. 迎接终结的寂灭
题意
输出 \(42\)。
思路
输出 \(42\)。
时间复杂度：\(O(1)\)
对应AC代码
import java.util.*;
public class Main{
public static void main(String[] args) {
System.out.println(42);
}
}怎么会是呢
G. 严肃古板的秩序
题意
给定一个运算式，其中等式左边的符号全都被替换成 \(?\)，等式右边只有一个数字，符号只有三种可能：\(+\)，\(-\)， #，其中定义\(a\)#\(b=a^a \bmod b,a>0且b>0\)，三个符号的优先级相同，输出一个合法的式子，否则输出 \(-1\)。
思路
暴力 \(Dfs\) 即可，其中模幂运算需要使用快速幂。
时间复杂度：\(O(3^x \log n),x \leq 12\)
对应AC代码
import java.math.BigInteger;
import java.util.*;
public class Main{
static int n;
static long ans;
static long[] nums;
static char[] op;
static boolean ok = false;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] s = scanner.next().split("\\?");
n = s.length;
nums = new long[n];
for(int i=0;i<n-1;i++) nums[i] = Long.parseLong(s[i]);
nums[n - 1] = Long.parseLong(s[n - 1].split("=")[0]);
ans = Long.parseLong(s[n - 1].split("=")[1]);
op = new char[n - 1];
dfs(0, nums[0]);
if(!ok) System.out.println(-1);
}
private static void dfs(int index, long last){
if(index == n - 1){
if(last == ans) {
ok = true;
print();
}
return;
}
if(ok) return;
op[index] = '+';
dfs(index + 1, last + nums[index + 1]);
if(ok) return;
op[index] = '-';
dfs(index + 1, last - nums[index + 1]);
if(ok || last <= 0 || nums[index + 1] <= 0) return;
op[index] = '#';
dfs(index + 1, BigInteger.valueOf(last).modPow(BigInteger.valueOf(last), BigInteger.valueOf(nums[index + 1])).longValue());
}
private static void print(){
System.out.printf("%d", nums[0]);
for(int i=1;i<n;i++){
System.out.printf("%c%d", op[i - 1], nums[i]);
}
System.out.printf("=%d\n", ans);
}
}很经典的回溯搜索
H. 穿越万年的轮回
待补充
I. 灵魂碎片的收集
题意
定义 \(S(n)\) 为 \(n\) 的所有不包括 \(n\) 的因数的和，给定正整数 \(x\)，输出满足 \(S(n)=x\) 的正整数 \(n\)，否则输出 \(-1\)。
限制
对于输入的 \(x\)，有以下限制：
- \(x\%2=0\)，则 \(x-1\) 和 \(x-3\) 之间一定有一个是质数。
- \(x\%2=1\)，则无限制
思路
我们可以直接从限制入手：
若 \(x\) 为偶数，且 \(x-1\) 是质数，那么显然只有一种分解 \(S(n)=1+(x-1)=x\)，那么 \(n=(x-1)^2\)。
若 \(x\) 为偶数，且 \(x-3\) 是质数，那么也只有一种分解 \(S(n)=1+2+(x-3)=x\)，那么 \(n=2(x-3)\)。
若 \(x\) 为奇数，因为 \(1\) 一定是其中一个因子，那么剩下的一定是偶数。因为所有偶数都可以分解为两个质数之和，那么我们可以直接暴力，枚举出一种可能即可。
当然，为了判定素数方便，我们采取用线性筛打表的方式来让查询的复杂度降到 \(O(1)\)。
时间复杂度：懒得分析
对应AC代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
#define ll long long
vector<int> primes;
bool vis[N + 1], isPrime[N + 1];
void init() {
for (int i = 2; i<= N; ++i) {
if (!vis[i]) {
primes.emplace_back(i);
isPrime[i] = true;
}
for (int &j : primes) {
if (1ll * i * j > N) break;
vis[i * j] = true;
if (i % j == 0) break;
}
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
init();
int t;
ll x;
cin >> t;
int ans[] = {0, -1, -1, 4, 9, -1, 25, 8};
while (t--) {
cin >> x;
if(x <= 7) cout << ans[x] << '\n';
else {
if (x % 2 == 0) {
if (isPrime[x - 1]) cout << (x - 1) * (x - 1) << '\n';
else cout << 2 * (x - 3) << '\n';
} else {
for (int i = 2; i <= x; i++) {
if(isPrime[i] && isPrime[x - i - 1]) {
cout << (ll)i * (x - i - 1) << '\n';
break;
}
}
}
}
}
}
赛时眼瞎了没看到限制
J. 无法磨灭的悔恨
待补充
K. 永恒守候的爱恋
题意
假设 \(p_1,p_2,...,p_n\) 为前 \(n\) 个素数，定义 \(S\) 为 \(a_i\) 个 \(p_i\) 组成的多重集合 \((i \in [1,n])\)。
例如，多重集{2,2,3,3,3,7}可以表示为：
\(n=4,a=[2,3,0,1]\)。
定义\(f(i)\) 为一个数组前 \(i\) 个元素的乘积的因子数量，给定 \(n\) 和数组 \(a\)，他表示了一个大小为 \(\displaystyle{size=\sum_{i=1}^{n}a_i}\) 的多重集。用这个多重集的所有元素构造一个大小为 \(size\) 的数组，输出 \(\displaystyle{\sum_{i=1}^{size}f(i)}\) 的最大值，对 \(10^9+7\) 取模。
思路
\(Buff\) 叠满的数学题。
我们先来考虑因子个数：根据算数基本定理，对于一个分解式 \(x=P_1^{\alpha_1}P_2^{\alpha_2}...P_n^{\alpha_n}\)，因数数量为 \((\alpha_1 + 1)(\alpha_2 + 1)...(\alpha_n+1)\)。
那么既然我们要让这个乘积更大，我们就可以每次都不重复地将数字放上去，如 \(|2,3,7||2,3||3|\)。那么对于第一块，结果为 \(2 \times 1 \times 1\)、\(2 \times 2 \times 1\)、\(2 \times 2 \times 2\)。对于第二块，结果为 \(3 \times 2 \times 2\)、\(3 \times 3 \times 2\)。对于第三块，结果为 \(4 \times 3 \times 2\)。
显然，上述式子是分块的等比数列求和，其中 \(q=2,\frac{3}{2},\frac{4}{2},...\)
因而，我们只需一块一块地处理即可。
当然，为了快速求出每一块的元素个数，我们只需在读入的时候使用差分的方法，具体地来说：
横向从左到右绘制一张柱状图，那么纵切面的数量即为每块的元素数量。
时间复杂度：不好评价
对应AC代码
注意，此代码不一定能运行通过，有概率会超时
import java.math.BigInteger;
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] t = new int[200010];
for(int i=0;i<n;i++){
t[scanner.nextInt() + 1] --;
t[1] ++;
}
int max = 0;
for(int i=1;i<200010;i++) {
t[i] += t[i - 1];
if(t[i] == 0) {
max = i - 1;
break;
}
}
long ans = 0, a1 = 1, an;
BigInteger res = BigInteger.ONE, ip1, mod = BigInteger.valueOf(1000000007L);
for(int i=1;i<=max;i++){ //规避一下逆元
int now = t[i], nxt = t[i + 1];
ip1 = BigInteger.valueOf(i + 1);
res = res.multiply(ip1.modPow(BigInteger.valueOf(now - nxt), mod)).mod(mod);
a1 = (a1 * (i + 1)) % 1000000007L;
an = res.multiply(ip1.modPow(BigInteger.valueOf(nxt), mod)).mod(mod).longValue();
ans = (ans + (an * (i + 1)) % 1000000007L + 1000000007L - a1) % 1000000007L;
a1 = an;
}
System.out.println(ans);
}
}不用考虑第几个质数是啥呢