2021牛客多校3-B、J

比赛链接

https://ac.nowcoder.com/acm/contest/11254

B Black and white

思路：

1、十分巧妙，构造二分（部）图：对于位置(i,j)，若其被染黑，则在Ai和Bj之间连一条边，即A是n个点组成的点集，B是m个点组成的点集；
2、我们可以发现，魔法操作并不会改变该二分图的连通性（十分重要，画画图可以验证）；
3、实际上一开始染黑一些格再通过魔法操作使格子全部染黑，要求一开始的状态保证二分图联通即可；
4、问题转换为求最小生成树，采用桶排序优化边的排序部分。

细节：

1、通过表达式生成矩阵时，int类型会溢出。

AC代码

#include 
using namespace std;
const int maxn=5e3+10;
typedef long long ll;int fa[maxn<<1];
int val[maxn][maxn];
vector<pair<int,int> > e[100010];void ini(){for(int i=1;i<(maxn<<1);i++) fa[i]=i;
}int find(int x){if(x==fa[x]) return x;else return fa[x]=find(fa[x]);
} int main() {int n,m,a,b,c,d,p;cin>>n>>m>>a>>b>>c>>d>>p;for(int i=0;i<n;i++){for(int j=0;j<m;j++){a=((ll)a*a*b+(ll)a*c+d)%p;//溢出 val[i][j]=a;//桶排序 e[val[i][j]].push_back(make_pair(i,j+n));}}ini();ll ans=0;for(int i=0;i<p;i++){for(int j=0;j<(int)e[i].size();j++){int f1=find(e[i][j].first),f2=find(e[i][j].second);if(f1!=f2){ans+=i;fa[f1]=f2;}}}cout<<ans<<endl;return 0;
}

参考

hei___hei队的比赛代码

J Counting Triangles

思路

1、题目一开始是一个随机数程序，对一幅完全图进行黑白染色操作，粘上去就好；
2、实际问题是对一个黑白染色的完全图求同色△的个数；
3、正面考虑是O（n ^3）的做法，再优化也不可能优于O（n ^2），会超时；
4、△的总数是n*(n-1)*(n-2)/6,我们可以求出异色△，再减去总数；
5、异色△有两个顶点连接的两条边异色，对每个顶点将其连接黑边和白边的总数相乘求和除2可得异色△数。

细节

int数据溢出

AC代码

#include 
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 s1[8005],s2[8005];int main() {int n, seed;std::cin >> n >> seed;srand(seed);for (int i = 0; i < n; i++)for (int j = i + 1; j < n; j++){if(read()) s1[i]++,s1[j]++;else s2[i]++,s2[j]++;}ll ans=1ll*n*(n-1)*(n-2)/6;//long long类型转换 ll sum=0;for(int i=0;i<n;i++)sum+=1ll*s1[i]*s2[i];ans-=sum/2;std::cout<<ans<<'\n';return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！