20200724比赛总结

这是省选范围的比赛，可是这一次的比赛考的比较简单，但还是有许多值得学习的地方，所以我在这里写下比赛总结。 $$\text{\color{red}Talk\; is\;cheap,show\;my\;summary.}$$ -------------- [T1](https://www.maipdf.com/pdf/?email=jem2Yq18UeUU.z) 这一道题题目还是有趣，在没有想到的时候我一度以为这是**变异的二分图匹配**。可是钱与钱之间可以进行**拆分**，即对于一个欠钱的人，ta可以同时还$i(i\geq 1)$个人的钱，与此同时，对于一个债主，ta可以同时接受$k(k\geq 1)$个人的还钱。 考虑题目说所有的人不关心自己是从哪里拿到的钱，而是拿没拿到应得的钱，所以我们可以开两个数组表示欠钱的人该换多少，债主该拿多少，简化问题后再做分析。 现在我们来考虑性质。 ### 前提 我们设集合$S$为借钱的人的集合，集合$T$为债主们的集合。集合存的是该还多少钱|该拿多少钱。 设一个集合的$|S|$表示集合$S$中点权值之和。 引理： 1. 选取两个权值和相等的子集总是比不相等的优秀 这个引理用数学语言证明起来很麻烦，所以我们可以大致理解一下。 因为相等的话所有的连边都是在内部进行，但是不相等的话就至少有一条边伸到外部去。 2. 选取两个集合，总数目越小的越优 因为对于两个相等的集合，他们所对答案产生的贡献为$size(S\rq)+size(T\rq)-1$ 有人说，这幅图就直接推翻了你的理论啊！  可是这明显是当时思维不深的表现，但需要注意的是**思考不缜密或者思考不深**都会让一些转化性质的题直接暴毙。 对于上面的一幅图，明显违背了我们的假设 因为这个集合内部本身就有**小型的，满足条件**的集合  悖论消失 -------------------- ## 阐述 设$S\rq \subseteq S\;\;$,$\;\;T\rq \subseteq T$ - 如果$|S\rq|\neq |T\rq|$ 那么无论如何，总有一个集合的点权值没法用完，需要到外面去。相当于消去两个集合后增加了一个点。可能是最优的选择，但绝大多数不是最优的选择。(预知后事如何，且听下面分解) - 如果$|S\rq|= |T\rq|$ 那么集合内部就可以约去，而上面说的**可能是最优**就是你误打误撞将一个相等的子集的子集给分解了。 所以我们就可以拿出这个像是**贪心**，像是**dp**的东西了。 ```cpp #include<cstdio> #include<algorithm> #define ri register int #define Starseven main using namespace std; const int N=30; int read(); void write(int);//要记得自己加换行和空格 int n,m,zhuang; int cost[N]; int out[N],in[N],numout,numin,ans,num; bool visout[N],visin[N]; struct node{ int id,val; }bag[1<<22]; void Init(void){ freopen("ex_bill3.in","r",stdin); return ; } int Get_bag(int x){ int num=1,re=0; while(x){ if(x&1) re+=in[num]; x>>=1;num++; } return re; } bool cmp(const node &a,const node &b){ if(a.val!=b.val) return a.val<b.val; return a.id>b.id; } bool Is(int x){ int num=1; while(x){ if(x&1) if(visin[num]) return false; x>>=1;num++; } return true; } int Find(int x){ int l=1,r=zhuang; while(l<r){ int mid=l+r>>1; if(bag[mid].val>=x) r=mid; else l=mid+1; } if(bag[l].val!=x) return 0; while(!Is(bag[l].id)&&bag[l].val==x) l--; while(!Is(bag[r].id)&&bag[r].val==x) r++; if(bag[r].val==x) return r; if(bag[l].val==x) return l; return 0; } bool Dfs(int x,int re,int st){ if(x==0){ int j=Find(re); if(j==0) return false; int y=bag[j].id,num=1,cnt=0; while(y){ if(y&1) visin[num]=true,cnt++; y>>=1;num++; } // cout<<st<<" "<<cnt<<endl; ans+=st+cnt-1; return true; } for(ri i=1;i<=numout;i++){ if(visout[i]) continue; visout[i]=true; bool ok=Dfs(x-1,re+out[i],st); if(!ok) visout[i]=false; else return true; } return false; } int Starseven(void){ // Init(); n=read(),m=read(); for(ri i=1;i<=m;i++){ int ai=read(),bi=read(),ci=read(); cost[ai]-=ci;cost[bi]+=ci; } for(ri i=1;i<=n;i++) if(cost[i]<0) out[++numout]-=cost[i]; else if(cost[i]>0) in[++numin]+=cost[i]; if(numout>numin) swap(numout,numin),swap(out,in); sort(out+1,out+1+numout);sort(in+1,in+1+numin); zhuang=1<<numin;zhuang--; for(ri i=0;i<=zhuang;i++) bag[i].val=Get_bag(i),bag[i].id=i; sort(bag+1,bag+zhuang+1,cmp); for(ri i=1;i<=numout;i++){ bool ok=true; while(ok==true) ok=Dfs(i,0,i); if(num==numin) break; } write(ans); return 0; } int read(){ char ch=getchar(); int re=0,op=1; while(ch<'0'||ch>'9'){ if(ch=='-') op=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ re=(re<<3)+(re<<1)+ch-'0'; ch=getchar(); } return re*op; } void write(int x){ if(x<0){ putchar('-'); x=-x; } if(x>9) write(x/10); putchar(x%10+'0'); return ; } /* 4 4 1 2 1 2 3 1 3 4 1 4 1 1 */ /* 4 3 1 2 1 2 3 2 3 4 3 */ ``` 这是本人在考场上打的代码，与正解有一点不同，现在将正解展示 标程如下 ```cpp #include<bits/stdc++.h> using namespace std; const int N=1010; int a[N],c[N],t[N]; int n,m; int cmax; int ans=0; int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar(); return s*w; } void dfs(int x,int num,int val){ if(num>cmax) return; t[num]=x; if(val==0){ if(num<cmax){ // cout<<"qwq"<<cmax<<" "<<num<<" "; memset(c,0,sizeof(c)); cmax=num;//cout<<cmax<<endl; for(int i=1;i<=num;i++) c[i]=t[i]; return; } else return; } for(int i=x+1;i<=n;i++) if(a[i]!=0){ dfs(i,num+1,val+a[i]); } t[num]=0; } int work(int u){ memset(c,0,sizeof(c));//最终结果 memset(t,0,sizeof(t)); cmax=N; dfs(u,1,a[u]); for(int i=1;i<=cmax;i++) a[c[i]]=0; return cmax; } int main(){ // freopen("ex_bill1.in","r",stdin); n=read(),m=read(); for(int i=1;i<=m;i++){ int u=read(),v=read(),w=read(); a[u]-=w;a[v]+=w; } ans=0; for(int i=1;i<=n;i++){ if(a[i]!=0){ ans+=work(i)-1; } } printf("%d\n",ans); return 0; } ```  红色为我的代码，绿色为标程，慢不了多少的，对吧。 (~~暴力还是太惨了~~) ----------------------- [T2](https://pdf.maitube.com/pdf/?e=jgIShPWgG.u9Ut) 这道题很值得做一下，它本身不需要太多的知识，或者换而言之，它基本不需要知识（对于省选来说，甚至是对于提高组来说），但是这个题目本身的思路是很值得学习的。 有人会说：这不就是基环树模板题吗？ 但是对不对，只要勤动脑子，这题不需要基环树的基础。 但是还是要学习基环树，有模板可套谁想要去想啊qwq --------------- 题目分析：