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;
}