怎么做菠菜网站,福建宏盛建设集团有限公司网站,宁波网站建设服务提供商,网站文章不收录的原因ABC342 题解
A
Description
给定一个串 s s s#xff0c;求与 s s s 中其它字符不同的唯一字符的编号。
Solution
直接把 s s s 存到 t t t 里排序#xff08;确实#xff0c;sort(t.begin(), t.end()) 就可以#xff09;#xff0c;首尾特判再到 s s s 里查一下…ABC342 题解
A
Description
给定一个串 s s s求与 s s s 中其它字符不同的唯一字符的编号。
Solution
直接把 s s s 存到 t t t 里排序确实sort(t.begin(), t.end()) 就可以首尾特判再到 s s s 里查一下就可以了。
Code
void solve(int testcase, ...){init_vars();string s; cin s;string t s; sort(t.begin(), t.end());char ans;if(t[0] ! t[1]) ans t[0];else ans t[t.length() - 1];for(int i 0; i s.length(); i){if(s[i] ans) cout i 1 endl;}
}B
Description
给定一个数列 a a a表示 b a i i \displaystyle{b_{a_i} i} baii。
给定 q q q 次查询 x x x 和 y y y求 b x b_x bx 是否小于 b y b_y by。
Solution
比 A 还简单直接模拟。
Code
int p[201];void solve(int testcase, ...){init_vars();int n; cin n;for(int i 1; i n; i){int x; cin x; p[x] i;}int q; cin q;for(int i 0; i q; i){int a, b; cin a b;if(p[a] p[b]) cout a endl;else cout b endl;}
}C
Description
给定一个串和 q q q 个操作每次操作将一种字符换成另一个。
问最后的字符串。
Solution
维护一个 a 到 z 的表。
暴力当然不是那种 bt的复杂度是 O ( 26 ⋅ n ) O(26\cdot n) O(26⋅n)。
Code
void solve(int testcase, ...){init_vars();int n; cin n;string s; cin s;cin n;int bucket[26];for(int i 0; i 26; i) bucket[i] i;for(int i 0; i n; i){char u, v; cin u v;u - a, v - a;for(int j 0; j 26; j){if(bucket[j] u) bucket[j] v;}}for(int i 0; i s.length(); i){cout (char)(a bucket[s[i] - a]);}cout endl;
}D
Description
给定数列 a a a求 ( i , j ) (i,j) (i,j) 的个数 i j ij ij满足 a i a j x 2 ( x ∈ Z ) a_ia_jx^2\ (x\in \Z) aiajx2 (x∈Z)。
Solution
对于每个数求最小的数使其满足相乘后乘积是完全平方数记为 f ( x ) f(x) f(x)。
例如 45 × 5 1 5 2 45\times 515^2 45×5152所以 f ( 45 ) 5 f(45)5 f(45)5。
可以证明 f f f 值相等的两个数乘积才会完全平方。请读者自行证明
注意特判 0 0 0 的情况
Code
int a[200001], b[200001];int calc(int x){if(x 0) return 0;vectorpairint, int vec;for(int i 2; i * i x; i){if(x % i 0){vec.push_back(make_pair(i, 0));while(x % i 0){vec[vec.size() - 1].second;x / i;}}}if(x) vec.push_back(make_pair(x, 1));int ans 1;for(int i 0; i vec.size(); i){if(vec[i].second % 2) ans * vec[i].first;}return ans;
}void solve(int testcase, ...){init_vars();int n; cin n;for(int i 0; i n; i){cin a[i];a[i] calc(a[i]);}mapint, int mp;for(int i 0; i n; i) mp[a[i]];int ans 0, tot 0;for(int i 0; i n; i){if(a[i] 0){ans n - tot - 1, tot;continue;}mp[a[i]]--;ans mp[a[i]];}cout ans endl;
}E
Description
自己看去。
Solution
按着 Dij 的方法做笔者没有能力加以证明。
复杂度 O ( Dij ) O(\text{Dij}) O(Dij)。
Code
vectorpairint, node gv[200001];int dis[200001], vis[200001];inline void add_edge(int u, int v, int l, int d, int k, int c){gv[u].push_back(make_pair(v, (node){l, d, k, c}));
}void dij(int st){memset(dis, -1, sizeof(dis));priority_queuepairint, int pq;pq.push(make_pair(LONG_LONG_MAX, st));dis[st] LONG_LONG_MAX;while(pq.size()){int x pq.top().second, y pq.top().first;pq.pop();if(vis[x]) continue;vis[x] 1;for(auto v : gv[x]){if(y - v.second.l - v.second.c 0) continue;int z min((y - v.second.l - v.second.c) / v.second.d * v.second.d v.second.l, \v.second.l (v.second.k - 1) * v.second.d);
// cout v.first z endl;if(z dis[v.first]){dis[v.first] z;pq.push(make_pair(z, v.first));}}}
}void solve(int testcase, ...){init_vars();int n, m; cin n m;for(int i 0; i m; i){int l, d, k, c, a, b;cin l d k c a b;add_edge(b, a, l, d, k, c);}dij(n);for(int i 1; i n; i){if(dis[i] -1) cout Unreachable endl;else cout dis[i] endl;}
}FG
F 建议看下 Pigeon 的题解。
G 可持久化启动
