题解视频正在录制中

A - Candies

二进制

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int T,N;
int main(){
    // debug;
    ios;
    cin>>T;
    while(T--){
        cin>>N;
        int cur = 3,ans = -1;
        for(int i = 2;i<=31;i++){
            if(N%cur == 0){
                ans = N/cur;
                break;
            }
            cur = cur<<1|1;
        }
        cout<<ans<<'\n';
    }



    return 0;
}

B - Balanced Array

思维+构造

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int T,N;
int main(){
    // debug;
    ios;
    cin>>T;
    while(T--){
        cin>>N;
        if((N/2)%2 == 1) cout<<"NO\n";
        else{
            cout<<"YES\n";
            int cur = 2;
            for(int i = 1;i<=N/2;i++){
                cout<<cur<<" ";
                cur +=2;
            }
            cur = 1;
            for(int i = 1;i<=N/2;i++){
                if(i<N/2) cout<<cur<<" ";
                else cout<<cur + N/2<<'\n';
                cur +=2;
            }
        }
    }



    return 0;
}

C - Alternating Subsequence

dp

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int T,N;
int arr[maxn];
int dp[maxn];
int main(){
    // debug;
    ios;
    cin>>T;
    while(T--){
        cin>>N;
        for(int i = 1;i<=N;i++) cin>>arr[i];
        dp[1] = arr[1];
        int tail = 1;
        for(int i =2;i<=N;i++){
            if((ll)arr[i] * dp[tail] < 0) dp[++tail] = arr[i];
            else dp[tail] = max(dp[tail],arr[i]);
        }
        ll sum = 0;
        for(int i = 1;i<=tail;i++) sum += dp[i];
        cout<<sum<<'\n';
    }



    return 0;
}

D - Constant Palindrome Sum

差分

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int T,N,K;
int arr[maxn],ca[maxn],equ[maxn];

void init_ca(){
    memset(ca,0,4*2*K+10);
    memset(equ,0,4*2*K+10);
    for(int i = 1;i<=N/2;i++){
        int &a = arr[i],&b = arr[N-i+1];
        equ[a+b] ++;
        ca[min(a,b)+1] += 1;
        ca[max(a,b)+K+1] -=1;
    }
    for(int i = 1;i<=2*K;i++) ca[i] += ca[i-1];
}
int sovle(){
    int ans = 2e9;
    for(int i = 2;i<=2*K;i++){
        int cnt2 = (N/2 - ca[i])*2;
        int cnt1 = ca[i] - equ[i];
        ans = min(ans,cnt1 + cnt2);
    }
    return ans;
}
int main(){
    // debug;
    ios;
    cin>>T;
    while(T--){
        cin>>N>>K;
        for(int i = 1;i<=N;i++) cin>>arr[i];
        init_ca();
        cout<<sovle()<<'\n';
    }
    return 0;
}

E - Weights Distributing

BFS+思维

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5+10;
using namespace std;

int T,N,M,a,b,c;
ll edg[maxn];
int h[maxn],e[maxn*2],ne[maxn*2],idx;
int disa[maxn],disb[maxn],disc[maxn];bool vis[maxn];
queue<int> q;
void add(int a,int b){
    e[++idx] = b,ne[idx] = h[a],h[a]= idx;
}
void bfs(int u,int dis[]){
    memset(vis,false,4*N+5);
    while(q.size()) q.pop();
    q.push(u);
    vis[u] = true;
    dis[u] = 0;
    while(q.size()){
        int u = q.front();q.pop();
        for(int i = h[u];i;i = ne[i]){
            int v = e[i];
            if(vis[v]) continue;
            vis[v] = true;
            dis[v] = dis[u] + 1;
            q.push(v);
        }
    }
}

ll solve(){
    sort(edg+1,edg+M+1);
    for(int i = 1;i<=M;i++) edg[i] += edg[i-1];
    bfs(a,disa);bfs(b,disb);bfs(c,disc);
    ll ans = 1e18;
    for(int i = 1;i<=N;i++) {
        int da = disa[i],db = disb[i],dc = disc[i];
        if(da + db + dc > M) continue;
        ans = min(ans,2*edg[db] + (edg[da+db+dc] - edg[db]));
    }
    return ans;
}


int main(){
    // debug;
    ios;
    cin>>T;
    while(T--){
        cin>>N>>M>>a>>b>>c;
        memset(disa,0,4*N+5);
        memset(disb,0,4*N+5);
        memset(disc,0,4*N+5);
        memset(h,0,4*N+5);
        for(int i = 1;i<=M;i++) cin>>edg[i];
        idx = 0;
        for(int i = 1;i<=M;i++){
            int a,b;cin>>a>>b;
            add(a,b);
            add(b,a);
        }
        cout<<solve()<<'\n';
    }



    return 0;
}

F - Restore the Permutation by Sorted Segments

思维+构造+答案验证

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int T,N;
set<int> st[205];
vector<int> adj[205];
int ans[205],order[205];
void init(){
    for(int i = 1;i<=200;i++) st[i].clear();
    memset(ans,0,sizeof ans);
    for(int i = 1;i<=200;i++) adj[i].clear();
}
bool dfs2(int u,int pos,set<int> st[]){
    if(pos == N+1) return true;
    if(u == -1 && pos<=N) return false;
    ans[pos] = u;
    int nx_u = -1;
    for(int i = 1;i<=N-1;i++){
        st[i].erase(u);
        if(st[i].size() == 1) nx_u = *(st[i].begin());
    }    
    return dfs2(nx_u,pos+1,st);
}
bool cmp(int &a,int &b){
    return order[a] < order[b];
}
bool judge(){
    for(int i = 1;i<=N;i++) order[ans[i]] = i;
    for(int i = 1;i<=N-1;i++){
        sort(adj[i].begin(),adj[i].end(),cmp);
        for(int j = 1;j<adj[i].size();j++){
            int &l = adj[i][j-1],&r = adj[i][j];
            if(order[r] - order[l] != 1) return false;
        }
    }
    return true;
}
void solve(){
    for(int i = 1;i<=N;i++){
        set<int> tmp[205];
        for(int j = 1;j<=200;j++){
            for(auto v:st[j]){
                tmp[j].insert(v);
            }
        }
        if(dfs2(i,1,tmp) && judge()) break;
    }
    for(int i = 1;i<=N;i++) cout<<ans[i]<<" ";cout<<'\n';
}

int main(){
    // debug;
    ios;
    cin>>T;
    while(T--){
        init();
        cin>>N;
        for(int i = 1;i<=N-1;i++){
            int k;cin>>k;
            while(k--){
                int cur;cin>>cur;
                st[i].insert(cur);
                adj[i].push_back(cur);
            }
        }
        solve();
    }



    return 0;
}