精华内容
下载资源
问答
  • A -Frogs' Neighborhood Time Limit:5000MSMemory Limit:10000KB64bit IO Format:%I64d & %I64u SubmitStatus Description 未名湖附近共有N个大小湖泊L1,L2, ...,Ln(其中包括未名湖),每个湖泊Li...
    A - Frogs' Neighborhood
    Time Limit:5000MS     Memory Limit:10000KB     64bit IO Format:%I64d & %I64u
    Submit  Status

    Description

    未名湖附近共有N个大小湖泊L1L2, ..., Ln(其中包括未名湖),每个湖泊Li里住着一只青蛙Fi(1 ≤ i ≤ N)。如果湖泊LiLj之间有水路相连,则青蛙FiFj互称为邻居。现在已知每只青蛙的邻居数目x1x2, ..., xn,请你给出每两个湖泊之间的相连关系。

    Input

    第一行是测试数据的组数T(0 ≤ T ≤ 20)。每组数据包括两行,第一行是整数N(2 < N < 10),第二行是N个整数,x1x2,..., xn(0 ≤ xi ≤N)。

    Output

    对输入的每组测试数据,如果不存在可能的相连关系,输出"NO"。否则输出"YES",并用N×N的矩阵表示湖泊间的相邻关系,即如果湖泊i与湖泊j之间有水路相连,则第i行的第j个数字为1,否则为0。每两个数字之间输出一个空格。如果存在多种可能,只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。

    Sample Input

    3
    7
    4 3 1 5 4 2 1 
    6
    4 3 1 4 2 0 
    6
    2 3 1 1 2 1 
    

    Sample Output

    YES
    0 1 0 1 1 0 1 
    1 0 0 1 1 0 0 
    0 0 0 1 0 0 0 
    1 1 1 0 1 1 0 
    1 1 0 1 0 1 0 
    0 0 0 1 1 0 0 
    1 0 0 0 0 0 0 
    
    NO
    
    YES
    0 1 0 0 1 0 
    1 0 0 1 1 0 
    0 0 0 0 0 1 
    0 1 0 0 0 0 
    1 1 0 0 0 0 
    0 0 1 0 0 0 





    #include<stdio.h>
    #include<string.h>
    
    int g[20][20]; struct node { int data; int b; }a[50]; int main() { int T,n; scanf("%d",&T); while(T--) { memset(g,0,sizeof(g)); scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a[i].data); a[i].b=i; } int flag=1; while(flag!=0) { for(int i=0;i<n-1;i++) { for(int j=i+1;j<n;j++) { if(a[i].data < a[j].data) { struct node t=a[i]; a[i]=a[j]; a[j]=t; } } } if(a[0].data == 0) break; else { for(int j=1;j<=a[0].data;j++) { a[j].data--; if(a[j].data < 0) { flag = 0; break; } g[a[j].b][a[0].b] = 1; g[a[0].b][a[j].b] = 1; } } a[0].data = 0; } if(flag != 0) { printf("YES\n"); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { printf("%d",g[i][j]); if

    转载于:https://www.cnblogs.com/sunxueke/p/4251165.html

    展开全文
  • bool cmp(node a,node b) { return a.du>b.du; } int main() { int t; scanf("%d",&t); while(t--) { memset(map,0,sizeof(map)); scanf("%d",&n); for(int i=1;i;i++) { scanf("%d",&no[i].du); no[i]....

    问题描述

    未名湖附近共有N个大小湖泊L1, L2, ..., Ln(其中包括未名湖),每个湖泊Li里住着一只青蛙Fi(1 ≤ iN)。如果湖泊LiLj之间有水路相连,则青蛙FiFj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, ..., xn,请你给出每两个湖泊之间的相连关系。


    输入

    第一行是测试数据的组数T(0 ≤ T ≤ 20)。每组数据包括两行,第一行是整数N(2 < N < 10),第二行是N个整数,x1, x2,..., xn(0 ≤ xi N)。


    输出

    对输入的每组测试数据,如果不存在可能的相连关系,输出"NO"。否则输出"YES",并用N×N的矩阵表示湖泊间的相邻关系,即如果湖泊i与湖泊j之间有水路相连,则第i行的第j个数字为1,否则为0。每两个数字之间输出一个空格。如果存在多种可能,只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。


    样例输入

    3
    7
    4 3 1 5 4 2 1 
    6
    4 3 1 4 2 0 
    6
    2 3 1 1 2 1 
    

    样例输出

    YES
    0 1 0 1 1 0 1 
    1 0 0 1 1 0 0 
    0 0 0 1 0 0 0 
    1 1 1 0 1 1 0 
    1 1 0 1 0 1 0 
    0 0 0 1 1 0 0 
    1 0 0 0 0 0 0 
    
    NO
    
    YES
    0 1 0 0 1 0 
    1 0 0 1 1 0 
    0 0 0 0 0 1 
    0 1 0 0 0 0 
    1 1 0 0 0 0 
    0 0 1 0 0 0 
    


    先用havel定理判断是否能构成一个图,然后再每次变化的时候,记录两个点的坐标,并且都赋值成1即可;

    代码如下:

    #include <iostream>
    #include <stdio.h>
    #include <algorithm>
    #include <string.h>
    using namespace std;
    
    const int maxx=15;
    int n;
    int map[maxx][maxx];
    
    struct node
    {
        int du;int id;
    }no[maxx];
    
    bool cmp(node a,node b)
    {
        return a.du>b.du;
    }
    
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            memset(map,0,sizeof(map));
            scanf("%d",&n);
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&no[i].du);
                no[i].id=i;
            }
            bool mark=true;
    
            while(1)
            {
                sort(no+1,no+1+n,cmp);
                if(no[1].du==0)
                {
                    mark=true;break;
                }
    
                for(int i=1;i<=no[1].du;i++)
                {
                    no[i+1].du--;
                    if(no[i+1].du<0)
                    {
                         mark=false;break;
                    }
                    map[no[1].id][no[1+i].id]=1;
                    map[no[1+i].id][no[1].id]=1;
                }
                no[1].du=0;
                if(!mark)
                    break;
            }
                if(mark)
                {
                    printf("YES\n");
                    for(int i=1;i<=n;i++)
                    {
                        for(int j=1;j<=n;j++)
                       cout<<map[i][j]<<" ";
                        cout<<endl;
                    }
    
                }
                else
                    printf("NO\n");
                    if(t)cout<<endl;
        }
    }



    展开全文
  • poj 1659

    2016-04-09 00:47:11
    today 传送 1659 今天是一个神奇~的定理。。大概他的名字叫额、、 HAVEL可图定理。 就是给你一组度,让你判断可图否? Havel-Hakimi定理的内容可百度之。 Havel-Hakimi定理很容易理解: 三步走就可以了:。 ...

    嘿嘿嘿,我又回来写题解了。

    today 传送 1659
    今天是一个神奇~的定理。。大概他的名字叫额、、
    HAVEL可图定理。
    就是给你一组度,让你判断可图否?
    Havel-Hakimi定理的内容可百度之。
    Havel-Hakimi定理很容易理解:
    三步走就可以了:。
    排序,删边,减1
    下面举一个例子:
    已经排序:
    5433222111.
    删除第一个数5:
    433222111.
    把前面5个数减1:
    322112111
    排序:
    322211111.
    删除第一个数3:
    22211111.
    把前面3个数减1:
    11111111.
    排序:
    11111111.
    删除第一个数1:
    1111111.
    把前面1个数减1:
    0111111.
    排序:
    1111110
    删除第一个数1:
    111110
    把前面1个数减1:
    011110
    排序:
    111100
    依此类推:到最后只剩下:
    0000
    由此判断该序列是可图的。

    so 代码
    但是注意:
    1.格式的\n,WA一次
    2YES,NO ,WA一次
    3.和样例不一样没关系,毕竟specialjudge

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int t,n,ans[11][11];
    struct node{
        int id,num;
    }frog[11];
    int cmp(node a,node b){
        return a.num>b.num;
    }
    int main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d",&n);
            for(int i=1;i<=n;i++){
                scanf("%d",&frog[i].num);
                frog[i].id=i;
            }
            memset(ans,0,sizeof(ans));
            bool jy=0;
            for(int i=1;i<=n;i++)
            {
                sort(frog+i,frog+n+1,cmp);
                if(frog[i].num == 0) {
                    jy=0;break;
                } 
                if(frog[i].num>n-i){
                    jy=1;break;
                }
                for(int j=i+1;j<=i+frog[i].num;j++){
                    frog[j].num--;
                    if(frog[j].num<0){
                        jy=1;break;
                    }
                    ans[frog[i].id][frog[j].id]=ans[frog[j].id][frog[i].id]=1;
                }
                if(jy == 1) break;
                frog[i].num=0;
            }
            if(jy == 0){
                printf("YES\n");
                for(int i=1;i<=n;i++){
                    for(int j=1;j<=n;j++){
                        if(j!=1){
                            printf(" ");
                        }printf("%d",ans[i][j]);}
                        printf("\n");}
            }
            else{
                printf("NO\n");}
            printf("\n");}
    }

    睡觉,世界晚安

    展开全文
  • POJ 1659

    2016-03-14 10:55:17
    Node a) const { return val > a.val; } }Num[maxn]; int main() { int T, N; cin >> T; while (T-- ) { bool Jug = true ; cin >> N; memset(Map, 0 , sizeof (Map)); ...
    题意: 给你一个数列, 判断是否可以构成一个图, 可以则输出 构成图的一种方式
    

    构图根据 Havel-Hakimi定理来构图

    (在排序的时候注意 节点下标会变化, 故用结构体)

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn = 50;
    int Map[maxn][maxn];
    struct Node
    {
        int val, pos;
        bool operator < (const Node a) const
        {
            return val > a.val;
        }
    }Num[maxn];
    int main()
    {
        int T, N;
        cin >> T;
        while(T--)
        {
            bool Jug = true;
            cin >> N;
            memset(Map,0,sizeof(Map));
            for(int i = 0; i < N; ++i)
            {
                cin >> Num[i].val;
                Num[i].pos = i;
            }
    
            for(int i = 0; i < N && Jug; ++i)
            {
                sort(Num+i,Num+N);
                /
                /*for(int k = 0; k < N; ++k)
                {
                    if(k) cout << " ";
                    cout << Num[k].val;
                }
                cout << endl;*/
                //
                int Be = Num[i].pos;
                if(Num[i].val > N-i-1) Jug = false;
                for(int j = 1; j <= Num[i].val && Jug; ++j)
                {
                    int Ed = Num[i+j].pos;
                    Num[i+j].val--;
                    if(Num[i+j].val < 0) Jug = false;
                    else Map[Be][Ed] = Map[Ed][Be] = 1;
                }
            }
            if(!Jug) {
                puts("NO\n");
                continue;
            }
            puts("YES");
            for(int i = 0; i < N; ++i)
            {
                for(int j = 0; j < N; ++j)
                {
                    if(j) cout << " ";
                    cout << Map[i][j];
                }
                cout << endl;
            }
            cout << endl;
        }
        return 0;
    }
    展开全文
  • pku1659

    2010-05-14 11:37:00
    /* * File: pku1659.cpp * 题意:给定一些点的度数,问根据这些度数能否构成一个图。 * 根据大牛说的Havel定理进行贪心。 * Author: chenjiang * * Created on 2010年5月13日, 下午9:24 */#include #include ...
  • 1659. 合法数统计II

    2021-06-19 10:51:12
    1659.合法数统计II 给出n个数和m个询问,每个询问包含两个整数L,R,对于每个询问输出有多少数满足取值范围在[L, R] 样例 样例1: 输入:a=[1,2,3,4,5,6],q=[[1,2],[1,5]] 输出: [2,5] 说明: 对于...
  • poj1659

    千次阅读 2013-11-05 19:07:39
    bool cmp(struct Point a, struct Point b) { return a.degree > b.degree; } struct Point point[MAX_NUMBER]; int main() { int test_case; scanf("%d", &test_case); int first = 1; while (test_case--) {...
  • POJ1659

    2011-08-10 15:53:00
    (a)若G中存在边(V1,V2), (V1,V3), ...(V1,V(d1+1)),则把这些边除去得简单图G',于是d'可简单图化为G' (b)若存在点Vi,Vj使得i, (V1,Vi)不在G中,但(V1,Vj)在G中。这时,因为di>=dj,必存在k使得(Vi, Vk)在G中但(Vj...
  • poj 1659

    2011-03-24 20:21:00
    map[a[i].id][a[j].id]=map[a[j].id][a[i].id]=1; } if(!flag) break; a[i].num=0; } if(!flag) printf("NO/n"); else { printf("YES/n"); for(int i=1;i;++i) { for(int j=1;j;++j) { ...
  • poj1659Havel

    2014-07-22 14:31:52
    #include #include #include const int MAX_VER = 12; int map[MAX_VER][MAX_VER]; struct Vertex  { int index;...int cmp(const void*a,const void * b) { return ((Vertex*)b)->deg- (
  • 一本通1659礼物

    2019-03-19 19:45:00
    Exgcd(ll a,ll b,ll &X,ll & Y) { if (b== 0 ) { X = 1 ; Y = 0 ; return ; } Exgcd(b,a % b,X,Y); ll XX =X,YY= Y; X = YY; Y =XX-a/b* YY; return ; } inline ll Inv(ll Num,ll Mod) // Num*Inv =...
  • poj1659题解

    2018-11-10 16:34:07
    bool cmp ( Point a, Point b){ return a.weight > b.weight; } int main(){ int t,n,flag ; cin >>t; while(t--){ cin >> n ; flag = 1; memset(tag,0,sizeof(tag)); for(int i =0 ; i ;++i){ cin...
  • POJ-1659

    2015-02-04 21:21:00
    bool cmp(frog a, frog b) { return a.num > b.num; } bool cmp2(int a, int b) { return a > b; } void init() { flag = true; memset(ans_arr, 0, sizeof(ans_arr)); memset(base_arr, 0, sizeof(base_arr)...
  • 洛谷P1659 养猪

    2017-09-19 13:37:00
    洛谷P1659 养猪 1 #include <bits/stdc++.h> 2 #define For(i,j,k) for(int i=j;i<=k;i++) 3 using namespace std ; 4 5 const int N = 1011 ; 6 int n,day ; 7 int f[N] ; 8 ...
  • Vijos1659 河蟹王国 题目链接:Vijos1659 河蟹王国 题意:维护一个数据结构,支持区间最大值查询、区间加操作 一看就线段树水题 我们在建树时将最大值搞好查询就好了 那么区间加怎么办? 显然区间加操作会将影响...
  • 洛谷 P1659 养猪

    2017-10-17 21:54:55
    题目描述 你有一个猪圈,有N头猪,每天你最多可以杀一头猪卖钱,获益就是猪的...第二行N个数,表示猪的初始重量A[i]; 第三行N个数表示P[i]。 【数据规模】 对于20%的数据,满足1≤N≤20; 对于100%的数据,满足1
  • POJ 1659 Frogs' Neighborhood

    2013-10-02 20:48:20
    int cmp(const void *a, const void *b) { vertex *aa = (vertex *)a; vertex *bb = (vertex *)b; return aa->degree < bb->degree; } int main() { int i; bool flag; int Edge[N][N]; int T; int n, d1; ...
  • shuoj 1659 跳马问题

    2015-11-07 22:55:34
    每组测试数据仅1行,每行上有2个方格pos1、pos2,之间用一个空格隔开,每格方格表示棋盘上的一个位置,该位置由表示列的1个字母(a-h)及表示行的一个数字(1-8)构成,如“d7”表示第4列第7行。 Output
  • NDK1659(种花)

    2011-07-23 22:44:37
    program NDK1659; type edge=record x,y:longint; end; var a:array [0..16] of edge; n:longint; ans:real;{最终结果} f:array [-1..77
  • 『杭电1659』Spreadsheet

    2020-09-20 06:27:43
    Problem Description In 1979, Dan Bricklin and Bob ... It became a huge success and, at that time, was the killer application for the Apple II computers. Today, spreadsheets are found on most deskto

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,140
精华内容 1,656
关键字:

a1659