今日总结：
1:约数个数和
这道题主要是一道数学题，主要的推到过程需要用到莫比乌斯反演，但是在求第一步用分块处理出1~n内的f(i)的值，再用线性筛求出u(i)的值和他的前缀和，我卡在了最后一步对原式进行数论分块
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
typedef long long LL;
int t,cnt;
int p[N],mu[N],sum[N];
LL g[N];
bool v[N];
void init(int n)
{
mu[1] = 1;
for(int i = 2;i <= n;i ++)
{
if(!v[i])
{
p[ ++ cnt] = i;
mu[i] = -1;
}
for(int j = 1;j <= cnt && p[j] * i <= n;j ++)
{
v[p[j] * i] = 1;
if(i % p[j] == 0) break;
else mu[i * p[j]] = -mu[i];
}
}
for(int i = 1;i <= n;i ++)
sum[i] = sum[i - 1] + mu[i];
for(int i = 1;i <= n;i ++)
{
LL res = 0;
for(int l = 1,r;l <= i;l = r + 1)
{
r = (i / (i / l));
res += 1LL * (r - l + 1) * 1ll * (i / l);
}
g[i] = res;
}
}
int main()
{
scanf("%d",&t);
init(50000);
while(t --)
{
int n,m;
scanf("%d %d",&n,&m);
LL res = 0;
for(int l = 1,r;l <= min(n,m);l = r + 1)
{
r = min(n / (n / l),m / (m / l));
res += (sum[r] - sum[l - 1]) * 1ll * g[n / l] * 1ll * g[m / l];
}
printf("%lld\n",res);
}
return 0;
}
2:硬币购物
动态转移方程如下:
dp[j] += dp[j - c[i]];
res += pm[cnt % 2] * (tmp >= 0 ? dp[tmp] : 0);
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 4;
const int Max = 1e5 + 10;
const int pm[] = {1,-1};
int tot,s;
int c[N],d[N],dp[Max] = {1};
signed main()
{
for(int i = 0;i < 4;i ++)
{
scanf("%lld",&c[i]);
for(int j = c[i];j < Max;j ++)
dp[j] += dp[j - c[i]];
}
scanf("%lld",&tot);
while(tot --)
{
for(int i = 0;i < 4;i ++)
scanf("%lld",&d[i]);
scanf("%lld",&s);
int res = 0;
for(int i = 0;i < 16;i ++)
{
int tmp = s,cnt = 0;
for(int j = 0;j < 4;j ++)
{
if((i >> j) & 1)
{
cnt ++;
tmp -= (d[j] + 1) * c[j];
}
}
res += pm[cnt % 2] * (tmp >= 0 ? dp[tmp] : 0);
}
printf("%lld\n",res);
}
return 0;
}
3:
雨天的尾巴
此题为一道线段树合并的板子题
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 6e6 + 10;
typedef long long ll;
int n,m,cnt,R,num;
int l[M],r[M],d[M],t[M];
int top[N],fa[N],head[N],deep[N],son[N],sum[N],X[N],Y[N],Z[N],rt[N],Ans[N];
struct Node
{
int val,nxt;
}e[N << 1];
inline void add(int x,int y)
{
e[++ num].val = y;
e[num].nxt = head[x];
head[x] = num;
}
inline void dfs_1(int x)
{
sum[x] = 1;
int Max = -1;
for(int i = head[x];i;i = e[i].nxt)
{
if(!deep[e[i].val])
{
deep[e[i].val] = deep[x] + 1;
fa[e[i].val] = x;
dfs_1(e[i].val);
sum[x] += sum[e[i].val];
if(sum[e[i].val] > Max) Max = sum[e[i].val],son[x] = e[i].val;
}
}
}
inline void dfs_2(int x,int topp)
{
top[x] = topp;
if(!son[x]) return;
dfs_2(son[x],topp);
for(int i = head[x];i;i = e[i].nxt)
{
if(!top[e[i].val])
dfs_2(e[i].val,e[i].val);
}
}
inline int Lca(int x,int y)
{
while(top[x] != top[y])
{
if(deep[top[x]] < deep[top[y]]) swap(x,y);
x = fa[top[x]];
}
if(deep[x] < deep[y]) return x;
return y;
}
inline void pushup(int a)
{
if(d[l[a]] >= d[r[a]])
{
d[a] = d[l[a]];
t[a] = t[l[a]];
}
else
{
d[a] = d[r[a]];
t[a] = t[r[a]];
}
}
inline int query(int a,int x,int y,int pos,int val)
{
if(!a) a = ++ cnt;
if(x == y)
{
d[a] += val;
t[a] = x;
return a;
}
int mid = (x + y) / 2;
if(pos <= mid) l[a] = query(l[a],x,mid,pos,val);
else r[a] = query(r[a],mid + 1,y,pos,val);
pushup(a);
return a;
}
inline int merge(int a,int b,int x,int y)
{
if(!a) return b;
if(!b) return a;
if(x == y)
{
d[a] += d[b];
t[a] = x;
return a;
}
int mid = (x + y) / 2;
l[a] = merge(l[a],l[b],x,mid);
r[a] = merge(r[a],r[b],mid + 1,y);
pushup(a);
return a;
}
inline void redfs(int x)
{
for(int i = head[x];i;i = e[i].nxt)
{
if(deep[e[i].val] > deep[x])
{
redfs(e[i].val);
rt[x] = merge(rt[x],rt[e[i].val],1,R);
}
}
if(d[rt[x]]) Ans[x] = t[rt[x]];
}
int main()
{
scanf("%d %d",&n,&m);
int x,y;
for(int i = 1;i < n;i ++)
{
scanf("%d %d",&x,&y);
add(y,x),add(x,y);
}
deep[1] = 1;
dfs_1(1),dfs_2(1,1);
for(int i = 1;i <= m;i ++)
{
scanf("%d %d %d",&X[i],&Y[i],&Z[i]);
R = max(R,Z[i]);
}
for(int i = 1;i <= m;i ++)
{
int lca = Lca(X[i],Y[i]);
rt[X[i]] = query(rt[X[i]],1,R,Z[i],1);
rt[Y[i]] = query(rt[Y[i]],1,R,Z[i],1);
rt[lca] = query(rt[lca],1,R,Z[i],-1);
if(fa[lca]) rt[fa[lca]] = query(rt[fa[lca]],1,R,Z[i],-1);
}
redfs(1);
for(int i = 1;i <= n;i ++)
printf("%d\n",Ans[i]);
return 0;
}