前言

空間開小導致無法$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】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。