2021暑假牛客多校联赛第三场补题

（爆零了QAQ）

J Counting Triangles

题目大意：给出一个无向图，每条边为黑色或者白色，输出三条边颜色都相同的三角形的个数

解题思路：思维题，

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 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();return 0;
}

E Math 数学

输入：

101010010001000010000011451419198102019010412312312312310000001000000

 输出：

2
5
14
31
65
67
158
326
5226
22091

题目大意：

给出一个数字n，求出在1<=x<=n,1<=y<=n的范围内，有多少组解满足xy+1>x^2+y^2。

解题思路：直接对其进行预处理，求出所有数据范围之内的解，每次询问进行二分查询。

代码：23

#include
using namespace std;const long long inf=1000000000000000000ll;
int cnt,T,l,r,mid,ans;
long long A[3000010],n;int main()
{for (int k=2; k<=1000000; k++){long long a=0,b=k,c;while (1){if (b>(inf+a)/(1ll*k*k)) break;c=b,b=b*k*k-a,a=c;A[++cnt]=b;}}sort(A+1,A+1+cnt);scanf("%d",&T);while (T--){scanf("%lld",&n);l=1,r=cnt,ans=0;while (l<=r){mid=(l+r)>>1;if (A[mid]<=n) ans=mid,l=mid+1; else r=mid-1;}printf("%d\n",ans+1);}return 0;
}

F：24点 

输入：

4 24

 输出：

16
1 3 4 6 
1 4 5 6 
1 5 5 5 
1 6 6 8 
1 8 12 12 
2 2 11 11 
2 2 13 13 
2 3 5 12 
2 4 10 10 
2 5 5 10 
2 7 7 10 
3 3 7 7 
3 3 8 8 
4 4 7 7 
5 5 7 11 
5 7 7 11

题目大意：24点是一个著名的游戏。你会得到一组n张卡片，每张卡片包含一个1到13之间的整数。你可以把卡片按任意顺序排列，在任何两张卡片之间添加 + 或 - 或 * 或 /，并添加任意多的括号。你的目标是使表达式有效，其值等于 m mm。
然而，有些情况下存在有效的解决方案，但所有有效的解决方案在计算过程中都涉及分数，即非整数。例如，如果你想用 ( 1 , 5 , 5 , 5 ) (1,5,5,5)(1,5,5,5) 来得到24，唯一的解是 5 ∗ ( 1 − ( 1 / 5 ) ) 5 *(1-(1/5))5∗(1−(1/5))，其中 1 / 5 1/51/5 是一个分数。
给出牌的数量 n nn 和你想得到的结果 m mm ，找出所有可能的牌组，这些牌组有一个有效的解决方案，但任何解决方案在计算中都涉及分数。
解题思路：直接按照题意进行暴力枚举第一次或者最后一次出现的两数。

代码：

#include 
#include 
#include 
#include 
#include 
#define EPS (1e-7)
using namespace std;
int n,m;
struct ANS{int a[4];
}ans[1000000];
int num,sum;
double stk[10];
int check(double a[],int len,int is_f);
int nsh(double a[],int len,double b0, int i,int j,int is_f)
{double b[10];int cnt=0;b[cnt++] = b0;for(int k=0;kEPS)) );}int check(double a[],int len,int is_f)
{int flag=0;if(len==1){if(abs(a[0] - m) < EPS){if(is_f)return 1;else return 2;}else return 0;}for(int i=0;iEPS)flag=max(flag,nsh(a,len,a[i]/a[j],i,j,is_f));if(abs(a[i])>EPS)flag=max(flag,nsh(a,len,a[j]/a[i],i,j,is_f));}}return flag;
}void dfs(int pre,int dep)
{if(dep>n){if(check(stk+1,n,0) == 1){++sum;for(int i=1;i<=n;i++){ans[sum].a[i]=stk[i];}}return;}for(int i=pre;i<=13;i++){stk[++num]=i;dfs(i,dep+1);num--;}
}
int main()
{scanf("%d%d",&n,&m);dfs(1,1);printf("%d\n",sum);for(int i=1;i<=sum;i++){for(int j=1;j<=n;j++)printf("%d%c",ans[i].a[j],j==n?'\n':' ');}return 0;
}

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