乱搞及剪枝

剪枝乱搞我觉得还是要总结一下的

乱搞

毛三琛

正解是乱搞及剪枝

随机化,用剪枝增多随机化次数

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define A 44444
ll n,mod,k,ans,maxx;
ll a[A],b[A],p[A],q[A];
ll random(ll x){
    return 1ll*rand()%x;
}
ll check(ll mid){
    ll cnt=1,sum=0;
    for(ll i=1;i<=n;i++){
        if(sum+b[i]<=mid){
            sum+=b[i];
        }
        else {
            sum=b[i];
            cnt++;
        }
        if(cnt>k) return 0;
    }
    return 1;
}
void work(){
    ll l=maxx,r=ans;
    ll nowans=0x7fffffff;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid)){
            r=mid-1;
            nowans=mid;
        }
        else l=mid+1;
//        if(l>ans) return ;
    }
    ans=min(ans,nowans);
}
int main(){
    ans=0;
    srand((unsigned)time(0));
    double st=clock();
    scanf("%d%d%d",&n,&mod,&k);
    for(int i=0;i<mod;++i)p[i]=i;
    random_shuffle(p+0,p+mod);
    random_shuffle(p+0,p+mod);
    random_shuffle(p+0,p+mod);
    random_shuffle(p+0,p+mod);
    random_shuffle(p+0,p+mod);    
    for(ll i=1;i<=n;i++)
        scanf("%d",&a[i]),ans+=a[i],maxx=max(a[i],maxx);
    for(int kx=1;kx<=mod;++kx){
        ll i=p[kx-1];
        maxx=0;
        double ed=clock();
        if((ed-st)/1e6>0.99) break;
        for(ll j=1;j<=n;j++)
            b[j]=(a[j]+i)%mod,maxx=max(maxx,b[j]);
        if(!check(ans)) continue ;
        work();
        
    }
    printf("%d
",ans);
}

小P的生成树

神仙生成树

类似最小方差生成树

然而可以用这种方法乱搞

    friend bool operator < (const node &c,const node &d){
        return c.a*k1+c.b*k2>d.a*k1+d.b*k2;
    }

        k1=random(20000)-10000,k2=random(20000)-10000;
        init();
        sort(edg+1,edg+m+1);

SKYH的最短路

有一些边权不确定,但不确定的边权全部相等,每个点能否在最短路上

随机化,卡时==AC

注意判断每个点能否在最短路

可能有多条最短路径

vector存一下跑拓扑排序

最长不下降子序列

$1e12$,有循环节

循环接长度150

正解太神了,我不会,神仙矩阵快速幂优化

怎么乱搞?

找出len*len循环节即可

若n>len*len跑len*len,否则跑满n

为什么是len*len

这样能取遍循环节每一个元素

即使出现1 2 3 4 5 6 这样循环节,我们也可以这样取出第一个循环节1,第二个循环节2,,,,,,,,,,,依次类推

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,t,a,b,c,d,kuku,maxn;
struct node{
    ll l,r,val;
}tr[8222222];
void built(ll x,ll l,ll r){
    tr[x].l=l,tr[x].r=r;
    if(l==r){
        tr[x].val=0;
        return ;
    }
    ll mid=(l+r)>>1;
    built(x<<1,l,mid);
    built(x<<1|1,mid+1,r);
}
void change(ll x,ll pla,ll val){
    if(tr[x].l==tr[x].r){
        tr[x].val=val;
        return ;
    }
    ll mid=(tr[x].l+tr[x].r)>>1;
    if(mid>=pla)change(x<<1,pla,val);
    else change(x<<1|1,pla,val);
    tr[x].val=max(tr[x<<1].val,tr[x<<1|1].val);
}
void ask(ll x,ll l,ll r){
    if(tr[x].l>=l&&tr[x].r<=r){
        maxn=max(maxn,tr[x].val);
        return ;
    }
    ll mid=(tr[x].l+tr[x].r)>>1;
    if(mid>=l) ask(x<<1,l,r);
    if(mid<r)  ask(x<<1|1,l,r);
}
ll top;
ll lis[22222222],vis[22222222];
ll cnt=0,len,tot,lit,st,ans=0;
int main(){
    scanf("%lld",&n);
    scanf("%lld%lld%lld%lld%lld",&t,&a,&b,&c,&d);
    ll mx=t;
    for(ll i=1;i<=n;i++){
        if(vis[lis[++tot]=t]){st=vis[lis[tot]];len=i-vis[t];lit=i-1;break;}
        vis[t]=i;
        t=(t*t*a+b*t+c)%d;
        mx=max(mx,t);
    }
    if(!st) st=n+1;
    lit=min(n,lit+len*len);
    for(ll i=st+len;i<=lit;i++){
        lis[i]=lis[i-len];
        tot++;
    }
    built(1,0,mx);
    for(ll i=1;i<=tot;i++){
        maxn=0;
        ask(1,0,lis[i]);
        change(1,lis[i],maxn+1);
        if(i>=st){
            ans=max(ans,(n-i)/len+maxn+1);
//            printf("a[i]=%lld i=%lld n-i/len+maxn+1=%lld
",lis[i],i,(n-i)/len+maxn+1);
        }
        else ans=max(ans,maxn+1);
    }
    printf("%lld
",ans);
}

 

贪心就是按照$b-a$从大到小排序,然后每次先取出a最大值,如果可以爬出就爬出,否则取出$b-a$继续爬

然而不对

2 999

100 1

900 800

会先选900 800,然后选100 1

显然不对

然后SBLrefrain跟我BB说贪心是对的,可以微扰证明,我没过就是我个傻逼写错了

他当时那种自大的神情我根本模仿不出来

他说对拍700000组都没错,这个贪心一定是对的

第二天我两组hack数据他都没过

正解很神

所以枚举角度无脑AC

/*
2 999
900 800
99 0
2 
2




2but-1
6 8
4 2
3 5
3 4
2 4
6 3
1 1
1
3
2
2
3
1
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 111111
ll vis[A],c[A];
ll ans=0x3f3f3f3f;
ll n,l,zong,now,wwb;
struct node{
    ll a,b,id;
    node(){}
    node(const ll &c,const ll &d,const ll &e){a=c,b=d,id=e;}
    friend bool operator < (const node &c,const node &d){
        return c.a<d.a;
    }
}s[A];
priority_queue<node> q;
inline ll cmp1(const node &x,const node &y){
    return ((x.a-x.b)==(y.a-y.b))?(x.a<y.a):(x.a-x.b>y.a-y.b);
}
double delta=0;
inline ll cmp5(const node &x,const node &y){
    return 1.0*x.a*delta-x.b>1.0*y.a*delta-y.b;
}
ll work(){
    memset(vis,0,sizeof(vis));
    now=0,wwb=0;
    while(!q.empty()) q.pop();
    for(ll i=1;i<=n;i++)
        q.push(s[i]);
    for(ll i=1;i<=n;i++){
        while(vis[q.top().id]) q.pop();
        if(now+q.top().a>=l) return i;
        vis[s[i].id]=1;
        now+=s[i].a-s[i].b;wwb+=c[i];
        if(now<=wwb) return 0x3f3f3f3f;
    }
}
void print(){
    if(ans==0x3f3f3f3f) puts("-1");
    else printf("%lld
",ans);
}
int main(){
    freopen("climb.in","r",stdin);
    freopen("climb.out","w",stdout);
    scanf("%lld%lld",&n,&l);
    for(ll i=1;i<=n;i++){
        scanf("%lld%lld",&s[i].a,&s[i].b);
        s[i].id=i;
    }
    for(ll i=1;i<=n;i++)
        scanf("%lld",&c[i]);
    for(double i=0;i<=1;i+=0.1){
        if(clock()>1800000){
            print();
            return 0;
        }
        delta=i;
        sort(s+1,s+n+1,cmp5);
        ans=min(work(),ans);
        if(clock()>1800000){
            print();
            return 0;
        }
    }
    print();
    return 0;
}

剪枝

打扫卫生

打扫干净屋子再请客

最优性剪枝

            if(nowcnt*nowcnt>f[i]) break;

毛三琛

剪枝比较显然,但没有见过,没有想到

r越大符合可能性越高,如果check(r)都不符合,那么就一定不符合直接continue,,check下一个

matrix

最优性剪枝,可行性剪枝

还有一种剪枝1 2 3 ,1 3 2 ,2 1 3都是一种方案,只枚举其中一种,

因为是矩阵实现起来比较麻烦,但可以用id实现

还有为了剪最优性的枝可以先sort贪心求出一种看似很优的解

void dfs(ll sum,ll qs){
//    printf("sum=%lld
",sum);
//    printf("%lld
",ans);
    if(sum>=ans) return ;
    if(check()){
        ans=min(ans,sum);
//        printf("ans=%lld
",ans);
        return ;
    }
    if(clock()>960000){
        printf("%lld
",ans);
        exit(0);
    }
    for(ll k=qs;k<=n*m;k++){
        ll i=tmp[k].x,j=tmp[k].y;
            if(!vis[i][j]){
                if(ok(i,j)){
//                    printf("enter %lld %lld
",i,j);
                    vis[i][j]=1;
                    ll x=i,y=j,
                    yuan1=now[x-1<1?1:x-1][y],
                    yuan2=now[x+1>n?x:x+1][y],
                    yuan3=now[x][y-1<1?1:y-1],
                    yuan4=now[x][y+1>m?y:y+1],
                    yuan5=now[x][y];
                    now[x-1<1?1:x-1][y]=1;
                    now[x+1>n?x:x+1][y]=1;
                    now[x][y-1<1?1:y-1]=1;
                    now[x][y+1>m?y:y+1]=1;
                    now[x][y]=1;
                    dfs(sum+val[i][j],k+1);
//                    printf("hui %lld %lld
",i,j);
                    vis[i][j]=0;
                    now[x-1<1?1:x-1][y]=yuan1;
                    now[x+1>n?x:x+1][y]=yuan2;
                    now[x][y-1<1?1:y-1]=yuan3;
                    now[x][y+1>m?y:y+1]=yuan4;
                    now[x][y]=yuan5;
                }
            }
    }
}