eoj monthly 2019.11

原题

T1 纸条

题目大意：

给出一个长度为n的字符串，其中m位未知，对于每一位未知的字母，有k个备选字母，最终答案为备选字母按字典序排序后的第x个。

题解：

签到题……

按照题目意思直接写就可以了。

#include<cstdio>

#include<algorithm>

#define N 500010

typedef long long ll;

using namespace std;

int n,m,k,num[N];

ll x;

char s[N],a[N][30];

int main()

{

	scanf("%d%d%d%lld",&n,&m,&k,&x);

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

	for (int i=1;i<=m;i++) scanf("%s",a[i]+1);

	for (int i=1;i<=m;i++) sort(a[i]+1,a[i]+k+1);

	for (int i=m;i;i--)

	{

		num[i]=(x%k)?(x%k):k;

		x=x/k+((x%k)!=0);

	}

	for (int i=n,j=m;i;i--)

		if (s[i]=='#')

		{

			s[i]=a[j][num[j]];

			j--;

		}

	for (int i=1;i<=m;i++) printf("%d%c",num[i]," \n"[i==n]);

	printf("%s",s+1);

	return 0;

}

/*

5 2 3 3

c##nb

std

lws

*/

T2 安全带

题目大意：

给出n个点，每个点有一个点权，定义每条边的边权为端点点权之和，初始状态为相邻的点间有一条边（i-i+1,n-1)。接下来的操作为摁下一个点后，将所有其余的点与其相连（已经连接的不再连）。询问所有操作结束后，边权之和。

题解：

利用sum记录所有点权之和，每次连接时增加边权为当前点权*(sum-当前点-相邻点)。这样会导致两个都被摁下的点之间连接了两条线，所以只有利用相同的方法减去多连的线即可，即将摁下的点建一个新图，记录sum，减去图中的边，注意减时判除相邻的点（因为连接时并没有多连）。

#include<cstdio>

#define N 100010

typedef long long ll;

using namespace std;

int n,a[N],b[N];

ll sum,ans,sum1,mns;

int read()

{

	int ans=0,op=1;

	char c=getchar();

	for (;(c<'0' || c>'9') && c!='-';c=getchar()) ;

	if (c=='-') op=-1,c=getchar();

	for (;c>='0' && c<='9';c=getchar()) ans*=10,ans+=c^48;

	return ans*op;

}

int main()

{

	n=read();

	for (int i=1;i<=n;i++) a[i]=read(),sum+=a[i];

	a[0]=a[n];a[n+1]=a[1];

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

	{

		b[i]=read();

		if (b[i]) sum1+=a[i];

	}

	b[n+1]=b[1];b[0]=b[n];

	for (int i=1;i<=n;i++) ans+=a[i]*a[i+1];

	//printf("1: %lld\n",ans);

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

		if (b[i])

		{

			ans+=a[i]*(sum-a[i-1]-a[i]-a[i+1]);

			mns+=a[i]*(sum1-a[i]-(b[i-1]?a[i-1]:0)-(b[i+1]?a[i+1]:0));

		}

	//printf("mns %lld\n",mns);

	mns/=2;

	ans-=mns;

	printf("%lld",ans);

	return 0;

}

/*

4

2 3 4 5

1 0 1 1

*/

巴特西

eoj monthly 2019.11

原题

T1 纸条

T2 安全带

最新文章

热门文章