牛客编程巅峰赛S2赛季第7场AC代码
初级场A 牛牛爱喝酒
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回牛牛能喝的最多的酒
* @param m int整型 酒单价
* @param n int整型 牛牛的现金
* @return int整型
*/
int countWine(int m, int n) {
// write code here
int ans=n/m;
int jp=ans,pg=ans;
while (jp>=2||pg>=4){
int te=pg/4;
ans+=te;
jp+=te;
pg=pg%4+te;
te=jp/2;
ans+=te;
jp=jp%2+te;
pg+=te;
}
return ans;
}
};
初级场B&高级场A 牛牛的独特子序列
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param x string字符串
* @return int整型
*/
string t;
bool che(int x){
int te=0;
int i=0;
for(;i<t.length();++i){
if (t[i]=='a') ++te;
if (te==x) break;
}
if (i==t.length()) return 0;
te=0;
for(;i<t.length();++i){
if (t[i]=='b') ++te;
if (te==x) break;
}
if (i==t.length()) return 0;
te=0;
for(;i<t.length();++i){
if (t[i]=='c') ++te;
if (te==x) break;
}
if (i==t.length()) return 0;
return 1;
}
int Maximumlength(string x) {
// write code here
int n=x.length();
int l=0;
int r=n/3;
int mid;
t=x;
while (l<r){
mid=(l+r+1)>>1;
if (che(mid)) l=mid;else r=mid-1;
}
return l*3;
}
};
初级场C&高级场B 分贝壳游戏
class Solution {
public:
/**
*
* @param n int整型
* @param p int整型
* @param q int整型
* @return int整型
*/
int Gameresults(int n, int p, int q) {
// write code here
if (p<q){
return (n<=p)?1:-1;
}
if (p>q){
return 1;
}
if (p==q){
return (n%(p+1))?1:-1;
}
return 0;
}
};
高级场C 经过直径的点
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型 节点个数
* @param u int整型vector
* @param v int整型vector
* @return int整型
*/
vector<int> e[110000];
int d[110000],q[110000],he,ta,r1,r2,las[110000],dep[110000],ma;
bool b[110000],ind[110000];
void bfs(int st){
q[he=ta=1]=st;
d[st]=0;
las[st]=0;
memset(b,0,sizeof b);
b[st]=1;
while (he<=ta){
int &x=q[he];
for(int y:e[x]) if (!b[y]){
b[y]=1;
d[y]=d[x]+1;
las[y]=x;
q[++ta]=y;
}
++he;
}
}
void dfs(int x,int fa){
if (dep[x]==ma) ind[x]=1;
for(int y:e[x]) if (y!=fa&&!ind[y]){
dep[y]=dep[x]+1;
dfs(y,x);
if (ind[y]) ind[x]=1;
}
}
int PointsOnDiameter(int n, vector<int>& u, vector<int>& v) {
// write code here
for(int i=0;i<u.size();++i){
e[u[i]].push_back(v[i]);
e[v[i]].push_back(u[i]);
}
bfs(1);
r1=1;
for(int i=2;i<=n;++i) if (d[i]>d[r1]) r1=i;
bfs(r1);
r2=1;
for(int i=2;i<=n;++i) if (d[i]>d[r2]) r2=i;
int te=r2;
/*for(int i=0;i<=d[r2];++i){
ind[te]=1;
dep[te]=min(i,d[r2]-i);
te=las[te];
}
for(int i=1;i<=n;++i) if (ind[i]){
ma=dep[i];
dep[i]=0;
dfs(i,0);
}*/
int ans=0;
//for(int i=1;i<=n;++i) if (dep[i]==d[r2]) ind[i]=1;
for(int i=1;i<=n;++i) if (d[i]==d[r2]){
te=i;
while (te){
if (ind[te]) break;
ind[te]=1;
te=las[te];
}
}
for(int i=1;i<=n;++i) if (ind[i]) ++ans;
//return d[5];
return ans;
}
};
OPPO公司福利 1154人发布