原博客链接：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

待更新