A
int n, a[1000];
void solve(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
for(int i = 1; i <= n; i ++){
if(a[i] > a[1]){
cout << i << '\n';
return ;
}
}
cout << "-1";
}
B
int n, k;
int a[1100];
void solve(){
cin >> n >> k;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
int s = 0;
int now = 0;
for(int i = 1; i <= n; i ++){
if(now + a[i] > k){
s ++;
now = a[i];
}
else{
now += a[i];
}
}
cout << s + 1 << '\n';
}
C
For positive integers x x x and y y y, define f ( x , y ) f(x, y) f(x,y) as the remainder of ( x + y ) (x + y) (x+y) divided by 1 0 8 10^8 108.
You are given a sequence of positive integers A = ( A 1 , … , A N ) A = (A_1, \ldots, A_N) A=(A1,…,AN) of length N N N. Find the value of the following expression:∑ i = 1 N − 1 ∑ j = i + 1 N f ( A i , A j ) \displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j) i=1∑N−1j=i+1∑Nf(Ai,Aj)
注意到 a i ≤ 1 0 8 a_i\leq 10^8 ai≤108 , 所以 f ( a , b ) f(a,b) f(a,b) 需要取模的时候实际上只用减掉 1 0 8 10^8 108 ,再排序一下数组,遍历到位置 i 的时候,看看 [1, i) 哪个位置满足 a j + a i ≥ 1 0 8 a_j+a_i\geq 10^8 aj+ai≥108 , 当然也可能不存在 ;超过的位置加上 a i a_i ai 之后要减掉 1 0 8 10^8 108 , 其余位置正常加上 。前缀和优化一下即可。
void solve(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i ++){
s[i] = s[i - 1] + a[i];
}
int res = 0;
for(int i = 2; i <= n; i ++){
if(a[i - 1] + a[i] < 1e8){
res += a[i] * (i - 1) + s[i - 1];
// cout << i << ' ' << res << '\n';
continue;
}
int l = 1, r = i - 1;
while(l < r){
int mid = l + r >> 1;
if(a[mid] + a[i] >= (int)1e8) r = mid;
else l = mid + 1;
}
res += a[i] * (l - 1) + s[l - 1]; // 一种答案
int len = i - l; // (i - 1) - l + 1;
res += a[i] * len + s[i - 1] - s[l - 1] - len * (int)1e8;
}
cout << res << '\n';
}
D
For positive integers x x x and y y y, define f ( x , y ) f(x, y) f(x,y) as follows:
Interpret the decimal representations of x x x and y y y as strings and concatenate them in this order to obtain a string z z z. The value of f ( x , y ) f(x, y) f(x,y) is the value of z z z when interpreted as a decimal integer.
For example, f ( 3 , 14 ) = 314 f(3, 14) = 314 f(3,14)=314 and f ( 100 , 1 ) = 1001 f(100, 1) = 1001 f(100,1)=1001.
You are given a sequence of positive integers A = ( A 1 , … , A N ) A = (A_1, \ldots, A_N) A=(A1,…,AN) of length N N N. Find the value of the following expression modulo 998244353 998244353 998244353:∑ i = 1 N − 1 ∑ j = i + 1 N f ( A i , A j ) \displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j) i=1∑N−1j=i+1∑Nf(Ai,Aj)
首先呢,将字符串 a 跟字符串 b 拼接 = a × b l e n b + b a\times b^{lenb}+b a×blenb+b
枚举到位置 i i i 的时候, i i i 跟前面的所有的拼接 = ∑ i = 1 j − 1 ( a i × b l e n b + b ) \sum_{i=1}^{j-1}(a_i\times b^{lenb}+b) ∑i=1j−1(ai×blenb+b) ,注意取模问题,然后用前缀和优化
int const mod = 998244353;
int n, a[200010], s[200010];
void solve(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
for(int i = 1; i <= n; i ++){
s[i] = s[i - 1] + a[i];
}
auto ask = [&] (int l, int r) -> int{
return s[r] - s[l - 1];
};
auto ksm = [&] (int a, int b) {
int res = 1;
while(b --){
res = res * 10;
}
return res % mod;
};
int res = 0;
for(int i = 1; i <= n; i ++){
int len = to_string(a[i]).size();
int tmp = (ask(1, i - 1) % mod * ksm(10LL, len) % mod) % mod + (i - 1) * a[i] % mod;
res = (res + tmp % mod) % mod;
// cout << i << ' ' << tmp << '\n';
}
cout << res << '\n';
}
E
- f ( x , y ) f(x, y) f(x,y) is the length of the longest common prefix of x x x and y y y.
You are given N N N strings ( S 1 , … , S N ) (S_1, \ldots, S_N) (S1,…,SN) consisting of lowercase English letters. Find the value of the following expression:
∑ i = 1 N − 1 ∑ j = i + 1 N f ( S i , S j ) \displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(S_i,S_j) i=1∑N−1j=i+1∑Nf(Si,Sj).
- Solution One 哈希表判定前缀相不相等
字符串总长度不超过 3 e 5 3e5 3e5 , 我们不停枚举,递增的将前 cnt 个字符串的哈希值存到映射,每次答案就加上哈希值相等的元素 x 的数量 y 对应的 C y 2 C_y^2 Cy2 , 直到答案不再增加
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef unsigned long long ull;
int const P = 13331;
int const N = 3e5 + 10;
ull p[N]; // ull 溢出自动取模, 相当于 MOD 2^64
int n;
string s[N];
vector<ull> h[N];
int len[N];
ull get(int x, int l, int r){
return h[x][r] - h[x][l - 1] * p[r - l + 1];
}
void solve(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> s[i];
len[i] = s[i].size();
s[i] = ' ' + s[i];
h[i].reserve(len[i] + 3);
for(int j = 1; j <= len[i]; j ++){
h[i][j] = h[i][j - 1] * P + s[[j];
}
}
for(int i = 1; i <= n; i ++){
// cout << i << ' ' << get(i, 1, 1) << '\n';
}
int res = 0;
int now = 0;
int tmp = 0;
int cnt = 0;
while(true){
map<ull, int> mp;
tmp = 0;
now ++;
for(int i = 1; i <= n; i ++){
if(len[i] < now) continue;
mp[get(i, 1, now)] ++;
}
for(auto &[x, y] : mp){
tmp = tmp + y * (y - 1) / 2;
// if(cnt == 0) cout <<"y: "<< y << '\n';
}
// cout << ++cnt << ' ' << tmp << '\n';
if(tmp == 0) break;
res += tmp;
}
cout << res << '\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
p[0] = 1;
for(int i = 1; i < N; i ++){
p[i] = p[i - 1] * P;
}
solve();
return 0;
}
- Solution Two
字典树解法,找规律,对于每个字符串,走过哪个节点,res += 这个节点来过几个字符串,同时这个节点加 1
(自己找规律看看,我讲不清楚)
#include<bits/stdc++.h>
using namespace std;
#define int long long
int const N = 3e5 + 10;
int res = 0;
struct Trie{
int son[N][26];
int cnt[N];
int idx;
Trie(){
memset(son, 0, sizeof son);
memset(cnt, 0, sizeof cnt);
idx = 0;
}
void insert(string x){
int p = 0;
for(int i = 0; i < x.size(); i ++){
int u = x[i] - 'a';
if(!son[p][u]) son[p][u] = ++ idx; // 新建一个节点
p = son[p][u]; // 走到这个节点
res += cnt[p] ++; // 加上这个节点的答案
}
}
};
void solve(){
Trie t;
int n;
cin >> n;
for(int i = 1; i <= n; i ++){
string s;
cin >> s;
t.insert(s);
}
cout << res << '\n';
}
signed main(){
// ios::sync_with_stdio(false);
// cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T --){
solve();
}
return 0;
}