网站素材站,做商城网站在哪里注册营业执照,服务器网站源码在哪,傻瓜式安卓app开发工具第一次打牛客直接。。。 y1s1牛客的评测系统真的慢#xff0c;搞得我不想交
B - 划分
题目链接 首先先对数组a[]逆序贪心可得val(i,j)a1a2⋯aijval(i,j)a_1a_2\dotsa_{ij}val(i,j)a1a2⋯aij 尝试证明#xff1a;分析可知我们最终会选择ijijij个数组a[]的数#xff0…第一次打牛客直接。。。 y1s1牛客的评测系统真的慢搞得我不想交
B - 划分
题目链接 首先先对数组a[]逆序贪心可得val(i,j)a1a2⋯ai×jval(i,j)a_1a_2\dotsa_{i×j}val(i,j)a1a2⋯ai×j 尝试证明分析可知我们最终会选择i×ji×ji×j个数组a[]的数贪心肯定每个数选的越大越好尝试每一组的前jjj大的数都是数组中前i×ji×ji×j大的数的子集即可将原数组分成iii个部分选出前i×ji×ji×j大。
#includeiostream
#includealgorithm
using namespace std;
const int N100010;
typedef long long ll;
ll a[N],s[N];
int n;
int x,y;
int main()
{cinn;for(int i1;in;i) cina[i];cinxy;sort(a1,a1n);reverse(a1,a1n);for(int i1;in;i) s[i]s[i-1]a[i];ll res0;for(int i1;ix;i)for(int j1;jy;j)ress[i*j];coutresendl;return 0;
}C - 旅行
题目链接 对于一个连通图尝试去掉一些边但是最终保证图连通而且留下的边尽量的大如果我们用kurskal求最大生成树刚好满足上述需求。我们在求dist(u,v)dist(u,v)dist(u,v)时只走最大生成树上的边一定能保证dist(u,v)dist(u,v)dist(u,v)最大。选择排列时对于每条边最少都要经过一次答案一定不会超过最大生成树上的边权和。尝试构造一种解使得答案等于最大生成树上的边权和依次选择最小的边的两个点然后把这条边删去意思为不能再次选择该边这样构造即可构造出最优答案。
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N500010;
struct node
{int a,b,w;bool operator (const node o)const{return wo.w;}
}e[N];
int n,m;
int p[N];
int find(int x)
{return xp[x]?x:p[x]find(p[x]);
}
int main()
{cinnm;for(int i0;im;i) cine[i].ae[i].be[i].w;for(int i1;in;i) p[i]i;sort(e,em);ll res0;for(int i0;im;i){int ae[i].a,be[i].b,we[i].w;int pafind(a),pbfind(b);if(pa!pb){p[pa]pb;resw;}}coutresendl;return 0;
}补完2题发现牛客的思维难度还是挺高的如果能够推出结论还是挺好写代码的以后要多练练这种思维算法题目。
D - 火柴排队
刚开始看还以为是个数论题数论渣渣不想看数论其实是个dp 状态表示f[i][j][0/1]f[i][j][0/1]f[i][j][0/1]表示对于前iii个人选择jjj个增加ddd 并且不选/选择第iii个人 状态计算 f[i][j][0]f[i−1][j][0](a[i−1]d≤a[i])f[i−1][j][1]f[i][j][0]f[i-1][j][0](a[i-1]d \leq a[i])f[i-1][j][1]f[i][j][0]f[i−1][j][0](a[i−1]d≤a[i])f[i−1][j][1] f[i][j][1]f[i−1][j−1][0]f[i−1][j−1][1]f[i][j][1]f[i-1][j-1][0]f[i-1][j-1][1]f[i][j][1]f[i−1][j−1][0]f[i−1][j−1][1] 很多dp概率实质都是算方案数然后借用阶乘和逆元算答案。
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N5010;
const ll mod998244353;
ll a[N],d;
ll f[2][N][2];// f[i][j][0/1] 表示对于前i个人选择j个增加d 并且不选/选择第i个人
int n;
ll fact[N],infact[N];
ll qmi(ll a,ll b,ll p)
{ll res1;while(b){if(b1) resres*a%p;aa*a%mod;b1;}return res;
}
void init(int n)
{fact[0]infact[0]1;for(int i1;in;i){fact[i]fact[i-1]*i%mod;infact[i]qmi(fact[i],mod-2,mod);}
}int main()
{cinnd;init(n);for(int i1;in;i) cina[i];sort(a1,a1n);f[0][0][0]1;for(int i1;in;i){for(int j0;ji;j){if(j) f[i1][j][1](f[i-11][j-1][0]f[i-11][j-1][1])%mod;f[i1][j][0](f[i-11][j][0]f[i-11][j][1]*(a[i-1]da[i]))%mod;}}for(int i1;in;i){ll res((f[n1][i][0]f[n1][i][1])%mod*fact[n-i]%mod*fact[i]%mod*infact[n]%modmod)%mod;coutresendl;}
}要加油哦~
