添加回复
作者
作者其它话题
新奇的函数:
数论问题,只要考虑2和5这两个素因子出现的次数。(后导零,指末尾0的个数,例如:12000后导零是3, 106500后导零是2)
示例代码:
#include <iostream> #include <cstring> #include <string> #include <cmath> #include <set> #include <map> #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <cassert> #pragma warning( disable : 4996) using namespace std; int count(int n, int m) { int sum = 0; while (n) { sum += n / m; n /= m; } return sum; } int bin(int x) { int left = 1, right = 1000000000; //10^9 int ret = -1; while (left <= right) { int mid = (left + right) >> 1; int c = count(mid, 5); if (c == x) { ret = mid; right = mid - 1; } else if (c > x) { right = mid - 1; } else { left = mid + 1; } } return ret; } int main() { //freopen("func_10.in", "r", stdin); //freopen("func_10.out", "w", stdout); int x; while (cin >> x) { assert(x >= 1 && x <= 100000000); cout << bin(x) << endl; } }
修路:
枚举一条边,把一颗树拆成两颗,两棵树各取一条路径即可。
示例代码:
#include <cstdio> #include <cmath> #include <vector> #define maxn 309 using namespace std; vector<int>G[maxn]; int n; int X[maxn],Y[maxn]; int color[maxn]; void dfs(int u, int fa, int c){ color[u] = c; for(auto v: G[u]){ if(v == fa) continue; dfs(v, u, c); } } int dfs_max(int u, int fa){ int ans = 0; for(auto v: G[u]){ if(color[v] != color[u]) continue; if(v == fa) continue; ans = max(ans, dfs_max(v, u) + 1); } return ans; } int solve(int c){ int ans = 0; for(int i = 1; i <= n; i++){ if(color[i] == c){ ans = max(ans, dfs_max(i, -1)); } } return ans; } int main(){ while(scanf("%d", &n) != EOF){ for(int i = 1; i <= n; i++) G[i].clear(); for(int i = 0; i < n - 1; i ++){ scanf("%d%d", &X[i], &Y[i]); G[X[i]].push_back(Y[i]); G[Y[i]].push_back(X[i]); } int ans = 0; for(int i = 0; i < n - 1; i++){ int u = X[i]; int v = Y[i]; dfs(u, v, 1); dfs(v, u, 2); ans = max(solve(1) * solve(2), ans); } printf("%d\n", ans); } return 0; }
括号序列:
把左括号看成+1,右括号看成-1,一段合法的括号序列任意前缀和大于等于0,且最后求和为0。dp[i][j]表示前i和数的前缀和为j的最高价值,答案为dp[n][0]。
示例代码:
#include <bits/stdc++.h> #define maxn 2009 using namespace std; const int INF=1e9; int a[maxn],b[maxn],n; int dp[maxn][maxn]; int main(){ scanf("%d",&n); n*=2; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); for(int i=1;i<=n+1;i++) dp[0][i]=-INF; for(int i=1;i<=n;i++){ for(int j=0;j<=i;j++){ if(j){ dp[i][j]=max(dp[i-1][j-1]+a[i],dp[i-1][j+1]+b[i]); } else{ dp[i][j]=dp[i-1][j+1]+b[i]; } } } printf("%d\n",dp[n][0]); //system("pause"); return 0; }