[경기 매듭과 문제풀이] Codeforces Global Round 1 욕심 주의, 간단한 dp 기교, 그리고 AC 자동기 + 디지털 dp
59979 단어 codeforces시합 소결문제풀이종합 사고 문제
1110H - Modest Substrings
제목: 길이가 n인 문자열을 구하고 최대 몇 개의 하위 문자열 x를 구하며 L<=x<=R, |L|<=|R|<=800, n<=2000을 만족시키면 모두 10진법 표시입니다
이것은 디지털 dp의 좋은 문제다!fdf 양반의 가르침에 감사 드립니다.fdf의 문제풀이는 모든 하위 문자열의 공헌을 처음으로 제한에서 벗어난 곳에 놓고 통계합니다.제한을 벗어나면 l 또는 r의 접두사를 열거하고 다음 차원 통계를 열거할 수 있다.여기서 우리는 이 열의 길이를 고정시켜야 한다. 제한을 벗어난 후에 임의로 채워야 하기 때문에 길이가 합법적이면 [l]<|r|-1이면 둘 사이의 열을 통계해야 한다.제한에서 벗어난 모든 열을 AC 자동기에 삽입(모든 상태의 제한에서 벗어난 합법적인 길이를 기록)하면 이 노드와 일치하고 길이가 합법적이면 답안을 공헌할 수 있다.또한 모든 페일 나무의 조상들은 이 상태의 접미사로 답을 바칠 수 있다.f(i, u)는 길이가 i임을 나타내며 AC 로봇에서 u와 일치하는 가장 좋은 답안을 나타낸다.이동할 때 g(x, i)를 미리 처리하면 노드 x를 표시하고 길이 i가 공헌할 수 있는 답안수를 남깁니다.사전의 순서가 가장 작아야 하기 때문에 기억화 검색을 하고 위치별로 가장 좋은 코드를 확정하여 분류하는 토론을 매우 길게 썼지만 주석은 비교적 뚜렷하다
총결산: L=R의 특판이 잘못 걸려서 1시간을 조정했다.이런 오류는 정말 모든 코드의 세부 사항을 꼼꼼히 보아야 한다. 대조를 빌려서는 안 된다!왜 아직도 카메라에 오류가 나면 어디가 틀렸는지 알 수 있지만 코드를 보면 알아낼 수가 없어요.반드시 자신의 문제를 조정하는 악습을 고쳐야 하며, 반드시 마음을 가라앉히고 곳곳의 잘못을 알아내야 한다!코드는 정말 한 마디 한 마디 읽어야 해!뼈에 사무치는 교훈이여!
#include
",DP(n,0));
int cur = 0;
rep(i,1,n){
a[i] = from[n - i + 1][cur].se;
cur = from[n - i + 1][cur].fi;
}
/* memset(f,-1,sizeof(f));
f[0][0] = 0;
rep(i,0,n - 1){
rep(j,0,tot){
if ( f[i][j] == -1 ) continue;
rep(k,0,9){
int to = trans[j][k] , len = n - i - 1;
int d = f[i][j] + g[to][len];
if ( f[i + 1][to] < d ) f[i + 1][to] = d , pre[i + 1][to] = mp(j,k);
}
}
}
int ans = 0 , rec = 0;
rep(i,0,tot){
if ( f[n][i] > ans ){
ans = f[n][i] , rec = i;
}
}
printf("%d
",ans);
repd(i,n,1){
a[i] = pre[i][rec].se;
rec = pre[i][rec].fi;
}*/
rep(i,1,n) printf("%d",a[i]);
puts("");
}
int main(){
freopen("input.txt","r",stdin);
scanf("%s %s %d",s1 + 1,s2 + 1,&n);
lenl = strlen(s1 + 1) , lenr = strlen(s2 + 1);
init();
build();
solve();
}
1110G - Tree-Tac-Toe
제목: 나무 한 그루를 주는데 그 위에 흰 점과 염색하지 않은 점이 있고 흰색이 먼저 손을 잡고 번갈아 염색한다.세 개의 연속 백점으로 염색하면 이긴다.무승부냐, 백승이냐.n<=5e5 욕심 좋아!우선 화이트 포인트를 무색으로 바꿔주세요.가점은 같은 염색을 한 후 선후손이 변하지 않고 상태가 이전과 일치할 것을 보증한다.이렇게 전환되어 분류 토론의 상황을 크게 감소시켰다.전환하지 않아도 토론할 수 있다.하지만 전환 후 모델은 훨씬 간단합니다!
이어서 특수 상황의 분류 토론을 진행한다.시험장에서 너무 흐리멍덩하게 생각해서 뼈형에 중간점이 홀수인 경우(당시 중간점만 논의했는데 확장이 가능할 줄은 몰랐다) 자신의 알고리즘을 확인할 때 더욱 꼼꼼해야 한다. 물론 이런 사고는 많이 단련해야 한다!
my code
1110F - Nearest Leaf
제목: dfs 순서에 따라 표시된 나무를 제시하고 점 거리 [l,r]에서 가장 가까운 잎의 거리를 묻는다.
이 문제를 직접 풀면 lca가 어디에 있는지 모르기 때문에 유지하기 어렵고 dfs 서열이 정해져 있어 점분과 중연쇄 분할을 할 수 없다.이때 오프라인을 고려하여 (원래 명백한 사고방식을 들었기 때문에 시험장에서 wxh를 물어서야 비로소 생각났다.) 각 점에서 모든 잎사귀까지의 거리를 직접 유지하고 질문을 통일적으로 처리하면 된다.
1110E - Magic Stones
의미: 시퀀스 c[i]를 조작할 수 있음: 위치 i를 선택하고, (2 < = i < = n - 1) c[i]를 c [i + 1] + c [i 1] + c [i 1 1] - - c [i 1] - c [i 1] - c [i 1] - c [i 1] + c [i + 1] + c [i + 1] + c [i - i - 1] - c [i] - c [i] - i] - i[i] 위치 i, (2 < = i < n = 1]]]] 위치 i, (2 < = i< = i = i = i = i]를 선택하고, c[i]]를 [i] + 1]로 바꾸고, c[i]를 [i] [i] [i] [i] [i] [i]]
매번 조작은 차분수 그룹을 위치를 바꾸려고 할 때 문제가 비교적 차분 서열로 바뀌어 순서가 같은지 첫 번째 요소와 같은지 여부가 분명하다. 만약 상술한 것이 같으면 원 서열은 같다.또한 마지막 원소 c[n]=sigma(d[i])+c[1]는 차분수 그룹의 순서에 따라 바뀌지 않으며 특판할 필요가 없다.판단 서열이 같은 사고방식은 항상 차분이나 접두어와 판단으로 바뀐다!
1110D - Jongmah
제목: n개의 숫자를 제시하면 두 가지 삼원조(i, i+1, i+2)를 구성할 수 있고, (i, i, i)는 최대 몇 개의 삼원조를 구성할 수 있느냐고 묻는다.
처음엔 1e6 보고 욕심인 줄 알았는데사실 간단해야 할 dp(동료에게 물었다)는 3개가 넘는 중복된 순자를 3개의 삼원조로 직접 대체하기 때문에 순자의 개수인%3을 기록하면 된다.f(i, 0... 2, 0... 2)는 i로 시작하고 i가 중간에 있는 순자 개수를 나타낸다.간단하게 옮기면 된다.불법 상태를 버리지 않도록 주의하시오
매우 간단해 보이는 모형으로 때로는 욕심으로, 때로는 dp로 처리한다.축적된 것이 너무 적으니 총결과 융합이 관통되고 성질을 찾는 것을 배워야 한다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
