诣天诣练03

编程入门 行业动态 更新时间:2024-10-24 07:35:09

<a href=https://www.elefans.com/category/jswz/34/1686622.html style=诣天诣练03"/>

诣天诣练03

A - Detective Book CodeForces - 1140A

小思维+手速题

题意:即每页都有个悬念需要到另一页去找,然后有悬念的一定要看完到那一页,问你需要多少天。

分析:即更新最大值当悬疑页数小于等等于当前页数时+1天。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+ 10;int n, ans, a[maxn], d;
int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%d", &a[i]);d = max(d, a[i]);if(d <= i) ans++;}printf("%d\n", ans);return 0;
}

B - Good String CodeForces - 1140B

水题,题意:<删除他左边的>括号,>删除他右边的<括号,问你操作几次可以把存在的括号变成相同的。

分析:两边删,因为存在<在左边无法用>删除,>在最右边无法用<删除。因而我们只需要遍历左右查找在左边的<和右边的>取最小值即可。

#include<bits/stdc++.h>
using namespace std;int t, n;
string str;int main()
{scanf("%d", &t);while(t--){scanf("%d", &n);cin >> str;int ans1 = 0, ans2 = 0;for(int i = 0; i < n; i++)if(str[i]== '<') ans1++;else ans2++;if(ans1 == n || ans2 == n || str[0] == '>'|| str[n - 1] == '<'){printf("0\n");continue;}ans1 = ans2 = 0;for(int i = 0; i < n; i++){if(str[i] == '<') ans1++;else break;}for(int i = n - 1; i >= 0; i--)if(str[i] == '>') ans2++;else break;printf("%d\n", min(ans1, ans2));}return 0;
}

C - Playlist CodeForces - 1140C

题意:给两组数ti和bi,选k个数,然后(t1 + ...+ti)*min(b1,b2,...bi)的最大值。

分析,暴力贪心加优先队列维护。我们可以将b值按从大到小排序,然后每次乘的最小b都是当前b接下来我们只需维护,优先队列中至多有k个值即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;int n, k;
struct nod
{long long t, b;
} a[maxn];
bool cmp(nod x, nod y)
{if(x.b == y.b) return x.t > y.t;return x.b > y.b;
}
priority_queue<long long, vector<long long>, greater<long long> > pre;
int main()
{scanf("%d%d", &n, &k);for(int i = 1; i <= n; i++) scanf("%lld%lld", &a[i].t, &a[i].b);sort(a + 1, a + n + 1, cmp);long long sum = 0, ans = -1;for(int i = 1; i <= n; i++){sum += a[i].t;pre.push(a[i].t);while(pre.size() > k){sum -= pre.top();pre.pop();}ans = max(ans, sum * a[i].b);}printf("%lld\n", ans);return 0;
}

D - Minimum Triangulation CodeForces - 1140D

老水老水的D题,思维含量甚至不超过B,简单递推题,给你一个多边形逆时针编号,然后每个点都有值,一个三角形的权值是三个角乘积。问最小值。

不断连嘛最小值即连1,n-2,n-1才能使他最小。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 600;int n;
long long a[maxn];
void init()
{a[3] = 1 * 2 * 3;for(int i = 4; i < maxn; i++) a[i] = a[i - 1] + 1 * i * (i - 1);
}
int main()
{init();scanf("%d", &n);printf("%lld\n", a[n]);return 0;
}

E - Palindrome-less Arrays CodeForces - 1140E

DP题,题意奇数的逆回文串为坏的,否则为好的。

分析奇数回文串一定有一个长度为3的回文串,我们只需要判定有没有即可。

 要求不存在奇回文串,说明相邻的偶数标号的数不相同(奇数同理).

我们不妨用dp [i] [j]表示到i时选择第j个数的方案数。

d * (k - 1) % mod; 

(s + (k - 2) * d % mod) % mod;

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const int mod = 998244353;
#define ll long longint n, k, tot1, tot2;
long long a[maxn], b[maxn];
long long solve(long long *a, int len)
{if(len == 1)if(a[1] == - 1) return k; // -1的话 就有k种情况else return 1;long long s = 1, d = 0, res = 1;ll ls = a[1];for(int i = 2; i <= len; i++){ll ns = d * (k - 1) % mod; ll nd = (s + (k - 2) * d % mod) % mod;if(a[i] == -1) s = ns, d = nd;else{if(ls == -1) res = res * (ns + nd * (k -1) % mod) % mod;else res = res * (a[i] == ls ? ns : nd) % mod;ls = a[i], s= 1, d = 0;}}res = res * (s + d * (k - 1) % mod) % mod;if(ls == -1) return res * k % mod;return res;}
int main()
{scanf("%d%d", &n, &k);for(int i = 1; i <= n; i++){if(i & 1) scanf("%lld", &a[++tot1]); // 偶数奇数分段else scanf("%lld", &b[++tot2]);}printf("%lld\n", solve(a, tot1) * solve(b, tot2) % mod);return 0;
}

 

更多推荐

诣天诣练03

本文发布于:2024-02-12 06:31:20,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1686621.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:诣天诣练

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!