2019-2020 ICPC North-Western Russia Regional Contest[부분 문제풀이]

제목:
ICPC 2019-2020 North-Western Russia Regional Contest
E:Equidistant
제목:
나무 한 그루를 정하고 m개의 관건을 제시하면 이 점에서 m개의 관건까지의 거리가 같을 수 있는 점을 찾아낼 수 있다
분석:
(1) 직관적인 방법은 뿌리 dp를 바꾸는 것이다. 각 노드가 뿌리일 때 서브트리의 관건은 그 거리의 최대치와 최소치, 차 최대치와 차 최소치로 미리 처리한다. 뿌리 dp를 바꿀 때 모든 관건점에서 뿌리의 최대치와 최소치가 같은지 직접 본다.
(2) 문제는 하나의 점을 찾는 것으로 전환할 수 있다. 모든 관건점을 그 거리의 최대치로 최소화할 수 있다. 이 점은 반드시 관건점의 직경의 중점이다. 이 점은 반드시 유일한 것이다. 먼저 양쪽 dfs에서 직경을 찾은 다음에 중점을 찾아 마지막으로 이 중점이 문제의 뜻을 충족시키는지 판단하면 된다.
코드:

#include 
 
#define f first
#define s second
#define pii pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
const int maxn = 2e5+25;
int head[maxn],n,m,u,v,cnt,d[maxn],tag[maxn],p[maxn];
struct edge{
    int to,nxt;
}e[maxn<<1];
inline void add(int u,int v){
    e[++cnt] = (edge){v,head[u]};
    head[u] = cnt;
}
int x,len;
void dfs(int u,int fa,int step){
    if(tag[u]&&step>=len){
        x = u; len = step;
    }
    for(int i = head[u];i > 0;i = e[i].nxt){
        int v = e[i].to; if(v == fa) continue;
        dfs(v,u,step+1);
    }
}
bool flag;
int q[maxn],k;
void dfs2(int u,int fa){
    q[k++] = u;
    if(u == x){
        flag = true; return;
    }
    for(int i = head[u];i>0&&!flag;i = e[i].nxt){
        int v = e[i].to; if(v == fa) continue;
        dfs2(v,u); 
    }
    if(!flag) k--;
}
void dfs3(int u,int fa,int depth){
    d[u] = depth;
    for(int i = head[u];i > 0;i = e[i].nxt){
        int v = e[i].to; if(v == fa) continue;
        dfs3(v,u,depth+1);
    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 1;i < n; ++i){
        scanf("%d %d",&u,&v);
        add(u,v); add(v,u);
    }
    for(int i = 1;i <= m; ++i){
        scanf("%d",p+i); tag[p[i]] = 1;
    }
    if(m == 1){
        puts("YES"); puts("1"); return 0;
    }
    dfs(p[1],0,0); int y = x; len = 0;
    dfs(y,0,0); dfs2(y,0);
    if(k % 2 == 0) return puts("NO");
    else k /= 2;
    dfs3(q[k],0,1);
    for(int i = 2;i <= m; ++i){
        if(d[p[i]] != d[p[i-1]]) return puts("NO");
    }
    puts("YES");
    cout << q[k] << '
';
    return 0;
}

H:High Load Database
제목:
N 개의 수를 정해서, 이 수를 연속적인 블록으로 나누고, 각 블록의 수는 <=t로 나누어, 최소한 몇 개의 블록으로 나눌 수 있는지 구하세요
분석:
t의 값을 알면 O(N)가 가장 적은 블록 수를 욕심내서 구할 수 있지만 현재 t가 여러 개 있으면 직접 한 번 훑어보지 못하고 최적화를 고려한다.원수 그룹에 대해 접두사와 접두사를 한 번 구하면 매번 다음 경계의 위치를 2분할 수 있다. 그러면 이렇게 복잡도의 상한선은 총 블록수 *logN이다.각 t에 대해 그의 블록 수는 N/t 정도이고 같은 t에 대해 한 번만 구하면 이것은 조화급수이다.복잡성 O(NlogNlogN)
한참을 생각하고서야 비로소 발견하였다.
코드:

#include 
 
#define f first
#define s second
#define pii pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
const int maxn = 1e6+15;
const int mod = 1e9+7;
int n,q,t,m,a[maxn],sum[maxn],ans[maxn];
int solve(int t){
    int res = 0,pos = 0,num;
    while(pos < n){
        num = sum[pos]+t;
        pos = lower_bound(sum+pos+1,sum+n+1,num)-sum;
        if(sum[pos] > num) pos--;
        res++;
    }
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n; ++i){
        scanf("%d",a+i); m = max(m,a[i]);
        sum[i] = sum[i-1] + a[i];
    }
    scanf("%d",&q);
    while(q--){
        scanf("%d",&t);
        if(t < m) puts("Impossible");
        else if(ans[t]) printf("%d
",ans[t]);
        else printf("%d
",ans[t] = solve(t));
    }
    return 0;
}

I:Ideal Pyramid
제목:
N개의 기둥의 좌표와 높이를 정하여 가장 작은 사각뿔(사면과 밑면의 협각은 45도)을 찾아 모든 기둥이 안에 있게 하다
분석:
사각뿔의 사면과 밑면의 협각이 45도이기 때문에 그것의 높이만 알면 그것의 형상은 유일하게 확정된다.그러면 그것의 높이를 2분으로 나누고 어떻게 체크를 해야 하는지를 고려하여 하나의 기둥에 대해 그 안에 있어야 한다는 것을 발견할 수 있다. 그러면 사각뿔의 저면 중심은 이 기둥의 주위가 정사각형인 구역 안에서 N개의 정사각형에 대해 교집합을 구하면 된다.
코드:

#include 
 
#define f first
#define s second
#define pii pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
const int maxn = 2000;
struct point{
    LL x,y,h;
}p[maxn];
LL ansx,ansy,ans,n;
struct node{
    LL x,y,xx,yy;
};
node merge(node a,node b){
    return (node){max(a.x,b.x),max(a.y,b.y),min(a.xx,b.xx),min(a.yy,b.yy)};
}
bool check(LL mid){
    LL t = mid - p[1].h;
    node s = (node){p[1].x-t,p[1].y-t,p[1].x+t,p[1].y+t};
    for(int i = 2;i <= n; ++i){
        t = mid - p[i].h;
        s = merge(s,(node){p[i].x-t,p[i].y-t,p[i].x+t,p[i].y+t});
        if(s.xx < s.x || s.yy < s.y) return false;
    }
    ans = mid; ansx = s.x,ansy = s.y;
    return true;
}
int main(){
    cin >> n;
    LL L = 0, R = 1e18;
    for(int i = 1;i <= n; ++i){
        cin>>p[i].x>>p[i].y>>p[i].h;
        L = max(L,p[i].h);
    }
    while(L <= R){
        LL mid = (L+R)>>1;
        if(check(mid)) R = mid - 1;
        else L = mid + 1;
    }
    cout << ansx << " " << ansy << " " << ans << '
';
    return 0;
}

J:Just the Last Digit
제목:
유방향 무환도 한 장이 있는데, 각 점에서 다른 점까지의 방안 수의 개수를 제시하여, 이 그림을 복원하게 한다
분석:
쉽게 발견할 수 있듯이 s에서 e까지의 방안에서 직행하거나 k(s코드:

#include 
 
#define f first
#define s second
#define pii pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
const int maxn = 625;
char a[maxn][maxn];
int n,mp[maxn][maxn];
int main(){
    cin >> n;
    for(int i = 1;i <= n; ++i) scanf("%s",a[i]+1);
    for(int s = 1;s <= n; ++s){
        for(int e = s+1;e <= n; ++e){
            int sum = 0;
            for(int k = s+1;k < e; ++k){
                if(mp[s][k]) sum += a[k][e]-'0';
            }
            if(sum%10 != a[s][e]-'0') mp[s][e] = 1;
        }
    }
    for(int i = 1;i <= n; ++i){
        for(int j = 1;j <= n; ++j)
            printf("%d",mp[i][j]);
        puts("");
    }
    return 0;
}

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

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

[CodeForces][단조로운 대기열 최적화 DP] 939F Cutlet

스테이크 한 조각은 양면 모두 N N N 초간 구워야 하는데, 지금은 K K 시간대 [L i, R i] [L i, R i] [Li, Ri]만 면을 뒤집을 수 있고, 이 시간 안에 이 스테이크를 마음대로 뒤집을 수 있...

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

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

2019-2020 ICPC North-Western Russia Regional Contest[부분 문제풀이]

좋은 웹페이지 즐겨찾기