头像

L.L.


访客:5488

离线:19天前



L.L.
1个月前

来源:第九届蓝桥杯省赛C++B组

算法标签:贪心

题目描述:

给定 N 个整数 A1,A2,…AN。

请你从中选出 K 个数,使其乘积最大。

请你求出最大的乘积,由于乘积可能超出整型范围,你只需输出乘积除以 1000000009 的余数。

注意,如果 X<0, 我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009 的余数,即:0−((0−x)%1000000009)

输入格式

第一行包含两个整数 N 和 K。

以下 N 行每行一个整数 Ai。

输出格式

输出一个整数,表示答案。

数据范围

1≤K≤N≤1E5,
−1E5≤Ai≤1E5

输入样例1:

5 3
-100000
-10000
2
100000
10000

输出样例1:

999100009

输入样例2:

5 3
-100000
-100000
-2
-100000
-100000

输出样例2:

-999999829

思路

n 一共有n个数
k 一共选k个数
我们要在n个数当中选择k个数使得乘积最大

if n== k 所有的数字都要被选择,那么答案就是n个数字相乘
if n<k 不合法
if n>k 
if k%2 == 0
    如果负数为偶数个,负负得正,答案必定是正数
    如果负数为奇数个,则总有落单的负数,那我们只选择偶数个最大的负数,答案必定是正数
if k%2 == 1
    如果所有数字都为负数,那么答案肯定就是负数
    如果起码有一个正数,那我们把单独的整数拿出来,k - -,此时k转换为了奇数,回归到前面的式子进行解决


我们可以发现,除了k是 奇数 且 所有数字都为负数 的情况是负数,其他情况下都可以转换为正数

在负数特殊情况下,我们要确保整个数尽可能小,得到的答案就相对较大

其他情况下,我们从两边找最大值a[l]*a[l+1],a[r]*a[r-1]进行乘积。

代码

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

const int N=1E5+10,mod = 1000000009 ;
typedef long long LL;
int a[N];
LL res=1;

int main()
{
    int n,k;
    cin>>n>>k;

    for(int i=0;i<n;i++)cin>>a[i];

    sort(a,a+n);

    int sign=1;
    if(n==k){for(int i=0;i<n;i++)res*=a[i];}//n==k时
    else 
    {
        int l=0,r=n-1;
        if(k%2)//奇数情况
        {
            res=a[r--],k--;
            if(res<0)sign=-1;//唯一的全负状况 取最小
        }
        while(k)//转化为偶数状态处理
        {
            LL ll = (LL)a[l]*a[l+1],rr=(LL)a[r]*a[r-1];
            if(ll*sign>rr*sign){res=ll%mod*res%mod;l+=2;}//左右两边哪个绝对值大就选哪个 全负数状态相反
            else {res=rr%mod*res%mod;r-=2;}
            k-=2;
        }
    }

    cout<<res;
    return 0;
}



L.L.
1个月前

标题:黄金连分数

黄金分割数0.61803… 是个无理数,这个常数十分重要,在许多工程问题中会出现。有时需要把这个数字求得很精确。
对于某些精密工程,常数的精度很重要。也许你听说过哈勃太空望远镜,它首次升空后就发现了一处人工加工错误,对那样一个庞然大物,其实只是镜面加工时有比头发丝还细许多倍的一处错误而已,却使它成了“近视眼”!!
言归正传,我们如何求得黄金分割数的尽可能精确的值呢?有许多方法。
比较简单的一种是用连分数:
[HTML_REMOVED]
1
黄金数 = ---------------------
1
1 + -----------------
1
1 + -------------
1
1 + ---------
1 + …
[HTML_REMOVED]
这个连分数计算的“层数”越多,它的值越接近黄金分割数。
请你利用这一特性,求出黄金分割数的足够精确值,要求四舍五入到小数点后100位。
小数点后3位的值为:0.618
小数点后4位的值为:0.6180
小数点后5位的值为:0.61803
小数点后7位的值为:0.6180340
(注意尾部的0,不能忽略)
你的任务是:写出精确到小数点后100位精度的黄金分割值。
注意:尾数的四舍五入! 尾数是0也要保留!
显然答案是一个小数,其小数点后有100位数字,请通过浏览器直接提交该数字。
注意:不要提交解答过程,或其它辅助说明类的内容。

代码:

#include<iostream>
using namespace std;

typedef long long LL;

void div(LL a,LL b,int end,int begin)//模拟手工除法
{
    if(begin>end)return ;
    int tmpans=a/b;
    cout<<tmpans;
    div((a%b)*10,b,end,begin+1);
}

int main()
{
    unsigned long long f[500]={0,1};

    for (int i = 2; i<100; i++)f[i] = f[i - 1] + f[i - 2];

    div(f[48],f[49],100,0);

    return 0;


}

答案

0.6180339887498948481971959525508621220510663574518538453723187601229582821971784348083863296133320592

疑问

不是两个斐波拉契数字相除,那应该越大越好呀,为什么指定fib[38]/dib[39]




L.L.
1个月前

没有人我就来水一个

来源:第七届蓝桥杯省赛C++B组

算法标签:数论,最大公约数,辗转相减法

题目描述:

X星球的某个大奖赛设了 M 级奖励。

每个级别的奖金是一个正整数。

并且,相邻的两个级别间的比例是个固定值。

也就是说:所有级别的奖金数构成了一个等比数列。

比如:16,24,36,54,其等比值为:3/2。

现在,我们随机调查了一些获奖者的奖金数。

请你据此推算可能的最大的等比值。

输入格式

第一行为数字 N ,表示接下的一行包含 N 个正整数。

第二行 N 个正整数 Xi,用空格分开,每个整数表示调查到的某人的奖金数额。

输出格式

一个形如 A/B 的分数,要求 A、B 互质,表示可能的最大比例系数。

数据范围

0<N<100
0<Xi<1012
数据保证一定有解。

输入样例1:

3
1250 200 32

输出样例1:

25/4

输入样例2:

4
3125 32 32 200

输出样例2:

5/2

输入样例3:

3
549755813888 524288 2

输出样例3:

4/1

思路

我们要找一个数列的最大的等比值。
这种感觉和等差数列很相似,我们直接往GCD上靠

由于一串数据,排序之后肯定存在等差q

s= s1, s2 , s3 …sq … sn
s= aq^0,aq^1, aq^2 …a^q^k....aq^n

每个位次上都可以转换为[p/q]^w形式,即si=[s/a0,s/ai]^k
存在公比形如[p/q]^k
因为[p/q]^k>0,要使得整体最大则公比系数最大,则求K最大

k的限制条件
[p/q]^w是[p/q]^k的次幂
[p/q]^w=([p/q]^k)^s=[p/q]^k^s
则k是每一个w的约数
k最大就是wi的最大公约数

状如[p/q]^wi
我们现在转向了求每一个wi的最大公约数

[p/q]^k = [p^k/q^k]
我们可以直接求取分子分母
则分别求分子分母指数最大公约数

题目代码

#include<iostream>
#include<algorithm>


using namespace std;

typedef long long LL;

const int N=110;

int n;
LL x[N],a[N],b[N];

LL gcd(LL a,LL b)//辗转相除
{
    return b?gcd(b,a%b):a;
}

LL gcd_sub(LL a,LL b)//辗转相减
{
    if(b>a)swap(a,b);
    if(b==1)return a;
    return gcd_sub(b,a/b);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>x[i];//读入

    sort(x,x+n);

    LL dd=0;
    int cnt =0;
    for(int i=1;i<n;i++)
    {
        if(x[i]!=x[i-1])//去重
        {
            dd =gcd(x[i],x[0]);//最大公约数
            a[cnt] = x[i]/dd;
            b[cnt] = x[0]/dd;
            cnt++;
        }
    }

    LL up = a[0],down = b[0];//up分子 down分母
    for(int i=1;i<cnt;i++)//分开求分子分母的指数最大公约数
    {
        up = gcd_sub(up,a[i]);
        down = gcd_sub(down,b[i]);
    }

    cout<<up<<"/"<<down;

    return 0;
}


活动打卡代码 AcWing 1247. 后缀表达式

L.L.
1个月前
#include<iostream>
#include<algorithm>

using namespace std;

const int N=2E5+10;//因为数据总量实际是M+N+1
int a[N];

int main()
{
    int m,n;
    cin>>n>>m;
    int k = m+n+1;

    for(int i=0;i<k;i++)cin>>a[i];//读入数据
    sort(a,a+k);

    long long res=0;
    if(!m)for(int i=0;i<k;i++)res+=a[i];//如果没有-号
    else 
    {
        res=a[k-1]-a[0];
        for(int i=1;i<k-1;i++)res+=abs(a[i]);
    }

    cout<<res;
    return 0;
}



L.L.
1个月前

来源:第五届蓝桥杯省赛C++A/B组

算法标签:动态规划,DP

注:Y总版本详细解释

题目描述:

X 国王有一个地宫宝库,是 n×m 个格子的矩阵,每个格子放一件宝贝,每个宝贝贴着价值标签。

地宫的入口在左上角,出口在右下角。

小明被带到地宫的入口,国王要求他只能向右或向下行走。

走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。

当小明走到出口时,如果他手中的宝贝恰好是 k 件,则这些宝贝就可以送给小明。

请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这 k 件宝贝。

输入格式

第一行 3 个整数,n,m,k,含义见题目描述。

接下来 n 行,每行有 m 个整数 Ci 用来描述宝库矩阵每个格子的宝贝价值。

输出格式

输出一个整数,表示正好取 k 个宝贝的行动方案数。

该数字可能很大,输出它对 1000000007 取模的结果。

数据范围

1≤n,m≤50,
1≤k≤12,
0≤Ci≤12

输入样例1:

2 2 2
1 2
2 1

输出样例1:

2

输入样例2:

2 3 2
1 2 3
2 1 5

输出样例2:

14

思路

该题是摘花生最长上升子序列的缝合。

注意

2.1E9爆栈
val = (val + f[i-1][j][u][v])%MOD; 加两个数可以,可能加三个数就爆炸了

2.
因为价值C的数据是从0到12,而我们一开始不选择的时候f[i][j][u][v],此时v存在不选择的情况 则我们可以填写比0小的数字-1;
但因为-1无法做数组下标,因为我们直接对所有价值全部加1,就变成了1到13,原有的0就可以作为不选择的下标了。

思路图

在这里插入图片描述

题目代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int MOD=1000000007 ,N=55;

int map[N][N];//地图的值
int dp[N][N][13][14];//DP[A][B][C][D] AB横纵坐标 C数量 D最后一个为D的价值 

int main()
{
    int n,m,k;//n m横纵数量 k K件宝物
    cin>>n>>m>>k;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            {
                cin>>map[i][j];
                map[i][j]++;
            }//读入地图宝物价值,为了方便初始下标判断,全加1

    dp[1][1][1][map[1][1]]=1;//起始点选择 方案数1
    dp[1][1][0][0]=1;//起始点不选 方案数1

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(i==1&&j==1)continue;//如果是起始点 跳过

            for(int u=0;u<13;u++)
                for(int v=0;v<14;v++)
                {
                    int &val = dp[i][j][u][v];//引用 简化

                    val = (val+dp[i-1][j][u][v])%MOD;//左边 不选
                    val = (val+dp[i][j-1][u][v])%MOD;//上边 不选

                    if(u>0&&v==map[i][j])//最终的选择到了最大的价值宝物(因为题目递增),且有选择次数,则累加不同价值的子集
                    //当前的方案数量=上一步的所有价值的方案数量之和
                    {
                        for(int c=0;c<v;c++)//
                        {
                        val = (val+dp[i-1][j][u-1][c])%MOD;//左边
                        val = (val+dp[i][j-1][u-1][c])%MOD;//上边
                        }
                    }
                }
        }
    }

    int res=0;
    for(int i=1;i<=13;i++)res= (res+dp[n][m][k][i])%MOD;//总方案数量等于当前数量下所有价值的数量总和
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 1212. 地宫取宝

L.L.
1个月前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int MOD=1000000007 ,N=55;

int map[N][N];//地图的值
int dp[N][N][13][14];//DP[A][B][C][D] AB横纵坐标 C数量 D最后一个为D的价值 

int main()
{
    int n,m,k;//n m横纵数量 k K件宝物
    cin>>n>>m>>k;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            {
                cin>>map[i][j];
                map[i][j]++;
            }//读入地图宝物价值,为了方便初始下标判断,全加1

    dp[1][1][1][map[1][1]]=1;//起始点选择 方案数1
    dp[1][1][0][0]=1;//起始点不选 方案数1

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(i==1&&j==1)continue;//如果是起始点 跳过

            for(int u=0;u<13;u++)
                for(int v=0;v<14;v++)
                {
                    int &val = dp[i][j][u][v];//引用 简化

                    val = (val+dp[i-1][j][u][v])%MOD;//左边 不选
                    val = (val+dp[i][j-1][u][v])%MOD;//上边 不选

                    if(u>0&&v==map[i][j])//最终的选择到了最大的价值宝物(因为题目递增),且有选择次数,则累加不同价值的子集
                    //当前的方案数量=上一步的所有价值的方案数量之和
                    {
                        for(int c=0;c<v;c++)//
                        {
                        val = (val+dp[i-1][j][u-1][c])%MOD;//左边
                        val = (val+dp[i][j-1][u-1][c])%MOD;//上边
                        }
                    }
                }
        }
    }

    int res=0;
    for(int i=1;i<=13;i++)res= (res+dp[n][m][k][i])%MOD;//总方案数量等于当前数量下所有价值的数量总和
    cout<<res;
    return 0;
}



L.L.
1个月前

题目来源 模板题

算法标签 dfs

题目描述

给定一个整数n,将数字1~n排成一排,将会有很多种排列方法。

现在,请你按照字典序将所有的排列方法输出。

输入格式

共一行,包含一个整数n。

输出格式

按字典序输出所有排列方案,每个方案占一行。

数据范围

1≤n≤7

输入样例:

3

输出样例:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

思路

题目代码

#include<iostream>

using namespace std;

const int N=7;
int path[N];
bool st[N];
int n;

void dfs(int u)
{
    if(u==n){for(int i=0;i<n;i++)cout<<path[i]<<" ";cout<<endl;return;}//选了N个数字之后输出

    for(int i=1;i<=n;i++)
        {
            if(!st[i])//如果数字i没有被选
                {
                    path[u]=i;//选第n个为i
                    st[i]=true;//标记已选
                    dfs(u+1);//进入下一个数字选择
                    st[i]=false;//回溯
                }
        }
}
int main()
{
    cin>>n;
    dfs(0);//从第0个开始选
    return 0;
}



L.L.
1个月前

题目来源 模板题

算法标签 dfs,剪枝

题目描述

n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。


现在给定整数n,请你输出所有的满足条件的棋子摆法。

输入格式

共一行,包含整数n。

输出格式

每个解决方案占n行,每行输出一个长度为n的字符串,用来表示完整的棋盘状态。

其中”.”表示某一个位置的方格状态为空,”Q”表示某一个位置的方格上摆着皇后。

每个方案输出完成后,输出一个空行。

输出方案的顺序任意,只要不重复且没有遗漏即可。

数据范围

1≤n≤9

输入样例:

4

输出样例:

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

思路

1.从全排列的角度入手,每行逐步往下找,因为是逐层所以不用考虑行,每次只考虑列,对角线,反对角线是否占位,满足条件输出即可。

2.从棋子元素角度入手,每个棋子都有选和不选两种情况,如果满足条件则输出。

题目代码

时间复杂度 n^2

全排列角度
逐层

#include<iostream>

using namespace std;

int n;
const int N = 10*2;
char g[N][N];
int col[N],dg[N],udg[N];//dg[]对角线,udg[]反对角线,col列

void dfs(int u)
{
    if(u==n){for(int i=0;i<n;i++)cout<<g[i]<<endl;cout<<endl;return;}

    //y=-x+b b=x+y x=i y=u
    //y=x+b  b=y-x b=y-x+n x=i y=u
    for(int i=0;i<n;i++)
        if(!col[i]&&!dg[i+u]&&!udg[u-i+n])
        {
            g[i][u]='Q';
            col[i]=dg[i+u]=udg[u-i+n]=true;
            dfs(u+1);
            col[i]=dg[i+u]=udg[u-i+n]=false;
            g[i][u]='.';
        }
}

int main()
{
    cin>>n;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)g[i][j]='.';

    dfs(0);
    return 0;
}

o(2^(n^2))
棋子元素角度
逐个

#include<iostream>

using namespace std;

const int N=10*2;
char g[N][N];
int dg[N],udg[N],col[N],row[N];
int n;

void dfs(int x,int y,int s)
{
    if(x==n)y++,x=0;
    if(y==n)
    {
        if(s==n)
        {
            for(int i=0;i<n;i++)cout<<g[i]<<endl;
            cout<<endl;
        }
        return;
    }

    //不选
    g[x][y]='.';
    dfs(x+1,y,s);

    //选
    //反对角线 y=x+b b=y-x+ b=y-x+n 对角线 y=-x+b b=x+y
    if(!col[x]&&!row[y]&&!udg[y-x+n]&&!dg[x+y])
        {
            g[x][y]='Q';
            col[x]=row[y]=udg[y-x+n]=dg[x+y]=true;
            dfs(x+1,y,s+1);
            col[x]=row[y]=udg[y-x+n]=dg[x+y]=false;
            g[x][y]='.';
        }

}
int main()
{
    cin>>n;

    dfs(0,0,0);

    return 0;
}



L.L.
2个月前

题目来源:第十届蓝桥杯省赛C++B组

算法标签:二叉树

题目描述:

给定 N 个加号、M 个减号以及 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1,小明想知道在所有由这 N 个加号、M 个减号以及 N+M+1 个整数凑出的合法的后缀表达式中,结果最大的是哪一个?

请你输出这个最大的结果。

例如使用 123+−,则 “23+1−” 这个后缀表达式结果是 4,是最大的。

输入格式

第一行包含两个整数 N 和 M。

第二行包含 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1。

输出格式

输出一个整数,代表答案。

数据范围

0≤N,M≤10E5,
−109≤Ai≤10E9

思路

我们有N个加号,M个减号,拼凑最大的一个后缀表达式。
则我们从后缀表达式特征入手。

以二叉树后续遍历顺序描绘,则很明显有下面的特征。

Gt64aR.png

当我们将新的数放到左子树上且新的符号为负数时,会将原有的数据全部取反。
Gtc9Rf.png
依据这个特征,我们的数据实际上可以自由更改加减,又因为题目要求求最大值,则我们只需要根据以上反转的特性,构造负数,利用一个负数将多个负数都尽可能转换为正值,最终我们只需要加上最大值减去最小值,再添加完所有的中间值即可求到最大的可能。

其中,当m为0,也就是没有负数时,我们不需要实施反转操作,所有的操作都为+,此时我们只需增加所有的数字的绝对值即可。

题目代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N=2E5+10;//因为数据总量实际是M+N+1
int a[N];

int main()
{
    int m,n;
    cin>>n>>m;
    int k = m+n+1;

    for(int i=0;i<k;i++)cin>>a[i];//读入数据
    sort(a,a+k);

    long long res=0;
    if(!m)for(int i=0;i<k;i++)res+=a[i];//如果没有-号
    else 
    {
        res=a[k-1]-a[0];
        for(int i=1;i<k-1;i++)res+=abs(a[i]);
    }

    cout<<res;
    return 0;
}



L.L.
2个月前

来源: 模板题, Hulu面试题

算法标签:差分

题目描述

输入一个长度为n的整数序列。

接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。

请你输出进行完所有操作后的序列。

输入格式

第一行包含两个整数n和m。

第二行包含n个整数,表示整数序列。

接下来m行,每行包含三个整数l,r,c,表示一个操作。

输出格式

共一行,包含n个整数,表示最终序列。

数据范围

1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000

样例

输入样例:

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例:

3 4 5 3 4 2

思路

为什么要用差分?
在指定区域增加C,原本需要o(n)现在降低到o(1).

差分是什么?
对于数组a1+a2+...an,构造b[n]数组使得a[n]=b[1]+b[2]+b[3]...+b[n].

差分的核心操作
将a[L,R]全部加上C,等价于:b[L] += C, b[R + 1] -= C
1. a[l] ~ a[L-1]无影响
2.a[l] ~ a[r]加上了 c
3.a[r=1] ~ a[n]无影响

cpp代码

#include<iostream>

using namespace std;
const int N=1e5+10;
int a[N],b[N];//a正常数组,b差分数组

void add(int l,int r,int v)//插入
{
    b[l]+=v;
    b[r+1]-=v;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i]-a[i-1];

    while(m--)
        {
           int l,r,v;
           cin>>l>>r>>v;
           add(l,r,v);
        }

    for(int i=1;i<=n;i++)b[i]+=b[i-1],cout<<b[i]<<" ";//b[i]+=b[i-1]由于差分的定义,累加相当于a
}