Day 1
risk
题目描述
解法
考虑最后的集结，不妨考虑找出所有集结过程中可能经过的边，不难发现是一棵树，所以答案就是最小生成树。
代码
点击查看代码
struct node
{
int u,v,w;
}e[3000001];
int n,m;
int fa[3000001];
int find(int x)
{
return x==fa[x]?fa[x]:fa[x] = find(fa[x]);
}
int cnt;
long long ans;
bool cmp(node a,node b)
{
return a.w<b.w;
}
void kru()
{
sort(e+1,e+1+m,cmp);
int i;
int fu,fv;
for(i=1;i<=m;i++)
{
fu = find(e[i].u);
fv = find(e[i].v);
if(fu==fv)
continue;
ans += e[i].w;
fa[fu] = fv;
if(++cnt==n-1)
{
cout<<ans<<endl;
return;
}
}
return;
}
void solve()
{
cin>>n>>m;
int i,j;
for(i=1;i<=n;i++)
fa[i] = i;
for(i=1;i<=m;i++)
cin>>e[i].u>>e[i].v>>e[i].w;
kru();
return;
}
magic
题目描述
解法
考虑设 \(dp_{i,j}\) 为经过了前 \(i\) 次操作,特殊球放到 \(j\) 位置所需要删掉的最少的步数，这个显然是好求的。注意到每次 dp 只会改变 \(dp_{i,x}\) 和 \(dp_{i,y}\) 的值,因此可以优化到 \(O(n+m)\)。
代码
点击查看代码
int n,m,k;
int f[1000001];
void solve()
{
cin>>n>>m>>k;
for (int i = 1; i <= m; i++)
f[i] = 1e9;
f[k] = 0;
for (int i = 1; i <= m; i++)
{
int x,y;
cin>>x>>y;
int fx = f[x];
int fy = f[y];
f[x] = min(fx + 1, fy);
f[y] = min(fy + 1, fx);
}
for (int i = 1; i <= n; i++)
{
if (f[i] == 1e9)
cout<<-1<<' ';
else
cout<<f[i]<<' ';
}
return;
}
letters
题目描述
