\(Round1~D1T1\)外星千足虫
\(BSOJ2793\)-- 高斯消元解异或方程组
简述
有 \(n\)个数 \(\{a_i\}\)
给出 \(m\)个信息, 每个信息给出 \(\displaystyle{(\sum_{i=1}^m a_{b_i})\bmod 2}\)(\(\{b_i\}\)是 \({1,2,\cdots,n}\)的子集)
求最少几次操作即可确定可能取值
- Solution
- \(70pts'\)
给出的信息可以转化为 \(\displaystyle{\oplus_{i=1}^m a_{b_i}}\)
因此问题转化为求异或方程组最少几行就可以有解
高斯消元求自由元个数即可
复杂度 \(O(n^3)\)
\(100pts'\)
考虑高斯消元集合异或操作太浪费, 使用 \(bitset\)优化异或的特殊情况
复杂度 \(O(\frac{n^3}{64})\)
- Code
- int n,m,ans;
- bitset<N> a[M];
- int main(void){
- re int i,j;n=read()+1,m=read();
- for(i=1;i<=m;++i)
- for(j=1;j<=n;++j)a[i][j]=gc();
- for(i=1;i<n;++i){
- for(j=i;j<=m;++j)if(a[j][i])break;
- ans=max(ans,j);
- if(j>m)return puts("Cannot Determine"),0;
- if(i^j)swap(a[i],a[j]);
- for(j=1;j<=m;++j){if(i==j||!a[j][i])continue;a[j]^=a[i];}
- }
- printf("%d\n",ans);
- for(i=1;i<n;++i)puts((a[i][n])?"?y7M#":"Earth");
- return 0;
- }
错误
把 8 行的初始设为了 i+1
\(Round1~D1T2\)地精部落
\(BSOJ2794\)-- 补集思想简化状态 + 逆向递推计数 dp
简述
求长度为 \(n\)的排列满足任意 \(i\in[2,n-1]\)有 \(a_i>a_{i-1}\&a_i>a_{i+1}\)或 \(a_i<a_{i-1}\&a_i<a_{i+1}\)
Solution
形象来说本题是要我们求 //\ 和 // 的数量
首先考虑若排列 \(\{a_i\}\)满足要求那么 \(\{b_i\}(b_i=n-a_i)\)也满足要求
那么我们单求 // 就可以了(所以第一个不为 \(1\))
紧接着我们会发现这个计数题正着做不好做, 但构造任意一个序列是容易的所以我们逆推, 用反构造 (合法 \(\rightarrow\) 合法)的过程去实现 \(dp\)
已经有 \(1\rightarrow i\)首位为 \(j\)的序列, 设情况有 \(dp_{i,j}\)个
\(j-1\)不是首位, 那么交换 \(j-1,j\)没有影响, 贡献 \(dp_{i,j-1}\)
\(j-1\)是首位, 那么去掉 \(j\), 就得到一个 //\ 序列,\(a_i\rightarrow i-a_i\)即可, 贡献 \(dp_{i-1,i-j+1}\)
注意滚动一下
- Code
- int main(void){
- re int i,j,now=0;
- n=read(),mod=read();dp[now][2]=1;
- for(i=3;i<=n;++i){
- now^=1;
- for(j=2;j<=i;++j)dp[now][j]=Mod(dp[now][j-1]+dp[now^1][i-j+1]);
- }
- for(i=2;i<=n;++i)ans=Mod(ans+dp[now][i]);
- printf("%d\n",Mod(ans+ans));
- return 0;
- }
\(Round1~D1T3\)大陆争霸
\(BSOJ2795\)-- 最短路 + 拓扑排序
简述
给出一个有向图, 有一些点必须在限制他的点之后到达他, 求 \(1\rightarrow n\)的最短路
Solution
考虑到限制实际上是让我们满足限制关系 \(DAG\)拓扑序的去完成最短路
因此我们就魔改最短路, 加入 \(Topsort\)的过程即可
设 \(dis_x\)表示 \(1\rightarrow x\)的最短路 (中间未 \(Topsort\) 完不一定满足要求)
\(real_x\)表示满足拓扑序关系下 \(1\rightarrow x\)的实际最短路(限制我的都被走完)
注意: 每次用 \(real\)去更新 \(dis\), 只有被限制的更新完了才去更新别的, 这样才保证拓扑序
Code
核心
- inline void Dijkstra(void){
- re int i,x,v,d;
- for(i=1;i<=n;++i)dis[i]=INF;
- q.push((Node){1,dis[1]=real[1]=0});
- while(!q.empty()){
- x=q.top().x,d=q.top().dis,v=max(dis[x],real[x]),q.pop();
- if(v^d)continue;
- for(i=h[x];i;i=e[i].next){
- re int y=e[i].to;
- if(v+e[i].v<dis[y]){dis[y]=v+e[i].v;if(!deg[y])q.push((Node){y,max(dis[y],real[y])});}
- }
- for(re int y:g[x]){real[y]=max(real[x],v);if(!--deg[y])q.push((Node){y,max(real[y],dis[y])});}
- }
- }
\(Round1~D2T1\)所驼门王的宝藏
\(Round1~D2T3\)星际竞速
给一张 \(DAG\), 有边权, 每个点有出发点权. 求最小代价使得每个点都被经过.
遇到点权就拆入出点
建图: 对起点 \((S,i',1,a_i)\): 表示从 \(i\)直接出发
\((S,i,1,0),(i',T,1,0)\)
对每条边 \((x',y,1,w_{x,y})\)
跑最小费用流即可
\(Round2~D1T3\)猪国杀
来源: http://www.bubuko.com/infodetail-3342831.html