Atcoder Beginner Contest 315

Hints

尝试优化暴力。

A - tcdr

没啥好说的，模拟。

代码实现

void Solve()
{
	while(char ch=getchar())
	{
		if(!isalpha(ch))return;
		if(ch!='a'&&ch!='e'&&ch!='i'&&ch!='o'&&ch!='u')putchar(ch);
	}
}

B - The Middle Day

没啥好说的，统计总天数，找到中间的一天，再枚举月即可。

代码实现

const int N=105;
int n,a[N];
void Solve()
{
	cin>>n;
	int sum=0;
	for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
	sum=sum+1>>1;
	for(int i=1;i<=n;i++)
		if(sum>a[i])sum-=a[i];
		else return cout<<i<<" "<<sum,void();
}

C - Flavors

只有两种情况：

选择美味值最高的和第二高的；
选择美味值最高的，还有与美味值最高的口味不同的中的美味值最高的。

代码实现

const int N=300005;
int n;
struct ice
{
	int f,s;
	bool operator<(const ice B)const{return s>B.s;}
}a[N];
void Solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].f>>a[i].s;
	sort(a+1,a+n+1);
	int x=0,y=0;
	if(a[1].f==a[2].f)x=a[2].s;
	for(int i=2;i<=n;i++)
		if(a[1].f!=a[i].f){y=a[i].s;break;}
	for(int i=1;i<=n;i++)dbg(i,a[i].f,a[i].s);
	dbg(x,y);
	cout<<a[1].s+max(x>>1,y);
}

D - Magical Cookies

吐槽比 E 毒瘤。

有一个暴力的想法：每次检查每一行每一列，如果全一样且大于一个就标记上，然后全部删掉。

这样做，最坏情况是每次删除了一行/一列，但是却扫过了整个矩阵，时间复杂度 \(\Theta(nm(n+m))\)，成功 TLE。

我们发现，这个做法的瓶颈在于检查哪一行/列可以被删除。

怎样优化？

我们可以记录每一行/列所有 \(26\) 个字母的出现次数以及剩下的字母个数。这样做，我们就可以在 \(\Theta((n+m)|\Sigma|)\) 的时间找出哪一行/列可以被删除。

进一步的，我们可以直接记录每一行/列出现过的字母个数，做到 \(\Theta(n+m)\) 的 check。

然后每次用 vector 记录要删除的点，删除的时候即可更新一下行列信息即可。

最坏情况下，要删除 \(nm\) 个点，删点的复杂度 \(\Theta(1)\)；要 check \(n+m\) 次，每次 check 是 \(\Theta(n+m)\) 的。总复杂度 \(\Theta((n+m)^2)\)。

代码实现

const int N=2005;
int n,m;
string g[N];
int cntr[N][26],cntc[N][26],typr[N],typc[N],remr[N],remc[N];
void add(int x,int y)
{
	int t=g[x][y]-'a';
	if(!cntr[x][t]++)typr[x]++;
	if(!cntc[y][t]++)typc[y]++;
	remr[x]++,remc[y]++;
}
void del(int x,int y)
{
	if(g[x][y]==' ')return;
	int t=g[x][y]-'a';
	g[x][y]=' ';
	if(!--cntr[x][t])typr[x]--;
	if(!--cntc[y][t])typc[y]--;
	remr[x]--,remc[y]--;
}
vector<PII>mk;
void Solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>g[i],g[i]="$"+g[i];
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)add(i,j);
	while(1)
	{
		bool ok=0;
		for(int i=1;i<=n;i++)
			if(typr[i]==1&&remr[i]>1)
			{
				ok=1;
				for(int j=1;j<=m;j++)mk.PB(i,j);
			}
		for(int i=1;i<=m;i++)
			if(typc[i]==1&&remc[i]>1)
			{
				ok=1;
				for(int j=1;j<=n;j++)mk.PB(j,i);
			}
		if(!ok)break;
		for(PII i:mk)del(i.first,i.second);
		mk.clear();
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)ans+=(bool)isalpha(g[i][j]);
	cout<<ans;
}