2022牛客多校2

2022牛客多校2

• G Link with Monotonic Subsequence
• 代码：
• J Link with Arithmetic Progression
• 代码

G Link with Monotonic Subsequence

题意：

由从 1 到 n 的 n 个不同整数以某种顺序构造，使其最大上升子序列和最大下降子序列的长度的最大值最小。

思路：

类似是打表找规律，一开始是猜$\frac{n}{2}\backslash frac\{n\}\{2\}$,但发现n=5，$\max (\mathrm{l}\mathrm{i}\mathrm{s}(p),\mathrm{l}\mathrm{d}\mathrm{s}(p))\backslash max(\{\backslash rm\; lis\}(p),\{\backslash rm\; lds\}(p))$是3，n=7时也是3，于是就猜可能是$\lceil \sqrt{n}\rceil \backslash lceil\backslash sqrt\{n\}\backslash rceil$。 再找规律构造，先对1~n从小到大排序，再分成$\frac{n}{\lceil \sqrt{n}\rceil }\backslash frac\{n\}\{\backslash lceil\backslash sqrt\{n\}\backslash rceil\}$组，每组有$\lceil \sqrt{n}\rceil \backslash lceil\backslash sqrt\{n\}\backslash rceil$个数，最后特别处理一下最后一组，因为个数可能不够。分好组之后从大到小排序即可。所以$\mathrm{l}\mathrm{i}\mathrm{s}(p)\{\backslash rm\; lis\}(p)$为$\lceil \sqrt{n}\rceil \backslash lceil\backslash sqrt\{n\}\backslash rceil$，$\mathrm{l}\mathrm{d}\mathrm{s}(p)\{\backslash rm\; lds\}(p)$为$\frac{n}{\lceil \sqrt{n}\rceil }\backslash frac\{n\}\{\backslash lceil\backslash sqrt\{n\}\backslash rceil\}$。

代码：

using namespace std;
typedef long long ll;
inline void solve(){
    int n;
    scanf("%d",&n);
    double len=ceil(sqrt(n));
    //cout<<len<<endl;
    for(int i=n%int(len);i>=1;i--){
        cout<<n-i+1<<" ";
    }
    for(int i=n/len;i>=1;i--){
        for(int j=1;j<=len;j++){
            int x=(i-1)*len;
            cout<<x+j<<" ";
        }
    }
    cout<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	scanf("%d",&t);
	while(t--){
		solve();
	}
	return 0;
}

J Link with Arithmetic Progression

题意：

给定一个序列，可以对每个数进行更改，使序列变为一个等差数列，并且残差平方和最小。

思路： 可以把序列看成n个点，把n个点拟合成直线，就可以让序列变为一个等差数列，而用最小二乘法拟合则可让残差平方和最小。最小二乘法拟合的直线斜率为

$k=\frac{{\sum }_{i=1}^n(x_i{y}_i-\bar{x}\bar{y})}{{\sum }_{i=1}^n(x_i^2-{\bar{x}}^2)}k=\backslash frac\{\backslash sum\_\{i=1\}^\{n\}(x\_\{i\}y\_\{i\}-\backslash bar\{x\}\backslash bar\{y\})\}\{\backslash sum\_\{i=1\}^\{n\}(x\_\{i\}^2-\backslash bar\{x\}^2)\}$

$b=y_i-k\ast x_{i}b=y\_\{i\}-k*x\_\{i\}$

最后遍历一遍求残差平方和即可。

注意：题目要求用gti()和getchat()用法类似，double精度不够用long double。

代码

#include <vector>
#include <numeric>
#include <cstdio>
#include <cctype>
typedef long double ld ;
namespace GTI
{
    char gc(void)
       {
        const int S = 1 << 16;
        static char buf[S], *s = buf, *t = buf;
        if (s == t) t = buf + fread(s = buf, 1, S, stdin);
        if (s == t) return EOF;
        return *s++;
    }
    int gti(void)
       {
        int a = 0, b = 1, c = gc();
        for (; !isdigit(c); c = gc()) b ^= (c == '-');
        for (; isdigit(c); c = gc()) a = a * 10 + c - '0';
        return b ? a : -a;
    }
}
using GTI::gti;
using namespace std;
struct Parameter   {
	ld k; 
	ld b; 
};
 
bool LeastSquares(vector<ld>& X, vector<ld>& Y, Parameter& param)
{
	if (X.empty() || Y.empty())
		return false;
 
	int vec_size = X.size();
	ld sum1 = 0, sum2 = 0;
	ld x_avg = accumulate(X.begin(), X.end(), 0.0) / vec_size;
	ld y_avg = accumulate(Y.begin(), Y.end(), 0.0) / vec_size;
 
	for (int i = 0; i < vec_size; ++i) {
		sum1 += (X[i] * Y[i] - x_avg * y_avg);
		sum2 += (X[i] * X[i] - x_avg * x_avg);
	}
 
	param.k = sum1 / sum2;
	param.b = y_avg - param.k * x_avg;
	return true;
}
int t,n,a[100005];

void solve(){
    n=gti();
    vector<ld> x_vec ;
	vector<ld> y_vec ;
    for(int i=1;i<=n;i++){
        a[i]=gti();
        x_vec.push_back(ld(i));
        y_vec.push_back(ld(a[i]));
    }
    Parameter param{ 0, 0 };
	LeastSquares(x_vec, y_vec, param);
    ld ans=0;
    for(int i=1;i<=n;i++){
        ans+=(a[i]-(param.k*i+param.b))*(a[i]-(param.k*i+param.b));
    }
	printf("%0.15llf\n",ans);
} 

int main()
{
    t=gti();
    while(t--){
        solve();
    }
	
 
}