靶形数独,Z 大学生拿出了他多年来注脚的

靶形数独
(sudoku.cpp/.c/.pas)
【标题叙述】
小城和小华府是热爱数学的好学生,如今,他们不约而同地迷上了数独游戏,好胜的她
们想用数独来壹比高低。但普通的数独对他们的话都过度简短了,于是他们向 Z
大学生请教,
Z 硕士拿出了他不久前表明的“靶形数独”,作为那八个男女比试的标题。
靶形数独的方格同一般数独一样,在 9 格宽×玖 格高的大九宫格中有 玖 个 3格宽×三 格
高的小9宫格(用粗浅灰褐线隔开的)。在这些大玖宫格中,有部分数字是已知的,根据这么些
数字,利用逻辑推导,在其它的空格上填入 一 到 玖的数字。各种数字在种种小九宫格内不

双重出现,每一种数字在每行、每列也不能够重复出现。但靶形数独有某个和平日数独不一致,即
每1个方格都有2个分值,而且就像一个指标一样,离为主越近则分值越高。
上航海用教室具体的分值分布是:最中间一格(深深草绿区域)为 11分,茶绿区域外面的一圈(红
色区域)每一种格子为 九 分,再外面1圈(丁香紫区域)各种格子为 七分,黑褐区域外面一圈
(棕
色区域)每一种格子为 7 分,最外面一圈(黄色区域)每一种格子为 四分,如上海教室所示。比赛

须求是:各种人要求形成2个加以的数独(每一种给定数独大概有例外的填法),而且要分得
更加高的总分数。而以此总分数即每一个方格上的分值和形成这么些数独时填在对应格上的数字
的乘积的总数。如图,在以下的那些曾经填完数字的靶形数独游戏中,总分数为
282玖。游
戏规定,将以总分数的轻重决出高下。
鉴于求胜心切,小城找到了善于编制程序的你,让您帮他求出,对于给定的靶形数独,能
够获得的参天分数。

输入输出样例

输入样例#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

暴力搜索即可。

题材叙述

小城和小美利坚合众国的首都以青眼数学的好学生,近期,他们不约而同地迷上了数独游戏,好胜的她

们想用数独来一比高低。但常常的数独对他们来说都过度简短了,于是他们向 Z
硕士请教,

Z 大学生拿出了他近年来表明的“靶形数独”,作为那七个儿女比试的题材。

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

高的小九宫格(用粗浅莲红线隔绝的)。在那几个大九宫格中,有一些数字是已知的,根据那几个数字,利用逻辑推导,在其余的空格上填入
一 到 九 的数字。各个数字在各样小9宫格内不可能

双重出现,每一个数字在每行、每列也无法再现。但靶形数独有几许和日常数独不一样,即

每二个方格都有三个分值,而且如同三个指标壹样,离为主越近则分值越高。(如图)

图片 1

上航海用教室具体的分值分布是:最中间一格(深橙区域)为 十一分,柠檬黄区域外面包车型地铁1圈(红

色区域)种种格子为 玖 分,再外面1圈(银色区域)每一种格子为 捌分,紫红区域外面一圈(棕

色区域)种种格子为 柒 分,最外面1圈(土红区域)每一种格子为 四分,如上海教室所示。比赛的

须要是:各类人供给达成2个加以的数独(种种给定数独只怕有例外的填法),而且要分得

越来越高的总分数。而以此总分数即每一种方格上的分值和形成这么些数独时填在相应格上的数字

的乘积的总额

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

的乘积的总和。如图,在偏下的这一个已经填完数字的靶形数独游戏中,总分数为
282九。游戏规定,将以总分数的轻重决出输赢。

图片 2

鉴于求胜心切,小城找到了拿手工编织程的你,让你帮她求出,对于给定的靶形数独,能

够获得的最高分数。

#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;
}

P1074 靶形数独

专注对模版实行预处理,记录每一个1对此第二个一的对峙地方。

说明

【数据范围】

五分二的数量,数独中国和欧洲 0 数的个数不少于 30。

五分之四的数额,数独中国和澳洲 0 数的个数不少于 二6。

百分之百的数据,数独中国和北美洲 0 数的个数不少于 二四。

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;
 } 

 

 

输入输出格式

输入格式:

 

累计 玖 行。每行 九 个整数(各类数都在 0―九的界定内),表示四个从未填满的数独方

格,未填的空格用“0”表示。每多个数字之间用三个空格隔断。

 

输出格式:

 

出口文件 sudoku.out 共 一 行。

输出能够收获的靶形数独的万丈分数。固然这一个数独无解,则输出整数-一。

 

 图片 3

  1. 看球赛
    (football.cpp/.c/.pas)
    2200 年 Rio迪(奥迪)奥教导的10星巴西对阵Leonardo教导的阿根廷的FIFA World Cup决赛马
    上上马了!前来在大型球馆观察竞赛的客官数不甚数,不过出于出人意料的系统
    原因,我们不能够网上订票,只好到购票窗口,排成长龙领票.
    按买票处规定,每1个限购一张门票,且每一张门票 50 美元。
    在排成长龙的球
    迷中有 n 个人手持 50 美金,此外有 n 个人手持 十0
    欧元。若是买票处伊始的时
    候没有零钱,试问这 贰n 个看球的粉丝有多少种排队方式使得领票处不会产出找不出钱
    的窘迫局面,导致推延看球的粉丝看球时间。
    【输入与输出表明】
    输入两行,第一行三个正整数 T,表示数据个数。
    其次行有 T 个正整数,n一,n2,….nT.
    输出 T 行,每一行为被 10^九+7 模过的结果。

枚举前几项就很扎眼了,Carter兰数。(然鹅对于3个事先不会Carter兰数的鬼芋来说大概难炸了
先生总喜欢考1些大家没学过的事物qwq)

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

#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;
}

 
#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;
}

(大模拟)

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

  1. 鼎纹
    (grain.cpp/.c/.pas)
    【难题讲述】
    据称鼎纹的 种创制 式是 铜模印出来的,那是作者国梁国劳动 智慧
    的收获。铜模印过的地 ,会留下深深的印记,经过时间的熔融,洗
    练成历史的遗存。
    聪明的明清劳摄人心魄民有所1个 a 行 b 列的字样,每个岗位依旧是 0(代表
    以此点是平的),要么是 一(代表这几个点是凸起的)。他们想造 个 n 行 m 列
    的鼎 ,在这之中各种岗位也都以 0 或 一,表示通过若干
    次印后,每一个岗位的结果。
    有部分须求。铜模是不可能旋转和扭转的;在印的经过个中,铜模的凸起不
    能冒出在鼎面包车型大巴外界(平的有的是能够出现在外边的),鼎面上的同3个职位
    不能被八个优良印下(在四意一遍印时,鼎面上不设有贰个点,使得那四回都
    有铜模上为 壹 的点覆盖它)。
    请你判定那一个鼎面能否被印出来。
    【输入格式】
    输入文件件名叫 grain.in。
    核心多测。
    率先行,1个平头 T ,表示测试
    点数据。接下来 T 个测试点,每
    个测试点中:
    首先行李包裹罗 四 个整数 n,m,a,b。
    接下去 n 行 ,每行 m 个字符,描述鼎面 。“0”表示
    平,“一”表示凸起。接下来 a 行,每行 b 个字符,
    叙述铜模。“0”表示平,“一”表示凸起。
    【输出格式】
    输出 件名为 grain.out。
    共有 T 行 ,对于各个测试点,输出 “YES”(能)或“NO”(无法)。

然后相当的慢幂求逆元,停止。

相关文章