“蔚来杯“2022牛客暑期多校训练营2

Fly

G.Link with Monotonic Subsequence

题意：
对于每个样例，给出一个数字n。从1-n构成一个排列。一个排列的价值=max(最长上升子序列长度，最长下降子序列长度)，输出一个序列，使得这个排列的价值最小。

思路：
要尽量使得一个排列中的最长上升子序列长度和最长下降子序列长度都很小。我们的一个思路是先将1,2,```,n这个序列进行分组，再将这些组按降序排列，那么这样的话，因为每组内是严格递增的，这样就能控制最长上升子序列长度，又因为组间按降序排列，这样又可以控制最长下降子序列长度。综上所述，就是组内升序，组间降序。那么最后得到的价值最小其实就是len=ceil(sqrt(n))。
那么如何进行分组呢？每组怎么分呢？每组各有多少个呢？
我们想的是使每组内的元素为len=ceil(sqrt(n))个，最后一组元素个数<=len个，再将组间按降序排。比如一个初始为1，2，3，4，5，6的排列，
那么确保组内元素最大为ceil(sqrt(6))=3个，那么就变成[1,2,3][4,5,6]两组，再将组间按降序排列，变成[4 5 6] [1 2 3]。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline void solve(){
    int n;
    scanf("%d",&n);
    double len=ceil(sqrt(n));
    for(int i=n%int(len);i>=1;i--){//如果不能将n平均分，那么先将最后的余数个输出 
        cout<<n-i+1<<" ";
    }
    for(int i=n/len;i>=1;i--){//再降序输出够len个数的组  组数：降序 
        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的数组a（告诉每个数ai），想改变这些数使得这个数组成为等差数列ai=a1+(i−1)d。求出sum(ai’-ai)^2

思路：
考察最小二乘法，求残差平方和。
即x为1-n,对应的y为a1-an，先求出拟合的直线，再求出每个x对应的直线上的点，再求残差，累计残差平方和。

注意：
需要用到题目中给出的来进行数据输入。
还需要用到long double来控制精度，否则会错误。

代码：

#include <bits/stdc++.h>
#include <cstdio>
#include <cctype>
#include <vector>
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 GTI;
using namespace std;




typedef long long ll;
typedef long double ld;
using Parameter = struct {
	ld k; // 斜率
	ld b; // 截距
};
 
// 最小二乘法计算过程
bool LeastSquares(std::vector<ld>& X, std::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 = std::accumulate(X.begin(), X.end(), 0.0) / vec_size;
	ld y_avg = std::accumulate(Y.begin(), Y.end(), 0.0) / vec_size;
 
	for (int i = 0; i < vec_size; ++i) {
		sum1 += (X.at(i) * Y.at(i) - x_avg * y_avg);
		sum2 += (X.at(i) * X.at(i) - x_avg * x_avg);
	}
 
	param.k = sum1 / sum2;
	param.b = y_avg - param.k * x_avg;
	return true;
}
ld a[100005];
// 主函数
int main(int argc, char* argv[])
{
	int t;
// 	cin>>t;
    t=gti();
	while(t--){
		ll n;
// 		cin>>n;
        n=gti();//输入
		Parameter param{ 0, 0 };
		vector<ld> x_vec,y_vec;
		for(int i=1;i<=n;i++){
// 			cin>>a[i];
            a[i]=gti();//输入
			x_vec.push_back(i);
			y_vec.push_back(a[i]);
		}
		LeastSquares(x_vec, y_vec, param);
//         printf("y=%lfx+%lf\n",param.k,param.b);
        ld yi,ans=0;
        for(int i=1;i<=n;i++){
            yi=param.k*i+param.b;//计算出x对应到直线上的y值
            ans+=(yi-a[i])*(yi-a[i]);//累计残差平方和
        }
		printf("%.15llf\n",ans);
		
	}
}

K.Link with Bracket Sequence I

题意：
给出一个长度为n的括号子序列a，问有多少种可能的长度为m的原序列。

考察：
动态规划，字符串匹配

思路：
设置一个三维数组，dp[i][j][k]代表字符串长度为i,匹配长度为j，左括号比右括号多的数目为k时的答案。
当是左括号时，可以任意匹配。
当是右括号是，只有当左括号数目>右括号数目时才可以匹配。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 210;
const int mod = 1e9+7;
int n,m,f[N][N][N];
char s[N];
void add(int &x,int y){//传引用，改变x
	x=(x+y)%mod;
}

inline void solve(){
    scanf("%d%d%s",&n,&m,s+1);
    //先初始化为0 
    for(int i=0;i<=m;i++){
    	for(int j=0;j<=n;j++){
    		for(int k=0;k<=m;k++){
    			f[i][j][k]=0;
			}
		}
	}
	f[0][0][0]=1;//初始化为1 
	for(int i=0;i<m;i++){//枚举字符串长度 
		for(int j=0;j<=n;j++){//枚举匹配成功的长度 
			for(int k=0;k<=i;k++){// 枚举左括号比右括号多的数量
			    //如果是左括号，任何时候都可以匹配 字符串长度+1，左括号比右括号多的数目+1 
				add(f[i+1][j+(s[j+1]=='(')][k+1],f[i][j][k]);
				//只有当左括号数量>右括号数量时，才进行右括号匹配 字符串长度+1，左括号比右括号多的数目-1
				if(k) add(f[i+1][j+(s[j+1]==')')][k-1],f[i][j][k]);
			}
		}
	}
	//答案就是字符串长度为m，匹配长度为n,左括号与右括号数目相等时的f值 
	printf("%d\n",f[m][n][0]);
}

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

Link with Game Glitch

题意：
求出一个最大的w，使得不存在循环。

考察：
图论，用Bellman-Ford算法判断是否存在负环

思路：
考虑建图
对于每个物品建点，每个合成方式由 bi 向 di 建有向边，边权为 ci/ai 。
原问题实际上是要求一个最大的 w ，使得在每条边的边权乘上 w 之后，
不存在一个乘积大于 1 的环。
要求最大的w，那么就需要二分答案，check 的问题类似于求负环。由于边权乘积较大，需要
对其取对数。

技巧：
（1）数字太大就取对数
（2）正难则反，取相反数变成负边权，转化为求是否存在负环回路。

Bellman-Ford算法解决负边权问题

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010,M=2010;
const double eps=1e-9;
//对每个物品建点，每个合成方式从bi向di建有向边，边权为ci/ai 
int n,m,a[M],b[M],c[M],d[M];
double dis[N],w[M];


int Bellman_Ford(){
	for(int i=1;i<=n;i++) dis[i]=0.0;//dis数组初始化顶点u到各个顶点的距离，初始化为0 
	for(int i=1;i<n;i++){//外循环n-1次,n为顶点的个数 
		int f=0;
		for(int j=1;j<=m;j++){//内循环m次，m为边的条数 
		//每轮对输入的边进行松弛，更新dis数组 
			if(dis[b[j]]+w[j]<dis[d[j]]){
				dis[d[j]]=dis[b[j]]+w[j];
				f=1;//有负权回路 
			}
		}
		if(f==0) return 0;
	}
	return 1;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
    	scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
	}
	double L=0.0,R=1.0;
	while(R-L>eps){//二分答案
		double mid=(L+R)/2.0;
		for(int i=1;i<=m;i++){
			w[i]=-log(1.0*mid*c[i]/a[i]);//因为mid与边权c[i]/a[i]的乘积可能会很大，因此取对数，再取相反数，变成判断是否有负环 
		}
		if(Bellman_Ford()==0) L=mid;
		else R=mid;
	}
	printf("%.10lf\n",L);
	return 0;
}