2019 Multi-University Training Contest 5
1002 - three arrays
분석: 매번 욕심을 부리는 것은 두 개의 집합 중 이차나 값이 가장 작은pair를 취하면 먼저 사전 트리를 사용하여 해결할 수 있다.두 개의 사전 나무로 유지할 생각을 하기 쉽다. 문제는 어떻게 최소치를 취하는가이다. 왜냐하면 두 나무가 동시에 0을 걷는지 1을 걷는지 확정할 수 없기 때문이다.
사실 같이 가면 돼요. 같은 노드의 0과 1은 서로 영향을 주지 않기 때문에 0에서 아래로 귀속되고 1에서 아래로 귀속됩니다. 그들의 결과도 서로 영향을 주지 않기 때문에 나무 전체를 끝까지 완주하고 순서를 정하면 됩니다.
그러면 마지막 방법은 두 그루의 나무를 동시에 뛰고, 우선적으로 00과 11을 뛰고, 01과 10을 뛰는 것이다.#include "bits/stdc++.h"
using namespace std;
struct node {
int nxt[2], num;
} a[100004 * 32], b[100004 * 32];
int cnt1, cnt2;
int ans[100004];
int cnt;
void init() {
cnt1 = cnt2 = cnt = 0;
a[0].nxt[0] = a[0].nxt[1] = b[0].nxt[0] = b[0].nxt[1] = -1;
a[0].num = b[0].num = 0;
}
void ins(node t[], char s[], int root, int &cnt) {
int len = strlen(s);
for (int i = 0; i < len; ++i) {
if (t[root].nxt[s[i] - '0'] == -1) {
t[root].nxt[s[i] - '0'] = ++cnt;
root = cnt;
t[root] = {{-1, -1}, 0};
} else root = t[root].nxt[s[i] - '0'];
t[root].num++;
}
}
int qu(int rt1, int rt2, int w, int base) {
bool ok = 1;
int res = 0;
while ((~a[rt1].nxt[0]) && (~b[rt2].nxt[0])) {
int temp = qu(a[rt1].nxt[0], b[rt2].nxt[0], w, base >> 1);
res += temp;
a[rt1].num -= temp;
b[rt2].num -= temp;
int nx1 = a[rt1].nxt[0], nx2 = b[rt2].nxt[0];
if (a[nx1].num == 0)
a[rt1].nxt[0] = -1;
if (b[nx2].num == 0)
b[rt2].nxt[0] = -1;
ok = 0;
}
while ((~a[rt1].nxt[1]) && (~b[rt2].nxt[1])) {
int temp = qu(a[rt1].nxt[1], b[rt2].nxt[1], w, base >> 1);
res += temp;
a[rt1].num -= temp;
b[rt2].num -= temp;
int nx1 = a[rt1].nxt[1], nx2 = b[rt2].nxt[1];
if (a[nx1].num == 0)
a[rt1].nxt[1] = -1;
if (b[nx2].num == 0)
b[rt2].nxt[1] = -1;
ok = 0;
}
while ((~a[rt1].nxt[0]) && (~b[rt2].nxt[1])) {
int temp = qu(a[rt1].nxt[0], b[rt2].nxt[1], w + base, base >> 1);
res += temp;
a[rt1].num -= temp;
b[rt2].num -= temp;
int nx1 = a[rt1].nxt[0], nx2 = b[rt2].nxt[1];
if (a[nx1].num == 0)
a[rt1].nxt[0] = -1;
if (b[nx2].num == 0)
b[rt2].nxt[1] = -1;
ok = 0;
}
while ((~a[rt1].nxt[1]) && (~b[rt2].nxt[0])) {
int temp = qu(a[rt1].nxt[1], b[rt2].nxt[0], w + base, base >> 1);
res += temp;
a[rt1].num -= temp;
b[rt2].num -= temp;
int nx1 = a[rt1].nxt[1], nx2 = b[rt2].nxt[0];
if (a[nx1].num == 0)
a[rt1].nxt[1] = -1;
if (b[nx2].num == 0)
b[rt2].nxt[0] = -1;
ok = 0;
}
if (ok) {
ans[cnt++]=w;
res++;
a[rt1].num -= res;
b[rt2].num -= res;
}
return res;
}
char s[35];
int main() {
int t;cin>>t;
while (t--) {
int n,x;cin>>n;
init();
for (int i = 0; i < n; ++i) {
scanf("%d",&x);
for (int j = 30; j >= 0; --j) {
s[j] = '0' + (x & 1);
x >>= 1;
}
s[31] = '\0';
ins(a, s, 0, cnt1);
}
for (int i = 0; i < n; ++i) {
scanf("%d",&x);
for (int j = 30; j > 0; --j) {
s[j] = '0' + (x & 1);
x >>= 1;
}
s[31] = '\0';
ins(b, s, 0, cnt2);
}
qu(0, 0, 0, 1 << 30);
sort(ans,ans+cnt);
for (int i = 0; i < cnt; ++i) {
printf("%d%c", ans[i], (i == cnt - 1 ? '
' : ' '));
}
}
}
1004 - equation
분석: 이것은 분단 함수로 n+1단이 있고 각 단락의 함수의 해가 존재하는지 계산하면 된다.1년 동안 버그를 썼어요.#include "bits/stdc++.h"
using namespace std;
struct node {
int up, dw;
bool friend operator v, ans;
int a[100004], b[100004];
int main() {
int T;
cin >> T;
while (T--) {
int n, c;
scanf("%d%d", &n, &c);
v.clear();
ans.clear();
int A = 0, B = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &a[i], &b[i]);
v.push_back({-b[i], a[i]});
A += -a[i];
B += -b[i];
}
B -= c;
sort(v.begin(), v.end());
bool ok = 0;
for (int i = 0; i < v.size() && !ok; ++i) {
if (A == 0 && B == 0)ok = 1;
else if (A == 0 && B != 0) {
A += v[i].dw * 2;
B -= v[i].up * 2;
continue;
} else {
node t;
if (B == 0) {
t = {0, 1};
} else {
int g = __gcd(A, B);
t = {-B / g, A / g};
}
node s = {v[i].up, v[i].dw};
node las;
if (i != 0)las = {v[i - 1].up, v[i - 1].dw};
if (i == 0 && (t < s || t == s)) {
ans.push_back(t);
} else if ((t < s || t == s) && (las < t || las == t)) {
ans.push_back(t);
}
A += v[i].dw * 2;
B -= v[i].up * 2;
}
}
node t;
if (A == 0 && B == 0)ok = 1;
else if (A == 0 && B != 0);
else if (B == 0) {
t = {0, 1};
if (v[v.size() - 1] < t || v[v.size() - 1] == t)ans.push_back(t);
} else {
int g = __gcd(abs(A), abs(B));
t = {-B / g, A / g};
if (v[v.size() - 1] < t || v[v.size() - 1] == t)ans.push_back(t);
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
if (ok) {
puts("-1");
} else {
printf("%d", ans.size());
printf("%c", ans.size() == 0 ? '
' : ' ');
for (int i = 0; i < ans.size(); ++i) {
if (ans[i].dw < 0) {
ans[i].dw *= -1;
ans[i].up *= -1;
}
printf("%d/%d%c", ans[i].up, ans[i].dw, (i == ans.size() - 1 ? '
' : ' '));
}
}
}
}
1005 - permutation 1
분석: 우선 사전 서열이 가장 작은 두 자리는 n, 1이다.그렇다면 (n-2)! >=k 앞의 두 개가 n, 1이다.그러면 n<=9의 예처리 타표에 대해 n>9의 것은 선형적으로 추출할 수 있다. 우선 n>9의 앞자리는 n, 1이 틀림없다.그러면 사전서의 관계에 따라 3위의 수는 점차적으로 증가해야 하고 3위의 수는 개수에 대해fac[3]이어야 한다. 그러면 이때 k와fac[n-3]의 관계를 비교하고 작은 것부터 큰 것까지 일일이 열거하면 된다.#include "bits/stdc++.h"
using namespace std;
long long fac[24];
int ans[24];
bool vis[24];
int init[10][10004][10];
struct node {
int d[34];
int x[34];
int n;
bool friend operator b.d[i])return 0;
}
return 0;
}
} a[1000000];
vector v;
int cnt;
int main() {
fac[0] = 1;
v.resize(30);
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= 20; ++i) {
fac[i] = fac[i - 1] * i;
}
v[1] = 1;
for (int i = 2; i <= 9; ++i) {
v[i] = i;
for (int j = 1; j <= fac[i]; ++j) {
for (int k = 1; k < i; ++k) {
a[j].d[k] = v[k + 1] - v[k];
}
for (int k = 1; k <= i; ++k) {
a[j].x[k] = v[k];
}
a[j].n = i;
next_permutation(v.begin() + 1, v.begin() + i + 1);
}
sort(a + 1, a + fac[i] + 1);
for (int k = 1; k <= min(fac[i], 10000LL); ++k) {
for (int j = 1; j <= i; ++j) {
init[i][k][j] = a[k].x[j];
}
}
}
int t;
cin >> t;
while (t--) {
int n, k;
scanf("%d%d", &n, &k);
if (n > 9) {
memset(vis, 0, sizeof(vis));
ans[1] = n;
ans[2] = 1;
vis[n] = 1;
vis[1] = 1;
for (int i = 3; i <= n; ++i) {
int base;
for (int j = 1; j <= n; ++j) {
if (!vis[j]) {
base = j;
break;
}
}
while (k > fac[n - i]) {
k -= fac[n - i];
base++;
while (vis[base])base++;
}
ans[i] = base;
vis[base] = 1;
}
for (int i = 1; i <= n; ++i) {
printf("%d%c", ans[i], (i == n ? '
' : ' '));
}
} else {
for (int i = 1; i <= n; ++i) {
printf("%d%c", init[n][k][i], (i == n ? '
' : ' '));
}
}
}
}
1006 - string matching
exkmp 판자.공헌을 누적해서 계산하면 됩니다. 정답은 모든 위치의lcp를 더하고, 모든 check가 마지막 자리에 일치하는지 여부입니다. 그렇지 않으면 답은 +1입니다.#include
using namespace std;
void EX_ten(char *a, char *b, int M, int N, long long *Next, long long *ret) {
int i, j, k;
for (j = 0; 1 + j < M && a[j] == a[1 + j]; j++);
Next[1] = j;
k = 1;
for (i = 2; i < M; i++) {
int Len = k + Next[k], L = Next[i - k];
if (L < Len - i) {
Next[i] = L;
} else {
for (j = max(0, Len - i); i + j < M && a[j] == a[i + j]; j++);
Next[i] = j;
k = i;
}
}
for (j = 0; j < N && j < M && a[j] == b[j]; j++);
ret[0] = j;
k = 0;
for (i = 1; i < N; i++) {
int Len = k + ret[k], L = Next[i - k];
if (L < Len - i) {
ret[i] = L;
} else {
for (j = max(0, Len - i); j < M && i + j < N && a[j] == b[i + j]; j++);
ret[i] = j;
k = i;
}
}
}
char s1[1000005], s2[1000005];
long long ret[1000005];
long long Next[1000005];
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%s", s1);
int n = strlen(s1);
for (int i = 0; i <= n; i++) ret[i] = Next[i] = 0;
for (int i = 0; i <= n; i++) s2[i] = s1[i];
EX_ten(s1, s2, n, n, Next, ret);
long long ans = 0;
for (int i = 1; i < n; i++) {
ans += ret[i];
ans += (ret[i] != n - i);
}
printf("%lld
", ans);
}
return 0;
}
1007 - permutation 2
분석: n, 1, n의 데이터를 쉽게 얻을 수 있는 것은 점차적인 F[N]=F[N-1]+F[N-3]이며, 동시에 답을 얻을 수 있는 것은 x, y와 1, n의 차이와 관련이 있다.x는 x-2, x-4... 1, 3... x-3, x-1, 즉 예시 12 3 9, [4,8], 즉 515에 해당한다. x=1과 y=n을 특별히 판정하면 된다.#include "bits/stdc++.h"
using namespace std;
const int mod = 998244353;
long long f[100004];
int main() {
int t;
f[0] = 0;
f[1] = 1;
f[2] = 1;
for (int i = 3; i < 100004; ++i) {
f[i] = f[i - 1] + f[i - 3];
f[i] %= mod;
}
cin >> t;
int n, x, y;
while (t--) {
scanf("%d%d%d", &n, &x, &y);
int dx = x - 1, dy = n - y;
int pos = n;
if (dx == 0 && dy == 0) {
printf("%lld
", f[pos]);
} else {
if (dx)pos -= 1;
if (dy)pos -= 1;
pos -= dx;
pos -= dy;
pos = max(0, pos);
if ((x == 1 || y == n) && y - x == 1) {
puts("1");
} else printf("%lld
", f[pos]);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include "bits/stdc++.h"
using namespace std;
struct node {
int nxt[2], num;
} a[100004 * 32], b[100004 * 32];
int cnt1, cnt2;
int ans[100004];
int cnt;
void init() {
cnt1 = cnt2 = cnt = 0;
a[0].nxt[0] = a[0].nxt[1] = b[0].nxt[0] = b[0].nxt[1] = -1;
a[0].num = b[0].num = 0;
}
void ins(node t[], char s[], int root, int &cnt) {
int len = strlen(s);
for (int i = 0; i < len; ++i) {
if (t[root].nxt[s[i] - '0'] == -1) {
t[root].nxt[s[i] - '0'] = ++cnt;
root = cnt;
t[root] = {{-1, -1}, 0};
} else root = t[root].nxt[s[i] - '0'];
t[root].num++;
}
}
int qu(int rt1, int rt2, int w, int base) {
bool ok = 1;
int res = 0;
while ((~a[rt1].nxt[0]) && (~b[rt2].nxt[0])) {
int temp = qu(a[rt1].nxt[0], b[rt2].nxt[0], w, base >> 1);
res += temp;
a[rt1].num -= temp;
b[rt2].num -= temp;
int nx1 = a[rt1].nxt[0], nx2 = b[rt2].nxt[0];
if (a[nx1].num == 0)
a[rt1].nxt[0] = -1;
if (b[nx2].num == 0)
b[rt2].nxt[0] = -1;
ok = 0;
}
while ((~a[rt1].nxt[1]) && (~b[rt2].nxt[1])) {
int temp = qu(a[rt1].nxt[1], b[rt2].nxt[1], w, base >> 1);
res += temp;
a[rt1].num -= temp;
b[rt2].num -= temp;
int nx1 = a[rt1].nxt[1], nx2 = b[rt2].nxt[1];
if (a[nx1].num == 0)
a[rt1].nxt[1] = -1;
if (b[nx2].num == 0)
b[rt2].nxt[1] = -1;
ok = 0;
}
while ((~a[rt1].nxt[0]) && (~b[rt2].nxt[1])) {
int temp = qu(a[rt1].nxt[0], b[rt2].nxt[1], w + base, base >> 1);
res += temp;
a[rt1].num -= temp;
b[rt2].num -= temp;
int nx1 = a[rt1].nxt[0], nx2 = b[rt2].nxt[1];
if (a[nx1].num == 0)
a[rt1].nxt[0] = -1;
if (b[nx2].num == 0)
b[rt2].nxt[1] = -1;
ok = 0;
}
while ((~a[rt1].nxt[1]) && (~b[rt2].nxt[0])) {
int temp = qu(a[rt1].nxt[1], b[rt2].nxt[0], w + base, base >> 1);
res += temp;
a[rt1].num -= temp;
b[rt2].num -= temp;
int nx1 = a[rt1].nxt[1], nx2 = b[rt2].nxt[0];
if (a[nx1].num == 0)
a[rt1].nxt[1] = -1;
if (b[nx2].num == 0)
b[rt2].nxt[0] = -1;
ok = 0;
}
if (ok) {
ans[cnt++]=w;
res++;
a[rt1].num -= res;
b[rt2].num -= res;
}
return res;
}
char s[35];
int main() {
int t;cin>>t;
while (t--) {
int n,x;cin>>n;
init();
for (int i = 0; i < n; ++i) {
scanf("%d",&x);
for (int j = 30; j >= 0; --j) {
s[j] = '0' + (x & 1);
x >>= 1;
}
s[31] = '\0';
ins(a, s, 0, cnt1);
}
for (int i = 0; i < n; ++i) {
scanf("%d",&x);
for (int j = 30; j > 0; --j) {
s[j] = '0' + (x & 1);
x >>= 1;
}
s[31] = '\0';
ins(b, s, 0, cnt2);
}
qu(0, 0, 0, 1 << 30);
sort(ans,ans+cnt);
for (int i = 0; i < cnt; ++i) {
printf("%d%c", ans[i], (i == cnt - 1 ? '
' : ' '));
}
}
}
분석: 이것은 분단 함수로 n+1단이 있고 각 단락의 함수의 해가 존재하는지 계산하면 된다.1년 동안 버그를 썼어요.
#include "bits/stdc++.h"
using namespace std;
struct node {
int up, dw;
bool friend operator v, ans;
int a[100004], b[100004];
int main() {
int T;
cin >> T;
while (T--) {
int n, c;
scanf("%d%d", &n, &c);
v.clear();
ans.clear();
int A = 0, B = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &a[i], &b[i]);
v.push_back({-b[i], a[i]});
A += -a[i];
B += -b[i];
}
B -= c;
sort(v.begin(), v.end());
bool ok = 0;
for (int i = 0; i < v.size() && !ok; ++i) {
if (A == 0 && B == 0)ok = 1;
else if (A == 0 && B != 0) {
A += v[i].dw * 2;
B -= v[i].up * 2;
continue;
} else {
node t;
if (B == 0) {
t = {0, 1};
} else {
int g = __gcd(A, B);
t = {-B / g, A / g};
}
node s = {v[i].up, v[i].dw};
node las;
if (i != 0)las = {v[i - 1].up, v[i - 1].dw};
if (i == 0 && (t < s || t == s)) {
ans.push_back(t);
} else if ((t < s || t == s) && (las < t || las == t)) {
ans.push_back(t);
}
A += v[i].dw * 2;
B -= v[i].up * 2;
}
}
node t;
if (A == 0 && B == 0)ok = 1;
else if (A == 0 && B != 0);
else if (B == 0) {
t = {0, 1};
if (v[v.size() - 1] < t || v[v.size() - 1] == t)ans.push_back(t);
} else {
int g = __gcd(abs(A), abs(B));
t = {-B / g, A / g};
if (v[v.size() - 1] < t || v[v.size() - 1] == t)ans.push_back(t);
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
if (ok) {
puts("-1");
} else {
printf("%d", ans.size());
printf("%c", ans.size() == 0 ? '
' : ' ');
for (int i = 0; i < ans.size(); ++i) {
if (ans[i].dw < 0) {
ans[i].dw *= -1;
ans[i].up *= -1;
}
printf("%d/%d%c", ans[i].up, ans[i].dw, (i == ans.size() - 1 ? '
' : ' '));
}
}
}
}
1005 - permutation 1
분석: 우선 사전 서열이 가장 작은 두 자리는 n, 1이다.그렇다면 (n-2)! >=k 앞의 두 개가 n, 1이다.그러면 n<=9의 예처리 타표에 대해 n>9의 것은 선형적으로 추출할 수 있다. 우선 n>9의 앞자리는 n, 1이 틀림없다.그러면 사전서의 관계에 따라 3위의 수는 점차적으로 증가해야 하고 3위의 수는 개수에 대해fac[3]이어야 한다. 그러면 이때 k와fac[n-3]의 관계를 비교하고 작은 것부터 큰 것까지 일일이 열거하면 된다.#include "bits/stdc++.h"
using namespace std;
long long fac[24];
int ans[24];
bool vis[24];
int init[10][10004][10];
struct node {
int d[34];
int x[34];
int n;
bool friend operator b.d[i])return 0;
}
return 0;
}
} a[1000000];
vector v;
int cnt;
int main() {
fac[0] = 1;
v.resize(30);
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= 20; ++i) {
fac[i] = fac[i - 1] * i;
}
v[1] = 1;
for (int i = 2; i <= 9; ++i) {
v[i] = i;
for (int j = 1; j <= fac[i]; ++j) {
for (int k = 1; k < i; ++k) {
a[j].d[k] = v[k + 1] - v[k];
}
for (int k = 1; k <= i; ++k) {
a[j].x[k] = v[k];
}
a[j].n = i;
next_permutation(v.begin() + 1, v.begin() + i + 1);
}
sort(a + 1, a + fac[i] + 1);
for (int k = 1; k <= min(fac[i], 10000LL); ++k) {
for (int j = 1; j <= i; ++j) {
init[i][k][j] = a[k].x[j];
}
}
}
int t;
cin >> t;
while (t--) {
int n, k;
scanf("%d%d", &n, &k);
if (n > 9) {
memset(vis, 0, sizeof(vis));
ans[1] = n;
ans[2] = 1;
vis[n] = 1;
vis[1] = 1;
for (int i = 3; i <= n; ++i) {
int base;
for (int j = 1; j <= n; ++j) {
if (!vis[j]) {
base = j;
break;
}
}
while (k > fac[n - i]) {
k -= fac[n - i];
base++;
while (vis[base])base++;
}
ans[i] = base;
vis[base] = 1;
}
for (int i = 1; i <= n; ++i) {
printf("%d%c", ans[i], (i == n ? '
' : ' '));
}
} else {
for (int i = 1; i <= n; ++i) {
printf("%d%c", init[n][k][i], (i == n ? '
' : ' '));
}
}
}
}
1006 - string matching
exkmp 판자.공헌을 누적해서 계산하면 됩니다. 정답은 모든 위치의lcp를 더하고, 모든 check가 마지막 자리에 일치하는지 여부입니다. 그렇지 않으면 답은 +1입니다.#include
using namespace std;
void EX_ten(char *a, char *b, int M, int N, long long *Next, long long *ret) {
int i, j, k;
for (j = 0; 1 + j < M && a[j] == a[1 + j]; j++);
Next[1] = j;
k = 1;
for (i = 2; i < M; i++) {
int Len = k + Next[k], L = Next[i - k];
if (L < Len - i) {
Next[i] = L;
} else {
for (j = max(0, Len - i); i + j < M && a[j] == a[i + j]; j++);
Next[i] = j;
k = i;
}
}
for (j = 0; j < N && j < M && a[j] == b[j]; j++);
ret[0] = j;
k = 0;
for (i = 1; i < N; i++) {
int Len = k + ret[k], L = Next[i - k];
if (L < Len - i) {
ret[i] = L;
} else {
for (j = max(0, Len - i); j < M && i + j < N && a[j] == b[i + j]; j++);
ret[i] = j;
k = i;
}
}
}
char s1[1000005], s2[1000005];
long long ret[1000005];
long long Next[1000005];
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%s", s1);
int n = strlen(s1);
for (int i = 0; i <= n; i++) ret[i] = Next[i] = 0;
for (int i = 0; i <= n; i++) s2[i] = s1[i];
EX_ten(s1, s2, n, n, Next, ret);
long long ans = 0;
for (int i = 1; i < n; i++) {
ans += ret[i];
ans += (ret[i] != n - i);
}
printf("%lld
", ans);
}
return 0;
}
1007 - permutation 2
분석: n, 1, n의 데이터를 쉽게 얻을 수 있는 것은 점차적인 F[N]=F[N-1]+F[N-3]이며, 동시에 답을 얻을 수 있는 것은 x, y와 1, n의 차이와 관련이 있다.x는 x-2, x-4... 1, 3... x-3, x-1, 즉 예시 12 3 9, [4,8], 즉 515에 해당한다. x=1과 y=n을 특별히 판정하면 된다.#include "bits/stdc++.h"
using namespace std;
const int mod = 998244353;
long long f[100004];
int main() {
int t;
f[0] = 0;
f[1] = 1;
f[2] = 1;
for (int i = 3; i < 100004; ++i) {
f[i] = f[i - 1] + f[i - 3];
f[i] %= mod;
}
cin >> t;
int n, x, y;
while (t--) {
scanf("%d%d%d", &n, &x, &y);
int dx = x - 1, dy = n - y;
int pos = n;
if (dx == 0 && dy == 0) {
printf("%lld
", f[pos]);
} else {
if (dx)pos -= 1;
if (dy)pos -= 1;
pos -= dx;
pos -= dy;
pos = max(0, pos);
if ((x == 1 || y == n) && y - x == 1) {
puts("1");
} else printf("%lld
", f[pos]);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include "bits/stdc++.h"
using namespace std;
long long fac[24];
int ans[24];
bool vis[24];
int init[10][10004][10];
struct node {
int d[34];
int x[34];
int n;
bool friend operator b.d[i])return 0;
}
return 0;
}
} a[1000000];
vector v;
int cnt;
int main() {
fac[0] = 1;
v.resize(30);
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= 20; ++i) {
fac[i] = fac[i - 1] * i;
}
v[1] = 1;
for (int i = 2; i <= 9; ++i) {
v[i] = i;
for (int j = 1; j <= fac[i]; ++j) {
for (int k = 1; k < i; ++k) {
a[j].d[k] = v[k + 1] - v[k];
}
for (int k = 1; k <= i; ++k) {
a[j].x[k] = v[k];
}
a[j].n = i;
next_permutation(v.begin() + 1, v.begin() + i + 1);
}
sort(a + 1, a + fac[i] + 1);
for (int k = 1; k <= min(fac[i], 10000LL); ++k) {
for (int j = 1; j <= i; ++j) {
init[i][k][j] = a[k].x[j];
}
}
}
int t;
cin >> t;
while (t--) {
int n, k;
scanf("%d%d", &n, &k);
if (n > 9) {
memset(vis, 0, sizeof(vis));
ans[1] = n;
ans[2] = 1;
vis[n] = 1;
vis[1] = 1;
for (int i = 3; i <= n; ++i) {
int base;
for (int j = 1; j <= n; ++j) {
if (!vis[j]) {
base = j;
break;
}
}
while (k > fac[n - i]) {
k -= fac[n - i];
base++;
while (vis[base])base++;
}
ans[i] = base;
vis[base] = 1;
}
for (int i = 1; i <= n; ++i) {
printf("%d%c", ans[i], (i == n ? '
' : ' '));
}
} else {
for (int i = 1; i <= n; ++i) {
printf("%d%c", init[n][k][i], (i == n ? '
' : ' '));
}
}
}
}
exkmp 판자.공헌을 누적해서 계산하면 됩니다. 정답은 모든 위치의lcp를 더하고, 모든 check가 마지막 자리에 일치하는지 여부입니다. 그렇지 않으면 답은 +1입니다.
#include
using namespace std;
void EX_ten(char *a, char *b, int M, int N, long long *Next, long long *ret) {
int i, j, k;
for (j = 0; 1 + j < M && a[j] == a[1 + j]; j++);
Next[1] = j;
k = 1;
for (i = 2; i < M; i++) {
int Len = k + Next[k], L = Next[i - k];
if (L < Len - i) {
Next[i] = L;
} else {
for (j = max(0, Len - i); i + j < M && a[j] == a[i + j]; j++);
Next[i] = j;
k = i;
}
}
for (j = 0; j < N && j < M && a[j] == b[j]; j++);
ret[0] = j;
k = 0;
for (i = 1; i < N; i++) {
int Len = k + ret[k], L = Next[i - k];
if (L < Len - i) {
ret[i] = L;
} else {
for (j = max(0, Len - i); j < M && i + j < N && a[j] == b[i + j]; j++);
ret[i] = j;
k = i;
}
}
}
char s1[1000005], s2[1000005];
long long ret[1000005];
long long Next[1000005];
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%s", s1);
int n = strlen(s1);
for (int i = 0; i <= n; i++) ret[i] = Next[i] = 0;
for (int i = 0; i <= n; i++) s2[i] = s1[i];
EX_ten(s1, s2, n, n, Next, ret);
long long ans = 0;
for (int i = 1; i < n; i++) {
ans += ret[i];
ans += (ret[i] != n - i);
}
printf("%lld
", ans);
}
return 0;
}
1007 - permutation 2
분석: n, 1, n의 데이터를 쉽게 얻을 수 있는 것은 점차적인 F[N]=F[N-1]+F[N-3]이며, 동시에 답을 얻을 수 있는 것은 x, y와 1, n의 차이와 관련이 있다.x는 x-2, x-4... 1, 3... x-3, x-1, 즉 예시 12 3 9, [4,8], 즉 515에 해당한다. x=1과 y=n을 특별히 판정하면 된다.#include "bits/stdc++.h"
using namespace std;
const int mod = 998244353;
long long f[100004];
int main() {
int t;
f[0] = 0;
f[1] = 1;
f[2] = 1;
for (int i = 3; i < 100004; ++i) {
f[i] = f[i - 1] + f[i - 3];
f[i] %= mod;
}
cin >> t;
int n, x, y;
while (t--) {
scanf("%d%d%d", &n, &x, &y);
int dx = x - 1, dy = n - y;
int pos = n;
if (dx == 0 && dy == 0) {
printf("%lld
", f[pos]);
} else {
if (dx)pos -= 1;
if (dy)pos -= 1;
pos -= dx;
pos -= dy;
pos = max(0, pos);
if ((x == 1 || y == n) && y - x == 1) {
puts("1");
} else printf("%lld
", f[pos]);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
#include "bits/stdc++.h"
using namespace std;
const int mod = 998244353;
long long f[100004];
int main() {
int t;
f[0] = 0;
f[1] = 1;
f[2] = 1;
for (int i = 3; i < 100004; ++i) {
f[i] = f[i - 1] + f[i - 3];
f[i] %= mod;
}
cin >> t;
int n, x, y;
while (t--) {
scanf("%d%d%d", &n, &x, &y);
int dx = x - 1, dy = n - y;
int pos = n;
if (dx == 0 && dy == 0) {
printf("%lld
", f[pos]);
} else {
if (dx)pos -= 1;
if (dy)pos -= 1;
pos -= dx;
pos -= dy;
pos = max(0, pos);
if ((x == 1 || y == n) && y - x == 1) {
puts("1");
} else printf("%lld
", f[pos]);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.