靶形数独,Noip模拟考试八

枚举前几项就很显然了,Carter兰数。(然鹅对于多个事先不会Carter兰数的蒟蒻来说大致难炸了
先生总喜欢考一些豪门没学过的东西qwq)

说明

【数据范围】

十分之四的数量,数独中国和欧洲 0 数的个数不少于 30。

十分八的数额,数独中国和欧洲 0 数的个数不少于 26。

百分百的数据,数独中国和欧洲 0 数的个数不少于 24。

NOIP 2009 提高组 第四题

 

 

 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 10
using namespace std;
int s,sum,ans=-1,deep;
int x[N*10],y[N*10],l[N][N],h[N][N],g[N][N],map[N][N];
int p[9][9]={{6,6,6,6,6,6,6,6,6},
             {6,7,7,7,7,7,7,7,6},
             {6,7,8,8,8,8,8,7,6},
             {6,7,8,9,9,9,8,7,6},
             {6,7,8,9,10,9,8,7,6},
             {6,7,8,9,9,9,8,7,6},
             {6,7,8,8,8,8,8,7,6},
             {6,7,7,7,7,7,7,7,6},
             {6,6,6,6,6,6,6,6,6}
            };
int gg[9][9]={{0,0,0,1,1,1,2,2,2},
              {0,0,0,1,1,1,2,2,2},
              {0,0,0,1,1,1,2,2,2},
              {3,3,3,4,4,4,5,5,5},
              {3,3,3,4,4,4,5,5,5},
              {3,3,3,4,4,4,5,5,5},
              {6,6,6,7,7,7,8,8,8},
              {6,6,6,7,7,7,8,8,8},
              {6,6,6,7,7,7,8,8,8}        
             };
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void dfs(int ss,int sum)
{
    if(!ss)
    {
        ans=max(ans,sum);
        return ;
    }
    if(sum+ss*9*10<ans) return ;
    if(++deep>1e7) return ;
    int nx=x[ss],ny=y[ss];
    for(int i=1;i<=9;i++)
    {
        if(!h[nx][i]&&!l[ny][i]&&!g[gg[nx][ny]][i])
        {
            h[nx][i]=1;
            l[ny][i]=1;
            g[gg[nx][ny]][i]=1;
            dfs(ss-1,sum+i*p[nx][ny]);
            h[nx][i]=0;
            l[ny][i]=0;
            g[gg[nx][ny]][i]=0;
        }
    }
}
int main()
{
    for(int i=0;i<9;i++)
     for(int j=0;j<9;j++)
     {
          map[i][j]=read();
          if(!map[i][j])
          {
              s++;
              x[s]=i;
              y[s]=j;
        }
        else 
        {
            h[i][map[i][j]]=1;
            l[j][map[i][j]]=1;
            g[gg[i][j]][map[i][j]]=1;
            sum+=map[i][j]*p[i][j];
        }
     }
    dfs(s,sum);
    printf("%d",ans);
    return 0;
 } 

 

然后极快幂求逆元,停止。

输入输出样例

输入样例#1:

sudoku1
7 0 0 9 0 0 0 0 1 
1 0 0 0 0 5 9 0 0 
0 0 0 2 0 0 0 8 0 
0 0 5 0 2 0 0 0 3 
0 0 0 0 0 0 6 4 8 
4 1 3 0 0 0 0 0 0 
0 0 7 0 0 2 0 9 0 
2 0 1 0 6 0 8 0 4 
0 8 0 5 0 4 0 1 2

sudoku2
0 0 0 7 0 2 4 5 3 
9 0 0 0 0 8 0 0 0 
7 4 0 0 0 5 0 1 0 
1 9 5 0 8 0 0 0 0 
0 7 0 0 0 0 0 2 5 
0 3 0 5 7 9 1 0 8 
0 0 0 6 0 1 0 0 0 
0 6 0 9 0 0 0 0 1 
0 0 0 0 0 0 0 0 6

出口样例#1:

sudoku1
2829

sudoku2
2852

靶形数独
(sudoku.cpp/.c/.pas)
【标题叙述】
小城和小华府是热爱数学的好学生,方今,他们不约而同地迷上了数独游戏,好胜的她
们想用数独来一比高低。但普通的数独对她们来说都过度简短了,于是他们向 Z
大学生请教,
Z 博士拿出了他近日注脚的“靶形数独”,作为那两个孩子比试的题目。
靶形数独的方格同普通数独一样,在 9 格宽×9 格高的大九宫格中有 9 个 3
格宽×3 格
高的小九宫格(用粗中黄线隔断的)。在那些大九宫格中,有一对数字是已知的,依据那个
数字,利用逻辑推演,在任何的空格上填入 1 到 9
的数字。每一种数字在各种小九宫格内不

双重出现,各类数字在每行、每列也不能够重复出现。但靶形数独有一些和一般性数独分裂,即
每二个方格都有一个分值,而且如同二个对象一样,离为主越近则分值越高。
上海教室具体的分值分布是:最中间一格(紫铜色区域)为 13分,深灰蓝区域外面包车型客车一圈(红
色区域)各个格子为 9 分,再外面一圈(黄绿区域)各样格子为 八分,驼色区域外面一圈
(棕
色区域)各类格子为 7 分,最外侧一圈(墨紫区域)每一种格子为 5分,如上海体育场面所示。竞赛

必要是:每个人必须完结多个加以的数独(各种给定数独可能有两样的填法),而且要分得
更高的总分数。而这一个总分数即各样方格上的分值和成功这么些数独时填在相应格上的数字
的乘积的总数。如图,在以下的那些曾经填完数字的靶形数独游戏中,总分数为
2829。游
戏规定,将以总分数的轻重决出输赢。
是因为求胜心切,小城找到了善于编制程序的您,让您帮他求出,对于给定的靶形数独,能
够获得的万丈分数。

P1074 靶形数独

注意对模版实行预处理,记录每三个1对此第②个1的绝对地点。

输入输出格式

输入格式:

 

一起 9 行。每行 9 个整数(每种数都在 0―9
的范围内),表示2个不曾填满的数独方

格,未填的空格用“0”表示。每四个数字之间用二个空格隔绝。

 

出口格式:

 

出口文件 sudoku.out 共 1 行。

出口能够收获的靶形数独的最高分数。倘若这些数独无解,则输出整数-1。

 

#include<cstdio>
#include<algorithm>
#include<cstring>
#define searchnext(x,y) y==8?dfs(x+1,0):dfs(x,y+1)
using namespace std;
bool visx[10][10],visy[10][10],vis[5][5][10];
int a,b[10][10];
int getscore[10][10][10];
int ans=-1,score;
int cul(int x,int y,int s)
{
    if(x==4&&y==4)return 10*s;
    if(x>=3&&y>=3&&x<=5&&y<=5)return 9*s;
    if(x>=2&&y>=2&&x<=6&&y<=6)return 8*s;
    if(x>=1&&y>=1&&x<=7&&y<=7)return 7*s;
    return 6*s;
}
bool fillin(int x,int y,int k)
{
    if(visx[x][k]||visy[y][k]||vis[x/3][y/3][k])return false;
    visx[x][k]=visy[y][k]=vis[x/3][y/3][k]=1;
    b[x][y]=k;
    score+=getscore[x][y][k];
    return true;
}
void del(int x,int y,int k)
{
    visx[x][k]=visy[y][k]=vis[x/3][y/3][k]=0;
}
void dfs(int x,int y)
{
    if(x==9&&y==0)
    {
        ans=max(ans,score);
        return ;
    }
    if(b[x][y])searchnext(x,y);
    else 
    {
        for(int i = 1 ; i <= 9 ; ++i)
        {
            int t=score;
            if(fillin(x,y,i))
            {
                searchnext(x,y);
                del(x,y,i);
                score=t;
            }
        }
        b[x][y]=0;
    }
}

int main()
{
   // freopen("sudoku.in","r",stdin);
   // freopen("sudoku.out","w",stdout);
    for(int i = 0 ; i < 9 ; ++i)
        for(int j = 0 ; j < 9 ; ++j)
            for(int k = 1 ; k <= 9 ; ++k)
                getscore[i][j][k]=cul(i,j,k);
    for(int i = 8;i >= 0 ; --i)
        for(int j = 8 ; j >= 0 ; --j)
            {
                scanf("%d",&a);
                if(a)fillin(i,j,a);
            }
    dfs(0,0);
    printf("%d",ans);
    return 0;
}

难点叙述

小城和小华府是钟爱数学的好学生,近年来,他们不约而同地迷上了数独游戏,好胜的他

们想用数独来一比高低。但一般的数独对他们的话都过度简单了,于是他们向 Z
大学生请教,

Z 大学生拿出了他多年来表明的“靶形数独”,作为这多个子女比试的难题。

靶形数独的方格同普通数独一样,在 9 格宽×9 格高的大九宫格中有 9 个 3
格宽×3 格

高的小九宫格(用粗深湖蓝线隔离的)。在那些大九宫格中,有部分数字是已知的,依据那个数字,利用逻辑推导,在别的的空格上填入
1 到 9 的数字。各类数字在各种小九宫格内不可能

重新出现,各种数字在每行、每列也不可能再一次现身。但靶形数独有几许和日常数独差别,即

每3个方格都有四个分值,而且仿佛三个目的一样,离为主越近则分值越高。(如图)

图片 1

上海教室具体的分值分布是:最里面一格(金色区域)为 十分,珍珠白区域外面包车型地铁一圈(红

色区域)每种格子为 9 分,再外面一圈(深红区域)各个格子为 七分,深蓝区域外面一圈(棕

色区域)每一种格子为 7 分,最外侧一圈(深橙区域)每一个格子为 5分,如上海体育场地所示。竞赛的

须求是:各种人须求形成一个加以的数独(每一种给定数独或然有差异的填法),而且要力争

更高的总分数。而那几个总分数即每种方格上的分值和到位那么些数独时填在相应格上的数字

的乘积的总额

总分数即每一个方格上的分值和形成这几个数独时填在对应格上的数字

的乘积的总数。如图,在偏下的这些曾经填完数字的靶形数独游戏中,总分数为
2829。游戏规定,将以总分数的音量决出高下。

图片 2

是因为求胜心切,小城找到了善于编制程序的你,让您帮他求出,对于给定的靶形数独,能

够获得的最高分数。

  1. 看球赛
    (football.cpp/.c/.pas)
    2200 年 Rio迪(奥迪(Audi))奥引导的十星巴西对阵莱昂纳多辅导的阿根廷的FIFA World Cup决赛马
    上起始了!前来在巨型篮球场观望比赛的观者数不甚数,但是出于出其不意的体系
    原因,我们不能够网上定票,只可以到购票窗口,排成长龙买票.
    按订票处规定,每个限购一张入场券,且每一张门票 50 比索。
    在排成长龙的球
    迷中有 n 个人手持 50 比索,别的有 n 个人手持 100
    港币。借使购票处开始的时
    候没有零钱,试问那 2n 个球迷有个别许种排队情势使得购票处不会晤世找不出钱
    的狼狈局面,导致推延观球的观众看球时间。
    【输入与输出表达】
    输入两行,第①行一个正整数 T,表示数据个数。
    第②行有 T 个正整数,n1,n2,….nT.
    输出 T 行,每一行为被 10^9+7 模过的结果。
  1. 鼎纹
    (grain.cpp/.c/.pas)
    【问题讲述】
    据书上说鼎纹的 种创立 式是 铜模印出来的,那是我国东魏劳动 智慧
    的果实。铜模印过的地 ,会留给深入的印记,经过时间的熔融,洗
    练成历史的遗存。
    通晓的明朝劳摄人心魄民怀有多个 a 行 b 列的字样,各样地点照旧是 0(代表
    以此点是平的),要么是 1(代表那个点是优良的)。他们想造 个 n 行 m 列
    的鼎 ,在那之中每一个岗位也都以 0 或 1,表示经过若干
    次印后,各样岗位的结果。
    有部分须求。铜模是无法旋转和扭转的;在印的进度当中,铜模的凸起不
    能冒出在鼎面包车型大巴外面(平的局地是能够出现在外头的),鼎面上的同三个地点
    不能够被四个优良印下(在任意几遍印时,鼎面上不设有一个点,使得这次都
    有铜模上为 1 的点覆盖它)。
    请您认清那一个鼎面能否被印出来。
    【输入格式】
    输入文件件名为 grain.in。
    焦点多测。
    先是行,二个平头 T ,表示测试
    点数量。接下来 T 个测试点,每
    个测试点中:
    第二行李包裹括 4 个整数 n,m,a,b。
    接下去 n 行 ,每行 m 个字符,描述鼎面 。“0”表示
    平,“1”表示凸起。接下来 a 行,每行 b 个字符,
    叙述铜模。“0”表示平,“1”表示凸起。
    【输出格式】
    输出 件名为 grain.out。
    共有 T 行 ,对于每种测试点,输出 “YES”(能)或“NO”(不能够)。

坚实版八数据,代码借鉴hzwer大佬。

 图片 3

暴力搜索即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 1010
#define maxm 10000005
int a[maxn][maxn],ecnt,cnt,m,n,d,b;
int x1[maxm],y1[maxm],x2[maxm],y2[maxm];
char str[maxn];
bool check(int x,int y)
{
    a[x][y]=0;
    int tx,ty;
    for(int i = 1 ; i < ecnt ; ++i)
    {
        tx=x+x2[i];ty=y+y2[i];
        if(tx<1||ty<1||tx>n||ty>m||!a[tx][ty])return false;
        a[tx][ty]=0;
    }
    return true;
}
void solve()
{
    cnt=ecnt=0;
    memset(a,0,sizeof(a));
    scanf("%d%d%d%d",&n,&m,&d,&b);
    for(int i = 1 ; i <= n ; ++i)
    {
        scanf("%s",str+1);
        for(int j = 1 ; j <= m ; ++j)
            if(str[j]=='1'){x1[++cnt]=i;y1[cnt]=j;a[i][j]=1;}
    }
    for(int i = 1 ; i <= d;++i)
    {
        scanf("%s",str+1);
        for(int j = 1 ; j <= b ; ++j)
            if(str[j]=='1'){x2[ecnt]=i;y2[ecnt++]=j;}
    }
    for(int i = 1 ; i <ecnt ; ++i)
        {
            x2[i]-=x2[0];
            y2[i]-=y2[0];
        }
    for(int i = 1 ; i <= cnt ; ++i)
        if(a[x1[i]][y1[i]])
            if(!check(x1[i],y1[i]))
            {
                printf("NO\n");
                return ;
            }
    printf("YES\n");
}
int main()
{
  //  freopen("grain.in", "r", stdin);
 //   freopen("grain.out", "w", stdout);
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define mod 1000000007
using namespace std;
int n;
ll ksm(ll x,int b)
{
    ll fu(1);
    while(b)
    {
        if(b&1)fu=fu*x%mod;
        b>>=1;
        x=x*x%mod;    
    }
    return fu;
}
void solve()
{
    ll ret(1);
    ll rret(1);
    scanf("%d",&n);
    int m=n<<1;
    for(int i = 1 ; i <= n ; ++i)
        {
            rret=rret*(m-i+1)%mod;
            ret=ret*i%mod;
        }
    ret=ret*(n+1)%mod;
    ll ans=rret*ksm(ret,mod-2)%mod;
    printf("%I64d\n",ans);
}
int main()
{
    //freopen("football.in","r",stdin);
    //freopen("football.out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

 

 

(大模拟)

思路就是在鼎上找到三个为’1’的点,然后用模板对应,循环此操作。