前言

空间开小导致无法$AKQVQ$

---

成绩

$Rank$是有算别人的

$Rank$$Person$$Score$$A$$B$$C$

$6$	$2017myself$	$210$	$100$	$60$	$50$
$8$	$2017zyc$	$200$	$100$	$100$	$0$
$23$	$2017lw$	$160$	$60$	$100$	$0$
$48$	$2017xjq$	$100$	$90$	$10$	$0$
$61$	$2017xxy$	$60$	$60$	$0$	$0$
$74$	$2017hjq$	$50$	$50$	$0$	$0$
$97$	$2017hzb$	$10$	$10$	$0$	$0$
$97$	$2017lrz$	$10$	$10$	$0$	$0$

---

正题

---

$T1:jzoj1252,P5194-$天平【$dfs,set$】

博客链接:
https://blog.csdn.net/Mr_wuyongcong/article/details/86657589

---

$T2:jzoj1274-$游历的路线【分层图$,SPFA$】

博客链接:
https://blog.csdn.net/Mr_wuyongcong/article/details/86657618

---

$T3:jzoj4224-$食物【多重背包】

博客链接:
https://blog.csdn.net/Mr_wuyongcong/article/details/86657665

---

$someofcode$

---

T2 60分code

#include<cstdio> #include<queue> #include<cstring> #define N 40100 using namespace std; struct node{int to,next,ls,w; }a[N*20]; int tot,ls[N],n,m,f[N]; bool v[N]; queue<int> q; int p(int x,int y) {return x*n+y;} void addl(int x,int y,int w) {a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot; } void spfa() {memset(f,0x3f,sizeof(f));f[p(0,1)]=0;q.push(p(0,1));while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(f[x]+a[i].w<f[y]){f[y]=f[x]+a[i].w;if(!v[y]){v[y]=true;q.push(y);}}}v[x]=0;} } int main() {freopen("lines.in","r",stdin);freopen("lines.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i==j) continue;int t,pri,z=-1,ts;scanf("%d",&t);ts=t;while(ts--){scanf("%d",&pri);z++;if(!pri) continue;for(int k=z;k<m;k+=t)addl(p(k,i),p(k+1,j),pri);}}spfa();if(f[p(m,n)]>10000000) printf("0");else printf("%d",f[p(m,n)]); }

---

T3 50分code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=800,M=50010; int w1[N],v1[N],w2[N],v2[N],f2[M],f1[2000010]; int cnt1,cnt2,n,m,p,test,l,r; int main() {scanf("%d",&test);while(test--){memset(f1,0,sizeof(f1));memset(f2,0,sizeof(f2));cnt1=0;cnt2=0;scanf("%d%d%d",&n,&m,&p);for(int i=1;i<=n;i++){int t,u,v;scanf("%d%d%d",&t,&u,&v);for(int i=1;i<=v;i*=2){v-=i;w1[++cnt1]=u*i;v1[cnt1]=t*i;}if(v) w1[++cnt1]=u*v,v1[cnt1]=t*v;}for(int i=1;i<=m;i++){int t,u,v;scanf("%d%d%d",&t,&u,&v);for(int i=1;i<=v;i*=2){v-=i;w2[++cnt2]=u*i;v2[cnt2]=t*i;}if(v) w2[++cnt2]=u*v,v2[cnt2]=t*v;}for(int i=1;i<=cnt2;i++)for(int j=M;j>=w2[i];j--)f2[j]=max(f2[j-w2[i]]+v2[i],f2[j]);for(int i=1;i<=cnt1;i++)for(int j=f2[M];j>=w1[i];j--)f1[j]=max(f1[j-w1[i]]+v1[i],f1[j]);l=1;r=50000;while(l<=r){int mid=(l+r)/2;if(f1[f2[mid]]>=p) r=mid-1;else l=mid+1;}if(l<=50000) printf("%d\n",l);else printf("TAT\n");} }

---

总结

预计分(100+100+100=300)AK?

结果(100+60+50=210)爆炸了

T1:不是贪心吗，然后写了个贪心错了。之后发现40很有灵性，就想起了之前有一道题也是40，然后拆成两半dfs

T2:明显分层图裸题，然后数组开太小了

T3:不是很明显多重背包吗？数组开小了

记得数组开大些QVQ

总结

以上是生活随笔为你收集整理的欢乐纪中某B组赛【2019.1.26】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。