签到题这里久懒得写了。
B - 缺失的数据范围
Total Submission(s): 2602 Accepted Submission(s): 559
题意：求最大的N，满足N^a*[log2(N)]^b<=K;
思路：二分即可，log2要手写，然后就是注意判pow是否超过long long。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=;
const ll inf=1e18;
ll A,B,K,ans,aa[];
ll Log(ll x){
int pos=lower_bound(aa+,aa++,x)-aa;
return pos;
}
bool check(ll x){
ll a=,res=;
ll b=Log(x);// cout<<b<<" "<<aa[b]<<" ";
for(int i=;i<=A;i++){
if(a>K/x) return false;
a=a*x; if(a>K) return false;
}
for(int i=;i<=B;i++){
if(res>K/b) return false;
res=res*b; if(res>K) return false;
}
//cout<<a<<" "<<b<<endl;
if(a>K/res) return false;
if(a*res<=K) return true;
}
int main()
{
int T;
aa[]=;
for(int i=;i<=;i++) aa[i]=aa[i-]*;
scanf("%d",&T);
while(T--){
scanf("%lld%lld%lld",&A,&B,&K); ans=;
ll L=,R=K;
while(L<=R){
ll Mid=(L+R)/;
if(check(Mid)) ans=Mid,L=Mid+;
else R=Mid-;
}
printf("%lld\n",ans);
}
return ;
}
E - 对称数
Total Submission(s): 469 Accepted Submission(s): 88
题意：给出一棵带点权的树，Q次询问，每次询问给出(u,v)，求这个路径上最小的出现次数位偶数的正整数。
思路：树上莫队：皇室联邦法分块，括号法移动区间。
皇室联邦法分块：即按照DFS虚分块。
括号法：dfs时，记录第一次访问时间戳in[]和最后一次访问时间戳out[]。如果访问路径(u,v)，保证in[u]<in[v]起对应的区间就是：
1，LCA==u，对应[in[u],in[v]];
2，LCA!=u，对应[out[u],in[v]]+LCA;LCA单独考虑为pre，不要忽略。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int a[maxn],Laxt[maxn],Next[maxn],To[maxn],cnt,B;
int g[maxn],dep[maxn],fa[maxn][],ans[maxn],scc,tot;
int in[maxn],out[maxn],p[maxn];
bitset<maxn>Set;
struct in{
int u,v,id;
friend bool operator <(in ww,in vv){
if(g[ww.u]==g[vv.u]) return g[ww.v]<g[vv.v];
return g[ww.u]<g[vv.u];
}
}s[maxn];
void add(int u,int v)
{
Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v;
}
void dfs(int u,int f)
{
fa[u][]=f; dep[u]=dep[f]+;
if(tot%B==) scc++; g[u]=scc;
in[u]=++tot; p[tot]=a[u];
for(int i=Laxt[u];i;i=Next[i]){
if(To[i]!=f) dfs(To[i],u);
}
out[u]=++tot; p[tot]=a[u];
}
int LCA(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
for(int i=;i>=;i--)
if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
if(u==v) return u;
for(int i=;i>=;i--)
if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][];
}
int main()
{
int T,N,M,u,v,Lca;
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&M); B=sqrt(N);
cnt=; rep(i,,N) Laxt[i]=;
rep(i,,N) scanf("%d",&a[i]);
rep(i,,N-){
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
tot=; scc=; dfs(,);
rep(i,,) rep(j,,N) fa[j][i]=fa[fa[j][i-]][i-];
rep(i,,M) scanf("%d%d",&s[i].u,&s[i].v),s[i].id=i;
rep(i,,M) if(in[s[i].u]>in[s[i].v]) swap(s[i].u,s[i].v);
sort(s+,s+M+);
Set.set();
int L=,R=,pre=; Set.flip(p[]);
rep(i,,M) {
Set.flip(pre);
int Lca=LCA(s[i].u,s[i].v),l,r;
if(Lca==s[i].u) l=in[s[i].u],r=in[s[i].v],pre=;
else l=out[s[i].u],r=in[s[i].v],Set.flip(a[Lca]),pre=a[Lca];
while(l<L) Set.flip(p[--L]);
while(l>L) Set.flip(p[L++]);
while(r>R) Set.flip(p[++R]);
while(r<R) Set.flip(p[R--]);
int pos=Set._Find_next();
ans[s[i].id]=pos;
}
rep(i,,M) printf("%d\n",ans[i]);
}
return ;
}
I - 回文树
题意：给出一棵带权树，点权随机给出，求树上有多少回文串。
思路：由于是随机，我们大胆猜测，只存在长度为1，2和3的回文串。
Total Submission(s): 198 Accepted Submission(s): 45
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int a[maxn]; map<int,int>mp[maxn];
int main()
{
int N,T,u,v;
scanf("%d",&T);
while(T--){
int ans=;
scanf("%d",&N);
rep(i,,N) mp[i].clear();
rep(i,,N) scanf("%d",&a[i]);
rep(i,,N-){
scanf("%d%d",&u,&v);
if(a[u]==a[v]) ans++;
ans+=mp[u][a[v]];
ans+=mp[v][a[u]];
mp[u][a[v]]++; mp[v][a[u]]++;
}
printf("%d\n",ans+N);
}
return ;
}