首页 > 其他分享 >csp-j题解

csp-j题解

时间:2024-02-07 09:46:32浏览次数:25  
标签:10 小苞 int 题解 站点 leq 苹果 csp

csp-j题解

第一题:小苹果

原题洛谷P9748

题目描述

小 Y 的桌子上放着 \(n\) 个苹果从左到右排成一列,编号为从 \(1\) 到 \(n\)。
小苞是小 Y 的好朋友,每天她都会从中拿走一些苹果。
每天在拿的时候,小苞都是从左侧第 \(1\) 个苹果开始、每隔 \(2\) 个苹果拿走 \(1\) 个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。
小苞想知道,多少天能拿完所有的苹果,而编号为 \(n\) 的苹果是在第几天被拿走的?

输入格式

输入的第一行包含一个正整数 \(n\),表示苹果的总数。

输出格式

输出一行包含两个正整数,两个整数之间由一个空格隔开,分别表示小苞拿走所有苹果所需的天数以及拿走编号为 \(n\) 的苹果是在第几天。

样例 #1

样例输入 #1

8

样例输出 #1

5 5

提示

【样例 \(1\) 解释】
小苞的桌上一共放了 \(8\) 个苹果。
小苞第一天拿走了编号为 \(1\)、\(4\)、\(7\) 的苹果。
小苞第二天拿走了编号为 \(2\)、\(6\) 的苹果。
小苞第三天拿走了编号为 \(3\) 的苹果。
小苞第四天拿走了编号为 \(5\) 的苹果。
小苞第五天拿走了编号为 \(8\) 的苹果。
【样例 \(2\)】
见选手目录下的 apple/apple2.in 与 apple/apple2.ans。
【数据范围】
对于所有测试数据有:\(1\leq n\leq 10^9\)。

测试点 \(n\leq\) 特殊性质
\(1\sim 2\) \(10\)
\(3\sim 5\) \(10^3\)
\(6\sim 7\) \(10^6\)
\(8\sim 9\) \(10^6\)
\(10\) \(10^9\)
特殊性质:小苞第一天就取走编号为 \(n\) 的苹果。

思路

这题还是很简单的,稍微模拟一下就看的出来规律了
先对题意进行模拟

1 2 3 4 5 6 7 8 9
第一天 1 1 1
第二天 1 1
第三天 1 1
第四天 1
第五天 1

然后开始打暴力模拟题意 就会TLE

#include <iostream>
using namespace std;
const int N=1e6+5;
int n,a[N],day,day2;
int main(){
    freopen("apple.in","r",stdin);
    freopen("apple.out","w",stdout);
    cin>>n;
    while(1){
        int out=0;
        for(int i=1;i<=n;i++)
        {
            if(!a[i]){
                out++;
                if(out%3==1) a[i]=1;
            }
        }
        day++;
        if(a[n]==1) 
        {
            cout<<day<<endl;
            break;
        }
    }
    while(n){
        n=n-(n-1)/3-1;
        day2++;
    }
    cout<<day2;
    return 0;
}

结果如下

(好像是我的问题?)
这暴力比我的正解难打多了

分析一下

求几天取完很简单,每天会取走(n-1)/3+1个苹果,将原来的长度减去每天取走的长度,直到长度为0,用了几天就是几天。
第 \(n\) 个苹果第几天被取走可以这样想
题目里有这样一句话

每天在拿的时候,小苞都是从左侧第 \(1\) 个苹果开始、每隔 \(2\) 个苹果拿走 \(1\) 个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。

于是我们自然的想到,每次取完苹果后剩下的苹果会形成一个新的更短的序列
比如:一开始有 $ 9 $ 个苹果,我们要取第 $ 9 $ 个
在第一天取完后,就变为:有 \(6\) 个苹果,我们要取第 $ 6 $ 个
在第二天取完后,就变为:有 \(4\) 个苹果,我们要取第 \(4\) 个
………………
依次递推,直到恰好取到最后一个苹果

于是我们想:当最后一个苹果位于什么位置时,恰好能被取得
根据题意,易得:当序列长度为k * 3 + 1时,即最后一个苹果位于k * 3 + 1时刚好能被取到(k为整数)
那么代码如下

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    freopen("apple.in","r",stdin);
    freopen("apple.out","w",stdout);
	int n,tn=1,day=0;
	scanf("%d", &n);
	int m = n;
	while ((m - 1) % 3 != 0) {
		tn++;
		m = m - (m - 1) / 3 - 1;
	}
	while (n) {
		day++;
		n = n - (n - 1) / 3 - 1;
	}
	printf("%d %d", day, tn);
	return 0;
}

结果如下:

可以看出来基本在TLE边缘
时间复杂度约为O(2*logn),两个while循环是可以优化成一个的
如下

#include <iostream>
#include <cstdio>
int n, tn = 1, day = 0, k;
using namespace std;
int main()
{
    freopen("apple.in", "r", stdin);
    freopen("apple.out", "w", stdout);
    scanf("%d", &n);
    while (n)
    {
        if ((n-1) %3 != 0 &&k == 0)
            tn++;
        else
            k = 1;
        day++;
        n = n - (n - 1) / 3 - 1;
    }
    printf("%d %d", day, tn);
    return 0;
}

结果如下

500-650毫秒间,比较安全


第二题:公路

原题洛谷P9749

[CSP-J 2023] 公路

题目描述

小苞准备开着车沿着公路自驾。

公路上一共有 \(n\) 个站点,编号为从 \(1\) 到 \(n\)。其中站点 \(i\) 与站点 \(i + 1\) 的距离为 \(v_i\) 公里。

公路上每个站点都可以加油,编号为 \(i\) 的站点一升油的价格为 \(a_i\) 元,且每个站点只出售整数升的油。

小苞想从站点 \(1\) 开车到站点 \(n\),一开始小苞在站点 \(1\) 且车的油箱是空的。已知车的油箱足够大,可以装下任意多的油,且每升油可以让车前进 \(d\) 公里。问小苞从站点 \(1\) 开到站点 \(n\),至少要花多少钱加油?

输入格式

输入的第一行包含两个正整数 \(n\) 和 \(d\),分别表示公路上站点的数量和车每升油可以前进的距离。

输入的第二行包含 \(n - 1\) 个正整数 \(v_1, v_2\dots v_{n-1}\),分别表示站点间的距离。

输入的第三行包含 \(n\) 个正整数 \(a_1, a_2 \dots a_n\),分别表示在不同站点加油的价格。

输出格式

输出一行,仅包含一个正整数,表示从站点 \(1\) 开到站点 \(n\),小苞至少要花多少钱加油。

样例 #1

样例输入 #1

5 4
10 10 10 10
9 8 9 6 5

样例输出 #1

79

提示

【样例 1 解释】

最优方案下:小苞在站点 \(1\) 买了 \(3\) 升油,在站点 \(2\) 购买了 \(5\) 升油,在站点 \(4\) 购买了 \(2\) 升油。

【样例 2】

见选手目录下的 road/road2.in 与 road/road2.ans。

【数据范围】

对于所有测试数据保证:\(1 \leq n \leq 10^5\),\(1 \leq d \leq 10^5\),\(1 \leq v_i \leq 10^5\),\(1 \leq a_i \leq 10^5\)。

测试点 \(n \leq\) 特殊性质
\(1\sim 5\) \(8\)
\(6\sim 10\) \(10^3\)
\(11\sim 13\) \(10^5\) A
\(14\sim 16\) \(10^5\) B
\(17\sim 20\) \(10^5\)
  • 特殊性质 A:站点 \(1\) 的油价最低。
  • 特殊性质 B:对于所有 \(1 \leq i < n\),\(v_i\) 为 \(d\) 的倍数。

思路

一眼贪心

假设现在公路是有n个加油站,现在小苞位于\(a\)加油站,后面有\(m\)个加油站,每个加油站加油的价格都不相同
1.如果后面\(m\)个加油站的加油的价格都比\(a\)加油站贵,那么直接加到恰好能走完全程的油,因为后面的加油站无论在那个停下加油都会更贵
2.如果后面的\(m\)个加油站中,第一个比\(a\)加油站加油费便宜的是\(b\)加油站,则在\(a\)加油站加足量的油恰好能到b加油站,到b加油站加油
每到一个加油站,执行上述两个操作直到走完全程

上述这些大概就是程序要做的
但其实每必要到一个点就把整条路都扫一遍
两种做法

  1. 1.记录加油所需的钱,与到达的加油站的价格进行比较,如果价格更低廉的话,就记录当前 加油站的价格,否则依然记录之前加油所需的钱,然后对油费进行计算
    2.以1为起点的最长下降序列,就是提前找好在哪些地方加油
  2. 完全背包

1.1
需要注意的一点就是

每个站点只出售整数升的油

这样就会导致一个问题:到达下一个加油站可能油桶里的油会有剩余(比如样例1中1加油站到2加油站),再用两站之间的距离除油的价钱算得的油量会多出一些
所以为了解决这个问题,我们需要用一个变量 \(gv\) 来记录从第 \(1\) 个车站到第 \(i\) 个车站之间的距离,让后用 \(gv\) 减去已经加的油 \(tv\) 与每升油可以前进的距离 \(d\) 相乘的到的积,就可以的到实际上应加油支持走的路程
还有:不开 \(long long\) 见祖宗
代码如下:

#include <iostream>
#include <cmath>
using namespace std;
const int N=1e5+5;
long long n,d,v[N],a[N],w,x=N,tv,allv,gv;
int main(){
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    cin>>n>>d;
    for(int i=1;i<=n-1;i++) cin>>v[i],allv+=v[i];
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1,v1;i<n;i++)
    {
        gv+=v[i];
        x=min(x,a[i]);
        v1=ceil((gv-tv*d)*1.0/d);
        tv+=v1;
        w+=x*v1;
    }
    cout<<w;
    return 0;
}

结果如下

时间复杂度O(3*n) 稳过


1.2
没有写,以后有机会补上?


2.背包
我是想不到用背包做,这里是题解区dalao的东西
想到了也实现不来
原作者xvl_
在 dp 之前,我们需要明确以下几个东西:
状态的表示,状态转移方程,边界条件跟答案的表示。
状态的表示 $ dp_i $ 表示到达第 \(i\) 个站点所需要的最少钱数, \(w_i\) 表示在使用最少钱数到达第 \(i\) 个站点时多余的路程。
状态转移方程
\(dp_i=dp_{i-1}+(v_{i-1}-w_{i-1})/d*premin(i-1)\)
\(w_i=(v_{i-1}-w_{i-1})/d-v_{i-1}+w_{i-1}\)
其中 \(premin(i-1)\) 表示前 \(i\) 个站点中最小的油价。
边界条件
\(dp_i=0\)
\(w_i=0\)
答案的表示
\(dp_n\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll n, d, ans;
ll v[100005], a[100005], dp[100005], pm[100005], w[100005];
int main() {
	freopen("road.in", "r", stdin);
	freopen("road.out", "w", stdout);
	ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin >> n >> d;
	pm[0] = 1e18;
	for (int i = 1; i < n; i++) cin >> v[i];
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pm[i] = min(pm[i - 1], a[i]);
	}
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + ceil(1.0 * (v[i - 1] - w[i - 1]) / d) * pm[i - 1];
		w[i] = ceil(1.0 * (v[i - 1] - w[i - 1]) / d) * d - (v[i - 1] - w[i - 1]);
	}
	cout << dp[n];
	return 0;
}

结果如下:


第三题:一元二次方程

原题洛谷P9750

[CSP-J 2023] 一元二次方程

题目背景

众所周知,对一元二次方程 \(ax ^ 2 + bx + c = 0, (a \neq 0)\),可以用以下方式求实数解:

  • 计算 \(\Delta = b ^ 2 - 4ac\),则:
    1. 若 \(\Delta < 0\),则该一元二次方程无实数解。
    2. 否则 \(\Delta \geq 0\),此时该一元二次方程有两个实数解 \(x _ {1, 2} = \frac{-b \pm \sqrt \Delta}{2a}\)。

例如:

  • \(x ^ 2 + x + 1 = 0\) 无实数解,因为 \(\Delta = 1 ^ 2 - 4 \times 1 \times 1 = -3 < 0\)。
  • \(x ^ 2 - 2x + 1 = 0\) 有两相等实数解 \(x _ {1, 2} = 1\)。
  • \(x ^ 2 - 3x + 2 = 0\) 有两互异实数解 \(x _ 1 = 1, x _ 2 = 2\)。

在题面描述中 \(a\) 和 \(b\) 的最大公因数使用 \(\gcd(a, b)\) 表示。例如 \(12\) 和 \(18\) 的最大公因数是 \(6\),即 \(\gcd(12, 18) = 6\)。

题目描述

现在给定一个一元二次方程的系数 \(a, b, c\),其中 \(a, b, c\) 均为整数且 \(a \neq 0\)。你需要判断一元二次方程 \(a x ^ 2 + bx + c = 0\) 是否有实数解,并按要求的格式输出。

在本题中输出有理数 \(v\) 时须遵循以下规则:

  • 由有理数的定义,存在唯一的两个整数 \(p\) 和 \(q\),满足 \(q > 0\),\(\gcd(p, q) = 1\) 且 \(v = \frac pq\)。

  • 若 \(q = 1\),则输出 {p},否则输出 {p}/{q},其中 {n} 代表整数 \(n\) 的值;

  • 例如:

    • 当 \(v = -0.5\) 时,\(p\) 和 \(q\) 的值分别为 \(-1\) 和 \(2\),则应输出 -1/2
    • 当 \(v = 0\) 时,\(p\) 和 \(q\) 的值分别为 \(0\) 和 \(1\),则应输出 0

对于方程的求解,分两种情况讨论:

  1. 若 \(\Delta = b ^ 2 - 4ac < 0\),则表明方程无实数解,此时你应当输出 NO

  2. 否则 \(\Delta \geq 0\),此时方程有两解(可能相等),记其中较大者为 \(x\),则:

    1. 若 \(x\) 为有理数,则按有理数的格式输出 \(x\)。

    2. 否则根据上文公式,\(x\) 可以被唯一表示为 \(x = q _ 1 + q _ 2 \sqrt r\) 的形式,其中:

      • \(q _ 1, q _ 2\) 为有理数,且 \(q _ 2 > 0\);
      • \(r\) 为正整数且 \(r > 1\),且不存在正整数 \(d > 1\) 使 \(d ^ 2 \mid r\)(即 \(r\) 不应是 \(d ^ 2\) 的倍数);

    此时:

    1. 若 \(q _ 1 \neq 0\),则按有理数的格式输出 \(q _ 1\),并再输出一个加号 +
    2. 否则跳过这一步输出;

    随后:

    1. 若 \(q _ 2 = 1\),则输出 sqrt({r})
    2. 否则若 \(q _ 2\) 为整数,则输出 {q2}*sqrt({r})
    3. 否则若 \(q _ 3 = \frac 1{q _ 2}\) 为整数,则输出 sqrt({r})/{q3}
    4. 否则可以证明存在唯一整数 \(c, d\) 满足 \(c, d > 1, \gcd(c, d) = 1\) 且 \(q _ 2 = \frac cd\),此时输出 {c}*sqrt({r})/{d}

    上述表示中 {n} 代表整数 {n} 的值,详见样例。

    如果方程有实数解,则按要求的格式输出两个实数解中的较大者。否则若方程没有实数解,则输出 NO

输入格式

输入的第一行包含两个正整数 \(T\) , \(M\) ,分别表示方程数和系数的绝对值上限。

接下来 \(T\) 行,每行包含三个整数 \(a, b, c\)。

输出格式

输出 \(T\) 行,每行包含一个字符串,表示对应询问的答案,格式如题面所述。

每行输出的字符串中间不应包含任何空格

样例 #1

样例输入 #1

9 1000
1 -1 0
-1 -1 -1
1 -2 1
1 5 4
4 4 1
1 0 -432
1 -3 1
2 -4 1
1 7 1

样例输出 #1

1
NO
1
-1
-1/2
12*sqrt(3)
3/2+sqrt(5)/2
1+sqrt(2)/2
-7/2+3*sqrt(5)/2

提示

【样例 #2】

见附件中的 uqe/uqe2.inuqe/uqe2.ans

【数据范围】

对于所有数据有:\(1 \leq T \leq 5000\),\(1 \leq M \leq 10 ^ 3\),\(|a|,|b|,|c| \leq M\),\(a \neq 0\)。

测试点编号 \(M \leq\) 特殊性质 A 特殊性质 B 特殊性质 C
\(1\) \(1\)
\(2\) \(20\)
\(3\) \(10 ^ 3\)
\(4\) \(10 ^ 3\)
\(5\) \(10 ^ 3\)
\(6\) \(10 ^ 3\)
\(7, 8\) \(10 ^ 3\)
\(9, 10\) \(10 ^ 3\)

其中:

  • 特殊性质 A:保证 \(b = 0\);
  • 特殊性质 B:保证 \(c = 0\);
  • 特殊性质 C:如果方程有解,那么方程的两个解都是整数。

从未想过有一天会栽在一元二次方程上(数学老师看到我这题0分肯定笑死我)

分析

没什么好分析的
大模拟就对了

标签:10,小苞,int,题解,站点,leq,苹果,csp
From: https://www.cnblogs.com/faruzan/p/18005680

相关文章

  • AT_ddcc2019_final_a 题解
    原题传送门题目描述:企鹅经过$1$个雪地方格需要$1$秒,经过$1$个冰地方格需要$\frac{1}{(k+2)}$秒。$k$是紧接着冰雪方格之前的冰雪方格数。在企鹅开始之前,高桥可以把$1$个雪方块变成冰方块。问企鹅离开起点后到达终点最少需要多少时间?思路分析:这道题是模拟+贪心......
  • P10125 「Daily OI Round 3」Simple题解
    原题传送门题目概述:给我们一个字符串,不区分大小写,让我们判断此字符串是与Acoipp等价,还是与Svpoll等价,或者是与前两者都不等价,并按题目条件输出。思路分析:我们只需要把此字符串的第一个字符转成大写,其他字符转成小写,并与那两个字符串进行比较就行了代码:#include<bits/st......
  • 2024牛客寒假算法基础集训营1个人补题题解(I)
    比赛链接:2024牛客寒假算法基础集训营1I、It'sbertrandparadox.Again!这么抽象的东西出得很好,下次别再出了。从bit和buaa不同的抽数规则可以得出一个结论:bit抽取具体坐标点的次数会明显小于buaa,甚至只有在几乎不可能的理想范围内两者抽取的次数才相近,因此因为样本量极大(1e5次......
  • P8330 [ZJOI2022] 众数 题解
    Description给定一个长度为\(n\)的序列\(a_1,a_2,\dots,a_n\),问选一段区间,它的价值是里面的众数个数\(+\)外面的众数个数,求最大价值,以及所有满足这个最大价值的区间的外面的众数颜色。\(\sumn\leq5\times10^5,n\leq2\times10^5\)。Solution考虑根号分治。定义一个......
  • 2024年2月6号题解
    P2872[USACO07DEC]BuildingRoadsS洛谷题目链接解题思路这个是一个最小生成树,把在平面直角坐标系中的点定义为顶点,把两个点的距离定义为边但这个题目并没有给出图中的边,也就是两个点的距离,因此我们要把这个图的边给补上,这个平面直角坐标系的点的每条边都是图上的边。但因......
  • 题解 AT_exawizards2019_e【Black or White】
    设\(P_b(k),P_w(k)\)表示已经吃了\(k\)块巧克力,把所有黑/白巧克力都吃光了的概率。枚举最后一块黑/白巧克力被吃的时间,容易得到:\[\begin{aligned}P_b(k)&=\sum_{i=1}^k\frac{\binom{i-1}{b-1}}{2^i}\\P_w(k)&=\sum_{i=1}^k\frac{\binom{i-1}{w-1}}{2^i}\\\end{aligned}\]......
  • 【题解】P5907 数列求和加强版 / P4948 数列求和
    本题解是对warzone的题解的补充。题意:求\[\sum_{i=1}^ni^ka^i\]普通版:\(k\leq2\times10^3\)。加强版:\(k\leq10^7\)。首先先考虑普通版。\[\begin{aligned}\sum_{i=1}^ni^ka^i&=\sum_{i=1}^na^i\sum_{j=0}^k{k\bracej}i^{\underline{j}}\\&=\sum_{j=0......
  • 蚯蚓排队题解
    蚯蚓排队题目描述蚯蚓幼儿园有\(n\)只蚯蚓。幼儿园园长神刀手为了管理方便,时常让这些蚯蚓们列队表演。所有蚯蚓用从\(1\)到\(n\)的连续正整数编号。每只蚯蚓的长度可以用一个正整数表示,根据入园要求,所有蚯蚓的长度都不超过\(6\)。神刀手希望这些蚯蚓排成若干个队伍,初始时,每只蚯......
  • Codeforces Round 921 (Div. 1) 题解
    HelloAd-HocForces!A字符集为前\(k\)个小写字母,给定长度为\(m\)的字符串,求所有的长度为\(n\)的字符串是否是这个字符串的子串。(此处字串不连续)如果不是需要给出反例。\(1\len,k\le26\),\(1\lem\le1000\)。\(\sumn,\summ\le10^6\)sol.D1A就是神秘贪心,汗流浃背......
  • U405333 帕鲁世界迷路的一天 题解
    题目链接:帕鲁世界迷路的一天前置弱化版:P3604美好的每一天题解一个非常简单的普通莫队解很容易写出来,具体的看我前置弱化版题解,然而这个复杂度高达\(O(26n\sqrt{q})\),显然无法通过强化版。一种看上去很正确的“假解”我们思考如何去掉这个\(26\),我们猜想:能够组成\(pre[c......