牛客编程巅峰赛S2赛季第8场AC代码

牛客编程巅峰赛S2赛季第8场AC代码
初级场A
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回将这个数n拆成两个自然数之和一共有多少种拆法（符合规则）。
* @param n int整型 代表题意中的n
* @return int整型
*/
int solve(int n) {
// write code here
return (n-1)/2;
}
};

初级场B / 高级场A
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回总体积为V若干物品的最大总重量，如果g存在选择若干物品总体积为V的情况，返回-1
* @param v int整型vector
* @param g int整型vector
* @param V int整型
* @return int整型
/
int ans,n,vv;
vector<int> V,G;
void dfs(int now,int v,int g){
if (now==n){
if (v==vv&&g>ans) ans=g;
return;
}
dfs(now+1,v,g);
if (v+V[now]<=vv) dfs(now+1,v+V[now],g+G[now]);
}
int Maximumweight(vector<int>& v, vector<int>& g, int _vv) {
// write code here
ans=-1;
vv=_vv;
n=v.size();
for(int i=0;i<n;++i){
V.push_back(v[i]);
G.push_back(g[i]);
}
dfs(0,0,0);
return ans;
}
};
初级场C / 高级场B
class Solution {
public:
/*</int></int></int>
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 给定一个字符串s，返回具有相同前缀后缀的子串的第二大长度，反之，返回-1即可。
* @param s string字符串 代表题意中的字符串s
* @return int整型
/
int f[1100000];
int solve(string s) {
// write code here
int j=0;
int n=s.length();
f[1]=0;
int ans=0;
for(int i=2;i<=n;++i){
while (j&&s[i-1]!=s[j]) j=f[j];
if (s[i-1]==s[j]) ++j;
f[i]=j;
//if (f[i]>ans) ans=f[i];
}
ans=f[n];
if (ans==0) ans=-1;
return ans;
}
};
高级场C
class Solution {
public:
/*
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型 有n个城市
* @param m int整型 有m条路径
* @param s int整型 起始城市坐标
* @param t int整型 终点城市坐标
* @param edge int整型vector<vector<>> 边的格式如下:[[u1,v1,a1,b1],[u2,v2,a2,b2],...]
* @return int整型
/
const int p=1000000007;
long double f[510],fac[1110];
long long g[510],C[1110][1110];
void relax(int u,int v,int a,int b){
if (f[u]+fac[a]-fac[b]-fac[a-b]<f[v]){
f[v]=f[u]+fac[a]-fac[b]-fac[a-b];
g[v]=g[u]C[a][b]%p;
}
}
int minDist(int n, int m, int s, int t, vector<vector<int> >& edge) {
// write code here
for(int i=1;i<=1000;++i) fac[i]=fac[i-1]+log(i);
C[0][0]=1;//!!!!!!!!!!!!
for(int i=1;i<=1000;++i){
C[i][0]=1;
for(int j=1;j<=i;++j){
C[i][j]=C[i-1][j]+C[i-1][j-1];
if (C[i][j]>=p) C[i][j]-=p;
}
}
for(int i=1;i<=n;++i) f[i]=1e50;
f[s]=0;
g[s]=1;
for(int i=1;i<=n;++i){
for(int j=0;j<edge.size();++j){
relax(edge[j][0],edge[j][1],edge[j][2],edge[j][3]);
relax(edge[j][1],edge[j][0],edge[j][2],edge[j][3]);
}
}
return g[t];
}
};</int>