题解 | 牛客小白月赛93 BCDEF Java
生不逢七
https://ac.nowcoder.com/acm/contest/82401/A
B~F题解
需要知道这个性质，两数之和相同的时候，两数之差越大，乘积越小，那么就让每位数字，a的大，b的小，再通过拆位“相乘”，时间复杂度O(n)
import java.util.*;
public class Main{
static int mod=998244353;
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),a[]=new int[n],b[]=new int[n];
String s=sc.next();
for(int i=0;i<n;i++){
a[i]=s.charAt(i)-'0';
}
s=sc.next();
long num=0,ans=0;
for(int i=0;i<n;i++){
b[i]=s.charAt(i)-'0';
if(a[i]<b[i]){
a[i]^=b[i];
b[i]^=a[i];
a[i]^=b[i];
}
num=(num*10+a[i])%mod;
}
for(int i=n-1;i>=0;i--){
ans=(ans+b[i]*num)%mod;
num=num*10%mod;
}
System.out.println(ans);
}
}
按照期望的计算方法暴力计算，题中给出了逆元的公式，乘方可用快速幂计算，时间复杂度O(1)
import java.util.*;
public class Main{
static int mod=998244353;
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
long m=sc.nextInt(),a=sc.nextInt(),b=sc.nextInt(),c=sc.nextInt();
long sum=pow(m,3);
System.out.println(pow(sum,mod-2)*m%mod*(c+(m-1)*((m-2)*a+b*3)%mod)%mod);
}
}
static long pow(long a,int b){
long ans=1;
while(b!=0){
if(b%2==1){
ans=ans*a%mod;
}
b>>=1;
a=a*a%mod;
}
return ans;
}
}
反推每一层递归结束时候的x下标，重复n次，时间复杂度O(mn)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt();
for(int i=0;i<m;i++){
long x=sc.nextLong();
for(int j=0;j<n;j++){
//每个循环内部的目的是，还原出x在敌对区间内长度为1<<(j+1)时的编号是多少
long r=x&((1L<<(j+1))-1);//在此次递归组内的编号
x=(x>>(j+1)<<(j+1))|(r<(1L<<j)?r<<1:(r-(1L<<j)<<1|1));
}
System.out.println(x);
}
}
}
实际上通过观察可知，答案的二进制正好是x的翻转，此方法时间复杂度O(mn)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt();
for(int i=0;i<m;i++){
long x=sc.nextLong();
List<Long> list=new ArrayList<>();
for(int j=0;j<n;j++){
list.add(x&1);
x>>=1;
}
for(long a:list){
x=x<<1|a;
}
System.out.println(x);
}
}
}
本题需要利用前缀和解决，需要记载的数据分别为，01数量的前缀和，01分别下标的前缀和，以及截止到改下标，所有子区间影响值之和，计算的计算的时候，需要在“影响的前缀和”相应下标作差，得到的结果再减去两个区间之间相互的影响，时间复杂度O(n+m)
import java.io.*;
public class Main{
static int mod=998244353;
public static void main(String args[]) throws IOException{
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
String arr[]=bf.readLine().split(" ");
int n=Integer.parseInt(arr[0]),m=Integer.parseInt(arr[1]),count[][]=new int[n+1][2];
long sum[][]=new long[n+1][2],pre[]=new long[n+1];
String c=bf.readLine();
for(int i=1;i<=n;i++){
int a=c.charAt(i-1)-'0';
count[i]=count[i-1].clone();
sum[i]=sum[i-1].clone();
pre[i]=(pre[i-1]+(long)count[i-1][a^1]*i%mod+mod-sum[i-1][a^1])%mod;
count[i][a]++;
sum[i][a]=(sum[i][a]+i)%mod;
}
for(int i=0;i<m;i++){
arr=bf.readLine().split(" ");
int l=Integer.parseInt(arr[0]),r=Integer.parseInt(arr[1]);
bw.write((mod+(pre[r]-pre[l-1]-((sum[r][0]-sum[l-1][0])*count[l-1][1]-sum[l-1][1]*(count[r][0]-count[l-1][0]))-((sum[r][1]-sum[l-1][1])*count[l-1][0]-sum[l-1][0]*(count[r][1]-count[l-1][1])))%mod)%mod+"\n");
}
bw.flush();
}
}
首先明确的是，答案的长度一定是s长度的约数，因为假如不是的话，得到的“本初”的某些下标对应的s下标一定是相同的，且周期性分布，要想得到较大的匹配，这些位置字母要相同，那么不如直接缩短本初的长度，时间复杂度O(t*n*d(n)*C)，其中d(n)是n的约数个数，C是字符串中字母集大小，这里C==26
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
String s=sc.next();
int n=s.length();
for(int j=1;j<=n;j++){
if(n%j==0){
String ans=find(s,j);
if(ans!=null){
System.out.println(ans);
break;
}
}
}
}
}
static String find(String s,int len){
int count[][]=new int[len][26],max[]=new int[len+1];
for(int i=0;i<s.length();i++){
count[i%len][s.charAt(i)-'a']++;
}
for(int i=len-1;i>=0;i--){
for(int j=0;j<26;j++){
max[i]=Math.max(max[i],max[i+1]+count[i][j]);
}
}
if(max[0]*2<s.length()){
return null;
}
char ans[]=new char[len];
int pre=0;
for(int i=0;i<len;i++){
for(int j=0;j<26;j++){
if((pre+count[i][j]+max[i+1])*2>=s.length()){
ans[i]=(char)(j+'a');
pre+=count[i][j];
break;
}
}
}
return new String(ans);
}
}
