BestCoder Round #73(div.2)

경기 링크: 여 기 를 클릭 하 세 요
Rikka with Chess
Accepts: 393

Submissions: 548
Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)
문제 설명

   $\times m$

입력 설명

         $\leq 10)$

출력 설명

              ，           。

입력 샘플

출력 샘플

1
2
2

[사고방식]:
우선, 짝수 줄 에 반 을 취하 고 짝수 열 에 반 을 취하 면 [n/2] + [m/2] [n/2] + [m/2] + [m/2] (아래 추출) 의 해 를 얻 을 수 있 습 니 다. 이것 이 답 의 하계 라 는 것 만 설명 하면 됩 니 다.첫 번 째 열 을 고려 하면 매번 조작 할 때마다 두 개의 첫 번 째 열 에 있 는 인접 요 소 를 똑 같이 만 들 수 있다. 첫 번 째 열 에는 n - 1n - 1 쌍 의 인접 요소 가 있다. 그러면 첫 번 째 열 을 똑 같이 만 드 는 횟수 는 [(n - 1)/2] [(n - 1)/2] (위 에서 정리) 이 고 같은 이치 로 첫 번 째 줄 을 고려 하면 된다.
코드:

/*
Problem:BC#73 Rikka with Chess
Author :javaherongwei
Runtime:0ms
Language: G++
Result  :Accepted
*/
#include<stdio.h>
int main()
{
    int i,j,k,t,n,m,ans;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        printf("%d
",n/2+m/2);
    }
    return 0;
}

Rikka with Graph
Accepts: 123

Submissions: 525
Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)
문제 설명

    ，          ，                ，         ：

      $， （ ） 。 。 ， ， ？$

입력 설명

               $\leq 30)$

출력 설명

。

입력 샘플

출력 샘플

[사고방식]:
양보 하 다 nn 개 점 연결 최소 필요 n-1n−1 한 쪽, 그래서 최대 두 쪽 만 삭제 할 수 있 습 니 다. 우 리 는 삭제 한 두 쪽 (또는 유일한 한 쪽) 을 매 거 진 다음 에 폭력 적 으로 BFS 가 연관 성 을 판단 하면 됩 니 다.시간 복잡 도 O(n^3)O(n3).
코드:

/*
Problem:BC#73 Rikka with Graph
Author :javaherongwei
Runtime:296ms
Language: G++
Result  :Accepted
*/
#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cassert>
#include <climits>
#include <ctime>
#include <numeric>
#include <vector>
#include <algorithm>
#include <bitset>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <complex>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <string>
#include <sstream>
#include <set>
#include <stack>
#include <queue>
using namespace std;
template<class T> inline T sqr(T x)
{
    return x * x;
}
typedef long long LL;
typedef unsigned long long ULL;
typedef long double db;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
typedef pair<LL, LL> PLL;
typedef pair<LL, int> PLI;
typedef pair<db, db> PDD;
#define MP make_pair
#define PB push_back
#define sz(x) ((int)(x).size())
#define mem(ar,val) memset(ar, val, sizeof(ar))
#define istr stringstream
#define FOR(i,n) for(int i=0;i<(n);++i)
#define forIt(mp,it) for(__typeof(mp.begin()) it = mp.begin();it!=mp.end();it++)
const double EPS = 1e-6;
const int INF = 0x3fffffff;
const LL LINF = INF * 1ll * INF;
const double PI = acos(-1.0);
const int maxn = 1e5+10;

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define lowbit(u) (u&(-u))

using namespace std;
#define LETTER 26
#define lowbit(a) a&-a

int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
int dir6[6][3]= {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};///    
int movv[5][2]= {{1,0},{0,1},{0,0},{-1,0},{0,-1}};

inline LL read()
{
    int c=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
    return c*f;
}
int a[maxn],b[maxn],c[maxn];
char s1[maxn],s2[maxn];
struct node
{
    int u,v;
} edge[maxn];
int n;
int fa[maxn];
int Find(int x)
{
     return x==fa[x]?x:fa[x]=Find(fa[x]);
}
int solve(int a,int b)
{
    for(int i=1; i<=n; ++i) fa[i]=i;
    for(int i=1; i<=n+1; ++i)
    {
        if(i==a|| i==b) continue;
        int uu=Find(edge[i].u),vv=Find(edge[i].v);
        if(uu!=vv) fa[uu]=vv;
    }
    int sum=0;
    for(int i=1; i<=n; i++)
    {
        if(fa[i]==i)
        {
            sum++;
            if(sum>1) return false;
        }
    }
    return true;
}
int main()
{
    int t; t=read();
    while(t--)
    {
        int ret=0;
        n=read();
        for(int i=1; i<=n+1; ++i)
            scanf("%d%d",&edge[i].u,&edge[i].v);
        for(int i=1; i<=n+1; ++i)
            for(int j=i; j<=n+1; ++j)
                ret+=solve(i,j);
        printf("%d
",ret);
    }
    return 0;
}

Rikka with Array
Accepts: 2

Submissions: 22
Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)
문제 설명

    ，          ，                ，         ：

        $n A（ 1 n），A_i i 1 ， A[1]=1, A[3]=2, A[10]=2。 A A[i]>A[j] (i,j)(1 \leq i < j \leq n) 。 ， ， ？$

입력 설명

               $\leq 10)$

출력 설명

                  ，        ，           $。$

입력 샘플

1
10

출력 샘플

Hint

   $， 。 7。$

[사고방식]:
이것 은 디지털 DP 의 제목, 상태 임 이 분명 하 다. dp[i][j][k]dp[i][j][k] 에서 ii 비트 jj, 현재 두 개의 수 와 주어진 nn 의 크기 관 계 는? kk, 그리고 이 두 개의 현재 위치의 값 을 폭력 적 으로 매 거 한 다음 에 옮 기 면 됩 니 다.시간 복잡 도 O(\log^2 n)O(log2n).
후보 ~ ~
Rikka with Sequence
Accepts: 0

Submissions: 8
Time Limit: 3000/1500 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)
문제 설명

    ，          ，                ，         ：

        $， 。 （ ）。 ， ， 。 ， ， ？$

입력 설명

         $\leq 1000)$

출력 설명

             ，                ，            （      ）。

입력 샘플

1
3 5
1 2 5

출력 샘플

1 3.000

Hint

         $。$

[사고방식]:
이것 은 사고 함량 이 별로 없 는 문제 이지 만 세부 사항 이 비교적 많다.
일단 정 답 은 넘 지 않 습 니 다. nn, 왜냐하면 우 리 는 원래 평균 수의 위치 에 직접 가입 할 수 있 기 때문이다 nn 개수, 이렇게 중위 수 는 평균 수 와 같다.
그 다음 에 답 은 2 분 성 (첫 번 째 질문) 을 만족 시 킵 니 다. 가입 이 있 으 면... ii 개수 의 방안 은 우리 가 더 많은 수 를 현재 평균 수의 위치 에 놓 을 수 있 는데 분명히 요 구 를 만족 시 킬 수 있다.그래서 우 리 는 먼저 2 분 의 답 을 얻 을 수 있다. 그러면 문 제 는 가입 으로 바 뀌 었 다. KK 개 수 는 평균 수가 중위 수 보다 작 음 을 만족 시 키 는 동시에 평균 수 를 최소 화 시킨다.
처음 주 시 는 걸 발견 할 수 있어 요. nn 개수 [1,m][1,m] 갈라놓다 n+1n+1 한 구간 에서 우 리 는 중위 수가 어느 구간 에 있 는 지 매 거 할 수 있다. 물론 여기 서 분류 토론 을 해 야 한다. 대체적인 상황 은 이렇게 다양 하 다.
1. 총 수 는 홀수 이 고 중위 수 는 원래 제 시 된 수 이다.
2. 총 수 는 홀수 이 고 중위 수 는 가입 수 이다.
3. 총 수 는 짝수 이 고 중위 수 는 원래 제 시 된 두 수의 평균 수 이다.
4. 총 수 는 짝수 이 고 중위 수 는 가입 한 수 와 그 보다 큰 원래 제 시 된 수의 평균 이다.
5. 총 수 는 짝수 이 고 중위 수 는 가입 한 수 와 그 보다 작은 원래 제 시 된 수의 평균 수 이다.
6. 총 수 는 짝수 이 고 중위 수 는 두 개의 새로 가입 한 수의 평균 이다.
모든 상황 에 대하 여 우 리 는 중위 수 를 설정 할 수 있다. xx, 그리고 직접 욕심 을 내 면 방정식 을 얻 을 수 있 습 니 다. 이 방정식 을 풀 고 합 법 적 인지 판단 하고 답 을 업데이트 하면 됩 니 다.(물론 다시 생각해 보면 이런 상황 이 모두 고려 해 야 하 는 것 이 아니 라 두 가지 가 답 에 영향 을 주지 않 는 다 는 것 을 알 수 있다)
시간 복잡 도 O (n\\log n) O (nlogn) 보충 ~ ~ ~
Rikka with Phi
Accepts: 5

Submissions: 66
Time Limit: 16000/8000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)
문제 설명

        $n A， m 。 1 \; l \; r$

입력 설명

         $\leq 100)$

출력 설명

           ，           。

입력 샘플

1
10 10
56 90 33 70 91 69 41 22 77 45
1 3 9
1 1 10
3 3 8
2 5 6 74
1 1 8
3 1 9
1 2 10
1 4 9
2 8 8 69
3 3 9

출력 샘플

80
122
86

[사고방식]:
10 ^ 710 7 의 수가 가장 많은 것 을 알 수 있 습 니 다. O(log(n))O(log(n)) 다음 이 11 이 되 기 때문에 같은 11 이 아 닌 수 를 한 점 으로 줄 이 고 균형 트 리 로 유지 하 는 것 을 고려 할 수 있다.피 를 구 할 때마다 밸 런 스 트 리 에서 이 구간 을 꺼 내 고 피 를 폭력 적 으로 구 합 니 다. 한 단락 이 11 이 되면 밸 런 스 트 리 에서 지 웁 니 다. 마지막 으로 답 을 집계 할 때 구간 에서 삭 제 된 11 에 답 을 더 하면 됩 니 다. 시간 복잡 도 O (n + m) O (n + m) logn) O ((n + m) logn)
보충 해 야 합 니 다 ~ (밸 런 스 트 리: 빈 나무 또는 좌우 두 나무의 높이 차 이 는 절대 1 을 초과 하지 않 으 며, 좌우 두 개의 나 무 는 모두 밸 런 스 이 진 트 리 입 니 다. 구조 와 조정 방법 으로 이 진 트 리 를 균형 시 키 는 데 자주 사용 되 는 알고리즘 은 빨 간 검 은 나무, AVL, Treap 등 이 있 습 니 다. 최소 이 진 트 리 의 노드 공식 은 다음 과 같 습 니 다 F (n - 1) = F (n - 1) + F (n - 2)+ 1 이것 은 재 귀적 인 수열 과 유사 합 니 다. Fibonacci 수열 을 참고 할 수 있 습 니 다. 1 은 뿌리 노드 이 고 F (n - 1) 는 왼쪽 서브 트 리 의 노드 수량 이 며 F (n - 2) 는 오른쪽 서브 트 리 의 노드 수량 입 니 다.)

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

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[HDU] 4089 활성화 확률 DP

dp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

BestCoder Round #73(div.2)

좋은 웹페이지 즐겨찾기