Stilwell's Blog

趁没人在的时候刷rating

比赛刚开始的时候CH挂了，本来做的人就少，干脆就基本消失了

于是只切了两道就感觉稳稳的涨rating了，然后就看到一个ID为XXY的大爷刷出了4题，ORZ

F写了一种基于生成树的乱搞做法，WA了4发，然后老老实实地写对拍，发现细节奇多，可能算法本身就不对吧

感觉想rank1已经很难了，做F的话罚时已经爆表了，然后开始看B，发现一个后缀树就解决了，于是又无耻地刷了80+的rating

A  汉字统计

统计一个文本文件中的汉字数量

我只记得汉字的ASCLL码是负的（也许是我太naive），交了几发跪了就没理这道题

B  公共子串

统计n个串的公共子串的个数

Solution：一开始想的是把所有串放一起，做个后缀数组，然后利用DP什么的算一下，最后为了抢分，于是写了个不压缩路径的后缀树水过去了

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

int n,i,j,k,l,p,tot,ans;
int son[1000005][26],Max[1000005];
char s[1005],Trie[1000005];

int main()
{
	scanf("%d",&n);
	scanf("%s",s+1);
	l=strlen(s+1);
	for(i=1;i<=l;++i)
	{
		p=0;
		for(j=i;j<=l;++j)
		{
			if(!son[p][s[j]-'a'])son[p][s[j]-'a']=++tot;
			p=son[p][s[j]-'a'];
		}
	}
	for(i=0;i<=tot;++i)Max[i]=1;
	for(i=2;i<=n;++i)
	{
		scanf("%s",s+1);
		l=strlen(s+1);
		Max[0]=i;
		for(j=1;j<=l;++j)
		{
			p=0;
			for(k=j;k<=l;++k)
			{
				if(!son[p][s[k]-'a'])break;
				p=son[p][s[k]-'a'];
				if(Max[p]<i-1)break;
				Max[p]=i;
			}
		}
	}
	ans=0;
	for(i=1;i<=tot;++i)
	if(Max[i]==n)++ans;
	printf("%d\n",ans);
}

C  比分问题

开始比分是0:0，然后每次A赢和B赢的概率相等，问最后比分为A:B且A全程分数碾压B的概率

Solution：简单的DP，转移方案数

#include <stdio.h>
#include <stdlib.h>
using namespace std;

long long f[55][55],g[55][55];
int n,m,i,j,k;

int main()
{
	scanf("%d%d",&n,&m);
	f[0][0]=1;g[0][0]=1;
	for(i=0;i<=n;++i)
	for(j=0;j<=m;++j)
	{
		if(i+1>j)f[i+1][j]+=f[i][j];
		if(i>j+1)f[i][j+1]+=f[i][j];
		g[i+1][j]+=g[i][j];
		g[i][j+1]+=g[i][j];
	}
	printf("%.3lf\n",1.0*f[n][m]/g[n][m]);
}

D  选三角

平面上随机的n个点，选三个点组成一个三角形，求这个三角形面积大于M的任意方案

Solution：先做个凸包，然后在凸包上随机选点

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;

int n,i,j,k,st[100005],top,x,y,z;
long long m;

struct node
{
	long long x,y;
	int id;
}dot[100005];

inline bool cmp(const node &a,const node &b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;}
inline long long cross(node dot1,node dot2,node dot3){return (dot1.x-dot3.x)*(dot2.y-dot3.y)-(dot2.x-dot3.x)*(dot1.y-dot3.y);}
long long Abs(long long a){if(a<0)return -a;return a;}

int main()
{
	scanf("%d%lld",&n,&m);
	for(i=1;i<=n;++i)scanf("%lld%lld",&dot[i].x,&dot[i].y),dot[i].id=i;
	sort(dot+1,dot+n+1,cmp);
	top=2;
	st[1]=1;
	st[2]=2;
	for(i=3;i<=n;++i)
	{
		st[++top]=i;
		while((top!=2)&&(cross(dot[st[top]],dot[st[top-1]],dot[st[top-2]])>0))
		st[--top]=i;
	}
	for(i=n-1;i>=1;--i)
	{
		st[++top]=i;
		while((top!=2)&&(cross(dot[st[top]],dot[st[top-1]],dot[st[top-2]])>0))
		st[--top]=i;
	}
	m*=2;
	for(;;)
	{
		x=rand()%top+1;
		y=rand()%top+1;while(y==x)y=rand()%top+1;
		z=rand()%top+1;while(z==x||z==y)z=rand()%top+1;
		if(Abs(cross(dot[st[x]],dot[st[y]],dot[st[z]]))>=m)
		{
			printf("%d\n",dot[st[x]].id);
			printf("%d\n",dot[st[y]].id);
			printf("%d\n",dot[st[z]].id);
			return 0;
		}
	}
}

E 排座位

6*9的教室，某些人座位相邻就会产生噪声，求噪声总和小于M的任意方案

Solution：随机爬山

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int f[15][15],g[15][15],w[105][105];
int n,i,j,k,u,v,c,a1,b1,a2,b2;
long long ans,tmp,m;

int main()
{
	scanf("%d%lld",&n,&m);
	for(;n;--n)
	{
		scanf("%d%d%d",&u,&v,&c);
		w[u][v]+=c;
		w[v][u]+=c;
	}
	k=0;
	for(i=1;i<=6;++i)
	for(j=1;j<=9;++j)
	f[i][j]=++k;
	ans=0;
	for(i=1;i<=6;++i)
	for(j=1;j<=9;++j)
	{
		ans+=w[f[i][j]][f[i+1][j]];
		ans+=w[f[i][j]][f[i][j+1]];
	}
	while(ans>m)
	{
		for(i=1;i<=6;++i)
		for(j=1;j<=9;++j)
		g[i][j]=f[i][j];
		tmp=0;
		for(i=1;i<=5;++i)
		{
			a1=rand()%6+1;b1=rand()%9+1;
			a2=rand()%6+1;b2=rand()%9+1;
			swap(g[a1][b1],g[a2][b2]);
		}
		for(i=1;i<=6;++i)
		for(j=1;j<=9;++j)
		{
			tmp+=w[g[i][j]][g[i+1][j]];
			tmp+=w[g[i][j]][g[i][j+1]];
		}
		if(tmp<ans)
		{
			ans=tmp;
			for(i=1;i<=6;++i)
			for(j=1;j<=9;++j)
			f[i][j]=g[i][j];
		}
	}
	for(j=1;j<=9;++j)
	{
		printf("%d",f[1][j]);
		for(i=2;i<=6;++i)printf(" %d",f[i][j]);
		printf("\n");
	}
}

F  关键点

求在奇数简单环上的点的个数