备孕百度之星-8月30日

昨天打的很烂，A了两个题目的一半，发现了很多以前完全没写过的代码，甚至有一些未了解过的ACM的算法

糖果促销

一直思考这么从小的数量开始买，想到了二分检查答案的方法。正解类似于一种可退货的思想，当时最后手上要有一个糖纸。故k-(k-1)/p。（退货(k-1)/p）

注意：ACM赛制，一定不要多输出了，当上面输出了结果，记得continue或return

import java.util.Scanner;
import java.util.*;

class Main {

   public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while (T-- != 0){
            long p = in.nextInt();
            long k = in.nextInt();
            if(p == 1) {
                System.out.println(Math.min(1, k));
                continue;
            }
            if(p >= k) {
                System.out.println(k);
                continue;
            }
            int cur_t = 0;//糖
            int cur_z = 0;//糖紙
            long res = 0;
            res = k - k/p;
            if(k % p == 0) res++;
            System.out.println(res);
        }
        in.close();
   }
}

公园

过了一半的测试用例，思考是最短路径问题，然后存在小度和熊的共同走，考虑遍历其中一方的各个节点。但是存在两方最后都不走原来最短路径的情况，遍历所有点作为相遇点，存在三个超时的测试用例。

正解

三源的BFS问题，遍历所有集合点

A一半的最短路写法：

import java.util.Scanner;
import java.util.*;

class Main {

   public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // code here
        //f算法求最短路径，暴力枚举
        long TE = in.nextInt();
        long FE = in.nextInt();
        long S = in.nextInt();
        int T = in.nextInt()-1;
        int F = in.nextInt()-1;
        int N = in.nextInt();
        int M = in.nextInt();
        int[][] paths = new int[M][2];
        Set<String> set = new HashSet();

        long[][] f = new long[N][N];
        int[][] p = new int[N][N];
        for(int i = 0; i < N; i++) Arrays.fill(f[i], 50000);
        for(int i = 0; i < N; i++) Arrays.fill(p[i], i);//-1为直接到达
        p[N-1][N-1] = N-1;
        for(int i = 0; i < M; i++){
            paths[i][0] = in.nextInt()-1;
            paths[i][1] = in.nextInt()-1;
            //   set.add(paths[i][0] + "=" + paths[i][1]);
            //   set.add(paths[i][1] + "=" + paths[i][0]);
            f[paths[i][0]][paths[i][1]] = 1;
            f[paths[i][1]][paths[i][0]] = 1;
        }
        for(int k = 0; k < N; k++){
            for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                    if(i == j) f[i][j] = 0;
                    if(i != j && k != i && k != j && f[i][j] > f[i][k] + f[k][j]){
                        f[i][j] = f[i][k] + f[k][j];
                        p[i][j] = p[k][j];
                    }
                }
            }
        }
        //小度找熊
        //熊依次走自己的最短路径
        long res = Long.MAX_VALUE;
        for(int i = 0; i < N; i++){
            //在N点汇合
            if(f[T][i] < 50000 && f[F][i] < 50000 && f[i][N-1] < 50000){
                res = Math.min(res, TE * f[T][i] + FE * f[F][i] + (TE + FE - S) * f[i][N-1]);
            }
        }
        if (res == Long.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(res);
        }
        in.close();
   }
}

补的BFS：（10min就敲出来了。。。）

package Function;

import java.util.*;

public class BFS {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // code here
        //f算法求最短路径，暴力枚举
        long TE = in.nextInt();
        long FE = in.nextInt();
        long S = in.nextInt();
        int T = in.nextInt()-1;
        int F = in.nextInt()-1;
        int N = in.nextInt();
        int M = in.nextInt();
        List<Integer>[] path = new List[N];
        Arrays.setAll(path, e->new ArrayList<>());

        for(int i = 0; i < M; i++){
            int a = in.nextInt()-1;
            int b = in.nextInt()-1;
            path[a].add(b);
            path[b].add(a);
        }
        int[][] b = new int[3][N];// T、F、N-1
        b[0] = bfs(T, path);
        b[1] = bfs(F, path);
        b[2] = bfs(N-1, path);
        //枚举汇合点
        long res = Long.MAX_VALUE;
        for(int i = 0; i < N; i++){
            //在N点汇合
            if(b[0][i] != -1 && b[1][i] != -1 && b[2][i] != -1){
                res = Math.min(res, TE * b[0][i] + FE * b[1][i] + (TE + FE - S) * b[2][i]);
            }
        }
        if (res == Long.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(res);
        }
        in.close();
    }
    public static int[] bfs(int t, List<Integer>[] p){
        int n = p.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Queue<Integer> q = new ArrayDeque<>();
        q.add(t);
        res[t] = 0;
        int index = 0;
        while(!q.isEmpty()){
            index++;
            int c = q.size();
            for(int i = 0; i < c; i++){
                int num = q.poll();
                for(int j = 0; j < p[num].size(); j++){
                    if(res[p[num].get(j)] == -1){
                        res[p[num].get((j))] = index;
                        q.offer(p[num].get(j));
                    }
                }
            }
        }
        return res;
    }
}

第五维度

一开始想到二分，没有写，感觉写不出来。看了题解后写的java二分超时，发现要转化为c++了。

要多看看c++的代码了，比赛时如果存在超时的情况，使用c++在敲一遍

#include<bits/stdc++.h> 

using namespace std;
typedef long long ll;
int n,m;
int s[100010], v[100010];

bool check(ll j){
    ll sum = 0;
    ll remove = 0;
    for(int i = 0; i < n; i++){
        if(j > s[i]){
            remove = max(remove, v[i] * (j - s[i]));
            sum += v[i] * (j - s[i]);
        }
    }
    return (sum - remove) > m;
}

int main( )
{
    cin >> n >> m;
    ll count = 0;
    for(int i = 0; i < n; i++){
        cin >> s[i] >> v[i];
        if(v[i] != 0) count++;
    }
    int ans = -1;
    ll l = 1, r = 999999999;
    ll mid;
    while(l <= r){
        mid = l + (r - l) / 2;
        if(check(mid)){
            ans = mid;
            r = mid - 1;
        }else{
            l = mid + 1;
        }
    }
    cout << ans;
}