头像

mlxg


访客:17799

离线:9小时前



mlxg
9小时前

第六届蓝桥杯省赛C/C++B组(倒序)

10.生命之树

在X森林里,上帝创建了生命之树。

他给每棵树的每个节点(叶子也称为一个节点)上,都标了一个整数,代表这个点的和谐值。

上帝要在这棵树内选出一个非空节点集 S,使得对于 S 中的任意两个点 a,b,都存在一个点列 {a,v1,v2,…,vk,b} 使得这个点列中的每个点都是 S 里面的元素,且序列中相邻两个点间有一条边相连。

在这个前提下,上帝要使得 S 中的点所对应的整数的和尽量大。

这个最大的和就是上帝给生命之树的评分。

经过 atm 的努力,他已经知道了上帝给每棵树上每个节点上的整数。

但是由于 atm 不擅长计算,他不知道怎样有效的求评分。

他需要你为他写一个程序来计算一棵树的分数。

输入格式
第一行一个整数 n 表示这棵树有 n 个节点。

第二行 n 个整数,依次表示每个节点的评分。

接下来 n−1 行,每行 2 个整数 u,v,表示存在一条 u 到 v 的边。

由于这是一棵树,所以是不存在环的。

树的节点编号从 1 到 n。

输出格式
输出一行一个数,表示上帝给这棵树的分数。

数据范围
1≤n≤105,
每个节点的评分的绝对值均不超过 106。

输入样例:
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5
输出样例:
8

思路

利用树形dp,应该是树形dp吧hh。

f[u]表示的是以u为根节点的子树的最大分数。

f[u]=w[u]+f[j] j表示子结点 f[j]需要大于0,否则就不要

对树进行一遍dfs,dfs的过程中求解即可。

代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 100010,M = 2*N;
int h[N],e[M],ne[M],w[N],idx;
int n;
LL f[N];
void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int u,int father)
{
    f[u]=w[u];
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j!=father)
        {
            dfs(j,u);
            f[u]+=max(0ll,f[j]);//加上子树的大于0的值
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)cin>>w[i];
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;++i)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(1,-1);
    LL ans = f[1];
    for(int i=1;i<=n;++i)
        ans = max(f[i],ans);
    cout<<ans<<endl;
    return 0;   
}

9.垒骰子

赌圣atm晚年迷恋上了垒骰子,就是把骰子一个垒在另一个上边,不能歪歪扭扭,要垒成方柱体。

经过长期观察,atm 发现了稳定骰子的奥秘:有些数字的面贴着会互相排斥!

我们先来规范一下骰子:1 的对面是 4,2 的对面是 5,3 的对面是 6。

假设有 m 组互斥现象,每组中的那两个数字的面紧贴在一起,骰子就不能稳定的垒起来。

atm想计算一下有多少种不同的可能的垒骰子方式。

两种垒骰子方式相同,当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。

由于方案数可能过多,请输出模 109+7 的结果。

输入格式
第一行包含两个整数 n,m,分别表示骰子的数目和排斥的组数。

接下来 m 行,每行两个整数 a,b,表示 a 和 b 数字不能紧贴在一起。

输出格式
共一个数,表示答案模 109+7 的结果。

数据范围
1≤n≤109,
1≤m≤36,
1≤a,b≤6
输入样例:
2 1
1 2
输出样例:
544

思路

这个题目比较难,我也讲不清楚。简单说一下知识点。

首先我们考虑dp f[i][j]为垒i个骰子,第i个骰子j点朝上的情况数。如果一层一层求,铁定超时。

那么这个时候考虑矩阵乘法,寻求f[n][i]和f[n+1][j]的关系(这样表示似乎不对,就是第n层的六面和第n+1层的六面的关系),这个时候就可以找到关系矩阵A。然后由于排斥的组数,把某些位置改为0即可。

快速矩阵乘。

代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 6,mod = 1e9+7;
int f[N][N];
int a[N][N];
int get_op(int x)
{
    if(x<3)return x+3;
    return x-3;
}
void mul(int c[][N],int a[][N],int b[][N])
{
    static int t[N][N]={0};
    memset(t,0,sizeof t);
    for(int i=0;i<N;++i)
    {
        for(int j=0;j<N;++j)
        {
            for(int k=0;k<N;++k)
            {
                t[i][j]=(t[i][j]+1ll*a[i][k]*b[k][j])%mod;//不能+= 因为加上6个1e9会爆int
            }
        }
    }
    memcpy(c,t,sizeof t);   
} 
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<N;++i)
    {
        for(int j=0;j<N;++j)
        {
            a[i][j]=4;
        }
    }
    for(int i=0;i<m;++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        a[x][get_op(y)]=0;
        a[y][get_op(x)]=0;
    }
    for(int i=0;i<N;++i)
    {
        f[0][i]=4;
    }
    n--;
    while(n)
    {
        if(n&1)mul(f,f,a);
        n>>=1;
        mul(a,a,a);
    }
    LL res = 0;
    for(int i=0;i<N;++i)
    {
        res = (res+f[0][i])%mod;
    }
    cout<<res<<endl;
    return 0;
} 

8.移动距离

X星球居民小区的楼房全是一样的,并且按矩阵样式排列。其楼房的编号为1,2,3...
当排满一行时,从下一行相邻的楼往反方向排号。
比如:当小区排号宽度为6时,开始情形如下:
1   3  4  5  6
12 11 10 9  8  7
13 14 15 .....
我们的问题是:已知了两个楼号m和n,需要求出它们之间的最短移动距离(不能斜线方向移动)
输入为3个整数w m n,空格分开,都在1到10000范围内
w为排号宽度,m,n为待计算的楼号。
要求输出一个整数,表示m n 两楼间最短移动距离。
例如:
用户输入:
6 8 2
则,程序应该输出:
4
再例如:
用户输入:
4 7 20
则,程序应该输出:
5
资源约定:
峰值内存消耗 < 256M
CPU消耗  < 1000ms

思路

把编号变为0 1 2 3....

然后处理x,y坐标

代码

#include<iostream>
#include<cmath>
using namespace std;
int w,m,n;
int main()
{
    cin>>w>>m>>n;
    m--;n--;
    int x1,y1,x2,y2;
    x1=m/w;
    x2=n/w;
    y1=m%w;
    y2=n%w;
    if(x1%2)
        y1=w-1-y1;
    if(x2%2)
        y2=w-1-y2;
    cout<<abs(x1-x2)+abs(y1-y2)<<endl;
    return 0;
}

7.牌型种类

小明被劫持到X赌城,被迫与其他3人玩牌。
一副扑克牌(去掉大小王牌,共52张),均匀发给4个人,每个人13张。
这时,小明脑子里突然冒出一个问题:
如果不考虑花色,只考虑点数,也不考虑自己得到的牌的先后顺序,自己手里能拿到的初始牌型组合一共有多少种呢?
请填写该整数,不要填写任何多余的内容或说明文字。

思路

dfs即可 每种牌可选0-4张,然后从第一种搜到第13种就行了

代码

#include<iostream>
#include<cmath>
using namespace std;
int ans;
void dfs(int n,int m)
{
    if(m==0)
    {
        ans++;
        return;
    }
    if(n==13||m<0)
    {
        return;
    }
    for(int i=0;i<=4;++i)
        dfs(n+1,m-i);
}
int main()
{
    dfs(0,13); 
    cout<<ans<<endl;
    return 0;
}

6.加法变乘法

我们都知道:1+2+3+ ... + 49 = 1225
现在要求你把其中两个不相邻的加号变成乘号,使得结果为2015
比如:
1+2+3+...+10*11+12+...+27*28+29+...+49 = 2015
就是符合要求的答案。
请你寻找另外一个可能的答案,并把位置靠前的那个乘号左边的数字提交(对于示例,就是提交10)。
注意:需要你提交的是一个整数,不要填写任何多余的内容。

思路

这个思路看代码吧

代码

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

int main()
{
    for(int i=2;i<=49;++i)
    {
        for(int j=i+2;j<=49;++j)
        {
            if((1225+i*(i-1)+j*(j-1))-i-(i-1)-j-(j-1)==2015)
                cout<<i-1<<" "<<j-1<<endl;
        }
    }
    return 0;
}

答案

16

5.九数组分数

1,2,3...9 这九个数字组成一个分数,其值恰好为1/3,如何组法?
下面的程序实现了该功能,请填写划线部分缺失的代码。

思路

复制粘贴;读代码;填空,运行正确;完成。

代码

#include <stdio.h>

void test(int x[])
{
    int a = x[0]*1000 + x[1]*100 + x[2]*10 + x[3];
    int b = x[4]*10000 + x[5]*1000 + x[6]*100 + x[7]*10 + x[8];

    if(a*3==b) printf("%d / %d\n", a, b);
}

void f(int x[], int k)
{
    int i,t;
    if(k>=9){
        test(x);
        return;
    }

    for(i=k; i<9; i++){
        {t=x[k]; x[k]=x[i]; x[i]=t;}
        f(x,k+1);
        t=x[k]; x[k]=x[i]; x[i]=t;// 填空处
    }
}

int main()
{
    int x[] = {1,2,3,4,5,6,7,8,9};
    f(x,0);
    return 0;
}

答案

t=x[k]; x[k]=x[i]; x[i]=t;

4.格子中输出

StringInGrid函数会在一个指定大小的格子中打印指定的字符串。
要求字符串在水平、垂直两个方向上都居中。
如果字符串太长,就截断。
如果不能恰好居中,可以稍稍偏左或者偏上一点。
下面的程序实现这个逻辑,请填写划线部分缺少的代码。

思路

复制粘贴;读代码;填空,运行正确;完成。

printf(“%*s”,10,”abc”) 表示以10宽度来显示abc

 我们可能知道scanf里用*修饰符,是起到过滤读入的作用。比如一个有三列数值的数据,我只想得到第2列数值,可以在循环里用scanf(“%*d%d%*d”, a[i])来读入第i行的第2个数值到a[i]。 
  但是* 修饰符在printf中的含义完全不同。如果写成printf(“%6d”, 123),很多童鞋应该就不会陌生了,这是设置域宽的意思。同理,%6s也是域宽。* 修饰符正是用来更灵活的控制域宽。使用%*s,表示这里的具体域宽值由后面的实参决定,如printf(“%*s”, 6, “abc”)就是把”abc”放到在域宽为6的空间中右对齐
  来源:https://www.cnblogs.com/darklights/p/5296377.html

代码

#include <stdio.h>
#include <string.h>

void StringInGrid(int width, int height, const char* s)
{
    int i,k;
    char buf[1000];
    strcpy(buf, s);
    if(strlen(s)>width-2) buf[width-2]=0;

    printf("+");
    for(i=0;i<width-2;i++) printf("-");
    printf("+\n");

    for(k=1; k<(height-1)/2;k++){
        printf("|");
        for(i=0;i<width-2;i++) printf(" ");
        printf("|\n");
    }

    printf("|");

    printf("%*s%s%*s",(width-2-strlen(buf))/2,"",buf,(width-2-strlen(buf))/2,"");  //填空

    printf("|\n");

    for(k=(height-1)/2+1; k<height-1; k++){
        printf("|");
        for(i=0;i<width-2;i++) printf(" ");
        printf("|\n");
    }

    printf("+");
    for(i=0;i<width-2;i++) printf("-");
    printf("+\n");
}

int main()
{
    StringInGrid(20,6,"abcd123gjdjgdddddddddddddd4");
    return 0;
}

答案

(width-2-strlen(buf))/2,"",buf,(width-2-strlen(buf))/2,""

3.三羊献瑞

观察下面的加法算式:

      祥 瑞 生 辉   // 0 1 2 3
  +   三 羊 献 瑞   // 4 5 6 1
-------------------
   三 羊 生 瑞 气   // 4 5 2 1 7

(如果有对齐问题,可以参看【图1.jpg】)

其中,相同的汉字代表相同的数字,不同的汉字代表不同的数字。

请你填写“三羊献瑞”所代表的4位数字(答案唯一),不要填写任何多余内容。

思路

全排列+简单的判断

代码

#include<iostream>
#include<vector>
using namespace std;
//8
int ans;
vector<int> vec;
bool st[10];
int get(int a[],int n)
{
    int res = 0;
    for(int i=0;i<n;++i)
    {
        res = res*10+vec[a[i]];
    }
    return res;
}
bool check()
{
    int a[] = {0,1,2,3};
    int b[] = {4,5,6,1};
    int c[] = {4,5,2,1,7};
    if(vec[0]==0||vec[4]==0)
        return false;
    int A = get(a,4);
    int B = get(b,4);
    int C = get(c,5);
    if(A+B==C)
    {
        //cout<<ans<<endl;
        cout<<A<<" "<<B<<" "<<C<<endl;
        for(int i=0;i<4;++i)
        {
            cout<<vec[b[i]]<<" ";
        }
        cout<<endl; 
        return true;
    }
    return false;//必须返回 
}
void dfs(int n)
{
    if(n==8)
    {
        if(check())
            ans++;
        return;
    }
    for(int i=0;i<=9;++i)
    {
        if(!st[i])
        {
            st[i]=true;
            vec.push_back(i);
            dfs(n+1);
            st[i]=false;
            vec.pop_back();
        }
    }
}
int main()
{
    dfs(0);
    cout<<ans<<endl;
    return 0;
}

答案

1085

2.星系炸弹

思路

日期加法

代码

#include<iostream>
using namespace std;
int days[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
bool isleap(int x)
{
    if((x%4==0&&x%100!=0)||(x%400==0))
        return true;
    return false;
}
int modify(int x)
{
    int year = x/10000;
    int month = x%10000/100;
    int day = x%100;
    day++;
    int t = days[month];
    if(month==2&&isleap(year))
        t++;
    if(day>t)
    {
        month++;
        day=1;
    }
    if(month>12)
    {
        year++;
        month=1;
    }
    return year*10000+month*100+day;
}
int main()
{
    //2000 08 04
    int year,month,day,t;
    cin>>year>>month>>day>>t;
    int ans = year*10000+month*100+day;
    while(t--)
    {
        ans = modify(ans);
    }
    printf("%04d-%02d-%02d",ans/10000,ans%10000/100,ans%100);
    return 0;
}

答案

2017-08-05

1.奖券数目

有些人很迷信数字,比如带“4”的数字,认为和“死”谐音,就觉得不吉利。
虽然这些说法纯属无稽之谈,但有时还要迎合大众的需求。某抽奖活动的奖券号码是5位数(10000-99999),要求其中不要出现带“4”的号码,

主办单位请你计算一下,如果任何两张奖券不重号,最多可发出奖券多少张。


请提交该数字(一个整数),不要写任何多余的内容或说明性文字。

思路

代码

#include<iostream>
using namespace std;
bool check(int x)
{
    while(x)
    {
        int t=x%10;
        x/=10;
        if(t==4)return false;
    }
    return true;
}
int main()
{
    int ans = 0;
    for(int i=10000;i<=99999;++i)
    {
        if(check(i))
            ans++;
    }
    cout<<ans<<endl;
    return 0;
}

答案

52488




mlxg
2天前

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

1.煤球数目

有一堆煤球,堆成三角棱锥形。具体:
第一层放1个,
第二层3个(排列成三角形),
第三层6个(排列成三角形),
第四层10个(排列成三角形),
….
如果一共有100层,共有多少个煤球?

请填表示煤球总数目的数字。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

思路

这个题目说是三角形,那么我们就不难找出规律了。具体看代码

代码

#include<iostream>
using namespace std;
const int N = 110;
int a[N];
int ans; 
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<=n;++i)
    {
        a[i]=a[i-1]+i;
        ans+=a[i];
    }
    cout<<ans<<endl;
    return 0;
} 

答案

171700

2.生日蜡烛

某君从某年开始每年都举办一次生日party,并且每次都要吹熄与年龄相同根数的蜡烛。

现在算起来,他一共吹熄了236根蜡烛。

请问,他从多少岁开始过生日party的?

请填写他开始过生日party的年龄数。
注意:你提交的应该是一个整数,不要填写任何多余的内容或说明性文字。

思路

暴力枚举开始年龄和结束年龄。

#include<iostream>
using namespace std;
const int N = 110;

int main()
{
    for(int i=1;i<=N;++i)
    {
        int t = 0;
        for(int j=i;;j++)
        {
            t+=j;
            if(t==236)
            {
                cout<<i<<endl;
                return 0;
            }
            if(t>236)
            {
                break;
            }
        }
    }
    return 0;
} 

答案

26

3.凑算式

img

6+8/3+952/714 就是一种解法,
5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法?
注意:你提交应该是个整数,不要填写任何多余的内容或说明性文字。

思路

全排列+简单的判断

#include<iostream>
#include<vector>
using namespace std;
bool st[15];
vector<int> vec;
int ans;
double get(int l,int r)
{
    int res = 0;
    for(int i=l;i<=r;++i)
    {
        res = res*10+vec[i];
    }
    return res;
}
bool check()
{
    double A = get(0,0);
    double B = get(1,1);
    double C = get(2,2);
    double DEF = get(3,5);
    double GHI = get(6,8);
    if(A+B/C+DEF/GHI==10)
        return true;
    return false;
}
void dfs(int n)
{
    if(n==9)
    {
        if(check())
            ans++;
        return;
    }
    for(int i=1;i<=9;++i)
    {
        if(!st[i])
        {
            vec.push_back(i);
            st[i]=true;
            dfs(n+1);
            st[i]=false;
            vec.pop_back();
        }
    }
}
int main()
{
    dfs(0);
    cout<<ans<<endl; 
    return 0;
} 

答案

29

4. 快速排序

没什么说的

答案

swap(a,j,p);

5.抽签

X星球要派出一个5人组成的观察团前往W星。
其中:
A国最多可以派出4人。
B国最多可以派出2人。
C国最多可以派出2人。
….

那么最终派往W星的观察团会有多少种国别的不同组合呢?

下面的程序解决了这个问题。
数组a[] 中既是每个国家可以派出的最多的名额。
程序执行结果为:
DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
….
(以下省略,总共101行)
#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024

void f(int a[], int k, int m, char b[])
{
    int i,j;

    if(k==N){ 
        b[M] = 0;
        if(m==0) printf("%s\n",b);
        return;
    }

    for(i=0; i<=a[k]; i++){
        for(j=0; j<i; j++) b[M-m+j] = k+'A';
        ______________________;  //填空位置
    }
}
int main()
{   
    int  a[N] = {4,2,2,1,1,3};
    char b[BUF];
    f(a,0,M,b);
    return 0;
}

思路

补全代码题:先复制粘贴到编辑器上再说。然后读一下代码。然后就做出来结束了

解释一下这个函数的参数:第一个参数不用说了;第二个参数表示的是第几个国家的代表团;第三个参数是说明还有多少个空缺席位;第四个也不用说了。

然后把代码补全,运行验证一下即可。

答案

#include <stdio.h>
#define N 6
#define M 5
#define BUF 1024

void f(int a[], int k, int m, char b[])
{
    int i,j;

    if(k==N){ 
        b[M] = 0;
        if(m==0) printf("%s\n",b);
        return;
    }

    for(i=0; i<=a[k]; i++){
        for(j=0; j<i; j++) b[M-m+j] = k+'A';
        f(a,k+1,m-j,b);  //填空位置
    }
}
int main()
{   
    int  a[N] = {4,2,2,1,1,3};
    char b[BUF];
    f(a,0,M,b);
    return 0;
}

6.方格填数

如图,如下的10个格子,填入0~9的数字。要求:连续的两个数字不能相邻。
(左右、上下、对角都算相邻)一共有多少种可能的填数方案?
请填写表示方案数目的整数。

img

思路

全排列+简单的判断即可

代码

#include<iostream>
#include<algorithm>
using namespace std;
int a[10];
int b[3][4];
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
bool check()
{
    //填入数字 
    int k=0;
    for(int i=0;i<3;++i)
    {
        for(int j=0;j<4;++j)
        {
            if((i==0&&j==0)||(i==2&&j==3))continue;
            b[i][j]=a[k++];
        }
    }
    //开始判断
    for(int i=0;i<3;++i)
    {
        for(int j=0;j<4;++j)
        {
            if((i==0&&j==0)||(i==2&&j==3))continue;//注意这里,这两个不需要判断 
            for(int d=0;d<8;++d)
            {
                int x = i+dx[d];
                int y = j+dy[d];
                if(x<0||x>=3||y<0||y>=4)continue;
                if((x==0&&y==0)||(x==2&&y==3))continue;//谨记那两个空位也是不合法位置 
                if(b[x][y]==b[i][j]+1)return false;
            }
        }
    }
    return true;
}
int main()
{
    int ans = 0;
    for(int i=0;i<10;++i)a[i]=i;
    do{
        if(check())
            ans++; 
    }while(next_permutation(a,a+10));
    cout<<ans<<endl;
    return 0;
}

答案

1580

7.剪邮票

如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来,要求必须是连着的。
(仅仅连接一个角不算相连)
比如,【图2.jpg】,【图3.jpg】中,粉红色所示部分就是合> 格的剪取。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

思路

全排列+floodfill

代码

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
int a[3][4]={0,0,0,0,0,0,0,1,1,1,1,1};
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
bool st[3][4];
bool bfs()
{
    queue<PII> q;
    memset(st,0,sizeof st);
    for(int i=0;i<3;++i)
    {
        for(int j=0;j<4;++j)
        {
            if(a[i][j]==1)
            {
                q.push(make_pair(i,j));
                st[i][j]=true;
                i=100;
                break;  
            }
        }
    }
    int res = 0;
    while(q.size())
    {
        PII t = q.front();
        q.pop();
        res++;
        for(int i=0;i<4;++i)
        {
            int aa = dx[i]+t.x;
            int bb = dy[i]+t.y;
            if(aa<0||aa>=3||bb<0||bb>=4)continue;
            if(st[aa][bb])continue;
            if(a[aa][bb]==0)continue;
            q.push(make_pair(aa,bb));
            st[aa][bb]=true;
        }
    }
    return res==5;
}
int main()
{
    int ans = 0;
    do{
        if(bfs())
            ans++;
    }while(next_permutation(a[0],a[0]+12));
    cout<<ans<<endl;
    return 0;
}

答案

116

8.四平方和定理

四平方和定理,又称为拉格朗日定理:
每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去,就正好可以表示为4个数的平方和。
比如:
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
(^符号表示乘方的意思)
对于一个给定的正整数,可能存在多种平方和的表示法。
要求你对4个数排序:
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法

思路

二分 二分一定要记得排序hh

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2500010;
struct Node{
    int l,r,w;
    bool operator<(const Node& W)const
    {
        if(W.w!=w)return w<W.w;
        if(W.l!=l)return l<W.l;
        return r<W.r;
    }
}sum[N];
int main()
{
    int n;
    cin>>n;
    int k=0;
    for(int c=0;c*c<=n;++c)
    {
        for(int d=c;c*c+d*d<=n;++d)
        {
            sum[k].w=c*c+d*d;
            sum[k].l=c;
            sum[k].r=d;
            k++;
        }
    }
    sort(sum,sum+k);
    for(int a=0;a*a<=n;++a)
    {
        for(int b=a;b*b+a*a<=n;++b)
        {
            int t = n-a*a-b*b;
            int l=0,r=k-1;
            while(l<r)
            {
                int mid = l+r >>1;
                if(sum[mid].w<t)l=mid+1;
                else r=mid;
            }
            if(sum[l].w==t)
            {
                cout<<a<<" "<<b<<" "<<sum[l].l<<" "<<sum[l].r<<endl;
                return 0;
            }
        }
    }
    return 0;
} 

9.交换瓶子

有N个瓶子,编号 1 ~ N,放在架子上。

比如有5个瓶子:
2 1 3 5 4

要求每次拿起2个瓶子,交换它们的位置。
经过若干次后,使得瓶子的序号为:
1 2 3 4 5

对于这么简单的情况,显然,至少需要交换2次就可以复位。

如果瓶子更多呢?你可以通过编程来解决。
输入格式为两行:
第一行: 一个正整数N(N<10000), 表示瓶子的数目
第二行:N个正整数,用空格分开,表示瓶子目前的排列情况。

输出数据为一行一个正整数,表示至少交换多少次,才能完成排序。

思路

如果把至少去掉,可能大多数人就都会做了,我也被至少困扰了很久,但是其实对于我们菜鸡来说,能有一种方法算出来交换多少次就很好了,作对血赚。不过我感觉不做无效操作的话,求出来的一般都是至少的情况。

代码

#include<iostream>
using namespace std;
const int N = 10010;
int a[N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    int ans = 0;
    for(int i=1;i<=n;++i)
    {
        while(a[i]!=i)
        {
            swap(a[a[i]],a[i]);
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

10.最大比例

X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
并且,相邻的两个级别间的比例是个固定值。
也就是说:所有级别的奖金数构成了一个等比数列。比如:
16,24,36,54
其等比值为:3/2

现在,我们随机调查了一些获奖者的奖金数。
请你据此推算可能的最大的等比值。

输入格式:
第一行为数字 N (0<N<100),表示接下的一行包含N个正整数
第二行N个正整数Xi(Xi<1 000 000 000 000),用空格分开。每个整数表示调查到的某人的奖金数额

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

测试数据保证了输入格式正确,并且最大比例是存在的。

思路

思路其实很简单,关键是代码对分数的处理。

思路:求出相邻的数字之间的比例,然后取共同的q就行。(共同的q,就是假如有两个数x=q^a, y=q^b,那么求出这个q)。至于分数的处理,看代码。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
typedef long long LL;
LL up[N],down[N];
LL a[N];
LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;  
}
LL qgcd(LL a,LL b)
{
    if(a<b)swap(a,b);
    if(b==1)return a;
    return qgcd(b,a/b);
}
int n;
int len;
int main()
{
    cin>>n;
    for(int i=0;i<n;++i)cin>>a[i];
    sort(a,a+n);
    for(int i=1;i<n;++i)
    {
        LL d = gcd(a[i],a[i-1]);
        up[len]=a[i]/d;
        down[len]=a[i-1]/d;
        len++;  
    }   
    LL u = 1,d=1;
    for(int i=0;i<len;++i)
    {
        u = qgcd(u,up[i]);
        d = qgcd(d,down[i]); 
    }
    cout<<u<<"/"<<d<<endl;
    return 0;
}



mlxg
5天前

第八届蓝桥杯C++B组省赛题

1.购物单

小明刚刚找到工作,老板人很好,只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦,但又不好推辞。

这不,XX大促销又来了!老板夫人开出了长长的购物单,都是有打折优惠的。
小明也有个怪癖,不到万不得已,从不刷卡,直接现金搞定。
现在小明很心烦,请你帮他计算一下,需要从取款机上取多少现金,才能搞定这次购物。

取款机只能提供100元面额的纸币。小明想尽可能少取些现金,够用就行了。
你的任务是计算出,小明最少需要取多少现金。

需要说明的是,88折指的是按标价的88%计算,而8折是按80%计算,余者类推。
特别地,半价是按50%计算。

请提交小明要从取款机上提取的金额,单位是元。
答案是一个整数,类似4300的样子,结尾必然是00,不要填写任何多余的内容。

特别提醒:不许携带计算器入场,也不能打开手机。

思路

这里我选择了用记事本来替换掉了****和 折字,然后用文件读操作,完成了这道题目。

代码

#include<iostream>
#include<fstream>
using namespace std;

int main()
{
    ifstream fin("test01.txt");
    double price,count;
    double money = 0;
    while(fin>>price>>count)
    {
        if(count<10)count*=10;
        money+=price*count*0.01;
    }
    cout<<money<<endl;
    int ans = 0;
    while(ans<money)ans+=100;
    printf("%d",ans);
    return 0;
}

答案

5200

2. 等差素数列

2,3,5,7,11,13,....是素数序列。 类似:7,37,67,97,127,157 这样完全由素数组成的等差数列,叫等差素数数列。 上边的数列公差为30,长度为6。 2004年,格林与华人陶哲轩合作证明了:存在任意长度的素数等差数列。 这是数论领域一项惊人的成果! 有这一理论为基础,请你借助手中的计算机,满怀信心地搜索: 长度为10的等差素数列,其公差最小值是多少? 注意:需要提交的是一个整数,不要填写任何多余的内容和说明文字。

思路

这里我选择的思路是,先筛出来素数,然后暴力,枚举公差和首项。至于N取多少,取一个比较大的数看有没有答案。

代码

#include<iostream>
using namespace std;
const int N = 100010;
bool st[N];
int prime[N],cnt;
void init()
{
    for(int i=2;i<=N;++i)
    {
        if(!st[i])prime[cnt++]=i;
        for(int j=0;j<cnt&&prime[j]*i<=N;++j)
        {
            st[i*prime[j]]=true;
            if(i%prime[j]==0)
                break;
        }
    }
}
bool isok(int a,int d)
{
    for(int i=0;i<10;++i)
    {
        if(a+d*i>N||st[a+d*i])
        {
            return false;
        }
    }
    return true;
}
int main()
{
    init();
    for(int k=1;;k++)
    {
        for(int i=2;i<=N;++i)
        {
            if(!st[i]&&isok(i,k))
            {
                cout<<k<<endl;
                return 0;
            }
        }
    }
    return 0;   
} 

答案

210

3.承压计算

X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。

每块金属原料的外形、尺寸完全一致,但重量不同。
金属材料被严格地堆放成金字塔形。

                             7 
                            5 8 
                           7 8 8 
                          9 2 7 2 
                         8 1 4 9 1 
                        8 1 8 8 4 1 
                       7 9 6 1 4 5 4 
                      5 6 5 5 6 9 5 6 
                     5 5 4 7 9 3 5 5 1 
                    7 5 7 9 7 4 7 3 3 1 
                   4 6 4 5 5 8 8 3 2 4 3 
                  1 1 3 3 1 6 6 5 5 4 4 2 
                 9 9 9 2 1 9 1 9 2 9 5 7 9 
                4 3 3 7 7 9 3 6 1 3 8 8 3 7 
               3 6 8 1 5 3 9 5 8 3 8 1 8 3 3 
              8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9 
             8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4 
            2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9 
           7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6 
          9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3 
         5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9 
        6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4 
       2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4 
      7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6 
     1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3 
    2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8 
   7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9 
  7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6 
 5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1 
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 

其中的数字代表金属块的重量(计量单位较大)。
最下一层的X代表30台极高精度的电子秤。

假设每块原料的重量都十分精确地平均落在下方的两个金属块上,
最后,所有的金属块的重量都严格精确地平分落在最底层的电子秤上。
电子秤的计量单位很小,所以显示的数字很大。

工作人员发现,其中读数最小的电子秤的示数为:2086458231

请你推算出:读数最大的电子秤的示数为多少?

注意:需要提交的是一个整数,不要填写任何多余的内容。

思路

这里直接暴力枚举每一个位置的承重,直到枚举到第三十层,然后找到最大的重量和最小的重量进行比例扩大即可。

代码

#include<iostream>
#include<fstream>
using namespace std;

const int N = 35;
double f[N][N];
int main()
{
    ifstream fin("test03.txt");
    for(int i=1;i<=29;++i)
    {
        for(int j=1;j<=i;++j)
        {
            fin>>f[i][j];
        }
    }
    for(int i=2;i<=30;++i)
    {
        for(int j=1;j<=i;++j)
        {
            f[i][j]+=f[i-1][j-1]/2+f[i-1][j]/2;
        }
    }
    double maxv = -1e9,minv = 1e9;
    for(int i=1;i<=30;++i)
    {
        if(f[30][i]>maxv)maxv = f[30][i];
        if(f[30][i]<minv)minv = f[30][i];
    }
    printf("%.0f",2086458231/minv*maxv);
    return 0;
}

答案

72665192664

4.方格分割

6x6的方格,沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。

试计算:
包括这3种分法在内,一共有多少种不同的分割方法。
注意:旋转对称的属于同一种分割法。

请提交该整数,不要填写任何多余的内容或说明文字。

思路

很容易可以直到,若要使两部分的形状完全相同,那么切割线一定是中心对称的,且不能交叉。这时候只需要从中心深搜统计答案即可,最后要除以四,因为四个方向其实都是一样的。

代码

#include<iostream>
using namespace std;
const int N = 7;
bool st[N][N];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int ans;
void dfs(int x,int y)
{
    if(x==0||x==6||y==0||y==6)//到达了边界 
    {
        ans++;
        return;
    }
    for(int i=0;i<4;++i)
    {
        int a = dx[i]+x;
        int b = dy[i]+y;
        if(st[a][b])continue;//不能走走过的地方
        st[a][b]=true;
        st[6-a][6-b]=true;//防止交叉,两个都要标记
        dfs(a,b);
        st[a][b]=false;
        st[6-a][6-b]=false;
    }
}
int main()
{
    st[3][3]=true;
    dfs(3,3);
    cout<<ans/4<<endl;
    return 0;
}

答案

509

5.取数位

没啥说的

6.最大公共子串

没啥说的

7.日期问题

小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是,这些日期采用的格式非常不统一,有采用年/月/日的,有采用月/日/年的,还有采用日/月/年的。更加麻烦的是,年份也都省略了前两位,使得文献上的一个日期,存在很多可能的日期与其对应。  

比如02/03/04,可能是2002年03月04日、2004年02月03日或2004年03月02日。  

给出一个文献上的日期,你能帮助小明判断有哪些可能的日期对其对应吗?

输入
----
一个日期,格式是"AA/BB/CC"。  (0 <= A, B, C <= 9)  

输出
----
输出若干个不相同的日期,每个日期一行,格式是"yyyy-MM-dd"。多个日期按从早到晚排列。  

样例输入
----
02/03/04  

样例输出
----
2002-03-04  
2004-02-03  
2004-03-02  

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗  < 1000ms


请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。

注意:
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。

提交程序时,注意选择所期望的语言类型和编译器类型。

思路

暴力暴力,枚举所有的日期,看哪个符合题意输出即可

代码

#include<iostream>
using namespace std;
int days[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int first,second,third;
bool isleap(int year)
{
    if((year%4==0&&year%100!=0)||(year%400==0))
        return true;
    return false;
}
int modify(int x)
{
    int year = x/10000;
    int month = x%10000/100;
    int day = x%100;
    day++;
    int t = days[month];
    if(month==2&&isleap(year))
        t+=1;
    if(day>t)
    {
        day=1;
        month++;
    }
    if(month>12)
    {
        month=1;
        year++;
    }
    return year*10000+month*100+day;
}
bool check(int x)
{
    int year = x/10000%100;
    int month = x%10000/100;
    int day = x%100;
    if((first==year&&second==month&&third==day)||(first==month&&second==day&&third==year)||(first==day&&second==month&&third==year))
        return true;
    return false;
}
int main()
{
    scanf("%d/%d/%d",&first,&second,&third);
    int start = 19600101,end = 20591231;
    for(int i=start;i<=end;i=modify(i))
    {
        if(check(i))
            printf("%d-%02d-%02d\n",i/10000,i%10000/100,i%100);
    }
 } 

8.包子凑数

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼,其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼,可以认为是无限笼。

每当有顾客想买X个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼,分别能放3、4和5个包子。当顾客想买11个包子时,大叔就会选2笼3个的再加1笼5个的(也可能选出1笼3个的再加2笼4个的)。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼,分别能放4、5和6个包子。而顾客想买7个包子时,大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入
----
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)  

输出
----
一个整数代表答案。如果凑不出的数目有无限多个,输出INF。

例如,
输入:
2  
4  
5   

程序应该输出:
6  

再例如,
输入:
2  
4  
6    

程序应该输出:
INF

样例解释:
对于样例1,凑不出的数目包括:1, 2, 3, 6, 7, 11。  
对于样例2,所有奇数都凑不出来,所以有无限多个。  

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗  < 1000ms


请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。

注意:
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。

提交程序时,注意选择所期望的语言类型和编译器类型。

思路

前提知识:p,q当最大公约数>1时会有无数个数字无法表示出来,当==1的时候。最大不能表示的数是pq-q-p

这道题先判断最大公约数,若是大于1那么就输出INF。若是等于1,利用类似完全背包来计算哪些数字能被表示。

代码

#include<iostream>
using namespace std;
const int N = 110,M = N*N;
int n;
int v[N];
int f[M];
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)cin>>v[i];
    int d = 0;
    for(int i=1;i<=n;++i)d=gcd(d,v[i]);
    if(d>1)
    {
        puts("INF");
    }
    else{
        f[0]=true;
        for(int i=1;i<=n;++i)
        {
            for(int j=v[i];j<M;++j)
            {
                f[j]|=f[j-v[i]];
            }
        }
        int ans = 0;
        for(int i=0;i<M;++i)
        {
            if(!f[i])ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

9.分巧克力

标题: 分巧克力

    儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
    小明一共有N块巧克力,其中第i块是Hi x Wi的方格组成的长方形。

    为了公平起见,小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足:

    1. 形状是正方形,边长是整数  
    2. 大小相同  

例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。

当然小朋友们都希望得到的巧克力尽可能大,你能帮小Hi计算出最大的边长是多少么?

输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)  
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000) 
输入保证每位小朋友至少能获得一块1x1的巧克力。   

输出
输出切出的正方形巧克力最大可能的边长。

样例输入:
2 10  
6 5  
5 6  

样例输出:
2

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗  < 1000ms


请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。

注意:
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。

提交程序时,注意选择所期望的语言类型和编译器类型。

思路

二分答案,每次check一下是否符合情况即可,res要是long long 的,可能会爆int。

代码

#include<iostream>
using namespace std;
const int N = 100010;
int w[N],h[N];
int n,k;
bool check(int x)
{
    long long res = 0;
    for(int i=1;i<=n;++i)
    {
        res+=(w[i]/x)*(h[i]/x);
    }
    return res>=k;
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>w[i]>>h[i];
    int l=1,r=N;
    while(l<r)
    {
        int mid = l+r+1 >>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}

10.k倍区间

给定一个长度为N的数列,A1, A2, ... AN,如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。  

你能求出数列中总共有多少个K倍区间吗?  

输入
-----
第一行包含两个整数N和K。(1 <= N, K <= 100000)  
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)  

输出
-----
输出一个整数,代表K倍区间的数目。  


例如,
输入:
5 2
1  
2  
3  
4  
5  

程序应该输出:
6

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗  < 2000ms


请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。

注意:
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。

提交程序时,注意选择所期望的语言类型和编译器类型。

思路

前缀和:若是(a[r]-a[l])%k==0 ,那么就是符合条件的区间,其实可以转换为在模k的意义下,a[r]=a[l];

那么我们可以每次记录前缀和模k的个数,特殊的,sum[0]是需要初始化为1,因为0的前缀和是0,这样理解是可以的。也可以这样理解,后面模k的情况下a[r]-a[0]==0 也是符合的情况所以0是要被记录的,sum[0]=1。

代码

#include<iostream>
using namespace std;
const int N = 100010;
int n,k;
long long a[N],sum[N];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>a[i];
    sum[0]=1;
    long long res = 0;
    for(int i=1;i<=n;++i)
    {
        a[i]+=a[i-1];
        res+=sum[a[i]%k]++;
    }
    cout<<res<<endl;
    return 0;
 } 



mlxg
7天前

第九届蓝桥杯题解(C++B组)

1.第几天

2000年的1月1日,是那一年的第1天。
那么,2000年的5月4日,是那一年的第几天?
注意:需要提交的是一个整数,不要填写任何多余内容。

解法

相信大佬们有各种各样的解法,我就写一种纯代码实现的吧

代码

#include<iostream>
using namespace std;
int days[] = {31,28,31,30,31,30,31,31,30,31,30,31};
bool isleap(int year)
{
    if((year%4==0&&year%100!=0)||year%400==0)
        return true;
    return false;
}
int main()
{
    int year,month,day;
    int ans = 0;
    cin>>year>>month>>day;
    for(int i=0;i<month-1;++i)//下标是从0开始的 
    {
        ans += days[i];
        if(i==1&&isleap(year))
            ans+=1;
    }
    cout<<ans+day<<endl;
    return 0;
}

答案

125

2.明码

汉字的字形存在于字库中,即便在今天,16点阵的字库也仍然使用广泛。

16点阵的字库把每个汉字看成是16x16个像素信息。并把这些信息记录在字节中。

一个字节可以存储8位信息,用32个字节就可以存一个汉字的字形了。
把每个字节转为2进制表示,1表示墨迹,0表示底色。每行2个字节,
一共16行,布局是:

第1字节,第2字节
第3字节,第4字节
....
第31字节, 第32字节

这道题目是给你一段多个汉字组成的信息,每个汉字用32个字节表示,这里给出了字节作为有符号整数的值。

题目的要求隐藏在这些信息中。你的任务是复原这些汉字的字形,从中看出题目的要求,并根据要求填写答案。

这段信息是(一共10个汉字):下面这段数据直接输入的话,不会换行,可以先复制到记事本上,在复制记事本上的。
4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0
16 64 16 64 34 68 127 126 66 -124 67 4 66 4 66 -124 126 100 66 36 66 4 66 4 66 4 126 4 66 40 0 16
4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0
0 -128 64 -128 48 -128 17 8 1 -4 2 8 8 80 16 64 32 64 -32 64 32 -96 32 -96 33 16 34 8 36 14 40 4
4 0 3 0 1 0 0 4 -1 -2 4 0 4 16 7 -8 4 16 4 16 4 16 8 16 8 16 16 16 32 -96 64 64
16 64 20 72 62 -4 73 32 5 16 1 0 63 -8 1 0 -1 -2 0 64 0 80 63 -8 8 64 4 64 1 64 0 -128
0 16 63 -8 1 0 1 0 1 0 1 4 -1 -2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 5 0 2 0
2 0 2 0 7 -16 8 32 24 64 37 -128 2 -128 12 -128 113 -4 2 8 12 16 18 32 33 -64 1 0 14 0 112 0
1 0 1 0 1 0 9 32 9 16 17 12 17 4 33 16 65 16 1 32 1 64 0 -128 1 0 2 0 12 0 112 0
0 0 0 0 7 -16 24 24 48 12 56 12 0 56 0 -32 0 -64 0 -128 0 0 0 0 1 -128 3 -64 1 -128 0 0

注意:需要提交的是一个整数,不要填写任何多余内容。

解法

这题相信大佬们也有很多种方式,这里我使用bitset来完成

代码

#include<iostream>
#include<bitset>
using namespace std;

int main()
{
    for(int k=0;k<10;++k)//k个汉字 
    {
        for(int i=0;i<16;++i)//每次输入两个字节,供需输入16次 
        {
            int num1,num2;
            cin>>num1>>num2;
            bitset<8> bit1(num1),bit2(num2);
            string str1 = bit1.to_string();
            string str2 = bit2.to_string();
            for(int i=0;i<8;++i)
                if(str1[i]=='0')
                    cout<<" ";
                else 
                    cout<<"*";
            for(int i=0;i<8;++i)
                if(str2[i]=='0')
                    cout<<" ";
                else 
                    cout<<"*";
            cout<<endl;//换个行 
        }
    }
    return 0;
} 

答案

387 420 489

3.乘积尾零

如下的10行数据,每行有10个整数,请你求出它们的乘积的末尾有多少个零? 下列数据也先复制到记事本上
5650 4542 3554 473 946 4114 3871 9073 90 4329
2758 7949 6113 5659 5245 7432 3051 4434 6704 3594
9937 1173 6866 3397 4759 7557 3070 2287 1453 9899
1486 5722 3135 1170 4014 5510 5120 729 2880 9019
2049 698 4582 4346 4427 646 9742 7340 1230 7683
5693 7015 6887 7381 4172 4341 2909 2027 7355 5649
6701 6645 1671 5978 2704 9926 295 3125 3878 6785
2066 4247 4800 1578 6652 4616 1113 6205 3264 2915
3966 5291 2904 1285 2193 1428 2265 8730 9436 7074
689 5510 8243 6114 337 4096 8199 7313 3685 211

注意:需要提交的是一个整数,表示末尾零的个数。不要填写任何多余内容。

解法

相信大佬们都有自己的看法,我一开始是用的高精度乘法,但是有些蠢了,后来才得知另一种解法。

由10=2*5可知,一个尾零是有一个2和一个5乘积得到的,我们可以对每个数分解质因数(2和5),然后统计各自的个数,最终答案取min值就行了。

代码

#include<iostream>
#include<bitset>
using namespace std;

int main()
{
    int two=0,five=0;
    for(int i=0;i<100;++i)
    {
        int num;
        cin>>num;
        while(num%2==0)
        {
            two++;
            num/=2;
        }
        while(num%5==0)
        {
            five++;
            num/=5;
        }
    }  
    cout<<min(two,five)<<endl;
    return 0;
} 

答案

31

4.测试次数

x星球的居民脾气不太好,但好在他们生气的时候唯一的异常举动是:摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试,并且评定出一个耐摔指数来,之后才允许上市流通。
x星球有很多高耸入云的高塔,刚好可以用来做耐摔测试。塔的每一层高度都是一样的,与地球上稍有不同的是,他们的第一层不是地面,而是相当于我们的2楼。
如果手机从第7层扔下去没摔坏,但第8层摔坏了,则手机耐摔指数=7。
特别地,如果手机从第1层扔下去就坏了,则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏,则耐摔指数=n
为了减少测试次数,从每个厂家抽样3部手机参加测试。
某次测试的塔高为1000层,如果我们总是采用最佳策略,在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢?
请填写这个最多测试次数。
注意:需要填写的是一个整数,不要填写任何多余内容。

思路

本菜鸡理解了好久这道题,网上的分为数学解法和动态规划解法,我在这里介绍一下动态规划解法(毕竟我要是会数学,还会是现在这逼样子吗)

先入为主:dp[i][j]的含义是 i部手机,j层楼需要的测试次数。(需要注意楼层与楼层之间并没有什么不同,无非就是摔下去坏与不坏)

现在需要思考一下dp[i][j]怎么求?

dp[i][j]包括哪几种情况呢?第i部手机在j个层楼扔下去的情况之和。若是在第k层(这个第k并不是整体上的第k)扔下去,那么为摔坏和没摔坏,分别是dp[i-1][k-1]和dp[i][j-k],由于我们运气背,所以我们总是会需要max(dp[i-1][k-1],dp[i][j-k]).

那么现在就很明朗了:dp[i][j]=min(dp[i][j],max(dp[i-1][k-1],dp[i][j-k])+1),k=[1,j] 这里为什么最外层有一个min呢,这是因为我们的策略是最优的,我们只不过是运气背。(多理解一下,我也觉得很难理解)

初始化,由于一部手机j层楼肯定运气最差的话需要j次,二三部肯定<j次,初始化为f[i][j]=j即可

值得一提的是若是手机并没有限制个数,二分永远是最优的。

代码

#include<iostream>
#include<bitset>
using namespace std;
const int N = 10 ,M = 1010;
int f[N][M];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            f[i][j]=j;
        }
    }
    for(int i=2;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            for(int k=1;k<=j;++k)
            {
                f[i][j]=min(f[i][j],max(f[i-1][k-1],f[i][j-k])+1);
            }
        }
     } 
    cout<<f[n][m]<<endl;
    return 0;
} 

答案

19

5.快速排序

以下代码可以从数组a[]中找出第k小的元素。
它使用了类似快速排序中的分治算法,期望时间复杂度是O(N)的。

请仔细阅读分析源码,填写划线部分缺失的内容。

#include <stdio.h>

int quick_select(int a[], int l, int r, int k) {
    int p = rand() % (r - l + 1) + l;
    int x = a[p];
    {int t = a[p]; a[p] = a[r]; a[r] = t;}
    int i = l, j = r;
    while(i < j) {
        while(i < j && a[i] < x) i++;
        if(i < j) {
            a[j] = a[i];
            j--;
        }
        while(i < j && a[j] > x) j--;
        if(i < j) {
            a[i] = a[j];
            i++;
        }
    }
    a[i] = x;
    p = i;
    if(i - l + 1 == k) return a[i];
    if(i - l + 1 < k) return quick_select( _____________________________ ); //填空
    else return quick_select(a, l, i - 1, k);
}

int main()
{
    int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};
    printf("%d\n", quick_select(a, 0, 14, 5));
    return 0;
}

思路

这个代码的思路相信大佬们都很容易理解。我简单说一下:每次随机取一个数放在末尾并备份保存下来,然后开始遍历,从开头找比这个数大的,放到后面;然后从后面找比这个数小的,放到开头;重复到最后只剩一个空位,也就是i==j,这个时候,剩下的肯定就是我们备份的那个,赋值即可。

最后若是这个备份的数刚好是第k个数就返回,若不是,则分为两种情况:在左半段,这个时候就返回左半段的第k个数;在右半段,这个时候由于左半段有(i-l)+1个数字,那么我们返回第k-((i-l)+1)个数字。

答案

a,i+1,r,k-(i-l+1)

6.递增三元组

给定三个整数数组
A = [A1, A2, … AN],
B = [B1, B2, … BN],
C = [C1, C2, … CN],
请你统计有多少个三元组(i, j, k) 满足:

1 <= i, j, k <= N

Ai < Bj < Ck

【输入格式】
第一行包含一个整数N。
第二行包含N个整数A1, A2, … AN。
第三行包含N个整数B1, B2, … BN。
第四行包含N个整数C1, C2, … CN。

对于30%的数据,1 <= N <= 100
对于60%的数据,1 <= N <= 1000
对于100%的数据,1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000

【输出格式】
一个整数表示答案

【样例输入】
3
1 1 1
2 2 2
3 3 3

【样例输出】
27

思路

相信大佬们也会好多种做法,前缀和,二分啥的,我在这里介绍利用c++库函数得来的答案。

首先我们思路肯定是,对于一个b[i],找a中比他小的数的个数,c中比他大的数的个数,然后想乘。每个b[i]的答案最终相加就是最终的结果。那么怎么找呢,就要先对a,c排序,然后调用库函数求,说着比较抽象,看代码。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int a[N];
int b[N];
int c[N];
int n;
int main()
{
    cin>>n;
    for(int i=0;i<n;++i)cin>>a[i];
    for(int i=0;i<n;++i)cin>>b[i];
    for(int i=0;i<n;++i)cin>>c[i];
    sort(a,a+n);
    sort(c,c+n);
    long long res = 0;
    for(int i=0;i<n;++i)
    {
        long long t1 = lower_bound(a,a+n,b[i])-a;
        long long t2 = n-(upper_bound(c,c+n,b[i])-c);
        res+=t1*t2;
    }
    cout<<res<<endl;
    return 0;
} 

7.螺旋折线

如图p1.png所示的螺旋折线经过平面上所有整点恰好一次。
对于整点(X, Y),我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。
例如dis(0, 1)=3, dis(-2, -1)=9
给出整点坐标(X, Y),你能计算出dis(X, Y)吗?

img

【输入格式】
X和Y

对于40%的数据,-1000 <= X, Y <= 1000
对于70%的数据,-100000 <= X,Y <= 100000
对于100%的数据, -1000000000 <= X, Y <= 1000000000

【输出格式】

输出dis(X, Y)

【样例输入】
0 1

【样例输出】
3

思路

这个其实就是找规律,那么怎么找规律的呢。这个比较难以形容哈!但其实你可以看做是一个一个的正方形嵌套,第一个正方形的左下角开始到第二个正方形的左下角结束。这其中的点都由第一个正方形的长度+特殊判断的长度。

代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int main()
{
    LL x,y;
    cin>>x>>y;
    LL len = max(abs(x),abs(y));
    LL res = (len-1)*len*4;
    if(x==-len)res+=(y+len);
    else if(y==len)res+=2*len+x+len;
    else if(x==len)res+=4*len+len-y;
    else res+=6*len+len-x;
    cout<<res<<endl;
    return 0;
} 

8.日志统计

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志,日志共有 N 行。

其中每一行的格式是:

ts id
表示在 ts 时刻编号 id 的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。

如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞,小明就认为这个帖子曾是”热帖”。

具体来说,如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞,该帖就曾是”热帖”。

给定日志,请你帮助小明统计出所有曾是”热帖”的帖子编号。

第一行包含三个整数 N,D,K。

以下 N 行每行一条日志,包含两个整数 ts 和 id。

输出格式
按从小到大的顺序输出热帖 id。

每个 id 占一行。

数据范围
1≤K≤N≤105,
0≤ts,id≤105,
1≤D≤10000
输入样例:
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例:
1
3

思路

这个思路呢,有点像滑动窗口,我们利用双指针,每次统计一个区间内的各个帖子的点赞量,若是达到了热帖,就标记一下。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
#define x first
#define y second
typedef pair<int,int> PII;
PII query[N];
int cnt[N];//统计时间区间内的点赞量
bool st[N];
int n,d,k; 
int main()
{
    cin>>n>>d>>k;
    for(int i=0;i<n;++i)
    {
        int a,b;
        cin>>a>>b;
        query[i]=make_pair(a,b);
    }
    sort(query,query+n);
    for(int i=0,j=0;i<n;++i)
    {
        cnt[query[i].y]++;
        while(query[i].x-query[j].x>=d)
        {
            cnt[query[j].y]--;
            j++;
        }
        if(cnt[query[i].y]>=k)st[query[i].y]=true;
    }
    for(int i=0;i<N;++i)
        if(st[i])
            cout<<i<<endl;
    return 0;
} 

9.全球变暖

你有一张某海域NxN像素的照片,”.”表示海洋、”#”表示陆地,如下所示:
.......
.##....
.##....
....##.
..####.
…###.
.......
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
.......
.......
.......
.......
....#..
.......
.......

请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。

【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)

以下N行N列代表一张海域照片。

照片保证第1行、第1列、第N行、第N列的像素都是海洋。

【输出格式】

一个整数表示答案

思路

这个就是一个很典型的宽搜 FloodFill算法(不会的可以自行百度),但要注意题目求的是多少岛屿会被淹没。

代码

#include<iostream>
#include<algorithm>
#include<queue> 
using namespace std;
const int N = 1010;
typedef pair<int,int> PII;
#define x first
#define y second
char g[N][N];
bool st[N][N];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int n;
bool bfs(int sx,int sy)
{
    queue<PII> q;
    int res = 0;//记录存活的小方块 
    q.push(make_pair(sx,sy));
    st[sx][sy]=true;
    while(q.size())
    {
        PII t = q.front();
        q.pop();
        bool flag = true;
        for(int i=0;i<4;++i)
        {
            int a = t.x+dx[i];
            int b = t.y+dy[i];
            if(a<0||a>=n||b<0||b>=n)continue;
            if(st[a][b])
                continue;
            if(g[a][b]=='.')
            {
                flag = false;
                continue;
            }
            q.push({a,b});
            st[a][b]=true;
        }
        if(flag)
            res++;
    }
    if(res>0) return true;
    return false;
}
int main()
{
    cin>>n;
    int tol = 0,up = 0;//tol记录总的岛屿,up记录活着的岛屿 
    for(int i=0;i<n;++i)cin>>g[i];
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            if(!st[i][j]&&g[i][j]=='#')
            {
                tol++;
                if(bfs(i,j))
                    up++;
            }
        }
    }
    cout<<tol-up<<endl;
    return 0;
} 

10.最大乘积

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

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

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

注意,如果 X<0, 我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009 的余数,即:0−((0−x)%1000000009)
输入格式
第一行包含两个整数 N 和 K。

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

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

数据范围
1≤K≤N≤105,
−105≤Ai≤105
输入样例1:
5 3
-100000
-10000
2
100000
10000
输出样例1:
999100009
输入样例2:
5 3
-100000
-100000
-2
-100000
-100000
输出样例2:
-999999829

思路

当k为偶数的时候,当然很容易求了。每次取两个数,看看哪个乘积大。也就是求最大的非负数。

当k为奇数的时候,就不大容易求了,若是最大数是负数,那么我们另求最小非负数。若最大数是非负数,那么我们依旧求一个最大的非负数即可。

综上,我们要求最大的非负数或者最小的非负数,可以借助一个sign来将这两个代码块统一起来,而k为奇数的时候我们需要特判一下,将他变为偶数,因为偶数好求最大的非负数或者最小的非负数。

代码

#include<iostream>
#include<algorithm>
#include<queue> 
using namespace std;
const int N = 100010,mod = 1e9+9;
typedef long long LL;
LL a[N];
int n,k;
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;++i)cin>>a[i];
    sort(a,a+n);
    LL res= 1;
    int l=0,r=n-1;
    int sign=1;
    if(k%2)
    {
        res=a[r];
        r--;
        k--;
        if(res<0)
            sign=-1;//求最小的非负数 
    }
    while(k)
    {
        LL x = a[l]*a[l+1],y = a[r]*a[r-1];
        if(sign*x>sign*y)
        {
            res=x%mod*res%mod;
            l+=2;
        }
        else 
        {
            res=y%mod*res%mod;
            r-=2;   
        } 
        k-=2;
    }
    cout<<res<<endl;
    return 0;
} 



mlxg
3个月前

算法思路

最终的序列是第i个位置上应该放第i个数
那麽从前往后遍历,只要数字不再自己的位置上,就进行交换。

代码
#include<iostream>
using namespace std;
const int N = 10010;
int a[N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    int res = 0;
    for(int i=1;i<=n;++i)
        while(a[i]!=i)swap(a[a[i]],a[i]),res++;
    cout<<res<<endl;
    return 0;
}



mlxg
4个月前

闫氏dp分析

最大公约数若是>1,说明有无限个数不能被表示。
若是=1,则在最大数是100的情况下。
不能被表示最大的数最大是 (100-1)*(99-1)-1

包子凑数.png

#include<iostream>
using namespace std;
const int N = 110,M=N*N;
bool f[M];
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int v[N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)cin>>v[i];
    int d=0;
    for(int i=1;i<=n;++i)
    {
        d = gcd(d,v[i]);
    }
    if(d>1){
        puts("INF");
        return 0;
    }
    f[0]=true;
    for(int i=1;i<=n;++i)
    {
        for(int j=v[i];j<M;++j)
        {
            f[j]|=f[j-v[i]];
        }
    }
    int res = 0;
    for(int i=1;i<M;++i)
    {
        if(!f[i])
            res++;
    }
    cout<<res<<endl;
    return 0;
}



mlxg
4个月前

巧妙的矩阵构造

Fn= [fn,fn+1,sn]
Fn+1= [fn+1,fn+2,sn+1]
Fn*A = Fn+1
可求得A = 0 1 0
1 1 1
0 0 1
Fn = F1 * $A^{n-1}$

F1 = 1 1 1
0 0 0
0 0 0
求得Fn F[0][2]就是答案

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 3;
LL n,m;
void mul(LL c[][N],LL a[][N],LL b[][N])//多维数组除了第一维 其他都要指定长度
{
    LL temp[N][N]={0};
    for(int i=0;i<N;++i)
    {
        for(int j=0;j<N;++j)
        {
            for(int k=0;k<N;++k)
            {
                temp[i][j]=(temp[i][j]+a[i][k]*b[k][j])%m;
            }
        }
    }
    memcpy(c,temp,sizeof temp);//形参sizeof 是不可行的
}
int main()
{
    cin>>n>>m;
    LL f[N][N]={1,1,1};
    LL a[N][N]={
        {0,1,0},
        {1,1,1},
        {0,0,1}
    };
    n--;
    while(n)
    {
        if(n&1)mul(f,f,a);
        mul(a,a,a);
        n>>=1;
    }
    cout<<f[0][2]<<endl;
    return 0;
}



mlxg
4个月前

题目分析

要求求出S最大的值,S其实是一个联通块。所以就是求所有联通块里面值最大的那个。

树形dp

一般使用f[u]表示树形dp
本题中,f[u]表示的是以u为根节点的连通块的sum的最大值
f[u]=w[u]+max(子树的情况,0)

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 100010,M=N*2;
int h[N],e[M],ne[M],w[N],idx;
int n;
LL f[N];
void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int u,int father)
{
    f[u]=w[u];
    for(int i=h[u];~i;i=ne[i])
    {
        int j = e[i];
        if(j!=father)
        {
            dfs(j,u);
            f[u]+=max(0ll,f[j]);
        }
    }
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;++i)cin>>w[i];
    for(int i=0;i<n-1;++i){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(2,-1);
    LL res = f[1];
    for(int i=2;i<=n;++i)res = max(res,f[i]);
    cout<<res<<endl;
    return 0;
}



mlxg
4个月前

题目分析

得到最少的脱落数目,等价于求求最少的单个字符(无回文匹配的字符),那麽也就是求最大的回文字符数
然后由总长度减去最大回文字符数就是答案

注意下图右下角应该是 f[i+1][j-1]+2(s[i]==s[j])

闫氏dp法

密码脱落.png

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int f[N][N];
char str[N];
int main()
{
    cin>>str+1;
    int n = strlen(str+1);
    for(int len=1;len<=n;++len)
    {
        for(int i=1;i+len-1<=n;++i)
        {
            int j = i+len-1;
            if(len==1){f[i][j]=1;continue;}
            f[i][j]=max(f[i+1][j],f[i][j-1]);
            if(str[i]==str[j])
                f[i][j]=max(f[i+1][j-1]+2,f[i][j]);
        }
    }
    cout<<n-f[1][n]<<endl;
    return 0;
}



mlxg
4个月前

闫氏dp分析法

糖果.png

代码

#include<cstring>
#include<iostream>
using namespace std;

const int N = 110;
int f[N][N];
int n,k;
int main()
{
    cin>>n>>k;
    memset(f[0],-0x3f,sizeof f[0]);
    f[0][0]=0;
    for(int i=1;i<=n;++i)
    {
        int w;
        cin>>w;
        for(int j=0;j<k;++j)
        {
           f[i][j]=max(f[i-1][j],f[i-1][((j-w)%k+k)%k]+w);
        }
    }
    cout<<f[n][0]<<endl;
    return 0;
}