CSP模拟18
CSP模拟18
T1 站队 CF1850H
我们发现如果把怪抽象为节点,如果有两个节点可以用不同长度的路径联通,那么答案不合法,否则答案合法。
我们对每一个没有遍历过的点进行 \(DFS\) ,查找是否有不合法的点对。
注意 \(dis\) 要赋一个极小值/极大值,否则可能使某个点的值恰好为初始值而多次遍历导致超时。
code
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#define ll long long
using namespace std;
int n,m,tot,hea[400010],nex[400010],to[400010];
ll wa[400010],dis[400010];
bool f;
void add(int x,int y,ll z){
to[++tot]=y;
wa[tot]=z;
nex[tot]=hea[x];
hea[x]=tot;
}
void dfs(int x){
if(f==1) return;
for(int i=hea[x];i;i=nex[i]){
int t=to[i];
if(f==1) return;
if(dis[t]==-1e17){
dis[t]=dis[x]+wa[i];
dfs(t);
}
else{
if(dis[t]!=dis[x]+wa[i]){
f=1;
return ;
}
}
}
}
void work(){
scanf("%d%d",&n,&m);
f=0;tot=0;
for(int i=1;i<=n;i++) hea[i]=0;
for(int i=1;i<=m;i++){
int a,b;
ll d;
scanf("%d%d%lld",&a,&b,&d);
add(a,b,d);
add(b,a,-d);
}
for(int i=1;i<=n;i++) dis[i]=-1e17;
for(int i=1;i<=n;i++){
if(dis[i]==-1e17){
dis[i]=0;
dfs(i);
if(f==1) break;
}
}
if(f==1) printf("NO\n");
else printf("YES\n");
return;
}
int main(){
int t;
scanf("%d",&t);
while(t--) work();
return 0;
}
T2 打怪兽 CF1852C
我们把怪的生命值转化为矩形高度,红色部分为怪的生命值,黑色直线为选择的区间。我们发现只有后面怪的生命值相对于前一个怪增加时才会增加代价。
对于怪的生命值有两种情况,设怪的生命值分别为 \(a_1\) , \(a_2\) 。
-
前一个怪生命值小于后面一个怪。\(a_1 < a_2\)
-
前一个怪的生命值大于后面一个怪。\(a_1 > a_2\)
对于第一种情况,我们可以让这个怪前方一部分加 \(k\) ,转换为第二种情况。或者答案加上后一个怪和前一个怪的生命值的差值,代价是答案加上 \(a_2-a_1\)
对于第二种情况,我们可以在此时把后面的怪的生命值增加 \(k\) ,代价是答案增加 \(a_2 + k-a_1\) ,或者不进行任何操作。
我们可以把每一种方案的代价放入优先队列中,每次遇到第一种情况时选出代价最小的方案统计到答案中。
code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define ll long long
using namespace std;
int n,k,a[200010];
ll ans;
int work(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i]%=k;
}
priority_queue<int,vector<int>,greater<int> >q;
for(int i=1;i<=n;i++){
if(a[i]>a[i-1]){
q.push(a[i]-a[i-1]);
ans+=q.top();
q.pop();
}
if(a[i]<a[i-1]){
q.push(a[i]+k-a[i-1]);
}
}
printf("%lld\n",ans);
ans=0;
return 0;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
work();
}
}