Edu 145 A~D

A. Garland

将情况按照相同的数字的个数进行分类讨论即可。

如1113 相同数字数最大为3 对应的答案为6

B. Points on Plane

通过画图和观察数据,可以发现答案等于sqrt(n)向上取整再减1

值得注意的是浮点数会损失精度，保险起见，要用long double和sqrtl

或者使用二分

C. Sum on Subarrays

思维题，这类题目往往需要通过尝试，画图，模拟样例等找出一些性质

然后将这些性质组合起来，得出答案

写这类题目的关键就是要多尝试，不要心急

本题我们可以发现如果在数组的末尾放置合适的正数可以增加n个正区间，接着在n-1的位置放，又可以增加n-1个正区间。

我们就以这样的方式减少k，直到某个位置i使得k<i，这时我们就在k位置放，k+1位置放一个绝对值大于k位置正数的负数。

通过这种方式我们可以构造出所有的k

递归写法

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;

void fun(vector<int>&ans,int n,int k){
    if(!k){
        for(int i=0;i<n;i++)ans[i]=-1;
        return;
    }
    if(k>=n){
        ans[n-1]=400;
        fun(ans,n-1,k-n);
    }else{
        ans[k-1]=100;
        ans[k]=-200;
        for(int i=k+1;i<n;i++)ans[i]=-1;
        fun(ans,k-1,0);
    }
}

void solve(){
    int n,k;
    cin>>n>>k;
    vector<int>ans(n);
    fun(ans,n,k);
    for(int i=0;i<n;i++)cout<<ans[i]<<' ';
    cout<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        solve();
    }   
    return 0;
}

1809D - Binary String Sorting
最终状态一定是左边全为0，右边全为1

根据代价，我们一定是保证总操作次数最少的情况下，尽量多使用第一个操作

如果只使用交换，需要交换的次数就等于逆序对的数量

可以证明(无论是01串还是一般的串)：如果逆序对的数量大于等于2，那么一定存在一个数构成了2个及以上个数的逆序对，那么我们就可以通过一次删除替换2次以上的交换

所以使用操作一的次数一定小于等于1

这样我们就可以可以枚举断点，断点左右为10，就使用操作一，其余全部使用操作二，否则全部使用操作二

对所有断点的结果取个min即可

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;

const long long C=1e12;

void solve(){
    string s;
    cin>>s;
    s='?'+s;
    int n=s.size()-1;
    vector<int>cnt0(n+2),cnt1(n+2);
    for(int i=1;i<=n;i++)cnt1[i]=cnt1[i-1]+(s[i]=='1');
    for(int i=n;i;i--)cnt0[i]=cnt0[i+1]+(s[i]=='0');
    LL ans=1e18;
    //枚举断点 注意有n+1个点
    for(int i=0;i<=n;i++){
        LL res=0;
        if(s[i]=='1'&&s[i+1]=='0'){
            res+=C;
            res+=(cnt1[i-1]+cnt0[i+2])*(C+1);
        }else{
            res+=(cnt1[i]+cnt0[i+1])*(C+1);
        }
        ans=min(ans,res);
    }
    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}