2019 자바 스타 프로 그래 밍 프로 그래 밍 (개인전)

글 목록

A - 예의 상 왕래 (오열)

C - 찌 질 이 역 주 행 (시 뮬 레이 션)

D - 구산 훈련 (질량 인수 분해)

E - 하위 문자열 조회 (접두사 와)

F - 경기 문제 분석 (시 뮬 레이 션)

G - CCPC 생방송 (시 뮬 레이 션)

H - 엘리베이터 사랑 이야기 (시 뮬 레이 션)

A - 예의 상 왕래 (오 열)
원본 링크:https://vjudge.net/contest/340569#problem/A
제목: 선물 을 받 고 다시 다른 위치 에 놓 고 방안 이 몇 개 냐 고요?
사고: 템 플 릿 문 제 를 잘못 배열 하고 잘못된 배열 공식 을 직접 사용 하여 모형 을 만 들 면 된다.
롱 롱 형 을 사용 해 야 합 니 다. 그렇지 않 으 면 WA!
오 열 공식 을 모 르 고 어떻게 왔 는 지 여기 보 세 요: 오 열 공식 을 철저히 이해 하 세 요.
Code（C++）：

#include 
#include 
using namespace std;
typedef long long ll;
ll dp[105];
const int N=1e9+7;
int main(){
    int t;  scanf("%d",&t);
    dp[1]=0;
    dp[2]=1;
    for(int i=3;i<=100;i++)
        dp[i]=(i-1)*(dp[i-1]+dp[i-2])%N;
    while(t--){
        int n;
        scanf("%d",&n);
        printf("%lld
",dp[n]);
    }
}

C - 찌 질 이 역습 (시 뮬 레이 션)
원본 링크:https://vjudge.net/contest/340569#problem/C
제목: 남자 의 매력 치 는 마이너스 정수 로 표시 하고, 여자 의 매력 치 는 정수 로 표시 하 며, 특정 위치의 이웃 과 해당 위치의 주인 이 성별 이 다 르 면 총 점 에 이웃 의 매력 치 의 절대 치 를 더 해 빼 지 않 는 다.이곳 의 매력 은 이 위치의 매력 치 를 포함 하지 않 는 다 는 것 을 주의해 라.
사고: 모든 위치의 매력 치 는 배열 a [] [], 배열 b [] [] 에 저장 되 어 각 위치 주위 의 매력 치 를 합 친다.그리고 각 위 치 를 옮 겨 다 니 며 이 위치 주위 의 매력 치 를 합 쳐 성별 이 같은 경우 매력 치 절대 치 를 줄 이 고 그렇지 않 으 면 매력 치 절대 치 를 더 합 니 다.마지막 으로 모든 위 치 를 옮 겨 다 니 며 최대 매력 치가 있 는 위치 와 총 화 를 계속 업데이트 합 니 다.
Code（C++）：

#include 
#include 
using namespace std;
int a[25][25],b[25][25];
int main(){
    int n,m;
    while(cin>>n>>m){
        if(n==0 && m==0)
            break;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>a[i][j];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                b[i][j]=0;
                if(a[i][j]>0){
                    if(a[i-1][j]!=0)
                        b[i][j]-=a[i-1][j];
                    if(a[i+1][j]!=0)
                        b[i][j]-=a[i+1][j];
                    if(a[i][j-1]!=0)
                        b[i][j]-=a[i][j-1];
                    if(a[i][j+1]!=0)
                        b[i][j]-=a[i][j+1];
                }
                else if(a[i][j]<0){
                    if(a[i-1][j]!=0)
                        b[i][j]+=a[i-1][j];
                    if(a[i+1][j]!=0)
                        b[i][j]+=a[i+1][j];
                    if(a[i][j-1]!=0)
                        b[i][j]+=a[i][j-1];
                    if(a[i][j+1]!=0)
                        b[i][j]+=a[i][j+1];
                }
            }
        }
        int x=1,y=1,ans=b[1][1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(b[i][j]>ans){
                    ans=b[i][j];
                    x=i,y=j;
                }
            }
        }
        cout<<x<<" "<<y<<" "<<ans<<endl;
    }
}

D - 구산 훈련 (질 인수 분해)
원본 링크:https://vjudge.net/contest/340569#problem/D
제목: n 개의 숫자 a [1], a [2]... a [n] 와 m 개의 질문 을 드 립 니 다.모든 질문 은 l, r, d 를 입력 하고 구간 l 과 r 에서 a [l] * a [l + 1] *... * a [r] 가 d 로 제 거 될 수 있 는 지 물 어 봅 니 다.
사고: 합숙 훈련 을 할 때 TLE 를 직접 옮 겨 다 니 는 것 을 알 았 지만 새로운 생각 이 없 었 습 니 다. 자바 대 정수 류 의 폭력 을 옮 겨 다 녔 습 니 다. 과연 TLE 입 니 다.k 가 d 인지 아 닌 지 에 대해 우 리 는 이 두 개의 수 에 대해 질 인 수 를 분해 할 수 있다. 만약 에 d 에 대한 모든 질 인 수 를 만족 시 키 면 k 에서 모두 나타 난 적 이 있 고 k 에서 나타 난 횟수 가 d 와 같은 출현 횟수 보다 크 면 k 는 d 의 배수 이다.
Code（C++）：

#include 
#include 
#include 
#include 
using namespace std;
const int N=1e5+100;
vector<int> v[N];
int main(){
    int t;  scanf("%d",&t);
    while(t--){
        for(int i=1;i<N;i++)    //     vector
            v[i].clear();
        int n,m;
        scanf("%d%d",&n,&m);
        int x;
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            for(int j=2;j*j<=x;j++){
                while(!(x%j)){
                    v[j].push_back(i);  //       ，         ，                  
                    x/=j;
                }
            }
            if(x>1) v[x].push_back(i);  //        ，     ，       
        }
        while(m--){
            int l,r,d;
            scanf("%d%d%d",&l,&r,&d);
            int vis=0;
            for(int i=2;i*i<=d;i++){    //  d    
                int sum1=0;
                while(!(d%i)){
                    sum1++; //          
                    d/=i;
                }
                if(sum1){
                    int sum2=upper_bound(v[i].begin(),v[i].end(),r)-lower_bound(v[i].begin(),v[i].end(),l); //          
                    if(sum2<sum1){  //  d       k  ，    
                        vis=1;
                        break;
                    }
                }
            }
            if(d>1){    //  ，   d       
                int sum2=upper_bound(v[d].begin(),v[d].end(),r)-lower_bound(v[d].begin(),v[d].end(),l);
                if(!sum2)   vis=1;
            }
            if(vis)
                printf("No
");
            else
                printf("Yes
");
        }
    }
    return 0;
}

E - 하위 문자열 조회 (접두사 와)
원본 링크:https://vjudge.net/contest/340569#problem/E
제목: 검색 할 구간 의 사전 순서 가 가장 작은 하위 문자열 을 제 한 된 조회 횟수 에 출력 할 문자열 을 지정 합 니 다.
사고: 주어진 구간 에서 사전 순서 가 가장 작은 알파벳 이 나타 나 는 횟수 를 찾 습 니 다.
주의: cin, cout 로 TLE 를 할 것 같 습 니 다.
Code（C++）：

#include 
#include 
#include 
using namespace std;
const int N=1e5+10;
char s[N];
int a[N][30];   //      ，      
int main(){
    int t;  scanf("%d",&t);
    for(int k=1;k<=t;k++){
        memset(a,0,sizeof(a));  //          
        int n,m;
        scanf("%d%d",&n,&m);
        scanf("%s",s+1);    //      
        printf("Case #%d:
",k);
        for(int i=1;i<=n;i++){
            a[i][s[i]-'A']++;   //             
            for(int j=0;j<26;j++)   //     
                a[i+1][j]=a[i][j];  //              
        }
        while(m--){
            int l,r;
            scanf("%d%d",&l,&r);
            for(int j=0;j<26;j++){
                //                        ，           
                if(a[l-1][j]!=a[r][j]){ //       ，           ，    
                    printf("%d
",a[r][j]-a[l-1][j]);
                    break;
                }
            }
        }
    }
    return 0;
}

F - 경기 문제 분석 (시 뮬 레이 션)
원본 링크:https://vjudge.net/contest/340569#problem/F
제목: 시험 문제 자 중 최소 코드 바이트 수 와 AC 팀 에서 선수 가 가장 작은 코드 바이트 수 를 출력 하고 존재 하지 않 으 면 N / A 를 출력 합 니 다.
사고방식: 직접 시 뮬 레이 션 하면 된다.
Code（C++）：

#include 
#include 
#include 
using namespace std;
int a[100],b[505];
int main(){
    int t;  cin>>t;
    for(int k=1;k<=t;k++){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        int n,m;
        cin>>n>>m;
        int minn1=70000;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            minn1=min(minn1,a[i]);
        }
        int minn2=70000;
        for(int i=1;i<=m;i++){
            cin>>b[i];
            minn2=min(minn2,b[i]);
        }
        cout<<"Problem "<<1000+k<<":"<<endl;
        cout<<"Shortest judge solution: "<<minn1<<" bytes."<<endl;
        if(m!=0)
            cout<<"Shortest team solution: "<<minn2<<" bytes."<<endl;
        else
            cout<<"Shortest team solution: N/A bytes."<<endl;
    }
}

G - CCPC 생방송 (시 뮬 레이 션)
원본 링크:https://vjudge.net/contest/340569#problem/G
제목: 어, 그냥 원 제 를 보 세 요. 너무 길 어서 중국어 문 제 는 이해 하기 어렵 지 않 아 요.
사고방식: 아 날로 그 문제, 코드 를 직접 보 세 요. 어렵 지 않 아 요!왼쪽 과 오른쪽 정렬 의 서법 에 주의 하 세 요.
Code（C++）：

#include 
#include 
using namespace std;
int main(){
    int t;  cin>>t;
    for(int k=1;k<=t;k++){
        int rank;   cin>>rank;
        string str;
        cin>>str;
        int prob;   cin>>prob;
        string T;
        cin>>T;
        int x;
        if(T=="Running")
            cin>>x;
        cout<<setw(3)<<setfill(' ')<<right<<rank<<"|";
        cout<<setw(16)<<setfill(' ')<<left<<str<<"|"<<prob<<"|";

        if(T=="Running"){
            cout<<"[";
            for(int i=1;i<=x;i++)
                cout<<"X";
            for(int i=1;i<=10-x;i++)
                cout<<" ";
            cout<<"]"<<endl;
        }
        else{
            cout<<"[";
            if(T=="FB"){
                cout<<"    "<<"AC*";
                int len=T.length();
                for(int i=1;i<=5-len;i++)
                    cout<<" ";
                cout<<"]"<<endl;
            }
            else{
                cout<<"    "<<T;
                int len=T.length();
                for(int i=1;i<=6-len;i++)
                    cout<<" ";
                cout<<"]"<<endl;
            }

        }
    }
    return 0;
}

H - 엘리베이터 사랑 이야기 (시 뮬 레이 션)
원본 링크:https://vjudge.net/contest/340569#problem/H
제목: 엘리베이터 는 위로 한 층 씩 운행 하 는 데 6 초, 아래로 한 층 씩 운행 하 는 데 4 초, 문 을 열 때마다 5 초 (도착 하 는 사람 이 있어 야 문 을 연다), 그리고 다음 사람 은 1 초 를 더 해 야 한다.엘리베이터 는 처음에는 0 층 이 었 고 마지막 에는 0 층 으로 다시 돌아 가 야 임무 가 끝났다.엘리베이터 에 다 녀 오 는 데 걸 리 는 시간 을 구하 다.
사고: 먼저 가 야 할 모든 층 을 작은 것 에서 큰 것 으로 정렬 하고 모든 숫자 에 대해 앞의 숫자 에 비해 똑 같 으 면 이 두 사람 이 모두 이 층 아래 에 있다 는 것 을 의미한다. 그러면 문 을 여 는 시간 을 계산 할 필요 가 없다. 그렇지 않 으 면 문 을 여 는 시간 을 계산 해 야 한다.
Code（C++）：

#include 
#include 
#include 
using namespace std;
int a[105];
int main(){
    int t;  cin>>t;
    while(t--){
        memset(a,0,sizeof(a));
        int n;  cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+1+n);
        int ans=0;
        for(int i=1;i<=n;i++){
            if(a[i]-a[i-1]!=0)
                ans=ans+(a[i]-a[i-1])*6+1+5;
            else
                ans=ans+(a[i]-a[i-1])*6+1;
        }
        ans=ans+a[n]*4;
        cout<<ans<<endl;
    }
    return 0;
}