2019 HDOJ Multi-University Training Contest Stage 2(杭电多校)

开发技术作者： 2024-06-25 13:30:01

服务器时不时爆炸，有点难受。题目链接：http://acm.hdu.edu.cn/userloginex.php?cid=849 A：神仙题。不可做题。 B： dp。 C：推式子题。 D：边分治。 E：可以数学推理的题。但是显然打表更快找出规律。对打出来的结果做两次差分即可。 1 /* basic header */ 2 #include <bits/stdc++.h> 3 /

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

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

A：

神仙题。不可做题。

B：

dp。

C：

推式子题。

D：

边分治。

E：

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

 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,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已经暗示一切。

 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) 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,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)。

 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,a+1+b)
10 #define rep1(i,b) for(int i=a;i<=b;++i)
11 #define rep0(i,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,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 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,curr);
59         else if (curl > mid) return query(rson,curr);
60         else {
61             Node lnode = query(lson,mid),rnode = query(rson,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,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 }