LGB3642 二叉树的遍历
原题链接：二叉树的遍历
分析
至今没有理解遍历顺序……诶……是不是说什么我建一个东西，每次输一下……类似于什么l s lsls和r s rsrs分别为每一层的左儿子和右儿子……类似吧，那，还是看一下题解吧……
正解
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1000005;intn;intl[N],r[N];voiddfs1(intu){if(u==0)return;cout<<u<<" ";dfs1(l[u]);dfs1(r[u]);}voiddfs2(intu){if(u==0)return;dfs2(l[u]);cout<<u<<" ";dfs2(r[u]);}voiddfs3(intu){if(u==0)return;dfs3(l[u]);dfs3(r[u]);cout<<u<<" ";}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(inti=1;i<=n;i++)cin>>l[i]>>r[i];dfs1(1);cout<<"\n";dfs2(1);cout<<"\n";dfs3(1);}LGP17605 「RiOI-8」紫藤 アリサ
原题链接：「RiOI-8」紫藤 アリサ
分析
首先考虑质数，那么，我们有质数a aa，需要构造gcd ( a , b ) + gcd ( a , c ) + gcd ( b , c ) = gcd ( a , b + c ) \gcd(a,b)+\gcd(a,c)+\gcd(b,c)=\gcd(a,b+c)gcd(a,b)+gcd(a,c)+gcd(b,c)=gcd(a,b+c)。
我们发现，如果说b , c b,cb,c取1 11或者a aa，就会出现一些神秘的错误。所以，我们发现，这个b , c b,cb,c与a aa必然互质。
那么，我们需要使得
gcd ( b , c ) = gcd ( a , b + c ) − 2 \gcd(b,c)=\gcd(a,b+c)-2gcd(b,c)=gcd(a,b+c)−2，
那么，不妨使得
b + c = k a b+c=kab+c=ka
然后，使得
gcd ( b , c ) = a − 2 \gcd(b,c)=a-2gcd(b,c)=a−2
那么，我们不妨设
b = d ( a − 2 ) , c = e ( a − 2 ) b=d(a-2),c=e(a-2)b=d(a−2),c=e(a−2)
那么，有
b + c = ( d + e ) ( a − 2 ) b+c=(d+e)(a-2)b+c=(d+e)(a−2)
那么，我们只需要取
d = 2 , e = a − 2 d=2,e=a-2d=2,e=a−2
即可。
可以证明，合数同理（即两边同乘k kk），而对于a = 2 t a=2^ta=2t，由于这个会使得系数为0 00，所以，判定为无解。
正解
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintP=31623;intT;inta;boolvis[P];signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);vis[0]=vis[1]=true;for(inti=2;i*i<P;i++){if(!vis[i]){for(intj=i*i;j<P;j+=i){vis[j]=true;}}}vector<int>primes;for(inti=2;i<P;i++){if(!vis[i])primes.push_back(i);}cin>>T;for(intcs=1;cs<=T;cs++){cin>>a;if(a<=0||(a&(a-1))==0){cout<<-1<<"\n";continue;}intm=a;while(m%2==0)m/=2;intp=m;for(intprime:primes){if(prime==2)continue;if(prime*prime>m)break;if(m%prime==0){p=prime;break;}}intk=a/p;intx=p-2;intb=(k*x)*x;intc=2*k*x;cout<<b<<" "<<c<<"\n";}return0;}LGP5923 [IOI 2004] empodia 障碍段
原题链接：[IOI 2004] empodia 障碍段
分析
lyx大人太强了，一眼秒出了长度必须≥ 4 \ge 4≥4！
继续思考……
真是这吧……我会O ( n 3 ) O(n^3)O(n3)……
就是说，我可以轻易地判断连续，由于这是一个排列，所以说，我似乎可以通过前缀和轻易地判断出来是否连续……
那么，是不是可以做到O ( n 2 ) O(n^2)O(n2)？
继续思考……
我们发现，最小值和最大值都在序列的开头和末尾，那么，不妨使用两个单调栈维护每一个位置前面第一个比它小的和后面第一个比它大的，然后使用前缀和暴力维护……
正解
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1100005;constintM=1100000;intm,a[N];intstk[N],top;intf[N],g[N];intmatch[N];vector<int>buc[N*2];set<pair<int,int>>st;signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>m;for(inti=1;i<=m;i++)cin>>a[i];top=0;for(inti=1;i<=m;i++){while(top>0&&a[stk[top]]<a[i])top--;f[i]=top?stk[top]+1:1;stk[++top]=i;}top=0;for(inti=m;i>=1;i--){while(top>0&&a[stk[top]]>a[i])top--;g[i]=top?stk[top]-1:m;stk[++top]=i;}for(inti=1;i<=m;i++){buc[a[i]-i+M].push_back(i);}for(intd=0;d<N*2;d++){if(buc[d].empty())continue;top=0;for(intj:buc[d]){while(top>0&&g[stk[top]]<j)top--;if(top>0&&f[j]<=stk[top]){match[j]=stk[top];}while(top>0&&g[stk[top]]<=g[j])top--;stk[++top]=j;}}intlst=0;for(intj=1;j<=m;j++){if(match[j]&&match[j]>lst){st.insert({match[j],j});lst=j;}}cout<<st.size()<<"\n";for(autotmp:st){cout<<tmp.first<<" "<<tmp.second<<"\n";}return0;}所以，问题的关键是什么呢？
LGP10478 生日礼物
原题链接：生日礼物
分析
啊？那不是把负数隔出来，然后，负数也排一下序吧，然后把正数的和都掏出来……做完了……
假的……我知道了！
就比如说：
31100-1100你这样的话肯定是要出问题的。那么显然需要反悔对吧。对于一个位置，如果我们选了，那么，直接把贡献记下来，然后把不选的代价记进一个priority_queue里。
思考一下实现细节……大概就是说，我们把一个位置断开的代价扔进堆，然后m--，如果说当前堆顶更大，则m++，并进行反悔……
反正大概就是这吧……我又不想写代码了。
