26.11.8 比赛记录
T1 疯狂钻石
蓝色数组在数轴上把红色数字分分隔开,假如蓝色数字去重后有 个数,就会形成 个间隔。处在同一个间隔里的红色数字是可以一起选的,求每个间隔的红色数字的最大数量即可。
T2 绯红之王
定义 DP 数组, 表示处理了第一叠的前 张和第二叠的前 张的最优情况。这个最优情况是一个 pair,如果两个情况的处理批数不同,批数小的更优,否则剩余容量大的更优。转移方程就是从第一叠取和第二叠取,两种情况里选最优的。DP 可以用滚动数组,比较两种情况的优劣用 pair 自带的比较即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
const int N=5005;
int n,m,k,w,a[N],b[N];
pii dp[N];
pii add(pii x,int y){
if(!x.first||x.second+y>w)x.first++,x.second=y;
else x.second+=y;
return x;
}
signed main(){
cin>>n>>m>>w>>k;
for(int i=1;i<=n;i++)cin>>a[n-i+1];
for(int i=1;i<=m;i++)cin>>b[m-i+1];
for(int i=1;i<=m;i++)dp[i]=add(dp[i-1],b[i]);
for(int i=1;i<=n;i++){
dp[0]=add(dp[0],a[i]);
for(int j=1;j<=m;j++)
dp[j]=min(add(dp[j],a[i]),add(dp[j-1],b[j]));
}
cout<<dp[m].first*k;
return 0;
}
T3 紫色隐者
赛时想到正解了,最终没 AC(因为 SPJ 比较难测大样例,码完后直接去写下一题了)。
可以发现这题的问题可以拆分成很多子问题。假如你有一棵以 为根的树,还有很多子树。你可以把一些子树的编号设置成比 小的,另一些子树的编号设置成比 大的。这样所有子树就被划分成了两部分。如何划分最优呢?显然两部分 siz 之差最小是最优的。这可以使用背包 DP 计算。然后对于每个子树递归下去求解即可。注意 和 这两个点要忽略。总时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int n,fa[N],dp[N],siz[N],ans[N],sizz[N],cnt[N];
bool b[N],choose[N][N];
vector<int>g[N];
void dfs(int u){
sizz[u]=1,cnt[u]=(u!=1&&u!=n);
for(int v:g[u])dfs(v),sizz[u]+=sizz[v],cnt[u]+=cnt[v];
}
void bag(int u,int n,int m){
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
dp[j]=choose[i][j]=0;
for(int i=1;i<=n;i++)
for(int j=m;j>=1;j--)
if(j>=cnt[g[u][i-1]]&&dp[j]<dp[j-cnt[g[u][i-1]]]+cnt[g[u][i-1]])
dp[j]=dp[j-cnt[g[u][i-1]]]+cnt[g[u][i-1]],choose[i][j]=1;
for(int i=n,j=m;i>=1;i--)
if(choose[i][j])b[g[u][i-1]]=1,j-=cnt[g[u][i-1]];
}
void dfs1(int u,int l,int r){
if(!siz[u]){
ans[u]=l;
return;
}
int sum=l;
for(int v:g[u])
if(b[v])dfs1(v,sum,sum+sizz[v]-1),sum+=sizz[v];
ans[u]=sum++;
for(int v:g[u])
if(!b[v])dfs1(v,sum,sum+sizz[v]-1),sum+=sizz[v];
}
int main(){
cin>>n;
for(int i=2;i<=n;i++)cin>>fa[i],g[fa[i]].push_back(i);
for(int i=1;i<=n;i++)siz[i]=g[i].size();
dfs(1);
for(int i=1;i<=n;i++){
if(siz[i]<=1)continue;
int sum=0;
for(int v:g[i])sum+=cnt[v];
bag(i,siz[i],sum/2);
}
dfs1(1,1,n);
for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
return 0;
}
T4 公路之星
首先把所有 R 边转换成反向的 B 边。我们可以发现一个性质:如果有两条边指向同一个点,例如 ,,我们就可以把 这两个点视作互相可达的点,因为 和 都是合法的路径且 。既然这样,我们可以把 合成一个等效节点 。对于所有拥有两条及以上入边的点进行此操作,不断合成,直到无法操作。最终,如果 处于同一个等效节点中,就是互相可达的。对于不断合并的操作,我们可以使用并查集实现,因为节点的可达性具有自反性、传递性、对称性(这三个性质具体来讲,就是 可达 , 可达 且 可达 能推出 可达 , 可达 能推出 可达 )。我们可以使用链表记录每个节点有哪些入边,这样可以 合并。总时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,u[N],v[N],t;
int cnt[N],hd[N],tl[N],nx[N];//链表储存每个节点的入边
int fa[N],siz[N];
queue<int>q;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
if(siz[x]<siz[y])swap(x,y);
fa[y]=x;
siz[x]+=siz[y];
if(cnt[x])nx[tl[x]]=hd[y];
else hd[x]=hd[y];
if(cnt[y])tl[x]=tl[y];
cnt[x]+=cnt[y];
hd[y]=tl[y]=cnt[y]=0;
if(cnt[x]>=2)q.push(x);
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m;
for(int i=0;i<N;i++)
fa[i]=i,siz[i]=1;
for(int i=1;i<=m;i++){
char d;
cin>>u[i]>>v[i]>>d;
if(d=='R')swap(u[i],v[i]);
if(cnt[v[i]]++==0)hd[v[i]]=tl[v[i]]=i;
else nx[tl[v[i]]]=i,tl[v[i]]=i;
}
for(int i=1;i<=n;i++)
if(cnt[i]>=2)q.push(i);
while(q.size()){
int x=q.front();
q.pop();
while(cnt[x]>=2){
int e=hd[x];
hd[x]=nx[hd[x]];
cnt[x]--;
merge(u[e],u[hd[x]]);
x=find(x);
}
}
cin>>t;
while(t--){
int s,t;
cin>>s>>t;
cout<<(find(s)==find(t))<<'\n';
}
return 0;
}