长乐培训Day9

程序员文章站 2022-07-01 16:24:26

T1 立方数题目【题目描述】作为XX战队的*粉丝，MdZzZZ看到了自己心仪的队伍在半决赛落败，顿时心灰意冷。看着自己手中的从黄牛那里抢来的天价总决赛门票，MdZzZZ觉得去鸟巢已经没有意义了，于是他决定去跳“水立方”。在他准备进“水立方”体育馆时，一位大妈拦住了他的去路，并产生了一下对话： ......

t1 立方数

题目

【题目描述】

作为xx战队的*粉丝，mdzzzz看到了自己心仪的队伍在半决赛落败，顿时心灰意冷。看着自己手中的从黄牛那里抢来的天价总决赛门票，mdzzzz觉得去鸟巢已经没有意义了，于是他决定去跳“水立方”。在他准备进“水立方”体育馆时，一位大妈拦住了他的去路，并产生了一下对话：

大妈：“年轻人我看你印堂发黑，恕我冒昧直言，此去一行怕是会有什么不测。”

mdzzzz：“大妈别拦我，我要跳水立方发泄一下！”

大妈：“年轻人，做事要三思而后行，你知道这水立方最著名的是什么吗？”

mdzzzz：“不知...”

大妈：“这水立方最有名的是‘立方数’！”

mdzzzz：“哦？”

大妈：“别急，听我细细道来。‘立方数’就是，如果一个数可以被写作是一个正整数的3次方，则这个数就是立方数。例如1,8,27就是最小的3个立方数。”

mdzzzz：“……”

大妈：“当然，想要在这水立方中来去自如，你需要知道‘立方差数’！”

大妈：“若一个数可以被写作是两个立方数的差，则这个数就是‘立方差数’，例如7(8-1),26(27-1),19(27-8)都是立方差数。如果你能够判断随便一个数是不是‘立方差数’，那么你就可以真正地在这一片小天地中当一条无忧无虑的小鱼...”

未等mdzzzz反应过来，大妈以飘然远去，留下他一个人在那边细细思索。那么现在你的问题来了，你需要帮助mdzzzz解决这个问题。

现在给定一个数p，mdzzzz想要知道这个数是不是立方差数。

当然你有可能随机输出一些莫名其妙的东西，因此mdzzzz有t次询问~

这个问题可能太难了…… 因此mdzzzz规定p是个质数！

【输入格式】

第一行一个数t，表示有t组数据。

接下来t行，每行一个数p。

【输出格式】

输出t行，对于每个数如果是立方差数，输出“yes”，否则输出“no”。

【输入样例】

【输出样例】

yes

【数据规模】

对于30%的数据p<=100。

对于60%的数据p<=10^6。

对于100%的数据p<=10^12，t<=100。

解析

嗯......题目很长，去掉废话，实际上就是要求质数p是不是立方差数(立方数即为a³-b³(a，b均为正整数，且a≠b)。

我们尝试化简一下a³-b³=p这个式子，可以得到(a-b)(a²+ab+b²)=p，因为p是质数，根据质数的定义(只有1和它本身是它的因数)可以得到，a-b与a²+ab+b²其中一个为1，

很显然a²+ab+b²不为1(因为a与b为互不相等的正整数)，所以a-b=1，移项得a=b+1，带入a³-b³=p，得

(b+1)³-b³=p，即b³+3b²+3b+1-b³=p，化简并移项得3b²+3^b+1-p=0，显然，这是一个一元二次方程，解这个方程可得，

b=(-3±sqrt(12p-3))/6(sqrt为求根号函数)，由于b是正整数，所以如果-3±sqrt(12p-3)可以整除6的话，p就是立方差数。

由于p≤10^12，所以要记得开long long(本蒟蒻就是没开long long少了40分qaq)。

code

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
long long read()
{
    long long num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
int t;
long long p;
double a;
int main()
{
    //freopen("cubicp.in","r",stdin);
    //freopen("cubicp.out","w",stdout);
    t=read();
    while(t--)
    {
        p=read();
        a=(sqrt(12*p-3)-3)-(long long)(sqrt(12*p-3)-3);
        if(a==0&&(long long)(sqrt(12*p-3)-3)%6==0) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
    //fclose(stdin);
    //fclose(stdout);
}

t2 二叉树

题目

【题目描述】

从前有一棵二叉树，我们用如下方式来表示这棵二叉树。

（1）如果一个节点没有儿子，我们用“0”来表示他。

（2）如果一个节点有一个儿子，我们对它的表示以“1”开头，后面接对它儿子的表示。

（3）如果一个节点有两个儿子，我们对它的表示以“2”开头，后面先接对它左儿子的表示，后接对它右儿子的表示。

kjdh十分贪玩，将这棵树染了色，kjdh又十分聪明，它染色又很有规则：每个节点不能和它的孩子有相同的颜色，如果一个节点有两个孩子，那么这两个孩子也不能有相同的颜色。

由于这个树年代久远了，所以我们看不清每个节点的颜色了，但我们知道kjdh只染了红黄白三种颜色。我们想知道这棵树最多和最少有多少个节点是白色的。

【输入格式】

输入文件只有一行，一个字符串，只有“0”，“1”，“2”组成，表示这棵树的结构。

【输出格式】

输出文件包含两个用空格隔开的数，分别表示白色节点的最多和最少数量。

【输入样例】

200

【输出样例】

1 1

【数据规模】

对于 20% 的数据，len<=10。

对于 50% 的数据，len<=2000

对于 100% 的数据，len<=500000。其中len为读入字符串的长度。

解析

不想说话，直接上大佬题解（手动滑稽）：

长乐培训Day9

code

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 500005;
int f[maxn][3], g[maxn][3];
int n, m, i, j, len, k, lc[maxn], rc[maxn];
char s[maxn];
inline int maketree(int x)
{
    if (x > len) return 0;
    if (s[x] == '0') return x;
    if (s[x] == '1') {lc[x] = ++n; return maketree(x + 1);}
    if (s[x] == '2') {lc[x] = ++n; int nex = maketree(x + 1); rc[x] = ++n; return maketree(nex + 1);}
}
inline void dp(int now)
{
    f[now][0] = g[now][0] = 1;
    if (lc[now] && !rc[now])
    {
        dp(lc[now]);
        f[now][0] += max(f[lc[now]][1], f[lc[now]][2]);
        f[now][1] += max(f[lc[now]][0], f[lc[now]][2]);
        f[now][2] += max(f[lc[now]][0], f[lc[now]][1]);
        g[now][0] += min(g[lc[now]][1], g[lc[now]][2]);
        g[now][1] += min(g[lc[now]][0], g[lc[now]][2]);
        g[now][2] += min(g[lc[now]][0], g[lc[now]][1]);
    }
    if (lc[now] && rc[now])
    {
        dp(lc[now]); dp(rc[now]);
        f[now][0] += max(f[lc[now]][2] + f[rc[now]][1], f[lc[now]][1] + f[rc[now]][2]);
        f[now][1] += max(f[lc[now]][0] + f[rc[now]][2], f[lc[now]][2] + f[rc[now]][0]);
        f[now][2] += max(f[lc[now]][0] + f[rc[now]][1], f[lc[now]][1] + f[rc[now]][0]);
        g[now][0] += min(g[lc[now]][2] + g[rc[now]][1], g[lc[now]][1] + g[rc[now]][2]);
        g[now][1] += min(g[lc[now]][0] + g[rc[now]][2], g[lc[now]][2] + g[rc[now]][0]);
        g[now][2] += min(g[lc[now]][0] + g[rc[now]][1], g[lc[now]][1] + g[rc[now]][0]);
    }
}
int main()
{
    //freopen("tree.in", "r", stdin);
    //freopen("tree.out", "w", stdout);
    scanf("%s", s + 1);
    len = strlen(s + 1);
    n = 1;
    maketree(1);
    dp(1);
    cout << max(f[1][0], max(f[1][1], f[1][2])) << " " << min(g[1][0], min(g[1][1], g[1][2])) << endl;
}

t3 hanoi

题目

【题目描述】

众所周知, 汉诺塔是一个古老又经典的游戏. 这个游戏是这样的, 你有n个大小不同的盘子和3根柱子, 一开始所有盘子都叠放在第1根柱子上, 你需要把n个盘子全都移动到第3根柱子上, 每次都可以选择某根柱子最上面的盘子移动到另一根柱子上, 但是任何时候都必须保证没有一个盘子上面放了一个比它大的盘子. 求最少的移动步数.

这个问题太简单了, 乐于寻找挑战的你想要求出当有n个盘子, m个柱子且其他条件不变时, 把所有盘子从第1根柱子移动到第m根柱子的最少步数.

【输入格式】

一行两个整数分别代表题目中的n, m.

【输出格式】

一行一个整数代表答案.

【输入样例】

5 3

【输出样例】

【数据规模】

对于10%的数据, n <= 20, m = 3.

对于30%的数据, m = 3.

对于50%的数据, m <= 4.

对于100%的数据, n <= 63, 3 <= m <= n + 1;

解析

每天必不可少的dp题，令f[i][j]表示i个盘子j个柱子时的最少步数，怎样移动会是最少步数呢？

先把上面盘子移动到不是j的柱子上，再把剩下的盘子移动到j的柱子上，再把上面的盘子移动到j的柱子上。

递推式：f[i][j] = min(f[k][j] * 2 + f[i - k][j - 1])。

code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
int n,m;
long long f[100][100];
int main()
{
    //freopen("hanoi.in","r",stdin);
    //freopen("hanoi.out","w",stdout);
    memset(f,0x7f7f7f7f,sizeof(f));
    n=read(),m=read();
    for(int i=1;i<=m;i++) f[1][i]=1,f[0][i]=0;
    for(int i=2;i<=n;i++) f[i][3]=2*f[i-1][3]+1;
    for(int i=2;i<=n;i++)
        for(int j=4;j<=m;j++)
            for(int k=0;k<i;k++) f[i][j]=min(f[i][j],2*f[k][j]+f[i-k][j-1]);
    cout<<f[n][m];
    return 0;
    //fclose(stdin);
    //fclose(stdout);
}

t4 区间

题目

【题目描述】

有一个 n 个数的序列，一开始所有的数都是 0，每次可以将一个区间 [l,r](l ≤ r) 内的数 +1，求到达最终状态的最少操作次数

【输入格式】

第一行包含一个正整数 n，表示序列的长度。

第二行包含 n 个不同的正整数 a1,a2,...,an，表示最终的状态。

【输出格式】

输出的第一行是一个正整数 m，表示最少的操作次数。接下来 m 行每行两个正整数 li,ri，表示一次操作。你需要保证 1 ≤ li ≤ ri ≤ n。保证最少次数 m ≤ 105，输出可以以任意顺序输出。

【输入样例】

8 8

【输出样例】

1 2

【数据规模】

长乐培训Day9

解析

本蒟蒻只会o(nm)做法，直接上大佬题解吧：

长乐培训Day9

code

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
int n,a[100100],d1[1000100],d2[1000100],temp;
void work(int l,int r,int lastmin)
{
    for(int i=1;i<=lastmin;i++) d1[++temp]=l,d2[temp]=r;
    int nowmin=0x7f7f7f7f,ll=0;
    for(int i=l;i<=r;i++) a[i]-=lastmin;
    for(int i=l;i<=r;i++)
        if(a[i]==0)
        {
            if(ll==0) ll=i+1;
            else
            {
                if(ll>i-1) continue;
                for(int j=ll;j<=i-1;j++) nowmin=min(nowmin,a[j]);
                work(ll,i-1,nowmin);
                nowmin=0x7f7f7f7f,ll=i+1;
            }
        }
        else if(i==l) ll=l;
        else if(i==r)
        {
            for(int j=ll;j<=r;j++) nowmin=min(nowmin,a[j]);
            work(ll,r,nowmin);
        }
}
int main()
{
    //freopen("range.in","r",stdin);
    //freopen("range.out","w",stdout);
    n=read();
    int nowmin=0x7f7f7f7f,ll=0;
    for(int i=1;i<=n;i++) a[i]=read();
    if(n==1)
    {
        cout<<a[1]<<endl;
        for(int i=1;i<=a[1];i++) cout<<"1 1"<<endl;
        return 0;
    }
    work(1,n,0);
    cout<<temp<<endl;
    for(int i=1;i<=temp;i++) cout<<d1[i]<<" "<<d2[i]<<endl;
    return 0;
    //fclose(stdin);
    //fclose(stdout);
}

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 200005;
int sum[maxn << 2], cnt[maxn << 2];
int n, m, i, j, k, l, r, ans, a[maxn], tot;
inline int get()
{
    char c;
    while ((c = getchar()) < 48 || c > 57);
    int res = c - 48;
    while ((c = getchar()) >= 48 && c <= 57)
        res = res * 10 + c - 48;
    return res;
}
inline void updata(int k)
{
    sum[k] = min(sum[k << 1], sum[k << 1 | 1]);
}
inline void putdown(int k)
{
    if (cnt[k])
    {
        cnt[k << 1] += cnt[k];
        cnt[k << 1 | 1] += cnt[k];
        sum[k << 1] -= cnt[k];
        sum[k << 1 | 1] -= cnt[k];
        cnt[k] = 0;
    }
}
inline void change(int k, int p, int q, int l, int r)
{
    if (p >= l && q <= r)
    {
        cnt[k] ++;
        sum[k] --;
        return;
    }
    putdown(k);
    int mid = p + q >> 1;
    if (mid >= l) change(k << 1, p, mid, l, r);
    if (mid < r) change(k << 1 | 1, mid + 1, q, l, r);
    updata(k);
}
inline int query(int k, int p, int q, int w)
{
    if (p == q) return sum[k];
    putdown(k);
    int mid = p + q >> 1;
    if (mid >= w) return query(k << 1, p, mid, w);
    else return query(k << 1 | 1, mid + 1, q, w);
}
inline void maketree(int k, int p, int q)
{
    if (p == q)
    {
        sum[k] = a[p];
        return;
    }
    int mid = p + q >> 1;
    maketree(k << 1, p, mid);
    maketree(k << 1 | 1, mid + 1, q);
    updata(k);
}
inline void find(int k, int p, int q, int l, int r)
{
    int mid = p + q >> 1;
    if (tot) return;
    putdown(k);
    if (p == q) {if (!sum[k]) tot = p; return;}
    if (p >= l && q <= r)
    {
        if (!sum[k << 1]) find(k << 1, p, mid, l, r);
        else if (!sum[k << 1 | 1]) find(k << 1 | 1, mid + 1, q, l, r);
    }
    else
    {
        if (mid >= l) find(k << 1, p, mid, l, r);
        if (mid < r) find(k << 1 | 1, mid + 1, q, l, r);
    }
}
int main()
{
    //freopen("range.in", "r", stdin);
    //freopen("range.out", "w", stdout);
    cin >> n;
    for(i = 1; i <= n; i ++)
        a[i] = get();
    for(i = 1; i <= n; i ++)
        if (a[i] > a[i - 1]) ans += a[i] - a[i - 1];
    cout << ans << endl;
    maketree(1, 1, n);
    for(i = 1; i <= n; i ++)
        while (query(1, 1, n, i))
        {
            tot = 0;
            find(1, 1, n, i, n);
            if (!tot) printf("%d %d\n", i, n), change(1, 1, n, i, n);
            else printf("%d %d\n", i, tot - 1), change(1, 1, n, i, tot - 1);
        }
}

上一篇： file_get_contents('php://input') 和POST的区别

下一篇：葵花子致癌吗，怎么做才好吃，有什么作用与功效

长乐培训Day9

t1 立方数

题目

解析

code

t2 二叉树

题目

解析

code

t3 hanoi

题目

解析

code

t4 区间

题目

解析

code

软文写作培训：理解软文的4个级别

软文写作培训精选：用明确的利益点吸引消费者

我的自学Python之路（第二阶段Day9）

长乐国庆集训Day1

老外爆料：三星因屏幕问题取消Galaxy Fold售前培训、首销或推迟

如何抢抓互联网社交电商发展机遇？清科沙丘创业中心11月西安专题培训为你答疑解惑

大数据培训：分享大数据行业就业趋势

培训机构自建视频课程销售平台的技术方案

linuxprobe培训第2节课笔记2019年7月6日

seowhy论坛VIP培训视频免费分享