题不错,所以做了下.
A 多彩的树
给定一棵树,每个点有一种颜色,问恰好包含i种颜色的路径的数量(i从1-k) $k<=10$看见路径信息统计,想到点分治,k很小,状压即可.我们用num[1<<10]的桶记录这种状态的路径的数量然后考虑怎么合并两条路径:num[i|j] = cnt[i] * cnt[j]朴素暴力是$O(n*4^k)$的,5秒应该过不了很容易发现这是个或运算卷积,FWT优化一下即可.但是要注意当i==j的时候num[i|j] = cnt[i] * (cnt[i]-1)/2 + cnt[i](选两个合并,以及和空路径合并(减不合法路径时不包含)),然后注意到FWT中算的是cnt[i] * cnt[i] + 2*cnt[i],所以还要减掉一个cnt[i].由于是点权所以要注意些细节问题,特别是减掉不合法路径的时候,然后这题就做完了其实可以直接状压包含的颜色数,然后找到只包含这样颜色的连通块
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
| #include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 5e4 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7, two = (mod+1)/2;
int n, k, a[N];
vector<int> G[N];
ll pw[15];
int rt, sz[N], dp[N], mxsz;
ll mask[1<<10], num[1<<10], tmp[1<<10];
bool vis[N];
void FWT(ll *a, int n)
{
for(int d=1;d<n;d<<=1)
for(int m=d<<1,i=0;i<n;i+=m)
for(int j=0;j<d;j++)
{
ll x = a[i+j], y = a[i+j+d];
a[i+j+d] = (x+y)%mod;
}
}
void IFWT(ll *a, int n)
{
for(int d=1;d<n;d<<=1)
for(int m=d<<1,i=0;i<n;i+=m)
for(int j=0;j<d;j++)
{
ll x = a[i+j], y = a[i+j+d];
a[i+j+d] = (y-x+mod)%mod;
}
}
void findroot(int u, int fa)
{
dp[u] = 0, sz[u] = 1;
for(auto v : G[u])
{
if(vis[v]||v==fa) continue;
findroot(v, u);
dp[u] = max(dp[u],sz[v]);
sz[u] += sz[v];
}
dp[u] = max(dp[u],mxsz-sz[u]);
if(dp[u]<dp[rt]) rt = u;
}
void getdis(int u, int fa, int d)
{
d |= (1<<a[u]);
mask[d]++;
for(auto v : G[u])
{
if(vis[v]||v==fa) continue;
getdis(v, u, d);
}
}
void calcu(int u, int d)
{
memset(mask, 0, sizeof(mask));
if(!d) mask[0] = 1;
getdis(u, 0, d);
memcpy(tmp, mask, sizeof(mask));
FWT(tmp, 1<<k);
for(int i=0; i<(1<<k); i++) tmp[i] = tmp[i]*tmp[i]%mod;
IFWT(tmp, 1<<k);
for(int i=0; i<(1<<k); i++)
{
if(!d) (num[i] += tmp[i] - mask[i]) %= mod;
else (num[i] -= tmp[i] + mask[i]) %= mod;
}
}
void solve(int u)
{
vis[u] = 1;
calcu(u, 0);
for(auto v : G[u])
{
if(vis[v]) continue;
calcu(v, 1<<a[u]);
mxsz = sz[v], rt = 0;
findroot(v, u);
solve(rt);
}
}
int main()
{
scanf("%d%d", &n, &k);
pw[0] = 1;
for(int i=1; i<=k; i++) pw[i] = pw[i-1]*131%mod;
for(int i=1; i<=n; i++)
{
scanf("%d", a+i);
a[i]--;
}
for(int i=1; i<n; i++)
{
int u, v; scanf("%d%d", &u, &v);
G[u].pb(v); G[v].pb(u);
}
dp[0] = mxsz = n;
findroot(1, 0);
solve(rt);
ll ans = 0;
for(int i=1; i<(1<<k); i++)
{
int j = __builtin_popcount(i);
(ans += pw[j]*num[i]%mod) %= mod;
}
if(ans<0) ans += mod;
ans = ans*two%mod;
printf("%lld\n", ans);
return 0;
}
|
B 求幂
给定n(n<=1e6),问满足a^b = c^d的四元有序组个数,其中a,b,c,d在1-n之间有一个结论是各个非完全平方数的所有幂次组成的集合是没有交集的,考虑按此划分,显然不同集合间没有贡献.考虑一个集合中的两个元素a^b和a^c,令d=max(b,c)/__gcd(b,c),则有n/d组元素(ab,x∗d,ac,y),1<=x<=n/d.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 1e6 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n;
bool vis[N];
int main()
{
scanf("%d", &n);
ll ans = 1ll*n*n;
for(int i=2; i<=n; i++)
{
if(vis[i]) continue;
vector<pii> tmp;
for(ll j=i, k=1; j<=n; j*=i, k++)
{
vis[j] = 1;
tmp.pb({j, k});
}
ll cur = 0;
for(int i=0; i<sz(tmp); i++)
{
for(int j=0; j<sz(tmp); j++)
{
int x = tmp[i].se/__gcd(tmp[i].se, tmp[j].se), y = tmp[j].se/__gcd(tmp[i].se, tmp[j].se);
cur += n/max(x, y);
if(cur>=mod) cur -= mod;
}
}
ans = (ans + cur)%mod;
}
if(ans<0) ans += mod;
printf("%lld\n", ans);
return 0;
}
|
C 序列最小化
给定一个1-n的排列,每次可以选择k个连续的数将其变成最小的那个数,问最少经过几次操作使序列最小.最后肯定都变成了1,第一次操作肯定包含了1这个位置,所以枚举第一次操作的左右端点,则后面的操作一定是左右延伸.
D 小雨坐地铁
m条地铁线路,n个车站,第i条地铁线路花费a[i],经过c[i]个车站,每站花费b[i]元,问从s站到t站的最小花费.如果有多条地铁经过同一个车站,可以换乘.对于某个车站,如果存在于多个地铁线路中,其实是不同的状态,所以对于每个地铁线路中的车站我们都用一个新点来表示.这样就可以进行建图跑最短路了.对于某条线路中的车站,依次连双向边,权值为b[i] (表示继续乘坐) ,再向经过该车站的其他线路中的该车站所代表的点连单向边,权值为a[i] (表示换乘).由于s和t代表的点有多个,所以加上超源和超汇.超源向每个地铁线路中的s连单向边,权值为a[i], 每个地铁线路中的t向超汇连单向边,权值为0.注意s=t的时候,需要特判,因为以上建图方法,如果没有地铁线路通过s,则超源和s不连通,如果从超源跑dij,会输出-1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| #include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 1e3 + 5, M = 5e5 + 5;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
constexpr int mod = 1e9 + 7;
int n, m, s, t, a[N], b[N], c[N], idx[505][N], tot;
vector<int> p[N], q[N];
vector<pii> G[M];
ll dis[M];
bool vis[M];
void Dijkstra(int s)
{
memset(dis,0x3f,(tot+1)*sizeof(ll));
memset(vis,0,(tot+1)*sizeof(bool));
dis[s] = 0;
priority_queue <pli,vector<pli>,greater<pli>> q;
q.push(mp(0,s));
while(!q.empty())
{
int u = q.top().se; q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(auto it : G[u])
{
int v = it.fi, w = it.se;
if(dis[v]>dis[u]+w)
{
dis[v] = dis[u] + w;
q.push(mp(dis[v],v));
}
}
}
}
int main()
{
scanf("%d%d%d%d", &n, &m, &s, &t);
if(s==t)
{
puts("0");
return 0;
}
tot = m;
for(int i=1; i<=m; i++)
{
scanf("%d%d%d", a+i, b+i, c+i);
q[i].resize(c[i]);
for(int &x : q[i])
{
scanf("%d", &x);
p[x].pb(i);
}
}
for(int i=1; i<=m; i++)
{
int pre = i;
for(int x : q[i])
{
++tot;
idx[i][x] = tot;
G[pre].emplace_back(tot, b[i]);
G[tot].emplace_back(pre, b[i]);
pre = tot;
}
}
++tot;
for(int i=1; i<=m; i++)
for(int x : q[i])
{
if(x==t) G[idx[i][x]].emplace_back(tot, 0);
if(x==s) G[0].emplace_back(idx[i][x], a[i]);
for(int k : p[x])
G[idx[i][x]].emplace_back(idx[k][x], a[k]);
}
Dijkstra(0);
if(dis[tot]==LINF) dis[tot] = -1;
printf("%lld\n", dis[tot]);
return 0;
}
|
E 简单瞎搞题
有100个数,每个数$x_i$有$l_i\sim r_i$的范围(<=100),问$\sum x_i^2$的种类数一眼bitset的优化,但仔细算了下1e6*100*100/32,似乎不太行,想了一会别的方法没想出,看了眼别人的代码,然后发现就是bitset😐,只能说明牛客机子牛逼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 1e6 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
bitset <N> f;
int n;
int main()
{
scanf("%d", &n);
f[0] = 1;
for(int i=1; i<=n; i++)
{
int l, r; scanf("%d%d", &l, &r);
bitset <N> nextf;
for(int j=l; j<=r; j++) nextf |= f<<(j*j);
f = nextf;
}
printf("%d\n", f.count());
return 0;
}
|