T1 斐波那契
一道找规律题，被我做成了贼难的题。
观察图片可知x=f[i-1]+j。（j为x的父亲）且j<=f[i-1]，然后就二分找父亲没了。
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std; 4 const int mod=233; 5 ll f[61]; 6 struct Hush{ 7 int head[233],nxt[61],cnt; 8 ll to[61]; 9 void insert(ll x) 10 { 11 int k=x%mod; 12 to[++cnt]=x; 13 nxt[cnt]=head[k]; 14 head[k]=cnt; 15 return ; 16 } 17 bool find(ll x) 18 { 19 int k=x%mod; 20 for(int i=head[k];i;i=nxt[i])if(to[i]==x)return 1; 21 return 0; 22 } 23 void clear() 24 { 25 memset(head,0,sizeof(head)); 26 cnt=0; 27 } 28 }H; 29 ll Getlca(ll a,ll b) 30 { 31 if(a>b)swap(a,b); 32 H.clear(); 33 H.insert(a); 34 while(a!=1) 35 { 36 ll fa=lower_bound(f+1,f+61,a)-f; 37 fa=a-f[fa-1]; 38 H.insert(fa); 39 a=fa; 40 } 41 if(H.find(b))return b; 42 while(b!=1) 43 { 44 ll fb=lower_bound(f+1,f+61,b)-f; 45 fb=b-f[fb-1]; 46 if(H.find(fb))return fb; 47 b=fb; 48 } 49 } 50 int main() 51 { 52 f[0]=0;f[1]=1; 53 for(int i=2;i<=60;i++)f[i]=f[i-1]+f[i-2]; 54 int m; 55 scanf("%d",&m); 56 for(int i=1;i<=m;i++) 57 { 58 ll a,b; 59 scanf("%lld%lld",&a,&b); 60 printf("%lld\n",Getlca(a,b)); 61 } 62 return 0; 63 }
T2 水题不说了
T3 分组
一道好题。
k=1：
以前做过一道菜肴制作，然后就可以知道：区间越往后放，就越靠前。然后就维护最长的区间即可
k=2：
用扩展域并查集，直接维护，特判很恶心。
1 #include<bits/stdc++.h>
2 #define MAXN 333333
3 using namespace std; 4 int nxt[MAXN],a[MAXN],pf[MAXN],dr[MAXN],f[MAXN]; 5 bool vst[MAXN]; 6 vector<int>ans,cl; 7 inline int find(int x) 8 { 9 return f[x]==x?x:f[x]=find(f[x]); 10 } 11 inline void merge(int x,int y) 12 { 13 int fa=find(x),fb=find(y); 14 f[fa]=fb; 15 return ; 16 } 17 void bcj_clear(int l,int r) 18 { 19 for(int i=l;i<=r;i++)f[a[i]]=a[i],vst[a[i]]=0,dr[a[i]]=0; 20 cl.clear(); 21 return ; 22 } 23 int main() 24 { 25 int n,k,maxa=0; 26 scanf("%d%d",&n,&k); 27 for(int i=1;i<=n;i++) 28 { 29 scanf("%d",&a[i]); 30 maxa=max(maxa,a[i]); 31 } 32 int ed=n; 33 for(int i=0;i<=1024;i++)pf[i]=i*i; 34 if(k==1) 35 { 36 for(int i=n;i>=1;i--) 37 { 38 bool ok=1; 39 for(int j=sqrt(maxa*2);j>=2&&pf[j]>=a[i];j--) 40 if(vst[pf[j]-a[i]]){ok=0;break;} 41 if(!ok){ 42 ed=i; 43 for(int k=0;k<cl.size();k++) 44 vst[cl[k]]=0; 45 cl.clear(); 46 ans.push_back(i); 47 } 48 vst[a[i]]=1; 49 cl.push_back(a[i]); 50 } 51 if(!ans.size())printf("1\n"); 52 cout<<ans.size()+1<<endl; 53 for(int i=ans.size()-1;i>=0;i--) 54 printf("%d ",ans[i]); 55 return 0; 56 } 57 else
58 { 59 int last=n; 60 for(int i=1;i<=maxa*2;i++)f[i]=i; 61 for(int i=n;i>=1;i--) 62 { 63 bool ok=1; 64 for(int j=sqrt(maxa*2);j>=2&&pf[j]>=a[i];j--) 65 { 66 if(vst[pf[j]-a[i]]&&!vst[a[i]]) 67 { 68 // cout<<i<<"---"<<endl;
69 int now=pf[j]-a[i]; 70 if(find(a[i])==find(now)){ok=0;break;} 71 if(!dr[now])dr[now]=a[i]; 72 else if(dr[now]!=now)merge(dr[now],a[i]); 73 else {ok=0;break;} 74 if(!dr[a[i]])dr[a[i]]=now; 75 else if(dr[a[i]]!=a[i])merge(dr[a[i]],now); 76 else {ok=0;break;} 77 } 78 else if(vst[pf[j]-a[i]]&&a[i]==pf[j]-a[i]) 79 { 80 // cout<<i<<' '<<dr[a[i]]<<endl;
81 if(dr[a[i]]){ok=0;break;} 82 else dr[a[i]]=a[i]; 83 //cout<<i<<' '<<a[i]<<")S"<<endl;
84 } 85 } 86 if(!ok){ 87 ed=i; 88 bcj_clear(i,last); 89 last=i; 90 ans.push_back(i); 91 } 92 vst[a[i]]=1; 93 cl.push_back(a[i]); 94 } 95 if(!ans.size()){printf("1\n");return 0;} 96 cout<<ans.size()+1<<endl; 97 for(int i=ans.size()-1;i>=0;i--) 98 printf("%d ",ans[i]); 99 return 0; 100 } 101 }
主要反思一下：
考试策略不好，时间分配不合理，难度评估sb 认为T1最难，T3最水？？？？？？？？？
端正心态，不要去刚题，但也不要轻易放弃（暴力还是要打的）