服务器时不时爆炸，有点难受。
题目链接：http://acm.hdu.edu.cn/userloginex.php?cid=849
A：
神仙题。不可做题。
B：
dp。
C：
推式子题。
D：
边分治。
E：
可以数学推理的题。但是显然打表更快找出规律。对打出来的结果做两次差分即可。
1 1 /* basic header */ 2 2 #include <bits/stdc++.h> 3 3 /* define */ 4 4 #define ll long long 5 5 #define dou double 6 6 #define pb emplace_back 7 7 #define mp make_pair 8 8 #define sot(a,b) sort(a+1,a+1+b) 9 9 #define rep1(i,a,b) for(int i=a;i<=b;++i) 1010 #define rep0(i,a,b) for(int i=a;i<b;++i) 1111 #define eps 1e-8 1212 #define int_inf 0x3f3f3f3f 1313 #define ll_inf 0x7f7f7f7f7f7f7f7f 1414 #define lson (curpos<<1) 1515 #define rson (curpos<<1|1) 1616 #define mid (curl+curr>>1) 1717 /* namespace */ 1818 using namespace std; 1919 /* header end */ 2020 2121 const ll mod = 998244353; 2222 2323 ll qp(ll x, ll b) { 2424 ll ret = 1, base = x; 2525 while (b) { 2626 if (b & 1) ret = ret * base % mod; 2727 base = base * base % mod; 2828 b >>= 1; 2929 } 3030 return ret; 3131 } 3232 3333 int main() { 3434 ll n; 3535 while (~scanf("%lld", &n)) { 3636 ll k = 0, tmp = 3; 3737 rep1(i, 2, n) k += tmp, tmp += 2; 3838 printf("%lld\n", k * qp(9, mod - 2) % mod); 3939 } 4040 return 0; 4141 }
View Code
F：
fwt题。
G：
不均等博弈题。用surrealnumber秒杀。
H：
最小割。
I：
求出本质不同的回文串的数量分布(求每种回文串的个数)，然后对每种check一下叠加答案。manacher或者字符串hash都可以。
J：
签到题。1e6+3的阶乘后面全是0已经暗示一切。
1 1 /* basic header */ 2 2 #include <bits/stdc++.h> 3 3 /* define */ 4 4 #define ll long long 5 5 #define dou double 6 6 #define pb emplace_back 7 7 #define mp make_pair 8 8 #define sot(a,b) sort(a+1,a+1+b) 9 9 #define rep1(i,a,b) for(int i=a;i<=b;++i) 1010 #define rep0(i,a,b) for(int i=a;i<b;++i) 1111 #define eps 1e-8 1212 #define int_inf 0x3f3f3f3f 1313 #define ll_inf 0x7f7f7f7f7f7f7f7f 1414 #define lson (curpos<<1) 1515 #define rson (curpos<<1|1) 1616 #define mid (curl+curr>>1) 1717 /* namespace */ 1818 using namespace std; 1919 /* header end */ 2020 2121 const int mod = 1e6 + 3; 2222 ll p[mod + 10]; 2323 int n; 2424 2525 int main() { 2626 p[0] = p[1] = 1; 2727 rep0(i, 2, mod) p[i] = 1ll * i * p[i - 1] % mod; 2828 while (~scanf("%d", &n)) { 2929 if (n >= mod) { 3030 puts("0"); 3131 continue; 3232 } 3333 n %= mod; 3434 printf("%lld\n", p[n]); 3535 } 3636 return 0; 3737 }
View Code
K：
对于某个区间，首先考虑区间第1、2、3大的边能否构成三角形，然后考虑区间第2、3 、4大的边能否构成三角形，以此类推。
只要考虑区间前44大即可，因为区间最坏情况是斐波那契数列，然而第45项就爆了1e9的范围。时间复杂度O(44*nlogn)。
1 1 /* basic header */ 2 2 #include <iostream> 3 3 #include <cstring> 4 4 /* define */ 5 5 #define ll long long 6 6 #define dou double 7 7 #define pb emplace_back 8 8 #define mp make_pair 9 9 #define sot(a,b) sort(a+1,a+1+b) 1010 #define rep1(i,a,b) for(int i=a;i<=b;++i) 1111 #define rep0(i,a,b) for(int i=a;i<b;++i) 1212 #define eps 1e-8 1313 #define int_inf 0x3f3f3f3f 1414 #define ll_inf 0x7f7f7f7f7f7f7f7f 1515 #define lson (curpos<<1) 1616 #define rson (curpos<<1|1) 1717 /* namespace */ 1818 using namespace std; 1919 /* header end */ 2020 2121 const int maxn = 1e5 + 10; 2222 int a[maxn]; 2323 2424 struct Node { 2525 int l, r, val[50]; 2626 }; 2727 2828 Node segt[maxn << 2]; 2929 3030 void maintain(Node &fa, Node &ls, Node &rs) { 3131 int i = 0, j = 0; 3232 rep0(c, 0, 50) { 3333 if (i >= 50) 3434 fa.val[c] = rs.val[j++]; 3535 else if (j >= 50) 3636 fa.val[c] = ls.val[i++]; 3737 else if (ls.val[i] < rs.val[j]) 3838 fa.val[c] = rs.val[j++]; 3939 else fa.val[c] = ls.val[i++]; 4040 } 4141 } 4242 4343 void build(int curpos, int curl, int curr) { 4444 segt[curpos].l = curl, segt[curpos].r = curr; 4545 // memset(segt[curpos].val, 0, sizeof(segt[curpos].val)); 4646 if (curl < curr) { // if is not leaf node 4747 int mid = curl + curr >> 1; 4848 build(lson, curl, mid); build(rson, mid + 1, curr); 4949 maintain(segt[curpos], segt[lson], segt[rson]); 5050 } else 5151 segt[curpos].val[0] = a[curl]; // if is leaf node 5252 } 5353 5454 Node query(int curpos, int curl, int curr) { 5555 if (segt[curpos].l == curl && segt[curpos].r == curr) return segt[curpos]; 5656 else { 5757 int mid = segt[curpos].l + segt[curpos].r >> 1; 5858 if (curr <= mid) return query(lson, curl, curr); 5959 else if (curl > mid) return query(rson, curl, curr); 6060 else { 6161 Node lnode = query(lson, curl, mid), rnode = query(rson, mid + 1, curr); 6262 Node ret; ret.l = curl, ret.r = curr; 6363 maintain(ret, lnode, rnode); 6464 return ret; 6565 } 6666 } 6767 } 6868 6969 int main() { 7070 int n, q; 7171 while (~scanf("%d%d", &n, &q)) { 7272 rep1(i, 1, n) scanf("%d", &a[i]); 7373 build(1, 1, n); 7474 while (q--) { 7575 int l, r; scanf("%d%d", &l, &r); 7676 Node cur = query(1, l, r); 7777 ll ans = -1; 7878 rep0(i, 0, 48) { 7979 if ((ll)cur.val[i] < (ll)cur.val[i + 1] + (ll)cur.val[i + 2]) { 8080 ans = (ll)cur.val[i] + (ll)cur.val[i + 1] + (ll)cur.val[i + 2]; 8181 break; 8282 } 8383 } 8484 printf("%lld\n", ans); 8585 } 8686 } 8787 return 0; 8888 }
View Code
L：
又是线段树题，背锅。