Codeforces Round #495 (Div. 2) D. Sonya and Matrix[思维构造]

D. Sonya and Matrix

题意:给定t个数,要求构造一个矩阵,以0为中心,以菱形的方法依次+1扩展

思路:

假设0的坐标为(x,y),则有

max=n-x+m-y

max已知, n,m枚举O(sqrt(t)), x=MinNumber(MinNumber*4!=cnt[MinNumber])一旦(x,y)确定,整张图确定,再在O(n*m)=O(t)的时间内check构造的图,是不是和给定的t个数据相同.复杂度O(sqrt(t)*t)

对于x的分析:以0为中心,扩展开一个无穷大的图。拿一个n*m的矩阵去套,很明显有x=最小的不满足个数的数

#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N=1e6+6;
const int MOD=1e9+7;
ll a[N],sum[N],cnt[N],temp[N];
ll mx=-1e18;
ll no;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int t;
    cin >>t ;
    for(int i=1;i<=t;i++)   cin >>a[i],mx=max(mx,a[i]);
    for(int i=1;i<=t;i++)   cnt[a[i]]++;
    for(int i=1;i<=mx;i++){
        if(cnt[i]!=4*i){
            no=i;
            break;
        }
    }

    if(t==1&&a[1]==0){
        cout << 1 <<" " << 1<<endl;
        cout << 1 <<" " << 1<<endl;
        return 0;
    }

    for(int i=1;i*i<=t;i++){
        if(t%i!=0)  continue;
        int n=i,m=t/i;
        int x=no,y=n+m-mx-x;
        for(int i=1;i<=mx;i++)  temp[i]=0;
        if(x<=n&&x>=1&&y>=1&&y<=m){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++)
                    temp[abs(i-x)+abs(j-y)]++;
            }
            int isok=1;
            for(int i=1;i<=mx;i++){
                isok&=(cnt[i]==temp[i]);
            }
            if(isok){
                cout <<n <<" "<<m<<endl;
                cout << x <<" "<<y<<endl;
                return 0;
            }
        }
        n=i,m=t/i;
        swap(n,m);
        x=no,y=n+m-mx-x;
        for(int i=1;i<=mx;i++)  temp[i]=0;
        if(x<=n&&x>=1&&y>=1&&y<=m){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++)
                    temp[abs(i-x)+abs(j-y)]++;
            }
            int isok=1;
            for(int i=1;i<=mx;i++){
                isok&=(cnt[i]==temp[i]);
            }
            if(isok){
                cout <<n <<" "<<m<<endl;
                cout << x <<" "<<y<<endl;
                return 0;
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

 

 

 

全部评论

相关推荐

机械打工仔:不管啥专业,找工作改简历的第一课先把你那排版改了,简历上不要写个人简历四个字,找你要简历的谁不知道这个是简历?而且还占那么多空间,直接把自己名字和基础信息写上面,整体字体大一些。 还有这种经典两页简历一页大空白,导出PDF的时候多了一页几乎全是白的你自己看着不难受吗随手的事为啥不能改掉呢,这是态度问题,你试想一下你是HR你打开简历看到格式都没调整过会是什么感受?你自己都不重视你的简历,HR更不会在意。 然后内容你那个做两年咖啡就别往里写了,简历在精不在多,你在往你的简历里打字的时候就要想好这东西对你要找的工作有没有帮助。自我评价写一行就行了,不如给专业技能单开一栏。核心课程均分90这个真别写了,把你上过的有用的专业课列出来也行。有很多地方废话很多的精炼一下,比如你校内项目第一个写的那些,全然没有重点。 好好修改一下,我看你内容也挺优秀的,别被一个随便做的简历耽误了,我一个同专业的打工人看了都揪心更别说一天看几百份简历的HR
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
07-09 20:50
门头沟学院 Java
码农索隆:1.教育背景和荣誉证书合二为一。 2.获奖项目理一遍,你做了什么,对你求职的岗位有什么帮助,没有就删掉。 3.技能特长和教育背景交换位置。 4.技能特长写的太差,上网上找简历参考。都不用问你别的,一个redis就能把你问住,写写你具体会redis哪些方面的知识。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务