【Java/补题/CF/ACM赛制】 The 2022 Hangzhou Normal U Summer Trials

• • 题目链接
  • 知识一览
  • 题目列表
  • • 快输
    • C - Check Problems（二分/模拟）
    • F - Subarrays（前缀和）

The 2022 Hangzhou Normal U Summer Trials

01 - 二分
02 - 前缀和/子数组

    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        String tmp;

        public FastReader() {
            br=new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st==null||!st.hasMoreElements()) {
                try {
                    st=new StringTokenizer(br.readLine());
                }catch(IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong(){return Long.parseLong(next());}

        String nextLine() {
            String str="";
            try {
                str=br.readLine();
            }catch(IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        boolean hasNext(){
            if(st!=null&&st.hasMoreTokens())return true;
            try {
                tmp=br.readLine();
                st=new StringTokenizer(tmp);
            }catch(IOException e) {
                return false;
            }
            return true;
        }
    }

    static PrintWriter out=new PrintWriter(
            new BufferedWriter(new OutputStreamWriter(System.out)));
    static FastReader sc=new FastReader();

#pragma GCC optimize("Ofast","inline")
#include
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;

const ll maxn=5e5+10;
ll n,k;
ll a[maxn];
ll sum[maxn];
ll s[maxn];
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		
	}
	for(int i=2;i<=n;i++){
		sum[i]=a[i]-a[i-1];
		s[i]=s[i-1]+sum[i];
	}
	sum[n+1]=1e18;
	scanf("%lld",&k);
	while(k--){
		ll x;
		scanf("%lld",&x);
		ll l=1,r=n+1;
		while(l
			ll mid=(l+r)>>1;
			if(sum[mid]>=x){
				r=mid;
			}else{
				l=mid+1;
			}
		}
		l--;
		ll ans=0;
		ans=(n-l+1)*x;
		printf("%lldn",ans+s[l]);
	}
	return 0;
}

题解：F - Subarrays

	static int N=(int)1e5+10;
    static Map mp;
    static long n,k,a[]=new long[N],sum=0,ans=0;
    public static void main(String[] args) {
        //int T=sc.nextInt();
        int T=1;
        while(T-->0){
            solve();
        }
    }
    private static void solve(){
        n=sc.nextLong();
        k=sc.nextLong();
        mp=new HashMap<>();
        mp.put((long)0,(long)1);
        for(int i=1;i<=n;i++){
            a[i]=sc.nextLong();
            sum=sum+a[i];//算出前i个数的和
            sum=sum%k;//分别求出前i个数%k的余数，并用map存起来
            ans+=mp.getOrDefault(sum,(long)0);
            mp.put(sum,mp.getOrDefault(sum,(long)0)+1);
        }
        out.println(ans);
        out.flush();
    }