L2-4 缘之空
1.使用倍增法求最近公共祖先，然后利用公共祖先计算两点的树上距离
2.但是此题并没有提供根节点，所以要先找到根节点以后才可以进行倍增法求lca
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define ull unsigned long long
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
#define mod 998244353
const int N=2e5+5;
//-------------倍增法求最近公共祖先---------------------------
int n,q;
vector<int>vct[N];
int dep[N],fa[N][20];//dep存u点的深度，fa存从u点向上跳2的i次方层祖先节点
void dfs(int u,int father){
dep[u]=dep[father]+1;
fa[u][0]=father; ////init跳1步
for(int i=1;i<=17;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for(auto v:vct[u]) if(v!=father) dfs(v,u);
}
int lca(int u,int v){
if(dep[v]>dep[u]) swap(u,v);
////先跳到同一层
for(int i=17;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
if(u==v) return u;
for(int i=17;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
int dist(int u,int v){ return dep[u]+dep[v]-2*dep[lca(u,v)];}
//-------------------------------------------------------
//求树上距离使用倍增法方便，只求最近公共祖先使用tarjan方便
signed main()
{
cin>>n>>q;
map<int,int>mp;
for(int i=1;i<n;i++) {
int a,b;
cin>>a>>b;
mp[b]=1;
vct[a].push_back(b);
vct[b].push_back(a);
}
//------求根节点，看哪个节点没有父节点 -----
int head=1;
for(int i=1;i<=n;i++){
if(!mp[i]) {
head=i;
break;
}
}
//-------------------------------
dfs(head,0);
while(q--)
{
int u,v; cin>>u>>v;
int llca=lca(u,v),d=dist(u,v);
//不能同系
if(llca==u||llca==v||d<=4) cout<<"NO";
else cout<<"YES";
cout<<endl;
cout<<d;
cout<<endl;
}
}
L1-7 拼接梯子
1.本来以为要搜索，其实只需要看二进制位上的1即可，每一个1都代表2的次方，但是如果是奇数或者所有材料的和都比梯子小就无法满足题意，因为材料全为偶数，其次在左移的时候1要写成1ll。
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define ull unsigned long long
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
#define mod 998244353
const int N=2e5+5;
int a[68];
signed main()
{
int k,l; cin>>k>>l;
int ans=-1,cnt=0;
if(l&1||(1ll<<(k+1))-1<l) {
cout<<"No";//｜｜2的n次方的等比求和为2的n+1次方减1
}
else //注意-1要放在整个左移外面，不然就会先计算k+1-1，再左移
{
while(l)
{
if(l&1) ans=cnt;
l>>=1;//二进制位往右移检查是不是一，若是更新ans
cnt++;
}
cout<<"Yes"<<endl;
ans=(1ll<<ans);
cout<<ans;
}
}
L2-1 特殊的沉重球
也是一道dfs的好题，其实这个题可以总结成一类题
有n个物品，每个背包最大可以装w体积的物品，每个物品的体积为ci，且1<=ci<=w,求可以装下这n个物品的最少的背包数量。
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define ull unsigned long long
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
#define mod 998244353
int n,w;
int ans;
int a[70],b[1000005];//a为宝可梦的数量，b为每个球装的重量
void dfs(int x,int now)//x为第几个宝可梦，now为现在用了几个球
{
if(now>=ans) return ;
if(x>n)
{ for(int i=1;i<=now;i++) cout<<b[i]<<" ";
cout<<endl;
ans=min(now,ans);
return ;
}
for(int i=1;i<=now;i++)//注意这里是i<=now
{
if(a[x]+b[i]<=w){//之前的球可以装进去，那么就不增加
b[i]+=a[x];
dfs(x+1,now);//不增加球数
b[i]-=a[x];
}
}
//前面的球都无法装这个宝可梦，单独开一个
b[now+1]+=a[x];
dfs(x+1,now+1);
b[now+1]-=a[x];
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>w;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
ans=n;//最多用掉n个
dfs(1,1);
cout<<ans;
}
L1-6 分鸽子
二分答案，枚举鸽子肉重量，看这个重量下可以达到的人数是否大于等于m即可
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define ull unsigned long long
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
#define mod 998244353
int n,m;
int a[100005];
bool check(int x)
{
int sum=0;
for(int i=1;i<=n;i++)
{
if(a[i]>=x) sum+=a[i]/x;//注意要取等
}
if(sum>=m) return 1;
return 0;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int l=1,r=1e10;
int ans=0;
//---二分板子-----建议背这个--
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)){
ans=mid;
l=mid+1;
}else r=mid-1;
}
//-----------------------
cout<<ans;
}
L1-4 颠倒阴阳
按题意模拟即可，学会转二进制和十进制到相互转换
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define ull unsigned long long
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
#define mod 998244353
char c[505][505];
int n,m,flag=1;
int ans[15];
map<int,int>mp;
queue<pii>q;
signed main()
{
ios::sync_with_stdio(0),cin.tie(0);
int n;
cin>>n;
string s;
while(n)
{
s+=n%2+'0';
n/=2;
}
int ans=0;
//取反过程
for(int i=0;i<s.size();i++){
if(s[i]=='0') s[i]='1';
else s[i]='0';
}
//补0
while(s.size()<32) s+='0';
//cout<<s;
for(int i=0;i<s.size();i++)
{
ans=ans*2+s[i]-'0';//可以按十进制理解
}
cout<<ans;
}
L1-5 演唱会
转换为秒数来比较即可
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define ull unsigned long long
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
#define mod 998244353
char c[505][505];
int n,m,flag=1;
int ans[15];
map<int,int>mp;
queue<pii>q;
signed main()
{
//ios::sync_with_stdio(0),cin.tie(0);
int hh,mm,ss;
char cc;
//用cc吃掉百分号，因为实际上没用
cin>>hh>>cc>>mm>>cc>>ss;
int sum=hh*3600+mm*60+ss;
int tt=3600+22*60+33;
if(sum+tt<19*3600) cout<<"arrive on time";
else if(sum+tt<21*3600) cout<<"arrive late";
else if(sum+tt>=21*3600)cout<<"too late";
}
L1-3 Pokémon
不是闪光的概率为99，按要求保留两位输出，记得闪光还得多除100
/** - swj -
*
／＞_____フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define ull unsigned long long
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
#define mod 998244353
char c[505][505];
int n,m,flag=1;
int ans[15];
map<int,int>mp;
queue<pii>q;
signed main()
{
//ios::sync_with_stdio(0),cin.tie(0);
double a[8];
for(int i=1;i<=7;i++) {
char cc;
cin>>a[i]>>cc;
}
int xx,f; cin>>xx>>f;
if(f==1) printf("%.2lf",a[xx+1]/100);
else printf("%.2lf",a[xx+1]*0.99);
cout<<"%";
}