題目1:獎券數(shù)目

有些人很迷信數(shù)字，比如帶“4”的數(shù)字，認(rèn)為和“死”諧音，就覺得不吉利。
雖然這些說法純屬無稽之談，但有時還要迎合大眾的需求。某抽獎活動的獎券號碼是5位數(shù)（10000-99999），要求其中不要出現(xiàn)帶“4”的號碼，主辦單位請你計算一下，如果任何兩張獎券不重號，最多可發(fā)出獎券多少張。
請?zhí)峤辉摂?shù)字（一個整數(shù)），不要寫任何多余的內(nèi)容或說明性文字*
答案：52488

#include <bits/stdc++.h>
using namespace std;
void i2s(int num,string &str){
    stringstream ss;
    ss<<num;
    ss>>str;
}
int main()
{
    int ans=0;
    /*for(int i=10000;i<=99999;i++)
    {
        int t=i;
        int count=0;
        while(t>0)
        {
            int a=t%10;
            t=t/10;
            if(a!=4){
                count++;
                continue;
            }else{
                break;
            }
        }
        if(count==5)
             ans++;
    }*/
    for(int i=10000;i<=99999;i++)
    {
        string s;
        i2s(i,s);//s=to_string(i);
        if(s.find('4')==string::npos)
            ans++;
    }
    cout<<ans<<endl;//題目要求輸出最終個數(shù)的，可以將每次的結(jié)果輸出來看一看，避免小地方出錯
    return 0;
}

題目2：星系炸彈

在X星系的廣袤空間中漂浮著許多X星人造“炸彈”，用來作為宇宙中的路標(biāo)。
每個炸彈都可以設(shè)定多少天之后爆炸。
比如：阿爾法炸彈2015年1月1日放置，定時為15天，則它在2015年1月16日爆炸。
有一個貝塔炸彈，2014年11月9日放置，定時為1000天，請你計算它爆炸的準(zhǔn)確日期。
請?zhí)顚懺撊掌?，格式?yyyy-mm-dd 即4位年份2位月份2位日期。比如：2015-02-19
請嚴(yán)格按照格式書寫。不能出現(xiàn)其它文字或符號。
直接使用Excel計算：2017-08-05

題目3：三羊獻(xiàn)瑞

觀察下面的加法算式：
? 祥 瑞 生 輝
+? 三 羊 獻(xiàn) 瑞
-------------------------
三 羊 生 瑞 氣

其中，相同的漢字代表相同的數(shù)字，不同的漢字代表不同的數(shù)字。

請你填寫“三羊獻(xiàn)瑞”所代表的4位數(shù)字（答案唯一），不要填寫任何多余內(nèi)容。
答案：1085

//解法1，暴力枚舉法
//解法2,先簡單推導(dǎo)
/*
  a b c d
+ e f g b
------------
e f c b h
e=1,a=9,f=0,c=b+1.之后再進(jìn)行枚舉(從2到8)
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a=9,e=1,f=0;
    int b,c,d,g,h;
    for(b=2;b<9;b++){
        c=b+1;
        for( d=2;d<9;d++){
            if(d!=c && d!=b){
                for(g=2;g<9;g++){
                    if(g!=d && g!=c && g!=b){
                        for(h=2;h<9;h++){
                            if(h!=g && h!=d && h!=c && h!=b){
                                if((a*1000+b*100+c*10+d)+(e*1000+f*100+g*10+b)==e*10000+f*1000+c*100+b*10+h)
                                    cout<<e<<f<<g<<b<<endl;
                            }
                        }
                    }
                }
            }
        }
    }

    return 0;
}

題目4：格子中的輸出

StringInGrid函數(shù)會在一個指定大小的格子中打印指定的字符串。
要求字符串在水平、垂直兩個方向上都居中。
如果字符串太長，就截斷。
如果不能恰好居中，可以稍稍偏左或者偏上一點。

下面的程序?qū)崿F(xiàn)這個邏輯，請?zhí)顚憚澗€部分缺少的代碼。

#include <stdio.h>
#include <string.h>

void StringInGrid(int width, int height, const char* s)
{
    int i,k;
    char buf[1000];
    strcpy(buf, s);
    if(strlen(s)>width-2) buf[width-2]=0;

    printf("+");
    for(i=0;i<width-2;i++) printf("-");
    printf("+\n");

    for(k=1; k<(height-1)/2;k++){
        printf("|");
        for(i=0;i<width-2;i++) printf(" ");
        printf("|\n");
    }

    printf("|");

    //printf("%*s%s%*s",_____________________________________________);  //填空
     //可以先把要填空的部分注釋掉，然后先運行一下看看情況
     //要顯示空格-字符串-空格
     //"%*s%s%*s"中的*代表的是自己需要設(shè)定的寬度
     printf("%*s%s%*s",(width-strlen(buf)-2)/2 ,"",buf,(width-strlen(buf)-2)/2 ,"");
     /*strlen()
     頭文件：string.h
     格式：strlen （字符數(shù)組名）
     功能：計算字符串s的（unsigned int型）長度，不包括'\0'在內(nèi)
     */

     //*代表的寬度不可以固定，不只是要適應(yīng)給定的示例

    printf("|\n");

    for(k=(height-1)/2+1; k<height-1; k++){
        printf("|");
        for(i=0;i<width-2;i++) printf(" ");
        printf("|\n");
    }

    printf("+");
    for(i=0;i<width-2;i++) printf("-");
    printf("+\n");
}

int main()
{
    StringInGrid(20,6,"abcd1234");
    return 0;
}

題目5：九數(shù)組分?jǐn)?shù)

1,2,3...9 這九個數(shù)字組成一個分?jǐn)?shù)，其值恰好為1/3，如何組法？
下面的程序?qū)崿F(xiàn)了該功能，請?zhí)顚憚澗€部分缺失的代碼。
注意：只填寫缺少的內(nèi)容，不要書寫任何題面已有代碼或說明性文字。

#include <stdio.h>

void test(int x[])
{
    int a = x[0]*1000 + x[1]*100 + x[2]*10 + x[3];
    int b = x[4]*10000 + x[5]*1000 + x[6]*100 + x[7]*10 + x[8];

    if(a*3==b) printf("%d / %d\n", a, b);
}

void f(int x[], int k)
{
    int i,t;
    if(k>=9){
        test(x);
        return;
    }

    for(i=k; i<9; i++){
        {t=x[k]; x[k]=x[i]; x[i]=t;}
        f(x,k+1);
        //_____________________________________________ // 填空處
        {t=x[k]; x[k]=x[i]; x[i]=t;}//全排列問題
    }
}
int main()
{
    int x[] = {1,2,3,4,5,6,7,8,9};
    f(x,0);
    return 0;
}

題目6：加法變乘法

我們都知道：1+2+3+ ... + 49 = 1225
現(xiàn)在要求你把其中兩個不相鄰的加號變成乘號，使得結(jié)果為2015
比如：
1+2+3+...+1011+12+...+2728+29+...+49 = 2015
就是符合要求的答案。
請你尋找另外一個可能的答案，并把位置靠前的那個乘號左邊的數(shù)字提交（對于示例，就是提交10）。
注意：需要你提交的是一個整數(shù)，不要填寫任何多余的內(nèi)容
答案：16

#include <bits/stdc++.h>
using namespace std;

int main(){
    int ans=(1+49)*49/2;//等差數(shù)列的求和細(xì)節(jié)要注意，總共有多少項不要弄錯
    cout<<ans<<endl;
    for(int i=1;i<=46;i++){//i代表的是第一個*號之前的數(shù)字
            for(int j=i+2;j<=48;j++){//j代表的是第2個*號之前的數(shù)字
                    if((ans-(i+i+1)-(j+j+1)+i*(i+1)+j*(j+1))==2015){
                        cout<<i<<"*"<<i+1<<" "<<j<<"*"<<j+1<<endl;
                    }
            }
    }
}

題目7：牌型種數(shù)

小明被劫持到X賭城，被迫與其他3人玩牌。
一副撲克牌（去掉大小王牌，共52張），均勻發(fā)給4個人，每個人13張。
這時，小明腦子里突然冒出一個問題：
如果不考慮花色，只考慮點數(shù)，也不考慮自己得到的牌的先后順序，自己手里能拿到的初始牌型組合一共有多少種呢？
請?zhí)顚懺撜麛?shù)，不要填寫任何多余的內(nèi)容或說明文字。
答案：3598180

//遞歸問題，十三種，每種四張-派發(fā)完之后手中可以得到多少種十三張牌的組合--中亞
#include <bits/stdc++.h>
using namespace std;
int ans=0;
void f(int k,int sum){//k表示逐步考慮每一種牌型，對每種牌型逐步分配；sum表示目前手中已經(jīng)分配了多少張
    if(k>13 || sum>13) return;
    if(k==13 && sum==13){//牌型已經(jīng)考慮完畢，即牌已經(jīng)分發(fā)完畢，手中已經(jīng)分配有13張
        ans++;
        return ;
    }
    for(int i=0;i<5;i++)
    {
        f(k+1,sum+i);
    }
}
int main()
{
    f(0,0);
    printf("%d",ans);
    return 0;
}

題目8：移動距離

X星球居民小區(qū)的樓房全是一樣的，并且按矩陣樣式排列。其樓房的編號為1,2,3...
當(dāng)排滿一行時，從下一行相鄰的樓往反方向排號。
比如：當(dāng)小區(qū)排號寬度為6時，開始情形如下：
1 2 3 4 5 6
12 11 10 9 8 7
13 14 15 .....
我們的問題是：已知了兩個樓號m和n，需要求出它們之間的最短移動距離（不能斜線方向移動）
輸入為3個整數(shù)w m n，空格分開，都在1到10000范圍內(nèi)
w為排號寬度，m,n為待計算的樓號。
要求輸出一個整數(shù)，表示m n 兩樓間最短移動距離。
例如：
用戶輸入：
6 8 2
則，程序應(yīng)該輸出：
4
再例如：
用戶輸入：
4 7 20
則，程序應(yīng)該輸出：
5

//問題可以轉(zhuǎn)化為求出s型矩陣中的數(shù)字的行號和列號
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int w,m,n;
    scanf("%d %d %d",&w,&m,&n);
    int rm=m%w==0?m/w:m/w+1;//行列均從1開始
    int rn=n%w==0?n/w:n/w+1;
    int cm;
    if(rm%2==0){
        cm=rm*w-m+1;
    }else{
        cm=w-(rm*w-m);
    }
    int cn;
    if(rn%2==0){
        cn=rn*w-n+1;
    }else{
        cn=w-(rn*w-n);
    }
    cout<<abs(cm-cn)+abs(rm-rn)<<endl;

    return 0;
}

題目9：壘骰子

賭圣atm晚年迷戀上了壘骰子，就是把骰子一個壘在另一個上邊，不能歪歪扭扭，要壘成方柱體。
經(jīng)過長期觀察，atm 發(fā)現(xiàn)了穩(wěn)定骰子的奧秘：有些數(shù)字的面貼著會互相排斥！
我們先來規(guī)范一下骰子：1 的對面是 4，2 的對面是 5，3 的對面是 6。
假設(shè)有 m 組互斥現(xiàn)象，每組中的那兩個數(shù)字的面緊貼在一起，骰子就不能穩(wěn)定的壘起來。
atm想計算一下有多少種不同的可能的壘骰子方式。
兩種壘骰子方式相同，當(dāng)且僅當(dāng)這兩種方式中對應(yīng)高度的骰子的對應(yīng)數(shù)字的朝向都相同。
由于方案數(shù)可能過多，請輸出模 10^9 + 7 的結(jié)果。
不要小看了 atm 的骰子數(shù)量哦～

「輸入格式」
第一行兩個整數(shù) n m
n表示骰子數(shù)目
接下來 m 行，每行兩個整數(shù) a b ，表示 a 和 b 數(shù)字不能緊貼在一起。

「輸出格式」
一行一個數(shù)，表示答案模 10^9 + 7 的結(jié)果。

「樣例輸入」
2 1
1 2
「樣例輸出」
544

「數(shù)據(jù)范圍」
對于 30% 的數(shù)據(jù)：n <= 5
對于 60% 的數(shù)據(jù)：n <= 100
對于 100% 的數(shù)據(jù)：0 < n <= 10^9, m <= 36

//解法1：暴力遞歸--完成30%，其余會超時
#define MOD 1000000007
#include <bits/stdc++.h>
using namespace std;
int n,m;
int op[7];
bool conflict[7][7];
void init()
{
    op[1]=4;
    op[4]=1;
    op[2]=5;
    op[5]=2;
    op[3]=6;
    op[6]=3;
}
long long int f(int up,int cnt)
{//上一層定好了朝上的數(shù)字為up的情況下，壘好余下cnt個骰子的方案數(shù)
    long long ans=0;
    //遞歸出口
    if(cnt==0)
        return 4;
    for(int upp=1;upp<=6;upp++)
    {
        if(conflict[op[up]][upp])continue;
        ans=(ans+f(upp,cnt-1))%MOD;
    }
    return ans;//返回值不能忘記
}

int main()
{
    init();
    scanf("%d %d",&n,&m);//n表示骰子數(shù)，m表示幾對矛盾
    for(int i=0;i<m;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        conflict[x][y]=true;
        conflict[y][x]=true;
    }
    long long ans=0;
    for(int up=1;up<=6;up++)//最上邊的面的可能性
    {
        ans=(ans+4*f(up,n-1))%MOD;//這里的4*是考慮了最后的轉(zhuǎn)面，即定好了上邊的面，四個面可以轉(zhuǎn)動
    }
    cout<<ans<<endl;
    return 0;
}
//優(yōu)化：動態(tài)規(guī)劃和矩陣