这里的坑不少

女生是负数，数组下标有负数，所以要先变成正数,但是直接并查集会出现男生女生重合，编号相同，所以要把女生映射到+n上，这样就完美



```cpp
#include <iostream>
#include <vector>
using namespace std;

const int maxn = 500000;
int father[maxn];

int find(int x) {
    if (father[x] != x) {
        father[x] = find(father[x]);
    }
    return father[x];
}

void unionn(int x, int y) {
    int root_x = find(x);
    int root_y = find(y);
    if (root_x != root_y) {
        father[root_y] = root_x;
    }
}

int main() {
    int n, m, p, q;
    cin >> n >> m >> p >> q;

    for (int i = 1; i <= n + m; ++i) {
        father[i] = i;
    }

    for (int i = 1; i <= p; ++i) {
        int a, b;
        cin >> a >> b;
        if (find(a) != find(b)) {
            unionn(a, b);
        }
    }

    for (int i = 1; i <= q; ++i) {
        int a, b;
        cin >> a >> b;
        a *= -1;
        b *= -1;
        if (find(a + n) != find(b + n)) {
            unionn(a + n, b + n);
        }
    }

    int ansm = 0, ansf = 0;

    for (int i = 1; i <= n; ++i) {
        if (find(i) == find(1)) {
            ansm++;
        }
    }

    for (int i = n + 1; i <= n + m; ++i) {
        if (find(i) == find(n + 1)) {
            ansf++;
        }
    }

    int result = min(ansm, ansf);
    cout << result << endl;

    return 0;
}

```

P2078


```go
func (cm *ConsensusModule) persistToStorage() {
	var termData bytes.Buffer
	if err := gob.NewEncoder(&termData).Encode(cm.currentTerm); err != nil {
		log.Fatal(err)
	}
	cm.storage.Set("currentTerm", termData.Bytes())

	var votedData bytes.Buffer
	if err := gob.NewEncoder(&votedData).Encode(cm.votedFor); err != nil {
		log.Fatal(err)
	}
	cm.storage.Set("votedFor", votedData.Bytes())

	var logData bytes.Buffer
	if err := gob.NewEncoder(&logData).Encode(cm.log); err != nil {
		log.Fatal(err)
	}
	cm.storage.Set("log", logData.Bytes())
}


// Submit submits a new command to the CM. This function doesn't block; clients
// read the commit channel passed in the constructor to be notified of new
// committed entries. It returns true iff this CM is the leader - in which case
// the command is accepted. If false is returned, the client will have to find
// a different CM to submit this command to.
func (cm *ConsensusModule) Submit(command interface{}) bool {
	cm.mu.Lock()
	cm.dlog("Submit received by %v: %v", cm.state, command)
	if cm.state == Leader {
		cm.log = append(cm.log, LogEntry{Command: command, Term: cm.currentTerm})
		cm.persistToStorage()
		cm.dlog("... log=%v", cm.log)
		cm.mu.Unlock()
		cm.triggerAEChan <- struct{}{}
		return true
	}

	cm.mu.Unlock()
	return false
}


// RequestVote RPC.
func (cm *ConsensusModule) RequestVote(args RequestVoteArgs, reply *RequestVoteReply) error {
	cm.mu.Lock()
	defer cm.mu.Unlock()
	if cm.state == Dead {
		return nil
	}
	lastLogIndex, lastLogTerm := cm.lastLogIndexAndTerm()
	cm.dlog("RequestVote: %+v [currentTerm=%d, votedFor=%d, log index/term=(%d, %d)]", args, cm.currentTerm, cm.votedFor, lastLogIndex, lastLogTerm)

	if args.Term > cm.currentTerm {
		cm.dlog("... term out of date in RequestVote")
		cm.becomeFollower(args.Term)
	}

	if cm.currentTerm == args.Term &&
		(cm.votedFor == -1 || cm.votedFor == args.CandidateId) &&
		(args.LastLogTerm > lastLogTerm ||
			(args.LastLogTerm == lastLogTerm && args.LastLogIndex >= lastLogIndex)) {
		reply.VoteGranted = true
		cm.votedFor = args.CandidateId
		cm.electionResetEvent = time.Now()
	} else {
		reply.VoteGranted = false
	}
	reply.Term = cm.currentTerm
	cm.persistToStorage()
	cm.dlog("... RequestVote reply: %+v", reply)
	return nil
}

func (cm *ConsensusModule) AppendEntries(args AppendEntriesArgs, reply *AppendEntriesReply) error {

```



raft持久化

```go
func (cm *ConsensusModule) AppendEntries(args AppendEntriesArgs, reply *AppendEntriesReply) error {
	cm.mu.Lock()
	defer cm.mu.Unlock()
	if cm.state == Dead {
		return nil
	}
	cm.dlog("AppendEntries: %+v", args)

	if args.Term > cm.currentTerm {
		cm.dlog("... term out of date in AppendEntries")
		cm.becomeFollower(args.Term)
	}

	reply.Success = false
	if args.Term == cm.currentTerm {
		if cm.state != Follower {
			cm.becomeFollower(args.Term)
		}
		cm.electionResetEvent = time.Now()

		// Does our log contain an entry at PrevLogIndex whose term matches
		// PrevLogTerm? Note that in the extreme case of PrevLogIndex=-1 this is
		// vacuously true.
		if args.PrevLogIndex == -1 ||
			(args.PrevLogIndex < len(cm.log) && args.PrevLogTerm == cm.log[args.PrevLogIndex].Term) {
			reply.Success = true

			// Find an insertion point - where there's a term mismatch between
			// the existing log starting at PrevLogIndex+1 and the new entries sent
			// in the RPC.
			logInsertIndex := args.PrevLogIndex + 1
			newEntriesIndex := 0

			for {
				if logInsertIndex >= len(cm.log) || newEntriesIndex >= len(args.Entries) {
					break
				}
				if cm.log[logInsertIndex].Term != args.Entries[newEntriesIndex].Term {
					break
				}
				logInsertIndex++
				newEntriesIndex++
			}
			// At the end of this loop:
			// - logInsertIndex points at the end of the log, or an index where the
			//   term mismatches with an entry from the leader
			// - newEntriesIndex points at the end of Entries, or an index where the
			//   term mismatches with the corresponding log entry
			if newEntriesIndex < len(args.Entries) {
				cm.dlog("... inserting entries %v from index %d", args.Entries[newEntriesIndex:], logInsertIndex)
				cm.log = append(cm.log[:logInsertIndex], args.Entries[newEntriesIndex:]...)
				cm.dlog("... log is now: %v", cm.log)
			}

			// Set commit index.
			if args.LeaderCommit > cm.commitIndex {
				cm.commitIndex = intMin(args.LeaderCommit, len(cm.log)-1)
				cm.dlog("... setting commitIndex=%d", cm.commitIndex)
				cm.newCommitReadyChan <- struct{}{}
			}
		} else {
			// No match for PrevLogIndex/PrevLogTerm. Populate
			// ConflictIndex/ConflictTerm to help the leader bring us up to date
			// quickly.
			if args.PrevLogIndex >= len(cm.log) {
				reply.ConflictIndex = len(cm.log)
				reply.ConflictTerm = -1
			} else {
				// PrevLogIndex points within our log, but PrevLogTerm doesn't match
				// cm.log[PrevLogIndex].
				reply.ConflictTerm = cm.log[args.PrevLogIndex].Term

				var i int
				for i = args.PrevLogIndex - 1; i >= 0; i-- {
					if cm.log[i].Term != reply.ConflictTerm {
						break
					}
				}
				reply.ConflictIndex = i + 1
			}
		}
	}

	reply.Term = cm.currentTerm
	cm.persistToStorage()
	cm.dlog("AppendEntries reply: %+v", *reply)
	return nil
}
```


```go
// RequestVote RPC.
func (cm *ConsensusModule) RequestVote(args RequestVoteArgs, reply *RequestVoteReply) error {
	cm.mu.Lock()
	defer cm.mu.Unlock()
	if cm.state == Dead {
		return nil
	}
	lastLogIndex, lastLogTerm := cm.lastLogIndexAndTerm()
	cm.dlog("RequestVote: %+v [currentTerm=%d, votedFor=%d, log index/term=(%d, %d)]", args, cm.currentTerm, cm.votedFor, lastLogIndex, lastLogTerm)

	if args.Term > cm.currentTerm {
		cm.dlog("... term out of date in RequestVote")
		cm.becomeFollower(args.Term)
	}

	if cm.currentTerm == args.Term &&
		(cm.votedFor == -1 || cm.votedFor == args.CandidateId) &&
		(args.LastLogTerm > lastLogTerm ||
			(args.LastLogTerm == lastLogTerm && args.LastLogIndex >= lastLogIndex)) {
		reply.VoteGranted = true
		cm.votedFor = args.CandidateId
		cm.electionResetEvent = time.Now()
	} else {
		reply.VoteGranted = false
	}
	reply.Term = cm.currentTerm
	cm.persistToStorage()
	cm.dlog("... RequestVote reply: %+v", reply)
	return nil
}
```

raft两个重要的RPC

任务不会消耗时间，这是一个贪心题目，首先肯定会想到，完成任务并不会消耗时间，但你的时间得大于所需时间。



首先肯定是先完成b更大的因为能获得的时间更多之后能完成的任务也更多，但是所有都按b从大到小排序

做完b大于0的任务后，T=10，剩下2组任务：t1=9，b1=-5；t2=4，b2=-2；显然如果先做第二个的话，会使得第一个任务不能完成

我们可以这样想：对于两组任务t1、b1、t2、b2（其中b1、b2全为负）且当时的时间为T，若先做第一个任务会使得不能做第二个任务而先做第二个任务后还能继续完成第一个任务，则会有

T+b1<t2,T+b2>t1;

移项可得

T<t2-b1,T>t1-b2;

根据不等式的传递性可知

t1-b2<T<t2-b1即t1+b1<t2+b2;

所以我们可以看出按照b+t从大到小的顺序排序可使得答案最优
```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Task {
    int t;
    int b;

    Task(int time, int bonus) : t(time), b(bonus) {}
};

bool comparePositive(const Task& a, const Task& b) {
    return a.t < b.t; // Sort positive bonus tasks by time
}

bool compareNegative(const Task& a, const Task& b) {
    return (a.t + a.b) > (b.t + b.b); // Sort negative bonus tasks by (time + bonus)
}

int main() {
    int Z;
    cin >> Z;

    while (Z--) {
        int n, T;
        cin >> n >> T;

        vector<Task> positive;
        vector<Task> negative;

        for (int i = 0; i < n; i++) {
            int t, b;
            cin >> t >> b;
            Task task(t, b);
            if (b > 0) {
                positive.push_back(task);
            } else {
                negative.push_back(task);
            }
        }

        sort(positive.begin(), positive.end(), comparePositive);
        sort(negative.begin(), negative.end(), compareNegative);

        bool success = true;

        for (const Task& task : positive) {
            if (T > task.t) {
                T += task.b;
            } else {
                success = false;
                break;
            }
        }

        for (const Task& task : negative) {
            if (T > task.t) {
                T += task.b;
            } else {
                success = false;
                break;
            }

            if (T <= 0) {
                success = false;
                break;
            }
        }

        if (success) {
            cout << "+1s" << endl;
        } else {
            cout << "-1s" << endl;
        }
    }

    return 0;
}

```

p3619

并查集（Union-Find），又称不相交集合数据结构，是一种用于处理集合合并和查询问题的数据结构。它通常用于解决元素之间的分组问题，如连通分量问题、集合划分等。



并查集主要支持两种操作：

1. `Union`（合并）：将两个不相交的集合合并成一个集合。
2. `Find`（查询）：确定元素属于哪个集合，或者找到某个集合的代表元素。

通常情况下，并查集包括以下几个基本操作和概念：

- **初始化**：初始化并查集，通常将每个元素视为一个独立的集合，即每个元素是其自身的代表。

- **`Find` 操作**：用于查找元素所属的集合，通常通过沿着父节点链向上查找，直到找到代表元素（根节点）。这个操作通常包括路径压缩，即将路径上的每个节点都直接连接到根节点，以优化查询操作的性能。

- **`Union` 操作**：用于合并两个不相交的集合，通常通过将其中一个集合的根节点指向另一个集合的根节点，或者将其中一个根节点连接到另一个根节点。

在实际应用中，你可以使用一个数组或向量来表示并查集的元素，其中数组的索引表示元素，数组的值表示该元素的父节点。初始状态下，每个元素的父节点是自身。

**应用场景**：
并查集主要用于解决元素的分组问题，例如：

1. **连通分量问题**：在图论中，用于查找图中的连通分量，即图中的不相交子图。
2. **集合划分问题**：将一个元素集合分为若干个不相交的子集。
3. **Kruskal 算法**：用于构建最小生成树。
4. **网络连接问题**：查找网络中的连接关系。
5. **解决运算的等价关系**：如解决数学等价关系问题。
6. **分组问题**：将元素分为不相交的组。

**基本思想**：
并查集的基本思想是用树结构表示集合，每个树的根节点表示集合的代表元素。合并操作即将两个树合并成一个，查询操作即查找元素所在的集合根节点。路径压缩是一种优化方法，通过将查找路径上的每个节点直接连接到根节点，可以显著提高查询操作的效率。

并查集是一种高效且容易实现的数据结构，适用于解决多种实际问题中的分组和连接关系问题。
P3367


```cpp
#include <iostream>
#include <vector>

using namespace std;

vector<int> parent; // Parent array for Union-Find

// Initialize the Union-Find data structure with n elements
void initialize(int n) {
    parent.resize(n);
    for (int i = 0; i < n; i++) {
        parent[i] = i; // Each element is initially its own parent
    }
}

// Find the root (representative) of the set to which element x belongs
int find(int x) {
    if (x == parent[x]) {
        return x; // x is the root of its set
    }
    return parent[x] = find(parent[x]); // Path compression for optimization
}

// Union (merge) the sets to which elements x and y belong
void unite(int x, int y) {
    x = find(x); // Find the root of x's set
    y = find(y); // Find the root of y's set

    if (x != y) {
        parent[x] = y; // Make one of them the parent of the other
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    initialize(n); // Initialize Union-Find with n elements

    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            unite(x - 1, y - 1); // Adjust for 0-based indexing
        } else if (op == 2) {
            int root_x = find(x - 1);
            int root_y = find(y - 1);
            if (root_x == root_y) {
                cout << "Y" << endl;
            } else {
                cout << "N" << endl;
            }
        }
    }

    return 0;
}

```