const int N = 3e4 + 10, M = N * 2;
class Solution {
public:
int deg[N], time[N];
int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
int n = coins.size();
vector<vector<int>> e(n);
for(auto t: edges)
{
int x = t[0], y = t[1];
e[x].push_back(y);
e[y].push_back(x);
deg[x] ++ ;
deg[y] ++ ;
}
queue<int> q;
for(int i = 0;i < n;i ++ )
if(deg[i] == 1 && coins[i] == 0)
q.push(i);
while(q.size())
{
int t = q.front();
q.pop();
for(auto p: e[t])
if( -- deg[p] == 1 && coins[p] == 0)
q.push(p);
}
for(int i = 0;i < n;i ++ )
if(deg[i] == 1 && coins[i] == 1)
q.push(i);
if(q.size() <= 1) return 0;
while(q.size())
{
int t = q.front();
q.pop();
for(auto p: e[t])
{
if( -- deg[p] == 1)
{
time[p] = time[t] + 1;
q.push(p);
}
}
}
int ans = 0;
for(auto v: edges)
{
int x = v[0], y = v[1];
if(time[x] >= 2 && time[y] >= 2) ans += 2;
}
return ans;
}
};
活动打卡代码
LeetCode 2603. 收集树中金币
前言：WA了无数次，记录下坑点（太菜了还是qwq）
思路：
1. 对字符串U进行字符串哈希的求解。
2. 枚举每个字符，判断当这个字符是被插入的那个字符时，剩余的串能否满足前(n - 1) / 2个字符等于剩余字符。
3. 再求剔除一个字符后，新的字符串分成左右两半后各自的哈希值，具体情况如下：
len = n - 1 >> 1; // S串的长度
i > len:
左边串：h[len]
右边串：(h[i - 1] - h[len + 1 - 1] * p[i - len - 1]) * p[n - i] + (h[n] - h[i + 1 - 1] * p[n - i])
i <= len:
右边串：h[n] - h[n - len + 1 - 1] * p[len]
左边串：h[i - 1] * p[len + 1 - i - 1 + 1] + (h[len + 1] - h[i + 1 - 1] * p[len - i + 1])
坑点：
题目的“如果字符串S不唯一”这句话，表明了对于一个给定的U串，只有S在不同的情况下并且仍能组成U才算不唯一，例如像”AAA”，可以发现枚举三个位置后都可以满足构造方式，即S = 'A'，我一开始没有注意这个点，就只是将左右串出现多次哈希值相同的时cnt ++，这样判断是否唯一是错误的（在前面的例子里，就会使得cnt = 3，得出不唯一的错误结论）。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
const int N = 2e6 + 10, P = 131;
int n;
char s[N];
ULL h[N], p[N];
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
cin >> n >> s + 1;
p[0] = 1;
for(int i = 1;i <= n;i ++ )
{
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + s[i];
}
int k = 0;
int len = n / 2; // 向下取整
ULL last = 0;
for(int i = 1;i <= n;i ++ )
{
ULL l, r;
if(i > len)
{
l = get(1, len);
r = get(len + 1, i - 1) * p[n - i] + get(i + 1, n);
}
else
{
r = get(n - len + 1, n);
l = get(1, i - 1) * p[len - i + 1] + get(i + 1, len + 1);
}
if(l == r)
{
if(!last) last = l;
else if(last != l)
{
puts("NOT UNIQUE");
return 0;
}
if(!k) k = i;
}
}
if(!last || n % 2 == 0)
{
cout << "NOT POSSIBLE" << endl;
return 0;
}
for(int i = 1, j = 0;j < len;i ++ )
if(i == k) continue;
else
{
cout << s[i];
j ++ ;
}
return 0;
}
二分图最大匹配模板题：
根据题意知道如果有一道题无法坐下去就算失败，所以要在模板上增加break
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n, m;
int h[N], e[N * 2], ne[N * 2], idx;
bool st[N];
int match[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool dfs(int u)
{
for(int i = h[u];~i;i = ne[i])
{
int j = e[i];
if(st[j]) continue;
st[j] = true;
if(!match[j] || dfs(match[j]))
{
match[j] = u;
return true;
}
}
return false;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof(h));
for(int i = 1;i <= m;i ++ )
{
int a, b;
cin >> a >> b;
add(i, a);
add(i, b);
}
int ans = 0;
for(int i = 1;i <= m;i ++ )
{
memset(st, 0, sizeof(st));
if(dfs(i)) ans ++ ;
else break;
}
cout << ans << endl;
vector<PII> v;
for(int i = 0;i < n;i ++ )
if(match[i])
v.push_back({match[i], i});
sort(v.begin(), v.end(), [&](PII a, PII b){
return a.first < b.first;
});
for(auto [x, y]: v)
cout << y << endl;
return 0;
}
