비고정 상호 테스트 #0 t3

7775 단어

Case 1 제목


다음 코드의 답안을 제시하고 입력을 구성할 것을 요구합니다.그림, n 개 점 m 줄 q 회 질문, 모든 점 대 사이의 최대 권한 값 최소 경로를 출력합니다.

문제풀이


모든 질문의 출력을 하나의 변으로 보고 가장 작은 생성 나무를 세우세요.

Case 3 문제


출력에, 주어진 코드로 실행된 출력과 주어진 출력이 같도록 구조 입력을 요구합니다.주어진 코드: n회 Dijkstra에서 두 점 사이의 최단로를 구합니다

분석하다.


욕심을 생각해봐.

문제풀이


우선 모든 가장 짧은 질문의 결과를 한 변으로 보고 우리는 이 변들을 정렬한다.각 모서리에 대해 두 점의 현재 거리가 이 모서리의 가중치보다 크면 모서리를 추가하여 모든 점 쌍의 거리를 업데이트합니다.정확성이 뚜렷하다.현재 이렇게 하면 변수가 가장 짧다는 것을 증명한다. 이렇게 얻어진 구조 방안이 A라고 가정하고 또 하나의 구조 방안이 B라고 가정하면 변수가 더욱 적다.그러면 A에는 틀림없이 한 변이 존재하고 B에는 존재하지 않는다.따라서 B에서 이 모서리의 두 끝점 사이의 거리는 A에서 이 모서리의 모서리 권한보다 클 것이다.그렇지 않으면 A에서 이 모서리를 선택하지 않습니다.따라서 B라는 방안은 틀림없이 불법이다. 즉, A는 변수가 가장 적은 구조 방안이다.
#include <bits/stdc++.h>
using namespace std;

namespace one {
    const int N=1015, M=1000015;
    struct E {
        int x, y, w;
    }e[M];
    int p[N], n, tot, m;
    bool cmp(const E &a, const E &b) {
        return a.w<b.w;
    }
    int find(int x) {
        return x==p[x]?x:p[x]=find(p[x]);
    }
    void work() {
        scanf("%d%d", &n, &m);
        printf("%d %d
", n, m); int cnt=0; for(int i=1; i<=n; ++i) { for(int j=i+1; j<=n; ++j) { e[cnt].x=i; e[cnt].y=j; scanf("%d", &e[cnt].w); ++cnt; } } for(int i=1; i<=n; ++i) { p[i]=i; } sort(e, e+cnt, cmp); for(int i=0; i<cnt; ++i) { int x=e[i].x, y=e[i].y, fx=find(x), fy=find(y), w=e[i].w; if(fx!=fy) { p[fx]=fy; ++tot; printf("%d %d %d
", x, y, w); } } for(; tot<=m; ++tot) { printf("%d %d %d
", 1, 1, 0); } } } namespace two { const int mo1=9999991, mo2=3333331; typedef long long ll; int ipow(int a, int b, int mo) { int x=1; for(; b; b>>=1, a=(ll)a*a%mo) if(b&1) x=(ll)x*a%mo; return x; } void work() { int n; scanf("%d", &n); printf("%d
", n); for(int i=1; i<=n; ++i) { static char s[100005]; scanf("%s", s+1); int now1=0, now2=0, len=strlen(s+1); for(int i=1; i<=len; ++i) { now1=(now1*10+s[i]-'0')%mo1; now2=(now2*10+s[i]-'0')%mo2; } for(int x=1; x<=10000; ++x) { int h1=ipow(x, x, mo1), h2=ipow(x, x, mo2); if(h1==now1 && h2==now2) { printf("%d ", x); break; } } } } } namespace three { int d[1005][1005]; struct E { int x, y, w; }e[1000005]; bool cmp(const E &a, const E &b) { return a.w<b.w; } void work() { int n, m, cnt=0, tot=0; scanf("%d%d", &n, &m); printf("%d %d
", n, m); for(int i=1; i<=n; ++i) { for(int j=i+1; j<=n; ++j) { e[cnt].x=i; e[cnt].y=j; scanf("%d", &e[cnt].w); cnt++; } } memset(d, 0x3f, sizeof d); for(int i=1; i<=n; ++i) { d[i][i]=0; } sort(e, e+cnt, cmp); for(int it=0; it<cnt; ++it) { int x=e[it].x, y=e[it].y, w=e[it].w; if(w<d[x][y]) { ++tot; printf("%d %d %d
", x, y, w); d[x][y]=d[y][x]=w; for(int i=1; i<=n; ++i) { for(int j=1; j<=n; ++j) { d[i][j]=min(d[i][j], min(d[i][x]+d[x][j], d[i][y]+d[y][j])); } } } } for(; tot<=m; ++tot) { printf("%d %d %d
", 1, 1, 1); } } } namespace four { const int N=55005; vector<int> a[N]; void work() { int n, root; scanf("%d%d", &n, &root); printf("%d %d
", n, root); int csz=0, sz=pow(n, (double)2/3); for(int i=1; i<=n; ++i) { int blc; scanf("%d", &blc); csz+=a[blc].empty(); a[blc].push_back(i); } int j, rt, na; for(j=0, na=a[csz].size(); j<na; ++j) { if(a[csz][j]==root) { swap(a[csz][j], a[csz][0]); break; } } for(int i=csz; i>=1; --i) { rt=a[i][0], j=1, na=a[i].size(); for(; j<sz-1 && j<na; ++j) { printf("%d %d
", a[i][j-1], a[i][j]); } if(j<na) { printf("%d %d
", a[i][j++], root); } for(; j<sz*2-1 && j<na; ++j) { printf("%d %d
", a[i][j-1], a[i][j]); } if(j<na) { printf("%d %d
", a[i][j++], root); } for(; j<na; ++j) { printf("%d %d
", a[i][j-1], a[i][j]); } if(root!=rt) { printf("%d %d
", root, rt); } } } } namespace five { const int N=100015; struct E { int l, r, k, w; }e[N]; bool cmp(const E &a, const E &b) { if(a.w==-1) { return 0; } if(b.w==-1) { return 1; } return a.w<b.w; } int a[N], K[N], vis[N], left, right; void work() { int n, t; scanf("%d%d", &n, &t); printf("%d %d
", n, t); left=1; right=n; int len=n/t, tot=0; for(int i=0; i<t; ++i) { int w; scanf("%d%d", &K[i], &w); if(w==-1) { continue; } e[tot].l=i*len+1, e[tot].r=i*len+len; e[tot].k=len-K[i]+1; e[tot].w=w; ++tot; } sort(e, e+tot, cmp); for(int i=0; i<tot; ++i) { int l=e[i].l, k=e[i].k, w=e[i].w; for(int j=1; j<k; ++j, ++l) { while(vis[left]) { ++left; } a[l]=left; vis[left]=1; ++left; } a[l]=w; vis[w]=1; } for(int i=tot-1; i>=0; --i) { int r=e[i].r, k=e[i].k; for(int j=0; j<(len-k); ++j, --r) { while(vis[right]) { --right; } a[r]=right; vis[right]=1; --right; } } for(int i=1; i<=n; ++i) { if(a[i]) { continue; } while(vis[right]) { --right; } a[i]=right; --right; } for(int i=1; i<=n; ++i) { printf("%d ", a[i]); } for(int i=0; i<t; ++i) { printf("%d ", K[i]); } } } int main() { int C; scanf("%d", &C); printf("%d
", C); if(C<20) one::work(); else if(C<40) two::work(); else if(C<60) three::work(); else if(C<80) four::work(); else five::work(); return 0; }

좋은 웹페이지 즐겨찾기