2018 년 전국 다 교 알고리즘 겨울방학 훈련소 연습 경기 (2 차 전) A 거품 (시 뮬 레이 션)
1558 단어 ACM_경전 DP쇠 그물ACM_시 뮬 레이 션 실현
입력 설명: 데이터 가 여러 그룹 으로 파일 이 끝 날 때 까지 처 리 됩 니 다.
각 그룹의 입력 은 'O' 와 'o' 로 구 성 된 문자열 을 포함 합 니 다.출력 설명: 각 그룹의 출력 은 한 줄 만 포함 하고, 한 줄 의 문자열 은 작은 물고기 가 뱉 은 거품 이 융합 된 후에 남 은 거품 을 나타 낸다.
예시 1
입력
ooOOoooO
출력
oO
설명 하 다.
왼쪽 에서 오른쪽으로 병합 비고: 100% 데이터 에 대해,
문자열 의 길 이 는 100 을 넘 지 않 습 니 다.
제목: 문 제 는 처음에 분명하게 말 하지 않 았 고 매우 유도 적 인 사례 를 주 었 으 며 마지막 에 왼쪽 에서 오른쪽으로 합병 했다 고 말 했다.
생각: 제목 시 뮬 레이 션 을 하면 하나의 배열 을 구성 할 수 있 습 니 다. 두 개의 인접 한 작은 거품 은 하나의 큰 거품 으로 녹 고 두 개의 인접 한 큰 거품 은 터 지고 터 지 거나 서로 어 울 리 면 업데이트 가 필요 합 니 다.
if (a[i]==a[k]&&a[i]==1) { a[i]=0; a[k]=2; } (모두 작은 거품 일 때 i 는 거품 이 아니 라 k 는 큰 거품 이다)
else if (a [i] = a [k] & a [i] = 2) {a [i] = 0; a [k] = 0} (모두 큰 거품 일 때 i, k 는 거품 이 되 지 않 음)
k 의 획득 에 주의 하 세 요: 이전에 저 는 2 개의 배열 로 돌아 가면 서 수 치 를 저 장 했 지만 귀 찮 았 습 니 다. 나중에 배열 로 다음 거품 의 좌 표를 찾 았 습 니 다. 이 문제 로 인해 현재 의 값 은 다음 과 만 변화 할 수 있 습 니 다.
#include
using namespace std;
int main()
{
char s[105];
while(scanf("%s",s)!=EOF)
{
int a[105];
int len=strlen(s);
for(int i=0;i