Contestant(alt). Rank 1774. Rating +20.
A. TubeTube Feed
题意
给定两个序列 \(a, b\),选择 \(a_i\) 的代价为 \(a_i + i\) (从 \(0\) 开始),价值为 \(b_i\)。输出代价不超过 \(t\) 的条件下的最大价值。
思路
我们找出所有代价不超过 \(t\) 的价值,并遍历这些价值,找出最大值即可。
时间复杂度:\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n, t;
cin >> n >> t;
vector<int> p;
vector<int> e(n);
for(int i=0;i<n;i++){
int cur;
cin >> cur;
if(cur + i <= t) p.emplace_back(i);
}
for(int i=0;i<n;i++) cin >> e[i];
if(p.empty()){
cout << -1 << '\n';
return;
}
int mx = p[0];
for(auto &x : p) {
if(e[mx] < e[x]) mx = x;
}
cout << mx + 1 << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}
很水
B. Karina and Array
题意
给定一串整数序列,定义序列的美丽值为所有相邻两数乘积的最大值。在可以任意删除元素且最后至少剩余两个元素的条件下,输出最大的美丽值。
思路
很显然,我们直接排个序,对前两个和最后两个分别取乘积,并取最大值即可。
时间复杂度:\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
sort(a.begin(), a.end());
int ans = -inf;
ans = max(ans, a[0] * a[1]);
ans = max(ans, a[n - 2] * a[n - 1]);
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}
还是很水
C. Bun Lover
题意
给定一个肉桂卷的大小 \(n\),输出边长的总和。
具体来说,如下图,棕色线段的长度就是答案:
思路
我们将其拆分成两段,如下图(来自官方题解):
可以发现粉色和青色段最后都会向里折1格,我们将其展开,那么长度恰好成为了一个等差数列的前 \(n\) 项和。
具体来说,青色的长度为 \(1 + 2 + \dots + n = \frac{n \cdot (n + 1)}{2}\),粉色的长度为 \(1 + 2 + \dots + (n + 1) = \frac{(n + 1) \cdot (n + 2)}{2}\)
因此,最后的结果为 \(\frac{(n + 1) \cdot (n + 2)}{2} + \frac{n \cdot (n + 1)}{2} + 1 = \frac{(n + 1) \cdot (n + 2) + n \cdot (n + 1)}{2} + 1 = \frac{2 \cdot (n + 1)^2}{2} + 1 = (n + 1)^2 + 1\)
不过当然,像我这样盲猜有规律然后直接乱写也是可以的,这样你可以得到 \(26 + (n + 6)(n - 4)\)。
时间复杂度:\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
cout << 26 + (11 + 11 + (n - 5) * 2) * (n - 4) / 2 << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}
无脑Ocean在线乱猜
D. Super-Permutation
题意
给定排列 \(a\) 的长度,构造一个新序列 \(b\),其中 \(b_i = ((a_1 + a_2 + \ldots + a_i) \bmod n) + 1\)。
若能找出一个排列 \(a\),满足构造出的新序列 \(b\) 为一个排列,那么输出 \(a\),否则输出 \(-1\)。
思路
我们先来猜测一下如何构造:
首先,为了方便拿到 \(1\),我们将第一个数指定为 \(n\)。
那么我们接下来就可以放上 \(n - 1\) 和 \(2\),此时 \(n + n - 1 = 2n - 1, 2n - 1 + 2 = 2n + 1\),\((2n - 1) \bmod n + 1 = n, (2n + 1) \bmod n + 1 = 2\),此时我们拿到了 \(n, 2\)。
我们继续放上 \(n - 3\) 和 \(4\),此时 \(2n + 1 + n - 3 = 3n - 2, 3n - 2 + 4 = 3n + 2\),\((3n - 2) \bmod n + 1 = n - 1, (3n + 2) \bmod n + 1 = 3\),此时我们拿到了 \(n - 1, 3\)。
依次类推,我们可以构造出排列 \(\{n, n - 1, 2, n - 3, 4, \ldots \}\),以此得到序列 \(b = \{1, n, 2, n - 1, 3, \dots \}\)。
不难发现,上述构造方法对 \(1\) 和偶数都一定有解,而除 \(1\) 之外的奇数都无解。
事实上,我们来单独考虑这种无解情况,\(b_n = (a_1 + a_2 + \ldots + a_n) \bmod n + 1= (1 + 2 + \ldots + n) \bmod n + 1 = \frac{(1 + n)n}{2} \bmod n + 1\)。
如果 \(n\) 为 \(1\) 或者偶数,那么分母对 \(n\) 有效,可以写作 \((1 + n) \frac{n}{2} \bmod n + 1\),我们无法在提出 \(n\) 后让式子为整数。
而相反地,当 \(n\) 为除 \(1\) 之外的奇数时,上述式子变成了 \(n \frac{1 + n}{2} \bmod n + 1\),我们可以提出 \(n\),此时 \(b_n\) 变为了 \(1\)。
猜测的第一句话其实是一定需要满足的,我们假设 \(a_k = n\),此时 \(b_k = (b_{k - 1} - 1 + a_k) \bmod n + 1= b_{k - 1}\),那么为了防止 \(b\) 元素重复,\(k\) 只能为 \(1\)。
那么,\(b_1\) 只能为 \(1\)。
不难发现,当 \(n\) 为除 \(1\) 之外的奇数时,\(b_1 = b_n\),因此无解。
时间复杂度:\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
vector<bool> st(n + 1);
vector<int> ans(n);
ans[0] = n;
st[n] = true;
bool ok = true;
for(int i=1;i<n;i+=2) {
ans[i] = n - i;
if(st[n - i]) ok = false;
st[n - i] = true;
}
for(int i=2;i<n;i+=2){
ans[i] = i;
if(st[i]) ok = false;
st[i] = true;
}
if(!ok) cout << -1 << '\n';
else{
for(auto e : ans) cout << e << ' ';
cout << '\n';
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}
根据题意构造(x),根据猜测构造(√)
E. Making Anti-Palindromes
题意
定义反回文串为一个长为 \(n\) 的字符串 \(s\),满足对于任意 \(i \in [1, n]\) 都有 \(s_i \neq s_{n - i + 1}\)。
给定一个字符串,定义操作为选定任意两个不同位置的字符并交换它们,输出将字符串变为反回文串所需的最小的操作数。若无解输出 \(-1\)。
思路
首先,\(n\) 是奇数时,一定无解。
其次,只要有一个字母出现次数大于 \(\frac{n}{2}\),那么也是无解,毕竟一定会出现至少一对相同的字母。
那么,我们统计 \(s_i = s_{n + 1 - i}\) 的个数为 \(k\),以及对于所有字符 \(c\),\(s_i = s_{n + 1 - i}\) 的个数的最大值 \(m\),借此,我们可以先缩小一下范围:
\(ans \geq m\),因为这 \(m\) 对一定得和其他不同的字符对进行交换;
\(ans \geq \lceil \frac{k}{2} \rceil\),因为我们至少得两两配对。
那么显然,如果满足可以两两配对的条件,\(ans_{min} = \lceil \frac{k}{2} \rceil\)。
但如果不满足,那么我们不难发现,只要我们将数量少的字符对和其他数量少的字符对的进行交换,那么最后一定只会多出数量最多的那个字符对,也就是我们之前统计的数量为 \(m\) 的那个字符。
那么,最后约束就只剩下 \(m\) 了,\(ans_{min} = m\)。
因此,最后答案就是 \(\max(m, \lceil \frac{k}{2} \rceil)\)。
时间复杂度:\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
string s;
cin >> s;
if(n % 2 == 1){
cout << -1 << '\n';
return;
}
vector<int> cnt(26), oc(26);
int m = 0, k = 0;
for(int i=0;i<n/2;i++) {
oc[s[i] - 'a'] ++, oc[s[n - i - 1] - 'a'] ++;
if (s[i] == s[n - i - 1]) cnt[s[i] - 'a']++, k++;
}
for(int i=0;i<26;i++){
m = max(m, cnt[i]);
if(oc[i] > n / 2){
cout << -1 << '\n';
return;
}
}
cout << max(m, (k + 1) / 2) << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}
好绕,好高级,我好若
F. Gardening Friends
题意
给定一棵根为 \(1\) 且边权都是 \(k\) 的树,定义树的价值为所有点到根节点的 最大长度。
定义一次操作为将根修改为相邻的任意节点,代价为 \(c\)。
输出任意次操作后,树的价值 与 代价和 的差值的最大值。
思路
首先,我们可以用 \(\mathtt{bfs}\) 先找出以 \(1\) 为根的最长链,记端点为 \(s\)。
那么,我们再以 \(s\) 为根进行 \(\mathtt{bfs}\),显然最长链就是整棵树的最长链了。
我们记这个最长链的另一个端点为 \(t\),若我们以 \(t\) 为根再进行一次 \(\mathtt{bfs}\),那么对于所有的点,我们都可以快速求出以它为根的最长链长度了。
那么,我们枚举所有点,若长度为 \(p\),并且和 \(1\) 相距 \(q\),那么我们更新最大值 \(k * p - c * q\)。
为何能快速求出呢?因为在正反两次 \(\mathtt{bfs}\) 树的最长链时,我们可以更新出 每个点的所有链中 的 两条最长链,然后我们就可以取最大值。
时间复杂度:\(O(n)\)
对应AC代码
#define chatgpt "bits/stdc++.h"
#include chatgpt
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, k, c;
cin >> n >> k >> c;
vector<vector<int>> e(n + 1);
for(int i=1;i<n;i++){
int u, v;
cin >> u >> v;
e[u].pb(v), e[v].pb(u);
}
auto bfs = [&](int s){
queue<int> q;
q.ep(s);
vector<int> d(n + 1, -1);
d[s] = 0;
while(!q.empty()){
int x = q.front(); q.pop();
for(auto y : e[x]){
if(d[y] != -1) continue;
d[y] = d[x] + 1;
q.ep(y);
}
}
return d;
};
auto d1 = bfs(1);
int s = max_element(all(d1)) - d1.begin();
auto ds = bfs(s);//找出最长链
int t = max_element(all(ds)) - ds.begin();
auto dt = bfs(t);
int ans = 0;
for(int i=1;i<=n;i++) ans = max(ans, k * max(ds[i], dt[i]) - d1[i] * c);
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}
也是个很有意思的图论
G1. Magic Triples (Easy Version)
详见G2,区别是G1的数据量更小
G2. Magic Triples (Hard Version)
题意
定义如果一个三元组 \((i, j, k)\) 满足下面的条件,那么这个三元组是有魔力的:
\(1 \leq i, j, k \leq n\);
\(i, j, k\) 各不相同;
存在一个正整数 \(b\),满足 \(a_i \cdot b = a_j, a_j \cdot b = a_k\)。
给定一个序列,输出所有三元组中有魔力的个数。
思路
首先,我们完全可以在确定一个数的条件下,枚举正整数 \(b\) 来计算答案。
那么我们不妨确定 \(j\),并枚举 \(b\),那么 \(a_i = \frac{a_j}{b}, a_k = ba_j\)。
很显然,如果我们从小到大枚举,是一定会超时的。
考虑到 \(b\) 一定是整数,所以我们在计算 \(b\) 的时候可以顺便计算 \(\frac{a_j}{b}\),那么复杂度可以降到 \(\log a_j\)。
当然,考虑到重复问题,我们单独计算 \(b = 1\) 的贡献。
在 \(1e6\) 的范围内,复杂度可行,但对于 \(1e9\) 的数据,我们一定得做优化了。
考虑到 \(a_k = ba_j \leq \max(a)\),我们可以一定程度复杂度,此时可以 \(AC\)。
时间复杂度:\(小于O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
int mx = 0;
map<int, int> mp;
for(int i=0;i<n;i++){
int cur;
cin >> cur;
mp[cur] ++;
mx = max(mx, cur);
}
int ans = 0;
for(auto [a, cnt] : mp) {
ans += max(0ll, cnt * (cnt - 1) * (cnt - 2));
if(a != 1 && mp.count(1) && mp.count(a * a)) ans += cnt * mp[1] * mp[a * a];
for (int b = 2; b <= a / b && a * b <= mx; b ++){
if(a % b != 0) continue;
if(mp.count(a / b) && mp.count(a * b)) ans += cnt * mp[a / b] * mp[a * b];
if(b != a / b && mp.count(b) && mp.count(a * a / b)) ans += cnt * mp[b] * mp[a * a / b];
}
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}
卡过去力!