当前位置：首页 > news >正文

Codeforces Round 964 (Div. 4) A-E Java题解

news 来源：原创 2024/9/20 7:33:49

比赛地址

Dashboard - Codeforces Round 964 (Div. 4) - Codeforces

A题

签到题

给一个两位数求各位上的数字和

直接对10取余加上本来的数除以10

// 注意类名必须为 Main, 不要有任何 package xxx 信息
// package Dduo;
import java.io.*;
import java.math.*;
import java.util.*;// 北华大学 
// 大数据应用与开发工作室 
// 朱道阳
// Eclipse IDE 2020 08
// OpenJDK 1.8
// @author <a href="gczdy.blog.csdn.net">多多的博客</a>
// 支持Java8的最新特性，比如stream操作和lambda表达式public class Main {static Scanner sc = new Scanner(System.in);static long mod = (long) (1e9 + 7);public static void main(String[] args) {int t = 1;t = sc.nextInt();while (t-- > 0) {solve();}}static void solve() {int n=sc.nextInt();int s=sc.nextInt();//洗澡时间int m=sc.nextInt();//总分钟数int ans1=0;int ans2=0;int ans=0;int arr[][]=new int[n][2];for(int i=0;i<n;i++) {arr[i][0]=sc.nextInt();arr[i][1]=sc.nextInt();}for(int i=0;i<n;i++) {if(i==0) {if(arr[i][0]>=s) {System.out.println("YES");return;}}if(i==n-1) {if(m-arr[i][1]>=s) {System.out.println("YES");return;}}if(i>0&&arr[i][0]-arr[i-1][1]>=s) {System.out.println("YES");return;}}System.out.println("NO");}}// 被爱的人不用道歉
// 下次再见面 不要冷冰冰 也不要说反话!

B题

每一种情况都模拟一下

枚举一下就能过

// 注意类名必须为 Main, 不要有任何 package xxx 信息
//package Dduo;
import java.util.*;// 北华大学 
// 大数据应用与开发工作室 
// 朱道阳
// Eclipse IDE 2020 08
// OpenJDK 1.8
// @author <a href="gczdy.blog.csdn.net">多多的博客</a>
// 支持Java8的最新特性，比如stream操作和lambda表达式public class Main {static Scanner sc = new Scanner(System.in);static long mod = (long) (1e9 + 7);static int k=0;static int b=0;public static void main(String[] args) {int t = 1;t = sc.nextInt();while (t-- > 0) {solve();}sc.close();}private static void solve() {// TODO Auto-generated method stubint a=sc.nextInt();int b=sc.nextInt();int c=sc.nextInt();int d=sc.nextInt();int cnt=0;int ans1=0;int ans2=0;ans1=0;ans2=0;if(a>c)ans1++;if(a<c)ans2++;if(b>d)ans1++;if(b<d)ans2++;if(ans1>ans2)cnt++;ans1=0;ans2=0;if(a>d)ans1++;if(a<d)ans2++;if(b>c)ans1++;if(b<c)ans2++;if(ans1>ans2)cnt++;ans1=0;ans2=0;if(b>d)ans1++;if(b<d)ans2++;if(a>c)ans1++;if(a<c)ans2++;if(ans1>ans2)cnt++;ans1=0;ans2=0;if(b>c)ans1++;if(b<c)ans2++;if(a>d)ans1++;if(a<d)ans2++;if(ans1>ans2)cnt++;System.out.println(cnt);}}// 被爱的人不用道歉
// 下次再见面 不要冷冰冰 也不要说反话!

C题

这一题我们先把任务区间放在一个n行2列的数组里面

然后去遍历找是否有符合的区间

有符合的区间直接输出yes

如果遍历完了还没有return 输出no

需要注意的是s变量表示的是一天的时间

从0分钟到arr[0][0] 从arr[n-1][1]到s 要特判

需要注意的是题目已经指出给出的时间是按顺序的

// 注意类名必须为 Main, 不要有任何 package xxx 信息
//package Dduo;
import java.io.*;
import java.math.*;
import java.util.*;// 北华大学 
// 大数据应用与开发工作室 
// 朱道阳
// Eclipse IDE 2020 08
// OpenJDK 1.8
// @author <a href="gczdy.blog.csdn.net">多多的博客</a>
// 支持Java8的最新特性，比如stream操作和lambda表达式public class Main {static Scanner sc = new Scanner(System.in);static long mod = (long) (1e9 + 7);public static void main(String[] args) {int t = 1;t = sc.nextInt();while (t-- > 0) {solve();}}static void solve() {int n=sc.nextInt();int s=sc.nextInt();//洗澡时间int m=sc.nextInt();//总分钟数int ans1=0;int ans2=0;int ans=0;int arr[][]=new int[n][2];for(int i=0;i<n;i++) {arr[i][0]=sc.nextInt();arr[i][1]=sc.nextInt();}for(int i=0;i<n;i++) {if(i==0) {if(arr[i][0]>=s) {System.out.println("YES");return;}}if(i==n-1) {if(m-arr[i][1]>=s) {System.out.println("YES");return;}}if(i>0&&arr[i][0]-arr[i-1][1]>=s) {System.out.println("YES");return;}}System.out.println("NO");}}// 被爱的人不用道歉
// 下次再见面 不要冷冰冰 也不要说反话!

D题

这题简单在子串不一定是连续的

s串里面只要有t串的所有字母就行

遍历s串

用指针指向t串的第一个字符向字符串右边跑

在遍历过程中如果s串中的字符有指针指向的数值指针往右移

如果这个字符是符号把这个符号换成指针指向的字符指针右移

如果指针已经到达了最右边这个符号可以变成任意字符('a')

遍历一遍结束

如果指针没有到达最右边说明s串里并不能包含t串里的所有字符输出no

如果指针到达了最右边说明s串里面可以包含t串里的所有字符

时间复杂度O(n)

// 注意类名必须为 Main, 不要有任何 package xxx 信息
//package Dduo;
import java.io.*;
import java.math.*;
import java.util.*;// 北华大学 
// 大数据应用与开发工作室 
// 朱道阳
// Eclipse IDE 2020 08
// OpenJDK 1.8
// @author <a href="gczdy.blog.csdn.net">多多的博客</a>
// 支持Java8的最新特性，比如stream操作和lambda表达式public class Main {static Scanner sc = new Scanner(System.in);static long mod = (long) (1e9 + 7);public static void main(String[] args) {int t = 1;t = sc.nextInt();while (t-- > 0) {solve();}}static void solve() {String s = sc.next();String t = sc.next();//不一定为连续的char arr1[]=s.toCharArray();int index=0;String str="";for(int i=0;i<s.length();i++) {if(index<t.length()&&arr1[i]==t.charAt(index)) {index++;}if(arr1[i]=='?') {if(index<t.length()) {arr1[i]=t.charAt(index);index++;}else {arr1[i]='a';}}}if(index==t.length()) {System.out.println("YES");System.out.println(str);}else {System.out.println("NO");}}}// 被爱的人不用道歉
// 下次再见面 不要冷冰冰 也不要说反话!

E题

注意数据类型 2*10e5

为了防止超时

我们可以先把数组开出来然后直接根据数 l r 进去找

再来看题目

一个数/3 一个数*3

要把所有数变成0

在纸上画一下不难想到只要有一个0出现就能让这个数一直*3 其余的数/3

然后只要算一下此时n-1个数分别要/3多少次才能变成0的和就行

贪心算法那个数肯定是L 就是最小的那个数因为他/3最少次能变成0

然后其他数就只管/就好了

我们把先l-r这些数

一共要/3 多少次求出来

然后因为我们操作第一个数的时候给另一个数*3了f（l）次

再加上这个f（l）即可

但这题关键是是构造前缀和数组pre

前缀和最经典的空间复杂度换时间复杂度嗯...

// 注意类名必须为 Main, 不要有任何 package xxx 信息
// package Dduo;
import java.io.*;
import java.math.*;
import java.util.*;// 北华大学 
// 大数据应用与开发工作室 
// 朱道阳
// Eclipse IDE 2020 08
// OpenJDK 1.8
// @author <a href="gczdy.blog.csdn.net">多多的博客</a>
// 支持Java8的最新特性，比如stream操作和lambda表达式public class Main {static Scanner sc = new Scanner(System.in);static long mod = (long) (1e9 + 7);static int arr[]=new int[200005];static int pre[]=new int[200005];public static void main(String[] args) {int t = 1;t = sc.nextInt();for (int i = 1; i < 200005; i++) {arr[i] = f(i);pre[i] = pre[i - 1] + arr[i];}while (t-- > 0) {solve();}}static void solve() {int l=sc.nextInt();int r=sc.nextInt();System.out.println(pre[r]-pre[l-1]+arr[l]);}static int f(int x) {if(x<3) {return 1;}else if(x<9) {return 2;}else if(x<27) {return 3;}else if(x<81) {return 4;}else if(x<243) {return 5;}else if(x<729) {return 6;}else if(x<2187) {return 7;}else if(x<6561) {return 8;}else if(x<19683) {return 9;}else if(x<59049) {return 10;}else if(x<177147) {return 11;}else {return 12;}}}// 被爱的人不用道歉
// 下次再见面 不要冷冰冰 也不要说反话!