https://ac.nowcoder.com/acm/contest/95942#description

A

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int, int>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define maxn (int)2e5+5//*****************************************//
int a[maxn],dp[maxn];
void solve()
{
    int n,i;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    dp[0]=0;
    for(i=1;i<=n+1;i++)
        dp[i]=INF;
    for(i=1;i<=n;i++)
    {
        if(i>=a[i])
        dp[i]=min(dp[i],dp[i-a[i]]+1);//尾  
        if(i+a[i]<=n+1)
        dp[i+a[i]-1]=min(dp[i+a[i]-1],dp[i-1]+1); //头
    }         
    if(dp[n]==INF)
        cout<<-1<<endl;
    else
        cout<<dp[n]<<endl;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    solve();
    return 0;
} 

E
我们每次可以选择区间[1,i]进行翻转，要使得序列最后有序首先我们必须将有序的部分放到后面，因为区间[1,i]操作会使前面的部分翻转，导致原有的有序性被破坏，所以我虑先把序列[n−2,⋯,3,2,1] 这种，所以我们直接循环1∼n找对应数的下标，将其先翻转到第一个，然后再翻转区间[1,n−i+1]把这个数字放在后面有序部分，这样子接下来的操作不会影响到后面的有序部分，最进行一次区间 [1,n] 翻转即可。

# include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
#define int long long
int n;
const int N=2e3+10;
int p[N];
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
     cin>>n;
     for(int i=1;i<=n;i++)
         cin>>p[i];
    vector<int>v;
    int ans=0;
     for(int i=n;i>=1;i--)
     {
     if(i==p[i])
     continue;
         ans+=2;
     int x=p[i]; 
     v.push_back(i);
     v.push_back(x);   
     }
    cout<<ans<<endl;
    for(auto x:v)
    cout<<x<<" ";
    cout<<endl;
    }
}

G
对于长度为x的序列我们最大可以将每个数操作为x。排序后对于每个数依次枚举即可

#include <bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
    int n; cin>>n;
    vector<int> a(n + 1);
    for(int i = 1;i<=n;i++) cin>>a[i];
    sort(a.begin() + 1,a.end());
    vector<int> suf(n + 3);
    suf[n] = a[n];
    for(int i = n-1;i;i--) suf[i] = suf[i+1] + a[i];
    int ans = 0;
    for(int i = 0;i<=n;i++){
        ans = max(ans,i*i+suf[i+1]);
        // cout<<i*i<<" "<<suf[i+1]<<endl;
    }
    cout<<ans<<endl;
}

signed main(){
    int T; cin>>T; while(T--)
    solve();
    return 0;
}

I

# include <bits/stdc++.h>
using namespace std;
#define int long long 
int n,k;
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
    string s;
    cin>>n>>k;
    cin>>s;
    s=" "+s;
    int ti=0;
    while(k>=1&&k<=n)
    {
    if(s[k]=='>')
    s[k]='<',k=k+1;
    else if(s[k]=='<')
    s[k]='>',k=k-1;
    ti++;
    }
    cout<<ti;
    cout<<endl;
    }
}

K
段首和段尾都可以代表段长度,dp[i]代表1~i的最大段数，首先我们对 dp 数组进行全部初始化成无穷大，对于每一个位置 i,只要 i-a[i]和i+a[i]-1没有超出边界,对于每一个位置i可以从i位置往左a[i]个位置往右a[i]个位置转移而来，所以动态规划状态转移方程为 dp[i]=min(dp[i],dp[i-a[i]]+1)/dp[i+a[i]-1]=min(dp[i+a[i]-1],dp[i-1]+1) ，最后我们判断 dp[n] 即（1~n）是否被更新过，如果是无穷大就是无解输出 -1，否则就是有解，直接输出 dp[n] 的值即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn (int)2e5+5
int a[maxn],dp[maxn];
void solve()
{
    int n,i;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    dp[0]=0;
    for(i=1;i<=n+1;i++)
        dp[i]=1e18;
    for(i=1;i<=n;i++)
    {
        if(i>=a[i])
        dp[i]=min(dp[i],dp[i-a[i]]+1);//尾  
        if(i+a[i]<=n+1)
        dp[i+a[i]-1]=min(dp[i+a[i]-1],dp[i-1]+1); //头
    }         
    if(dp[n]==1e18)
        cout<<-1<<endl;
    else
        cout<<dp[n]<<endl;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    solve();
    return 0;
} 

N

# include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N=2e5+10;
int a[N],n;
signed main()
{

    int T;
    cin>>T;
    while(T--)
    {
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
        int mx=1e18;
    for(int i=n-1;i>=1;i--)
    {
    mx=min(mx,a[i]);
    }   
    cout<<mx+a[n]<<endl;    
    }
}