1、数字操作
答案：996
算法分析
直接模拟
Java 代码
public class Main {
public static void main(String[] args) {
int n = 998244353;
int k = 29;
while(k -- > 0)
{
if(n % 10 == 0) n /= 10;
else n -= 1;
}
System.out.println(n);
}
}
2、字符串操作
算法分析
说白了就是贪心的思想，尽可能的往大的字母靠，计算出每个字母有多少个，若当前字母有超过两个
Java 代码
public class Main {
static int N = 27;
static int[] cnt = new int[N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
char[] g = scan.next().toCharArray();
for(int i = 0;i < g.length;i ++)
{
cnt[g[i] - 'a'] ++;
}
for(int i = 0;i < 25;i ++)
{
if(cnt[i] >= 2)
{
cnt[i + 1] += cnt[i] / 2;
cnt[i] %= 2;
}
}
for(int i = 25;i >= 0;i --)
{
for(int j = cnt[i];j > 0;j --)
System.out.print((char)(i + 'a'));
}
}
}
3、煎牛扒
答案：499122180
算法分析
等价于一次能煎20个，一次需要10分钟
Java 代码
public static void main(String[] args){
long n = 998244353;
long cnt = 0;
if(n % 20 == 0) cnt = n / 20;
else cnt = n / 20 + 1;
System.out.println(cnt * 10);
}
4、数列求值
答案：959741112
算法分析
模拟，注意需要开longlong
Java代码
static int N = 20200202;
static long[] a = new long[N + 10];
static int mod = 998244353;
public static void main(String[] args){
a[1] = 1;
a[2] = 1;
a[3] = 1;
for(int i = 4;i <= N;i ++)
{
a[i] = (7 * a[i - 1] + 10 * a[i - 2] + 6 * a[i - 3]) % mod;
}
System.out.println(a[N]);
}
5、卡片游戏
答案
算法分析
爆搜所有的情况，当君选了左边或者右边时，妹都能通过贪心的算法固定选一个，在给定的区间中，dfs(start,end,v)表示搜索到当前区间[start,end]，君比妹多v的价值
- 当君选了
a[start]
若a[start + 1] >= a[end]，则妹就会选a[start + 1]，区间缩到[start + 2,end]，否则选择a[end]，区间缩到[start + 1,end - 1] - 当君选了
a[end]
若a[start] >= a[end - 1]，则妹就会选a[start]，区间缩到[start + 1,end - 1]，否则选择a[end - 1]，区间缩到[start,end - 2]
这样子做的跑的次数是2^50，大概是10^15次，1秒跑10^8次左右，基本要跑几个小时的，因此需要进行优化，由上面的递归过程可以发现，当区间固定时，该区间得到的差值一定是固定的，因此可以用记忆化搜索把当前区间的答案存储下来
Java 代码（爆搜版）
import java.util.Scanner;
public class Main {
static int N = 110;
static int[] a = new int[N];
static int ans = Integer.MIN_VALUE;
static void dfs(int start,int end,int v)
{
if(start > end)
{
ans = Math.max(ans, v);
return;
}
//拿start
if(a[start + 1] >= a[end]) dfs(start + 2,end,v + a[start] - a[start + 1]);
else dfs(start + 1,end - 1,v + a[start] - a[end]);
//拿end
if(a[start] >= a[end - 1]) dfs(start + 1,end - 1,v + a[end] - a[start]);
else dfs(start,end - 2,v + a[end] - a[end - 1]);
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 1;i <= n;i ++) a[i] = scan.nextInt();
dfs(1,n,0);
System.out.println(ans);
}
}
Java 代码（记忆化搜索版）
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N = 110;
static int[] a = new int[N];
static int[][] f = new int[N][N];
static int dfs(int start,int end)
{
if(start > end) return 0;
if(f[start][end] != -1) return f[start][end];
//拿start
f[start][end] = -0x3f3f3f3f;
if(a[start + 1] >= a[end])
f[start][end] = Math.max(f[start][end],dfs(start + 2,end) + a[start] - a[start + 1]);
else
f[start][end] = Math.max(f[start][end],dfs(start + 1,end - 1) + a[start] - a[end]);
//拿end
if(a[start] >= a[end - 1])
f[start][end] = Math.max(f[start][end], dfs(start + 1,end - 1) + a[end] - a[start]);
else
f[start][end] = Math.max(f[start][end], dfs(start,end - 2) + a[end] - a[end - 1]);
return f[start][end];
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i = 1;i <= n;i ++) a[i] = scan.nextInt();
for(int i = 0;i <= n;i ++) Arrays.fill(f[i], -1);
System.out.println(dfs(1,n));
}
}
6、打字
算法分析
用数组模拟栈或者栈模拟操作
Space：加一个'#'代表空格，最后输出的时候判断即可
CapsLock：切换大小写，state 为 false表示小写，true表示大写
Backspace：删除元素
字母：需要判断state是表示小写还是大写，再添加到数组中
时间复杂度)
Java 代码
import java.util.Scanner;
public class Main {
static int N = 100010;
static char[] ans = new char[N];
static int k = 0;
static boolean state = false;//一开始是小写
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
while(n -- > 0)
{
String op = scan.next();
if(op.equals("Space"))
{
ans[++ k] = '#';
}
else if(op.equals("CapsLock"))
{
state = state ? false : true;
}
else if(op.equals("Backspace"))
{
if(k >= 1) k --;
}
else
{
char t = op.toCharArray()[0];
if(state)
{
ans[++ k] = (char)(t - ('a' - 'A'));
}
else ans[++ k] = t;
}
}
for(int i = 1;i <= k;i ++)
{
if(ans[i] == '#') System.out.print(" ");
else System.out.print(ans[i]);
}
}
}
7、删除字符
算法分析
记录所有字母在某些位置出现过用链表记录，比如a字符在2,3,5位置出现过，则用链表存储2,3,5，从a到z枚举每个链表，标记需要删除的字符，最后枚举所有的元素，若该元素没有删除过则输出
时间复杂度)
Java 代码
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
static int N = 100010;
static char[] g;
static ArrayList[] list = new ArrayList[26];
static boolean[] bool = new boolean[N];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int k = scan.nextInt();
g = scan.next().toCharArray();
for(int i = 0;i < 26;i ++) list[i] = new ArrayList<Integer>();
for(int i = 0;i < n;i ++)
{
int idx = g[i] - 'a';
list[idx].add(i);
}
for(int i = 0;i < 26;i ++)
{
for(Object item : list[i])
{
int x = (int) item;
bool[x] = true;
k --;
if(k == 0) break;
}
if(k == 0) break;
}
String ans = "";
for(int i = 0;i < n;i ++)
{
if(!bool[i]) ans += g[i];
}
System.out.println(ans);
}
}
8、两个数组
算法分析
在a[]数组中，将x转化为x + y,和x - y,能否把a[]全部元素变成一致，
- 1、先求出一步的最少距离是多少，即求出
b[]数组所有元素的最大公约数c - 2、判断
a[]数组任意的两个元素能否通过走最少距离的走在一起，即判断任意的a[i],和a[j]的距离t = a[i] - a[j]，能否全能整除c，若能返回Yes，否则返回false
时间复杂度
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 100010;
static int n, m;
static int[] a = new int[N];
static int[] b = new int[N];
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
while (T-- > 0) {
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
String[] s2 = br.readLine().split(" ");
for (int i = 0; i < n; i++)
a[i] = Integer.parseInt(s2[i]);
Arrays.sort(a, 0, n);
String[] s3 = br.readLine().split(" ");
for (int i = 0; i < m; i++)
b[i] = Integer.parseInt(s3[i]);
// 求b数组的最大公约数
int c = b[0];
for (int i = 1; i < m; i++) {
c = gcd(c, b[i]);
}
if (c == 1)
System.out.println("Yes");
else {
boolean flag = true;
// 求a数组的每两个数的间隔是否都是b数组最大公约数的倍数
for (int i = 1; i < n; i++) {
int t = a[i] - a[i - 1];
if (t % c != 0) {
flag = false;
break;
}
}
if (flag)
System.out.println("Yes");
else
System.out.println("No");
}
}
}
}
9、数组求和
算法分析
假设当前a[]数组已固定，b[]数组已经进行了重排列，即f[i,i] = a[i] * b[i]已固定，求图中所有区间的总和
image.png
即
...
...
又由于a[i]是固定的，因此a[i]需要和 (n - i + 1) * i进行连体搭配，即一定是固定的，相当于转换成给定数组A[]，重排列B[]，求所有A[i] + B[i]总和的最小值，让A[]的第一大与B[]最小搭配，让A[]的第二大合B[]第二小搭配...，即对A[]和B[]进行排序，然后进行搭配
时间复杂度 )
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 100010;
static int mod = 998244353;
static int n,m;
static Long[] a = new Long[N];
static Long[] b = new Long[N];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] s1 = br.readLine().split(" ");
for(int i = 1;i <= n;i ++) a[i] = Long.parseLong(s1[i - 1]);
String[] s2 = br.readLine().split(" ");
for(int i = 1;i <= n;i ++) b[i] = Long.parseLong(s2[i - 1]);
for(int i = 1;i <= n;i ++)
{
a[i] = a[i] * (n - i + 1) * i;
}
Arrays.sort(a,1,n + 1);
Arrays.sort(b,1,n + 1);
long S = 0;
for(int i = 1;i <= n;i ++)
{
S = (S + (a[i] % mod) * b[n - i + 1]) % mod;
}
System.out.println(S);
}
}
网友评论