第一届"进化论杯"月赛 解题报告

Problem A: derivative

思路：水题。算出二阶导数，直接 printf 结果。

在求出二阶导数后可以不立刻化简，此时式中带有大量 e^(-x) 项。此时直接可以代入 ln|x0|，把式子丢给程序运算即可，能稍微提高解题速度。

代码：

#include<bits/stdc++.h>

#include<vector>

using namespace std;

typedef long long ll;

int read(){

	char ch=getchar();int x=0,f=1;

	while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}

	while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}

	return x*=f;

}

int main(){

	int n=read();

	while (n--){

		double x;

		scanf("%lf",&x);

		x=1/fabs(x);

		printf("%.3lf\n",(1+x)*(1+x)*(1+x)*(1+x)/(2.0*x*(1+x)*x-x*(1+x)*(1+x)));

	}

	return 0;

}

---

Problem B: fzuacmicpc

思路：水题。在环中找字符串并统计个数。复制字符串连接在末尾，然后枚举起点即可。

代码：

#include<bits/stdc++.h>

#include<vector>

using namespace std;

typedef long long ll;

int read(){

	char ch=getchar();int x=0,f=1;

	while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}

	while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}

	return x*=f;

}

char ss[200020];

int main(){

	cin>>ss;

	int len=strlen(ss);

	for (int i=0; i<len; i++){

		if (ss[i]<='Z') ss[i]+=32;

	}

	for (int i=0; i<len; i++){

		ss[len+i]=ss[i];

	}

	int ans=0;

	for (int i=0; i<len; i++){

		if (ss[i]=='f' && ss[i+1]=='z' && ss[i+2]=='u' && ss[i+3]=='a' &&ss[i+4]=='c' &&ss[i+5]=='m' &&ss[i+6]=='i' &&ss[i+7]=='c' && ss[i+8]=='p' && ss[i+9]=='c')

			ans++;

		if (ss[i]=='c' && ss[i+1]=='p' && ss[i+2]=='c' && ss[i+3]=='i' &&ss[i+4]=='m' &&ss[i+5]=='c' &&ss[i+6]=='a' &&ss[i+7]=='u' && ss[i+8]=='z' && ss[i+9]=='f')

			ans++;

	}

	cout<<ans;

	return 0;

}

---

Problem C: heroes

---

Problem D: ksubstring

思路：

代码：

#include<bits/stdc++.h>

using namespace std;

char ss[1000010];

int cnt[1000010][30];

int find(int l,int r,int k){

	if (l>r) return 0;

	int t=l-1,ans=0;

	int f=0;

	for (int i=l; i<=r; i++){

		int a=ss[i]-'a';

		if (cnt[r][a]-cnt[l-1][a]<k){

			f=1;

			ans=max(ans,find(t+1,i-1,k));

			t=i;

		}

	}

	if (f){

		ans=max(ans,find(t+1,r,k));

		return ans;

	}

	else return r-l+1;

}

int main(){

	int n,k;

	cin>>n>>k;

	scanf("%s",ss+1);

	int len=strlen(ss+1);

	for (int i=1; i<=len; i++){

		for (int j=0; j<=30; j++)

			cnt[i][j]=cnt[i-1][j];

		cnt[i][ss[i]-'a']++;

	}

	int ans=find(1,len,k);

	if (ans) printf("%d",ans);

	else printf("-1");

	return 0;

}

---

Problem E: magicwall

---

Problem F: monoid-group

思路：水题。虽然题目很长，但读完题目发现只需要模拟就能过。

代码：

#include<bits/stdc++.h>

#include<vector>

using namespace std;

typedef long long ll;

ll read(){

	char ch=getchar();ll x=0,f=1;

	while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}

	while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}

	return x*=f;

}

int num[1000010];

int main(){

	ll n=read(),k=read();

	for (int i=1; i<=n; i++)

		num[i]=n-i+1;

	ll tot=n*(n-1)/2;

	if (k==tot){

		printf("YES\n");

		for (int i=1; i<=n; i++)

			printf("%d ",num[i]);

		return 0;

	}

	for (int i=1; i<=n; i++){

		ll t=n-i+1;

		t=t*(t-1)/2;

		if (tot-t>k){

			i--;

			t=n-i+1;

			t=t*(t-1)/2;

			int res=(tot-t)-k,x=0;

			for (int j=i; j<=n; j++){

				num[j]=++x;

			}

			swap(num[i],num[i+res]);

			printf("YES\n");

			for (int j=1; j<=n; j++)

				printf("%d ",num[j]);

			return 0;

		}

	}

	printf("NO");

	return 0;

}

---

Problem G: ninja

思路：水题。虽然题目很长，但读完题目发现只要找到华丽值最大的边，然后在上面反复横跳k次即可。

计算华丽值：类似弗洛伊德；邻接表存图，每次枚举 i , j , k 判断（i，j）和（j，k）是否有边，若有，则（i，k）的华丽值加上（i，j）*（j，k）。

代码：

#include<bits/stdc++.h>

#include<vector>

using namespace std;

typedef long long ll;

ll read(){

	char ch=getchar();ll x=0,f=1;

	while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}

	while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}

	return x*=f;

}

ll p[210][210],v[210][210];

int main(){

	ll n=read(),m=read(),k=read();

	for (int i=1; i<=m; i++){

		ll a=read(),b=read(),c=read();

		v[a][b]=c;

		v[b][a]=c;

	}

	ll ans=0;

	for (int i=1; i<=n; i++){

		for (int j=1; j<=n; j++){

			ll tot=0;

			for (int k=1; k<=n; k++){

				if (v[i][k] && v[k][j]) tot+=v[i][k]*v[k][j];

			}

			ans=max(ans,tot);

		}

	}

	printf("%lld",ans*k);

	return 0;

}

---

Problem H: permutation-generation

思路：考场上思路不清晰，用了很奇怪的做法调试了很久才过。

代码：

咕咕咕