• 2022牛客暑期多校训练营2 个人题解

    title :2022牛客暑期多校训练营2 题解
    date : 2022-8-16
    tags : ACM,练习记录
    author : Linno

    2022牛客暑期多校训练营2 题解

    题目链接 ：https://ac.nowcoder.com/acm/contest/33186

    补题进度 ：9/11

    A - Falfa with Polygon

    设 f k [ i ] [ j ] 表示长度为 k 的从 i 开始到 j 结束的子序列最大长度，状态转移方程为 : f k [ i ] [ j ] = { d i s ( i , j ) , k = 2 m a x t { f k − 1 [ i ] [ t ] + f 2 [ t ] [ j ] } , k ≥ 3 设f_k[i][j]表示长度为k的从i开始到j结束的子序列最大长度，状态转移方程为:\\ f_k[i][j]=

    {dis(i,j),k=2maxt{fk−1[i][t]+f2[t][j]},k≥3" role="presentation" style="position: relative;">{dis(i,j),k=2maxt{fk−1[i][t]+f2[t][j]},k≥3
    设fk​[i][j]表示长度为k的从i开始到j结束的子序列最大长度，状态转移方程为:fk​[i][j]={dis(i,j),k=2maxt​{fk−1​[i][t]+f2​[t][j]},k≥3​

    带有{max,+}运算的dp转移可以用矩阵快速幂优化，然后注意到关于决策点t具有决策单调性，可以直接将复杂度降为 O ( n 2 l o g k ) O(n^2logk) O(n2logk)

    #include
#define inf 0x3f3f3f3f

using namespace std;
typedef long long ll;
const int N=2007;
const int mod=1e9+7;

double x[N],y[N];

struct Matrix{
	int n,m;
	vector<vector<double>>a;
	Matrix(){}
	Matrix(int n,int m):n(n),m(m){a.resize(n,vector<double>(m,0));}
	Matrix operator *(const Matrix &s)const{
		Matrix ans=Matrix(n,s.m);
		vector<vector<int> >p(n,vector<int>(m,0));
		for(int i=0;i<n;++i) p[i][i]=i;
		for(int len=1;len<=n;++len){
			for(int i=0;i+len<n;++i){
				for(int j=i+len,k=j?p[i][j-1]:0;k<=p[i+1][j];++k){
					if(ans.a[i][j]<a[i][k]+s.a[k][j]){
						ans.a[i][j]=a[i][k]+s.a[k][j];
						p[i][j]=k;
					}
				}
			}
		}
		return ans;
	}
};

Matrix fpow(Matrix a,ll b){
	Matrix ans=Matrix(a.n,a.m);
	while(b){
		if(b&1) ans=ans*a;
		a=a*a;
		b>>=1;
	}
	return ans;
}

inline double dis(int i,int j){
	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}

void Solve(){
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;++i) scanf("%lf%lf",x+i,y+i);
	Matrix bas=Matrix(n,n);
	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			bas.a[i][j]=dis(i,j);
		}
	}
	Matrix ans=fpow(bas,k-1);
	double mx=0;
	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j) mx=max(mx,ans.a[i][j]+dis(i,j));
	}
	printf("%.10lf\n",mx);
}

signed main(){
	int T=1;
	while(T--){
		Solve();
	}
	return 0;
}



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74

    B - light

    C - Link with Nim Game

    一般Nim游戏结论：异或和为0必败，否则必胜。那么先手把必败态转移为必胜态，只需要将异或和为1的数位变成另即可。①考虑必败的情况下，我们要尽量延长回合数，实际上任取一个即可，因为对手必须把最低位异或和变为0，因此也只能减一个。特殊地，初始操作时如果有某一堆存在两个连续的1会使得使得对手可以取多个石子，emofunc哥哥有比较详细的证明，用一个函数check一下即可。考虑必胜的情况下，对方会让我们进入只能取一个的局面，所以就是问我们第一步最多能取多少个，有多少种取法，因此记录最高的lowbit(a[i])使得s^lowbit(a[i]) 

    #include
#define lb(x) (x&(-x))
#define int long long
using namespace std;
const int N=1e5+7;
int n,a[N],T,s,sum;

map<int,int>V;

inline bool check(int x){
	if(V.count(x)) return V[x];
	for(int i=1;i<=n;++i){
		if((a[i]&x)&&a[i]&(x-1)) return V[x]=0;
	}
	return V[x]=1;
} 

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		sum=0;s=0;
		for(int i=1;i<=n;++i){
			cin>>a[i];
			sum+=a[i]; 
			s^=a[i];
		}
		if(!s){
			V.clear();
			int ans=0;
			for(int i=1;i<=n;++i){
				int t=lb(a[i]);
				if(check(t)) ++ans;
			}
			printf("%lld %lld\n",sum,ans);
		}else{
			int mx=0,ans=0;
			for(int i=1;i<=n;++i){
				if((a[i]^s)>=a[i]) continue;
				int t=a[i]-(s^a[i]);
				if(t>mx) mx=t,ans=1;
				else if(t==mx) ++ans; 
			}
			printf("%lld %lld\n",sum-mx+1,ans);
		}
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    D - Link with Game Glitch

    一个很经典的二分+Spfa，比赛时我忘记了有取对数变成加法来进行松弛的操作wa了一发，然后我把松弛的乘法换成了除法精度就够了。（不知道能不能被卡掉）

    //#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
//#define int long long
#define eps 1e-10
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
struct E{
	int v;
	double w1,w2;
	int nxt; 
}e[N<<1];
int cnt=0,head[N];
inline void addedge(int u,int v,double a,double c){
	e[++cnt]=(E){v,a,c,head[u]};head[u]=cnt;
}

int n,m,b[N],d[N],inq[N],num[N];
double L=0,R=1,M;
double a[N],c[N],has[N];

inline bool check(double x){
	queue<int>q;
	for(int i=1;i<=n;++i) inq[i]=0,num[i]=0;
	for(int i=1;i<=n;++i) has[i]=1.0,q.push(i);
	while(q.size()){
		int fro=q.front();
		q.pop();
		inq[fro]=0;
		for(int i=head[fro];i;i=e[i].nxt){
			int v=e[i].v;double w1=e[i].w1,w2=e[i].w2;
			if(has[v]*w1<=has[fro]*M*w2){
				has[v]=has[fro]*M*w2/w1;
				num[v]++;
				if(num[v]>n+1) return 0;
				if(!inq[v]) inq[v]=1,q.push(v);
			}
		}
	}
	return 1;
}

void Solve(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%lf%d%lf%d",&a[i],&b[i],&c[i],&d[i]);
		addedge(b[i],d[i],a[i],c[i]);
	}
	while(R-L>eps){
		M=(L+R)/2;
		if(check(M)) L=M;
		else R=M;
	}
	printf("%.10lf\n",L);
}

signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
//	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78

    E - Falfa with Substring

    设 G n , k G_{n,k} Gn,k​表示长度为n的字符串至少有k个bit子串，方案数为 G n , k = C n − 2 k k ∗ 2 6 n − 3 k G_{n,k}=C_{n-2k}^k*26^{n-3k} Gn,k​=Cn−2kk​∗26n−3k，利用容斥推除长度为n的字符恰好有k个bit子串方案数为 F n , k = ∑ j ≥ k ( − 1 ) j − k C j k F_{n,k}=\sum_{j\ge k}(-1)^{j-k}C_j^k Fn,k​=∑j≥k​(−1)j−kCjk​。经典地多项式卷积，可化为 k ! F n , k = ∑ j ≥ k H n , n − j + k j ! G n , j k!F_{n,k}=\sum_{j\ge k}H_{n,n-j+k}j!G_{n,j} k!Fn,k​=∑j≥k​Hn,n−j+k​j!Gn,j​,套一个NTT卷积即可。

    //#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e6+7;
const int mod=998244353,g=3,gi=332748118;
//998244353的一个原根为3,3在模此数意义下逆元为332748118 

int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}

int n,m,lim,ln,pw[N],F[N],G[N],rev[N],frac[N],invf[N],ans[N];

inline int fpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

inline int inv(int x){
	return fpow(x,mod-2);
}

inline int C(int n,int m){
	if(n<m) return 0;
	return frac[n]*invf[m]%mod*invf[n-m]%mod;
}=
void NTT(int *a,int op) {
    for (int i=0;i<lim;i++){
        if (i<rev[i]) swap(a[i],a[rev[i]]); 
    }
    for (int i=1;i<lim;i<<=1) {
        int w=fpow(3,(mod-1)/(i<<1));
        if (op==-1) w=fpow(w,mod-2); 
        for (int j=0;j<lim;j+=(i<<1)){
            int wn=1; 
            for (int k=j;k<i+j;k++) {
                int t=a[i+k]*wn%mod;
                a[i+k]=(a[k]+mod-t)%mod;
                a[k]=(a[k]+t)%mod;
                wn=wn*w%mod; 
            }
        }
    }
    if(op==-1){
        int invL=fpow(lim,mod-2);
        for(int i=0;i<lim;i++){
            a[i]=a[i]*invL%mod;
        }
    }
}

void Solve(){
	cin>>n;
	m=n/3;
	pw[0]=1;frac[0]=1;
	for(int i=1;i<=n;++i) pw[i]=pw[i-1]*26%mod;
	for(int i=1;i<=n;++i) frac[i]=frac[i-1]*i%mod;
	invf[n]=inv(frac[n]);
	for(int i=n;i>=1;--i) invf[i-1]=invf[i]*i%mod; 
	for(int i=0;i<=m;++i) F[i]=C(n-2*i,i)*pw[n-3*i]%mod*frac[i]%mod;
	for(int i=0;i<=m;++i) G[m-i]=invf[i]*fpow(mod-1,i)%mod;
	for(lim=1,ln=0;lim<=m+m;lim<<=1,ln++);
	for(int i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(ln-1));
	NTT(F,1);NTT(G,1);
	for(int i=0;i<lim;++i) F[i]=F[i]*G[i]%mod;
	NTT(F,-1);
	for(int i=0;i<=m;++i) ans[i]=F[i+m]*invf[i]%mod;
	for(int i=0;i<=n;++i) cout<<ans[i]<<" ";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
//	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94

    F - NIO with String Game

    感觉好复杂了没写。

    G - Link with Monotonic Subsequence

    很直观地能看出上升的段最多不超过根号级别，根据这个感觉把数列设成阶梯状就行了。

    #include 
using namespace std;
int T,n,cnt,f[1000005];
int main()
{
    cin>>T;
    while (T--)
    {
        scanf("%d",&n);
        int t=sqrt(n);
        if (t*t<n) t++;
        cnt=0;
        for (int i=1;i<=n;i+=t)
        {
            for (int j=min(n,i+t-1);j>=i;j--)
                f[++cnt]=j;
        }
        for (int i=1;i<=n;++i)
            printf("%d ",f[i]);
        printf("\n");
        
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    H - Take the Elevator

    把上电梯和下电梯的人分成两堆，每轮贪心地去选人并且送到当轮的最高点，用两个堆来维护即可。

    //#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}

struct node{
	int a,b,id;
	bool operator <(node B)const{
		return b<B.b;
	}
	bool operator >(node B)const{
		return a<B.a;
	}
}s[N];

bool cmp1(node A,node B){  //向上按结束楼层小优先 
	return A.b>B.b; 
}
bool cmp2(node A,node B){ //向下按结束楼层大优先 
	return A.a>B.a; 
}

int n,m,k,vis[N];
vector<node>up,down;
priority_queue<node,vector<node>,greater<node> >q1;
priority_queue<node>q2;

void Solve(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;++i){
		cin>>s[i].a>>s[i].b;
		s[i].id=i;
		if(s[i].a<=s[i].b) up.emplace_back(s[i]);
		else down.emplace_back(s[i]);
	}
	sort(up.begin(),up.end(),cmp1);
	sort(down.begin(),down.end(),cmp2);
	int ans=0;
	while(1){
		while(q1.size()) q1.pop();
		while(q2.size()) q2.pop();
		bool flag=0;
		int mx=0;  //该轮需要达到的最大高度 
		for(int i=0;i<up.size();++i){
			if(vis[up[i].id]) continue;
			flag=1;
			while(q1.size()&&q1.top().a>=up[i].b) q1.pop();
			if(q1.size()<m){
				mx=max(mx,up[i].b);
				q1.push(up[i]);
				vis[up[i].id]=1;
			}
		}
		for(int i=0;i<down.size();++i){
			if(vis[down[i].id]) continue;
			flag=1;
			while(q2.size()&&q2.top().b>=down[i].a) q2.pop();
			if(q2.size()<m){
				mx=max(mx,down[i].a);
				q2.push(down[i]);
				vis[down[i].id]=1;
			}
		}
		if(!flag) break;
		ans+=(mx-1)*2;
	}
	cout<<ans<<"\n";
}

signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
//	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93

    I - let fat tension

    如果求两两点对之间的效率则是 O ( n 2 ) O(n^2) O(n2)的复杂度，考虑分别构建三个大小分别为(n,k),(k,n)和(n,d)的矩阵，其效果为相乘等价于求 ∑ i − 1 n x i ⋅ x j ∣ x i ∣ ∣ x j ∣ \sum_{i-1}^n\frac{x_i·x_j}{|x_i||x_j|} ∑i−1n​∣xi​∣∣xj​∣xi​⋅xj​​，就可以用 O ( 2 k n d ) O(2knd) O(2knd)的复杂度求解。重点：利用结合律尽量减少矩阵运算。

    #include
using namespace std;
struct Matrix{
	int n,m;
	vector<vector<double>>a;
	Matrix(){}
	Matrix(int n,int m):n(n),m(m){a.resize(n,vector<double>(m,0));}
	Matrix operator *(const Matrix &b)const{
		Matrix res=Matrix(n,b.m);
		for(int i=0;i<n;++i){
			for(int j=0;j<b.m;++j){
				for(int k=0;k<m;++k){
					res.a[i][j]+=a[i][k]*b.a[k][j];
				}
			}
		}
		return res;
	}
};

signed main(){
	int n,k,d;
	scanf("%d%d%d",&n,&k,&d);
	Matrix A=Matrix(n,k),B=Matrix(k,n),C=Matrix(n,d);
	for(int i=0;i<n;++i){
		double sum=0;
		for(int j=0;j<k;++j){
			scanf("%lf",&A.a[i][j]);
			sum+=A.a[i][j]*A.a[i][j];
		}
		sum=sqrt(sum);
		for(int j=0;j<k;++j){
			A.a[i][j]/=sum;
			B.a[j][i]=A.a[i][j];
		}
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<d;++j){
			scanf("%lf",&C.a[i][j]);
		}
	}
	Matrix ans=B*C;
	ans=A*ans;
	for(auto i:ans.a){
		for(auto j:i) printf("%.8lf ",j);
		printf("\n");
	}
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    J - Link with Arithmetic Progression

    高中知识，最小二乘法。

    #include 
#include 
#define double long double
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;
int T,n,b[100005];
int main(){
     //Use gti() to get next int from standard input.
    T=gti();
    //scanf("%d",&T);
    while (T--)
    {
        n=gti();
        //scanf("%d",&n);
        double sum=0;
        double cc=0;
        double sq=0;
        for (int i=1;i<=n;++i)
        {
            b[i]=gti();
            //scanf("%d",&b[i]);
            sum+=(double)b[i];
            if(i>1)
            {
                cc+=(i-1)*(double)b[i];
            }
            if (i<n) sq+=(double)i*(double)i;
        }
        double dd=(2.0*cc-((double)n*1.0-1.0)*sum)/(2.0*sq-(double)n*1.0*(double)(n-1.0)*(double)(n-1.0)/2.0);
        double A=(sum-n*(n-1.0)*1.0*dd/2.0)/(n*1.0);
        double ans=0;
        for (int i=1;i<=n;++i)
        {
            ans+=(b[i]-A)*(b[i]-A);
            //printf("%.8lf ",A);
            A+=dd;
        }
        printf("%.10Lf\n",ans);
    }
    return  0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    K - Link with Bracket Sequence I

    区间dp，设 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示最终补成长度为i的字符串，已经匹配了a串中的的j个，并且剩余未匹配的左括号数为k时的方案数，那么分别枚举i,j,k，并且判断str[j]是左括号还是右括号分别进行转移即可。

    //#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
//#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=207;
const int mod=1e9+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
int n,m,dp[N][N][N];
string str;

void Solve(){
	cin>>n>>m;
	cin>>str;
	for(int i=0;i<=m;++i){
		for(int j=0;j<=n;++j){
			for(int k=0;k<=m;++k){
				dp[i][j][k]=0;
			}
		}
	}
	dp[0][0][0]=1;
	for(int i=0;i<=m;++i){
		for(int j=0;j<=n;++j){
			for(int k=0;k<=i;++k){
				if(k){
					if(str[j]==')') dp[i+1][j+1][k-1]=(dp[i+1][j+1][k-1]+dp[i][j][k])%mod; 
					else dp[i+1][j][k-1]=(dp[i+1][j][k-1]+dp[i][j][k])%mod;
				}
				if(str[j]=='(') dp[i+1][j+1][k+1]=(dp[i+1][j+1][k+1]+dp[i][j][k])%mod;
				else dp[i+1][j][k+1]=(dp[i+1][j][k+1]+dp[i][j][k])%mod;
			//	cout<<"dp["<
			}
		}
	}
	cout<<dp[m][n][0]<<"\n";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    L - Link with Level Editor I

    又是一个dp, d p [ i ] [ j ] dp[i][j] dp[i][j]表示在第i个师姐中到达j点，最晚可以从哪个世界出发，转移实际上就是和前面的世界取一个max，那么枚举第i个世界时，答案就是i-f[m]+1，这题卡空间，然后我们滚动掉第一维即可。

    //#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
int n,m;
//记 dp[i,j]表示在第i个世界中到达点j,最晚可以从哪个世界出发。
void Solve(){
	cin>>n>>m;
	int ans=n+1;
	vector<int>f(m+1,-1);
	for(int i=1,l;i<=n;++i){
		cin>>l;
		vector<int>g(f);
		f[1]=i;
		for(int j=1,u,v;j<=l;++j){
			cin>>u>>v;
			g[v]=max(g[v],f[u]);
		}
		f.swap(g);
		if(f[m]!=-1) ans=min(ans,i-f[m]+1);
	}
	if(ans>=n+1) cout<<"-1\n";
	else cout<<ans<<"\n";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
//	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
  • 相关阅读:
    高分辨空间代谢组学测试的样品要求以及常见问题
    Shell中括号的含义
    修改conda 虚拟环境下的PS1提示符格式
    java毕业设计百分百教育集团教务管理系统设计Mybatis+系统+数据库+调试部署
    磺胺甲恶唑肌SMZ白蛋白纳米粒|磺胺嘧啶豆清SD白蛋白纳米粒|真菌疏水蛋白修饰PLGA载姜黄素纳米粒
    Flink-看完就会flink基础API
    Mysql 5.7 新特性之 json 类型的增删改查
    高保链路分析——一看就会
    新生宝宝为何天生过敏体质 婴儿过敏体质的症状
    算法沉淀——动态规划之子数组、子串系列（上）（leetcode真题剖析）
  • 原文地址：https://blog.csdn.net/SC_Linno/article/details/126835516