又是一场JSOI（JS没事考那么多场干嘛，闲的蛋疼吗）
T1
看起来很水啊，似乎贪心就可以了嘛。
然而，一秒后发现反例……
再一看似乎是DP，不过是哪种类型呢。。好像是邮局dp（pol取的名字）
一分钟后又发现反例。。
然而这是一道区间dp。
首先把每个敌机抽象为一条a[i]-b[i]的线段，问题便转化为切断所有线段的最小代价。
对于区间[l,r],找到包含在区间内的代价最大的线段，枚举上面的点进行切割，然后分成两个小区间，这样就可以转移辣~
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 610
int a[N],b[N],c[N],p[N],d[N],f[11000],dp[N][N];
bool cmp(int x,int y){
return d[x]<d[y];
}
int r,n,m,k,l,t,s,cnt,cas;
int main(){
memset(f,0,sizeof(f));
scanf("%d",&n);
cnt=0;
for (int i=1;i<=n;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);
for (int i=1;i<=n;i++){d[++cnt]=a[i];d[++cnt]=b[i];p[i*2]=i*2;p[i*2-1]=i*2-1;}
sort(p+1,p+2*n+1,cmp);
cnt=0;
for (int i=1;i<=2*n;i++){
if (d[p[i]]!=d[p[i-1]]) cnt++;
f[d[p[i]]]=cnt;
}
memset(dp,10,sizeof(dp));
for (int i=1;i<=cnt+1;i++) dp[i][i-1]=0;
for (int t=1;t<=cnt;t++)
for (int i=1;i<=cnt-t+1;i++){
int j=i+t-1;
int mx=0;
for (int k=1;k<=n;k++)
if ((f[a[k]]>=i)&&(f[b[k]]<=j))
if (c[k]>mx) {mx=c[k];l=k;}
if (mx==0) dp[i][j]=0;
for (int k=f[a[l]];k<=f[b[l]];k++)
dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+mx);
}
printf("%d\n",dp[1][cnt]);
}
T2
此乃狗题（因为连gonens大神都不会做）
目前只有60分算法，对于每个点做dfs，线段树维护根到当前点有哪些边，统计答案即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 50010
#define M 1000010
int head[N],vet[N],cost[N],next[N],tree[4*M];
int num,n,m,k,l,t,x,y,z;
double s,ans;
void add(int a,int b,int c){
next[++num]=head[a];
head[a]=num;
vet[num]=b;
cost[num]=c;
}
void change(int l,int r,int x,int p,int vv){
if (l==r){
tree[p]+=vv;
return;
}
int mid=(l+r)/2;
if (x<=mid) change(l,mid,x,p+p,vv);
else change(mid+1,r,x,p+p+1,vv);
tree[p]=tree[p+p]+tree[p+p+1];
}
int find(int l,int r,int x,int p){
if (l==r){
return(l);
}
int mid=(l+r)/2;
if (tree[p+p]>=x) return(find(l,mid,x,p+p));
else return(find(mid+1,r,x-tree[p+p],p+p+1));
}
void dfs(int u,int fa,int len){
if ((len%2)==1){k++;s+=find(1,1000000,(len+1)/2,1);}
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (v!=fa){
change(1,1000000,cost[e],1,1);
dfs(v,u,len+1);
change(1,1000000,cost[e],1,-1);
}
}
}
int main(){
freopen("random.in","r",stdin);
freopen("random.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
for (int i=1;i<=n;i++){
dfs(i,0,0);
}
ans=(double)(s/k);
printf("%.7lf\n",ans);
}
T3
看着数据就感觉应该要转换成离线（否则不是人能做的）
没错正解就是转成离线→_→
排序后按边权从大到小加边，如果该边的两点已经连通，则删去两点间最长的边。
对每个前缀开可持久化线段树维护
询问[l,r]的答案为编号为l的数的前缀r。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
#define N 1000010
#define M 1000100
struct node{int l,r,s;}T[6000000];
int f[N],a[N],b[N],c[N],root[N],head[N],next[M],cost[M],vet[M],map[M],tid[M];
int num,n,m,k,l,t,s,ans,q,r,f1,f2,id,shit,x,y;
void add(int a,int b,int c,int d){
next[++num]=head[a];
head[a]=num;
vet[num]=b;
cost[num]=c;
tid[num]=d;
next[++num]=head[b];
head[b]=num;
vet[num]=a;
cost[num]=c;
tid[num]=d;
}
void sort(int l,int r){
int i=l;
int j=r;
int x=c[(l+r)/2];
while (i<j){
while (c[i]<x) i++;
while (x<c[j]) j--;
if (i<=j){
t=a[i];a[i]=a[j];a[j]=t;
t=b[i];b[i]=b[j];b[j]=t;
t=c[i];c[i]=c[j];c[j]=t;
i++;
j--;
}
}
if (l<j) sort(l,j);
if (i<r) sort(i,r);
}
int find(int x){
if (f[x]!=x) f[x]=find(f[x]);
return(f[x]);
}
void ins(int &i,int l,int r,int x,int v){
T[++id]=T[i];i=id;T[i].s+=v;
if (l==r) return;
int mid=(l+r)/2;
if (x<=mid) ins(T[i].l,l,mid,x,v);
else ins(T[i].r,mid+1,r,x,v);
}
int query(int i,int l,int r,int x){
if ((1<=x)&&(x>=r)) return(T[i].s);
int mid=(l+r)>>1;
if (x<=mid) return(query(T[i].l,l,mid,x));
else return(T[T[i].l].s+query(T[i].r,mid+1,r,x));
}
int dfs(int u,int fa,int st,int l){
if (u==st){
t=l;
return(1);
}
int p=l;
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (v!=fa){
p=l;
if ((c[map[l]]<c[map[tid[e]]])||(l==-1)) p=tid[e];
if (dfs(v,u,st,p)) return(1);
}
}
return(0);
}
int main(){
scanf("%d%d",&n,&m);
id=0;
for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
sort(1,m);
for (int i=1;i<=n;i++) f[i]=i;
for (int w=m;w>0;w--){
root[w]=root[w+1];
if (a[w]==b[w]) continue;
f1=find(a[w]);
f2=find(b[w]);
if (f1!=f2){
f[f2]=f1;
map[++map[0]]=w;
ins(root[w],1,m,w,c[w]);
}else{
int mx=0;
for (int i=1;i<=n;i++) head[i]=0;
num=0;
for (int i=1;i<=map[0];i++) add(a[map[i]],b[map[i]],c[map[i]],i);
dfs(a[w],0,b[w],-1);
// printf("-%d\n",map[t]);
ins(root[w],1,m,map[t],-c[map[t]]);
for (int i=t;i<map[0];i++) map[i]=map[i+1];
map[map[0]]=w;
ins(root[w],1,m,w,c[w]);
}
}
// return 0;
int ans=0;
scanf("%d%d",&q,&shit);
for (int i=1;i<=q;i++){
scanf("%d%d",&x,&y);
l=ans*shit+x;
r=l+y;
l=lower_bound(c+1,c+1+m,l)-c;
r=upper_bound(c+1,c+1+m,r)-c-1;
if (l>r) ans=0;
else ans=query(root[l],1,m,r);
printf("%d\n",ans);
}
}
评论 (0)
