- B 题 https://ac.nowcoder.com/acm/contest/11254/B 最小生成树
大意：给定一个n * m 的白色棋盘，现要将白色棋盘染成黑色，每个格子对应一个染色的价值，如果一个 “田字格” 已经有三个格子被染成了黑色，那么可以免费将第四个格子也染成黑色。问将棋盘全部染成黑色的最小花费是多少。
思路：比赛时一直在想贪心，说到底还是对此类题目不够敏感。对于很多问题，我们不妨从图的角度去思考问题，有时或许会达到意想不到的效果。我们把n行 m列看成一个个点的话，那么我们将第 x 行 y 列的格子染色就相当将 x , y 两点进行连通，对于相邻的四个格子 (x1,y1) (x1,y2) (x2,y1) (x2,y2)
如果我们把前三个格子染色，即相当于把 x1,y1,x2 连通，第四个格子是可以不用染色的，也就是说，我们我们使其全连通，没有环，并且使得权重之和最小，显然这就是最小生成树，用krusal 就可以做了。对于纵坐标的点我们可以全部加个偏移量 n 这样就不会出现重复的点了。
代码如下：此题明显是稠密图，最好用 prim 算法。下面是用kruskal 实现的代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5010;
int g[N][N];
int n,m,a,b,c,d,p,k;
struct node{
int a,b,c;
bool operator <(const node &W)const
{
return c<W.c;
}
}e[N*N];
int fa[N*2];
int find(int x)
{
if(fa[x]!=x)return fa[x]=find(fa[x]);
return fa[x];
}
int kusal()
{
//总共有 n+m 个点
for(int i=1;i<=n+m;i++)fa[i]=i;
int cnt=0;
int res=0;
sort(e+1,e+1+k);
for(int i=1;i<=k;i++)
{
int a=e[i].a,b=e[i].b,c=e[i].c;
a=find(a),b=find(b);
if(a!=b)
{
cnt++;
res+=c;
fa[a]=b;
}
if(cnt==n+m-1)break;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>a>>b>>c>>d>>p;
int lst=a;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
g[i][j]=(1LL*lst*lst*b+1LL*lst*c+d%p)%p;
e[++k]={i,j+n,g[i][j]};
lst=g[i][j];
}
int t=kusal();
cout<<t<<"\n";
return 0;
}
总结：对于某些问题思考时，往图的方向去思考也是一种思维方式。
- C题 https://ac.nowcoder.com/acm/contest/11254/C
大意：有一个空的矩阵，现在需要在矩阵规定的位置填一些非负数，并使其满足要求的某行某列的最大值的情况。确保存在合法的填数方式。要求矩阵数字之和最小，输出最小的数字之和。
思路：类似于数独，在给出的特定的位置填上一些数字，并且满足要求某行某列的最大值是规定的值。通过题目我们就会发现，此题很复杂，模拟都很困难。对于此类 “牵一发而动全身” 的题，我们考虑从图论的角度去思考。对于最坏情况，显然我们对于每行每列要求的最大值都填上一个对应的数。现在要求填的数之和尽可能小，所以我们在满足要求的情况下，尽量去减少填的数字。这时我们会自然而然的想到，对于某行某列规定的最大值相同的情况，我们只需要在它们的交叉位置填上一个数就好了。这样我们就可以减少一个要填的数字，也就是说，对于某些最值相同的行列，我们把行看成一系列点，把列看成一系列点，每当行和列连一条边，我们就可以减少一个要填的数，对于多行和某一列的，填的数也是最多减少一个。换句话说，也就是行列 一 一 对应最大数量就是我们“有效减少 ”的数量。显然这是个最大二分图匹配问题，用匈牙利算法来实现。
总结：对于“牵一发而动全身”的问题，我们考虑从图论的角度思考问题，一步步分析问题。
- E 题 https://ac.nowcoder.com/acm/contest/11254/E 数学
大意：t 组测试样例，（1<=t<=1e5）, 每次给定一个 n （1<=n<=1e18） 求满足以下条件的 (x,y) 的对数， 1<=x<=y<=n x 2 + y 2 x^2+y^2 x2+y2是 x y + 1 xy+1 xy+1 的整数倍。
思路：打表盯着数据看了半天，眼都瞪瞎了，就是找不出规律。但如果只是道规律题，也没有写这个题的总结的必要了，关键是这个题的分析方式，很巧妙。对于题目给出的条件，我们可以列出 x 2 + y 2 = k ( x y + 1 ) x^2+y^2=k(xy+1) x2+y2=k(xy+1) 其中 k 为正整数，如果我们把 y 当成常数的话，式子可以变形为 x 2 − k y x + y 2 − k = 0 x^2-kyx+y^2-k=0 x2−kyx+y2−k=0 根据韦达定理 有 x 1 + x 2 = k y x_1+x_2=ky x1+x2=ky x 1 x 2 = y 2 − k x_1x_2=y^2-k x1x2=y2−k
随着 x 1 x_1 x1 的增大 ， x 2 x_2 x2 必然是减小 ，极限条件下 x 2 x_2 x2=0 解得 x 1 = k y x_1=ky x1=ky 代入原方程 的 k = y 2 k=y^2 k=y2 则 x 1 = y 3 x_1=y^3 x1=y3
所以 ( y , y 3 ) (y,y^3) (y,y3) 为一组合法解 ，不妨记为 ( a , a 3 ) (a,a^3) (a,a3)
b 0 = a b_0=a b0=a
b 1 = a 3 b_1=a^3 b1=a3 此时代入方程得 k = a 2 k=a^2 k=a2 又因为 y = a 3 y=a^3 y=a3 代入我们的另一个根 b 2 = a 2 b 1 − b 0 b_2= a^2b_1-b_0 b2=a2b1−b0 是大于 b1 的 所以（b1,b2）又是一组解
b 2 = a 2 b 1 − b 0 b_2=a^2b_1-b_0 b2=a2b1−b0 …依次类推
…
所以我们可以根据递推式，提前把表打好，排好序，用的时候二分查找就好了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=1e18+10;
LL a[3000010],cnt;
LL mx=1e6;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
for(LL i=2;i<=mx;i++)
{
LL lt=0,nw=i,bk;
while(1)
{
if(nw>(N+lt)/(i*i))break;
bk=nw;
nw=i*i*nw-lt;lt=bk;
a[++cnt]=nw;
}
}
sort(a+1,a+1+cnt);
int _;
cin>>_;
while(_--)
{
LL n;
cin>>n;
int ans=upper_bound(a+1,a+1+cnt,n)-a;
cout<<ans<<"\n";
}
return 0;
}
总结：重点在于此题的分析方式，根据单调性找到边界位置的解，然后反推回去。
- F 题 https://ac.nowcoder.com/acm/contest/11254/F 模拟题，dfs 爆搜
大意：先要从 1~13中选出 n 个数字,(1<=n<=4),每个数字可以多次用，可以将四个数字任意方式排序并任意插入加减乘除运算法，使得表达式的结果等于 m,(1<=m<=1e9)。但是在这四个数字加上若干运算符的结果等于 m 的集合中，必须每一个表达式运算过程出现小数才算一组合法解，求和合法解得个数， 并按字典序从小到大输出每组合法解。
思路：n<=4 直接爆搜就完事了。但是题目有“合法解”的要求，所以我们先确定 n 个数字，然后在插入符号，判断是不是合法解。为了好写，我们插入符号的爆搜中返回值，分三种情况就好了，无解返回 0，小数解返回1，整数解返回 2, 将每次返回值进行或运算，显然只有当最终结果为 1 的时候才是一组合法解。
- J 题 https://ac.nowcoder.com/acm/contest/11254/J 思维题
大意：有 n 个点的无向完全图，每条边有都有黑白其中一种颜色，现要找到 (a,b,c)三边，满足三边颜色相同，且 a<b<c 的三角形的个数。（n<=8000), 由于数据很多，采用给出的随机生成数据随机生成。
思路：显然暴力枚举是不行的，肯定超时。所以正难则反，我们考虑同色三角形的个数不好考虑，显然我们可以考虑异色三角形的个数。因为就两种颜色，所以异色三角形也就两种组色方式，（黑黑白）（黑白白），抓住共同点，其中必能引出黑白两种颜色的边，对于另外一条边，无论是黑还是白必定都会造成剩下两点的其中一点也是异色边。只要有一个点引出两条异色边那么必定能构成异色三角形，但是另外一个点也是这样的点，所以我们会重复，要除以2.
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace GenHelper
{
unsigned z1,z2,z3,z4,b,u;
unsigned get()
{
b=((z1<<6)^z1)>>13;
z1=((z1&4294967294U)<<18)^b;
b=((z2<<2)^z2)>>27;
z2=((z2&4294967288U)<<2)^b;
b=((z3<<13)^z3)>>21;
z3=((z3&4294967280U)<<7)^b;
b=((z4<<3)^z4)>>12;
z4=((z4&4294967168U)<<13)^b;
return (z1^z2^z3^z4);
}
bool read() {
while (!u) u = get();
bool res = u & 1;
u >>= 1; return res;
}
void srand(int x)
{
z1=x;
z2=(~x)^0x233333333U;
z3=x^0x1234598766U;
z4=(~x)+51;
u = 0;
}
}
using namespace GenHelper;
bool edge[8005][8005];
int cnt[80005][2];
int main() {
int n, seed;
cin >> n >> seed;
srand(seed);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
edge[j][i] = edge[i][j] = read();
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
bool x=edge[i][j];
cnt[i][x]++;
cnt[j][x]++;
}
LL sum=0;
for(int i=0;i<n;i++)
sum+=(LL)cnt[i][0]*cnt[i][1];
cout<<1LL*n*(n-1)*(n-2)/6-sum/2<<"\n";
return 0;
}
总结：正难则反，这种思维方式很重要。