emmm...坐大牢
2021-07-24 12:00:00 至 2021-07-24 17:00:00
B Black and white
题意 :给定nm白色棋盘,每个格子价格用以下方式生成:
A0 = a
A(i+1) = (Ai * Ai * b + Ai * c + d)% p
cost c(i, j) = A(m(i-1)+j)
并且任意两行两列形成的四格,有三个黑色另一个白色格子即可不花钱染成黑色
问最少需要多少钱可以全部染成黑色
看成1 -- n+m 构成的完全图,求最小生成树 prime kruskasl√
题目数据很大,我被卡吐了,注意控制内存之类的 sb题
#include <bits/stdc++.h>
using namespace std;
long long a,b,c,d,p;
int n,m;
const int N=1e6+50;
int f[5000*2+50];
struct dd{
int x,y;
};
vector<dd> ed[N];
int get(int x)
{
return f[x]==x ? x : f[x]=get(f[x]);
}
int main()
{
cin >> n >> m >> a >> b >> c >> d >> p;
for(int i=1;i<=n+m;i++) f[i]=i;
for(int i=1;i<=n;i++)
{
for(int j=n+1;j<=n+m;j++)
{
a=(a*a*b+a*c+d)%p;
ed[a].push_back(dd{i,j});
}
}
int ans=0,x=0,y=0;
for(int i=0;i<p;i++)
{
for(auto z : ed[i])
{
x=get(z.x),y=get(z.y);
if(x!=y)
{
ans+=i;
f[x]=y;
}
}
}
cout << ans << 'n';
return 0;
}
J Counting Triangles
题意 : 完全无向图,边有黑白两种情况,找三条边同色边组成的三角形个数。
题目在限定范围内给测试数据
构成三角形只有同色或者一种不同的,一种不同的有两个异色角,故统计异色角数/2就是不同色三角形个数,总个数减去即为答案
#include <bits/stdc++.h>
#define ri int
typedef int lll;
typedef long long ll;
using namespace std;
const ll mod=1000000007;
const ll inf=999999999;
const ll N=5e3+5;
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;
}
}
bool edge[8005][8005];
int main()
{
ll n, seed;
cin >> n >> seed;
GenHelper::srand(seed);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
edge[j][i] = edge[i][j] = GenHelper::read();
ll ans=n*(n-1)*(n-2)/6; //总数cn3 //注意n取ll或者乘1ll
ll now=0;
for(ri i=0;i<n;i++)
{
now=0;
for(ri j=0;j<n;j++)
{
if(i!=j)
{
if(edge[i][j]) ++now;
}
}
ans-=(now*(n-1-now)/2);
}
cout << ans << 'n';
return 0;
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论,欢迎说说您的想法!