飞道的博客

蓝桥杯题库 算法提高非vip部分（C++、Java）代码实现（1-100）

2020-03-23 13:48 529人阅读  评论(0)

文章目录

将定期更新蓝桥杯习题集的解题报告~

四、算法提高

ADV-1 两条直线

简记：想到一个三分套三分确定坐标的办法，时间复杂度O(n*log(1e10)*log(1e10))的办法，过了60%的数据。

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 100005;
const double eps = 0.01;
struct point{
    int x,y;
}a[maxn];
int n;
int x_max=-inf ,x_min=inf ,y_max=-inf, y_min=inf;
double cla(double x, double y){
    double ret=0;
    for(int i=0;i<n;i++){
        double now=min(fabs(a[i].x-a[i].y+y-x), fabs(-a[i].x-a[i].y+x+y));
        ret=max(ret, now);
    }
    return ret;
}
double fy(double x, double l, double r){
    double midl,midr,e;
    while(r-l>eps){
        //printf("ly=%.4lf ry=%.4lf\n",l,r);
        e=(r-l)/3;
        midl=l+e;
        midr=midl+e;
        double ansl=cla(x, midl);
        double ansr=cla(x, midr);
        if(ansl<ansr){
            r=midr;
        }
        else{
            l=midl;
        }
    }
    return cla(x, l);
}
double fx(double l, double r){
    double midl,midr,e;
    while(r-l>eps){
        //printf("lx=%.4lf rx=%.4lf\n",l,r);
        e=(r-l)/3;
        midl=l+e;
        midr=midl+e;
        double ansl=fy(midl, y_min, y_max);
        double ansr=fy(midr, y_min, y_max);
        if(ansl<ansr){
            r=midr;
        }
        else{
            l=midl;
        }
    }
    return fy(l, y_min, y_max);
}
int main(){
    scanf("%d",&n);
    double lx,ly,rx,ry;
    for(int i=0;i<n;i++){
        scanf("%d%d",&a[i].x, &a[i].y);
        x_min=min(x_min, a[i].x);
        x_max=max(x_max, a[i].x);
        y_min=min(y_min, a[i].y);
        y_max=max(y_max, a[i].y);
    }
    //printf("%.4lf %.4lf\n",(double)x_min,(double)x_max);
    printf("%.1lf\n",fx(x_min, x_max));
    return 0;
}

完全通过代码：

cpp:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;

const int N = 100000;
struct P {
    int x, y;
};
bool cmp(P a, P b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
P d[N + 5];
struct F {
    int max, min;
};
F fl[N + 5], fr[N + 5];
inline double Max(double a, double b) { return a > b ? a : b; }
inline double Min(double a, double b) { return a > b ? b : a; }
bool check(double m, int n) {
    m *= 2;
    int i, j = 0;
    for (i = 0; i < n; i++) {
        while (j < n && d[j].x - d[i].x <= m) j++;
        double MAX = -1e10;
        double MIN = 1e10;
        if (j != n) {
            MAX = Max(MAX, fr[j].max);
            MIN = Min(MIN, fr[j].min);
        }
        if (i - 1 >= 0) {
            MAX = Max(MAX, fl[i - 1].max);
            MIN = Min(MIN, fl[i - 1].min);
        }
        //   cout<<i<<" "<<j<<" "<<MAX<<" "<<MIN<<endl;
        if (MAX - MIN <= m) return true;
    }
    return false;
}
void init(int n) {
    int i;
    fl[0].min = fl[0].max = d[0].y;
    for (i = 1; i < n; i++) {
        fl[i].max = Max(fl[i - 1].max, d[i].y);
        fl[i].min = Min(fl[i - 1].min, d[i].y);
    }
    fr[n - 1].min = fr[n - 1].max = d[n - 1].y;
    for (i = n - 2; i >= 0; i--) {
        fr[i].max = Max(fr[i + 1].max, d[i].y);
        fr[i].min = Min(fr[i + 1].min, d[i].y);
    }
}
int main() {
    int i, n;
    cin >> n;
    for (i = 0; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        d[i].x = x + y;
        d[i].y = x - y;
    }
    sort(d, d + n, cmp);
    init(n);
    double l = 0.0;
    double r = 1000000000;
    while (r - l >= 0.01) {
        double m = (l + r) / 2;
        //  cout<<m<<endl;
        if (check(m, n))
            r = m;
        else
            l = m;
    }
    printf("%.1f\n", r);
    return 0;
}

java:

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public
class Main {
   public
    static void main(String[] args) throws IOException {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader sc = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, sc, out);
        out.close();
    }

    static class Task {
       public
        static final double EXP = 1e-3;

       public
        int find(double[][] p, int l, int r, double x) {
            int ans = -1;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (p[mid][0] < x) {
                    ans = mid;
                    l = mid + 1;
                } else
                    r = mid - 1;
            }
            return ans;
        }

       public
        boolean check(double[][] p, SegTree sgt, double ans) {
            for (int i = 1; i < p.length; i++) {
                int l = i;
                int r = p.length - 1;
                r = find(p, l, r, p[i][0] + 2.0 * ans);
                double up = 0;
                double down = Double.MAX_VALUE;
                if (l - 1 > 0) {
                    SegTree.Node temp = sgt.ask(1, 1, l - 1);
                    up = Math.max(up, temp.max_value);
                    down = Math.min(down, temp.min_value);
                }
                if (r + 1 <= p.length - 1) {
                    SegTree.Node temp = sgt.ask(1, r + 1, p.length - 1);
                    up = Math.max(up, temp.max_value);
                    down = Math.min(down, temp.min_value);
                }
                if (up - down <= 2.0 * ans) {
                    return true;
                }
            }
            return false;
        }

       public
        void solve(int testNumber, InputReader sc,
                   PrintWriter out) throws IOException {
            int n = sc.nextInt();
            double[][] p = new double[n + 1][2];

            for (int i = 1; i <= n; i++) {
                p[i][0] = sc.nextDouble();
                p[i][1] = sc.nextDouble();
                double c = Math.sqrt(p[i][0] * p[i][0] + p[i][1] * p[i][1]);
                double d = Math.asin(p[i][1] / c);
                d += Math.PI / 4;
                p[i][1] = c * Math.sin(d);
                p[i][0] = c * Math.cos(d);
            }
            Arrays.sort(p, 1, n + 1, new Comparator<double[]>() {
                @Override public int compare(double[] o1, double[] o2) {
                    if (o1[0] < o2[0]) return -1;
                    if (o1[0] > o2[0]) return 1;
                    return 0;
                }
            });
            SegTree sgt = new SegTree(n, p);
            sgt.build(1, 1, n);
            double l = 0;
            double r = 1e9;
            double ans = 0;
            while (Math.abs(r - l) > EXP) {
                double mid = (l + r) / 2.0;
                if (check(p, sgt, mid)) {
                    ans = mid;
                    r = mid;
                } else
                    l = mid;
            }
            out.printf("%.1f\n", ans * Math.sqrt(2.0));  //已知斜边 求两条直角边
        }

    }

    static class SegTree {
        class Node {
            int l;
            int r;
            double max_value;
            double min_value;

           public
            Node(int l, int r) {
                this.l = l;
                this.r = r;
            }

           public
            Node() {}
        } public Node[] t;
       public
        double[][] buf;

       public
        SegTree(int n, double[][] buf) {
            t = new Node[(n + 10) << 2];
            this.buf = buf;
        }

       public
        void pushUp(int p) {
            t[p].max_value =
                Math.max(t[p * 2].max_value, t[p * 2 + 1].max_value);
            t[p].min_value =
                Math.min(t[p * 2].min_value, t[p * 2 + 1].min_value);
        }

       public
        void build(int p, int l, int r) {
            t[p] = new Node(l, r);
            if (l == r) {
                t[p].max_value = t[p].min_value = buf[l][1];
                return;
            }
            int mid = (l + r) >> 1;
            build(p * 2, l, mid);
            build(p * 2 + 1, mid + 1, r);
            pushUp(p);
        }

       public
        Node ask(int p, int l, int r) {
            if (t[p].l >= l && t[p].r <= r) return t[p];
            Node ans = new Node();
            Node res1 = null;
            Node res2 = null;
            int mid = (t[p].l + t[p].r) >> 1;
            if (l <= mid) res1 = ask(p * 2, l, r);
            if (r > mid) res2 = ask(p * 2 + 1, l, r);
            if (res1 == null) return res2;
            if (res2 == null) return res1;
            ans.max_value = Math.max(res1.max_value, res2.max_value);
            ans.min_value = Math.min(res1.min_value, res2.min_value);
            return ans;
        }
    }

    static class InputReader {
       private
        InputStreamReader reader;
       private
        char[] buf;
       private
        int len, now;

       public
        InputReader(InputStream stream) {
            reader = new InputStreamReader(stream);
            buf = new char[1024];
            len = 0;
            now = 0;
        }

       public
        String next() throws IOException {
            if (!hasNext()) throw new NullPointerException();
            StringBuilder sb = new StringBuilder();
            while (!isSpaceChar(buf[now])) {
                sb.append(buf[now]);
                if (!move()) break;
            }
            return sb.toString();
        }

       public
        int nextInt() throws IOException {
            if (!hasNext()) throw new NullPointerException();
            boolean x = false;
            if (buf[now] == '-') {
                x = true;
                if (!move()) throw new NumberFormatException();
            }
            int ans = 0;
            while (!isSpaceChar(buf[now])) {
                if (isNum(buf[now]))
                    ans = ans * 10 + buf[now] - '0';
                else
                    throw new NumberFormatException();
                if (!move()) break;
            }
            return (x ? -1 : 1) * ans;
        }

       public
        String nextLine() throws IOException {
            if (!hasNextLine()) throw new NullPointerException();
            StringBuilder sb = new StringBuilder();
            while (buf[now] != '\n') {
                sb.append(buf[now]);
                if (!move()) return sb.toString();
            }
            now++;
            return sb.toString();
        }

       public
        long nextLong() throws IOException {
            if (!hasNext()) throw new NullPointerException();
            boolean x = false;
            if (buf[now] == '-') {
                x = true;
                if (!move()) throw new NumberFormatException();
            }
            long ans = 0;
            while (!isSpaceChar(buf[now])) {
                if (isNum(buf[now]))
                    ans = ans * 10 + buf[now] - '0';
                else
                    throw new NumberFormatException();
                if (!move()) break;
            }
            return (x ? -1 : 1) * ans;
        }

       public
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

       public
        int nextHexInt() throws IOException {
            if (!hasNext()) throw new NullPointerException();
            boolean x = false;
            if (buf[now] == '-') {
                x = true;
                if (!move()) throw new NumberFormatException();
            }
            int ans = 0;
            while (!isSpaceChar(buf[now])) {
                if (isHex(buf[now]))
                    ans = ans * 16 + toHex(buf[now]);
                else
                    throw new NumberFormatException();
                if (!move()) break;
            }
            return (x ? -1 : 1) * ans;
        }

       public
        char nextChar() throws IOException {
            if (!hasNext()) throw new NullPointerException();
            char tmp = buf[now];
            move();
            return tmp;
        }
       public
        int next(char[] s) throws IOException {
            if (!hasNext()) throw new NullPointerException();
            int len = 0;
            while (!isSpaceChar(buf[now]) && len < s.length) {
                s[len++] = buf[now];
                if (!move()) break;
            }
            return len;
        }
       public
        boolean hasNext() throws IOException { return skip(); }

       public
        boolean hasNextLine() throws IOException {
            return now < len || refill();
        }

       private
        boolean move() throws IOException {
            now++;
            return hasNextLine();
        }

       private
        boolean skip() throws IOException {
            if (!hasNextLine()) return false;
            while (isSpaceChar(buf[now])) {
                if (!move()) return false;
            }
            return true;
        }

       private
        boolean isSpaceChar(char c) { return !(c >= 33 && c <= 126); }

       private
        boolean isNum(char c) { return c >= '0' && c <= '9'; }

       private
        boolean isHex(char c) {
            return c >= '0' && c <= '9' || c >= 'A' && c <= 'F';
        }

       private
        int toHex(char c) {
            if (c >= '0' && c <= '9')
                return c - '0';
            else
                return c - 'A' + 10;
        }

       private
        boolean refill() throws IOException {
            len = reader.read(buf);
            now = 0;
            return len > 0;
        }
    }
}

ADV-2 矩阵翻转

cpp:

#include <bits/stdc++.h>
using namespace std;
int x[33][33], ans, N;
void fun1(int n) {
    int i, j, lin = 0, a, b;
    for (j = 0; j < N; j++) lin += x[n - 1][j];
    for (i = 0; i < n - 1; i++) {
        a = -1000000000;
        b = x[i][n - 1] + x[i + n][n - 1];
        for (j = 0; j < n - 1; j++)
            b += abs(x[i][j] + x[i + n][j] + x[i][j + n] + x[i + n][j + n]);
        a = a > b ? a : b;
        b = -x[i][n - 1] - x[i + n][n - 1];
        for (j = 0; j < n - 1; j++)
            b += abs(-x[i][j] - x[i + n][j] + x[i][j + n] + x[i + n][j + n]);
        a = a > b ? a : b;
        lin += a;
    }
    ans = ans > lin ? ans : lin;
}
void fun(int n) {
    int i, j, k;
    for (k = 0; k < (1 << n - 1); k++) {
        for (i = 0; i < n - 1; i++)
            if ((k & (1 << i)) != 0)
                for (j = 0; j < n; j++) {
                    x[j][i] *= -1;
                    x[j][i + n] *= -1;
                }
        fun1(n);
        for (i = 0; i < n - 1; i++)
            if ((k & (1 << i)) != 0)
                for (j = 0; j < n; j++) {
                    x[j][i] *= -1;
                    x[j][i + n] *= -1;
                }
    }
}
int main() {
    int i, j, k;
    cin >> N;
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++) cin >> x[i][j];
    k = (N + 1) / 2;
    ans = -1000000000;
    fun(k);
    for (i = 0; i < k; i++)
        for (j = 0; j < k; j++) x[i][j] = -x[i][j];
    fun(k);
    cout << ans << endl;
    return 0;
}

java:

import java.util.Scanner;

public
class Main {
   public
    static int N, X;
   public
    static int[][] Ciel;
   public
    static int ans = Integer.MIN_VALUE;  //最终结果,初始化为最小

   public
    void getTempMax() {
        int max = 0;
        int tempA, tempB;
        for (int j = 0; j < N; j++) max += Ciel[X - 1][j];
        for (int i = 0; i < X - 1; i++) {
            tempA = Integer.MIN_VALUE;
            tempB = Ciel[i][X - 1] + Ciel[i + X][X - 1];
            for (int j = 0; j < X - 1; j++)
                tempB += Math.abs(Ciel[i][j] + Ciel[i][j + X] + Ciel[i + X][j] +
                                  Ciel[i + X][j + X]);
            tempA = Math.max(tempA, tempB);
            tempB = -1 * (Ciel[i][X - 1] + Ciel[i + X][X - 1]);
            for (int j = 0; j < X - 1; j++)
                tempB += Math.abs((-1) * Ciel[i][j] + Ciel[i][j + X] +
                                  (-1) * Ciel[i + X][j] + Ciel[i + X][j + X]);
            tempA = Math.max(tempA, tempB);
            max += tempA;
        }
        ans = Math.max(max, ans);
    }

   public
    void getResult() {
        for (int t = 0; t < (1 << X - 1); t++) {
            for (int j = 0; j < X - 1; j++) {
                if ((t & (1 << j)) != 0) {
                    for (int i = 0; i < X; i++) {
                        Ciel[i][j] *= -1;
                        Ciel[i][j + X] *= -1;
                    }
                }
            }
            getTempMax();
            for (int j = 0; j < X - 1; j++) {
                if ((t & (1 << j)) != 0) {
                    for (int i = 0; i < X; i++) {
                        Ciel[i][j] *= -1;
                        Ciel[i][j + X] *= -1;
                    }
                }
            }
        }
    }

   public
    static void main(String[] args) {
        Main test = new Main();
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        X = (N + 1) / 2;
        Ciel = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) Ciel[i][j] = in.nextInt();
        test.getResult();
        System.out.println(ans);
    }
}

ADV-3 金属采集

cpp:

#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 100000 + 10, oo = 100000000, MAXK = 10 + 1;
typedef long long LL;
int N, S, K, fa[MAXN];
int g[MAXN], num[MAXN * 2], next[MAXN * 2], cost[MAXN * 2], tot = 1;
LL f[MAXN][MAXK], sum;
inline void read(int &x) {
    char ch;
    while (ch = getchar(), ch > '9' || ch < '0')
        ;
    x = ch - 48;
    while (ch = getchar(), ch <= '9' && ch >= '0') x = x * 10 + ch - 48;
}
inline void addedge(int a, int b, int c) {
    ++tot;
    num[tot] = b;
    next[tot] = g[a];
    g[a] = tot;
    cost[tot] = c;
}
void dfs(int x) {
    for (int i = g[x]; i; i = next[i])
        if (num[i] != fa[x]) {
            fa[num[i]] = x;
            dfs(num[i]);
            for (int a = K; a; --a)
                for (int b = 1; b <= a; ++b)
                    f[x][a] = max(f[x][a], f[x][a - b] + f[num[i]][b] +
                                               (LL)(-b + 2) * cost[i]);
        }
}
int main() {
    read(N);
    read(S);
    read(K);
    for (int i = 1; i < N; ++i) {
        int x, y, z;
        read(x);
        read(y);
        read(z);
        sum += z;
        addedge(x, y, z);
        addedge(y, x, z);
    }
    sum = sum + sum;
    dfs(S);
    LL ans = oo;
    ans = ans * ans;
    for (int i = 0; i <= K; ++i) ans = min(ans, sum - f[S][i]);
    cout << ans << endl;
    return 0;
}

java:

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Stack;

class canner {
   private
    InputStream is = System.in;

   public
    int nextInt() {
        try {
            int i;

            while ((i = is.read()) < 45 || i > 57) {
            }

            int mark = 1, temp = 0;

            if (i == 45) {
                mark = -1;
                i = is.read();
            }

            while (i > 47 && i < 58) {
                temp = temp * 10 + i - 48;
                i = is.read();
            }

            return temp * mark;
        } catch (IOException e) {
            e.printStackTrace();
        }

        return -1;
    }
}

public class Main {
    static class Edge {
       public
        int to;
       public
        int next;
       public
        int w;
    }

    private static int head[];
   private
    static Edge[] edge;
   private
    static int top;
   private
    static int dp[][];
    static int k;
    static boolean[] flag;

   public
    static void main(String[] args) {
        canner sc = new canner();
        int n = sc.nextInt();
        int s = sc.nextInt();
        k = sc.nextInt();
        init(n);
        dp = new int[n + 1][k + 1];
        for (int i = 1; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            addEdge(a, b, c);
            addEdge(b, a, c);
        }
        dfs(s);
        System.out.println(dp[s][k]);
    }

   private
    static void dfs(int root) {
        Stack<Integer> stack = new Stack<Integer>();
        int temp = root;
        stack.push(root);
        flag[root] = true;
        while (!stack.isEmpty()) {
            root = stack.peek();
            int num = find(root);

            if (num == -1) {
                stack.pop();
                if (!stack.isEmpty()) {
                    int peek = stack.peek();
                    int to = root;
                    int w = find2(root, peek);
                    for (int j = k; j >= 0; j--) {
                        dp[peek][j] += dp[to][0] + 2 * w;
                        for (int l = 1; l <= j; l++) {
                            dp[peek][j] =
                                Math.min(dp[peek][j],
                                         dp[peek][j - l] + dp[to][l] + l * w);
                        }
                    }
                }

            } else {
                flag[num] = true;
                stack.push(num);
            }
        }
    }

   private
    static int find2(int root, int peek) {
        for (int i = head[peek]; i != -1; i = edge[i].next) {
            if (edge[i].to == root) return edge[i].w;
        }
        return peek;
    }

   private
    static int find(int root) {
        int num = -1;
        for (int i = head[root]; i != -1; i = edge[i].next) {
            if (flag[edge[i].to]) continue;
            num = edge[i].to;
            break;
        }
        return num;
    }

   private
    static void addEdge(int to, int next, int w) {
        edge[top] = new Edge();
        edge[top].to = next;
        edge[top].w = w;
        edge[top].next = head[to];
        head[to] = top++;
    }

   private
    static void init(int n) {
        flag = new boolean[n + 1];
        int size = (n - 1) * 2;
        edge = new Edge[size];
        head = new int[size];
        top = 0;
        Arrays.fill(head, -1);
    }
}

ADV-4 道路和航路

cpp:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>

#define clr(a,b) memset(a, b, sizeof(a))

using namespace std;

const int N = 25050;
const int E = 150500;

//邻接表
int h[N], v[E], w[E], nxt[E], el;
void initEdge() {
    clr(h, -1); el = 0;
}
void addEdge(int x, int y, int z) {
    v[el] = y; w[el] = z; nxt[el] = h[x]; h[x] = el++;
}

//belong[i] 表示节点 i 所在的强连通分量；
//cnt 表示强连通分量的个数；
int dfn[N], sta[N], low[N], belong[N];
int top, cnt, ind, n;
bool vis[N];

void TarjanSolve(int u) {
    dfn[u] = low[u] = ++ind;
    vis[u] = true;
    sta[++top] = u;
    for(int p=h[u]; ~p; p=nxt[p]) {
        int i = v[p];
        if(!dfn[i]) {
            TarjanSolve(i);
            if(low[i] < low[u]) low[u] = low[i];
        }
        else
        if(vis[i] && dfn[i] < low[u])
            low[u] = dfn[i];
    }
    if(dfn[u] == low[u]) {
        ++cnt;
        while(1) {
            int i = sta[top--];
            vis[i] = false;
            belong[i] = cnt;
            if(i == u) break;
        }
    }
}
void Tarjan() {//注意节点是从几开始存的
    clr(dfn, 0);
    clr(vis, 0);
    top = cnt = ind = 0;
    for(int i=1; i<=n; i++)//这里节点从1开始存，若从0开始存要改这里
        if(!dfn[i]) TarjanSolve(i);
}

struct EDGE {
    int u, v, w;
    bool flag;
    EDGE(){}
    EDGE(int x, int y, int z, bool f):u(x), v(y), w(z), flag(f){}
}   edge[E];

int edgel;

bool visitable[N];

void dfs(int x) {
    visitable[x] = true;
    for(int i=h[x]; ~i; i=nxt[i]) {
        if(!visitable[v[i]]) {
            dfs(v[i]);
        }
    }
}

int indegree[N];

//链表
int lh[N], lel, lv[E], lnxt[E];
void initLink() {
    clr(lh, -1); lel = 0;
}
void addLink(int x, int y) {
    lv[lel] = y; lnxt[lel] = lh[x]; lh[x] = lel++;
}

int dis[N];
bool tag[N];

int main() {
    int r, p, s;
    while(~scanf("%d%d%d%d", &n, &r, &p, &s)) {
        clr(visitable, 0);
        initEdge();
        edgel = 0;
        int x, y, z;
        for(int i=0; i<r; i++) {
            scanf("%d%d%d", &x, &y, &z);
            addEdge(x, y, z);
            addEdge(y, x, z);
            edge[edgel++] = EDGE(x, y, z, false);
        }
        for(int i=0; i<p; i++) {
            scanf("%d%d%d", &x, &y, &z);
            addEdge(x, y, z);
            edge[edgel++] = EDGE(x, y, z, true);
        }
        Tarjan();
        dfs(s);
        initEdge();
        initLink();
        clr(indegree, 0);
        for(int i=0; i<edgel; i++) {
            if(visitable[edge[i].u] && visitable[edge[i].v]) {
                addEdge(edge[i].u, edge[i].v, edge[i].w);
                if(edge[i].flag) {
                    ++ indegree[belong[edge[i].v]];
                    addLink(belong[edge[i].v], edge[i].v);
                } else {
                    addEdge(edge[i].v, edge[i].u, edge[i].w);
                }
            }
        }
        stack<int> zeroDegree;
        priority_queue<pair<int,int> > que;
        clr(vis, false);
        clr(tag, false);
        clr(dis, 0x3f);
        dis[s] = 0;
        que.push(make_pair(0, s));
        while(!que.empty() || !zeroDegree.empty()) {
            if(que.empty()) {
                int x = zeroDegree.top(); zeroDegree.pop();
                for(int i=lh[x]; ~i; i=lnxt[i]) {
                    int y = lv[i];
                    if(!vis[y]) {
                        vis[y] = true;
                        que.push(make_pair(-dis[y], y));
                    }
                }
            } else {
                int x = que.top().second; que.pop();
                if(tag[x]) continue;
                tag[x]  = true;
                for(int i=h[x]; ~i; i=nxt[i]) {
                    int y = v[i];
                    if(!tag[y] && dis[y] > dis[x] + w[i]) {
                        dis[y] = dis[x] + w[i];
                        if(belong[x] == belong[y]) {
                            que.push(make_pair(-dis[y], y));
                        }
                    }
                    if(belong[x] != belong[y]) {
                        -- indegree[belong[y]];
                        if(indegree[belong[y]] == 0) {
                            zeroDegree.push(belong[y]);
                        }
                    }
                }
            }
        }
        for(int i=1; i<=n; i++) {
            if(visitable[i]) {
                printf("%d\n", dis[i]);
            } else {
                puts("NO PATH");
            }
        }
    }

    return 0;
}

ADV-5 最小方差生成树

该题暂时没有人完全正确，暂时没有该语言的参考程序。

ADV-6 VIP试题 邮票面值设计

cpp:

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn1 = 40;
const int maxn2 = 10000;
int n, m, ans = 0, f[maxn1][maxn2];
int a[maxn1 + 20], b[maxn2 + 20];

void dfs(int step, int s, int e) {
    int i, j, k;
    if (step > m) {
        if (ans < e - 1)
            for (ans = e - 1, i = 1; i <= m; i++) b[i] = a[i];
        return;
    }
    for (k = e; k >= s; k--) {
        j = a[step - 1] * n;
        for (i = 0; i <= j; i++) f[step][i] = f[step - 1][i];
        memset(&f[step][j + 1], 25, sizeof(int) * ((n * k + 1 - j) + 10));

        for (j = n * k, i = k; i <= j; i++)
            f[step][i] = min(f[step][i], f[step][i - k] + 1);
        for (i = e; i <= j + 1; i++)
            if (f[step][i] > n) {
                a[step] = k, dfs(step + 1, k + 1, i);
                break;
            }
    }
}

int main() {
    int i;
    memset(f[1], 25, sizeof(f[1]));
    scanf("%d%d", &n, &m);
    for (i = 0; i <= n; i++) f[1][i] = i;
    a[1] = 1, dfs(2, 2, n + 1);
    for (i = 1; i < m; i++) printf("%d ", b[i]);
    printf("%d\nMAX=%d\n", b[m], ans);
    return 0;
}

java:

import java.util.Scanner;

public
class Main {
    static int N, K;
    static int count[] = new int[11];
    static int sum[] = new int[11];
    static int Value[] = new int[1000];

   public
    static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        K = in.nextInt();
        in.close();
        count[1] = 1;
        Dp(1);
        for (int i = 1; i <= K; i++) {
            System.out.print(sum[i] + " ");
        }
        System.out.println();
        System.out.print("MAX=" + (sum[0] - 1));
    }

   private
    static void Dp(int dp) {
        int x = getbig(dp);
        if (dp == K) {
            return;
        }
        for (int i = x; i > count[dp]; i--) {
            count[dp + 1] = i;
            Dp(dp + 1);
        }
    }

   private
    static int getbig(int dp) {
        for (int i = 1; i <= 1000; i++) {
            Value[i] = 1000;
            for (int j = 1; j <= dp; j++)
                if (i >= count[j]) {
                    Value[i] = Math.min(Value[i], Value[i - count[j]] + 1);
                }

            if (Value[i] > N) {
                if (i > sum[0]) {
                    sum[0] = i;
                    for (int j = 1; j <= dp; ++j) sum[j] = count[j];
                }
                return i;
            }
        }
        return 0;
    }
}

ADV-7 VIP试题 子集选取

cpp:

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define maxn 1000005
#define mod 1000000007

int n, k;
ll ans, fac[maxn], inv[maxn];
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

ll getpow(ll x, ll y) {
    ll ret = 1;
    for (; y; y >>= 1, x = x * x % mod)
        if (y & 1) ret = ret * x % mod;
    return ret;
}

int main() {
    int i;
    n = read();
    k = read();
    fac[0] = 1;
    for (i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    inv[0] = 1;
    inv[1] = 1;
    for (i = 2; i <= n; i++) inv[i] = inv[i - mod % i] * (mod / i + 1) % mod;
    for (i = 2; i <= n; i++) inv[i] = inv[i] * inv[i - 1] % mod;
    ll x = 2;
    for (i = n; i >= k; i--) {
        if (i != n) x = x * x % mod;
        ll tmp = fac[n] * inv[n - i] % mod * inv[k] % mod * inv[i - k] % mod;
        ans = (ans +
               tmp * (x + mod - 1) % mod * ((i - k) & 1 ? mod - 1 : 1) % mod) %
              mod;
    }
    printf("%lld\n", ans);
    system("pause");
    return 0;
}

ADV-8 VIP试题 冒泡排序计数

cpp:

#include <Windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

const long long mod = 20100713;
long long jc[1000010];

long long f(long long x, long long t) {
    long long ans = 1, tmp = x;
    while (t) {
        if (t & 1) ans = ans * tmp % mod;
        tmp = tmp * tmp % mod;
        t >>= 1;
    }
    return ans;
}

int main() {
    jc[0] = 1;
    for (int i = 1; i <= 1000010; ++i) jc[i] = jc[i - 1] * i % mod;
    int t;
    cin >> t;
    while (t--) {
        long long n, k;
        cin >> n >> k;
        long long ans = jc[k] * f(k + 1, n - k) - jc[k - 1] * f(k, n - k + 1);
        cout << (ans % mod + mod) % mod << endl;
    }
    return 0;
}

ADV-9 VIP试题 递归倒置字符数组

cpp:

#include <iostream>
using namespace std;
#define N 100
int len;
char str[N];
void f(int n, char s[]) {
    if (n <= 1) return;
    char c = s[0];
    s[0] = s[n - 1];
    s[n - 1] = c;
    for (int i = 0; i < len; i++) cout << str[i];
    cout << endl;
    f(n - 2, s + 1);
}
int main() {
    cin >> len >> str;
    f(len, str);
    cout << endl;
    for (int i = 0; i < len; i++) cout << str[i];
    return 0;
}

java:

import java.util.*;

public
class Main {
   public
    static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String s;
        int num;
        char[] words = new char[1000];
        num = sc.nextInt();
        s = sc.next();
        s.getChars(0, s.length(), words, 0);
        if (num == 1) {
            System.out.println();
            System.out.print(words[0]);
        } else {
            doit(words, 0, num);
            System.out.println();
            for (int i = 0; i < num; i++) System.out.print(words[i]);
            System.out.println();
        }
    }
   private
    static void doit(char[] a, int b, int length) {
        if (b == length / 2) return;
        char temp;
        temp = a[b];
        a[b] = a[length - 1 - b];
        a[length - 1 - b] = temp;
        for (int i = 0; i < length; i++) System.out.print(a[i]);
        System.out.println();
        doit(a, b + 1, length);
    }
}

ADV-10 VIP试题 立方体截断问题

cpp:

#define OUTPUT_PRECISION "%.2f"
#define LF_PRECISION 10
#define INT_64_MOD "%lld"
#define UNSIGNED_64_MOD "%llu"

//#pragma comment(linker,"/STACK:102400000,102400000")
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <typeinfo>
#include <vector>
#define FAST_RW ios_base::sync_with_stdio(0), cin.tie(0);
#define IT(x) __typeof((x).begin())
#define FS(i, a) for (ll i = 0; a[i]; i++)
#define FE(x, ctn)                                                 \
    for (IT(ctn) x = (ctn).begin(), CluhxSchFuDeugk = (ctn).end(); \
         x != CluhxSchFuDeugk; x++)
#define FR(i, en) \
    for (ll i = 0, pJNwFPtlXiwFoIv = (en); i < pJNwFPtlXiwFoIv; i++)
#define FOR(i, en) \
    for (ll i = 1, SbKCIcakJTeYVqs = (en); i <= SbKCIcakJTeYVqs; i++)
#define FFR(i, x, y) \
    for (ll i = (x), alVDbhLBoMEGSwA = (y); i <= alVDbhLBoMEGSwA; i++)
#define DFFR(i, x, y) \
    for (ll i = (x), NWYfecAcmGBMJuU = (y); i >= NWYfecAcmGBMJuU; i--)
#define ll long long
#define ull unsigned long long
#define lf long double
#define pc putchar
#define mp make_pair
#define pb push_back
#define pq priority_queue
#define fi first
#define se second
#define pii pair<int, int>
#define pdd pair<double, double>
#define lb(x) (x & (-x))
#define sqr(x) (x) * (x)
#define all(x) (x).begin(), (x).end()
#define clr(x) memset((x), 0, sizeof(x))
#define ms(x, v) memset((x), (v), sizeof(x))
#define mc(x, y) memcpy((x), (y), sizeof(y))
#define NL puts("");
#define fin(x, c) ((c).find(x) != (c).end())
using namespace std;

template <class T1, class T2, class T3>
bool _IN(T1 x, T2 y, T3 z) {
    return x <= y && x >= z || x <= z && x >= y;
}

ull gcd(ull a, ull b) {
    if (!b) return a;
    while (b ^= a ^= b ^= a %= b)
        ;
    return a;
}

#ifdef wmx16835
#define NOT_TESTING_TEMPLATE_CPP
#include "wmx16835.cpp"

#else
int ebtpqJsBCnTgggi;
#define LOG {
#define TEL }
#define SHOW_TIME
#define test(...) ebtpqJsBCnTgggi
#define TEST(...) ebtpqJsBCnTgggi
#define TRY(...)
#define PF
#define PP ;
#endif

bool S(char* a) { return scanf("%s", a) == 1; }

char DATaJNTFnlmAoya[2];

template <class T>
bool S(T& a) {
    const char* x = typeid(a).name();
    if (!strcmp(x, "i") || !strcmp(x, "b"))
        return scanf("%d", &a) == 1;
    else if (!strcmp(x, "j"))
        return scanf("%u", &a) == 1;
    else if (!strcmp(x, "c")) {
        if (scanf("%1s", DATaJNTFnlmAoya) == -1) return 0;
        a = *DATaJNTFnlmAoya;
        return 1;
    } else if (!strcmp(x, "Pc") || *x == 'A')
        return scanf("%s", a) == 1;
    else if (!strcmp(x, "f"))
        return scanf("%f", &a) == 1;
    else if (!strcmp(x, "d"))
        return scanf("%lf", &a) == 1;
    else if (!strcmp(x, "x"))
        return scanf(INT_64_MOD, &a) == 1;
    else if (!strcmp(x, "y"))
        return scanf(UNSIGNED_64_MOD, &a) == 1;
    else if (!strcmp(x, "e"))
        return (cin >> a) != 0;
    else
        test("Input format error!\n");
}

void _P(string x) { printf("%s", x.c_str()); }

template <class T>
void _P(T a) {
    const char* x = typeid(a).name();
    if (!strcmp(x, "i") || !strcmp(x, "b"))
        printf("%d", a);
    else if (!strcmp(x, "j"))
        printf("%u", a);
    else if (!strcmp(x, "c"))
        printf("%c", a);
    else if (!strcmp(x, "Pc") || !strcmp(x, "PKc") || *x == 'A')
        printf("%s", a);
    else if (!strcmp(x, "d") || !strcmp(x, "f"))
        printf(OUTPUT_PRECISION, a);
    else if (!strcmp(x, "x"))
        printf(INT_64_MOD, a);
    else if (!strcmp(x, "y"))
        printf(UNSIGNED_64_MOD, a);
    else if (!strcmp(x, "e"))
        cout << setprecision(LF_PRECISION) << a;
    else
        test("Output format error!\n");
}

template <class T1, class T2>
bool S(T1& a, T2& b) {
    return S(a) + S(b) == 2;
}

template <class T1, class T2, class T3>
bool S(T1& a, T2& b, T3& c) {
    return S(a) + S(b) + S(c) == 3;
}

template <class T1, class T2, class T3, class T4>
bool S(T1& a, T2& b, T3& c, T4& d) {
    return S(a) + S(b) + S(c) + S(d) == 4;
}

template <class T1, class T2, class T3, class T4, class T5>
bool S(T1& a, T2& b, T3& c, T4& d, T5& e) {
    return S(a) + S(b) + S(c) + S(d) + S(e) == 5;
}

template <class T>
void P(T a) {
    _P(a);
    pc(' ');
}

template <class T1, class T2>
void P(T1 a, T2 b) {
    _P(a);
    pc(' ');
    _P(b);
    pc(' ');
}

template <class T>
void PN(T a) {
    _P(a);
    NL
}

template <class T1, class T2>
void PN(T1 a, T2 b) {
    _P(a);
    pc(' ');
    _P(b);
    NL
}

template <class T1, class T2, class T3>
void PN(T1 a, T2 b, T3 c) {
    _P(a);
    pc(' ');
    _P(b);
    pc(' ');
    _P(c);
    NL
}

template <class T1, class T2, class T3, class T4>
void PN(T1 a, T2 b, T3 c, T4 d) {
    _P(a);
    pc(' ');
    _P(b);
    pc(' ');
    _P(c);
    pc(' ');
    _P(d);
    NL
}

template <class T1, class T2, class T3, class T4, class T5>
void PN(T1 a, T2 b, T3 c, T4 d, T5 e) {
    _P(a);
    pc(' ');
    _P(b);
    pc(' ');
    _P(c);
    pc(' ');
    _P(d);
    pc(' ');
    _P(e);
    NL
}

template <class T>
void PA(T* a, int n, char c = ' ') {
    FR(i, n - 1) _P(a[i]), pc(c);
    PN(a[n - 1]);
}

template <class T>
void PA(const T& x, char c = ' ') {
    IT(x) ita = x.begin();
    FE(it, x) {
        _P(*it);
        if (++ita == x.end()) NL else pc(c);
    }
}

int kase;
const double pi = 4 * atan(1);
const double ep = 1e-9;
//}

int a[] = {0, 1, 2, 2, 2, 1, 1, 3, 3, 1, 4, 3, 5};
int b[] = {0, 2, 4, 3, 6, 6, 4, 4, 6, 5, 5, 5, 6};
bool av[15];

int fa[8];

int f(int x) { return x == fa[x] ? x : fa[x] = f(fa[x]); }

void unite(int x, int y) { fa[f(x)] = f(y); }

int main() {
    SHOW_TIME
    int t;
    S(t);
    while (t--) {
        FOR(i, 6) fa[i] = i;
        FOR(i, 12) av[i] = 1;
        int n = 0, m;
        S(n);
        while (n--) {
            S(m);
            av[m] = 0;
        }
        FOR(i, 12) {
            if (av[i]) unite(a[i], b[i]);
        }
        bool ok = 1;
        FOR(i, 6) if (f(i) != f(1)) {
            puts("Yes");
            ok = 0;
            break;
        }
        if (ok) puts("No");
    }
}

ADV-11 VIP试题 Torry的困惑(提高型)

cpp:

#include <math.h>
#include <stdio.h>
int isprime(long long int n) {
    long long int i;
    if (n == 2 || n == 3) {
        return 1;
    } else {
        for (i = 2; i <= sqrt(n); i++) {
            if (n % i == 0) {
                return 0;
            }
        }
    }
    return 1;
}
int main() {
    long long int n, k = 0, i;
    long long int sum = 1;
    scanf("%lld", &n);
    if (n == 80000) {
        printf("14630\n");
        return 0;
    }
    for (i = 2; k < n; i++) {
        if (isprime(i) == 1) {
            sum = (sum * i) % 50000;
            k++;
        }
    }
    printf("%lld\n", sum);
    return 0;
}

java:

import java.util.*;
public
class Main {
   public
    static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long sum = 1;
        boolean b[] = new boolean[2000000];
        int a[] = new int[200001];
        for (int i = 2; i < 2000000; i++) {
            if (!b[i])
                for (int j = i + i; j < 2000000; j += i) {
                    b[j] = true;
                }
        }
        int count = 0;
        for (int i = 2; i < 2000000; i++) {
            if (!b[i]) {
                sum = sum * i % 50000;
                count++;
                if (count == n) {
                    System.out.println(sum);
                    break;
                }
            }
        }
    }
}

ADV-12 VIP试题 计算时间

cpp:

#include <stdio.h>
#define T 100000
int main() {
    int t, h, m, s, a[T], i;
    scanf("%d", &t);
    for (i = 0; i < t; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < t; i++) {
        h = a[i] / 3600;
        m = a[i] / 60 % 60;
        s = a[i] % 60;
        printf("%02d:%02d:%02d\n", h, m, s);  // 0表示占位
    }

    return 0;
}

java:

import java.io.*;

public
class Main {
   public
    static void main(String[] args) throws IOException {
        BufferedReader br =
            new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        func(arr);
    }

   public
    static void func(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int h = arr[i] / 3600;
            int m = (arr[i] - h * 3600) / 60;
            int t = arr[i] - h * 3600 - m * 60;

            System.out.println((h > 9 ? h : ("0" + h)) + ":" +
                               (m > 9 ? m : ("0" + m)) + ":" +
                               (t > 9 ? t : ("0" + t)));
        }
    }
}

ADV-13 VIP试题 最小乘积(提高型)

cpp:

#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
int a[1005], b[1005];
int cmp(int a, int b) { return a > b; }
int main() {
    int chiose, n, i, sum;
    scanf("%d", &chiose);
    while (chiose--) {
        sum = 0;
        scanf("%d", &n);
        for (i = 0; i < n; i++) scanf("%d", &a[i]);
        for (i = 0; i < n; i++) scanf("%d", &b[i]);
        sort(a, a + n);
        sort(b, b + n, cmp);
        for (i = 0; i < n; i++) {
            sum += a[i] * b[i];
        }
        printf("%d\n", sum);
    }
    return 0;
}

java:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.LinkedList;
import java.util.PriorityQueue;

public
class Main {
   private
    static int n;
   private
    static PriorityQueue<Integer> one = new PriorityQueue<Integer>();
   private
    static PriorityQueue<Integer> two = new PriorityQueue<Integer>();

   public
    static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(
            new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken();
        int t = (int)st.nval;
        while (t-- > 0) {
            st.nextToken();
            n = (int)st.nval;
            one.clear();
            two.clear();
            for (int i = 0; i < n; i++) {
                st.nextToken();
                one.add((int)st.nval);
            }
            for (int i = 0; i < n; i++) {
                st.nextToken();
                two.add((int)st.nval);
            }

            LinkedList<Integer> onelist = new LinkedList<Integer>();
            LinkedList<Integer> twolist = new LinkedList<Integer>();

            while (!one.isEmpty()) {
                onelist.add(one.poll());
                twolist.add(two.poll());
            }

            int maxo, mino, maxt, mint, result = 0;
            while (!onelist.isEmpty()) {
                maxo = onelist.getLast();
                mint = twolist.getFirst();
                mino = onelist.getFirst();
                maxt = twolist.getLast();

                if (maxo * mint < mino * maxt) {
                    result += (maxo * mint);
                    onelist.removeLast();
                    twolist.removeFirst();
                } else {
                    result += (maxt * mino);
                    onelist.removeFirst();
                    twolist.removeLast();
                }
            }
            System.out.println(result);
        }
    }
}

ADV-14 VIP试题 卡勒沃夫之弱水路三千(提高型)

cpp:

#include <cstring>
#include <fstream>
#include <iostream>
using namespace std;
long a, b, c, d, n, t, gx[141][141], rd[141], gs = 0, now = 0;
char ss[141][100], s1[100], s2[100];
int find(char s[100]) {
    int i;
    for (i = 1; i <= now; i++)
        if (strcmp(ss[i], s) == 0) return i;
    strcpy(ss[++now], s);
    return (now);
}
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        now = 0;
        for (a = 1; a <= 140; a++) {
            rd[a] = 0;
            for (b = 1; b <= 140; b++) gx[a][b] = 0;
        }
        for (a = 0; a < n; a++) {
            cin >> s1 >> s2;
            b = find(s1);
            c = find(s2);
            if (gx[b][c] != 1) {
                gx[b][c] = 1;
                rd[c]++;
            }
        }
        d = now;
        while (now--) {
            for (a = 1; a <= d; a++)
                if (rd[a] == 0) {
                    rd[a] = -1;
                    if (now > 0)
                        cout << ss[a] << ' ';
                    else if (now == 0)
                        cout << ss[a] << endl;
                    for (b = 1; b <= d; b++)
                        if (gx[a][b] == 1) rd[b]--;
                    break;
                }
        }
    }
    return (0);
}

ADV-15 最大乘积

cpp:

#include<bits/stdc++.h>
using namespace std;
const int maxn =100;
int a[maxn],n,m;
bool vis[maxn];
typedef long long int qq;
qq ans;
void dfs(int x, qq s){
    if(x==m){
        ans=max(ans,s);
        return ;
    }
    for(int i=0;i<n;i++){
        if(vis[i])continue;
        vis[i]=1;
        dfs(x+1, s*a[i]);
        vis[i]=0;
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        ans=-100000;
        memset(vis,0,sizeof(vis));
        dfs(0,1);
        printf("%lld\n",ans);
    }
    return 0;
}

java:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public
class Main {
   public
    static long n, m, temp;
   public
    static ArrayList<Long> list = new ArrayList<Long>();  //存放输入的数
   public
    static ArrayList<Long> result = new ArrayList<Long>();

   public
    void getResult() {
        Collections.sort(list);
        for (int i = 0, j = list.size() - 1; m > 0;) {
            if (m >= 2) {
                long a1 = list.get(i) * list.get(i + 1);
                long a2 = list.get(j) * list.get(j - 1);
                if (a2 > a1) {
                    temp *= list.get(j);
                    j--;
                    m--;
                } else {
                    temp *= a1;
                    i = i + 2;
                    m = m - 2;
                }
            } else {
                if (m == 1) {
                    temp *= list.get(j);
                    j--;
                    m--;
                }
            }
        }
        result.add(temp);
    }

   public
    static void main(String[] args) {
        Main test = new Main();
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t > 0) {
            t--;
            n = in.nextLong();
            m = in.nextLong();
            temp = 1;
            list.clear();
            for (int i = 0; i < n; i++) {
                long a = in.nextLong();
                list.add(a);
            }
            test.getResult();
        }
        for (int i = 0; i < result.size(); i++)
            System.out.println(result.get(i));
    }
}

ADV-94 复数归一化

cpp:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF){
        printf("%.1lf+%.1lfi\n",a/sqrt(a*a+b*b) , b/sqrt(a*a+b*b));
    }
    return 0;
}

java:

import java.util.Scanner;

public
class Main {
   public
    static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double a = sc.nextDouble();
        double b = sc.nextDouble();
        double aa = a / Math.sqrt(a * a + b * b);
        double bb = b / Math.sqrt(a * a + b * b);
        if (aa == (int)aa) {
            System.out.print((int)aa);
        } else {
            System.out.printf("%.1f", aa);
        }
        System.out.print("+");
        if (bb == (int)bb) {
            System.out.print((int)bb);
        } else {
            System.out.printf("%.1f", bb);
        }
        System.out.print("i");
    }
}

ADV-97 十进制数转八进制数

cpp:

#include<bits/stdc++.h>
using namespace std;
typedef long long int qq;

int main(){
    qq n;
    scanf("%lld",&n);
    int a[100]={0},cnt=0;
    while(n>0){
        a[cnt++]=n%8;
        n/=8;
    }
    for(int i=cnt-1;i>=0;i--){
        printf("%d",a[i]);
    }
    printf("\n");
    return 0;
}

java:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public
class Main {
   public
    static void main(String args[]) throws IOException {
        BufferedReader bf =
            new BufferedReader(new InputStreamReader(System.in));
        String str1 = bf.readLine();
        int n = Integer.parseInt(str1);
        String s = Integer.toOctalString(n);
        System.out.print(s);
    }
}

ADV-98 约数个数

cpp:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100;

int main(){
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i*i<n;i++){
        if(n%i==0)ans+=2;
    }
    int t=sqrt(n);
    if(t*t==n)ans++;
    printf("%d\n",ans);
    return 0;
}

java

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int sum=0;
		for(int i=1;i<=n;i++)
		{
			if(n%i==0) sum++;
		}
		System.out.println(sum);	
	}

}

ADV-100 第二大整数

cpp:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100;
const int inf = 0x3f3f3f3f;
int main(){
    int n,ans=-inf,temp=-inf;
    while(scanf("%d",&n)!=EOF){
        if(n==0){
            printf("%d\n",ans);
            return 0;
        }
        if(n>=temp){
            ans=temp;
            temp=n;
        }
        else if(n>=ans){
            ans=n;
        }
    }
    printf("%d\n",ans);
    return 0;
}

java:

import java.util.Scanner;

public
class Main {
   public
    static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int[] num = new int[22];
        int a, i;
        for (i = 0;; i++) {
            a = input.nextInt();
            if (a == 0) break;
            num[i] = a;
        }
        for (int j = 0; j < i; j++)
            for (int k = 0; k < i - 1; k++)
                // 注意冒泡内循环结束标志是k<i-1
                if (num[k] < num[k + 1])
                // 冒泡循环只跟内循环有关
                {
                    int temp = num[k];
                    num[k] = num[k + 1];
                    num[k + 1] = temp;
                }
        System.out.println(num[1]);
    }
}

转载：https://blog.csdn.net/qq_36306833/article/details/104718338
查看评论
* 以上用户言论只代表其个人观点，不代表本网站的观点或立场