T1--平方数对(sqrt)
把 \(\sqrt x\) 化成 \(o\sqrt \alpha\) 的形式，\((\sqrt A+\sqrt B)^2\in N\) 当且仅当 \(\alpha_A=\alpha_B\)，那记一下 \(\alpha=x\) 的 \(A/B\) 即可求出答案。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
using namespace std;
const int N=2e6;
int n, m, p[N+5], top, vis[N+5], sp[N+5], L[N], Ans;
signed main() {
freopen("sqrt.in","r",stdin);
freopen("sqrt.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
sp[1]=1;
up(i,2,N) {
if(!vis[i]) p[++top]=i, sp[i]=i;
for(int j=1; i*p[j]<=N; ++j) {
int x=i*p[j];
vis[x]=1;
if(sp[i]%p[j]==0) sp[x]=sp[i]/p[j];
else sp[x]=sp[i]*p[j];
if(i%p[j]==0) break;
}
}
cin >> n >> m;
up(i,1,n) ++L[sp[i]];
up(i,1,m) Ans+=L[sp[i]];
cout << Ans;
return 0;
}
T2--树上路径(tree)
每种颜色的贡献相互独立，分别考虑每一种颜色之后把贡献加起来即可得到答案。
考虑一种颜色，我们称颜色为钦定颜色的点为黑点，我们很难求经过黑点的路径数，正难则反，不经过黑点的路径数是好求的，考虑黑点分割出的连通块大小为 \(\{p_i\}\)，那么这个就是 \(\sum \frac{p_i\times (p_i-1)}{2}\)，因为 \(|p|\leq count(col),\sum|p|=O(n)\)，不妨求出 \(p\)，按照黑点 \(dfn\downarrow\) 考虑，用 dfn + 树状数组 维护子树连通块大小即可。
#include<bits/stdc++.h>
#define ll long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
using namespace std;
const int N=1000005;
int n, L[N], R[N], stamp, tr[N], sp[N], dep[N], siz[N];
ll Ans;
vector<pii> to[N];
vector<int> ran[N];
void add(int x,int v) {
x=L[x];
for( ; x<=n; x+=x&-x) tr[x]+=v;
}
int Ask(int x) {
int ret=0;
for( ; x; x-=x&-x) ret+=tr[x];
return ret;
}
int ask(int x) {
return Ask(R[x])-Ask(L[x]-1);
}
void dfs(int x) {
L[x]=++stamp;
siz[x]=1;
for(pii p:to[x]) {
int y=p.first, w=p.second;
sp[y]=w;
ran[w].pb(y);
dep[y]=dep[x]+1;
dfs(y);
siz[x]+=siz[y];
}
R[x]=stamp;
}
bool cmp(int x,int y) {
return dep[x]==dep[y]?x<y:dep[x]>dep[y];
}
signed main() {
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
up(i,2,n) {
int fa, w;
cin >> fa >> w;
to[fa].pb(mp(i,w));
}
dfs(1);
up(i,1,n) if(ran[i].size()) {
Ans+=(ll)n*(n-1)/2;
sort(ran[i].begin(),ran[i].end(),cmp);
vector<pii> reg;
bool flag=1;
for(int x:ran[i]) {
if(x==1) flag=0;
int lyl=siz[x]-ask(x);
Ans-=(ll)lyl*(lyl-1)/2;
add(x,lyl);
reg.pb(mp(x,lyl));
}
if(flag) {
int lyl=n-ask(1);
Ans-=(ll)lyl*(lyl-1)/2;
}
for(pii p:reg) add(p.first,-p.second);
}
cout << Ans;
return 0;
}
T3--信息传递(info)
原神启动。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
using namespace std;
const int N=500005;
int n, k, t, a[N], b[N];
bool check(int v) {
up(i,1,n) b[i]=a[i]-2*v*t*i;
if(b[1]<b[n]) return 0;
int lyl=k, lsy=k;
dn(i,k-1,1) if(b[i]>=b[lyl]) lyl=i;
up(i,k+1,n) if(b[i]<=b[lsy]) lsy=i;
int l=k, r=k, L, R, opt;
while(lyl<l||r<lsy) {
opt=0;
L=l;
while(L>lyl&&b[r]<=b[L-1]) {
--L;
if(b[l]<=b[L]) { opt=1, l=L; break; }
}
R=r;
while(R<lsy&&b[R+1]<=b[l]) {
++R;
if(b[r]>=b[R]) { opt=1, r=R; break; }
}
if(!opt) return 0;
}
l=1, r=n;
while(l<lyl||lsy<r) {
opt=0;
L=l;
while(L<lyl&&b[r]<=b[L+1]) {
++L;
if(b[l]<=b[L]) { opt=1, l=L; break; }
}
R=r;
while(R>lsy&&b[R-1]<=b[l]) {
--R;
if(b[r]>=b[R]) { opt=1, r=R; break; }
}
if(!opt) return 0;
}
return 1;
}
signed main() {
freopen("info.in","r",stdin);
freopen("info.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k >> t;
up(i,1,n) cin >> a[i];
if(a[n]==0) { cout << 0 << '\n'; return 0; }
int l=1, r=2e9, Ans=0;
while(l<=r) {
int mid=(l+r)>>1;
if(check(mid)) Ans=mid, r=mid-1;
else l=mid+1;
}
cout << Ans << '\n';
return 0;
}