galileio

1007

TTT320

thejohn

galileio
17天前

galileio
17天前

galileio
20天前
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
char p[N], s[M];
int ne[N];
int main()
{
int n, m;
cin >> n >> p + 1 >> m >> s + 1;
for (int i = 2, j = 0; i <= n; i++)
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j++;
ne[i] = j;
}
for (int i = 1, j = 0; i <= m; i++)
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j++;
if (j == n)
{
printf("%d ", i - n);
j = ne[j];
}
}
}


galileio
26天前
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int s[N];
int find_root(int x)
{
if (s[x] != x) return s[x] = find_root(s[x]);
return s[x];
}
void merge(int x1, int x2)
{
int root1 = find_root(x1), root2 = find_root(x2);
s[root1] = root2;
}
bool check()
{
for (int i = 1; i <= n; i++) s[i] = i;
for (int u = 1; u <= n; u++)
{
for (int j = 1; j < adj[u].size(); j++)
{
if (find_root(v) == find_root(u)) return false;
}
}
return true;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
}
if (check()) puts("Yes");
else puts("No");
}


galileio
1个月前
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], q;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
for (int i = 0; i < n; i++) cin>> a[i];
while (q--)
{
int l = 0, r = n, c;
cin >> c;
while (l < r)
{
int mid = l + r >> 1;
if (a[mid] < c) l = mid + 1;
else r = mid;
}
if (a[l] != c)
{
cout << -1 << ' ' << -1 << endl;
continue;
}
cout << l << ' ';
r = n - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (a[mid] <= c) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}


galileio
1个月前
#include <iostream>
#include <unordered_set>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
string s;
bool check(int val)
{
unordered_set<string> st;
for (int i = 0; i + val <= s.size(); i++)
{
string sub_str = s.substr(i, val);
if (st.count(sub_str)) return false;
st.insert(sub_str);
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin >> s;
int l = 1, r = n;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
}


galileio
1个月前
#include <iostream>
using namespace std;
const int N = 1010;
int s[N][N], d[N][N], n, m, q;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> s[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
d[i][j] = s[i][j] - s[i - 1][j] - s[i][j - 1] + s[i - 1][j - 1];
while (q--)
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
d[x1][y1] += c, d[x1][y2 + 1] -= c, d[x2 + 1][y1] -= c, d[x2 + 1][y2 + 1] += c;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
cout << d[i][j] <<' ';
}
cout << endl;
}
}


galileio
1个月前
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m, d[N], s[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> s[i], d[i] = s[i] - s[i - 1];
while (m--)
{
int l, r, c;
cin >> l >> r >> c;
d[l] += c, d[r + 1] -= c;
}
for (int i = 1; i <= n; i++) d[i] += d[i - 1], cout << d[i] << ' ';
}


galileio
1个月前
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], d[N];
int main()
{
cin >> n;

for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) d[i] = a[i] - a[i - 1];
long long pos = 0, neg = 0;
for (int i = 2; i <= n; i++)
{
if (d[i] > 0) pos += d[i];
else neg += -d[i];
}
cout << max(neg, pos) << endl << abs(neg - pos) + 1 << endl;
}


galileio
1个月前
//最后一步是删除f[i - 1][j] + 1，最后一步是插入f[i][j - 1] + 1，最后一步是替换f[i - 1][j - 1] + 0/1
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, dp[N][N];
int main()
{
char a[N], b[N];
cin >> n >> a + 1 >> m >> b + 1;
for (int i = 1; i <= n; i++) dp[i][0] = i;
for (int i = 1; i <= m; i++) dp[0][i] = i;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (a[i] != b[j]));
}
cout << dp[n][m];
}