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]
已固定,求图中所有区间的总和
即
...
...
又由于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);
}
}
网友评论