bzoj 3287: Mato的刷屏计划 高精水题 && bzoj AC150

3287: Mato的刷屏计划

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 124  Solved: 43
[Submit][Status]

Description

Mato同学喜欢上QQ,但是有少数傻逼总是问他一些弱智问题。Mato感到很反感,想要鄙视一下他们。他决定在QQ上刷屏,也就是发出一大堆字符。Mato的键盘上有4个键:A、B、C、D。按A就会输入一个字符,按B会把所有字符选中,按C会把选中的字符放入剪贴板,按D会插入剪贴板的内容。他的时间很宝贵,只能按n个键,你能告诉他最多能够输入多少字符吗?

Input

一个正整数n

Output

一个正整数,表示Mato所能输入的最多字符数。

Sample Input

7

Sample Output

9

HINT

Hint

n <= 1000000

样例1解释:Mato可以按AAABCDD,就可以输入9个字符。

注意此题中的粘贴与现实生活中有一定差别,不会覆盖选中的部分。

  java水过,此题膜拜网上用FFT优化高精乘DP的大牛。

import java.io.IOException;
import java.util.Scanner;
import java.math.BigInteger;
public class Main {

    public static void main(String[] args) throws IOException
    {
        // TODO Auto-generated method stub
        int arr[]={0,1,2,3,4,5,6,9,12,16,20,27,36,48,64,81,108,144,192,256,324,432,576,768,1024,1296,1728,2304,3072,4096};
        int n;
        Scanner scanf= new Scanner(System.in);
        n=scanf.nextInt();
        if (n<25)
        {
            System.out.println(arr[n]);
            scanf.close();
            System.exit(0);
        }else
        {
            int x=n%5;
            x+=15;
            BigInteger ans=new BigInteger("0");
            BigInteger four = new BigInteger("4");
            ans=BigInteger.valueOf(arr[x]);
            four=four.pow((n-x)/5);
            ans=ans.multiply(four);
            System.out.println(ans);
        }
        scanf.close();
    }
}
时间: 11-15

bzoj 3287: Mato的刷屏计划 高精水题 && bzoj AC150的相关文章

[bzoj3287] Mato的刷屏计划

第一眼以为是傻逼斜率优化>_< f[i]表示按i次最多可输出字符数..f[i]=max{ f[i-1]+1,(i-j-1)*f[j] },j<i-2 结果n在100+的时候就喜闻乐见地爆了longlong 根据网上题解可得(T_T)..这题大概是要FFT优化?(跟着ccz大爷刷题果然高风险TAT 然而题解表示,这题求出f的前几项后,令x=n%5+15,最终答案f[n]=f[x]*4^((n-x)/5).......... 我死活没看出来这是为啥... 我显然是连FFT都不会的傻逼..只好

BZOJ 1432: [ZJOI2009]Function(新生必做的水题)

1432: [ZJOI2009]Function Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 1205  Solved: 895[Submit][Status][Discuss] Description Input 一行两个整数n; k. Output 一行一个整数,表示n 个函数第k 层最少能由多少段组成. Sample Input 1 1 Sample Output 1 HINT 对于100% 的数据满足1 ≤ k ≤ n ≤ 100. Sou

HDOJ1002-A + B Problem II(高精加)

Problem Description I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B. Input The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines fol

各种高精——一入高精深似海,从此AC是路人.

1.高精简单操作 题面 https://www.luogu.org/problemnew/show/P2152 代码 https://www.luogu.org/record/show?rid=5655289 高精,GCD,stein. 即 gcd(a,b)=2*gcd(a/2,b/2); gcd(a,b)=gcd(a/2,b); gcd(a,b)=gcd(a,b/2); 再用辗转相减套个高精就好 2.高精除int 题面 https://www.luogu.org/problemnew/show

高精专题——一入高精深似海,从此AC是路人.

1.高精简单操作 题面 代码 高精,GCD,stein. 即 gcd(a,b)=2*gcd(a/2,b/2); gcd(a,b)=gcd(a/2,b); gcd(a,b)=gcd(a,b/2); 再用辗转相减套个高精就好 2.高精除int 题面 代码 高精,katalan,组合数学. 即 暴力打表观察/分析一下,易得答案为katalan数 递推显然是要T的,化简一波就好了 再套个高精,支持除非高精就行 3.高精乘高精 题面 代码 高精,DP. DP不难,高精乘高精倒是DEBUG了一晚上... 4

[BZOJ 2729][HNOI2012]排队(排列组合+高精)

Description 某中学有 n 名男同学,m 名女同学和两名老师要排队参加体检.他们排成一条直线,并且任意两名女同学不能相邻,两名老师也不能相邻,那么一共有多少种排法呢?(注意:任意两个人都是不同的) Solution 好像必须写压位高精的QAQ 先排n名男生,插空,讨论两名老师插在两个不同的空里的情况和先排在一起再在中间插一名女生的情况 #include<iostream> #include<cstdio> #include<cstring> #include&

bzoj 1754: [Usaco2005 qua]Bull Math【高精乘法】

高精乘法板子 然而WA了两次也是没救了 #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=105; int la,lb,lc,a[N],b[N],c[N],tot; char ch[N]; int main() { scanf("%s",ch+1); la=strlen(ch+1); for(int i=1;i<=la;i

BZOJ_1002_[FJOI2007]_轮状病毒(递推+高精)

描述 http://www.lydsy.com/JudgeOnline/problem.php?id=1002 )*&*(^&*^&*^**()*) 分析 题目是求一种特殊的图的生成树的个数,但是貌似有更一般的算法,等明天再看吧... 只搞懂了打表找规律,然后题推的解法. 随便写个暴力打个表(其实我并不会写,明天再写吧今天好累),找一找规律. 1~14的答案如下 1 5 16 45 121 320 841 2205 5776 15125 39601 103680 271441 71

高精-----各种模板

高精加法 代码 #include<string> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; char a[501],b[501]; int x[501],y[501],z[50000]; int main() { cin>>a; cin>