题目链接 Problems
Problem A
快速幂累加即可。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; LL ans = 0; LL n, d; int T; const LL mod = 1e9 + 7; inline LL Pow(LL a, LL b, LL Mod){ LL ret(1); for (; b; b >>= 1, (a *= a) %= Mod) if (b & 1) (ret *= a) %= Mod; return ret; } int main(){ scanf("%d", &T); while (T--){ cin >> n >> d; ans = 0; rep(i, 1, n){ ans += Pow(i, d, mod); ans %= mod; } printf("%lld\n", ans); } return 0; }Problem B
对于每个帮派，并查集维护就可以了。
求第$k$大的时候树状数组上二分就好了。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; const int N = 1e5 + 10; int T; int sz[N], c[N], father[N]; int n, m; int num; void update(int x, int val){ for (; x <= n; x += x & -x) c[x] += val; } int query(int x){ int ret = 0; for (; x; x -= x & -x) ret += c[x]; return ret; } int getfather(int x){ return father[x] == x ? x : father[x] = getfather(father[x]); } int main(){ scanf("%d", &T); while (T--){ scanf("%d%d", &n, &m); memset(c, 0, sizeof c); memset(father, 0, sizeof father); rep(i, 1, n) father[i] = i; rep(i, 1, n) update(1, 1); num = n; rep(i, 1, n) sz[i] = 1; while (m--){ int op; scanf("%d", &op); if (op == 1){ int x, y; scanf("%d%d", &x, &y); int fx = getfather(x), fy = getfather(y); if (fx == fy) continue; father[fy] = fx; int f1 = sz[fx], f2 = sz[fy], f3 = sz[fx] + sz[fy]; sz[fx] += sz[fy]; sz[fy] = 0; --num; update(f1, -1); update(f2, -1); update(f3, 1); } else{ int x; scanf("%d", &x); if (num < x){ puts("-1"); continue; } int l = 1, r = n; while (l + 1 < r){ int mid = (l + r) >> 1; if (num - query(mid - 1) >= x) l = mid; else r = mid - 1; } if (num - query(r - 1) >= x) printf("%d\n", r); else printf("%d\n", l); } } } return 0; }Problem C
递推。$f_{n} = 2f_{n-1} + f_{n-3}$
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; const int A = 5; const LL mod = 1e9 + 7; struct matrix{ LL a[A][A];} init, unit, aa; int n; LL m; int T; matrix Mul(matrix a, matrix b){ matrix c; rep(i, 1, n) rep(j, 1, n){ c.a[i][j] = 0; rep(k, 1, n) (c.a[i][j] += (a.a[i][k] * b.a[k][j] % mod)) %= mod; } return c; } matrix Pow(matrix a, LL k){ matrix ret(unit); for (; k; k >>= 1ll, a = Mul(a, a)) if (k & 1) ret = Mul(ret, a); return ret; } int main(){ n = 3; matrix dd; memset(dd.a, 0, sizeof dd.a); memset(unit.a, 0, sizeof unit.a); rep(i, 1, n) unit.a[i][i] = 1ll; dd.a[1][1] = 2; dd.a[1][2] = 0; dd.a[1][3] = 1; dd.a[2][1] = 1; dd.a[3][2] = 1; scanf("%d", &T); while (T--){ scanf("%lld", &m); LL fuck = m - 3; if (m <= 3){ if (m == 1ll) puts("1"); if (m == 2ll) puts("2"); if (m == 3ll) puts("5"); continue; } matrix cc = Pow(dd, fuck); LL ans = cc.a[1][1] * 5ll + cc.a[1][2] * 2ll + cc.a[1][3] * 1ll; ans %= mod; printf("%lld\n", ans); } return 0; }Problem D
最坏的情况即为斐波那契数列中的某几项。
那么当询问元素个数超过一定的时候（大概$87$）直接输出Yes就好了。
否则就暴力特判。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; LL a[100010]; LL c[100010]; int n, q; int cnt = 0; int main(){ scanf("%d", &n); rep(i, 1, n) scanf("%lld", a + i); scanf("%d", &q); while (q--){ int l, r; scanf("%d%d", &l, &r); if (r - l + 1 >= 100){ puts("Yes"); continue; } cnt = 0; rep(i, l, r) c[++cnt] = a[i]; sort(c + 1, c + cnt + 1); int fg = 0; rep(i, 1, cnt - 2) if (c[i] + c[i + 1] > c[i + 2]){ fg = 1; break; } puts(fg ? "Yes" : "No"); } return 0; }Problem E
分解质因数之后令$a_{i}$为每个质因数的指数。
答案为
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; LL n; int T; LL bs; LL cc; LL ans; int main(){ while (~scanf("%d", &T)){ while (T--){ scanf("%lld", &n); LL bs = sqrt(n); ans = 1; for (LL i = 2; i <= sqrt(n); ++i){ LL cc = 0; while (n % i == 0) ++cc, n /= i; ans *= (2 * cc + 1ll); } if (n > 1) ans *= 3; ++ans; ans /= 2; printf("%lld\n", ans); } } return 0; }
Problem F
答案为$2^{n-3} * n^{2} * (n+3)$
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; const LL mod = 1e9 + 7; int T; LL n, ans; inline LL Pow(LL a, LL b, LL Mod){ LL ret(1); for (; b; b >>= 1, (a *= a) %= Mod) if (b & 1) (ret *= a) %= Mod; return ret; } int main(){ scanf("%d", &T); while (T--){ scanf("%lld", &n); if (n == 1ll){ puts("1"); continue; } if (n == 2ll){ puts("10"); continue; } if (n == 3ll){ puts("54"); continue; } LL ans = Pow(2, n - 3, mod); ans *= n; ans %= mod; ans *= n; ans %= mod; ans *= (n + 3ll); ans %= mod; printf("%lld\n", ans); } return 0; }Problem G
从小到大枚举答案，每次做一遍极大极小搜索，若符合题意就直接输出。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; const int N = 2e3 + 10; LL a[N]; LL f[2][N]; LL s[N]; LL xxx; int n; int m; int ans; LL dp(int x, int pos){ if (~f[x][pos]) return f[x][pos]; if (pos == m){ if (x) return f[x][pos] = a[pos]; else return f[x][pos] = 0; } LL ret = 0; if (x){ ret = a[pos] + dp(x ^ 1, pos + 1); ret = max(ret, dp(x, pos + 1)); } else{ ret = dp(x ^ 1, pos + 1); ret = min(ret, a[pos] + dp(x, pos + 1)); } return f[x][pos] = ret; } int main(){ while (~scanf("%d", &n) && n != -1){ rep(i, 1, n) scanf("%lld", a + i); scanf("%lld", &xxx); s[0] = 0; rep(i, 1, n) s[i] = s[i - 1] + a[i]; ans = -1; for (m = 1; m <= n; ++m){ memset(f, -1, sizeof f); LL gg = dp(1, 1); if (gg >= xxx){ ans = m; break; } } printf("%d\n", ans); } return 0; }Problem H
贪心。求出每个块的大小，然后枚举每个块。记块的个数为$cnt$
两边的块如果有不小于$2$的，那么答案用$cnt + 1$更新。
中间的块大小如果有不小于$3$的，那么答案用$cnt + 2$更新。
UPD：哦草我好像没考虑0011然后翻转中间的0和1的情况，这也是一个case
代码就不改乐
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; const int N = 1e5 + 10; int a[N]; int c[N]; int n, cnt, xx, now; int ans; int main(){ while (~scanf("%d", &n)){ rep(i, 1, n) scanf(" ", a + i); xx = -1; cnt = -1; now = 0; rep(i, 1, n){ if (a[i] != xx){ c[++cnt] = now; now = 1; } else ++now; xx = a[i]; } c[++cnt] = now; ans = cnt; if (c[1] == 2 || c[cnt] == 2) ans = max(ans, cnt + 1); rep(i, 1, cnt) if (c[i] >= 3) ans = max(ans, cnt + 2); printf("%d\n", ans); } return 0; }Problem I
模拟题。
#include <cstdio> #include <set> #include <string> #include <iostream> #include <algorithm> #include <cstring> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; char s[11010]; int T; set <string> mp; int l; int n; set <string> :: iterator it; int judge(char ch){ if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9') || (ch == '-') || (ch == '_')) return 1; return 0; } int main(){ scanf("%d", &T); while (T--){ mp.clear(); scanf("%d", &n); getchar(); rep(op, 1, n){ gets(s); l = strlen(s); string s1 = ""; int i; for (i = 0; i < l; ++i){ if (s[i] == '@'){ if (i && judge(s[i - 1])) continue; s1 = ""; for (; i + 1 < l && judge(s[i + 1]); ){ s1 += s[i + 1]; ++i; } if (s1 != "") mp.insert(s1); } } } printf("%d\n", (int)mp.size()); for (it = mp.begin(); it != mp.end(); ++it) cout << *it << endl; } return 0; }Problem J
签到。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; int a[100010], b[100010]; int n ; int T; int main(){ scanf("%d", &T); while (T--){ scanf("%d", &n); rep(i, 1, n) scanf("%d", a + i); rep(i, 1, n) scanf("%d", b + i); int ff = 1, fg = 1; rep(i, 1, n) if (a[i] > b[i]) ff = 0; rep(i, 1, n) if (a[i] > b[n - i + 1]) fg = 0; if (ff && fg) puts("both"); else if (ff && !fg) puts("front"); else if (!ff && fg) puts("back"); else puts("none"); } return 0; }
转载于:https://www.cnblogs.com/cxhscst2/p/8646146.html
