Codeforces Round #526(Div.2) A-D

독종 문제.

A문제:
문제 풀이:
제면에서는 엘리베이터가 x층부터 i층을 마중하는 사람이 i층에서 1층, 그리고 1층에서 i층까지 있는데 이 엘리베이터는 매우 귀신이어서 매번 사람을 배웅할 때마다 x층으로 돌아간다.이 엘리베이터는 하루에 몇 층을 오르내리느냐고 물었다.
데이터 범위 n<=100을 한 번 보면 x를 매거한 다음에 층을 매거하여 답을 가장 적게 구한다.복잡도 n방
제목:https://codeforces.com/contest/1084/problem/A
코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f3f
const int N=3e5+7;
const long long mod=1e9+7;
char str[N];
int a[120];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int ans=INF,res;
    for(int i=1;i<=n;i++){
        res=0;
        for(int j=1;j<=n;j++){
            res+=2*(abs(i-j)+j-1+i-1)*a[j];
        }
        ans=min(ans,res);
    }
    printf("%d
",ans);
    return 0;
}

B:
(처음에는 정말 제목이 뭔지 모르겠다는 뜻)
문제 풀이:
제목은 n컵vi리터의 무언가를 주고 s리터의 무언가를 받으라고 했습니다. 받은 후 최소한의 컵 중의 물건은 최대 얼마까지 받을 수 있는지 요구합니다.
이 문제는 ∑vi를 먼저 한 번 구한 다음에 결과를 s를 빼면 남은 가설이다. 그가 가장 적게 분배할 수 있다고 가정하면 (∑vi-s)/n이다.
물론 컵이 원래 전에 구한 값보다 작다면 가장 작은 최대는min(min),(∑vi-s)/n)
제목:https://codeforces.com/contest/1084/problem/B
코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f3f
const int N=3e5+7;
const long long mod=1e9+7;
char str[N];
long long a[1200];
int main(){
    long long n,m,sum=0,minn=INF;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum+=a[i];
        if(minn>a[i]) minn=a[i];
    }
    if(sum

C문제:
문제 풀이:
제목은 문자열을 질서정연하게 선택해서 모든 요소가 'a' 이고, 모든 요소가 원열에 있는 위치 사이에 'b' 가 존재한다는 것을 보장하는 것이다.
원열을 몇 개의 블록으로 미리 처리하여 각 블록 간에 서로 연결할 수 있고 블록 간의 원소가 서로 연결되지 않는다. 즉, 블록과 블록 사이의 a에는 반드시'b'가 존재한다. 그러면 우리는 답안에 대해 첫 번째 블록에서 마지막 블록까지 일일이 열거할 수 있다. 한 블록을 훑어보지 않고 답안에 답안 자체를 덧붙인다. * 블록 중의 a의 개수와 블록 중의 a의 개수를 더하는 자체
즉sum+=(sum*que[i])%mod+que[i]; sum%=mod;
(현재 블록의 모든 요소가 앞의 모든 답안과 연결되고 단독 현재 블록으로 이해할 수 있음)
제목:https://codeforces.com/contest/1084/problem/C
코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f3f
const int N=3e5+7;
const long long mod=1e9+7;
char str[N];
long long que[N];
int tot;
int arr[N],pp[N],wei[N];
int main(){
    scanf("%s",str);
    tot=0;
    int len=strlen(str);
    int tmp=0;
    for(int i=0;i

D:
문제 풀이:
한 그루의 나무에 있는 지름의 점권을 구하는 거예요. - 변권이 제일 커요.
나무에서 가장 큰 지름을 구하는 dp라고 생각할 수 있다.
유지 보수 데이터 d[N]는 이 노드가 하위 노드를 유통하는 최대 지름을 나타냅니다.
한 노드의 지름이 가장 큰 라인이 이 노드를 통과하면 다음과 같은 몇 가지 상황이 될 수 있다
1.오직 이 점 d[x]=a[x];
2. 가장 큰 하위 노드와 연결된 d[x]=max(d[x], d[x]+d[y]-wei[i]) 주: y는 하위 노드, wei[i]는 x에서 y까지의 경계권
3. 그 다음에 대자 노드와 최대자 노드는 x를 통해 연결된다(답안 업데이트에 사용되며 d[x]값 업데이트에 사용되지 않는다)ans=max(ans, a[x]+tmp1+tmp2)
제목:https://codeforces.com/contest/1084/problem/D
코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f3f
const int N=3e5+7;
const long long mod=1e9+7;
char str[N];
int head[N];
int NEXT[3*N],ver[3*N];
long long wei[3*N];
long long dp[N],a[N];
int n,tot;
long long ans;
void init(){
    tot=1;
    ans=0;
    memset(head,-1,sizeof(head));
}
long long Max(long long a,long long b){
    if(a>b) return a;
    return b;
}
void link(int u,int v,int w){
    ver[++tot]=v;
    NEXT[tot]=head[u];
    head[u]=tot;
    wei[tot]=w;
    ver[++tot]=u;
    NEXT[tot]=head[v];
    head[v]=tot;
    wei[tot]=w;
}
void dfs(int x,int pre){
    dp[x]=a[x];
    long long res=0,rres=0;
    for(int i=head[x];i;i=NEXT[i]){
        int y=ver[i];
        if(y==pre) continue;
        dfs(y,x);
        if(res<=dp[y]-wei[i]){
            if(rres<=dp[y]-wei[i]){
                res=rres;
                rres=dp[y]-wei[i];
            }
            else {
                res=dp[y]-wei[i];
            }
        }
    }
    dp[x]=Max(dp[x],a[x]+rres);
    ans=Max(ans,dp[x]);
    ans=Max(ans,rres+res+a[x]);

}
int main(){
    int u,v;
    long long w;
    scanf("%d",&n);
    init();
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i

E(보정)

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.

Codeforces Round #526(Div.2) A-D

좋은 웹페이지 즐겨찾기