2019 HDOJ Multi

可莉
• 阅读 607

服务器时不时爆炸,有点难受。

题目链接:http://acm.hdu.edu.cn/userloginex.php?cid=849


A:

神仙题。不可做题。

B:

dp。

C:

推式子题。

D:

边分治。

E:

可以数学推理的题。但是显然打表更快找出规律。对打出来的结果做两次差分即可。

2019 HDOJ Multi 2019 HDOJ Multi

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 #define mid (curl+curr>>1)
17 /* namespace */
18 using namespace std;
19 /* header end */
20 
21 const ll mod = 998244353;
22 
23 ll qp(ll x, ll b) {
24     ll ret = 1, base = x;
25     while (b) {
26         if (b & 1) ret = ret * base % mod;
27         base = base * base % mod;
28         b >>= 1;
29     }
30     return ret;
31 }
32 
33 int main() {
34     ll n;
35     while (~scanf("%lld", &n)) {
36         ll k = 0, tmp = 3;
37         rep1(i, 2, n) k += tmp, tmp += 2;
38         printf("%lld\n", k * qp(9, mod - 2) % mod);
39     }
40     return 0;
41 }

View Code

F:

fwt题。

G:

不均等博弈题。用surrealnumber秒杀。

H:

最小割。

I:

求出本质不同的回文串的数量分布(求每种回文串的个数),然后对每种check一下叠加答案。manacher或者字符串hash都可以。

J:

签到题。1e6+3的阶乘后面全是0已经暗示一切。

2019 HDOJ Multi 2019 HDOJ Multi

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 #define mid (curl+curr>>1)
17 /* namespace */
18 using namespace std;
19 /* header end */
20 
21 const int mod = 1e6 + 3;
22 ll p[mod + 10];
23 int n;
24 
25 int main() {
26     p[0] = p[1] = 1;
27     rep0(i, 2, mod) p[i] = 1ll * i * p[i - 1] % mod;
28     while (~scanf("%d", &n)) {
29         if (n >= mod) {
30             puts("0");
31             continue;
32         }
33         n %= mod;
34         printf("%lld\n", p[n]);
35     }
36     return 0;
37 }

View Code

K:

对于某个区间,首先考虑区间第1、2、3大的边能否构成三角形,然后考虑区间第2、3 、4大的边能否构成三角形,以此类推。

只要考虑区间前44大即可,因为区间最坏情况是斐波那契数列,然而第45项就爆了1e9的范围。时间复杂度O(44*nlogn)。

2019 HDOJ Multi 2019 HDOJ Multi

 1 /* basic header */
 2 #include <iostream>
 3 #include <cstring>
 4 /* define */
 5 #define ll long long
 6 #define dou double
 7 #define pb emplace_back
 8 #define mp make_pair
 9 #define sot(a,b) sort(a+1,a+1+b)
10 #define rep1(i,a,b) for(int i=a;i<=b;++i)
11 #define rep0(i,a,b) for(int i=a;i<b;++i)
12 #define eps 1e-8
13 #define int_inf 0x3f3f3f3f
14 #define ll_inf 0x7f7f7f7f7f7f7f7f
15 #define lson (curpos<<1)
16 #define rson (curpos<<1|1)
17 /* namespace */
18 using namespace std;
19 /* header end */
20 
21 const int maxn = 1e5 + 10;
22 int a[maxn];
23 
24 struct Node {
25     int l, r, val[50];
26 };
27 
28 Node segt[maxn << 2];
29 
30 void maintain(Node &fa, Node &ls, Node &rs) {
31     int i = 0, j = 0;
32     rep0(c, 0, 50) {
33         if (i >= 50)
34             fa.val[c] = rs.val[j++];
35         else if (j >= 50)
36             fa.val[c] = ls.val[i++];
37         else if (ls.val[i] < rs.val[j])
38             fa.val[c] = rs.val[j++];
39         else fa.val[c] = ls.val[i++];
40     }
41 }
42 
43 void build(int curpos, int curl, int curr) {
44     segt[curpos].l = curl, segt[curpos].r = curr;
45     // memset(segt[curpos].val, 0, sizeof(segt[curpos].val));
46     if (curl < curr) { // if is not leaf node
47         int mid = curl + curr >> 1;
48         build(lson, curl, mid); build(rson, mid + 1, curr);
49         maintain(segt[curpos], segt[lson], segt[rson]);
50     } else
51         segt[curpos].val[0] = a[curl]; // if is leaf node
52 }
53 
54 Node query(int curpos, int curl, int curr) {
55     if (segt[curpos].l == curl && segt[curpos].r == curr) return segt[curpos];
56     else {
57         int mid = segt[curpos].l + segt[curpos].r >> 1;
58         if (curr <= mid) return query(lson, curl, curr);
59         else if (curl > mid) return query(rson, curl, curr);
60         else {
61             Node lnode = query(lson, curl, mid), rnode = query(rson, mid + 1, curr);
62             Node ret; ret.l = curl, ret.r = curr;
63             maintain(ret, lnode, rnode);
64             return ret;
65         }
66     }
67 }
68 
69 int main() {
70     int n, q;
71     while (~scanf("%d%d", &n, &q)) {
72         rep1(i, 1, n) scanf("%d", &a[i]);
73         build(1, 1, n);
74         while (q--) {
75             int l, r; scanf("%d%d", &l, &r);
76             Node cur = query(1, l, r);
77             ll ans = -1;
78             rep0(i, 0, 48) {
79                 if ((ll)cur.val[i] < (ll)cur.val[i + 1] + (ll)cur.val[i + 2]) {
80                     ans = (ll)cur.val[i] + (ll)cur.val[i + 1] + (ll)cur.val[i + 2];
81                     break;
82                 }
83             }
84             printf("%lld\n", ans);
85         }
86     }
87     return 0;
88 }

View Code

L:

又是线段树题,背锅。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
2019 HDOJ Multi
服务器时不时爆炸,有点难受。题目链接:http://acm.hdu.edu.cn/userloginex.php?cid849(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Facm.hdu.edu.cn%2Fuserloginex.php%3Fcid%3D849)
Wesley13 Wesley13
3年前
P2P技术揭秘.P2P网络技术原理与典型系统开发
Modular.Java(2009.06)\.Craig.Walls.文字版.pdf:http://www.t00y.com/file/59501950(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fwww.t00y.com%2Ffile%2F59501950)\More.E
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法
Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法参考文章:(1)Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.codeprj.com%2Fblo
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这