[bestcoder\# 36] ABCD 문제 풀이
Accepts: 519 Submissions: 1749 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) 문 제 는 Vivid 의 학교 에 이상 한 반 (SC) 이 있다 고 묘사 했다. SC 에 서 는 이 학생 들 의 이름 이 매우 이상 하 다.그들의 이름 형식 은 이러한 anbncn (a, b, c 두 가지 가 다르다.) 이다. 예 를 들 어 'abc', 'ddppqq' 라 는 학생 은 SC 에 있 지만 'aaa', 'ab', 'ddppqq' 라 는 학생 은 SC 에 있 는 학생 이 아니다.Vivid 는 많은 친 구 를 사 귀 었 다. 그 는 그들 중 어떤 사람 이 SC 에 있 는 지 알 고 싶 어 했다.설명 여러 그룹 테스트 데이터 (약 10 그룹) 를 입력 하 십시오. 모든 데 이 터 는 한 줄 에 하나의 문자열 S 를 보 여 줍 니 다. Vivid 한 친구 의 이름 을 대표 합 니 다.파일 끝까지 처리 해 주세요.
[매개 변수 약정] 1 ≤ | S | ≤ 10. | S | 는 S 의 길 이 를 말 합 니 다. S 는 소문 자 만 포함 합 니 다. 출력 설명 은 모든 데이터 에 대해 Vivid 의 친구 가 SC 에 있 으 면 YES 를 출력 합 니 다. 그렇지 않 으 면 NO 를 출력 합 니 다.입력 샘플 abc bc 출력 샘플 YES NO
WA 는 두 번 밖 에 지나 지 않 았 습 니 다. abc 를 처음 보지 못 했 을 때 연속 이 어야 합 니 다.두 번 째 는 abc 를 보지 못 했 습 니 다.
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
char s[100];
int cnt[100];
int main()
{
while (scanf("%s",s)!=EOF)
{
for (int i=1;i<=30;i++)
cnt[i]=0;
int l=strlen(s);
int num=0;
if (l<3)
{
cout<<"NO"<<endl;
continue;
}
int k;
int now=0,f=1;
while (now<l)
{
int x=now;
while (now+1<l&&s[now]==s[now+1])
now++;
num++;
if (cnt[s[now]-'a'+1]) f=0;
else cnt[s[now]-'a'+1]=1;
if (num==1) k=now-x+1;
else
{
if (now-x+1!=k) f=0;
}
now++;
}
if (num!=3||!f)
{
cout<<"NO"<<endl;
}
else
{
cout<<"YES"<<endl;
}
}
return 0;
}
Gunner
Accepts: 391 Submissions: 1397 Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) 문 제 는 아주 오래 전에 Jack 이라는 총 잡 이 를 묘사 했다.그 는 사냥 을 매우 좋아한다.어느 날, 그 는 작은 숲 에 갔다.거기에 새 n 마리, 그리고 나무 n 그루 가 있 습 니 다.i 번 째 새 는 i 번 째 나무의 꼭대기 에 서 있다.이 나무 들 은 왼쪽 에서 오른쪽으로 일 직선 으로 늘 어 섰 다.모든 나 무 는 그것 의 높이 를 가지 고 있다.Jack 은 맨 왼쪽 나무 왼쪽 에 서 있 습 니 다.잭 이 높이 H 인 곳 에서 오른쪽으로 총알 한 발 을 쏘 면 높이 H 인 나무 에 서 있 던 새 가 떨어진다.Jack 은 여러 번 사격 을 하 는데, 그 는 매번 사격 할 때마다 얼마나 많은 새들 이 떨 어 지 는 지 알 고 싶 어 한다.설명 여러 조 의 테스트 데이터 (약 5 조) 를 입력 하 십시오. 각 조 의 첫 줄 은 n, m, n 은 n 그루 의 나무 와 n 마리 의 새 가 있 음 을 표시 합 니 다. m 는 Jack 이 m 회 사격 할 것 임 을 표시 합 니 다.두 번 째 줄 에는 n 개의 정수 가 있 는데 h [1], h [2], h [3], h [n] 는 이 나무의 높이 를 나타 낸다.세 번 째 줄 에는 m 개의 정수 가 있 는데 q [1], q [2], q [3], q [m] 는 Jack 사격 의 높이 를 나타 낸다.
[매개 변수 약정] 1 ≤ n, m ≤ 1000000 (106) 1 ≤ h [i], q [i] ≤ 100000000 (109) 출력 설명 은 각 q [i] 에 대해 한 줄 에 Jack 을 출력 하여 새 몇 마 리 를 떨 어 뜨 렸 다.입력 샘플 43 1 2 3 4 14 출력 샘플 101 Hint 빅 데이터 입력, 빠 른 읽 기 를 추천 합 니 다.
맵 물 로 지 냈어요.
정 해 는 원래 의 나 무 를 높 은 곳 에서 낮은 곳 으로 정렬 한 다음 에 매번 2 점 을 물 어 구간 을 찾 는 것 이다.
찾 은 후에 지 워 야 한 다 는 것 을 주의해 라.
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
map<int,int> mp;
int n,m,cnt[1000010];
void read(int &tmp)
{
int ch=getchar();
int fu=1;
tmp=0;
for (;ch<'0'||ch>'9';ch=getchar())
if (ch=='-') fu=-1;
for (;ch>='0'&&ch<='9';ch=getchar())
tmp=tmp*10+ch-'0';
tmp*=fu;
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
mp.clear();
for (int i=1;i<=1000005;i++)
cnt[i]=0;
for (int i=1;i<=n;i++)
{
int x;
read(x);
if (!mp[x]) mp[x]=i;
cnt[mp[x]]++;
}
for (int i=1;i<=m;i++)
{
int x;
read(x);
printf("%d
",cnt[mp[x]]);
cnt[mp[x]]=0;
}
}
return 0;
}
Trees
Accepts: 156 Submissions: 533 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) 문 제 는 오늘 CodeFamer 가 칸 트 리 에 가 는 것 을 묘사 합 니 다.나무 N 그루 가 일렬 로 서 있다.그들 은 1 부터 N 까지 레이 블 을 받 았 다.i 번 나무의 높이 는 hi 이다.두 그루 의 떨 어 지지 않 은 나무 번 호 는 각각 x, y 이 고 그들 이 다음 과 같은 조건 중 하 나 를 만족 시 킬 때 그들 은 같은 블록 에 속한다. 1) x + 1 = y 또는 y + 1 = x;2) 떨 어 지지 않 은 나무 가 존재 합 니 다. 번 호 는 z 이 고 x 와 z 는 같은 조각 에 있 으 며 y 와 z 도 같은 조각 에 있 습 니 다.현재 CodeFamer 는 어떤 값 보다 높 지 않 은 나 무 를 떨 어 뜨리 려 고 합 니 다. 떨 어 지면 몇 개의 블록 이 형성 되 나 요?설명 여러 그룹 테스트 데이터 (약 15 그룹) 를 입력 하 십시오. 각 그룹의 데이터 에 대해 첫 번 째 줄 은 두 개의 정수 N 과 Q 를 포함 하고 하나의 빈 칸 으로 나 누 어 집 니 다. N 은 N 그루 의 나무 가 있 고 Q 는 Q 개의 조회 가 있 음 을 표시 합 니 다.다음 N 행 에 서 는 h [1], h [2], h [3], h [N] 이 나타 나 N 그루 의 높이 를 나타 낸다.다음 Q 줄 에는 q [1], q [2], q [3], q [Q] 가 나타 납 니 다.
파일 끝까지 처리 해 주세요.
[매개 변수 약정] 1 ≤ N, Q ≤ 500000 ≤ h [i] ≤ 100000000 (109) 0 ≤ q [i] ≤ 100000000 (109) 출력 설명 은 각 q [i] 에 대해 출력 CodeFamer 칸 의 높이 가 q [i] 보다 크 지 않 은 나 무 를 출력 한 후 몇 개의 블록 이 있 습 니까?입력 샘플 322 3262 출력 샘플 002 Hint 는 이 샘플 에 나무 3 그루 가 있 고 이들 의 높이 는 523 이다.
6 이 조회 에 대해 CodeFamer 가 높이 가 6 보다 크 지 않 은 나 무 를 떨 어 뜨리 면 나머지 나무의 높이 모양 은 - 1 - 1 (- 1 은 그 나무 가 떨 어 졌 다 는 뜻) 이다.이렇게 하면 0 원 입 니 다.
2 이 조회 에 대해 CodeFamer 가 높이 가 2 보다 크 지 않 은 나 무 를 떨 어 뜨리 면 나머지 나무의 높이 모양 은 5 - 13 (- 1 은 그 나무 가 떨 어 졌 다 는 뜻) 이다.이렇게 두 개 있어 요.
사고 문제.
오프라인 으로 하 다.
먼저 나무의 표 시 를 ok [i] 1 로 설정 하여 그들 이 모두 베 이지 않 았 음 을 나타 낸다.트 리 높이 에 따라 정렬 을 읽 고 질문 도 트 리 높이 에 따라 정렬 합 니 다. 현재 ans = 1.
순서대로 질문 을 처리 합 니 다. 질문 은 오름차 순 이기 때문에 반드시 현재 나무의 순서에 따라 베 어야 합 니 다.첫 번 째 나 무 를 베 려 고 할 때 ok [i] = 0, 판단: 1. ok [i - 1] = 1, ok [i + 1] = 1 은 이 나 무 를 베 면 한 조각 이 더 많다 는 뜻 이다. ans +
2. ok [i - 1] = 0, ok [i + 1] = 0 은 이 나무 가 원래 한 조각 이라는 것 을 의미한다. 베 어 낸 후에 ans –
3. ok [i - 1] ^ ok [i + 1] = 1, 이 나 무 를 베 는 것 은 덩어리 에 아무런 영향 을 주지 않 습 니 다.
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
struct data
{
int v,id,ans;
}h[50005],q[50005];
int n,Q,ok[50005];
void read(int &tmp)
{
int ch=getchar();
int fu=1;
tmp=0;
for (;ch<'0'||ch>'9';ch=getchar())
if (ch=='-') fu=-1;
for (;ch>='0'&&ch<='9';ch=getchar())
tmp=tmp*10+ch-'0';
tmp*=fu;
}
bool cmp(data a,data b)
{
return a.v<b.v;
}
bool cmpp(data a,data b)
{
return a.id<b.id;
}
int main()
{
while (scanf("%d%d",&n,&Q)!=EOF)
{
ok[0]=0,ok[n+1]=0;
for (int i=1;i<=n;i++)
ok[i]=1,read(h[i].v),h[i].id=i;
sort(h+1,h+1+n,cmp);
for (int i=1;i<=Q;i++)
read(q[i].v),q[i].id=i;
sort(q+1,q+1+Q,cmp);
int now=0;
int ans=1;
for (int i=1;i<=Q;i++)
{
while (h[now+1].v<=q[i].v&&now+1<=n)
{
int x=h[now+1].id;
ok[x]=0;
if (ok[x-1]&&ok[x+1]) ans++;
if (!ok[x-1]&&!ok[x+1]) ans--;
now++;
}
q[i].ans=ans;
}
sort(q+1,q+1+Q,cmpp);
for (int i=1;i<=Q;i++)
printf("%d
",q[i].ans);
}
return 0;
}
The Monkey King
Accepts: 19 Submissions: 71 Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) 문제 설명그 와 그의 후손 들 은 화 과 산 에서 생활 한다.어느 날, 그의 아들 은 n 개의 복숭아 를 얻 었 다.현재 그들 은 m 명의 원숭이 (오 공 포함) 가 있 는데 그들 은 1 부터 m 까지 표 시 를 받 았 고 오 공의 번 호 는 1 이다.오 공 은 이 복숭아 들 을 그들 자신 에 게 나 누 어 주 려 고 한다.오 공 은 대왕 이기 때문에 그 가 얻 은 복숭아 가 가장 많아 야 한다.오 공 은 몇 가지 다른 분배 방법 이 있 는 지 알 고 싶 어 한다.예 를 들 어 n = 2, m = 3 일 때 는 한 가지 분 법 2000 밖 에 없다.n, m 를 정 했 을 때 당신 의 임 무 는 오 공이 이 복숭아 들 을 분배 할 수 있 는 몇 가지 다른 방법 이 있 는 지 계산 하 는 것 입 니 다.답 이 비교적 크 기 때문에 1000000007 에 남 은 결 과 를 출력 하면 된다.다 중 그룹 테스트 데 이 터 를 입력 하 십시오.입력 파일 의 첫 줄 에 T 조 데이터 가 있 음 을 나타 내 는 정수 T 가 있 습 니 다.다음 T 줄 에는 n 과 m 가 포함 되 어 있 습 니 다.그들의 의 미 는 위 에서 이미 언급 되 었 다.
[Technical Specification] 모든 입력 은 정수 입 니 다.1 ≤ T ≤ 25 1 ≤ n, m ≤ 100000 출력 설명 은 각 데이터 가 한 줄 에서 출력 하 는 답 입 니 다.샘플 을 보면 더 많은 정 보 를 얻 을 수 있 습 니 다.입력 샘플 22 23 5 출력 샘플 15 Hint 2 조 샘플 중 5 가지 배분 방안 이 있 는데, 이들 은 21, 0, 0, 2, 0, 2, 0, 0, 1, 0, 2, 0, 0, 0, 0, 1, 3, 0 0 이다.
용 척 원리 + 다 중 집합 배열 조합 ~
(이틀 전에 하나 했 는데 [BZOJ 1272] 시험 을 봤 는데 TT 가 생각 나 지 않 았 어 요)
오 공이 나 누 어 얻 은 복숭아 수 는 i 이다. 그러면 다른 사람 이 나 누 어 얻 은 복숭아 수 는 모두 < i, 다른 사람 이 나 누 어 얻 은 복숭아 수 < i 의 분 법 은 용 척 원리 로 한다.
아무런 제한 없 는 분 법 - (원숭이 한 마리 ≥ i 의 분 법 이 있 음) + (원숭이 두 마리 ≥ i 의 분 법 이 있 음)...
n - i 개의 복숭아 를 m - 1 마리 의 원숭이 에 게 나 누 어 주 는 방법 을 어떻게 계산 합 니까? 그 중에서 j 마리 의 원숭이 가 나 누 어 얻 은 복숭아 ≥ i 의 분 법 이 있 습 니까?
먼저 j 마리 의 원숭이 C (m - 1, j) 를 뽑 으 면 i - 8727 ° j 개의 복숭아 는 이미 귀속 되 었 다.문 제 는 n - i - i - 8727 ° j 개의 복숭아 를 m - 1 마리 의 원숭이 에 게 나 누 어 주 고 칸막이 법 으로!
복숭아 는 1 로 보고 원숭이 는 0 으로 본다.
C(n−i−i∗j+m−2,m−2)
마지막 답 은...
C(m−1,j)∗C(n−i−i∗j+m−2,m−2)
이렇게 두 층 의 매 거 는 O (n2) 의 복잡 도로 보이 지만 실제로는 n + n2 + n3 + n4 + = nlogn 의 ~
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode(61)UniquePath1제목은 다음과 같습니다. A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
