ABC334 总结
https://atcoder.jp/contests/abc333
A - Three Threes
翻译
输入一个正整数 \(n\)，输出 \(n\) 遍这个正整数。
\(1\le n\le 9\)。
分析
没啥好说的，直接输出就好了。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int main ()
{
cin>>n;
for(int i=1;i<=n;i++) cout<<n;
return 0;
}
B - Pentagon
翻译
给出两条线段，保证它们的端点均为正五边形 \(ABCDE\) 的顶点，问这两条线段的长度是否相等？
分析
设两端点字母的差的绝对值分别为 \(x\) 和 \(y\)，两条线段长度相等，要么就 \(x=y\)，要么就 \(x+y=5\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
string a,b;
int main ()
{
cin>>a>>b;
int x=abs(a[1]-a[0]);
int yr=abs(b[1]-b[0]);
if(x==y||x+y==5) cout<<"Yes";
else cout<<"No";
return 0;
}
C - Repunit Trio
翻译
「repunit 数」是指由若干个 \(1\) 拼起来的数，如 \(1, 11, 111, \dots\)。
输出所有能够表示为 \(3\) 个「repunit 数」之和的数中，第 \(n\) 小的数。
\(1 \le n \le 333\)。
分析
\(n\) 的范围不大，直接暴力枚举就可以，由三个「repunit 数」相加得到数，那么就可以直接 \(3\) 个 for，将所有情况都求出来，然后排序，最后也可以打表，也可以就这么暴力。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,t,a[15],x[15],b[15],c[15],ans[3333];
int main ()
{
cin>>n;
a[0]=b[0]=c[0]=1;
x[1]=10;
for(int i=2;i<=12;i++) x[i]=x[i-1]*10;
for(int i=1;i<=12;i++) a[i]=a[i-1]+x[i],b[i]=c[i]=a[i];
int tot=0;
for(int i=0;i<=12;i++)
for(int j=0;j<=12;j++)
for(int k=0;k<=12;k++)
{
tot++;
ans[tot]=a[i]+b[j]+c[k];
}
sort(ans+1,ans+tot);
tot=unique(ans+1,ans+tot)-ans;
cout<<ans[n];
return 0;
}
D - Erase Leaves
翻译
给定一颗 \(n\) 个节点的无根树。每次你可以删除一个叶子节点（即度数为 \(1\) 的点），问最少多少次操作可以删除 \(1\) 节点。
\(2 \le n \le 3 \times 10^5\)。
分析
要能够删除 \(1\) 节点，那么就要把 \(1\) 节点变成叶子节点，每个节点都只有一个父亲，那么如果把 \(1\) 节点作为根节点，它的子树最多只能留下一个，其他的都要删除。那么要删掉最少得点，就需要保证留下的子树节点数最大。也就是说，找出把 \(1\) 作为根节点的子树中最大的节点数，然后用 \(n\) 减去它就得到答案了。统计节点数，其实就是调用了几次函数。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int n,m,t,ans=0,cnt;
int head[N<<1],ver[N<<1],tot=1,ne[N<<1];
void add(int x,int y)
{
ver[++tot]=y,ne[tot]=head[x],head[x]=tot;
}
void dfs(int u,int fa)
{
cnt++;
for(int i=head[u];i;i=ne[i])
{
int v=ver[i];
if(v==fa) continue;
dfs(v,u);
}
}
int main ()
{
cin>>n;
int m=n-1,x,y;
while(m--)
{
cin>>x>>y;
add(x,y);
add(y,x);
}
for(int i=head[1];i;i=ne[i])
{
int v=ver[i];
cnt=0;
dfs(v,1);
ans=max(ans,cnt);
}
cout<<n-ans<<"\n";
return 0;
}
E - Takahashi Quest
翻译
Takahashi 在进行一次冒险。
在第 \(i\) 个位置上发生一件事情，用 \((t_i, x_i)\) 表示。
- 若 \(t_i = 1\)，则表示这里有一个 \(x_i\) 魔法的药水。Takahashi 可以选择捡起会不捡起；
- 若 \(t_i = 2\)，则表示这里有一个 \(x_i\) 魔法的怪兽，需要用一个 \(x_i\) 魔法的药水才能打败。
你需要求出，在 Takahashi 能打败所有怪兽的情况下，每个时刻手中的药水瓶数的最大值最小是多少。若不能打败所有怪兽输出 \(-1\)。
分析
要想使得每个时刻手中的药水瓶数的最大值最小，那么就要尽可能把越晚获得的药水消耗掉，后进先出，可以用栈来维护。用 \(n\) 个栈来存储每瓶药水出现的时间，将时间插入到对应的栈中，遇到怪物时取出栈顶，打上标记。如果栈为空就说明前面没有获得合适的药水，就无法打败，输出 -1。
后面统计答案就是从头再来一遍，模拟即可。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,t[N],v[N];
stack<int> a[N];
int main ()
{
cin>>n;
for(int i=1,x;i<=n;i++)
{
cin>>t[i]>>x;
if(t[i]==1) a[x].push(i);
else
{
if(a[x].empty())
{
cout<<-1<<"\n";
return 0;
}
v[a[x].top()]=1;
a[x].pop();
}
}
int ans=0;
for(int i=1,cnt=0;i<=n;i++)
{
if(v[i]==1) cnt++,ans=max(ans,cnt);
else if(t[i]==2) cnt--;
}
cout<<ans<<"\n";
for(int i=1;i<=n;i++) if(t[i]==1) cout<<v[i]<<" ";
return 0;
}