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;
}

本栏目推荐文章
• NSSCTF Round#16 Basic WriteUp
• Hey left 1 Codeforces Round 918 (Div. 4)
• vue3 获取循环的div的总宽度
• CodeForces 1312G Autocompletion
• Educational Codeforces Round 152 (Rated for Div. 2)
• codeforces 918 div4
• div滚动加载数据
• CF Beta Round 93-D.Fibonacci Sums-齐肯多夫分解、DP
• CodeForces 1329D Dreamoon Likes Strings
• CodeForces 1237H Balanced Reversals

Codeforces Round 867 Divcodeforces round 867 div codeforces round 867 a-c codeforces round 911 div codeforces round 887 div codeforces round 864 div codeforces round 863 div codeforces round 913 div codeforces round 915 div codeforces round 917 div codeforces round 912 div