2022赛前模测 提高组 第一场
Chain
题面描述:
现有\(n\)个不超过\(10^6\)的合数，每个均可表示为\(a=p*q\)( 为两个互异素数)。 若\(a=p_1*q_1(p_1<q_1),b=p_2*q_2(p_2<q_2)\)当且仅当\(q_1=p_2\)时，\(b\)能接在\(a\)后面。 请问从给定的这\(n\)个数中选数接龙，最长可以形成一个包含多少数的接龙序列
Input
第一行输入一个正整数\(n\)，意义如题干所述。\(（n≤5*10^4）\)
第二行输入 \(n\) 个不超过 \(10^6\) 的合数。
Output
输出仅一个整数，表示问题的答案。
数据范围
测试点 满足\(1\sim3\) : 每个数不超过 \(10^3\) , \(n=9\) ;
测试点 满足\(4\sim6\) : 每个数不超过 \(10^{6}\),\(n=1000\);
测试点 满足\(7\sim10\)：每个数不超过 \(10^6\),\(n=50000\)。
Solution:
对每个合数分解质因子，先提前把素数筛出来，然后以素数为点，和数为边建一个\(DAG\)跑\(DP\)
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 1e6;
int n;
int cnt, prime[N];
bool vis[N];
void init()
{
for(int i = 2; i <= M; i++)
{
if(!vis[i])prime[++cnt] = i;
for(int j = 1; j <= cnt && prime[j] * i <= M; j++)
{
vis[i * prime[j]] = true;
if(i % prime[j] == 0)break;
}
}
}
struct node
{
int x, y;
node(int _x = 0, int _y = 0) : x(_x), y(_y) {}
friend bool operator < (node a, node b)
{
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
};
node d[N], dx[N], dy[N];
int f[N];
int dfs(int x)
{
if(f[x])return f[x];
int pos = lower_bound(dx + 1, dx + n + 1, x) - dx;
for(int i = pos; i <= n; i++)
{
if(d[i].x > x)break;
f[x] = max(dfs(d[i].y) + 1, f[x]);
}
return f[x];
}
int main()
{
init();
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
int x;scanf("%d", &x);
for(int j = 1; j <= cnt; j++)
{
if(x % prime[j] == 0)
{
d[i] = node(prime[j], x / prime[j]);
dx[i] = prime[j]; dy[i] = x / prime[j];
break;
}
}
}
sort(d + 1, d + n + 1);
sort(dx + 1, dx + n + 1);
sort(dy + 1, dy + n + 1);
for(int i = 1; i <= n; i++)
f[d[i].x] = max(f[d[i].x], dfs(d[i].y) + 1);
int ans = 0;
for(int i = 1; i <= M; i++)
ans = max(ans, f[i]);
printf("%d\n", ans);
return 0;
}
Mintree
题目描述:
你有一个含\(n\)个点, \(m\) 条边的图。现在选出一棵生成树，你每次可以选择树上一条边使其边权 \(-1\) 问至少需要操作多 少次之后这棵树会成为图的最小生成树? 保证图完全连通且不含重边。
注: 图中节点编号从\(1\sim n\) .
Input
第一行輸入两个数 \(n, m\) ，分别表示图的点数和边数; \(\quad(1 \leq n \leq 10000 ， 1 \leq m \leq 100000)\)
之后 \(m\) 行，每行三个数 \(u, v, w\) ，表示从点\(u\)到点\(v\) 的连边权值为 \(w\) ;
之后\(n-1\)行，每行两个数 \(a,b\)，表示选定生成树的每条边。
Output
输出一个数，表示最少的操作次数。
数据范围
对于 \(25 \%\) 的数据， \(1 \leq n \leq 20 ， 1 \leq m \leq 100\) ；
对于 \(40 \%\) 的数据， \(1 \leq n \leq 100 ， 1 \leq m \leq 500\) ；
对于 \(60 \%\) 的数据， \(1 \leq n \leq 1000 ， 1 \leq m \leq 5000\) ；
对于 \(100 \%\) 的数据， \(1 \leq n \leq 10000 ， 1 \leq m \leq 100000 ， 1 \leq w \leq 1000000 ， 1 \leq a, b<=n\);
Solution:
先做如下定义，在给出的生成树中的边，我们称为树边。不在生成树中的为非树边。
如何才能让给定的生成树成为最小生成树呢?
对于非树边 \(E(u, v)\) ，对应生成树上的一条路径 \((u\rightarrow v)\) 。如果 \(E(u, v)\) 的边权小于这条路径上的某条边，那 我们选择 \(E(u, v)\) ，而去掉那条边，就会得到一棵新的生成树。并且这棵生成树的权值和更小。因此对于生成树上 \((u\rightarrow v)\) 每一条边的边权，都要小于等于 \(E(u, v)\) 才行。
所以我们需要修改路径上树边权值，使得所有非树边 \(E(i, j)\) 的权值大于生成树上路径 \((i \rightarrow j)\) 的每条边的权 值。
这种暴力更新的方法，最坏复杂度可能是平方的。我们对非树边按照权值从小到大排序。先处理权值小的，再处理 权值大的。这样如果某个边的权值已经被修改过，那么后面的更新就不用重复修改了。
这样的话，每条边只被处理一次。之后我们可以利用路径压缩，来解决边被多次枚举的问题。复杂度 \(O(m l o g m)\) - 因为需要对所有非树边进行排序。
Code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
ll read()
{
ll x=0;char ch = getchar();
while(!isdigit(ch)) ch =getchar();
for(;isdigit(ch);ch=getchar()) x= (x<<3) + (x<<1) + (ch^48);
return x;
}
const int N = 200005;
int n,m;
int dfn[N],id[N],dfnt,dep[N];
int top[N],siz[N],son[N],fa[N];
vector<int>gra[N];
struct edge
{
int u,v,w;
}e[N];
void dfs1(int x,int f)
{
siz[x] = 1;
dep[x] = dep[f] + 1;
fa[x] = f;
for(auto v:gra[x])
{
if(v==f) continue;
dfs1(v,x);
siz[x]+=siz[v];
if(siz[son[x]] < siz[v]) son[x] = v;
}
}
void dfs2(int x,int topf)
{
top[x] = topf;
id[x] = ++dfnt;
dfn[dfnt] = x;
if(son[x]) dfs2(son[x],topf);
for(auto v:gra[x])
{
if(v==fa[x] || v==son[x]) continue;
dfs2(v,v);
}
}
int t[N<<2];
void build(){
memset(t,0x3f,sizeof t);
}
#define ls (p<<1)
#define rs (p<<1|1)
void getmin(int x,int y,int k,int p=1,int l=1,int r=n)
{
if(x<=l && r<=y){
t[p] = min(k,t[p]);
return ;
}
int mid = l + r >> 1;
if(x<=mid) getmin(x,y,k,ls,l,mid);
if(y>mid) getmin(x,y,k,rs,mid+1,r);
}
int query(int x,int p=1,int l=1,int r=n)
{
if(l==r) return t[p];
int mid = l + r >> 1;
if(x<=mid) return min(t[p],query(x,ls,l,mid));
else return min(t[p],query(x,rs,mid+1,r));
}
int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x,y);
x = fa[top[x]];
}
if(dep[x] < dep[y]) swap(x,y);
return y;
}
void solve(int x,int y,int k)
{
int lca = LCA(x,y);
while(top[x]!=top[lca])
{
getmin(id[top[x]],id[x],k);
x = fa[top[x]];
}
if(x!=lca) getmin(id[lca]+1,id[x],k);
while(top[y]!=top[lca])
{
getmin(id[top[y]],id[y],k);
y = fa[top[y]];
}
if(y!=lca) getmin(id[lca]+1,id[y],k);
}
#define pa pair<int,int>
#define se second
#define fi first
#define ma(x,y) make_pair(x,y)
map<pa,int>mp;
signed main()
{
n = read();m=read();
for(int i=1;i<=m;i++){
e[i].u = read();
e[i].v = read();
e[i].w = read();
}
for(int i=1;i<n;i++)
{
int u = read();
int v = read();
gra[u].emplace_back(v);
gra[v].emplace_back(u);
mp[ma(u,v)] = mp[ma(v,u)] = 1;
}
dfs1(1,0);
dfs2(1,1);
build();
for(int i=1;i<=m;i++)
{
if(mp.count(ma(e[i].u,e[i].v))) continue;
solve(e[i].u,e[i].v,e[i].w);
}
long long ans = 0;
for(int i=1;i<=m;i++)
{
if(mp.count(ma(e[i].u,e[i].v)))
{
if(dep[e[i].u] > dep[e[i].v]) swap(e[i].u,e[i].v);
ans += max(0ll,e[i].w-query(id[e[i].v]));
}
}
cout << ans;
return 0;
}
Rlprime
题面描述：
两个数 A, B \quad(B>=A) ，问有多少个序列满足以下条件:
- 序列是递增的。
- 所有数字属于区间 [A, B] (包括 A 和 B ， B-A<=100 ) 。
- 序列中的所有数字两两互质
Input
一行输入两个数 \(\mathrm{A}, \mathrm{B}\) 。其中 \(1\leq \mathrm{A} \leq \mathrm{B} \leq 1 \mathrm{e} 18 ， \mathrm{~B}-\mathrm{A} \leq 100\) 。
Output
输出对应的答案
Solution:
注意两个数之间最多不超过\(100\)所质因子的大小最多也不超过\(100\),所以预处理出前\(25\)个质数,然后再把包含的质数存到vector里，然后考虑\(dp\)考虑状压每一个质数是否被包含，枚举每个数从\(l\)到\(r\)的时候，设当前状态为该数包含质因子的数，然后满足条件的就是$S = ((1 << len) - 1) \oplus now \(然后枚举该集合的子集统计答案即可，最后记得把\)ans$减一因为不能不取把\(0\)的情况减去
Code:
#include<bits/stdc++.h>
using namespace std ;
#define re cout<<"Fuck";
const int SIZE = 1<<23 ;
typedef long long ll ;
int prime[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
ll dp[SIZE];
vector<int> e;
bool use[30] ;
int main(){
ll l,r ;
cin>>l>>r;
dp[0]=1;
for(ll i=l;i<=r;i+=1){
for(int j=0;j<25;j+=1){
if(i%prime[j]==0){
use[j]=true ;
}
}
}
for(int i=0;i<25;i+=1)
if(use[i]) e.emplace_back(prime[i]) ;
for(ll i=l;i<=r;i+=1){
int s=0;
for(int j=0;j<e.size();j+=1){
if(i%prime[j]==0){
s |= (1 << j) ;
}
}
int ns = s ^ ((1 << e.size()) - 1) ;
for(int j=ns;j;j=(j-1)&ns){
dp[j|s] += dp[j] ;
}
dp[s]+=dp[0] ;
}
ll ans=0;
for(int i=0;i<(1<<e.size());i+=1){
ans+=dp[i];
}
cout<<ans-1;
}
Seq
题面描述：
鬼鬼是一个十四岁的少女，她特别喜欢等差数列。出于对等差数列的喜欢，她想找这种序列: 向这个序列 a 中加上 不多于 k 个数，使这个新的数列排序后可以得到一个公差为 d 的等差序列。
鬼鬼给你了一个由 n 个整数组成的数列 a 。你的任务是找到它的最长子串，使它是鬼鬼想找的序列。鬼鬼会十分感 谢你的!
Input
第一行輸入三个整数\(\mathrm{n},\mathrm{k},\mathrm{d}。\quad(1<=\mathrm{n}<=2\mathrm{e} 5,0<=\mathrm{k}<=2\mathrm{e}5,0<=\mathrm{d}<=1\mathrm{e}9)\)
第二行输入\(\mathrm{n}\) 个整数，表示数列\(a[]\)。\(\quad(-1 \mathrm{e} 9<=\mathrm{a}>. [\mathrm{i}]<=1 \mathrm{e} 9)\)
Output
输出两个整数 \(L, R\) ， 描述这个最长子串的左/右边界。如果有多个最优答案，输出 L 值最小的。
数据范围：
对于 \(20 \%\) 的数据， \(1 \leq n \leq 10\) ；
对于 \(40 \%\) 的数据， \(1 \leq n \leq 1000\) ；
对于 \(100 \%\) 的数据，\(1 \leq n, k \leq 200000,0 \leq d \leq 10^{9},-10^{9} \leq a[i] \leq 10^{9}\)。
Solution:
我们先将序列拆分（ (a[i] 相等的连续一段为一组 ) ，每组单独处理。
先对 \(a[i] /=D\) ，于是我们就可以得到如下等式:\(\max (a[i], i \in\{l, r\})-\min (a[i], i \in\{l, r\}) \leq r-l+k\)
移项得:
\(\max (a[i], i \in\{l, r\})-\min (a[i], i \in\{l, r\})+l \leq r+k\)
因此，我们枚举 \(r\) ，用线段树维护 \(l\) 。
而对于不等号左面那一大坨，如果加入一个数进来，会将之前所有 \(\min\)值比它大的数降低 \(\min -a[i]\) ，所以我们可以用单调栈维护， \(\max\) 同理。注意如果出现重复的数，我们开一个 \(map\)记录数字上一个出现的位置,如果重复则把\(l \rightarrow r-1\)赋值成\(inf\)
Code
#include <bits/stdc++.h>
#define pir pair<int, int>
using namespace std;
const int SIZE = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int x[SIZE], y[SIZE];
struct Stack
{
int st[SIZE];
int tp;
void clear() { tp = 0; }
void push(int x) { st[++tp] = x; }
int top() { return st[tp]; }
int sec() { return st[tp - 1]; }
void pop() { --tp; }
bool empty() { return tp == 0; }
} stmn, stmx;
struct Laffey
{
#define ls(i) (i << 1)
#define rs(i) (i << 1 | 1)
int l, r;
int mn, cov, add;
Laffey(int l = 0, int r = 0, int mn = INF, int cov = -1, int add = 0) : l(l), r(r), mn(mn), cov(cov), add(add) {}
} tree[SIZE << 2];
void push_up(int i)
{
tree[i].mn = min(tree[ls(i)].mn, tree[rs(i)].mn);
}
void update(int i, int cov, int add)
{
if (cov != -1)
{
tree[i].add = 0;
tree[i].mn = cov;
tree[i].cov = cov;
}
tree[i].add += add;
tree[i].mn += add;
}
void push_down(int i)
{
if (!tree[i].cov)
return;
update(ls(i), tree[i].cov, tree[i].add);
update(rs(i), tree[i].cov, tree[i].add);
tree[i].cov = -1;
tree[i].add = 0;
}
void build(int l, int r, int i)
{
tree[i].l = l, tree[i].r = r;
if (l == r)
return;
int mid = (l + r) >> 1;
build(l, mid, ls(i));
build(mid + 1, r, rs(i));
push_up(i);
}
void cover(int l, int r, int i, int k)
{
if (l > r)
return;
if (tree[i].l >= l && tree[i].r <= r)
{
update(i, k, 0);
return;
}
push_down(i);
if (tree[ls(i)].r >= l)
cover(l, r, ls(i), k);
if (tree[rs(i)].l <= r)
cover(l, r, rs(i), k);
push_up(i);
}
void add(int l, int r, int i, int k)
{
if (tree[i].l >= l && tree[i].r <= r)
{
update(i, -1, k);
return;
}
push_down(i);
if (tree[ls(i)].r >= l)
add(l, r, ls(i), k);
if (tree[rs(i)].l <= r)
add(l, r, rs(i), k);
push_up(i);
}
int query(int i, int k)
{
if (tree[i].l == tree[i].r)
return tree[i].l;
push_down(i);
if (tree[ls(i)].mn <= k)
return query(ls(i), k);
if (tree[rs(i)].mn <= k)
return query(rs(i), k);
return INF;
}
int cnm(int s, int i)
{
if (tree[i].l == tree[i].r)
return tree[i].mn;
push_down(i);
if (tree[ls(i)].r >= s)
return cnm(s, ls(i));
return cnm(s, rs(i));
}
pir comp(pir a, pir b)
{
if (a.first == b.first)
return a.second < b.second ? a : b;
return a.first > b.first ? a : b;
}
int z[SIZE];
map<int, int> t;
int lst[SIZE];
int main()
{
freopen("seq.in", "r", stdin);
freopen("seq.out", "w", stdout);
int n, k, d;
cin >> n >> k >> d;
for (int i = 1; i <= n; i++)
{
cin >> x[i];
if (d == 0)
continue;
y[i] = (x[i] % d + d) % d, z[i] = floor(x[i] * 1.0 / d);
lst[i] = t[x[i]];
t[x[i]] = i;
}
if (d == 0)
{
pir ans = {0, INF};
int l = 0, r = 0;
for (int i = 1; i <= n; i++)
{
if (x[i] != x[i - 1])
l = i;
ans = comp(ans, {i - l + 1, l});
}
cout << ans.second << " " << ans.second + ans.first - 1;
return 0;
}
build(1, n, 1);
int last = 1;
pir ans = {0, INF};
for (int i = 1; i <= n; i++)
{
if (y[i] != y[i - 1])
{
cover(1, i - 1, 1, INF);
stmn.clear();
stmx.clear();
}
cover(1, lst[i], 1, INF);
cover(i, i, 1, 0);
add(1, i, 1, -1);
add(stmn.top() + 1, i, 1, z[i] - z[stmn.top()]);
add(stmx.top() + 1, i, 1, z[stmx.top()] - z[i]);
while (!stmn.empty() && z[i] < z[stmn.top()])
add(stmn.sec() + 1, stmn.top(), 1, z[stmn.top()] - z[i]), stmn.pop();
while (!stmx.empty() && z[i] > z[stmx.top()])
add(stmx.sec() + 1, stmx.top(), 1, z[i] - z[stmx.top()]), stmx.pop();
int l = query(1, k - 1);
ans = comp(ans, make_pair(i - l + 1, l));
stmn.push(i);
stmx.push(i);
}
cout << ans.second << " " << ans.second + ans.first - 1;
return 0;
}