Virtual NOIP 2018 Day3 总结

## 上午 ### T1 三次方 $40$分：进行枚举即可。 $100$分：首先，根据立方差公式，$a^3-b^3=(a-b)(a^2+ab+b^2)$，而由于$p$是质数，且由$a,b\in \mathbb{N^{*}}$得$a^2+ab+b^2\ge 3$，因此：$a-b=1,a^2+ab+b^2=p$。 联立得二次方程$3a^2-3a-p+1=0$，即$a^2-a-\frac{p-1}{3}=0$。由于上述方程有整数根，因此$3\mid p-1$。 用整除的条件判断可行性，再解方程验证即可。 ### T2 积木 $50$分：对于$10$步或以内有解的数据，直接$\text{dfs}$搜索，并令最大迭代层次为$10$即可。 $100$分：考虑数据范围，计算量为$4^{20}=2^{40}$，因此我们可以试着使用$\text{Meet in the Middle}$。 或者可以使用$\text{IDA*}$，令乐观估价函数为当前状态中不在自己位置上的数的数量即可。 ### T3 对答案 $30$分：直接枚举每个"*"的长度。 $70$分：采用动态规划。令状态$f[i][j]$表示模式串的$[1,i]$能否和匹配串的$[1,j]$完全匹配，则对不是`'*'`或`'.'`但$a[i]=b[j]$的$j$，$f[i][j]=f[i-1][j-1]$；对`'.'`，$f[i][j]=f[i-1][j-1]$；对`'*'`，$f[i][j]=f[i][j-2]\mid f[i-k][j-2]$（后一项要求$a[i]=a[i-1]=a[i-2]=\cdots=a[i-k+1]=b[j-1]\left (k\in\mathbb{N^{*}}\right)$，即都等于`'*'`前的字符；若`'*'`前是`'.'`，则只要求这些字符彼此相等即可）。 $100$分：对动态规划进行优化。 观察下图：  在$f[7][6]$和$f[8][6]$的计算中，我们的计算明显有重复。可以发现，当`b[j]='*'`时，$f[i][j]$的计算仅仅比$f[i-1][j]$多或了$f[i][j-2]$。因此，可以把最后一条方程优化为$f[i][j-2]\mid f[i-1][j]$。这个优化思路类似于一般动态规划中的求前缀最值的问题，具体依然可以复习[绝美的挣扎](https://www.luogu.org/problemnew/show/T44253)。 ## 下午 ### T1 打扑克 $30$分：暴力搜索。 $100$分：记录每一个数的个数，$1$和$2$全部组成对子，$[3,n]$先判断能不能和前两个数组成顺子（只组成$1$个），剩余的组成对子。 或者使用$\text{dp}$。设$f[i][j]$为计算到$i$，且前两个数剩余的$\min$值为$j$的最多牌对数，动态规划计算即可。 ### T2 清零 $40$分：枚举买的区间和清零的区间即可。注意到每个玩具的价格都是正数，因此由贪心策略，清零的区间大小一定是$D$。$\text{O}(n^3)$。 $60$分：首先枚举买的区间。对于某个买的区间，由贪心策略，清零的区间一定是买的区间内 和最大的区间。如何求出某段区间内和最大的、长度为$k$的区间呢？可以考虑用前缀和技巧预处理出所有$k$区间的和，再用单调队列的方法维护买的区间内$k$区间和的最大值即可。 $100$分：题目求的是最大值，因此我们可以考虑用二分法。我们二分最多能买的玩具个数，在判断$x$是否可行时，可以枚举区间$[i,i+x-1]$，并使用单调队列维护区间内$k$区间和的最大值。$\text{O}(n\log n)$。 我们还可以使用双指针法（尺取法）。我们枚举答案区间的右端点，那么左端点的可行性是单调的。同样使用单调队列维护$k$区间和的最大值。 ### T3 星星 $10$分：枚举四个点，$\text{O}(n^4)$。 $[40,60]$分：枚举两个三度顶点，并对与它们相邻的点求交，$\text{O}(n^3)$。可以使用压位$\text{(bitset)}$优化，常数性能有较大提升。 $70$分：按点的度数分治。把点按度数分成轻点（$\deg (x)\le \sqrt{m}$）和重点（$\deg(x)>\sqrt {m}$）的两类，并对它们采用不同的枚举策略。对于轻点我们枚举它的出边，因为它的出边很少；对于重点我们枚举其余重点检查是否相邻。 具体实现方法如下：我们仍旧枚举两个三度顶点之间的边，如果这两个三度顶点中存在一个是轻点，那么我们就枚举这个轻点的所有出边，用 蛤 习 表 检查出边的$v$是否与重点连通；如果两个顶点都是重点，那么这样的边不会超过$m$条，同样枚举其中某一个点的出边，判断是否与另一个点连通即可。 如何用蛤 习 表检查这条边是否存在呢？我们维护一个`unordered_set`，对于某一条边$i-j$，我们用$ni+j$和$nj+i$两个无错 蛤 习 值来代替，如果`set`中存在其中某个元素，就说明存在这条边。 $100$分：再次进行转化。原题可以转化为求一条边在多少个三元环中出现（设在$x$个三元环中出现，则对答案的贡献为$\frac{x^2-x}{2}$）。 接下来就要体现枚举的艺术了。对于有轻点的环，我们枚举边来统计；对于没有轻点（即三个点都是重点）的环，我们在重点集合中枚举统计。 下面是这题的$\text{std}$。这个程序中介绍了`unordered_set`的用法，可以学习一下。 ```cpp #include<bits/stdc++.h> #include<tr1/unordered_set> using namespace std; typedef long long ll; const int maxn = 1e5+5; int vis[maxn],link[maxn],d[maxn]; vector<int> v[maxn]; tr1::unordered_set<ll> st; void init(int x){ for(int i = 1; i <= x; i++) { d[i] = vis[i] = link[i] = 0; v[i].clear(); } st.clear(); } void add(int x,int y){ v[x].push_back(y); d[x]++; } int main(){ int n,m,a,b,y,z,zh; ll ans,sum; int T;cin>>T; while(scanf("%d%d",&n,&m)!=EOF){ init(n); for(int i = 0; i < m; i++){ scanf("%d%d",&a,&b); add(a,b); add(b,a); st.insert((ll)a*n+b); st.insert((ll)b*n+a); } zh = sqrt(m); ans = 0; for(int i = 1; i <= n; i++){ vis[i] = 1; for(int j = 0; j < v[i].size(); j++){ y = v[i][j]; link[y] = i; } for(int j = 0; j < v[i].size(); j++){ y = v[i][j]; //Edge i-y sum = 0; //Count if(vis[y]) continue; //The edge has counted by the vertex y if(d[y] <= zh){ //y is light //Count every count which connects with y for(int k = 0; k < v[y].size(); k++){ z = v[y][k]; if(link[z] == i) sum++; } } else{ //Heavy for(int k = 0; k < v[i].size(); k++){ z = v[i][k]; //Find from the i side if(st.find((ll)z*n+y) != st.end()) sum++; } } ans += sum*(sum-1)/2; } } cout<<ans<<endl; } return 0; } ```