AtCoder Regular Contest 099 C~E

C - Minimization

枚举就可以了

因为最后一定会变成1，所以第一次操作的区间就包含1会比较优，然后枚举1在第一次操作区间里排第几个取min即可

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

const int N=100005;

int n,k,w,a[N],ans=1e9;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int main()

{

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

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

	{

		a[i]=read();

		if(a[i]==1)

			w=i;

	}

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

		if(w>=i&&n-w>=k-i)

			ans=min(ans,(int)(ceil((double)(w-i)/(double)(k-1))+ceil((double)(n-(w+k-i))/(double)(k-1))));

	printf("%d\n",ans+1);

	return 0;

}

D - Snuke Numbers

卡死在这道题上了，思路比较迷

首先打表发现，Snuke数只会出现在结尾为9,99,999,9999……的数中，9的数量是单调递增的，但是变化点看起来并没有规律实际上也没有，但是可以通过O(能过)的方式判断出来

设p和q分别表示最高位数和位数，每次判断一下，如果当前位数不满足，则q++，否则输出答案，p++

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

int S(long long x)

{

	int r=0;

	while(x)

		r+=x%10,x/=10;

	return r;

}

int main()

{

	long long k,p=2,q=1;

	scanf("%d",&k);

	while(k)

	{

		long long n=p*q-1,m=ceil((double)p/10.0)*q*10-1;//cerr<<n<<" "<<m<<endl;

		if(n*S(m)>m*S(n))

			p=ceil((double)p/10.0),q*=10;

		else

		{

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

			k--,p++;

		}

	}

	return 0;

}

E - Independence

其实挺好做的，但是在D上纠结太久了

建出补图，分成两个团就变成了分成两个集合，有边相连的点不能在同一集合。找最小值黑白染色之后跑取min即可，bitset的用法非常棒

#include<iostream>

#include<cstdio>

#include<bitset>

using namespace std;

const int N=705;

int n,m,a[N][N],s[2],c[N],ans=1e9;

bool v[N],flg;

bitset<N>b;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void dfs(int u,int col)

{

	c[u]=col;

	v[u]=1;

	s[col]++;

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

		if(i!=u&&!a[u][i])

		{

			if(!v[i])

				dfs(i,col^1);

			else if(c[i]!=col^1)

				flg=1;

		}

}

int main()

{

	n=read(),m=read();b[0]=1;

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

	{

		int x=read(),y=read();

		a[x][y]=a[y][x]=1;

	}

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

		if(!v[i])

		{

			s[0]=s[1]=0;

			dfs(i,0);

			b=(b<<s[0])|(b<<s[1]);

		}

	if(flg==1)

	{

		puts("-1");

		return 0;

	}

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

		if(b[i])

			ans=min(ans,i*(i-1)/2+(n-i)*(n-i-1)/2);

	printf("%d\n",ans);

	return 0;

}

巴特西

AtCoder Regular Contest 099 C~E

C - Minimization

D - Snuke Numbers

E - Independence

最新文章

热门文章