A.Yet Another Dividing into Teams
略
B.Books Exchange
题意
题解
把关系连边后，可以发现一定是形成若干个环，那么 $O(n)$ 搜索一遍即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const int N=200005;
bool vis[N];
int t,n,a[N],ans[N];
int dfs(int x,int res)
{
vis[x]=1;
if (vis[a[x]]) return ans[x]=res;
return ans[x]=dfs(a[x],res+1);
}
signed main()
{
t=read();
while (t--)
{
memset(vis,0,sizeof(vis));
n=read();
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<=n;i++)
{
if (vis[i]) continue;
dfs(i,1);
}
for (int i=1;i<=n;i++) printf("%d ",ans[i]);
puts("");
}
return 0;
}C.Good Numbers
题意
题解
正向的凑不太现实，考虑反向来减。可以发现 $3^{38} > 10^{18}$ ，所以可以先得到 $sum=\sum_{i=0}^{38} 3^i$ 。
与 $2$ 的性质相似，$3^x > \sum_{i=0}^{x-1} 3^i$ 。所以从大到小枚举 $i$ ，如果能减就减去 $3^i$ 。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar(); ll f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
ll t,n,sum,f[40];
signed main()
{
f[0]=sum=1;
for (int i=1;i<=38;i++) f[i]=f[i-1]*3,sum+=f[i];
t=read();
while (t--)
{
n=read();
ll d=sum-n;
for (int i=38;~i;i--) if (f[i]<=d) d-=f[i];
printf("%lld\n",d+n);
}
return 0;
}D.Too Many Segments
题意
题解
经典线段覆盖的思路，只可能是线段之间完全覆盖的情况使答案减小。所以按右端点从小到大排序（或者左端点从大到小），枚举所有线段，能放就放，否则加入答案。用线段树维护。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const int N=200005;
struct Tree {
int left,right,mx,d;
} tree[N<<2];
struct node {
int l,r,id;
} s[N];
int n,k;
vector <int> v;
inline void pushup(int x) { tree[x].mx=max(tree[x<<1].mx,tree[x<<1|1].mx); }
inline void pushdown(int x)
{
tree[x<<1].mx+=tree[x].d;
tree[x<<1|1].mx+=tree[x].d;
tree[x<<1].d+=tree[x].d;
tree[x<<1|1].d+=tree[x].d;
tree[x].d=0;
}
void build(int x,int l,int r)
{
tree[x].left=l;
tree[x].right=r;
if (r-l>1)
{
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid,r);
}
}
void update(int x,int l,int r,int d)
{
if (l<=tree[x].left && r>=tree[x].right) tree[x].mx+=d,tree[x].d+=d;
else
{
if (tree[x].d) pushdown(x);
int mid=(tree[x].left+tree[x].right)>>1;
if (l<mid) update(x<<1,l,r,d);
if (r>mid) update(x<<1|1,l,r,d);
pushup(x);
}
}
int query(int x,int l,int r)
{
if (l<=tree[x].left && r>=tree[x].right) return tree[x].mx;
else
{
if (tree[x].d) pushdown(x);
int mid=(tree[x].left+tree[x].right)>>1,ans=0;
if (l<mid) ans=max(ans,query(x<<1,l,r));
if (r>mid) ans=max(ans,query(x<<1|1,l,r));
return ans;
}
}
signed main()
{
n=read(); k=read();
for (int i=1;i<=n;i++) s[i].l=read(),s[i].r=read(),s[i].id=i;
sort(s+1,s+n+1,[](node x,node y){ return x.r<y.r; });
build(1,1,s[n].r+1);
for (int i=1;i<=n;i++)
{
int res=query(1,s[i].l,s[i].r+1);
if (res>=k) v.emplace_back(s[i].id); //不能放
else update(1,s[i].l,s[i].r+1,1);
}
printf("%lu\n",v.size());
for (auto i:v) printf("%d ",i);
return 0;
}E.By Elevator or Stairs?
题意
有个 $n(\le 2\times 10^5)$ 层的楼房。从第 $i$ 层 $\rightarrow$ 第 $(i+1)$ 层，走楼梯要 $a_i$ 分钟，电梯要 $b_i$ 分钟。电梯可以从任意楼层一次性到达其它任何楼层，但每次等电梯需要花费 $c$ 分钟。可以多次搭乘电梯，问到第 $n$ 层最少需要多久。
题解
DP水题。用 $f[i][0/1]$ 表示当前到了 $i$ 层，上次是走楼梯/坐电梯的最小时间。方程式显然为：
$$\begin{cases} f[i][0]=\min(f[i-1][0],f[i-1][1])+a_{i-1} \\ f[i][1]=\min(f[i-1][0]+c,f[i-1][1])+b_{i-1} \end{cases}$$
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const int N=200005;
int n,m,a[N],b[N],f[N][2];
signed main()
{
n=read(); m=read();
for (int i=1;i<n;i++) a[i]=read();
for (int i=1;i<n;i++) b[i]=read();
memset(f,0x3f,sizeof(f));
f[1][0]=0;
printf("0 ");
for (int i=2;i<=n;i++)
{
f[i][0]=min(f[i-1][0],f[i-1][1])+a[i-1];
f[i][1]=min(f[i-1][0]+m,f[i-1][1])+b[i-1];
printf("%d ",min(f[i][0],f[i][1]));
}
return 0;
}F.Maximum Weight Subset
题意
题解
先将题目中给出的 $k+1$ ，这样 $k$ 表示两点之间的最小距离。
树形DP。用 $f[x][dep]$ 表示在以 $x$ 为根的子树中，深度至少为 $dep$ （$x$ 的深度为 $0$）的点才能取，这时的最大权值。初值为 $f[x][0]=a[x]$ 。
对于每个 $x$ ，枚举 $dep$ 转移，设 $y$ 为 $x$ 的子节点。如果 $dep=0$ ，意味着选了 $x$ ，这时可以在以 $y$ 为根的子树中深度至少为 $k-1$ 的点中选择，所以
$$f[x][0]=\max (\sum f[y][k-1])\tag{1}$$
当 $dep\neq 0$ 时，说明各个 $y$ 为根的子树中可选的深度不同：如果选了一个子树在深度 $dep-1$ 处选，那么其它子树，假设根节点为 $z$ ，就受两个距离限制，所以取最大值为 $\max(dep-1,k-dep-1)$ 。方程式为
$$f[x][dep]=\max (f[y][dep-1]+\sum f[z][\max(dep-1,k-dep-1)])\tag{2}$$
最后还应该让答案随深度保持单调不增，因为不一定每次都选距离严格 $=k$ 的节点。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read()
{
char ch=getchar(); int f=1,x=0;
while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
return f*x;
}
const int N=205;
struct Edge {
int next,to;
} edge[N<<1];
int cnt,head[N],n,m,a,b,s[N],f[N][N];
inline void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int x,int fa)
{
f[x][0]=s[x];
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==fa) continue;
dfs(y,x);
}
for (int i=head[x];i;i=edge[i].next) //dep=0
{
int y=edge[i].to;
if (y==fa) continue;
f[x][0]+=f[y][max(0,m-1)];
}
for (int j=1;j<n;j++) //枚举 dep
{
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==fa) continue;
int cur=f[y][j-1];
for (int k=head[x];k;k=edge[k].next)
{
int z=edge[k].to;
if (z==fa || z==y) continue;
cur+=f[z][max(j-1,m-j-1)];
}
f[x][j]=max(f[x][j],cur);
}
}
for (int i=n-2;~i;i--) f[x][i]=max(f[x][i],f[x][i+1]);
}
signed main()
{
n=read(); m=read()+1;
for (int i=1;i<=n;i++) s[i]=read();
for (int i=1;i<n;i++)
{
a=read(); b=read();
add(a,b);
add(b,a);
}
dfs(1,0);
return !printf("%d",f[1][0]);
}