Good Bye 2021: 2022 is NEAR

A. Integer Diversity

题目：

思路分析：

就是给你一个序列 通过改变数字的正负 可以得到最大不同数字的个数是多少 

代码分析：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long  ull;
inline int read() {
    int x=0,f=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
ll _gcd(ll m, ll n){return n == 0 ? m : _gcd(n, m%n);}
ll _lcm(ll m, ll n){return m*n / _gcd(m, n);}
ll pows(ll base, ll power,ll mod){ll result=1;while(power>0){if(power&1){result=result*base%mod;}power>>=1;base=(base*base)%mod;}return result;}
ll poww(ll base, ll power){ll result=1;while(power>0){if(power&1){result=result*base;}power>>=1;base=(base*base);}return result;}
void init(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);}
const int MAX=1e6+10;
int t;
bool cmp(int a,int b){return a>b;}
ll max(ll a,ll b){if(a>b)return a;else return b;}


void solve(){
    int n;cin>>n;
    int a[110];
    for(int i=0;i<=100;i++)a[i]=0;
    for(int i=0;i<n;i++) {int x;cin>>x;a[abs(x)]++;}int ans=0;
    if(a[0]!=0) ans++;
    for(int i=1;i<=100;i++) {
        if(a[i]>=2) ans+=2;
        else if(a[i]==1) ans++;
    }
    cout<<ans<<endl;
}
int main(){
    init();
    cin>>t;
    while(t--) solve();
//    solve();
    return 0;
}

B. Mirror in the String

题目：

思路分析：

就是从字符串的第一位找一小段字符串 然后镜像对称使其字典序最小

我们可以开头遍历如果遇到字符序不减则停止 然后镜像对称即可

代码实现：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long  ull;
inline int read() {
    int x=0,f=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
ll _gcd(ll m, ll n){return n == 0 ? m : _gcd(n, m%n);}
ll _lcm(ll m, ll n){return m*n / _gcd(m, n);}
ll pows(ll base, ll power,ll mod){ll result=1;while(power>0){if(power&1){result=result*base%mod;}power>>=1;base=(base*base)%mod;}return result;}
ll poww(ll base, ll power){ll result=1;while(power>0){if(power&1){result=result*base;}power>>=1;base=(base*base);}return result;}
void init(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);}
const int MAX=1e6+10;
int t;
bool cmp(int a,int b){return a>b;}
ll max(ll a,ll b){if(a>b)return a;else return b;}


void solve(){
    int n;cin>>n;
    string s;s="";cin>>s;s="z"+s;
    int ans=1;
    if(s[1]==s[2]) ans=1;
    else {for(int i=1;i<=n;i++){
        if((s[i]-'a')>(s[i-1]-'a')){
            ans=i-1;break;
        }
        else ans=i;
        
    }}
//    cout<<ans<<endl;
    for(int i=1;i<=ans;i++){
        cout<<s[i];
    }
    for(int i=ans;i>=1;i--){
        cout<<s[i];
    }
    cout<<endl;
}
int main(){
    init();
    cin>>t;
    while(t--) solve();
//    solve();
    return 0;
}

C. Representative Edges

题目：

思路分析：

题意就是给你一个数字序列 然后可以修改单个数字的值 来构造一个等差序列

找出最少的操作数

由于数据很小 我们可以枚举d  然后遍历得出最小的操作数就行 

代码实现：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long  ull;
inline int read() {
    int x=0,f=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
ll _gcd(ll m, ll n){return n == 0 ? m : _gcd(n, m%n);}
ll _lcm(ll m, ll n){return m*n / _gcd(m, n);}
ll pows(ll base, ll power,ll mod){ll result=1;while(power>0){if(power&1){result=result*base%mod;}power>>=1;base=(base*base)%mod;}return result;}
ll poww(ll base, ll power){ll result=1;while(power>0){if(power&1){result=result*base;}power>>=1;base=(base*base);}return result;}
void init(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);}
const int MAX=1e6+10;
int t;
bool cmp(int a,int b){return a>b;}
ll max(ll a,ll b){if(a>b)return a;else return b;}


void solve(){
    int n;cin>>n;
    int a[110];
    for(int i=0;i<n;i++){int x;cin>>x;a[i]=x;}
    int ans=0x3f3f3f3f;
    if(n<=2) {cout<<0<<endl;return;}
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            int num=n;
            double d=1.0*(a[j]-a[i])/(j-i);
            for(int z=0;z<n;z++){
                if(abs(a[z]-(a[i]+(z-i)*d))<=1e-10)
                    num--;
            }
            ans=min(ans,num);
        }
    }
    cout<<ans<<endl;
}
int main(){
    init();
    cin>>t;
    while(t--) solve();
//    solve();
    return 0;
}

D. Keep the Average High

题目：

思路分析：

题意就是从给出的数学序列里找出x个数字 然后这个x个数字的序列中 任意区间和都满足一个关系 区间元素不少于二个

我们可以1-n进行枚举 当前第i个数能否选中和前面的数有关系

dp[i][0/1][0/1] 表示第i位前一位和第i位的选择情况

状态转移方程看代码吧！

代码实现：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long  ull;
inline int read() {
    int x=0,f=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
ll _gcd(ll m, ll n){return n == 0 ? m : _gcd(n, m%n);}
ll _lcm(ll m, ll n){return m*n / _gcd(m, n);}
ll pows(ll base, ll power,ll mod){ll result=1;while(power>0){if(power&1){result=result*base%mod;}power>>=1;base=(base*base)%mod;}return result;}
ll poww(ll base, ll power){ll result=1;while(power>0){if(power&1){result=result*base;}power>>=1;base=(base*base);}return result;}
void init(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);}
const int MAX=2e5+10;
int t;
bool cmp(int a,int b){return a>b;}
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll min(ll a,ll b){if(a>b)return b;else return a;}


void solve(){
    int a[MAX];int n;cin>>n;int dp[50005][2][2];
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++){cin>>a[i];}int k;cin>>k;
    for(int i=1;i<=n;i++) a[i]-=k;
    dp[1][0][1]=1;
    if(n==1) {cout<<1<<endl;return;}
    for(int i=2;i<=n;i++){
        dp[i][0][0]=max(dp[i-1][1][0],dp[i-1][0][0]);
        dp[i][0][1]=max(dp[i-1][0][0],dp[i-1][1][0])+1;
        dp[i][1][0]=max(dp[i-1][1][1],dp[i-1][0][1]);
        //1 1
        if(a[i]+a[i-1]>=0){
            dp[i][1][1]=dp[i-1][0][1]+1;
            if(a[i-2]+a[i-1]+a[i]>=0){
                dp[i][1][1]=max(dp[i][1][1],dp[i-1][1][1]+1);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<2;j++){
            for(int z=0;z<2;z++){
                ans=max(ans,dp[i][j][z]);
            }
        }
    }
    cout<<ans<<endl;
}
int main(){
    init();
    cin>>t;
    while(t--) solve();
//    solve();
    return 0;
}

E. Lexicographically Small Enough

题目：

思路分析：

给出二个字符串 s1 s2 我们可以交换相邻二个字符 要让s1调整到字典序严格小于s2的最少操作数

首先用最少操作次数使得s[i]<t[i]，并更新答案，但并不真的执行该操作。然后用最少操作次数使得s[i]==t[i]，这次操作需要执行。如果没有合法字符使得s[i]==t[i]，则退出循环。每轮操作都需要将一个连续子串右移一位。等价地，我们也可以把该子串后的后缀子串向前移动一位。记pos[i]为s[i]移动后的位置，上述操作等价于对后缀的pos[]同时减1，可以用树状数组维护，转化为单点修改，前缀求和的问题

代码实现：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long  ull;
inline int read() {
    int x=0,f=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
ll _gcd(ll m, ll n){return n == 0 ? m : _gcd(n, m%n);}
ll _lcm(ll m, ll n){return m*n / _gcd(m, n);}
ll pows(ll base, ll power,ll mod){ll result=1;while(power>0){if(power&1){result=result*base%mod;}power>>=1;base=(base*base)%mod;}return result;}
ll poww(ll base, ll power){ll result=1;while(power>0){if(power&1){result=result*base;}power>>=1;base=(base*base);}return result;}
void init(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);}
const int MAX=2e5+10;
int t;
bool cmp(int a,int b){return a>b;}
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll min(ll a,ll b){if(a>b)return b;else return a;}

int n,sum[MAX];
queue<int>qu[30];
string s1,s2;
void add(int x,int d){for(int i=x;i<=n;i+=(i&(-i))){sum[i]+=d;}}
int get_sum(int x){
    int ans=0;
    for(int i=x;i;i-=(i&(-i))){ans+=sum[i];}
    return ans;
}
void updata(ll &x,ll y){
    if(x==-1) x=y;
    else x=min(x,y);
}
void solve(){
    cin>>n;cin>>s1;cin>>s2;s1=" "+s1;s2=" "+s2;
    for(int i=0;i<=25;i++) {while(!qu[i].empty()) qu[i].pop();}
    for(int i=1;i<=n;i++){qu[s1[i]-'a'].push(i);sum[i]=0;}
    for(int i=1;i<=n;i++){add(i,1);}
    ll ans=-1;ll ans2=0;
    for(int i=1;i<=n;i++){
        int num=n+1;int mx=s2[i]-'a';
        for(int j=0;j<mx;j++){
            if(!qu[j].empty()){
                int k=qu[j].front();
                num=min(num,get_sum(k-1));
            }
        }
        if(num<n+1) updata(ans,num+ans2);
        if(!qu[mx].empty()){
            int k=qu[mx].front();qu[mx].pop();
            ans2+=get_sum(k-1);
            add(k,-1);
        }
        else break;
    }
    printf("%lld\n",ans);

}
int main(){
    init();
    cin>>t;
    while(t--) solve();
//    solve();
    return 0;
}