1355C - Count Triangles，2021CCPC桂林 C，D

14天阅读挑战赛

1355C - Count Triangles 

枚举i=x+y的值，i一定是要>=c+1的，那么z的取值就是min(d+1,i)-c,再去看x和y的值，

x属于[a,b],y属于[b,c],a+b<=i<=b+c--->i-b>=a,i-c<=b,那么对于每一个y，x的取值就是max(i-c,a),min(i-b,b),那么x可取的数就是min(i-b,b)-max(i-c,a)+1,然后将x和z的个数相乘就是这个i对答案的贡献

C. Count Triangles(组合数学)_Harris-H的博客-CSDN博客

#include 
using namespace std;
#define endl '\n'
#define int long long
const int N = 2e5+5;
//const int mod=1e9+7;
const int inf=1e18;
const double eps=1e-8;
const double pi=acos(-1);
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
//int getinv(int a){return qpow(a,mod-2);}
int Lcm(int a,int b){return a*b/__gcd(a,b);}
int a,b,c,d;
signed main()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    cin>>a>>b>>c>>d;
    int ans=0;
    for(int i=max(a+b,c+1);i<=b+c;i++)
    {
        ans+=(min(d+1,i)-c)*(min(i-b,b)-max(i-c,a)+1);
    }
    cout<
    return 0;
}
//

G - Occupy the Cities 二分

二分答案，check函数就是看看第i个零距离两侧的1是否小于等于x，不然就让右边的1向左感染，然后标记右边的1，表示这个右边的1如果作为左边的1的话已经被用了，不可以再向右感染了；否则可以向右感染；

#include 
using namespace std;
#define endl '\n'
#define int long long
const int N = 2e6+5;
//const int mod=1e9+7;
const int inf=1e18;
const double eps=1e-8;
const double pi=acos(-1);
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
//int getinv(int a){return qpow(a,mod-2);}
int Lcm(int a,int b){return a*b/__gcd(a,b);}
int n,t,pre[N],suf[N],pos[N],vis[N];
char s[N];
bool check(int x)
{
    for(int i=1;i<=n;i++) pos[i]=i,vis[i]=0;
    pos[0]=-inf;pos[n+1]=inf;
    vis[0]=vis[n+1]=0;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='1') continue;
        int l=pre[i],r=suf[i];
        if(pos[l]==l&&!vis[l]) pos[l]=pos[l]+1;
        int minn=min(i-pos[l]+1,pos[r]-i+1);
        //cout<
        if(minn<=x) continue;
        int tmp=pos[r]-1;vis[r]=1;
        minn=min(i-pos[l]+1,tmp-i+1);
        if(minn>x) return 0;
    }
    return 1;
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    cin>>t;
    while(t--)
    {
        cin>>n;
        cin>>(s+1);
        for(int i=1;i<=n;i++) pre[i]=suf[i]=pos[i]=0;
        int last=0;
        for(int i=1;i<=n;i++)
        {
            pre[i]=last;
            if(s[i]=='1') last=i;
        }
        last=n+1;
        for(int i=n;i>=1;i--)
        {
            suf[i]=last;
            if(s[i]=='1') last=i;
        }
        pos[0]=-inf;pos[n+1]=inf;
        int l=0,r=n,ans=n;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(check(mid)) ans=mid,r=mid-1;
            else l=mid+1;
        }
        cout<
    }
    return 0;
}
//
/*
11
000100001000
*/

1474C - Array Destruction multiset

每次都要选数组里的最大值，因为不选的话以后就没机会选了，然后再找一个上一个最大值与该最大值的差就可以，因为第一个最大值所对应的差值是不确定的，那就去枚举，除最大值外所有的数，然后看看是否符合条件

C. Array Destruction(思维+树形结构+枚举)_小菜鸡加油的博客-CSDN博客

#include 
using namespace std;
#define endl '\n'
#define int long long
const int N = 2e6+5;
//const int mod=1e9+7;
const int inf=1e18;
const double eps=1e-8;
const double pi=acos(-1);
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
//int getinv(int a){return qpow(a,mod-2);}
int Lcm(int a,int b){return a*b/__gcd(a,b);}
int t,n,a[2005],m,flag;
multiset<int>s;
vectorint,int>>ans;
bool sol(int x)
{
    for(int i=1;i
    {
        int maxx=*prev(s.end());
        s.erase(s.find(maxx));
        if(s.find(x-maxx)!=s.end())
        {
            s.erase(s.find(x-maxx));
            ans.push_back({maxx,x-maxx});
            x=maxx;
        }
        else break;
    }
    return ans.size()==n;
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    cin>>t;
    while(t--)
    {
        cin>>n;
        m=2*n;flag=0;
        for(int i=1;i<=m;i++) cin>>a[i];
        sort(a+1,a+m+1);
        for(int i=1;i
        {
            s.clear();ans.clear();
            for(int j=1;j
            {
                if(j!=i) s.insert(a[j]);
            }
            ans.push_back({a[m],a[i]});
            if(sol(a[m])){flag=1;break;}
        }
        if(flag)
        {
            cout<<"YES\n";
            cout<0].first+ans[0].second<
            for(auto [x,y]:ans) cout<" "<
        }
        else cout<<"NO\n";
    }
    return 0;
}
//
/*
11
000100001000
*/

D - Assumption is All You Need 构造

大的数只能往右走，小的数只能往左走，每次交换较大的两个数，直到较大数回到正确的位置，然后次大数再继续走，这样会留出更多的机会给后面的数，也就是每次枚举大数往下走

D. Assumption is All You Need_chmpy的博客-CSDN博客

#include 
using namespace std;
#define endl '\n'
#define int long long
const int N = 3e5+5;
const int mod=1e9+7;
const int inf=1e18;
const double eps=1e-8;
const double pi=acos(-1);
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
//int getinv(int a){return qpow(a,mod-2);}
int Lcm(int a,int b){return a*b/__gcd(a,b);}
int t,n,a[2025],b[2035],posa[2035],posb[2035];
vectorint,int>>ans;
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    cin>>t;
    while(t--)
    {
        ans.clear();
        cin>>n;
        int flag=1;
        for(int i=1;i<=n;i++) cin>>a[i],posa[a[i]]=i;
        for(int i=1;i<=n;i++) cin>>b[i],posb[b[i]]=i;
        for(int i=n;i>=1;i--)
        {
            for(int j=i-1;j>=1;j--)
            {
                if(posa[j]>posa[i]&&posa[j]<=posb[i])
                {
                    ans.push_back({posa[i],posa[j]});
                    swap(a[posa[i]],a[posa[j]]);
                    swap(posa[i],posa[j]);
                }
            }
            if(posa[i]!=posb[i])
            {
                flag=0;break;
            }
        }
        if(!flag) cout<<"-1\n";
        else
        {
            cout<size()<
            for(auto [x,y]:ans) cout<" "<
        }
    }
    return 0;
}
//