7/24 训练日志

每日一题

D2. Chopping Carrots (Hard Version) 1.枚举极小值，其值存在上限，为数组a中最小的那个数，即为a[1]； 2.无法如D1一般枚举a[i]，数据范围改变，存在超时问题； 3.可改变思路：枚举p[i],范围是1~k。a[i]数组是单调不减的，根据极差值，可构造a[i]/p[i],使得大小存在递增关系； 4.通过枚举极差中的最小值，再枚举每一个p，再通过lower_bound查找数组a中的值； 5.若正好存在i*p==a[i]，则找到；若大于数组a中最大值，则跳出；

#include 
#define int long long
#define endl '\n'

using namespace std;
const int N=1e6+5;
int n,k,a[N];

signed main()
{
    int t;cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=1;i>a[i];
        int mn=a[1],mx=a[n],ans=1e9;
        for(int i=1;i=i)
                ans=min(ans,res-i);
        }
        couts;
        int a=0,b=0;
        for(int i=0;is;
        tl[0]=0,tr[0]=n;
        for(int i=1;i>l[i]>>r[i];
            tl[i]=tr[i-1]+1;
            tr[i]=tl[i]+(r[i]-l[i]+1)-1;
        }
        while(q--)
        {
            int x;cin>>x;
            for(int i=c;i>=1;i--)
                if(tl[i]>e[i].z;
    kruskal();
    while(q--)
    {
        int ans=0;
        int k;cin>>k;
        for(int i=1;i>tmp[i],tmp[i]^=lans;
        sort(tmp+1,tmp+k+1,cmp1);
        for(int i=2;i