CF 1023 & 1025
pantw
2018-10-17 21:39:50
## 1023A
```cpp
#include <cstdio>
#define maxn 200010
char a[maxn], b[maxn];
int main() {
int n, m;
scanf("%d%d", &n, &m);
scanf("%s%s", a + 1, b + 1);
int star = -1;
for(int i = 1; i <= n; ++i) if(a[i] == '*') star = i;
bool valid = true;
if(star == -1) {
if (n == m) {
for(int i = 1; i <= n; ++i) if(a[i] != b[i]) valid = false;
}
else valid = false;
} else {
for(int i = 1; i < star; ++i) if(a[i] != b[i]) valid = false;
for(int i = n; i > star; --i) if(a[i] != b[m-(n-i)]) valid = false;
if(n - 1 > m) valid = false;
}
puts(valid ? "YES" : "NO");
return 0;
}
```
## 1023B
```cpp
#include <cstdio>
#define Lovelive long long
#define lld "%I64d"
int main() {
Lovelive n, k, ans = 0;
scanf(lld lld, &n, &k);
if(k <= n + 1) ans = (k - 1) / 2;
else if(k <= n + n) ans = (n + n + 1 - k) / 2;
printf(lld, ans);
return 0;
}
```
## 1023C
```cpp
#include <cstdio>
#define maxn 200010
char str[maxn];//
int main() {
int n, k, l = 0, r = 0;
scanf("%d%d", &n, &k);
scanf("%s", str + 1);
for(int i = 1; i <= n; ++i) {
if(str[i] == '(') ++l;
else ++r;
putchar(str[i]);
if(l == k / 2) break;
}
for(int i = 1, rest = (k / 2 - r); i <= rest; ++i) putchar(')');
return 0;
}
```
## 1023D
```cpp
#include <cstdio>
#include <set>
#define maxn 200100
int l[maxn], r[maxn];
int seq[maxn];
int main() {
int n, q;
bool hasq = false;
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; ++i) scanf("%d", seq + i);
for(int i = 1; i <= n && !hasq; ++i) if(seq[i] == q) hasq = true;
for(int i = 1; i <= n; ++i) if(seq[i] && !l[seq[i]]) l[seq[i]] = i;
for(int i = n; i >= 1; --i) if(seq[i] && !r[seq[i]]) r[seq[i]] = i;
if(!hasq) for(int i = 1; i <= n && !hasq; ++i) if(seq[i] == 0) seq[i] = q, hasq = true;
std::set<int> S;
bool valid = true;
for(int i = 1; i <= n; ++i) {
if(l[seq[i]] == i) S.insert(seq[i]);
if(r[seq[i]] == i) S.erase(seq[i]);
if(!S.empty()) {
std::set<int>::reverse_iterator it = S.rbegin();
if(*it > seq[i] && seq[i] != 0) valid = false;
if(seq[i] == 0) seq[i] = *it;
} else if(seq[i] == 0) seq[i] = 1;
}
if(!hasq) valid = false;
puts(valid ? "YES" : "NO");
if(valid) for(int i = 1; i <= n; ++i) printf("%d ", seq[i]);
return 0;
}
```
## 1025A
```cpp
#include <cstdio>
char str[100010];
int cnt[256], n;
int main() {
scanf("%d%s", &n, str + 1);
for(int i = 1; i <= n; ++i) if(++cnt[str[i]] >= 2) return puts("Yes"), 0;
return puts(n == 1 ? "Yes" : "No"), 0;
}
```
## 1025B
```cpp
#include <cstdio>
#define Lovelive long long
bool np[100010];
int a[150010], b[150010];
int main() {
for(int i = 2; i * i < 100010; ++i) {
if(!np[i]) {
for(int j = i * i; j < 100010; j += i) np[j] = true;
}
}
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d%d", a + i, b + i);
for(int i = 2; i < 100010; ++i) {
if(a[1] % i != 0 && b[1] % i != 0) np[i] = true;
while(a[1] % i == 0) a[1] /= i;
while(b[1] % i == 0) b[1] /= i;
}
for(int i = 2; i < 100010; ++i) {
if(!np[i]) {
bool valid = true;
for(int j = 2; j <= n; ++j) if(a[j] % i != 0 && b[j] % i != 0) valid = false;
if(valid) return printf("%d", i), 0;
}
}
bool valid1 = true;
for(int j = 2; j <= n; ++j) if(a[j] % a[1] != 0 && b[j] % a[1] != 0) valid1 = false;
if(valid1 && a[1] != 1) return printf("%d", a[1]), 0;
bool valid2 = true;
for(int j = 2; j <= n; ++j) if(a[j] % b[1] != 0 && b[j] % b[1] != 0) valid2 = false;
if(valid2 && b[1] != 1) return printf("%d", b[1]), 0;
return puts("-1"), 0;
}
```
## 1025C
```cpp
#include <cstdio>
#include <cstring>
#define maxn 200010
int n;
char s[maxn];
inline void cmax(int &p, int x) {
if(x > p) p = x;
}
int main() {
int ans = 0;
scanf("%s", s);
n = strlen(s);
for(int i = 0; i < n; ++i) s[n + i] = s[i];
for(int i = 1, ta = 1; i < 2 * n; ++i) {
if(s[i] == s[i-1]) ta = 1;
else ++ta;
cmax(ans, ta);
}
printf("%d", ans < n ? ans : n);
return 0;
}
```
## 1025D
```cpp
#include <cstdio>
#define maxn 710
int a[maxn], n;
bool dp[maxn][maxn][2];
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", a + i);
for(int i = 1; i <= n - 1; ++i) {
if(gcd(a[i], a[i+1]) > 1) dp[i][i][1] = dp[i+1][i+1][0] = true;
}
for(int l = 2; l <= n; ++l) {
for(int i = 1; i <= n - l + 1; ++i) {
int j = i + l - 1;
if(i >= 2) {
if(dp[i+1][j][0] && gcd(a[i-1], a[i]) > 1) dp[i][j][0] = true;
for(int k = i + 1; !dp[i][j][0] && k < j; ++k) {
if(dp[i][k-1][1] && dp[k+1][j][0] && gcd(a[i-1], a[k]) > 1) dp[i][j][0] = true;
}
if(dp[i][j-1][1] && gcd(a[i-1], a[j]) > 1) dp[i][j][0] = true;
}
if(j < n) {
if(dp[i+1][j][0] && gcd(a[i], a[j+1]) > 1) dp[i][j][1] = true;
for(int k = i + 1; !dp[i][j][1] && k < j; ++k) {
if(dp[i][k-1][1] && dp[k+1][j][0] && gcd(a[k], a[j+1]) > 1) dp[i][j][1] = true;
}
if(dp[i][j-1][1] && gcd(a[j], a[j+1]) > 1) dp[i][j][1] = true;
}
// printf("%d %d %d %d\n", i, j, dp[i][j][0], dp[i][j][1]);
}
}
bool valid = false;
for(int i = 1; i <= n; ++i) if(dp[1][i-1][1] && dp[i+1][n][0]) valid = true;
if(n >= 2 && (dp[1][n-1][1] || dp[2][n][0])) valid = true;
puts(valid ? "Yes" : "No");
return 0;
}
```