标题

思路

解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

J1A. 『FLA - III』Spectral

思路

模拟。当火焰的温度相同时，跳出循环并输出答案。

Code

#include <bits/stdc++.h>

using namespace std;

int T, n;
double k, t, p;

int main()
{
	scanf("%d", &T);
	while (T -- )
	{
		t = 0;
		scanf("%d %lf", &n, &k);
		for (int i = 1; i <= n; i ++ )
		{
			p = t;
			t = max(t, k + t / i);
			if (p == t)
				i = n;
		}
		printf("%.1lf\n", t);
	}
	return 0;
}

题解

思路

这题只需根据题目递推关系式,找规律即可

解题方法

我们从 $n=0$ 开始计算

$T_0=0$

$T_1=k$

$T_2=k+T_1/2=3/2 \times k$

$T_3=k+T_2/3=3/2 \times k$

$T_4=k+T_3/4=3/8 \times k=(3/(2 \times 4))\times k$

$T_5=k+T_4/5=3/40 \times k=(3/(2 \times 4 \times 5))\times k$

$T_6=k+T_5/6=3/240 \times k=(3/(2 \times 4 \times 5 \times 6))\times k$

我们设 $x =3/2k$

$T_0=0$

$T_1=1$

$T_2=x$

$T_3=x$

$T_n=(x \times (4 \times 5 \times 6 ... \times n))k$

众所周知,随着 $n$ 的变化, $(4 \times 5 \times 6 ... \times n))$ 越来越大,也就是除数越来越大.

而被除数不变,除数变大,商也就越来越小,即 $T_n$ 越来越小 .

可以看出,除 $T_2$ 到 $T_3$ 不变,其余 $T_n$ 的趋势为越来越小.

又因为 $3/2 \times k > k$ ,即 $T_2>T_1$

所以,当 $n=1$ 时,只能取 $T_0$ 或 $T_1$.

因为 $T_0=0$ , $T_1=k$ , $k>0$

所以 $T_1>T_0$

所以取 $T_1$ , 即 $k$ .

否则,即 $n>=2$时.

因为除 $T_2$ 到 $T_3$ 不变,其余 $T_n$ 的趋势为越来越小.

所以 $n>=2$ 时,答案取 $T_2$ 或 $T_3$ 时最大,即 $3/2 \times k$ .

时间复杂度:

添加时间复杂度, 示例： $O(1)$

空间复杂度:

添加空间复杂度, 示例： $O(1)$

Code

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        double k;
        cin>>k;
        double ans=k*3/2*1.00; //保留精度
        if(n!=1) printf("%.1lf\n",ans);
        else printf("%.1lf\n",k); //特殊情况
    }
    return 0;
}

模拟、数学

测试点 $1 \sim 2$

容易得到在 $n=1$ 时答案为 $k$，在 $n=2$ 时答案为 $1.5k$。

测试点 $3 \sim 4$

暴力计算 $T_1 \sim T_n$ 后取最大值。

测试点 $5$

序列 $T$ 的最大值是 $T_2$ 和 $T_3$，读者可以自行查看题解结尾处的证明。

当 $n=1$ 时答案为 $k$，否则答案为 $1.5k$。

单组数据时间复杂度 $O(1)$。

#include<bits/stdc++.h>
using namespace std;
int T,n,k;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        if(n==1) printf("%d.0\n",k);
        else if(k%2==0) printf("%d.0\n",k+k/2);
        else printf("%d.5\n",k+k/2);
    }
    return 0;
}

证明：若 $T_i > T_{i+1}$，由于 $T_{i+1}=k+ \dfrac{T_i}{i+1}$，$T_{i+2}=k+ \dfrac{T_{i+1}}{i+2}$，那么 $T_{i+2}-T_{i+1}=\dfrac{T_{i+1}}{i+2}- \dfrac{T_i}{i+1}<0$，因为 $\dfrac{T_{i+1}}{i+2}$ 的分母更大，分子更小。

因为 $T_{i+2}-T_{i+1}<0$，所以 $T_{i+1}>T_{i+2}$，又因为 $T_{i+1}>T_{i+2}$ 所以 $T_{i+2}>T_{i+3}$。以此类推，只要存在 $T_i > T_{i+1}$，那么对于所有大于 $i$ 的整数 $j$ 都有 $T_i > T_j$，又因为 $T_3 > T_4$，所以序列 $T$ 的最大值只可能在 $T_1,T_2,T_3$ 中取到，可知序列 $T$ 的最大值为 $T_2=T_3=1.5k$。

J1A 题解

第二篇题解。

此题按照题意模拟，当两次火焰的温度相同时即可跳出循环并输出答案。

代码：

#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        double k,t=0;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            double p=t;
            t=max(t,k+t/i);
            if(p==t)i=n;
        }
        printf("%.1lf\n",t);
    }
    return 0;
}

赛时用实时更新最大值并判断的方法通过了此题，现在证明一下这个算法的时间复杂度。

首先，我们可以将 $T_1 \sim T_n$ 都表示为 $(1 + \frac{p}{q})k$ 的形式，$T_1$ 显然是 $k$，$T_2$ 通过推导可得 $(1 + \frac{1}{2})k = \frac{3}{2}k$。随着 $i$ 的增加，$q$ 也随之增加，那么 $T_i$ 也会变得越来越小。对于 $i$ 在 $2 \sim n$ 中的 $T_i$，我们就有 $T_2 \ge T_3 \ge T_4 \ge T_5 \ge \ldots \ge T_n$，实际上从 $T_3$ 开始就已经满足严格单调递减了，所以这个算法最多会执行 $3$ 次，时间复杂度显然是 $O(1)$。

参考代码如下：

// #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define ll long long
#define writes(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n');
static char buf[100000], * pa(buf), * pb(buf);
int st[114], top;
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
void debug(auto st, auto ed, bool endline) {
	for (auto it = st; it != ed; ++it) {
		cout << *it << " ";
	}
	if (endline) cout << '\n';
}
template <typename T> void read(T& x) {
	T t = 0, sgn = 1;
	char ch = gc;
	while (!isdigit(ch)) {
		if (ch == '-') sgn = -sgn;
		ch = gc;
	}
	while (isdigit(ch)) {
		t = (t << 3) + (t << 1) + (ch ^ 48);
		ch = gc;
	}
	x = sgn * t;
}
template <typename T, typename ...Args> void read(T& tmp, Args &...tmps) {
	read(tmp); read(tmps...);
}
template <typename T> void write(T x) {
	if (x < 0) putchar('-'), x = -x;
	top = 0;
	while (x) {
		st[++top] = x % 10;
		x /= 10;
	}
	do {
		putchar(st[top--] + '0');
	} while (top > 0);
}
template <typename T, typename ...Args> void write(T& tmp, Args &...tmps) {
	writes(tmp);
	writes(tmps...);
}
template <typename T> T rand(T l, T r) {
	return rnd() % (r - l + 1) + l;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0)->sync_with_stdio(0);
	int t;
	cin >> t;
	while (t--) {
		ll n, k;
		cin >> n >> k;
		double ans = 0.0;
		double mxn = 0.0;
		for (int i = 1; i <= n; i++) {
			ans = (1.0 * k + 1.0 * ans / i);
			if (ans > mxn) {
				mxn = ans;
			}
			else break;
		}
		cout << fixed << setprecision(1) << mxn << '\n';
	}
}

J1A 题解

思路

通过找规律，发现：

• 当 $n = 0$ 时，答案为 $0.0$；
• 当 $n = 1$ 时，答案为 $k$；
• 当 $n > 1$ 时，答案为 $1.5k$。

复杂度

时间复杂度:

$O(1)$

空间复杂度:

$O(1)$

Code

#include <bits/stdc++.h>
int main() 
{
    int _t; std::cin >> _t;
    for(; _t; --_t) 
    {
        long double n, k;
        std::cin >> n >> k;
        long double ans;
        if(n == 0) ans = 0;
        else if(n == 1) ans = k;
        else ans = 1.5 * k;
        std::cout << std::fixed << std::setprecision(1) << ans << '\n';
    }
}

J1A题解

40分思路

暴力解决

复杂度

时间复杂度: $O(Tn)$，空间复杂度: $O(1)$

Code

#include <bits/stdc++.h>
using namespace std;
int i, j, k, n, T; double C;
int main() {
    scanf("%d", &T);
    for (i = 1; i <= T; i++) {
        scanf("%d %d", &n, &k);
        for (j = 1; j <= n; j++) C = C / j + k;
        printf("%.1lf\n", C);
    }
    return 0;
}

喜提TLE

80分思路

还是暴力，只不过加一个最大值

复杂度

时间复杂度: $O(Tn)$，空间复杂度: $O(1)$

Code

#include <bits/stdc++.h>
using namespace std;
int i, j, k, n, T; double C, c;
int main() {
    scanf("%d", &T);
    for (i = 1; i <= T; i++) {
        scanf("%d %d", &n, &k);
        for (j = 1; j <= n; j++) c = C / j + k, C = max(C, c);
        printf("%.1lf\n", C);
    }
    return 0;
}

又双叒叕敠敪喜提TLE

100分思路

打一个表，发现如下规律：
|$T_1$|$T_2$|$T_3$|$T_4$|$T_5$| |-----|-----|-----|-----|-----| |$k$|$\frac{3}{2}k$|$\frac{3}{2}k$|$\frac{11}{8}k$|$\frac{51}{40}k$|

整个序列 $\{T_n\}$ 的峰值在 $T_2$ 和 $T_3$。

复杂度

时间复杂度: $O(T)$，空间复杂度: $O(1)$

Code

#include <bits/stdc++.h>
using namespace std;
int i, k, n, T;
int main() {
    scanf("%d", &T);
    for (i = 1; i <= T; i++) {
        scanf("%d %d", &n, &k);
        if (n == 1) printf("%d.0\n", k);
        else if (k & 1) printf("%d.5\n", k + k / 2);
        else printf("%d.0\n", k + k / 2);
    }
    return 0;
}

终于AC了

Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        double k,t=0;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            double p=t;
            t=max(t,k+t/i);
            if(p==t)i=n;
        }
        printf("%.1lf\n",t);
    }
    return 0;
}
...

P10781 【MX-J1-T1】『FLA - III』Spectral 题解

大致思路：

这道题目最直接的方法就是暴力找最大值，显然会超时，接着就是进行打表，我们会发现，这道题的函数，是一个单峰函数，只会在一开始持续上升，在一定的位置持续下降，所以我们只需要找到那个转折点，直接退出即可。

代码实现：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int N = 5e5 + 10;
inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
int T;
signed main() {
	T = read();
    while (T--) {
        double k, res = 0;
        int n;
        n = read();
        cin >> k;
        if(n == 1) cout << fixed << setprecision(1) << k << "\n";
        else{
			for (int i = 1;i <= n; ++ i)
			{
				if(k + res / i < res) break;
				else res = k + res / i;
			}
			cout << fixed << setprecision(1) << res << "\n";
        }
    }
    return 0;
}

这样这道题目就完成啦！！！

由于此题 $t,n,k$ 都很（hen）大，所以易得是奇思妙想题。

打个表 ： |烧炭数$i$|$T_i$| |:---:|:---:| |$0$|$0$| |$1$|$k$| |$2$|$1.5k$| |$3$|$1.5k$| |$4$|$1.375k$| 容易发现，$T_i$ 在烧2块时达到峰值

所以直接算，特判 $n=1$ 就行

代码如下：

#include<bits/stdc++.h>
using namespace std;
double ans,f; 
signed main(){
	int t,n,k;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&k);
		ans=0;f=0;
		if(n<2)ans=k;
		else ans=1.5*k; 
		printf("%.1lf\n",ans);
	} 
	return 0; 
} 

标题 P10781 【MX-J1-T1】『FLA - III』Spectral 题解

大致思路：