1、三角形面積

如【圖1】所示。圖中的所有小方格面積都是1。
那么，圖中的三角形面積應(yīng)該是多少呢？

請(qǐng)?zhí)顚?xiě)三角形的面積。不要填寫(xiě)任何多余內(nèi)容或說(shuō)明性文字。

這題為不規(guī)則圖形求面積的問(wèn)題，通常的解題思路是在不規(guī)則圖形中尋找規(guī)則圖形：
①整體法：整體視為一個(gè)規(guī)則圖形，減去局部的規(guī)則圖形
②局部法：將不規(guī)則圖形分解為多個(gè)規(guī)則圖形求解
所有方格面積為1，說(shuō)明每個(gè)方格的長(zhǎng)度為1。
8*8-(8*4+6*4+8*2)/2=28

答案：28

2、立方變自身

觀察下面的現(xiàn)象,某個(gè)數(shù)字的立方，按位累加仍然等于自身。
1^3 = 1
8^3 = 512 5+1+2=8
17^3 = 4913 4+9+1+3=17
...

請(qǐng)你計(jì)算包括1,8,17在內(nèi)，符合這個(gè)性質(zhì)的正整數(shù)一共有多少個(gè)？

請(qǐng)?zhí)顚?xiě)該數(shù)字，不要填寫(xiě)任何多余的內(nèi)容或說(shuō)明性的文字。

package lanqiao;

public class Two {

    public static void main(String[] args) {
        int count = 0;
        // 100*100*100 = 1000000(7位)，即使7位全部為9，也不可能，大于100的就更不可能了
        for (int i = 1; i < 100; i++) {
            int result = i * i * i;
            char[] array = String.valueOf(result).toCharArray();
            int sum = 0;
            StringBuilder builder = new StringBuilder();
            for (int j = 0; j < array.length; j++) {
                sum += Integer.valueOf(array[j] - 48);
                if (j != 0) {
                    builder.append("+");
                }
                builder.append(array[j]);
            }
            if (i == sum) {
                count++;
                System.out.println(i + "^3=" + result + "," + i + "=" + builder.toString());
            }
        }
        System.out.println("count=" + count);
    }
}

1^3=1,1=1
8^3=512,8=5+1+2
17^3=4913,17=4+9+1+3
18^3=5832,18=5+8+3+2
26^3=17576,26=1+7+5+7+6
27^3=19683,27=1+9+6+8+3

答案：6

3、三羊獻(xiàn)瑞

觀察下面的加法算式

其中，相同的漢字代表相同的數(shù)字，不同的漢字代表不同的數(shù)字。
請(qǐng)你填寫(xiě)“三羊獻(xiàn)瑞”所代表的4位數(shù)字（答案唯一），不要填寫(xiě)任何多余內(nèi)容。

package lanqiao;

public class Three {
    public static void main(String[] args) {
        //兩個(gè)4位數(shù)且各位不相同則為 1023~9876
        for(int i = 1023; i <= 9876; i++){
            for(int j = 1023; j <= 9876; j++) {
                int sum = i+j;
                //和為5位數(shù)，且各位都不相同10234~97654
                if(sum > 10234 && sum <= 97654) {
                    char[] a1 = String.valueOf(i).toCharArray();
                    char[] a2 = String.valueOf(j).toCharArray();
                    char[] a3 = String.valueOf(sum).toCharArray();
                    //三個(gè)數(shù)相同的數(shù)字位
                    if(a1[1] == a2[3] && a1[1]==a3[3] && a2[3] == a3[3] &&a1[2]==a3[2] &&a2[0]==a3[0]&&a2[1]==a3[1]){
                        //第一個(gè)數(shù)各自的每一位都不相同
                        if(a1[0]!=a1[1]&& a1[0]!=a1[2]&& a1[0]!=a1[3]&& a1[1]!=a1[2]&& a1[1]!=a1[3]&& a1[2]!=a1[3]){
                            //第二個(gè)數(shù)各自的每一位都不相同
                            if(a2[0]!=a2[1]&& a2[0]!=a2[2]&& a2[0]!=a2[3]&& a2[1]!=a2[2]&& a2[1]!=a2[3]&& a2[2]!=a2[3]){
                                //第三個(gè)數(shù)各自的每一位都不相同
                                if(a3[0]!=a3[1]&&a3[0]!=a3[2]&&a3[0]!=a3[3]&&a3[0]!=a3[4]&&a3[1]!=a3[2]&&a3[1]!=a3[3]&&a3[1]!=a3[4]&&a3[2]!=a3[3]&&a3[2]!=a3[4]&&a3[3]!=a3[4]){
                                    //第一個(gè)數(shù)的第0位和第3位其他兩個(gè)數(shù)都不包含
                                    if(!String.valueOf(j).contains(String.valueOf(i).substring(0,1)) && !String.valueOf(j).contains(String.valueOf(i).substring(3,4))){
                                        //第二個(gè)數(shù)的第2位與第三個(gè)數(shù)的第二位不相同
                                        if(a2[2] != a3[2]){
                                            System.out.println(" " + i);
                                            System.out.println(" " + j);
                                            System.out.println(sum);
                                        }                   
                                    }                   
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

打印結(jié)果

9567
1085
10652

答案：1085

4、循環(huán)節(jié)長(zhǎng)度

兩個(gè)整數(shù)做除法，有時(shí)會(huì)產(chǎn)生循環(huán)小數(shù)，其循環(huán)部分稱為：循環(huán)節(jié)。
比如，11/13=6=>0.846153846153..... 其循環(huán)節(jié)為[846153] 共有6位。
下面的方法，可以求出循環(huán)節(jié)的長(zhǎng)度。

請(qǐng)仔細(xì)閱讀代碼，并填寫(xiě)劃線部分缺少的代碼。

    public static int f(int n, int m)
    {
        n = n % m;  
        Vector v = new Vector();
        
        for(;;)
        {
            v.add(n);
            n *= 10;
            n = n % m;
            if(n==0) return 0;
            if(v.indexOf(n)>=0)  _________________________________ ;  //填空
        }
    }

注意，只能填寫(xiě)缺少的部分，不要重復(fù)抄寫(xiě)已有代碼。不要填寫(xiě)任何多余的文字。

解題思路：將每次求余的到余數(shù)存在Vector中，如果有發(fā)現(xiàn)有重復(fù)并且不是第0位（第0位有是整數(shù)位），這個(gè)題目比較簡(jiǎn)單。

答案：

v.size()-v.indexOf(n);

5、九數(shù)組分?jǐn)?shù)

1,2,3...9 這九個(gè)數(shù)字組成一個(gè)分?jǐn)?shù)，其值恰好為1/3，如何組法？

下面的程序?qū)崿F(xiàn)了該功能，請(qǐng)?zhí)顚?xiě)劃線部分缺失的代碼。

public class A
{
    public static 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) System.out.println(a + " " + b);
    }
    
    public static void f(int[] x, int k)
    {
        if(k>=x.length){
            test(x);
            return;
        }
        
        for(int i=k; i<x.length; i++){
            {int t=x[k]; x[k]=x[i]; x[i]=t;}
            f(x,k+1);
            _______________________________________       // 填空
        }
    }
    
    public static void main(String[] args)
    {
        int[] x = {1,2,3,4,5,6,7,8,9};      
        f(x,0);
    }
}

注意，只能填寫(xiě)缺少的部分，不要重復(fù)抄寫(xiě)已有代碼。不要填寫(xiě)任何多余的文字。

解題思路：這題是排列組合問(wèn)題，代碼中就是對(duì)9個(gè)數(shù)字進(jìn)行全排列。
答案：

{int t=x[k]; x[k]=x[i]; x[i]=t;}

6、加法變乘法

我們都知道：1+2+3+ ... + 49 = 1225
現(xiàn)在要求你把其中兩個(gè)不相鄰的加號(hào)變成乘號(hào)，使得結(jié)果為2015

比如：
1+2+3+...+1011+12+...+2728+29+...+49 = 2015
就是符合要求的答案。

請(qǐng)你尋找另外一個(gè)可能的答案，并把位置靠前的那個(gè)乘號(hào)左邊的數(shù)字提交（對(duì)于示例，就是提交10）。

注意：需要你提交的是一個(gè)整數(shù)，不要填寫(xiě)任何多余的內(nèi)容。

解題思路：這種題目意思很明確，可以借助計(jì)算機(jī)的強(qiáng)大計(jì)算能力進(jìn)行遍歷,需要注意題目中的不相鄰的加號(hào)。
方法一(逆向)：

package lanqiao;

public class Six {

    public static void main(String[] args) {

        int sum;
        for (int i = 1; i < 49; i++){
            for (int j = i+2; j < 49; j++) {
                sum = 1225;
                sum -= i+i+1+j+j+1;//減去四個(gè)相乘的數(shù)
                sum += i*(i+1)+j*(j+1);
                if(sum == 2015) {
                    System.out.println("i=" + i + ",j=" + j);
                }
            }
        }
        
    }

}

方法二(正向)：

package lanqiao;

public class Six {

    public static void main(String[] args) {

        int sum = 0;
        // 總共有48個(gè)加號(hào)，符號(hào)的下標(biāo)即為左邊的數(shù)字
        for (int i = 1; i < 49; i++) {
            // 乘號(hào)之間至少間距2
            for (int j = i + 2; j < 49; j++) {
                sum = 0;
                for (int k = 1; k < 50; k++) {
                    if (i == k || j == k) {
                        sum += k * (k + 1);
                        k++;//兩個(gè)數(shù)相乘，要略過(guò)for循環(huán)一次
                    } else {
                        sum += k;
                    }
                }
                if (sum == 2015) {
                    System.out.println("i=" + i + ",j=" + j);
                }
            }
        }
    }

}

打印結(jié)果

i=10,j=27
i=16,j=24

即

1+2+3+...+10*11+12+...+27*28+29+...+49 = 2015
1+2+3+...+16*17+18+...+24*25+26+...+49 = 2015

答案：

16

7、牌型種數(shù)

小明被劫持到X賭城，被迫與其他3人玩牌。
一副撲克牌（去掉大小王牌，共52張），均勻發(fā)給4個(gè)人，每個(gè)人13張。
這時(shí)，小明腦子里突然冒出一個(gè)問(wèn)題：
如果不考慮花色，只考慮點(diǎn)數(shù)，也不考慮自己得到的牌的先后順序，自己手里能拿到的初始牌型組合一共有多少種呢？

請(qǐng)?zhí)顚?xiě)該整數(shù)，不要填寫(xiě)任何多余的內(nèi)容或說(shuō)明文字。

解題思路：動(dòng)態(tài)規(guī)劃

package lanqiao;

public class Seven {

    public static void main(String[] args) {
        int[][] dp = new int[14][14];
        dp[0][0] = 1;
        for (int i = 1; i < 14; i++)
            for (int j = 0; j < 14; j++)
                for (int k = 0; k < 5; k++)
                    if (j + k <= 13)
                        dp[i][j + k] += dp[i - 1][j];
        System.out.println(dp[13][13]);
    }
}

答案：

3598180

8、飲料換購(gòu)

樂(lè)羊羊飲料廠正在舉辦一次促銷(xiāo)優(yōu)惠活動(dòng)。樂(lè)羊羊C型飲料，憑3個(gè)瓶蓋可以再換一瓶C型飲料，并且可以一直循環(huán)下去，但不允許賒賬。

請(qǐng)你計(jì)算一下，如果小明不浪費(fèi)瓶蓋，盡量地參加活動(dòng)，那么，對(duì)于他初始買(mǎi)入的n瓶飲料，最后他一共能得到多少瓶飲料。

輸入：一個(gè)整數(shù)n，表示開(kāi)始購(gòu)買(mǎi)的飲料數(shù)量（0<n<10000）
輸出：一個(gè)整數(shù)，表示實(shí)際得到的飲料數(shù)

例如：
用戶輸入：
100
程序應(yīng)該輸出：
149

用戶輸入：
101
程序應(yīng)該輸出：
151

資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 256M
CPU消耗 < 1000ms

答案：

請(qǐng)嚴(yán)格按要求輸出，不要畫(huà)蛇添足地打印類(lèi)似：“請(qǐng)您輸入...” 的多余內(nèi)容。

所有代碼放在同一個(gè)源文件中，調(diào)試通過(guò)后，拷貝提交該源碼。
注意：不要使用package語(yǔ)句。不要使用jdk1.7及以上版本的特性。
注意：主類(lèi)的名字必須是：Main，否則按無(wú)效代碼處理。

解題思路：這道題目邏輯比較清晰簡(jiǎn)單，但是需要注意這個(gè)輸入整數(shù)的范圍，比如是用int 還是long，否則會(huì)因?yàn)橛行y(cè)試用例超出了該數(shù)據(jù)類(lèi)型所能表示的范圍而發(fā)生異常，一般比賽里面都會(huì)有10個(gè)左右的測(cè)試用例，每個(gè)測(cè)試用例對(duì)應(yīng)一定的分?jǐn)?shù)，另外比賽類(lèi)的題目一定要嚴(yán)格按照指定格式輸出，否則就白做了。在比賽中一般是使用黑盒自動(dòng)化測(cè)試。

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        long sum = 0;
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        sum += n;
        while(n >= 3) {
            long n2 = n / 3;
            sum += n2;
            n = n2 + n % 3;//目前擁有的瓶蓋 = 換來(lái)的飲料+剩余的瓶蓋（不是3的倍數(shù)的時(shí)候會(huì)有）
        }
        
        System.out.println(sum);
    }

}

9、壘骰子

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

不要小看了 atm 的骰子數(shù)量哦～

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

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

「樣例輸入」
2 1
1 2

「樣例輸出」
544

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

資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 256M
CPU消耗 < 2000ms

請(qǐng)嚴(yán)格按要求輸出，不要畫(huà)蛇添足地打印類(lèi)似：“請(qǐng)您輸入...” 的多余內(nèi)容。

所有代碼放在同一個(gè)源文件中，調(diào)試通過(guò)后，拷貝提交該源碼。
注意：不要使用package語(yǔ)句。不要使用jdk1.7及以上版本的特性。
注意：主類(lèi)的名字必須是：Main，否則按無(wú)效代碼處理。

解題思路：遞推,還得用矩陣加速吧

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int MOD = (int) (1e9 + 7);

    public static void main(String[] args) {
        int[][] ar = new int[40][40];
        int[] mm = { 0, 4, 5, 6, 1, 2, 3 };
        long[][] dp = new long[2][7];
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        for (int i = 0; i < m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            ar[u][v] = 1;
            ar[v][u] = 1;
        }

        int pre = 1;
        int now = 0;
        for (int i = 1; i < 7; i++)
            dp[0][i] = 4;
        for (int i = 2; i <= n; i++) {
            pre = (pre + 1) % 2;
            now = (now + 1) % 2;
            Arrays.fill(dp[now], 0);
            for (int j = 1; j < 7; j++)
                for (int k = 1; k < 7; k++) {
                    dp[now][j] += (dp[pre][k] * 4) % MOD;
                }
            for (int j = 0; j < 7; j++) {
                for (int k = 0; k <= j; k++)
                    if (ar[j][k] == 1) {
                        dp[now][mm[j]] = (MOD + dp[now][mm[j]] - dp[pre][k] * 4) % MOD;
                        dp[now][mm[k]] = (MOD + dp[now][mm[k]] - dp[pre][j] * 4) % MOD;
                    }
            }
        }
        long ans = 0;
        for (int i = 1; i < 7; i++)
            ans = (ans + dp[now][i]) % MOD;
        System.out.println(ans);

    }
}

10、生命之樹(shù)

在X森林里，上帝創(chuàng)建了生命之樹(shù)。

他給每棵樹(shù)的每個(gè)節(jié)點(diǎn)（葉子也稱為一個(gè)節(jié)點(diǎn)）上，都標(biāo)了一個(gè)整數(shù)，代表這個(gè)點(diǎn)的和諧值。
上帝要在這棵樹(shù)內(nèi)選出一個(gè)非空節(jié)點(diǎn)集S，使得對(duì)于S中的任意兩個(gè)點(diǎn)a,b，都存在一個(gè)點(diǎn)列 {a, v1, v2, ..., vk, b} 使得這個(gè)點(diǎn)列中的每個(gè)點(diǎn)都是S里面的元素，且序列中相鄰兩個(gè)點(diǎn)間有一條邊相連。

在這個(gè)前提下，上帝要使得S中的點(diǎn)所對(duì)應(yīng)的整數(shù)的和盡量大。
這個(gè)最大的和就是上帝給生命之樹(shù)的評(píng)分。

經(jīng)過(guò)atm的努力，他已經(jīng)知道了上帝給每棵樹(shù)上每個(gè)節(jié)點(diǎn)上的整數(shù)。但是由于 atm 不擅長(zhǎng)計(jì)算，他不知道怎樣有效的求評(píng)分。他需要你為他寫(xiě)一個(gè)程序來(lái)計(jì)算一棵樹(shù)的分?jǐn)?shù)。

「輸入格式」
第一行一個(gè)整數(shù) n 表示這棵樹(shù)有 n 個(gè)節(jié)點(diǎn)。
第二行 n 個(gè)整數(shù)，依次表示每個(gè)節(jié)點(diǎn)的評(píng)分。
接下來(lái) n-1 行，每行 2 個(gè)整數(shù) u, v，表示存在一條 u 到 v 的邊。由于這是一棵樹(shù)，所以是不存在環(huán)的。

「輸出格式」
輸出一行一個(gè)數(shù)，表示上帝給這棵樹(shù)的分?jǐn)?shù)。

「樣例輸入」
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5

「樣例輸出」
8

「數(shù)據(jù)范圍」
對(duì)于 30% 的數(shù)據(jù)，n <= 10
對(duì)于 100% 的數(shù)據(jù)，0 < n <= 10^5, 每個(gè)節(jié)點(diǎn)的評(píng)分的絕對(duì)值不超過(guò) 10^6 。

資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 256M
CPU消耗 < 3000ms

請(qǐng)嚴(yán)格按要求輸出，不要畫(huà)蛇添足地打印類(lèi)似：“請(qǐng)您輸入...” 的多余內(nèi)容。

所有代碼放在同一個(gè)源文件中，調(diào)試通過(guò)后，拷貝提交該源碼。
注意：不要使用package語(yǔ)句。不要使用jdk1.7及以上版本的特性。
注意：主類(lèi)的名字必須是：Main，否則按無(wú)效代碼處理。

解題思路：LAC問(wèn)題

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[] head1 = new int[100010];
    static int[] head2 = new int[100010];
    static int[] node = new int[100010];
    static Edge[] edge1 = new Edge[300010];
    static Edge[] edge2 = new Edge[300010];
    static int[] degree = new int[100010];
    static int[] fa = new int[100010];
    static int tot1 = 0, tot2 = 0;
    static int Node;
    static long[] max = new long[100010];
    static long ans = Long.MIN_VALUE;

    static void add1(int u, int v) {
        edge1[tot1].u = u;
        edge1[tot1].v = v;
        edge1[tot1].nxt = head1[u];
        head1[u] = tot1++;
    }

    static void add2(int u, int v) {
        edge2[tot2].u = u;
        edge2[tot2].v = v;
        edge2[tot2].nxt = head2[u];
        head2[u] = tot2++;
    }

    static void dfs(int u, int par, long nn) {
        max[u] = nn;
        fa[u] = u;
        for (int i = head1[u]; i != -1; i = edge1[i].nxt) {
            int v = edge1[i].v;
            if (v == par)
                continue;
            dfs(v, u, nn + node[v]);
            fa[v] = u;
        }
        for (int i = head2[u]; i != -1; i = edge2[i].nxt) {
            int v = edge2[i].v;
            if (max[v] != Long.MAX_VALUE) {
                ans = Math.max(ans, max[v] + max[u] - max[parent(v)]);
            }
        }
    }

    static int parent(int x) {
        if (fa[x] == -1 || fa[x] == x)
            return x;
        return fa[x] = parent(fa[x]);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Node = in.nextInt();
        for (int i = 0; i < Node; i++)
            node[i] = in.nextInt();
        for (int i = 0; i <= Node + Node; i++)
            edge1[i] = new Edge();
        for (int i = 0; i <= Node * Node * 2; i++)
            edge2[i] = new Edge();
        Arrays.fill(fa, -1);
        Arrays.fill(head1, -1);
        Arrays.fill(head2, -1);
        Arrays.fill(max, Long.MAX_VALUE);
        for (int i = 1; i < Node; i++) {
            int u, v;
            u = in.nextInt() - 1;
            v = in.nextInt() - 1;
            degree[u]++;
            degree[v]++;
            add1(u, v);
            add1(v, u);
        }
        for (int i = 0; i < Node; i++)
            for (int j = 0; j < Node; j++) {
                add2(i, j);
                add2(j, i);
            }
        if (Node == 2) {
            System.out.println(node[0] + node[1]);
            return;
        }
        dfs(0, -1, node[0]);
        System.out.println(ans);
    }
}

class Edge {
    int u, v, nxt;
    int par;
}

總體來(lái)看，省賽的題目相對(duì)來(lái)說(shuō)是比較簡(jiǎn)單，如愿獲得廣西賽區(qū)一等獎(jiǎng)，5月份去北京參加決賽。