Atcoder Beginner Contest 315
Hints
D
尝试优化暴力。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;}
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;
}
E - Prerequisites
水题。
把依赖关系看成一张图，则它是个 DAG。
直接从 \(1\) 开始 dfs，在 dfs 树上后序遍历即可。
代码实现
const int N=200005;
int n;
VI g[N];
bool vis[N];
void dfs(int x)
{
if(vis[x])return;
vis[x]=1;
for(int y:g[x])dfs(y);
cout<<x<<" ";
}
void Solve()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int sz;cin>>sz;
while(sz--){int x;cin>>x;g[i].PB(x);}
}
for(int i:g[1])dfs(i);
}