3.29携程笔试
记录一下，AK了，消消最近的霉运。
码风属于依托答辩，勿吐槽。
T1
// #define STRESS
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <cstring>
#include <sstream>
#include <numeric>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef set<int> si;
typedef vector<int> vi;
typedef unsigned int uint;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef unsigned long long ull;
#ifdef STRESS
#include <random>
#include <chrono>
mt19937 rr(chrono::system_clock::now().time_since_epoch().count());
ll r(ll L, ll R) {uniform_int_distribution<ll> dist(L, R); return dist(rr);}
#endif
#ifdef LOCAL
#include "DEBUG.cpp"
#else
#define dbg(...) { }
#endif
#define rep(i, a, n) for(int i = (a); i <= (n); ++i)
#define per(i, a, n) for(int i = (a); i >= (n); --i)
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define mst(a, b) memset((a), (b), sizeof(a));
#define all(x) (x).begin(),(x).end()
#define tem template<class T> inline
#define sz(v) ((int)(v).size())
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define space putchar(' ')
#define enter puts("")
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define mid ((l + r) >> 1)
#define ls u << 1
#define rs u << 1 | 1
#define lson u << 1, l, mid
#define rson u << 1 | 1, mid + 1, r
const pii dir[] = { {1, 0}, { -1, 0}, {0, 1}, {0, -1}};
const double pi = acos(-1.0);
const double eps = 1e-8;
const uint mod = 1e9 + 7;
inline ll qpow(ll a, ll b) {assert(b >= 0); ll r = 1; for(; b; b >>= 1) {if(b & 1) r = r * a % mod; a = a * a % mod;} return r;}
inline ll inv(const ll &x) {return qpow(x, mod - 2);}
tem bool chkmax(T &a, T b) {if(a < b) {a = b; return 1;} return 0;}
tem bool chkmin(T &a, T b) {if(a > b) {a = b; return 1;} return 0;}
tem int sgn(T x) {return x > eps ? 1 : (x < -eps ? -1 : 0);}
inline int msb(const ll &x) {return x ? 63 - __builtin_clzll(x) : -1;}
inline int lsb(const ll &x) {return x ? __builtin_ctzll(x) : 64;}
inline int popcnt(const ll &x) {return __builtin_popcountll(x);}
inline int p2(const ll &x) {return 1ll << x;}
inline int lowbit(const ll &x) {return x & -x;}
inline ll sq(const ll &x) {return x * x;}
const int N = 2e5 + 5;
int a[N];
void solve() {
a[0] = a[6] = a[9] = 1;
a[8] = 2;
int ans =0;
string s; cin >> s;
for(auto c : s) {
ans += a[c - '0'];
}
cout <<ans<<endl;
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
IOS; cout << fixed << setprecision(12);
solve();
return 0;
}
T2
// #define STRESS
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <cstring>
#include <sstream>
#include <numeric>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef set<int> si;
typedef vector<int> vi;
typedef unsigned int uint;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef unsigned long long ull;
#ifdef STRESS
#include <random>
#include <chrono>
mt19937 rr(chrono::system_clock::now().time_since_epoch().count());
ll r(ll L, ll R) {uniform_int_distribution<ll> dist(L, R); return dist(rr);}
#endif
#ifdef LOCAL
#include "DEBUG.cpp"
#else
#define dbg(...) { }
#endif
#define rep(i, a, n) for(int i = (a); i <= (n); ++i)
#define per(i, a, n) for(int i = (a); i >= (n); --i)
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define mst(a, b) memset((a), (b), sizeof(a));
#define all(x) (x).begin(),(x).end()
#define tem template<class T> inline
#define sz(v) ((int)(v).size())
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define space putchar(' ')
#define enter puts("")
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define mid ((l + r) >> 1)
#define ls u << 1
#define rs u << 1 | 1
#define lson u << 1, l, mid
#define rson u << 1 | 1, mid + 1, r
const pii dir[] = { {1, 0}, { -1, 0}, {0, 1}, {0, -1}};
const double pi = acos(-1.0);
const double eps = 1e-8;
const uint mod = 1e9 + 7;
inline ll qpow(ll a, ll b) {assert(b >= 0); ll r = 1; for(; b; b >>= 1) {if(b & 1) r = r * a % mod; a = a * a % mod;} return r;}
inline ll inv(const ll &x) {return qpow(x, mod - 2);}
tem bool chkmax(T &a, T b) {if(a < b) {a = b; return 1;} return 0;}
tem bool chkmin(T &a, T b) {if(a > b) {a = b; return 1;} return 0;}
tem int sgn(T x) {return x > eps ? 1 : (x < -eps ? -1 : 0);}
inline int msb(const ll &x) {return x ? 63 - __builtin_clzll(x) : -1;}
inline int lsb(const ll &x) {return x ? __builtin_ctzll(x) : 64;}
inline int popcnt(const ll &x) {return __builtin_popcountll(x);}
inline int p2(const ll &x) {return 1ll << x;}
inline int lowbit(const ll &x) {return x & -x;}
inline ll sq(const ll &x) {return x * x;}
const int N = 2e5 + 5;
int n, k, a[N];
void solve() {
cin >> n >> k;
--k;
int i = 1;
for(i = 1; i <= 2 * k; i += 2) {
a[i] = i + 1;
a[i + 1] = i;
}
rep(j, 1, i - 1) cout << a[j] << ' ';
per(j, n, i) cout << j << ' ';
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
IOS; cout << fixed << setprecision(12);
solve();
return 0;
}
T3
// #define STRESS
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <cstring>
#include <sstream>
#include <numeric>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef set<int> si;
typedef vector<int> vi;
typedef unsigned int uint;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef unsigned long long ull;
#ifdef STRESS
#include <random>
#include <chrono>
mt19937 rr(chrono::system_clock::now().time_since_epoch().count());
ll r(ll L, ll R) {uniform_int_distribution<ll> dist(L, R); return dist(rr);}
#endif
#ifdef LOCAL
#include "DEBUG.cpp"
#else
#define dbg(...) { }
#endif
#define rep(i, a, n) for(int i = (a); i <= (n); ++i)
#define per(i, a, n) for(int i = (a); i >= (n); --i)
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define mst(a, b) memset((a), (b), sizeof(a));
#define all(x) (x).begin(),(x).end()
#define tem template<class T> inline
#define sz(v) ((int)(v).size())
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define space putchar(' ')
#define enter puts("")
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define mid ((l + r) >> 1)
#define ls u << 1
#define rs u << 1 | 1
#define lson u << 1, l, mid
#define rson u << 1 | 1, mid + 1, r
const pii dir[] = { {1, 0}, { -1, 0}, {0, 1}, {0, -1}};
const double pi = acos(-1.0);
const double eps = 1e-8;
const uint mod = 1e9 + 7;
inline ll qpow(ll a, ll b) {assert(b >= 0); ll r = 1; for(; b; b >>= 1) {if(b & 1) r = r * a % mod; a = a * a % mod;} return r;}
inline ll inv(const ll &x) {return qpow(x, mod - 2);}
tem bool chkmax(T &a, T b) {if(a < b) {a = b; return 1;} return 0;}
tem bool chkmin(T &a, T b) {if(a > b) {a = b; return 1;} return 0;}
tem int sgn(T x) {return x > eps ? 1 : (x < -eps ? -1 : 0);}
inline int msb(const ll &x) {return x ? 63 - __builtin_clzll(x) : -1;}
inline int lsb(const ll &x) {return x ? __builtin_ctzll(x) : 64;}
inline int popcnt(const ll &x) {return __builtin_popcountll(x);}
inline int p2(const ll &x) {return 1ll << x;}
inline int lowbit(const ll &x) {return x & -x;}
inline ll sq(const ll &x) {return x * x;}
const int N = 2e5 + 5;
#define int ll
int n, a[N];
map<int, pair<int, int>> m;
int f(int x, int y) {
return a[x] * y - y - n;
}
void solve() {
cin >> n;
m[n] = {1, 1};
a[1] = 1;
rep(i, 2, 12) a[i] = a[i - 1] * i;
rep(x, 3, 12) {
m[abs(f(x, 1))] = {x, 1};
int l = 3, r = 1e9;
while(l <= r) {
m[abs(f(x, mid))] = {x, mid};
m[abs(f(x, mid + 1))] = {x, mid + 1};
if(mid - 1 >= 3) m[abs(f(x, mid - 1))] = {x, mid - 1};
if(f(x, mid) > 0) r = mid - 1;
else l = mid + 1;
}
// cout << "x = " << x << ' ' << l << ' ' << r << endl;
rep(i, max(3ll, l - 5), r + 5) m[abs(f(x, i))] = {x, i};
}
auto [x, y] = m.begin()->second;
cout << x << ' ' << y << endl;
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
IOS; cout << fixed << setprecision(12);
solve();
return 0;
}
T4
// #define STRESS
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <cstring>
#include <sstream>
#include <numeric>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef set<int> si;
typedef vector<int> vi;
typedef unsigned int uint;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef unsigned long long ull;
#ifdef STRESS
#include <random>
#include <chrono>
mt19937 rr(chrono::system_clock::now().time_since_epoch().count());
ll r(ll L, ll R) {uniform_int_distribution<ll> dist(L, R); return dist(rr);}
#endif
#ifdef LOCAL
#include "DEBUG.cpp"
#else
#define dbg(...) { }
#endif
#define rep(i, a, n) for(int i = (a); i <= (n); ++i)
#define per(i, a, n) for(int i = (a); i >= (n); --i)
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define mst(a, b) memset((a), (b), sizeof(a));
#define all(x) (x).begin(),(x).end()
#define tem template<class T> inline
#define sz(v) ((int)(v).size())
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define space putchar(' ')
#define enter puts("")
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define mid ((l + r) >> 1)
#define ls u << 1
#define rs u << 1 | 1
#define lson u << 1, l, mid
#define rson u << 1 | 1, mid + 1, r
const pii dir[] = { {1, 0}, { -1, 0}, {0, 1}, {0, -1}};
const double pi = acos(-1.0);
const double eps = 1e-8;
const uint mod = 1e9 + 7;
inline ll qpow(ll a, ll b) {assert(b >= 0); ll r = 1; for(; b; b >>= 1) {if(b & 1) r = r * a % mod; a = a * a % mod;} return r;}
inline ll inv(const ll &x) {return qpow(x, mod - 2);}
tem bool chkmax(T &a, T b) {if(a < b) {a = b; return 1;} return 0;}
tem bool chkmin(T &a, T b) {if(a > b) {a = b; return 1;} return 0;}
tem int sgn(T x) {return x > eps ? 1 : (x < -eps ? -1 : 0);}
inline int msb(const ll &x) {return x ? 63 - __builtin_clzll(x) : -1;}
inline int lsb(const ll &x) {return x ? __builtin_ctzll(x) : 64;}
inline int popcnt(const ll &x) {return __builtin_popcountll(x);}
inline int p2(const ll &x) {return 1ll << x;}
inline int lowbit(const ll &x) {return x & -x;}
inline ll sq(const ll &x) {return x * x;}
const int N = 2e5 + 5;
#define int ll
int n, f[N][2];
vector<pair<int, int>> e[N];
void dfs(int u, int fa) {
for(auto [v, w] : e[u]) {
if(v == fa) continue;
dfs(v, u);
}
for(auto [v, w] : e[u]) {
if(v == fa) continue;
f[u][0] += max(f[v][0], f[v][1]);
}
for(auto [v, w] : e[u]) {
if(v == fa) continue;
chkmax(f[u][1], f[u][0] - max(f[v][0], f[v][1]) + w + f[v][0]);
}
}
void solve() {
cin >> n;
rep(i, 1, n - 1) {
int u, v, w; cin >> u >> v >> w;
e[u].pb({v, w});
e[v].pb({u, w});
}
dfs(1, 0);
cout << max(f[1][0], f[1][1]) << endl;
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
IOS; cout << fixed << setprecision(12);
solve();
return 0;
}
#携程#
投递携程等公司10个岗位 >
