牛客编程巅峰赛S2第9场 - 钻石&王者 A题 贪心
牛牛与三角形
https://ac.nowcoder.com/acm/contest/9977/A
A题：
排好序后，最大值肯定是连续的3个数，这个没得说。
最小值的话，一定有两条边是连续的，二分第三条边即可。而且是最长的两条边一定是连续的。
//数据：5,[1,5,6,12,12] 答案是5
//5, [2, 40, 70, 100, 101] 答案是68
#define all(x) (x).begin(), (x).end()
typedef long long LL;
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回在所有合法的三角形的组成中，最大的三角形的周长减去最小的三角形的周长的值
* @param n int整型 代表题目中的n
* @param a int整型vector 代表n个数的大小
* @return int整型
*/
int solve(int n, vector<int>& a) {
// write code here
sort(all(a));
LL Mx = 0, Mn = 1e18;
for(int i = 2; i < n; ++i) {
if(a[i - 1] + a[i - 2] > a[i]) {
Mx = max(Mx, (LL)a[i] + a[i - 1] + a[i - 2]);
}
}
for(int i = 1; i + 1 < n; ++i) {
int p = upper_bound(a.begin(), a.begin() + i, a[i + 1] - a[i]) - a.begin();
if(p < i) {
Mn = min(Mn, (LL)a[p] + a[i] + a[i + 1]);
}
}
return (int)(Mx - Mn);
}
}; B题
打表发现，只有当n + 1是2的幂次时，答案才是奇数，也就是true。
有一点卡常，不要直接把string当参数传自己写的函数离去，容易因为动态开辟内存而tle。
#define fi first
#define se second
#define mk make_pair
#define o2(x) (x) * (x)
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a), (b), sizeof((a)))
#define GKD std::ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, s, t) for(int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(int i = (s), LIM=(t); i >= LIM; --i)
#define my_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
typedef long long LL;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;// 998244353
const int MXN = 1e5 + 5;
int ksm(int a, int64 b, int kmod = mod) {int res = 1;for(;b > 0;b >>= 1, a = (int64)a * a % kmod) if(b &1) res = (int64)res * a % kmod;return res;}
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n string字符串 三角形的长和高
* @return bool布尔型
*/
string mul(string n) {
reverse(n.begin(), n.end());
int len = n.length();
for(int i = 0; i < len; ++i) n[i] = (n[i] - '0') * 2 + '0';
for(int i = 0; i < len; ++i) {
if(n[i] > '9') {
if(i == len - 1) ++ len, n += '0';
n[i + 1] += (n[i] - '0') / 10;
n[i] = (n[i] - '0') % 10 + '0';
}
}
reverse(n.begin(), n.end());
return n;
}
void chu(string &n, int &len) {
for(int i = len - 1; i >= 0; --i) {
int x = n[i] - '0';
if(x % 2 == 0) n[i] = x / 2 + '0';
else {
n[i] = x / 2 + '0';
n[i - 1] += 10;
}
}
while(n[len - 1] == '0') -- len;
}
string add1(string n) {
reverse(n.begin(), n.end());
int len = n.length();
n[0] ++;
for(int i = 0; i < len; ++i) {
if(n[i] > '9') {
if(i == len - 1) ++ len, n += '0';
n[i + 1] += (n[i] - '0') / 10;
n[i] = (n[i] - '0') % 10 + '0';
}
}
reverse(n.begin(), n.end());
return n;
}
bool judge(string n) {
// write code here
bool flag = 0;
n = add1(n);
reverse(all(n));
int len = n.length();
while(1) {
if(len == 1 && n[0] == '1') {
flag = 1;
break;
}
if((n[0] - '0') % 2 == 1) break;
chu(n, len);
}
// string x = "2";
// for(int i = 1; i <= 4000; ++i) {
// if(x == n) {
// flag = 1;
// break;
// }
// x = mul(x);
// }
return flag;
}
}; C题
n只有5000，找出环，然后枚举删掉哪一条边即可。
#define fi first
#define se second
#define mk make_pair
#define o2(x) (x) * (x)
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a), (b), sizeof((a)))
#define GKD std::ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, s, t) for(int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(int i = (s), LIM=(t); i >= LIM; --i)
#define my_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
typedef long long LL;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;// 998244353
const int MXN = 5e3 + 5;
int ksm(int a, int64 b, int kmod = mod) {int res = 1;for(;b > 0;b >>= 1, a = (int64)a * a % kmod) if(b &1) res = (int64)res * a % kmod;return res;}
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型
* @param u int整型vector
* @param v int整型vector
* @return int整型
*/
map<pair<int,int>, int> vis;
vector<int> vs, mp[MXN];
int fa[MXN], dis[MXN], ip[MXN];
void dfs(int u, int ba) {
ip[u] = 1;
fa[u] = ba;
for(int v: mp[u]) {
if(v == ba) continue;
if(ip[v]) {
vs.eb(v);
int x = u;
while(x != v) {
vs.eb(x);
x = fa[x];
}
return ;
}
dfs(v, u);
if(vs.size()) return;
}
}
void dfs2(int u, int ba) {
dis[u] = dis[ba] + 1;
for(int v: mp[u]) {
if(v == ba) continue;
if(vis[mk(u, v)]) continue;
dfs2(v, u);
}
}
int solve(int n) {
dfs2(1, 0);
int pa = 1;
for(int i = 2; i <= n; ++i) if(dis[i] > dis[pa]) pa = i;
dfs2(pa, 0);
for(int i = 2; i <= n; ++i) if(dis[i] > dis[pa]) pa = i;
return dis[pa];
}
int MaxDiameter(int n, vector<int>& u, vector<int>& v) {
// write code here
int Ans = 0;
rep(i, 0, n + 1) ip[i] = 0, mp[i].clear();
rep(i, 0, n) {
mp[u[i]].eb(v[i]);
mp[v[i]].eb(u[i]);
}
int flag = 0;
rep(i, 1, n + 1) {
int x = mp[i].size();
my_unique(mp[i]);
if(mp[i].size() != x) flag = 1;
}
if(flag) return solve(n) - 1;
dfs(1, 0);
int len = vs.size();
for(int i = 1; i < len; ++i) {
vis[mk(vs[i-1], vs[i])] = 1;
vis[mk(vs[i], vs[i-1])] = 1;
Ans = max(Ans, solve(n));
vis.clear();
}
return Ans - 1;
}
}; 
查看9道真题和解析
