drawer - 个人主页动态 - 牛客网

发布(13) 评论刷题收藏

12-04 17:55

山西大学算法工程师

题解 | #【模板】多重背包#

很坑，标记处的内个j非得从0开始，从一开始就过不去； void solve() { ll n, m; cin >> n >> m; vector<ll> dp(m + 1); for (ll i = 1; i <= n; i++) { ll w, v; cin >> w >> v; ll s; cin >> s; if (w == 0) { for (ll j = 1; j <= m; j++) {////这儿 dp[j] += s * v; } continue; } for (ll a = 0; a &lt...

0 点赞评论收藏

分享

11-29 15:17

山西大学算法工程师

题解 | #走一个大整数迷宫#

将set换成unordered_set就过了； 红黑树并没那么高效； 解题过程 还是传统的bfs，只不过每一步多存了个value；然后将visited换为比较value； void solve() { int n, m, p; cin >> n >> m >> p; vector<vector<int>> grid(n + 1, vector<int>(m + 1)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { int x; ci...

0 点赞评论收藏

分享

11-27 21:51

山西大学算法工程师

题解 | #火车进站#

非常强； void dfs(int index) { if (index == n) { vector<int> vec; for (int i : dend) { vec.push_back(i); } for (int i = de.size() - 1; i >= 0; i--) { vec.push_back(de[i]); } vecs.push_back(vec); return; } if (de.empty()) { de.push_back(vec[index]); dfs(index + 1); } else { int si = de.size(); f...

0 点赞评论收藏

分享

11-27 19:28

山西大学算法工程师

题解 | #kotori和素因子#

遍历一遍所有非重复的质因子即可； prime[i] == 0 && nn % i == 0&&find(de.begin(),de.end(),i)==de.end() void dfs(int index) { if (index == n) { if (de.size() != n)return; int sum = 0; for (int i : de) { sum += i; } ans = min(ans, sum); return; } int nn = vec[index]; for (int i = 2; i <= nn; i++) { i...

0 点赞评论收藏

分享

11-27 17:54

已编辑

山西大学算法工程师

题解 | #实现字通配符*#

经测试字符串s的长度在1000以内； 遇到*时分两步， 第一步直接迭代到末尾； 第二步依次返回；即为*分别取 最大~0 时的情况 string p, s; set<int> se; void dfs(int a, int b) { if (a == p.size()) { se.insert(b - 1); } else if (b == s.size()){ if(a==p.size()-1&&p[a]=='*') {se.insert(b-1);} } else if (p[a] == s[b]) { dfs(a + 1, b + 1); } else if (...

0 点赞评论收藏

分享

11-27 12:19

山西大学算法工程师

题解 | #数组分组#

数据范围没那么大，可以直接二叉递归求和； void dfs(int l, vector<int> vec) { if (l == vec.size()) { if (sum == subtract)flag = 1; return; } sum += vec[l]; dfs(l + 1, vec); sum -= vec[l]; sum -= vec[l]; dfs(l + 1, vec); sum += vec[l]; }

0 点赞评论收藏

分享

11-24 11:10

山西大学算法工程师

题解 | #能量辐射#

考察单调递减栈 当tower.high小于等于栈顶元素时直接入栈； 当tower.high大于栈顶元素时出栈并更新左右value值； 特别的：当出栈元素等于栈内下一个元素时，将出栈元素value传递给这个等高元素，以便同时传给栈内更高的元素； 结束时：加一个至高元素来更新栈内元素； struct tower { int high, value, position; }; void solve() { int n; cin >> n; vector<tower> towers; for(int i=0;i<n;i++){ int a, b; cin >>...

0 点赞评论收藏

分享

11-24 11:22

已编辑

山西大学算法工程师

题解 | #墙壁划线#

mathematics 在构建ab*ab二维向量 将原始图形放缩至长宽相等 列重合点横坐标为(0*b,1*b,2*b,...,ab) 横重合点纵坐标为(0*a,1*a,2*a,...,ba) 由于斜线正直，轴线上的点到斜线上的射影即为所求 1：（一条斜线）取列数； 2：（一条斜线）取行数空过重合点； 3：加倍并判断中心点； void solve() { ll a, b; cin >> a >> b; ll ans = b + 1;//1 for (ll l = 1; l <= a; l++) { if (l * b % a)ans++;//2 } ans *= 2...

0 点赞评论收藏

分享

11-23 11:50

山西大学算法工程师

题解 | #最小连通代价#

最外层分四种情况，内层再加一种全奇全偶的情况； 当a，b都大于零时再分为a大和b大两种； 一共十种情况 void solve() { ll n, a, b; cin >> n >> a >> b; ll even=0,odd=0; for (ll i = 0; i < n; i++) { ll x; cin >> x; if (x & 1)odd++; else even++; } ll sum = odd + even,ans; if (a <= 0 && b <= 0) { ans = factori...

0 点赞评论收藏

分享

11-23 10:52

山西大学算法工程师

题解 | #放苹果#

以（5，6）为例： 第一个place有5，4，3，2，1，五种情况； i=5：执行（5，0，5）返回1； i=4：执行（4，1，5）返回1； i=3：执行（3，2，5）继续执行 i=2：（2，0，4）返回1； i=1:（1，1，4）返回1； 返回2； i=2：执行（2，3，5）继续执行 i=2：（2，1，4）返回1： i=1:（1，2，4）执行i=1：（1，1，3）返回1： 返回2； i=1；执行（1，4，5）继续执行i=1：（1，3，4）继续执行i=1：（1，2，3）继续i=1：（1，1，2）返回1； 返回7； 结束； int recursion(int pro,int item, int ...

0 点赞评论收藏

分享

11-22 11:39

已编辑

山西大学算法工程师

题解 | 小A弹吉他

mathematical formula:四面体数也叫三角锥体数是可以排成底为三角形的锥体（即四面体）的数。四面体数每层为三角形数，其公式是首n个三角形数之和，即n(n+1)(n+2)/6其首几项为：1, 4, 10, 20, 35, 56, 84, 120.(1) 先在vector里标记每个i对应的vec[i]；即vec[i]为排列[1,i]存在时的最小数;vec[i]=(1,2,3,...,i)(i,i-1,i-2,...,1)=i(i+1)(i+2)/6;(2) 找出n所属的i；即vec[i-1] <= n <vec[i]; i+1为排列的mex值； ll binarys(...

0 点赞评论收藏

分享

11-21 22:45

已编辑

山西大学算法工程师

题解 | 牛妹的位运算

//归纳法,原理我在学； //(1) [0,2)=4^0;[2,4)=4^1;[4,8)=4^2;...... //(2) [0,2)=4^0;[0,4)=[0,2)+[2,4);[0,8)=[0,2)+[2,4)+[4,8);...... void solve() { vector<ll> vec(100001,1); for (int i = 3; i <= 100000; i++) { vec[i] = vec[i-1]*4%MOD;//(1) } for (int i = 2; i <= 100000; i++) { vec[i] = (vec[i] + vec...

0 点赞评论收藏

分享

11-21 09:49

山西大学算法工程师

题解 | 小苯的计算式

//暴力，纯纯暴力，直接0，c遍历一遍就完了 void solve() { int n, c; cin >> n >> c; int csize = to_string(c).size(); int absize = n - 2 - csize; ll ncount = 0; for (int i = 0; i <= c; i++) { int j = c - i; int abnewsize = to_string(i).size() + to_string(j).size(); if (abnewsize == absize)ncount++; } cout ...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务