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

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

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

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>

模板——高精系列

存放一下高精的模板 高精加: #include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> using namespace std; int a[1001],b[1001],c[1001],lena,lenb; char a1[1001],b1[1001]; int main(){ gets(a1); gets(b1); lena=strlen(a1); lenb=strlen

c++普通高精加

//作为一名蒟蒻,还请诸位不要吐槽. //第一次打c++高精加,内心有点小激动. //为codevs3116 高精度练习之加法 //程序太简单,就不打注释了. #include<cstdio>#include<cstring>int main(){char s1[600],s2[600];int a1[600],a2[600],a3[600]={0},len1,len2,i;scanf("%s",s1);scanf("%s",s2);len1

高精阶乘

求n!.当n很大的时候,会超出整数的范围. 这里用数组来进行高精阶乘.a[1]是个位,a[2]是十位......依次类推.每次要乘一个数的时候,就从个位(即a[1])开始乘这个数,>10的时候要%10再进位. 1 #include<cstdio> 2 #include<cstring> 3 const int N=100000; 4 5 int a[N]; 6 int i, j, n; 7 int t, pos/*位数*/, carry/*进位*/; 8 9 int main

[贪心][高精]P1080 国王游戏(整合)

题目描述 恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏.首先,他让每个大臣在左.右手上面分别写下一个整数,国王自己也在左.右手上各写一个整数.然后,让这 n 位大臣排成一排,国王站在队伍的最前面.排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果. 国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少.注意,国