2021牛客暑期多校训练营3,签到题BEFJ
【摘要】
题号 标题 已通过代码 通过率 团队的状态 A Guess and lies 点击查看 33/437 未通过 B Black and white 点击查看 785/5177 未通过 (最小生成树) C M...
题号 标题 已通过代码 通过率 团队的状态
A Guess and lies 点击查看 33/437 未通过
B Black and white 点击查看 785/5177 未通过 (最小生成树)
C Minimum grid 点击查看 291/759 未通过
D Count 点击查看 13/57 未通过
E Math 点击查看 1030/3674 通过 (数学,预处理)
F 24dian 点击查看 492/1301 未通过 (大模拟,dfs)
G Yu Ling(Ling YueZheng) and Colorful Tree 点击查看 51/193 未通过
H Ling Qiu, Luna and Triple Backpack 点击查看 5/30 未通过
I Kuriyama Mirai and Exclusive Or 点击查看 131/556 未通过
J Counting Triangles 点击查看 1362/4223 通过 (性质,结论)
B Black and white
题意:
- 给出一个n*m的棋盘,每个点有被染成黑色的代价cij, 对于任意两行两列的四个相交方格,如果其中三个是黑色方格,那么可以零成本地将第四个方格染成黑色。求染黑棋盘的最低成本。
- 由于格子的数量很多,权重由公式产生,
A0 = a,A(i+1) = (Ai * Ai * b + Ai * c + d)% p
,其中A(m*(i-1)+j)
是第i行和第j列的网格的成本c(i, j)。
思路:
- 对于⼀个位置(i, j) ,如果该格⼦是⿊⾊,我们连⼀条ai 到bj 的边。操作不改变连通性,由此容易证明,可以全 部染⿊等价于初始联通。求解最⼩⽣成树即可。复杂度为 O(n^2)。
- 对于 n*m 的矩阵,需要 n+m-1 格子涂色,分别是每行对应一个格子,每列对应一个格子,减去重复的一个。
- 考虑任意两行两列所成的四个坐标,若已经出现了三个坐标,则第四个就不需要了。
- 考虑如何判断新加入点是否需要,即它不会由之前的坐标推出来。根据题目一行一点,一列一点,不如将行列看成点,现将两行点和两列点放在同一个连通块里,第四个坐标放进来,行坐标和列坐标连通,即不需要,用并查集维护,再根据边权从小到大去跑最小生成树即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
int fa[maxn+10];
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
vector<pair<int,int> >G[maxn];
int main(){
int n, m; cin>>n>>m;
LL a, b, c, d, p; cin>>a>>b>>c>>d>>p;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
a = (a*a*b+a*c+d)%p;
G[a].push_back(make_pair(i,j+n));//第i行和第j列有一条w=a的边
}
}
LL ans = 0, cc = 0; init(n+m);
for(int i = 0; i <= p; i++){//从小到大枚举权值
for(auto u : G[i]){
int x = find(u.first), y = find(u.second);
if(x != y){
ans += i;
merge(x,y);
}
}
if(cc==n+m-1)break;
}
cout<<ans<<"\n";
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
E Math
题意:
- 给出一个n,计算有多少对正整数(x,y),使得
xy+1|x^2+y^2
, 1<=x,y<=n
思路:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e6+10;
const LL inf = 1e18;
LL a[maxn], cnt;
int main(){
a[cnt++] = 1;
for(LL k = 2; k*k*k<=inf; k++){
LL x = k, y = k*k*k;
a[cnt++] = y;
while(y <= (inf+x)/k/k){
x = k*k*y-x;
swap(x,y);
a[cnt++] = y;
}
}
sort(a, a+cnt);
int T; cin>>T;
while(T--){
LL n; cin>>n;
cout<<upper_bound(a,a+cnt,n)-a<<"\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
F 24dian
题意:
- 给出n张牌,求凑出m点的方案数,输出方案。(每张牌为1-13, 过程需要有分数)
思路:
- 按照题⾯模拟即可。暴⼒枚举第⼀次或最后⼀次的两数均可
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5e5+10;
int n, m, ans, as[maxn][5];
int ok; double a[5];
bool chk(double x){x-=(int)x;return x>1e-6&&x<1-1e-6;}
void dfs1(int cur, int flag){//枚举所有可行方案
if(ok==3)return ;
if(cur==n){
if(abs(a[1]-m)<1e-6){
if(flag)ok = 1;
else ok = 3;
}
return ;
}
double A[5];
for(int i = 0; i <= 4; i++)A[i]=a[i];
for(int i = 1; i <= n-cur+1; i++){
for(int j = 1; j <= n-cur+1; j++){
if(i!=j){
for(int k = 1; k <= 4; k++){
int w = flag;
if(k==1)a[i]+=a[j];
if(k==2)a[i]-=a[j];
if(k==3)a[i]*=a[j];
if(k==4){
a[i]/=a[j];
if(chk(a[i]))w=1;
}
a[j] = 9e9;
sort(a+1,a+n+2-cur);
a[n+1-cur] = 0;
dfs1(cur+1, w);
memcpy(a, A, sizeof(a));
}
}
}
}
}
void dfs(int cur, int k){//枚举所有排列
if(cur>n){
ok = 0;
dfs1(1,0);
if(ok==1){
ans++;
for(int i=1; i <= 4; i++)as[ans][i]=a[i];
}
}else{
for(int i = k; i <= 13; i++){
a[cur] = i;
dfs(cur+1, i);
}
}
}
int main(){
cin>>n>>m;
if(n<3){cout<<"0\n"; return 0;}
dfs(1,1);
printf("%d\n",ans);
for(int i = 1; i <= ans; i++){
for(int j = 1; j <= n; j++){
printf("%d",as[i][j]);
if(j!=n)putchar(' ');
}
cout<<"\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
J Counting Triangles
题意:
- 按照给出的代码生成一张n个点的完全图,边分为0或1两种颜色,求图中有多少个满足非等边等腰且存在边颜色相同的三角形。
思路:
- 注意到⼀个神奇的性质:每个三角形要么同色,要么有两边同色另⼀边异色。前者没有异色角,而对于后者,三角形有恰有两个异色角。
- 因此异⾊⻆数/2 即为不符合条件的三⻆个数。⽤总数减去即可。复杂度 O(n^2)。
#include<bits/stdc++.h>
using namespace std;
//数据生成
namespace GenHelper{
unsigned z1,z2,z3,z4,bb,u;
unsigned get()
{
bb=((z1<<6)^z1)>>13;
z1=((z1&4294967294U)<<18)^bb;
bb=((z2<<2)^z2)>>27;
z2=((z2&4294967288U)<<2)^bb;
bb=((z3<<13)^z3)>>21;
z3=((z3&4294967280U)<<7)^bb;
bb=((z4<<3)^z4)>>12;
z4=((z4&4294967168U)<<13)^bb;
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];
//题目
typedef long long LL;
LL d[8005];
int main() {
//int n, seed;
LL n; int 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++){
d[i] += edge[i][j];
d[j] += edge[i][j];
}
}
LL ans = 0;
for(int i = 0; i < n; i++)
ans += d[i]*(n-d[i]-1);
cout<<n*(n-1)*(n-2)/6-ans/2<<"\n";
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
文章来源: gwj1314.blog.csdn.net,作者:小哈里,版权归原作者所有,如需转载,请联系作者。
原文链接:gwj1314.blog.csdn.net/article/details/119116371
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)