3.3万

JavaBear
yqG_G

Lam4.
277
edgdcgxgbx

wyc1996

TheXX

AcKing_HIT
233333
acwing_ydx
zy23

1..
fly668

30天前

### 题目描述

#### 样例

//输入
2
fixprefixsuffix
abcdabc

//输出
fix
not exist


### 算法1

##### (KMP) $O(n)$

st[i]表示ne[2~n-1]中有=i的情况

#### 时间复杂度

KMP时间复杂度$O(n)$,然后依次枚举q,$O(n)$,总的时间复杂度$O(n)$.

#### C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1000010;
char s[N], st[N];
int T, ne[N];

int main()
{
scanf("%d", &T);
while (T --) {
scanf("%s", s + 1);
int n = strlen(s + 1);
for (int i = 2, j = 0; i <= n; i ++) {
while (j && s[i] != s[j + 1]) j = ne[j];
if (s[i] == s[j + 1]) j ++;
ne[i] = j;
}
memset(st, 0, sizeof st);
for (int i = 2; i < n; i ++)
if (ne[i]) st[ne[i]] = 1;
int ans = -1;
int p = ne[n];
while (p) {
if (st[p]) ans = max(ans, p);
p = ne[p];
}
// cout << n <<" " <<ans << endl;
if (ans == -1) printf("not exist\n");
else {
for (int i = 1; i <= ans; i ++) printf("%c", s[i]);
printf("\n");
}

}
}


1个月前

1个月前

1个月前

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int a, b;
int T;

int main()
{
cin >> T;
while(T--) {
int flag = 1, num = 1;
cin >> a >> b;
while (a >= 0 && b >= 0) {
if (flag) {
a -= num;
}
else {
b -= num;
}
num ++;
flag = !flag;
// cout << flag << endl;
}
if (a < 0) cout << "Vladik" << endl;
else cout << "Valera" << endl;
}
}


1个月前

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
int arr[N];
int n;
int ans;

bool check(int l, int r) {
bool flag = true;
for (int i = l; i < r; i ++) {
if (arr[i] > arr[i + 1]) {
flag = false;
break;
}
}
return flag;
}

void dfs(int l, int r) {
if (l >= r) return;
if (check(l, r)) {
ans = max(ans, r - l + 1);
// cout << "ans = " << ans << endl;
return;
}
int mid = l + r >> 1;
dfs(l, mid);
dfs(mid + 1, r);

}

int main()
{
int T;
cin >> T;
while (T --) {
ans = 1;
cin >> n;
for (int i = 0; i < n; i ++) cin >> arr[i];
dfs(0, n - 1);
cout << ans << endl;
}
}


1个月前

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long LL;
int a[N];
int n;
int main()
{
int T;
scanf("%d", &T);
while (T --) {
scanf("%d", &n);
int mx = 0;
for (int i = 0; i < n; i ++) {
scanf("%d", &a[i]);
mx = max(mx, a[i]);
}
int res = 0;
for (int i = 0; i < n; i ++) {
if (a[i] == mx) {
int j = i + 1;
while (j < n && a[j] == mx) j ++;
res = max(res, j - i);
i = j - 1;
}
}
printf("%d\n", res);

}
}


1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
int T;
cin >> T;
while (T--) {
long long n;
cin >> n;
string strn = to_string(n);
// cout << "strn = " << strn << endl;
int len = strn.size();
// cout << "len = " << len << endl;

if (strn[0] == '9') {
long long num = pow(10, len);
cout << num - n << endl;
}
else {
long long num = (strn[0] - '0' + 1) * pow(10, len - 1);
cout << num - n << endl;
}
}
}


2个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
int ans = 0;
int nowm = m;
for (int i = 0; i < n; i ++ ){
int x;
cin >> x;
if (nowm < x) ans ++, nowm = m;
nowm -= x;
}
ans ++;
cout << ans << endl;
}
}


2个月前

#include <bits/stdc++.h>
using namespace std;

int main() {
int T;
cin >> T;
while (T --) {
int n, x;
cin >> n >> x;
int a = 0;
int flag = 0;
while (n --) {
int t;
cin >> t;
if (t == x) flag = 1;
a = max(a, t);
}
if (flag) cout << "1" << endl;
else if (a > x) cout << "2" << endl;
else cout << (x + a - 1) / a << endl;
}
return 0;
}


2个月前
#include<bits/stdc++.h>
using namespace std;

int a[105];
int n, d;

int main() {
int t;
cin >> t;
while (t --) {
cin >> n >> d;
for (int i = 0; i < n; i ++) cin >> a[i];
for (int i = 1; i < n && d; i ++) {
if (d >= i * a[i]) {
d -= i * a[i];
a[0] += a[i];
}
else {
a[0] += d / i;
d = 0;
}
// cout <<"a[0] = " << a[0] << endl;
// cout << "d = " << d << endl;
}
cout << a[0] << endl;
}
return 0;
}