SamuelXuch's blog
提高组1题解
SamuelXuch LV 6 MOD @ 2022-11-13 22:47:48

提高组1

序列

题解

题意：求最长数字接龙。

$\text{Subtask1}$ ：暴搜

$\text{Subtask2}$ ：各种数字乱搞+优化

$\text{Subtask3}$ ：分解因数之后，以素数为点，合数为边，建图，对所得 $DAG$ 进行 $DP$ 即可。

出题意图：送分。考察因数分解与建图、拓扑排序的能力。

期望得分 $100$ 分。

标准代码

C++

#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int Mn=100005;
struct Edge{int to,next;}w[Mn];
int cnt=0,h[Mn];
struct node{int a,b;}a[Mn];
int n,m=0,p[1005],vst[1005],b[Mn],Rd[Mn],f[Mn];
void AddEdge(int x,int y){w[++cnt]=(Edge){y,h[x]};h[x]=cnt;Rd[y]++;}
void init(){
	 int i,j,x;
     for(i=2;i<=1000;i++){
    	if(!vst[i])p[++p[0]]=i;
    	for(j=i;j<=1000;j+=i)vst[j]=1;
     }
     scanf("%d",&n);
     for(i=1;i<=n;i++){
    	scanf("%d",&x);
    	for(j=1;j<=p[0];j++)if(x%p[j]==0)break;
    	a[i].a=p[j];a[i].b=x/p[j];
    	if(a[i].a>a[i].b)swap(a[i].a,a[i].b);
    	b[++m]=a[i].a;b[++m]=a[i].b;
     }
     sort(b+1,b+1+m);
     m=unique(b+1,b+1+m)-b-1;
     for(i=1;i<=n;i++){
     	a[i].a=lower_bound(b+1,b+1+m,a[i].a)-b;
     	a[i].b=lower_bound(b+1,b+1+m,a[i].b)-b;
     	AddEdge(a[i].a,a[i].b);
     }
}
void solve(){
	 int i,j,x,y,ans=0;
	 queue<int>q;
	 for(i=1;i<=m;i++){
	   f[i]=-0x7fffffff/2;
	   if(!Rd[i]){q.push(i);f[i]=0;}
	 }
	 while(!q.empty()){
	 	x=q.front();q.pop();
	 	for(j=h[x];j;j=w[j].next){
	 		y=w[j].to;
	 		Rd[y]--;f[y]=max(f[x]+1,f[y]);
	 		if(!Rd[y])q.push(y);
	 	}
	 }
	 for(i=1;i<=m;i++)ans=max(ans,f[i]);
	 printf("%d\n",ans);
}
int main(){
    init();
    solve();
    return 0;
}

生成最小树

题解

先做如下定义，在给出的生成树中的边，我们称为树边。不在生成树中的为非树边。

如何才能让给定的生成树成为最小生成树呢？

对于非树边 $E(u,v)$ ，对应生成树上的一条路径 $(u->v)$ 。如果 $E(u,v)$ 的边权小于这条路径上的某条边，那我们选择 $E(u,v)$ ，而去掉那条边，就会得到一棵新的生成树。并且这棵生成树的权值和更小。因此对于生成树上 $(u->v)$ 每一条边的边权，都要小于等于 $E(u,v)$ 才行。

所以我们需要修改路径上树边权值，使得所有非树边 $E(i,j)$ 的权值大于生成树上路径 $(i->j)$ 的每条边的权值。

这种暴力更新的方法，最坏复杂度可能是平方的。我们对非树边按照权值从小到大排序。先处理权值小的，再处理权值大的。这样如果某个边的权值已经被修改过，那么后面的更新就不用重复修改了。

这样的话，每条边只被处理一次。之后我们可以利用路径压缩，来解决边被多次枚举的问题。复杂度 $O(mlogm)$ 。因为需要对所有非树边进行排序。

标准代码

C++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10010, MAXM = 200010;
int vis[MAXN], pos = 0;
map<pair<int, int>, int> MP;
vector<int> notTree;

ll ans = 0;

struct edge {
    int from, to, weight;
    bool inTree;
} Edges[MAXM];

struct node {
    int parent, weight, height;
    vector<int> childs;
    void set(int w) {
        if(weight > w) {
            ans += weight - w;
            weight = w;
        }
    }
} Nodes[MAXN];

void add(int a, int b, int weight) {
    Edges[pos].weight = weight; MP[make_pair(a, b)] = pos;
    Edges[pos].from = a; Edges[pos].to = b; 
    Nodes[a].childs.push_back(pos); pos++;
    Edges[pos].weight = weight; MP[make_pair(b, a)] = pos;
    Edges[pos].from = b; Edges[pos].to = a; 
    Nodes[b].childs.push_back(pos); pos++;
}

bool cmp(int a, int b) {
    return Edges[a].weight < Edges[b].weight;
}

void DFS(int x, int height) {
    if(vis[x]) return;
    vis[x] = true;
    for(int i = 0; i < Nodes[x].childs.size(); i++) {
        int eid = Nodes[x].childs[i];
        int to = Edges[eid].to;
        
        if(Edges[eid].inTree) {
            if(vis[to]) continue;
            Nodes[to].weight = Edges[eid].weight;
            Nodes[to].height = height + 1; 
            Nodes[to].parent = x;
            DFS(to, height + 1);
        }
        else if(to < x)
            notTree.push_back(eid); //非树边集合
    }
}

int un(int a, int b, int w) {
    if(a == b) return a;
    node na = Nodes[a], nb = Nodes[b];
    int p;
    if(na.height == nb.height) {
        Nodes[a].set(w); Nodes[b].set(w);
        p = un(na.parent, nb.parent, w);
    }
    else if(na.height > nb.height) {
        Nodes[a].set(w); 
        p = un(na.parent, b, w);
    }
    else {
        Nodes[b].set(w);
        p = un(a, nb.parent, w);
    }
    
    if(a != p)
        Nodes[a].parent = p;
    if(b != p)
        Nodes[b].parent = p;
        
    return p;
}

int main() {
    int n, m, u, v, weight;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> weight;
        add(u, v, weight);
    }

    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        Edges[MP[make_pair(u, v)]].inTree = true;
        Edges[MP[make_pair(v, u)]].inTree = true;
    }
    
    DFS(1, 0);
    sort(notTree.begin(), notTree.end(), cmp);
    
    for(int i = 0; i < notTree.size(); i++) {
        edge e = Edges[notTree[i]];
        un(e.from, e.to, e.weight);
    }

    cout << ans << endl;
    return 0;
}

互质序列

题解

由于 $A$ 与 $B$ 之间的差不超过 $100$ ，因此他们所拥有的的共同的质因子，也不会超过 $100$ ，而 $100$ 以内的质数共有 $25$ 个，因此考虑状压 $DP$ 。

尽管 $A,B$ 的范围有 $1e18$ ，但我们并不需要知道每个数所有的质因子，只需要得到 $100$ 以内的质因子，就可以进行状态转移了。 $DP[i][s]$ 表示最大的数不超过 $A+i$ ，对应的质因子选择的状态为 $s$ 的序列数量。

每加入一个新的数 $i$ ，有选和不选 $2$ 种可能：

如果选择 $i$ ，则可以从 $i-1$ 的所有不包括 $i$ 的质因子的状态做状态转移（即 $i$ 的补集的所有子集）。

如果不选择 $i$ ，则直接从 $i-1$ 转移到 $i$ 。

这样可以得到 $70$ 分。

考虑到大于 $50$ 的质因子，某些只出现 $1$ 次，因此并不需要记录状态，因此状态数量并不需要到 $2^{25}$ ，剔除掉只出现 $1$ 次的质因子，可以得到 $100$ 分

标准代码

C++

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int primes[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 };
int cnt[25];
ll dp[1 << 25];
int main() {
    ll a, b;
	cin >> a >> b;
	dp[0] = 1;
	vector<int> p;
	for (ll i = a; i <= b; i++) {
	    for (int j = 0; j < 25; j++) 
	        if(i % primes[j] == 0)
	            cnt[j]++;
	}
	for (int j = 0; j < 25; j++) 
	    if(cnt[j] > 1)
	        p.push_back(primes[j]);
	ll mul = 1;
	for (ll i = a; i <= b; i++) {
		int s = 0;
		for (int j = 0; j < p.size(); j++)
			if (i % p[j] == 0)
			    s |= (1 << j);
		if(s == 0) {
		    mul *= 2;
		    continue;
		}
		int S = ((1 << p.size()) - 1) ^ s;
		for (int j = S; j; j = (j - 1) & S)
			dp[j | s] += dp[j];
		dp[s] += dp[0];
	}
	ll ans = 0;
	for (int i = 0; i < (1 << p.size()); i++)
		ans += dp[i];
	cout << ans * mul - 1 << endl;
	return 0;
}

鬼鬼的序列

题解

我们先将序列拆分（ $(a[i]%D+D)%D$ 相等的连续一段为一组），每组单独处理。

先对 $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$ 同理。

标准代码

C++

#include<cstdio>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 200005;
int n, K, D, Ans, AnsL, AnsR = -1, a[MAXN], b[MAXN], A[MAXN], Hsh[MAXN], Min[MAXN << 2], Add[MAXN << 2];
#include<cctype>
int read() {
	int ret = 0; char ch = getchar(); bool f = 1;
	for (; !isdigit(ch); ch = getchar()) f ^= !(ch ^ '-');
	for (; isdigit(ch); ch = getchar()) ret = ret * 10 + ch - 48;
	return f ? ret : -ret;
}
void PushUp(int rt) { Min[rt] = min(Min[rt << 1], Min[rt << 1 | 1]); }
void PushDown(int rt) {
	if (!Add[rt]) return;
	Add[rt << 1] += Add[rt], Add[rt << 1 | 1] += Add[rt];
	Min[rt << 1] += Add[rt], Min[rt << 1 | 1] += Add[rt], Add[rt] = 0;
}
void Insert(int rt, int L, int R, int l, int r, int p) {
	if (l <= L && R <= r) { Add[rt] += p, Min[rt] += p; return; }
	PushDown(rt); int mid = (R + L) >> 1;
	if (l <= mid) Insert(rt << 1, L, mid, l, r, p);
	if (r > mid) Insert(rt << 1 | 1, mid + 1, R, l, r, p);
	PushUp(rt);
}
int Query(int rt, int L, int R, int p) {
	if (Min[rt] > p) return 0;
	if (L == R) return L;
	PushDown(rt); int mid = (R + L) >> 1;
	return Min[rt << 1] <= p ? Query(rt << 1, L, mid, p) : Query(rt << 1 | 1, mid + 1, R, p);
}
void Fnd(int rt, int L, int R, int l, int r, int p) {
	if (l <= L && R <= r) { if (!Ans) Ans = Query(rt, L, R, p); return; }
	int mid = (R + L) >> 1; PushDown(rt);
	if (l <= mid) Fnd(rt << 1, L, mid, l, r, p);
	if (r > mid) Fnd(rt << 1 | 1, mid + 1, R, l, r, p);
}
void Build(int rt, int L, int R) {
	Add[rt] = Min[rt] = 0;
	if (L == R) return; int mid = (R + L) >> 1;
	Build(rt << 1, L, mid); Build(rt << 1 | 1, mid + 1, R);
}
int s1[MAXN], Top1, s2[MAXN], Top2;
void Work(int Left) {
	s1[Top1 = 1] = s2[Top2 = 1] = 0; Build(1, 1, *A);
	for (int i = 1, lst = 1; i <= *A; i++) {
		for (; Top1 > 1 && A[s1[Top1]] <= A[i]; Top1--) Insert(1, 1, *A, s1[Top1 - 1] + 1, s1[Top1], A[i] - A[s1[Top1]]); s1[++Top1] = i;
		for (; Top2 > 1 && A[s2[Top2]] >= A[i]; Top2--) Insert(1, 1, *A, s2[Top2 - 1] + 1, s2[Top2], A[s2[Top2]] - A[i]); s2[++Top2] = i;
		Insert(1, 1, *A, i, i, i);
		int L = lst = max(lst, Hsh[b[i + Left - 1]] + 1), R = i; Hsh[b[i + Left - 1]] = i;
		Ans = 0; Fnd(1, 1, *A, L, R, i + K);
		if (AnsR - AnsL + 1 < i - Ans + 1) AnsL = Left + Ans - 1, AnsR = Left + i - 1;
	}
	for (int i = 1; i <= *A; i++) Hsh[b[i + Left - 1]] = 0;
}
void Updata(int x, int y) {
	if (y - x < AnsR - AnsL) return;
	if (y - x > AnsR - AnsL) AnsR = y, AnsL = x; else if (x < AnsL) AnsL = x, AnsR = y;
}
int main() {
	n = read(); K = read(), D = read();
	for (int i = 1; i <= n; i++) Hsh[i] = a[i] = read();
	sort(Hsh + 1, Hsh + 1 + n); int Len = unique(Hsh + 1, Hsh + 1 + n) - Hsh - 1;
	for (int i = 1; i <= n; i++) b[i] = lower_bound(Hsh + 1, Hsh + 1 + Len, a[i]) - Hsh;
	memset(Hsh, 0, sizeof(Hsh));
	if (D == 0) {
		for (int i = 1, j = 1; i <= n; i = j)
			for (j = i + 1; j <= n && a[j] == a[i]; j++) Updata(i, j);
	}
	else {
		for (int l = 1, r; l <= n; l = r) {
			for (r = l + 1; r <= n && (a[l] % D + D) % D == (a[r] % D + D) % D; r++); *A = 0;
			for (int i = l; i < r; i++) A[++ * A] = a[i] / D; Work(l);
		}
	}
	printf("%d %d\n", AnsL, AnsR);
	return 0;
}

提高组1题解

提高组1

序列

题解

标准代码

C++

生成最小树

题解

标准代码

C++

互质序列

题解

标准代码

C++

鬼鬼的序列

题解

标准代码

C++

Status

Development

Support

提高组1题解

提高组1

序列

题解

标准代码

C++

生成最小树

题解

标准代码

C++

互质序列

题解

标准代码

C++

鬼鬼的序列

题解

标准代码

C++

Status

Development

Support

Don't have an account?

SIGN IN