鞍山网站建设优化,住宅和城乡建设部网站,室内设计毕业设计代做网站,网络服务费的资金产出有哪些文章目录A. 日期统计B. 01 串的熵C. 冶炼金属D. 飞机降落E. 接龙数列F. 岛屿个数G. 子串简写H. 整数删除I. 景区导游J. 砍树今年比去年难好多
Update 2023.4.10 反转了#xff0c;炼金二分没写错#xff0c;可以AC了
Update 2023.4.9 rnm退钱#xff0c;把简单的都放后面…
文章目录A. 日期统计B. 01 串的熵C. 冶炼金属D. 飞机降落E. 接龙数列F. 岛屿个数G. 子串简写H. 整数删除I. 景区导游J. 砍树今年比去年难好多
Update 2023.4.10 反转了炼金二分没写错可以AC了
Update 2023.4.9 rnm退钱把简单的都放后面是吧。在C语言网测了一下民间数据地址在这里。果然二分写错了0分qwq更新一个正确做法。飞机场不知道为什么也T了很对的时间复杂度啊。最后再更新一下J题把这个题就是一个最简单的树上差分题。
A. 日期统计
直接8个for然后剪枝一下只取2023开头的跑起来还是很快的自己电脑100ms机房1s左右 我算的答案是235,不一定对qwq
#include bits/stdc.h
using namespace std;
mapstring, int f;
int m[] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int res;
void check(string s) {if(f.count(s)) return;int mon (s[0] - 0) * 10 s[1] - 0;int day (s[2] - 0) * 10 s[3] - 0;if(mon 1 || mon 12) return ;if (day 1 || day m[mon] ) return ;f[s] 1;res ;
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int a[101];for (int i 1; i 100; i ) {cin a[i];}for (int y1 1; y1 100; y1 ) {for (int y2 y1 1; y2 100; y2 ) {for (int y3 y2 1; y3 100; y3 ) {for (int y4 y3 1; y4 100; y4 ) {string year ;year char(a[y1] 0);year char(a[y2] 0);year char(a[y3] 0);year char(a[y4] 0);if(year ! 2023) {continue;}for (int m1 y4 1; m1 100; m1 ) {for (int m2 m1 1; m2 100; m2 ) {for (int d1 m2 1; d1 100; d1 ) {for (int d2 d1 1; d2 100; d2 ) {string s ;s char(a[m1] 0);s char(a[m2] 0);s char(a[d1] 0);s char(a[d2] 0);check(s);}}}}}}}}cout res \n;// 235return 0;}B. 01 串的熵
枚举一下1的个数然后算一下c自带log函数的 我算的结果是11027421,不知道对不对qwq
#include bits/stdc.h
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);double ans 11625907.5798;int n 23333333, t -1;for (int i 1; i n; i ) {double x1 1.0 * i / n;double x2 1.0 * (n - i) / n;double res -1.0 * i * x1 * log2(x1) - 1.0 * (n - i) * x2 * log2(x2);if(fabs(res - ans) 1e-4) {t min(i, n - i);break;}}// 11027421cout t \n;}
C. 冶炼金属
瞎几把二分,过样例就没管了。二分没错 下面是看群友写的可以过C语言网民间数据
#include bits/stdc.h
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin n;int a 0, b 1e9;for (int i 0; i n; i ) {int x, y;cin x y;b min(b, x / y);a max(a, x / (y 1) 1);}cout a b \n;return 0;}二分这样写
#include bits/stdc.h
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin n;vectorint a(n), b(n);for (int i 0; i n; i ) {cin a[i] b[i];}int l 1, r 1e9;while (l r) {int mid (l r) 1;int t 0;for (int i 0; i n; i ) {if(a[i] / mid b[i]) t --;else if(a[i] / mid b[i]) t ;}if(t 0) r mid;else l mid 1;}cout l ;l 1, r 1e9;while (l r) {int mid (l r 1) 1;int t 0;for (int i 0; i n; i ) {if(a[i] / mid b[i]) t --;else if(a[i] / mid b[i]) t ;}if(t 0) l mid;else r mid - 1;}cout l \n;return 0;}D. 飞机降落
看到数据量就只有10,直接就是全排列去判断合不合法了。C语言网TLE了呜呜呜
#include bits/stdc.h
using namespace std;
typedef long long ll;
struct P{int t, d, l;
};
void solve() {int n;cin n;vectorP a(n);for (int i 0; i n; i ) {cin a[i].t a[i].d a[i].l;}vectorint p(n);iota(p.begin(), p.end(), 0);bool ok false;do {bool ft true;int s a[p[0]].t a[p[0]].l;for (int i 1; i n; i ) {auto [t, d, l] a[p[i]];if(t d s) ft false;else {s l;}}if(ft) ok true;} while (next_permutation(p.begin(), p.end()));if(ok) {cout YES\n;} else {cout NO\n;}
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin t;while (t --) {solve();}return 0;
}E. 接龙数列
和LISLISLIS类似的DP吧, 可以做到O(n)O(n)O(n)的,但是脑抽了想了个O(n2)O(n^2)O(n2)又瞎几把优化了一下,样例过了 f[i][j]f[i][j]f[i][j]表示选aia_iai以数字jjj结尾的最长接龙数列,然后答案就是nnn减去最长的. f[i][j]maxj≤if[j][k]f[i][j] \max_{j \le i} f[j][k]f[i][j]maxj≤if[j][k].然后我这里用树状数组优化成了 lognlognlogn,应该能过.
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int N 1e5 10;
struct BIT {int c[N];int lowbit(int x) {return x -x;}void add(int x, int v) {while (x N) {c[x] max(c[x], v);x lowbit(x);}}int sum(int x) {int res 0;while (x) {res max(res, c[x]);x - lowbit(x);}return res;}
};
BIT bit[10];
int f[N][10];
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin n;for (int i 1; i n; i ) {string s;cin s;int a s[0] - 0, b s.back() - 0;f[i][b] 1;f[i][b] max(f[i][b], bit[a].sum(i - 1) 1);bit[b].add(i, f[i][b]);}int res 0;for (int i 1; i n; i )for (int j 0; j 10; j ) {res max(res, f[i][j]);}cout n - res \n;return 0;
}F. 岛屿个数
不会 看了几分钟没思路就看后面去了. 看了一些群佬的思路:大致是,从海开始dfs,遇到了岛就去dfs岛然后标记,这么想确实很对,代码还没写
G. 子串简写
我宣布这是最简单的, 比赛前一天晚上的牛客小白月赛D和这个极其类似 如果一个位置是c2,那么看前面有多少c1就可以了.注意要判断一下距离,用前缀和搞一下就行
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int N 5e5 10;
int f[N];
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int k;cin k;string s;char c1, c2;cin s c1 c2;int n s.size();for (int i 0; i n; i ) {f[i 1] f[i] (s[i] c1);}ll res 0;for (int i k - 1; i n; i ) {int l i - k 1;if(s[i] c2) {res f[l 1];}}cout res \n;return 0;
}H. 整数删除
不会, 据说是set优先队列乱搞)
I. 景区导游
对于树上两个点(u,v)(u,v)(u,v)之间的最距离就是dist[u]dist[v]−2∗dist[lca(u,v)]dist[u] dist[v] - 2 * dist[lca(u,v)]dist[u]dist[v]−2∗dist[lca(u,v)], dist[u]dist[u]dist[u]是根节点到uuu的距离. 然后就好做了
#include bits/stdc.h
using namespace std;
typedef long long ll;
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, k;cin n k;vectorvectorpairint,int adj(n 1);for (int i 0; i n - 1; i ) {int u, v, w;cin u v w;adj[u].emplace_back(v, w);adj[v].emplace_back(u, w);}vectorint t(k);for (int i 0; i k; i ) {cin t[i];}vector f(n 1, vectorint(22));vectorll dist(n 1), dep(n 1);functionvoid(int, int) dfs [](int u, int p) {f[u][0] p;dep[u] dep[p] 1;for (int i 1; i 20; i ) {f[u][i] f[f[u][i - 1]][i - 1];}for (auto [v, w] : adj[u]) {if(v p) continue;dist[v] dist[u] w;dfs(v, u);}};functionint(int,int) lca [](int x, int y) - int{if(dep[x] dep[y]) swap(x, y);for (int i 20; i 0; i --) {if (dep[f[x][i]] dep[y]) {x f[x][i];}}if(x y) return x;for (int i 20; i 0; i --) {if(f[x][i] ! f[y][i]) {x f[x][i];y f[y][i];}}return f[x][0];};dfs(1, 0);auto go [](int u, int v) - ll {return dist[u] dist[v] - 2 * dist[lca(u, v)];};ll alls 0;for (int i 0; i 1 k; i ) {alls go(t[i], t[i 1]);}for (int i 0; i k;i ) {if(i 0) {cout alls - go(t[0], t[1]) ;} else if(i k - 1) {cout alls - go(t[k - 2], t[k - 1]) \n;} else {cout alls - go(t[i - 1], t[i]) - go(t[i], t[i 1]) go(t[i - 1], t[i 1]) ;}}return 0;
}J. 砍树
这个题其实很简单。它的题意是给出一棵树然后mmm对点让你切断一条边使得这mmm对点都不连通。 对于一颗树上的两个点u,vu, vu,v他是一定联通的并且它的路径是u−lca(u,v)−vu - lca(u,v) - vu−lca(u,v)−v, 那么我们就可以利用差分的思想让这mmm对点的路径都加上111然后去看哪个边被加了mmm次那么把这个点切断那就可以满足题意了。具体可以看代码
另外这个题又是一个lca难不成今年蓝桥杯要成lca杯了吗雾
#include bits/stdc.h
using namespace std;
typedef long long ll;
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin n m;vectorvectorpairint,int adj(n 1);for (int i 0; i n - 1; i ) {int u, v;cin u v;adj[u].emplace_back(v, i 1);adj[v].emplace_back(u, i 1);}vectorvectorint f(n 1, vectorint(21));vectorint d(n 1), dep(n 1);functionvoid(int,int) dfs1 [](int u, int p) {dep[u] dep[p] 1;f[u][0] p;for (int i 1; i 20; i ) {f[u][i] f[f[u][i - 1]][i - 1];}for (auto [v, id] : adj[u]) {if(v p) continue;dfs1(v, u);}};auto lca [](int u, int v) - int {if(dep[u] dep[v]) swap(u, v);for (int i 20; i 0; i --) {if(dep[f[u][i]] dep[v]) {u f[u][i];}}if(u v) return u;for (int i 20; i 0; i --) {if(f[u][i] ! f[v][i]) {u f[u][i];v f[v][i];}}return f[u][0];};int ans -1;functionint(int,int) dfs [](int u, int p) - int {int res d[u];for (auto [v, id] : adj[u]) {if(v p) continue;int s dfs(v, u);if(s m) {ans max(ans, id);}res s;}return res;};dfs1(1, 0);for (int i 0; i m; i ) {int u, v;cin u v;d[u] ;d[v] ;d[lca(u, v)] - 2; }dfs(1, 0);cout ans \n;return 0;
}
