• 2022杭电多校联赛第八场 题解

    比赛传送门
    作者： fn

    目录

    签到题

    1004题 Quel’Thalas / 奎尔萨拉斯（幻方）

    题目大意
    有一个幻方，其中包含二维平面上的所有点，其坐标为 [ 0 , n ] [0,n] [0,n] 内的整数。
    他能在平面上画几条直线。每条线将覆盖其上的所有点。这些线没有端点，并且在两个方向上延伸到无穷远。
    还有一条特殊规则：他的线不能经过点 ( 0 , 0 ) (0,0) (0,0) 。

    他需要画多少条线才能覆盖除 ( 0 , 0 ) (0,0) (0,0) 之外的幻方的所有点？

    考察内容
    签到

    分析

    斜着切就可以。答案是 2 n 2n 2n 。

    #include 
#define endl '\n'
using namespace std;
signed main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    while(t--){
		int n;
		cin>>n;
        cout<<2*n<<endl;
	}
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    1001题 Theramore / 塞拉摩岛（翻转字符串）

    题目大意
    给定一个 01 序列，可以翻转奇数长度的区间任意次。求字典序最小的结果。

    考察内容
    思维

    分析
    每次翻转不能改变下标的奇偶性，所以统计奇偶下标的0和1的个数，按照字典序最小的情况放置即可。

    #include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e5+5;
ll n,m,a[N];
string s;
char ch[N];

int main(){ 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		ll numodd[2]={0};
		ll numeven[2]={0};
		
		cin>>s;
		ll len=s.size();
		
		for(int i=0;i<len;i+=2){
			if(s[i]=='0'){
				numeven[0]++;
			}
			else{
				numeven[1]++;
			}
		}
		for(int i=1;i<len;i+=2){
			if(s[i]=='0'){
				numodd[0]++;
			}
			else{
				numodd[1]++;
			}
		}
		
		for(int i=len-1;i>=0;i--){
			if(i%2==1){
				if(numodd[1]>0){
					ch[i]='1';
					numodd[1]--;
				}
				else{
					ch[i]='0';
				}
			}
			else{
				if(numeven[1]>0){
					ch[i]='1';
					numeven[1]--;
				}
				else{
					ch[i]='0';
				}
			}
		}
		for(int i=0;i<=len-1;i++){
			cout<<ch[i];
		}
		cout<<endl;
	}
	return 0;
}

    • 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

    基本题

    1011题 Stormwind / 暴风城（分割矩形）

    题目大意

    给定一个 n ∗ m n*m n∗m 的长方形，沿水平或竖直方向画若干条线，每条线的两端点都在长方形的边界上。要求这些线划分出的每个小长方形面积都 ≥ k ≥k ≥k 。
    求最多可以画几条线。

    考察内容
    贪心

    分析
    贪心策略：

    1. 让一边切的次数尽可能多，然后再去切另一边。
    2. 尽可能把每块切成一样的。

    考虑两边（先切一边，后切另外一边），取两者的最大值即可。
    时间复杂度 O ( 1 ) O(1) O(1) 。

    #include
#define ll long long
#define int long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
ll n,m,k;

signed main(){ 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>n>>m>>k;
		
		if(n*m<k){ 
			cout<<0<<endl;
			continue;
		}
		
		ll ans=0;
		
		if(m>=k){ // 切成条 
			ll cnt=n-1;
			cnt+=m/k-1;
			ans=max(ans,cnt);
		}
		else{ // m
			ll d=(k+m-1)/m; 
			ll cnt=n/d-1;
			ans=max(ans,cnt);
		} 
		
		if(n>=k){ // 从另外一边切
			ll cnt=m-1;
			cnt+=n/k-1;
			ans=max(ans,cnt);
		}
		else{ // n
			ll d=(k+n-1)/n; 
			ll cnt=m/d-1;
			ans=max(ans,cnt);
		} 
		cout<<ans<<endl;
	}
	return 0;
}
/*
1
7 6 14

2


1
5 4 5

3

*/ 

    • 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

    1008题 Orgrimmar / 奥格瑞玛（树上最大分离集）

    题目大意
    求一棵树的最大分离集的大小。
    分离集：一个顶点集，其中所有顶点的度数 ≤ 1 \leq1 ≤1 。

    考察内容
    树形dp

    分析
    状态：
    对于每个结点 i i i ：
    f [ 2 ] [ i ] f[2][i] f[2][i] : 选 i i i 且下面有选的答案。
    f [ 1 ] [ i ] f[1][i] f[1][i] : 选 i i i 且下面没选的答案。
    f [ 0 ] [ i ] f[0][i] f[0][i] : 不选 i i i 时的答案。

    转移：
    跑一遍dfs。

    void dfs(int x,int fa){
	ll sum0=0;
	ll sum=0;
	for(auto a1:g[x]){ // 遍历子树 
		if(a1==fa)continue;
		
		dfs(a1,x); 
		sum0+=f[0][a1]; // 下面没选
		sum+=max(f[2][a1],max(f[1][a1],f[0][a1]));
	}
	f[1][x]=sum0+1; // 选这个点，且下面没选 
	f[0][x]=sum; // 不选这个点 
	
	ll sum2=-1e18; 
	for(auto a1:g[x]){ // 遍历子树，子树可以选1个下面没选的 
		if(a1==fa)continue;
		
		sum2=max(sum2,sum0-f[0][a1]+f[1][a1]);
	}
	f[2][x]=sum2+1; 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    完整代码：

    #include
#define ll long long
#define int long long 
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
ll read(ll &n){
	char ch=' '; ll q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
}
const int N=5e5+5;
ll n;
vector<ll> g[N];

ll f[3][N]; // f[2]:选i且下面有选的答案 f[1]:选i且下面没选的答案  f[0]:不选i时的答案 

void init(ll n){ // 初始化 
	for(int i=0;i<=n;i++){
		f[0][i]=f[1][i]=f[2][i]=0;  
		g[i].clear();
	}
}

void dfs(int x,int fa){
	ll sum0=0;
	ll sum=0;
	for(auto a1:g[x]){ // 遍历子树 
		if(a1==fa)continue;
		
		dfs(a1,x); 
		sum0+=f[0][a1]; // 下面没选
		sum+=max(f[2][a1],max(f[1][a1],f[0][a1]));
	}
	f[1][x]=sum0+1; // 选这个点，且下面没选 
	f[0][x]=sum; // 不选这个点 
	
	ll sum2=-1e18; 
	for(auto a1:g[x]){ // 遍历子树，子树可以选1个下面没选的 
		if(a1==fa)continue;
		
		sum2=max(sum2,sum0-f[0][a1]+f[1][a1]);
	}
	f[2][x]=sum2+1; 
}

signed main(){ // AC
    int size(512<<20);  // 512M,536870912
	__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size)); // 给栈扩容 

	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; read(t);
	while(t--){
		read(n);
		init(n);
		for(int i=1;i<=n-1;i++){
			ll u0,v0;
			read(u0); read(v0);
			g[u0].push_back(v0);
			g[v0].push_back(u0);
		}
	
		int root=1;
		dfs(root,0);
		
		ll ans=max(f[0][root],f[1][root]);
		ans=max(ans,f[2][root]);
		
		cout<<ans<<endl;
	}
    exit(0);
}
/*
1
10
1 2
2 4
3 2
5 3
6 4
7 5
8 3
9 8
10 7


1
7
1 3
2 3
3 4
4 5
5 6
5 7

正确输出：
5

*/ 

    • 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

    进阶题

    1007题 Darnassus / 达纳苏斯（最小生成树）

    题目大意
    给定一个排列 p p p ，把每个位置视为点，建一个无向图， i , j i,j i,j 之间的边权为 ∣ i − j ∣ ∗ ∣ p i − p j ∣ |i−j|∗|pi−pj| ∣i−j∣∗∣pi−pj∣ 。
    求这个图的最小生成树。

    考察内容
    最小生成树，Kruskal 算法，并查集

    分析
    1007题

    #include
using namespace std;
typedef long long ll;
const int MAXN = 50005;

template <typename T> inline void read(T &WOW) {
    T x = 0, flag = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') flag = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    WOW = flag * x;
}

int n, p[MAXN], pos[MAXN], ufs[MAXN];

int getf(int x) {
    return (ufs[x] == x)? x : ufs[x] = getf(ufs[x]);
}

struct Edge {
    int u, v, nxt;
} e[MAXN * 460];
int first[MAXN], eCnt;

inline void AddEdge(int w, int u, int v) {
    e[++eCnt].u = u;
    e[eCnt].v = v;
    e[eCnt].nxt = first[w];
    first[w] = eCnt;
}

void solve() {
    read(n);
    for (int i = 1; i <= n; ++i) {
        read(p[i]);
        pos[p[i]] = i;
        ufs[i] = i;
        first[i] = 0;
    }
    eCnt = 0;
    int m = sqrt(n);
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= i + m && j <= n; ++j) {
            int tmp = (j - i) * abs(p[j] - p[i]);
            if (tmp < n) {
                AddEdge(tmp, i, j);
            }
            tmp = (j - i) * abs(pos[j] - pos[i]);
            if (tmp < n) {
                AddEdge(tmp, pos[i], pos[j]);
            }
        }
    }
    ll ans = 0;
    int cnt = n - 1;
    for (int i = 1; i < n; ++i) {
        for (int j = first[i]; j; j = e[j].nxt) {
            int u = getf(e[j].u), v = getf(e[j].v);
            if (u == v) continue;
            ufs[u] = v;
            ans += i;
            --cnt;
        }
        if (cnt == 0) break;
    }
    printf("%lld\n", ans);
}

int main() {
    int T; read(T);
    while (T--) {
        solve();
    }
    return 0;
}

    • 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

    1005题 Ironforge / 铁炉堡（铁炉堡的地铁）

    题目大意

    给定一条 n n n 个顶点的链，每个点上有一个数，每条边上有一个质数。
    带着一个空背包从某个点出发，走到一个点上可以把它上面数字的所有质因子放进背包，一条边如果背包里有那个质数就可以走。允许多次通过每个顶点和每条边。

    m m m 次询问，每次回答点 x x x 是否可以到达点 y y y 。

    2 ≤ n , m ≤ 2 × 1 0 5 2≤n,m≤2×10^5 2≤n,m≤2×105

    考察内容
    双指针，二分，质数筛，复杂度优化

    分析

    预处理每个点能走到的范围。

    2 ≤ n , m ≤ 2 × 1 0 5 2≤n,m≤2×10^5 2≤n,m≤2×105 ，要做到 O ( n l o g n ) O(nlogn) O(nlogn) 。

    两个关键的地方：

    1. 先从右往左枚举一遍只向右走的最大范围，再从左往右枚举向左右两边走的范围。

    2. 判断一个范围内是否存在某个质因子的方法：对每个质因子维护一个 vector 存它出现的所有位置，在 vector 上二分。

    #include
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
using namespace std;
typedef long long ll;
const int MAXN = 200005;

template <typename T> inline void read(T &WOW) {
    T x = 0, flag = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') flag = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    WOW = flag * x;
}

int n, m, a[MAXN], b[MAXN], clean[MAXN], tim;
int L[MAXN], R[MAXN];

int pr[MAXN], pcnt, vis[MAXN], low[MAXN];
vector<int> pos[MAXN];

bool Check(int p, int l, int r) { // 询问在区间[l,r]是否有质数p 
    if (!pos[p].size() || pos[p].back() < l) return 0;
    int x = *lower_bound(pos[p].begin(), pos[p].end(), l);
    return (x <= r);
}

void sieve() {
    n = 200000;
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            pr[++pcnt] = i;
            low[i] = i;
        }
        for (int j = 1; j <= pcnt && i * pr[j] <= n; ++j) {
            vis[i * pr[j]] = 1;
            low[i * pr[j]] = pr[j];
            if (i % pr[j] == 0) break;
        }
    }
}

void solve() {
    read(n); read(m); // 读入数据 
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
    }
    for (int i = 1; i < n; ++i) {
        read(b[i]);
    }
    
    for (int i = 1; i <= n; ++i) {
        int x = a[i];
        while (x > 1) {
            int nowp = low[x];
            while (nowp == low[x]) {
                x /= nowp;
            }
            if (clean[nowp] != tim) {
                pos[nowp].clear();
                clean[nowp] = tim;
            }
            pos[nowp].push_back(i);
        }
    }
    ++tim;
    
	for (int i = n; i >= 1; --i) { // 先从右往左枚举
        R[i] = i;
        while (R[i] < n && Check(b[R[i]], i, R[i])) {
            R[i] = R[R[i] + 1];
        }
    }
    for (int i = 1; i <= n; ++i) { // 再从左往右枚举
        if (i > 1 && R[i - 1] >= i) {
            if (Check(b[i - 1], i, R[i])) {
                L[i] = L[i - 1];
                R[i] = R[i - 1];
            } else {
                L[i] = i;
            }
        } else {
            L[i] = i;
            bool flag = 1;
            while (flag) { // 上一轮有在更新 
            	flag = 0;
                while (R[i] < n && Check(b[R[i]], L[i], R[i])) { // 向右更新 
                    flag = 1;
                    R[i] = R[R[i] + 1];
                }
                while (L[i] > 1 && Check(b[L[i] - 1], L[i], R[i])) { // 向左更新 
                    flag = 1;
                    L[i] = L[L[i] - 1];
                }
            }
        }
    }

    for (int i = 1, x, y; i <= m; ++i) { // 处理询问 
        read(x); read(y);
        if (L[x] <= y && y <= R[x]) {
            puts("Yes");
        } else {
            puts("No");
        }
    }
}

int main() {
    sieve(); // 筛一下质数 
    int T; read(T);
    while (T--) {
        solve();
    }
    return 0;
}

    • 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
  • 相关阅读:
    Codeforces Round #788 (Div. 2)
    Swift - swiftc
    背包问题---怎么选取物品，可以使得背包装的物品价值最大？
    关于Netty的一些问题
    造！又有新的生产力语言了「GitHub 热点速览 v.22.30」
    使用js搭建简易的WebRTC实现视频直播
    使用python操作mysql,，SQL注入问题, 视图, 触发器 ,事务(掌握重点), 存储过程,索引 问题
    vue3 webpack打包流程及安装 （1）
    速卖通跨境智星靠谱吗？还有其他隐藏费用吗？
    mysql InnoDB 事务的实现原理
  • 原文地址：https://blog.csdn.net/weixin_51937688/article/details/126290580