乱搞及剪枝
rtrt
3月 14, 2025
归档于 2019-10-22 15:27
剪枝乱搞我觉得还是要总结一下的
乱搞
毛三琛
正解是乱搞及剪枝
随机化,用剪枝增多随机化次数
#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\n",ans);
}
View Code
小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>lenlen跑lenlen,否则跑满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\n",lis[i],i,(n-i)/len+maxn+1);
}
else ans=max(ans,maxn+1);
}
printf("%lld\n",ans);
}
View Code
贪心就是按照$b-a$从大到小排序,然后每次先取出a最大值,如果可以爬出就爬出,否则取出$b-a$继续爬
然而不对
2 999
100 1
900 800
会先选900 800,然后选100 1
显然不对
然后Lrefrain神跟我说贪心是对的,可以微扰证明,我没过就是我个傻逼写错了
他说对拍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\n",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;
}
View Code
剪枝
打扫卫生
打扫干净屋子再请客
最优性剪枝
if(nowcnt*nowcnt>f[i]) break;
毛三琛
剪枝比较显然,但没有见过,没有想到
r越大符合可能性越高,如果check(r)都不符合,那么就一定不符合直接continue,,check下一个
matrix
最优性剪枝,可行性剪枝
还有一种剪枝1 2 3 ,1 3 2 ,2 1 3都是一种方案,只枚举其中一种,
因为是矩阵实现起来比较麻烦,但可以用id实现
还有为了剪最优性的枝可以先sort贪心求出一种看似很优的解
1 void dfs(ll sum,ll qs){
2 // printf("sum=%lld\n",sum);
3 // printf("%lld\n",ans);
4 if(sum>=ans) return ;
5 if(check()){
6 ans=min(ans,sum);
7 // printf("ans=%lld\n",ans);
8 return ;
9 }
10 if(clock()>960000){
11 printf("%lld\n",ans);
12 exit(0);
13 }
14 for(ll k=qs;k<=n*m;k++){
15 ll i=tmp[k].x,j=tmp[k].y;
16 if(!vis[i][j]){
17 if(ok(i,j)){
18 // printf("enter %lld %lld\n",i,j);
19 vis[i][j]=1;
20 ll x=i,y=j,
21 yuan1=now[x-1<1?1:x-1][y],
22 yuan2=now[x+1>n?x:x+1][y],
23 yuan3=now[x][y-1<1?1:y-1],
24 yuan4=now[x][y+1>m?y:y+1],
25 yuan5=now[x][y];
26 now[x-1<1?1:x-1][y]=1;
27 now[x+1>n?x:x+1][y]=1;
28 now[x][y-1<1?1:y-1]=1;
29 now[x][y+1>m?y:y+1]=1;
30 now[x][y]=1;
31 dfs(sum+val[i][j],k+1);
32 // printf("hui %lld %lld\n",i,j);
33 vis[i][j]=0;
34 now[x-1<1?1:x-1][y]=yuan1;
35 now[x+1>n?x:x+1][y]=yuan2;
36 now[x][y-1<1?1:y-1]=yuan3;
37 now[x][y+1>m?y:y+1]=yuan4;
38 now[x][y]=yuan5;
39 }
40 }
41 }
42 }
View Code