11_15做题总结
今天来讲两个题目，一个是昨天的D1，一个是自己找的D4的E
D1
序列一开始从1到1e12
输入x,y,k做x次操作,然后找到每次在数列中删掉下标是y的倍数的数,求操作完之后第k号数
先特判,如果y=-1或者暴力的边更新边删完x次n/y后n<k,那么就输出-1
否则从最后一次反解出第k号元素的初始值
令新元素B是A删完A/y后的第k号数
A=q*y+r
B=A-q
所以B=q*(y-1)+r
这个时候就要对r分情况讨论了
如果r=y-1,即x整除y-1,(因为r不可能=0,否则A不存在)
此时q=B/(y-1)-1,A=B+[B/(y-1)]-1
如果r不等于y-1,即x不整除y-1那么q=B/(y-1),r=A%(y-1),A=B+[B/(y-1)]
综合一下,A=B+[(B-1)/(y-1)],涵盖了两种情况,这里很神
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define endl '\n'
const int INF=1e18,N=2e5,MOD=1e9+7;void solve(){int x,y,k;cin>>x>>y>>k;if(y==1){cout<<-1<<endl;return ;}int n=1000000000000;for(int i=0;i<x;i++){n=n-n/y;}if(k>n){ cout<<-1<<endl;return ;}int ans=k;for(int i=0;i<x;i++) ans=ans+(ans-1)/(y-1);cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);int T=1;cin>>T;while(T--)solve();return 0;
}
E
一棵树,枚举每个点作为根节点时,求任意k个点形成的LCA的种数.输出每个点作为根节点时的和
其实不需要求LCA,每次找一棵根节点是i的子树,找树里面的k-1ge3点和它自己作为集合,这个集合的LCA就是i,如果根节点是子树外面的话,///其实如果根节点在里面也可以这样算,只不过答案加的值要变换一下
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define endl '\n'
const int INF=1e18,N=2e5,MOD=1e9+7;
vector<int>g[N+5];
int sz[N+5];
void dfs(int u,int fa){for(int v:g[u]){if(v!=fa){dfs(v,u);sz[u]+=sz[v];}}
}void solve(){int n,k;cin>>n>>k;memset(sz,0,sizeof(sz));for(int i=0;i<=n;i++) g[i].clear();for(int i=0;i<n-1;i++){int u,v;cin>>u>>v;g[u].pb(v);g[v].pb(u);}for(int i=0;i<=n;i++) sz[i]=1;dfs(1,0);int ans=0;for(int i=1;i<=n;i++){if(sz[i]>=k) ans+=n-sz[i];if(n-sz[i]>=k) ans+=sz[i];}cout<<ans+n<<endl;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);int T=1;cin>>T;while(T--)solve();return 0;
}
