A. TubeTube Feed
分析:
从所有a[i]+i-1<=t的选择种取个max即可
code:
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int a[N], b[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i ++)
cin >> a[i];
for (int i = 0; i < n; i ++)
cin >> b[i];
int s = 0, res = 0, idx = -1;
bool flag = false;
for (int i = 0; i < n; i ++)
{
if (s + a[i] <= m)
{
flag = true;
if (b[i] > res)
{
res = b[i];
idx = i + 1;
}
}
s ++;
}
if (!flag)
cout << -1 << endl;
else
cout << idx << endl;
}
return 0;
}
B. Karina and Array
分析:
实际上就是取同符号乘积的最大值
code:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N], b[N];
typedef long long LL;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
if (n == 2)
{
int num1, num2;
cin >> num1 >> num2;
cout << (LL)num1 * num2 << endl;
}
else
{
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n; i ++)
{
int x;
cin >> x;
if (x >= 0)
a[cnt1 ++] = x;
else
b[cnt2 ++] = x;
}
sort(a, a + cnt1);
sort(b, b + cnt2);
LL res;
if (cnt1 >= 2 && cnt2 >= 2)
{
res = max((LL)b[0] * b[1], (LL)a[cnt1 - 2] * a[cnt1 - 1]);
}
else if (cnt1 >= 2 && cnt2 < 2)
res = (LL)a[cnt1 - 2] * a[cnt1 - 1];
else if (cnt1 < 2 && cnt2 >= 2)
res = (LL)b[0] * b[1];
cout << res << endl;
}
}
return 0;
}
C. Bun Lover
分析:
找规律，发现结果与边长n的关系是：res = n * (n + 3) - (n - 2)
code:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N], b[N];
typedef long long LL;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
LL n;
cin >> n;
cout << n * (n + 3) - (n - 2) << endl;
}
return 0;
}
D. Super-Permutation
分析:
①当n为奇数时，除了1其他均无解
②当n为偶数时，我们可以构造一个形如n,1,n - 2,3,...的数列
首先我们可以发现n必定出现在起始位置。如果n不在起始位置，假设在位置i，那么s[i - 1] % n == (s[i - 1] + n) % n = s[i] % n。
接着，考虑构造方式。最方便的即是考虑让序列取模结果为：0，1，-1，2，-2...(-1取模意义下溢出实际上就是n - 1),按上述结果形式构造的序列n,1,n - 2,3,...即可满足所有条件
最后从结果来看就是n在偶数位递减，1在奇数位递增。
code:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
if (n == 1)
cout << 1 << endl;
else if (n & 1)
cout << -1 << endl;
else
{
for (int i = 0, j = n; i < n; i += 2, j -= 2)
a[i] = j;
for (int i = 1, j = 1; i < n; i += 2, j += 2)
a[i] = j;
for (int i = 0; i < n; i ++)
cout << a[i] << " ";
cout << endl;
}
}
return 0;
}
E. Making Anti-Palindromes
分析:
①当n为奇数时：根据定义无解。
②当n为偶数时：
当某个字符出现的次数大于n / 2时，根据容斥原理，一定存在s[i] = s[n - i + 1]。
若不存在上述情况则一定有解，考虑如何处理对称字符：倘若存在形如..a..b..b..a的字符对我们优先选择交换a和b，这样一次操作可以处理两对字符，否则将对称对形如..a..b..d..a的情况交换a和d，一次操作处理一对字符。统计出现次数最多的字符对，其出现次数记为cnt1，所有字符对总数量记为cnt2，优先处理cnt1，所以当cnt1 <= cnt2 - cnt1时，答案即cnt2 / 2，否则答案即cnt1
code:
#include <bits/stdc++.h>
using namespace std;
const int N = 27;
int h[N], h2[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
string s;
cin >> s;
if (n & 1)
cout << -1 << endl;
else
{
bool check = true;
memset(h2, 0, sizeof h2);
memset(h, 0, sizeof h);
for (int i = 0; i < n; i ++)
{
h2[s[i] - 'a'] ++;
if (h2[s[i] - 'a'] > n / 2)
{
check = false;
break;
}
}
if (check)
{
int Max = 0, cnt = 0;
for (int i = 0, j = n - 1; i < n / 2; i ++, j --)
{
if (s[i] == s[j])
{
h[s[i] - 'a'] ++;
Max = max(Max, h[s[i] - 'a']);
cnt ++;
}
}
if (Max <= cnt - Max)
cout << (cnt + 1) / 2 << endl;
else
cout << Max << endl;
}
else
cout << -1 << endl;
}
}
return 0;
}