牛客小白月赛93
生不逢七
https://ac.nowcoder.com/acm/contest/82401/A
原博客链接：https://blog.nowcoder.net/n/b691f958253842008554474d6f94af70
A
模拟
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65535);
static StreamTokenizer st = new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static Scanner sc = new Scanner(System.in);
static int n,m,maxn=200005,inf = 0x3f3f3f3f;
static long ans=0,mod=(int)1e9+7,INF=(long)2e18;
public static void main(String[]args) throws IOException{
new Task().main();
pw.flush();
}
static int I() throws IOException {
st.nextToken();
return (int)st.nval;
}
static String S() throws IOException {
String res=bf.readLine();
while(res.equals("")) res = bf.readLine();
return res;
}
static class Task{
void main()throws IOException{
int t=1;
t=I();
while(t-->0) solve();
}
private void solve() throws IOException {
n=I();
int a=I(),k=I();
for(int i=0,num=a+1,cnt=0;cnt<k;i=(i+1)%n,num++) {
if(check(num)) {
if(i==0) {
cnt++;
pw.print("p ");
}
}
else {
if(i==0) {
cnt++;
pw.print(num+" ");
}
}
}
pw.println();
}
private boolean check(int num) {
// TODO Auto-generated method stub
String s = String.valueOf(num);
if(s.contains("7") || num%7 ==0)
return true;
else return false;
}
}
}
B
凑最小最大两个数相乘
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65535);
static StreamTokenizer st = new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static Scanner sc = new Scanner(System.in);
static int n,m,maxn=200005,inf = 0x3f3f3f3f;
static long ans=0,mod=(int)1e9+7,INF=(long)2e18;
public static void main(String[]args) throws IOException{
new Task().main();
pw.flush();
}
static int I() throws IOException {
st.nextToken();
return (int)st.nval;
}
static String S() throws IOException {
String res=bf.readLine();
while(res.equals("")) res = bf.readLine();
return res;
}
static class Task{
void main()throws IOException{
int t=1;
//t=I();
while(t-->0) solve();
}
private void solve() throws IOException {
n=I();mod = 998244353;
char[]x = S().toCharArray();
char[]y = S().toCharArray();
for(int i=0;i<n;i++) {
if(x[i]>y[i]) {
char t=x[i];x[i]=y[i];y[i]=t;
}
}
BigInteger a = new BigInteger(String.valueOf(x));
BigInteger b = new BigInteger(String.valueOf(y));
pw.println(a.multiply(b).mod(BigInteger.valueOf(mod)));
}
}
}
C
中学数学题
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65535);
static StreamTokenizer st = new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static Scanner sc = new Scanner(System.in);
static int n,m,maxn=200005,inf = 0x3f3f3f3f;
static long ans=0,mod=(int)1e9+7,INF=(long)2e18;
public static void main(String[]args) throws IOException{
new Task().main();
pw.flush();
}
static int I() throws IOException {
st.nextToken();
return (int)st.nval;
}
static String S() throws IOException {
String res=bf.readLine();
while(res.equals("")) res = bf.readLine();
return res;
}
static class Task{
void main()throws IOException{
int t=1;
t=I();
while(t-->0) solve();
}
long qpow(long a,long b) {
long res=1;
a%=mod;
while(b>0) {
if(b%2==1) res = res*a%mod;
a = a*a%mod;
b/=2;
}
return res;
}
private void solve() throws IOException {
m=I();long a=I(),b=I(),c=I();mod=998244353;
ans= a*m%mod*(m-1)%mod*(m-2)%mod;
ans = (ans + 1L*m*3*(m-1)%mod*b%mod)%mod;
ans = (ans + m*c)%mod;
ans = ans * qpow(1L*m*m%mod*m%mod,mod-2)%mod;
pw.println(ans);
}
}
}
D
递归模拟
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65535);
static StreamTokenizer st = new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static Scanner sc = new Scanner(System.in);
static int n,m,maxn=200005,inf = 0x3f3f3f3f;
static long ans=0,mod=(int)1e9+7,INF=(long)2e18;
public static void main(String[]args) throws IOException{
new Task().main();
pw.flush();
}
static int I() throws IOException {
st.nextToken();
return (int)st.nval;
}
static String S() throws IOException {
String res=bf.readLine();
while(res.equals("")) res = bf.readLine();
return res;
}
static class Task{
void main()throws IOException{
int t=1;
//t=I();
while(t-->0) solve();
}
private void solve() throws IOException {
n=I();
m=I();
while(m-->0) {
pw.println(qu(0L,(long)Math.pow(2,n)-1L,Long.parseLong(S()),0L));
}
}
private long qu(long l, long r, long x,long sum) {
// TODO Auto-generated method stub
long mid = (l+r)/2;
if(l==r) return sum;
if(x%2==0) {
long p = x/2;
return qu(l,mid,p,sum);
}
else {
sum += (mid-l+1);
x = (x-1)/2;
return qu(mid+1,r,x,sum);
}
}
}
}
E
前缀和，官方是放过了线段树做法，但是用线段树就可以带修改
前缀和做法：
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65535);
static StreamTokenizer st = new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static Scanner sc = new Scanner(System.in);
static int n,m,maxn=200005,inf = 0x3f3f3f3f;
static long ans=0,mod=(int)1e9+7,INF=(long)2e18;
public static void main(String[]args) throws IOException{
new Task().main();
pw.flush();
}
static int I() throws IOException {
st.nextToken();
return (int)st.nval;
}
static String S() throws IOException {
String res=bf.readLine();
while(res.equals("")) res = bf.readLine();
return res;
}
static class Task{
void main()throws IOException{
int t=1;
//t=I();
while(t-->0) solve();
}
char[]s ;
long s0[] = new long[maxn];//sum of (s[i]=='0'?i:0) from 1 to i
long s1[] = new long[maxn];//sum of (s[i]=='1'?i:0) from 1 to i
long cnt0[] = new long[maxn];//sum of (s[i]=='0'?1:0) from 1 to i
long cnt1[] = new long[maxn];//sum of (s[i]=='1'?1:0) from 1 to i
long sum[] = new long[maxn];//answer of [1,i]
private void solve() throws IOException {
n=I();mod=998244353;m=I();
s = (")"+S()).toCharArray();
for(int i=1;i<=n;i++) {
cnt1[i]=cnt1[i-1];
cnt0[i]=cnt0[i-1];
s0[i]=s0[i-1];
s1[i]=s1[i-1];
if(s[i] == '1') {
cnt1[i]++;
s1[i] += i;
ans = (ans + cnt0[i-1]*i - s0[i-1] +mod)%mod;
}
else {
cnt0[i]++;
s0[i]+=i;
ans = (ans + cnt1[i-1]*i - s1[i-1] +mod)%mod;
}
sum[i] = ans;
}
while(m-->0) {
int l=I(),r=I();
long res=(sum[r]-sum[l-1]+mod)%mod;
long c0 = cnt0[r]-cnt0[l-1];
long c1 = cnt1[r]-cnt1[l-1];
long ss1 = s1[r]-s1[l-1],ss0 = s0[r]-s0[l-1];
res = (res - (-c0*s1[l-1]%mod + ss1*cnt0[l-1]%mod +mod)%mod + mod)%mod;
res = (res - (-c1*s0[l-1]%mod + ss0*cnt1[l-1]%mod +mod)%mod + mod)%mod;
pw.println(res);
}
}
}
}
线段树做法：
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in),65535);
static StreamTokenizer st = new StreamTokenizer(bf);
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static Scanner sc = new Scanner(System.in);
static int n,m,maxn=200005,inf = 0x3f3f3f3f;
static long ans=0,mod=(int)1e9+7,INF=(long)2e18;
public static void main(String[]args) throws IOException{
new Task().main();
pw.flush();
}
static int I() throws IOException {
st.nextToken();
return (int)st.nval;
}
static String S() throws IOException {
String res=bf.readLine();
while(res.equals("")) res = bf.readLine();
return res;
}
static class node{
long le[] = new long[2];//所有0或1到区间左端的距离之和
long ri[] = new long[2];//所有0或1到区间右端的距离之和
long cnt[] = new long[2];//区间0或1的数量
long res=0;//区间答案
long len=0;//区间长度
}
static class Task{
void main()throws IOException{
int t=1;
//t=I();
while(t-->0) solve();
}
char[]s ;
node[] tr = new node[maxn<<2];
node p[] = new node[100];
int pi=0;
private void solve() throws IOException {
n=I();mod=998244353;
m=I();
s = (")"+S()).toCharArray();
build(1,1,n);
for(int i=0;i<p.length;i++) p[i]=new node();
while(m-->0) {
int l=I(),r=I();pi=0;
clear(p[pi]);
if(l==r) pw.println(0);
else {
qu(1,1,n,l,r);
pw.println(p[pi].res%mod);
}
}
}
private void clear(node p) {
for(int i=0;i<2;i++) {
p.le[i]=p.ri[i]=0;p.cnt[i]=0;
}
p.len=0;p.res=0;
}
private void build(int i, int l, int r) {
tr[i] = new node();
if(l==r) {
clear(tr[i]);
tr[i].le[s[l]-'0'] = tr[i].ri[s[l]-'0'] = 1;
tr[i].len=1;
tr[i].cnt[s[l]-'0']=1;
return;
}
int mid=(l+r)/2;
build(i<<1,l,mid);build(i<<1|1,mid+1,r);
up(tr[i],tr[i<<1],tr[i<<1|1]);
}
private void qu(int i, int l, int r, int ll, int rr) {
if(ll<=l && r<=rr) {
up(p[pi+1],p[pi],tr[i]);
pi++;
return;
}
int mid=l+r>>1;
if(mid >= ll) qu(i<<1,l,mid,ll,rr);
if(mid+1 <= rr) qu(i<<1|1,mid+1,r,ll,rr);
}
private void up(node w, node x, node y) {
node a = w;
clear(a);
a.len = x.len + y.len;
a.res = (x.res + y.res) %mod;
for(int j=0;j<2;j++) {
a.le[j] = x.le[j] + y.cnt[j]*x.len%mod + y.le[j];
a.le[j]%=mod;
a.ri[j] = y.ri[j] + x.cnt[j]*y.len%mod + x.ri[j];
a.ri[j]%=mod;
a.cnt[j] = x.cnt[j]+y.cnt[j];
long cnt = x.cnt[j]*y.cnt[1-j]%mod;
a.res = (a.res + x.ri[j]*y.cnt[1-j] + y.le[1-j]*x.cnt[j] - cnt + mod)%mod;
}
}
}
}
F
待更新
万得信息开奖6人在聊
投递菜鸟集团等公司10个岗位 >