AC不了怎么办

3.6万

GGBoy-
CHN_OMoon
bongin

acwing_29853
86_4

DS_Tape

forhjh
32小时摸鱼选手
hbq
VFmissile
3423
WA自由人
Ainzs.
mushan_xiong

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;
}
};


finish

finish

finish

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])


#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;
}


#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];

{
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;
}
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;
}