[51NOD]BSG白山极客挑战赛

2023-11-05 13:30

本文主要是介绍[51NOD]BSG白山极客挑战赛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

比赛链接:http://www.51nod.com/contest/problemList.html#!contestId=21

 

 1 /*
 2 ━━━━━┒ギリギリ♂ eye!
 3 ┓┏┓┏┓┃キリキリ♂ mind!
 4 ┛┗┛┗┛┃\○/
 5 ┓┏┓┏┓┃ /
 6 ┛┗┛┗┛┃ノ)
 7 ┓┏┓┏┓┃
 8 ┛┗┛┗┛┃
 9 ┓┏┓┏┓┃
10 ┛┗┛┗┛┃
11 ┓┏┓┏┓┃
12 ┛┗┛┗┛┃
13 ┓┏┓┏┓┃
14 ┃┃┃┃┃┃
15 ┻┻┻┻┻┻
16 */
17 #include <algorithm>
18 #include <iostream>
19 #include <iomanip>
20 #include <cstring>
21 #include <climits>
22 #include <complex>
23 #include <fstream>
24 #include <cassert>
25 #include <cstdio>
26 #include <bitset>
27 #include <vector>
28 #include <deque>
29 #include <queue>
30 #include <stack>
31 #include <ctime>
32 #include <set>
33 #include <map>
34 #include <cmath>
35 
36 using namespace std;
37 
38 #define fr first
39 #define sc second
40 #define cl clear
41 #define BUG puts("here!!!")
42 #define W(a) while(a--)
43 #define pb(a) push_back(a)
44 #define Rint(a) scanf("%d", &a)
45 #define Rll(a) scanf("%lld", &a)
46 #define Rs(a) scanf("%s", a)
47 #define Cin(a) cin >> a
48 #define FRead() freopen("in", "r", stdin)
49 #define FWrite() freopen("out", "w", stdout)
50 #define Rep(i, len) for(int i = 0; i < (len); i++)
51 #define For(i, a, len) for(int i = (a); i < (len); i++)
52 #define Cls(a) memset((a), 0, sizeof(a))
53 #define Clr(a, x) memset((a), (x), sizeof(a))
54 #define Full(a) memset((a), 0x7f7f, sizeof(a))
55 #define lrt rt << 1
56 #define rrt rt << 1 | 1
57 #define pi 3.14159265359
58 #define RT return
59 typedef long long LL;
60 typedef long double LD;
61 typedef unsigned long long ULL;
62 typedef pair<int, int> pii;
63 typedef pair<string, int> psi;
64 typedef map<string, int> msi;
65 typedef vector<LL> vl;
66 typedef vector<vl> vvl;
67 typedef vector<bool> vb;
68 
69 LL p[11];
70 int a,b,d,n;
71 
72 int main() {
73     // FRead();
74     int T;
75     Rint(T);
76     W(T) {
77         Cls(p);
78         Rint(a); Rint(b); Rint(d); Rint(n);
79         if(n==1) {
80             if(a*b >= 10) p[(a*b)/10]++;
81             p[(a*b)%10]++;
82             cout << p[d] << endl;
83         }
84         else {
85             int k = a*b;
86             int t = k / 10;
87             int x = k % 10;
88             int y = (x + t) / 10;
89             int g = (x +t) % 10;
90             int j = (x + y + t) % 10;
91             p[j] += n-2;
92             p[g] += 1;
93             p[x] += 1;
94             if(k >= 10) p[y+t] += 1;
95             cout << p[d] << endl;
96         }
97     }
98     RT 0;
99 }
A
  1 /*
  2 ━━━━━┒ギリギリ♂ eye!
  3 ┓┏┓┏┓┃キリキリ♂ mind!
  4 ┛┗┛┗┛┃\○/
  5 ┓┏┓┏┓┃ /
  6 ┛┗┛┗┛┃ノ)
  7 ┓┏┓┏┓┃
  8 ┛┗┛┗┛┃
  9 ┓┏┓┏┓┃
 10 ┛┗┛┗┛┃
 11 ┓┏┓┏┓┃
 12 ┛┗┛┗┛┃
 13 ┓┏┓┏┓┃
 14 ┃┃┃┃┃┃
 15 ┻┻┻┻┻┻
 16 */
 17 #include <algorithm>
 18 #include <iostream>
 19 #include <iomanip>
 20 #include <cstring>
 21 #include <climits>
 22 #include <complex>
 23 #include <fstream>
 24 #include <cassert>
 25 #include <cstdio>
 26 #include <bitset>
 27 #include <vector>
 28 #include <deque>
 29 #include <queue>
 30 #include <stack>
 31 #include <ctime>
 32 #include <set>
 33 #include <map>
 34 #include <cmath>
 35 
 36 using namespace std;
 37 
 38 #define fr first
 39 #define sc second
 40 #define cl clear
 41 #define BUG puts("here!!!")
 42 #define W(a) while(a--)
 43 #define pb(a) push_back(a)
 44 #define Rint(a) scanf("%d", &a)
 45 #define Rll(a) scanf("%lld", &a)
 46 #define Rs(a) scanf("%s", a)
 47 #define Cin(a) cin >> a
 48 #define FRead() freopen("in", "r", stdin)
 49 #define FWrite() freopen("out", "w", stdout)
 50 #define Rep(i, len) for(int i = 0; i < (len); i++)
 51 #define For(i, a, len) for(int i = (a); i < (len); i++)
 52 #define Cls(a) memset((a), 0, sizeof(a))
 53 #define Clr(a, x) memset((a), (x), sizeof(a))
 54 #define Full(a) memset((a), 0x7f7f, sizeof(a))
 55 #define lrt rt << 1
 56 #define rrt rt << 1 | 1
 57 #define pi 3.14159265359
 58 #define RT return
 59 typedef long long LL;
 60 typedef long double LD;
 61 typedef unsigned long long ULL;
 62 typedef pair<int, int> pii;
 63 typedef pair<string, int> psi;
 64 typedef map<string, int> msi;
 65 typedef vector<LL> vl;
 66 typedef vector<vl> vvl;
 67 typedef vector<bool> vb;
 68 
 69 
 70 const int maxn = 3333;
 71 const int mod = 1000000007;
 72 LL dp[maxn][maxn];
 73 LL ans;
 74 int n;
 75 
 76 int main() {
 77     // FRead();
 78     while(~Rint(n)) {
 79         Cls(dp);
 80         dp[0][0] = dp[1][1] = 1; dp[2][2] = 2;
 81         For(i, 3, n+1) {
 82             Rep(j, i) {
 83                 For(k, 1, 17) {
 84                     dp[i][k] += (dp[j][k-1] * dp[i-j-1][k-1]) % mod;
 85                     if(dp[i][k] >= mod) dp[i][k] %= mod;
 86                     if(k >= 2) {
 87                         dp[i][k] += (dp[j][k-1] * dp[i-j-1][k-2]) % mod;
 88                         if(dp[i][k] >= mod) dp[i][k] %= mod;
 89                     }
 90                     dp[i][k] += (dp[j][k-2] * dp[i-j-1][k-1]) % mod;
 91                     if(dp[i][k] >= mod) dp[i][k] %= mod;
 92                 }
 93             }
 94         }
 95         ans = 0;
 96         Rep(i, 17) {
 97             ans += dp[n][i];
 98             ans %= mod;
 99         }
100         cout << ans << endl;
101     }
102     RT 0;
103 }
B
 1 /*
 2 ━━━━━┒ギリギリ♂ eye!
 3 ┓┏┓┏┓┃キリキリ♂ mind!
 4 ┛┗┛┗┛┃\○/
 5 ┓┏┓┏┓┃ /
 6 ┛┗┛┗┛┃ノ)
 7 ┓┏┓┏┓┃
 8 ┛┗┛┗┛┃
 9 ┓┏┓┏┓┃
10 ┛┗┛┗┛┃
11 ┓┏┓┏┓┃
12 ┛┗┛┗┛┃
13 ┓┏┓┏┓┃
14 ┃┃┃┃┃┃
15 ┻┻┻┻┻┻
16 */
17 #include <algorithm>
18 #include <iostream>
19 #include <iomanip>
20 #include <cstring>
21 #include <climits>
22 #include <complex>
23 #include <fstream>
24 #include <cassert>
25 #include <cstdio>
26 #include <bitset>
27 #include <vector>
28 #include <deque>
29 #include <queue>
30 #include <stack>
31 #include <ctime>
32 #include <set>
33 #include <map>
34 #include <cmath>
35 
36 using namespace std;
37 
38 #define fr first
39 #define sc second
40 #define cl clear
41 #define BUG puts("here!!!")
42 #define W(a) while(a--)
43 #define pb(a) push_back(a)
44 #define Rint(a) scanf("%d", &a)
45 #define Rll(a) scanf("%lld", &a)
46 #define Rs(a) scanf("%s", a)
47 #define Cin(a) cin >> a
48 #define FRead() freopen("in", "r", stdin)
49 #define FWrite() freopen("out", "w", stdout)
50 #define Rep(i, len) for(int i = 0; i < (len); i++)
51 #define For(i, a, len) for(int i = (a); i < (len); i++)
52 #define Cls(a) memset((a), 0, sizeof(a))
53 #define Clr(a, x) memset((a), (x), sizeof(a))
54 #define Full(a) memset((a), 0x7f7f, sizeof(a))
55 #define lrt rt << 1
56 #define rrt rt << 1 | 1
57 #define pi 3.14159265359
58 #define RT return
59 typedef long long LL;
60 typedef long double LD;
61 typedef unsigned long long ULL;
62 typedef pair<int, int> pii;
63 typedef pair<string, int> psi;
64 typedef map<string, int> msi;
65 typedef vector<LL> vl;
66 typedef vector<vl> vvl;
67 typedef vector<bool> vb;
68 
69 
70 // const int maxn = ;
71 int n;
72 
73 int main() {
74     // FRead();
75     double r, R, s, v;
76     cin >> s;
77     
78     r = sqrt(s / pi) / 2;
79     R = s / (pi * r) - r;
80     v = pi * r * r * sqrt(R * R - r * r) / 3;
81     printf("%.6lf\n", v);;
82     
83     RT 0;
84 
85 }
C
  1 /*
  2 ━━━━━┒ギリギリ♂ eye!
  3 ┓┏┓┏┓┃キリキリ♂ mind!
  4 ┛┗┛┗┛┃\○/
  5 ┓┏┓┏┓┃ /
  6 ┛┗┛┗┛┃ノ)
  7 ┓┏┓┏┓┃
  8 ┛┗┛┗┛┃
  9 ┓┏┓┏┓┃
 10 ┛┗┛┗┛┃
 11 ┓┏┓┏┓┃
 12 ┛┗┛┗┛┃
 13 ┓┏┓┏┓┃
 14 ┃┃┃┃┃┃
 15 ┻┻┻┻┻┻
 16 */
 17 #include <algorithm>
 18 #include <iostream>
 19 #include <iomanip>
 20 #include <cstring>
 21 #include <climits>
 22 #include <complex>
 23 #include <fstream>
 24 #include <cassert>
 25 #include <cstdio>
 26 #include <bitset>
 27 #include <vector>
 28 #include <deque>
 29 #include <queue>
 30 #include <stack>
 31 #include <ctime>
 32 #include <set>
 33 #include <map>
 34 #include <cmath>
 35 using namespace std;
 36 #define fr first
 37 #define sc second
 38 #define cl clear
 39 #define BUG puts("here!!!")
 40 #define W(a) while(a--)
 41 #define pb(a) push_back(a)
 42 #define Rint(a) scanf("%d", &a)
 43 #define Rll(a) scanf("%lld", &a)
 44 #define Rs(a) scanf("%s", a)
 45 #define Cin(a) cin >> a
 46 #define FRead() freopen("in", "r", stdin)
 47 #define FWrite() freopen("out", "w", stdout)
 48 #define Rep(i, len) for(int i = 0; i < (len); i++)
 49 #define For(i, a, len) for(int i = (a); i < (len); i++)
 50 #define Cls(a) memset((a), 0, sizeof(a))
 51 #define Clr(a, x) memset((a), (x), sizeof(a))
 52 #define Full(a) memset((a), 0x7f7f, sizeof(a))
 53 #define lp p << 1
 54 #define rp p << 1 | 1
 55 #define pi 3.14159265359
 56 #define RT return
 57 #define lowbit(x) x & (-x)
 58 #define onenum(x) __builtin_popcount(x)
 59 typedef long long LL;
 60 typedef long double LD;
 61 typedef unsigned long long ULL;
 62 typedef pair<int, int> pii;
 63 typedef pair<string, int> psi;
 64 typedef map<string, int> msi;
 65 typedef vector<int> vi;
 66 typedef vector<LL> vl;
 67 typedef vector<vl> vvl;
 68 typedef vector<bool> vb;
 69 
 70 const int maxn = 300000;
 71 int n;
 72 LL k;
 73 int bit[maxn<<1][2];
 74 int t[maxn], dp[maxn];
 75 
 76 void add(int i, int x, int j) {
 77     while(i <= maxn) {
 78         bit[i][j] += x;
 79         i += lowbit(i);
 80     }
 81 }
 82 
 83 int sum(int i, int j) {
 84     int s = 0;
 85     while(i) {
 86         s += bit[i][j];
 87         i -= lowbit(i);
 88     }
 89     return s;
 90 }
 91 
 92 bool ok(int x) {
 93     Cls(dp); Cls(bit);
 94     Rep(i, n+1) {
 95         if(t[i] >= x) dp[i] = dp[i-1] + 1;
 96         else dp[i] = dp[i-1];
 97     }
 98     Rep(i, n+1) dp[i] = 2 * dp[i] - i + 100000;
 99     LL ret = 0;
100     Rep(i, n+1) {
101         ret += sum(dp[i]-1, !(i&1));
102         add(dp[i], 1, i&1);
103     }
104     if(ret >= k) return 1;
105     return 0;
106 }
107 
108 int main() {
109     // FRead();
110     while(~Rint(n) && ~Rll(k)) {
111         int l = 0, r = 0;
112         For(i, 1, n+1) {
113             Rint(t[i]);
114             r = max(r, t[i]);
115         }
116         while(l <= r) {
117             int m = (l + r) >> 1;
118             if(ok(m)) l = m + 1;
119             else r = m - 1;
120         }
121         printf("%d\n", r);
122     }
123     RT 0;
124 }
E

 

E题:

二分中位数x,dp(i)维护[1,i]区间内大于等于x的数量。注意到长为奇数的区间[l,r],l和r奇偶一定不同,这一点非常重要。

如果区间[l,r]内的中位数大于等于x的话,那么(dp(r)-dp(l))*2>r-l+1,即2*dp[r]-r>2*dp(l)-l+1。

更新dp,使dp(i)-2*dp(i)-i,统计有多少个dp(j)<dp(i) j<i 且i,j奇偶不同。

有一个问题,就是2*dp[i]-i<0,解决方法就是加一个数,并且不至于让dp[i]计算后溢出的数。

转载于:https://www.cnblogs.com/kirai/p/5527130.html

这篇关于[51NOD]BSG白山极客挑战赛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/350185

相关文章

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码

【51nod】算法马拉松4 F 移数字 【快速求N!%P】【FFT】

传送门:【51nod】算法马拉松4 F 移数字 涉及知识点:多项式求逆,多项式除法,多点插值,阶乘取模。 对于N!%P,复杂度为 O(N−−√log2N−−√) O(\sqrt N \log^2\sqrt N)。 但常数巨大,和暴力算实际复杂度只相差常数= = 这个是可以扩展到组合数取模的~ my  code: my~~code: #include <stdio.h>#includ

2024年第十届数维杯国际大学生数学建模挑战赛

竞赛介绍 为了培养学生的创新意识及运用数学方法和计算机技术解决实际问题的能力,内蒙古创新教育学会、内蒙古基础教育研究院决定主办2024年第十届数维杯国际大学生数学建模挑战赛(国际赛)。 数维杯大学生数学建模挑战赛每年分为两场,每年上半年为数维杯国赛(5月,俗称小国赛),下半年为数维杯国际赛(11月),2023年数维杯国际大学生数学建模挑战赛共有近1.5万名学生参赛,参赛队伍来自国内外1177所

高校计算机能力挑战赛C++

2020 1.Excel表列名称由字母A~Z组成,列字母的规律如下: A、B、C.....Z、AA、AB......AZ、BA、BB.......ZZZZY、ZZZZZ....... 输入:输入包含两个列名称字符串,长度均小于等于5。输出: 输出:两个列名称之间共有多少列 样例输入: AA  AZ 样例输出: 24 2."九键拼音中数字与英文字母成对应关系:2--abc, 3-def,

2020计算机挑战赛Java组真题

单选题 1.下列叙述哪些是错误的(). A.final 类不可以有子类 B.构造方法是类的一种特殊方法,其方法名必须与类名相同 C.抽象类可以用new运算符创建对象 D.内存回收程序不允许程序员直接释放内存2.下列叙述哪些是错误的(). A.abstract类不可以用new和构造函数定义对象 B.构造方法的返回值类型只能是void型 C.内存回收程序负责释放无用内存 D.Java类只能是单继承的

极客天成分布式全闪存储在大模型训练中的应用

01 国内大语言模型训练使用的存储系统应用现状 近年来,中国在人工智能领域,特别是大语言模型(LLM)的研发和应用方面取得了显著进展。随着百度文心一言、阿里通义千问、讯飞星火等国产大模型的推出,中国AI产业进入了快速发展期。这一趋势带动了对高性能存储系统的巨大需求,尤其是在模型训练阶段。 当前,中国大语言模型训练的存储市场呈现以下特点,随着更多企业和研究机构投入LLM研发,对大容量、高性能存

2017年华为精英挑战赛

http://blog.csdn.net/h532600610/article/details/70183608 http://blog.csdn.net/mmy1996/article/details/64443159

终于!我找到了开发的得力助手!阿里云天池云原生编程挑战赛参赛攻略

作者:ysevenk_7 参赛准备 我是机缘巧合在 6 月底了解到了天池云原生编程挑战赛,于是乎搜了一下,之前本人对于比赛并没有太多经验,看了大赛介绍之后莫名兴奋,果断拉了队友报名,完成认证、起队名、下载插件注册等准备任务,然后根据官方给出的赛题进行选择,由于我对开源的经验非常少,束手束脚,对于选题只是盲目的看了所使用的技术栈是否匹配,并没有考虑其他因素,于是选择了几天的项目后,看到项目诉求中

第七届MathorCup高校数学建模挑战赛-A题:基于改进的神经网络和混沌时间序列预测控制高炉炼铁过程(续)

目录 6.4 混沌时间序列预测模型  6.4.1 一步预测模型 6.4.4 二步预测模型 6.4.5 二步预测的参数 6.4.6 二步预测的结果 七.问题二模型的建立与求解 7.1 模型的预测成功率 7.1.1 训练集与验证集 7.1.2 数值预测成功率 7.1.3 炉温升降方向预测成功率 7.2 动态预测控制的可行性 7.2.1 神经网络训练函数的选取 7.2.2 神经

第七届MathorCup高校数学建模挑战赛-A题:基于改进的神经网络和混沌时间序列预测控制高炉炼铁过程

目录 摘要 一.问题重述 二.模型假设 三.符号说明 四.问题分析 五.数据预处理 5.1 异常值剔除 5.2 归一化处理 5.3 预处理后的数据 六.问题一模型的建立与求解 6.1 BP 神经网络预测模型 6.1.1 输入层和输出层 6.1.2 训练集和验证集 6.1.3 三层 BP 神经网络结构 6.1.4 BP 神经网络的参数 6.1.6 相关性分析 6.2 小波神经网络预测模型 6.2.