A. TubeTube Feed
#include <bits/stdc++.h>
using namespace std;
int main() {
int q;
cin >> q;
while (q--) {
int n, t, res = -1, id = -1;
cin >> n >> t;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
for (int i = 1; i <= n; i++) {
if (a[i] <= t) {
if (b[i] > res) res = b[i], id = i;
}
t--;
}
cout << id << "\n";
}
}
B. Karina and Array
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read(){
int x = 0 , f = 1 , ch = getchar();
while( (ch < '0' || ch > '9') && ch != '-' ) ch = getchar();
if( ch == '-' ) f = -1 , ch = getchar();
while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
return x * f;
}
void solve(){
int n = read();
vector<int> a(n);
for( auto & i : a ) i = read();
sort( a.begin() ,a.end() );
printf("%lld\n" , max( a[0] * a[1] , a[n-1] * a[n-2] ) );
}
int32_t main(){
for( int t = read() ; t ; t -- )
solve();
}
C. Bun Lover
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read(){
int x = 0 , f = 1 , ch = getchar();
while( (ch < '0' || ch > '9') && ch != '-' ) ch = getchar();
if( ch == '-' ) f = -1 , ch = getchar();
while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
return x * f;
}
int32_t main(){
for( int t = read() , n ; t ; t -- ){
n = read();
printf("%lld\n" , (n+1)*(n+1) + 1 );
}
}
D. Super-Permutation
打表找规律，发现\(b_i+1\)一定有\(n,1,n-1,2,n-2,3,\cdots\)这样的，根据\(b_i\)还原\(a_i\)即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read(){
int x = 0 , f = 1 , ch = getchar();
while( (ch < '0' || ch > '9') && ch != '-' ) ch = getchar();
if( ch == '-' ) f = -1 , ch = getchar();
while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
return x * f;
}
int32_t main(){
for( int t = read() , n ; t ; t -- ){
n = read();
if( n == 1 ){
printf("1\n");
}else if( n & 1 ){
printf("-1\n");
}else{
int l = 1 , r = n;
vector<int> a;
for( int i = n / 2 ; i ; i -- , l ++ , r -- )
a.push_back(l-1) , a.push_back(r-1);
printf("%d" , n );
for( int i = 1 , s = n , x ; i < n ; i ++ ){
x = ((a[i] - s) % n + n) % n;
s = ( s + x ) % n;
printf(" %d" , x );
}
printf("\n");
}
}
}
E. Making Anti-Palindromes
如果有任意个字母出现次数超过一半，则一定无法构成。
统计每一个相同的字母对的数量。如果有一种字母的对数大于\(\frac n 2\)，则一定不可以。
交换次数，要么是最多的字母对数，要么是重复的最多的对数。两者取较大值即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
#define Count(arr) ( accumulate(arr.begin(),arr.end(),0ll) )
#define Max(arr) ( *max_element( arr.begin() , arr.end() ) )
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
for (int n, m; t; t--) {
cin >> n;
string s;
cin >> s;
if (n & 1) {
cout << "-1\n";
continue;
}
m = n / 2;
vector<int> cnt(26), p(26);
for (int i = 1; i <= m; i++) {
if (s[i - 1] == s[n - i]) cnt[s[i - 1] - 'a']++;
p[s[i - 1] - 'a']++, p[s[n - i] - 'a']++;
}
if (Max(p) > m) cout << "-1\n";
else cout << max(Max(cnt), (Count(cnt) + 1) / 2) << "\n";
}
}
F. Gardening Friends
首先找到直径的的两个端点\(p,q\)，树上任意一个点距离最远的点一定包括\(p,q\)中至少一个。所以计算出任意点的\(p,q\)的距离，就可以\(O(1)\)的计算出根移动到每一个的点的收益。枚举根移动的位置取最大收益即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
void solve() {
int n = read(), k = read(), c = read();
vector<vector<int>> e(n + 1);
for (int i = n - 1, x, y; i; i--)
x = read(), y = read(), e[x].push_back(y), e[y].push_back(x);
auto bfs = [e, n](int x) {
vector<int> d(n+1, -1);
queue<int> q;
q.push(x), d[x] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v: e[u]) {
if (d[v] >= 0) continue;
d[v] = d[u] + 1, q.push(v);
}
}
return d;
};
auto d1 = bfs(1);
int p = max_element(d1.begin(), d1.end()) - d1.begin();
auto d2 = bfs(p);
int q = max_element(d2.begin(), d2.end()) - d2.begin();
auto d3 = bfs(q);
int res = 0;
for (int i = 1; i <= n; i++)
res = max(res, max(d2[i], d3[i]) * k - d1[i] * c);
printf("%lld\n", res);
return;
}
int32_t main() {
for (int t = read(); t; t--)
solve();
return 0;
}
G1. Magic Triples (Easy Version)
对于每一个组数，\((a_i,a_j,a_k)\)如果枚举 出\(a_i\)，实际上就是\(a_i,a_ix,a_ix^2\)，这里\(x\)的取值范围是\(10^3\),实际上远远不到这么多。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
const int N = 1e6+5;
int cnt[N];
void solve() {
int n = read() , res = 0;
set<int> st;
for( int i = n , x ; i ; i -- )
x = read() , cnt[x] ++ , st.insert(x);
for( auto i : st ){
if( cnt[i] == 0 ) continue;
if( cnt[i] >= 3 ) res += cnt[i] * (cnt[i]-1) * (cnt[i]-2);
for( int j = 2 ; j * j * i <= *st.rbegin() ; j ++ ){
res += cnt[i] * cnt[i*j] * cnt[i*j*j];
}
}
for( auto i : st ) cnt[i] = 0;
printf("%lld\n" , res);
return;
}
int32_t main() {
for (int t = read(); t; t--)
solve();
return 0；
}
G2. Magic Triples (Hard Version)
考虑改变枚举方式，枚举\(a_j\)，则三元组就是\((\frac {a_j} b,a_j,a_jb)\)，考虑到\(b\)一定是\(a_j\)的因子，所以我们可以算出\(a_j\)的所有因子，但是计算因子是\(\sqrt {a_j}\)的。
我们考虑按照值域分治，当\(a_j<S\)时枚举因子，复杂度\(O(\sqrt S)\)，当\(a_j\ge S\)时，采取暴力枚举，复杂度\(O(\frac{10^9}{S})\)，计算可知当\(S=10^6\)时，两种情况的复杂度都是\(O(10^3)\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
const int S = 1e6;
vector<int> getFac(int x) {
vector<int> f;
for (int i = 1, t = sqrt(x); i <= t; i++){
if( x % i ) continue;
f.push_back(i);
if( i * i != x ) f.push_back(x/i);
}
return f;
}
void solve() {
int n = read(), res = 0;
map<int, int> cnt;
for (int i = 1, x; i <= n; i++)
x = read(), cnt[x]++;
for (auto [x, y]: cnt) {
res += y * (y - 1) * (y - 2);
if (x >= S) {
for( int i = 2 ; i * x <= cnt.rbegin()->first ; i ++ )
if( x % i == 0 && cnt.count(x/i) && cnt.count(x*i) )
res += cnt[x/i] * cnt[x*i] * y;
} else {
auto f = getFac(x);
for( auto i : f ){
if( i == 1 ) continue;
if( i * x > cnt.rbegin()->first) continue;
if( cnt.count(x/i) && cnt.count(x*i) )
res += cnt[x/i] * cnt[x*i] * y;
}
}
}
cout << res << "\n";
return;
}
int32_t main() {
for (int t = read(); t; t--)
solve();
return 0;
}