欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客多校第九场 Groundhog and 2-Power Representation(大整数,java)

程序员文章站 2022-07-15 10:34:53
...

牛客多校第九场 Groundhog and 2-Power Representation(大整数,java)
思路:
直接java模拟递归写。
不过python貌似可以用语法直接写。



import java.util.*;
import java.math.*;
import java.io.*;
import java.lang.*;

public class Main {
    public static BigInteger qpow(BigInteger n) {
        BigInteger res = BigInteger.ONE;
        BigInteger zero = BigInteger.ZERO;
        BigInteger one = BigInteger.ONE;
        BigInteger two = one.add(one);
        BigInteger x = two;
        while(n != zero) {
            if(n.mod(two).equals(one)) {
                res = res.multiply(x);
            }
            n = n.divide(two);
            x = x.multiply(x);
        }
        return res;
    }

    public static BigInteger cal(int l,int r,String s) {
        BigInteger zero = BigInteger.ZERO;
        BigInteger one = BigInteger.ONE;
        BigInteger two = one.add(one);

        if(s.charAt(l) == '(' && s.charAt(r) == ')') {
            l++;
            r--;
        }
        if(l == r) {
            if(s.charAt(l) == '0') return zero;
            else if(s.charAt(l) == '2') return two;
        }

        int pre = l;
        BigInteger res = BigInteger.ZERO;
        int cnt = 0;
        for(int i = l;i <= r;i++) {
            if(s.charAt(i) == '(') cnt--;
            else if(s.charAt(i) == ')') cnt++;
            else if(s.charAt(i) == '+' && cnt == 0) {
                BigInteger num = cal(pre,i - 1,s);
//                System.out.println(num + " " + pre + " " + (i - 1));
                res = res.add(num);
                pre = i + 1;
            }
        }
        if(pre < r) pre++;
        BigInteger num = cal(pre,r,s);
        if(r - pre + 1 != 1) num = qpow(num);
        res = res.add(num);

        return res;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String s;
        s = cin.next();
        int len = s.length();
        BigInteger ans = cal(0,len - 1,s);
        System.out.println(ans);
    }
}



//2(2+2(0))

上一篇: ibatis的简单运用

下一篇: 整数反转