- 题意
给出 A A A， B B B，表示两场地震的强度。已知强度每 + 1 +1 +1所产生的能量就是原来的 32 32 32倍。求 A A A地震产生的能量是 B B B地震产生能量的多少倍。数据保证 A ≥ B A≥B A≥B。
- 思路
输出 3 2 A − B 32^{A-B} 32A−B即可 - 代码
#includeB.typousing namespace std; int main() { long long a, b; cin >> a >> b; cout << (long long)pow(32, a - b) << endl; return 0; }
- 题意
现在给出两个字符串 S S S， T T T，问 S S S串交换相邻的两个字符或不交换是否能变成 T T T
- 思路
找到S与T的第一个不同的字符，将它与后面一个字符进行交换，再比较两串是否相同。如果没有不同的字符，则直接相同 - 代码
#includeC.Select Mulusing namespace std; int main() { char s[105], t[105]; cin >> s + 1; cin >> t + 1; int len = strlen(s + 1); for (int i = 1; i < len; i++) { if (s[i] != t[i]) { swap(s[i], s[i + 1]); break; } } if (strcmp(s + 1, t + 1) == 0) cout << "Yesn"; else cout << "Non"; return 0; }
- 题意
给你一个数 n n n， n n n的每位数可以随便排列，然后可以将 n n n分成两部分。求这两部分乘积的最大值。注意两部分都不能有前导零。 n ≤ 1 0 9 n≤10^9 n≤109。
- 思路
直接贪心求解，将每位的数字进行排序，然后从大到小的依次交替排列到两个数的后面即可 - 代码
#includeD.online gamesusing namespace std; char s[15]; int x, y; int main() { cin >> s + 1; int len = strlen(s + 1); sort(s + 1, s + 1 + len); for (int i = len; i >= 1; i--) { if (x > y) y = y * 10 + s[i] - '0'; else x = x * 10 + s[i] - '0'; } cout << x * y << endl; return 0; }
- 题意
给你 n n n条线段，每条线段有一个左端点 a i a_i ai和长度 b i b_i bi。设 d k d_k dk表示有 d k d_k dk个点被覆盖了 k k k次，求出所有 d k ( k ∈ [ 1 , n ] ) dk(k∈[1,n]) dk(k∈[1,n])并输出。
n ≤ 2 × 1 0 5 n≤2×10^5 n≤2×105， 1 ≤ a i , b i ≤ 1 0 9 1≤ai,bi≤10^9 1≤ai,bi≤109。
- 思路
考虑差分统计贡献。
需要对 +1 贡献的 左端点 和有 -1 贡献的 右端点+1 进行离散化。
设离散化后一共有 c n t cnt cnt个点，实际上这 c n t cnt cnt个点构成了 c n t − 1 cnt−1 cnt−1个左开右闭的区间，那么
第 i i i个点用来统计 [ d a t e i , d a t e i + 1 ) [date_i,date_{i+1}) [datei,datei+1)这段区间的贡献，直接用一个 c n t i cnt_i cnti来记录。（显然这段区间中没个点被覆盖次数都是一样的吧）
最后枚举所有表示的区间统计答案即可。 - 代码
#includeE. LEQusing namespace std; const int N = 4e5 + 5; int n; int a[N], b[N], date[N], ans[N], cnt[N]; set s; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d", &a[i], &b[i]); b[i] += a[i]; s.insert(a[i]); s.insert(b[i]); } date[0] = 0; int cntt = 0; for (auto i : s) date[++cntt] = i; for (int i = 1; i <= n; i++) { a[i] = lower_bound(date + 1, date + 1 + cntt, a[i]) - date; b[i] = lower_bound(date + 1, date + 1 + cntt, b[i]) - date; cnt[a[i]]++; cnt[b[i]]--; } for (int i = 1; i <= cntt; i++) cnt[i] += cnt[i - 1]; for (int i = 1; i < cntt; i++) ans[cnt[i]] += date[i + 1] - date[i]; for (int i = 1; i <= n; i++) cout << ans[i] << " n"[i == n]; return 0; }
- 题意
给你一个长度为 n n n的序列 a a a，统计有多少长度 k ≥ 2 k≥2 k≥2的子序列 a b 1 , a b 2 , . . . , a b k a_{b_1},a_{b_2},...,a_{b_k} ab1,ab2,...,abk满足 a b 1 ≤ a b k a_{b_1}≤a_{b_k} ab1≤abk，答案对 998244353 998244353 998244353取模。
n ≤ 3 × 1 0 5 , 1 ≤ a i ≤ 1 0 9 n≤3×10^5,1≤ai≤10^9 n≤3×105,1≤ai≤109。
- 思路
不难发现所有贡献只和序列首元素和序列尾元素之间的大小关系有关。
然后你考虑找出所有满足 a j ≤ a i aj≤ai aj≤ai的 ( j , i ) (j,i) (j,i)数对，然后 j , i j,i j,i之间的数可以随便选，假设有 s = i − j − 1 s=i−j−1 s=i−j−1个，那么 ( j , i ) (j,i) (j,i)的贡献就是 2 s 2^s 2s。
暴力找所有合法数对是 O ( n 2 ) O(n^2) O(n2)的，考虑用上面那个错解的方法优化。
假设现在有三个点 j , k , i j,k,i j,k,i，满足 j , k < i j,k 不难发现 ( j , i ) (j,i) (j,i)的贡献是 ( k , i ) (k,i) (k,i)的贡献的 2 1 2^1 21倍。
那我们对 j j j这个点在树状数组上统计贡献时可以用 2 n − j 2^{n−j} 2n−j，这样每个点的贡献都是 2 倍 2 倍的缩小。
然后考虑枚举右端点 i i i，并且再次之前 [ 1 , i − 1 ] [1,i−1] [1,i−1]中的点的全部被统计进树状数组了。
假设 j 1 , j 2 , . . . , j k j_1,j_2,...,j_k j1,j2,...,jk的点都满足 a j x ≤ a i a_{j_x}≤a_i ajx≤ai。
此时在树状数组上查询的和其实就是 ∑ x = 1 k 2 n − j x sum_{x=1}^k2^{n-j_x} ∑x=1k2n−jx
显然算多了，那么算多了多少？
假设 j k = i − 1 j_k=i−1 jk=i−1，但 j k j_k jk在树状数组中的贡献为 2 n − i + 1 2^{n−i+1} 2n−i+1，它与 i i i的贡献为 2 0 = 1 2^0=1 20=1，所以应该除以这个数 2 n − i + 1 2^{n−i+1} 2n−i+1，然后你发现与前面所有的有贡献的点都需要除以 2 n − i + 1 2^{n−i+1} 2n−i+1。
所以答案为
∑ x = 1 k 2 n − j x 2 n − i + 1 frac{sum_{x=1}^{k}2^{n-j_x}}{2^{n-i+1}} 2n−i+1∑x=1k2n−jx
统计所有 i i i的贡献求和即为最终答案。 - 代码
#includeusing namespace std; const int N = 1.2e6 + 5, MOD = 998244353; int norm(int x){if(x<0){x+=MOD;} if(x>=MOD){x-=MOD;}return x;} template T binpow(T a, int b){T res=1;for(;b;b/=2,a*=a){if(b%2){res*=a;}}return res;} struct Z { int x; Z(int x = 0): x(norm(x)){} int val() const { return x; } Z operator-() const { return Z(norm(MOD - x)); } Z inv() const={assert(x != 0);return binpow(*this, MOD - 2);} Z& operator*=(const Z& rhs){x=1LL*x*rhs.x%MOD;return *this;} Z& operator+=(const Z& rhs){x=norm(x+rhs.x);return *this;} Z& operator-=(const Z& rhs){x=norm(x-rhs.x);return *this;} Z& operator/=(const Z& rhs){return *this*=rhs.inv();} friend Z operator*(const Z& lhs, const Z& rhs){Z res=lhs;res*=rhs;return res;} friend Z operator+(const Z& lhs, const Z& rhs){Z res=lhs;res+=rhs;return res;} friend Z operator-(const Z& lhs, const Z& rhs){Z res=lhs;res-=rhs;return res;} friend Z operator/(const Z& lhs, const Z& rhs){Z res=lhs;res/=rhs;return res;} }; struct Fenwick_tree { vector bit; Fenwick_tree(int n): bit(n + 1){} void update(int pos, Z val){ for (int i = pos; i < (int)bit.size(); i += i & (-i)) bit[i] += val; } Z query(int pos){ Z res = 0; for (int i = pos; i >= 1; i -= i & (-i)) res += bit[i]; return res; } }; int main() { ios::sync_with_stdio(0), cin.tie(0); int n; cin >> n; vector a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector b(a); sort(b.begin(), b.end()); b.resize(unique(b.begin(), b.end()) - b.begin()); for (auto& i : a) i = lower_bound(b.begin(), b.end(), i) - b.begin() + 1; Z ans = 0; Fenwick_tree F(n); for (int i = 0; i < n; i++) { ans += F.query(a[i]) * binpow(Z(2), i); F.update(a[i], binpow(Z(2), i + 1).inv()); } cout << ans.val() << "n"; return 0; }
