暴力杯？dp杯！

重鑄國二榮光，省三義不容辭

• java和c/c++的題目差不太多，就A題和E題有點區別，這篇博客主要用java語言寫的，有什么看不懂的地方可以評論區留言，有什么寫錯的地方也還請指教
• 其中D、I、J的題解待更新，E題java和c/c++組的問法有點區別，手上只有c/c++的題目

試題A：空間(c/c++)

小藍準備用 256MB 的記憶體空間開一個陣列，陣列的每個元素都是 32 位二進制整數，如果不考慮程式占用的空間和維護記憶體需要的輔助空間，請問256MB 的空間可以存盤多少個 32 位二進制整數？

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	cout<<256*1024*1024/4;
    return 0;
}

ans = 67108864

試題A：ASCII碼(Java)

大致題意是已知‘A’的ascii碼，求‘L’的ascii碼

public class Main{
	public static void main(Stirng args[]){
		System.out.println((int)'L');
	}
}

ans = 76

試題B：卡片

小藍有很多數字卡片，每張卡片上都是數字 0 到 9，
小藍準備用這些卡片來拼一些數，他想從 1 開始拼出正整數，每拼一個，就保存起來，卡片就不能用來拼其它數了，
小藍想知道自己能從 1 拼到多少，
例如，當小藍有 30 張卡片，其中 0 到 9 各 3 張，則小藍可以拼出 1 到 10，但是拼 11 時卡片 1 已經只有一張了，不夠拼出 11，
現在小藍手里有 0 到 9 的卡片各 2021 張，共 20210 張，請問小藍可以從 1拼到多少？
提示：建議使用計算機編程解決問題，

import java.util.*;
public class Main{

	static Map<Integer,Integer>map;
	public static void main(String[] args) {
		map = new HashMap<Integer, Integer>();
		for(int i=0;i<=9;i++) {
			map.put(i,2021);
		}
		for(int i=1;i<100000;i++) {
			if(pd(i))System.out.println(i);
			else break;
		}
	}
	public static boolean pd(int idx) {
		int index = idx;
		Integer a;
		while(index>0) {
			a = map.get(index%10);
			if(a==0)return false;
			map.put(index%10, a-1);
			index/=10;
		}
		return true;
	}
}

Console:
1
2
3
…………
3177
3178
3179
3180
3181

ans = 3181

試題C：直線

在平面直角坐標系中，兩點可以確定一條直線，如果有多點在一條直線上， 那么這些點中任意兩點確定的直線是同一條，
給定平面上 2 × 3 個整點 {(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z}，即橫坐標是 0 到 1 (包含 0 和 1) 之間的整數、縱坐標是 0 到 2 (包含 0 和 2) 之間的整數的點，這些點一共確定了 11 條不同的直線，
給定平面上 20 × 21 個整點 {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}，即橫坐標是 0 到 19 (包含 0 和 19) 之間的整數、縱坐標是 0 到 20 (包含 0 和 20) 之間的整數的點，請問這些點一共確定了多少條不同的直線，

//暴力即可，但要進行特判，如果兩個點連成的線段不是所在的直線中該規定坐標系內最長的線段則不記數
public class Main {

	static Node[]list;
	static int ans;
	public static void main(String[] args) {
		solve(2,3);
		solve(3,3);
		solve(20,21);
	}
	public static void solve(int m,int n) {//m*n的平面坐標系
		ans=0;
		list = new Node[m*n];
		int cur=0;
		for(int x=0;x<m;x++) {
			for(int y=0;y<n;y++) {
				list[cur++] = new Node(x,y);
			}
		}
		
		int xfar,yfar,gcd;
		for(int i=0;i<m*n-1;i++) {
			for(int j=i+1;j<m*n;j++) {
				xfar = list[j].x-list[i].x;
				yfar = list[j].y-list[i].y;
				if(xfar==0 || yfar==0)continue;//垂直和水平的線先排除掉，不然求公約數有點麻煩
				gcd = gcd(xfar,yfar);
				xfar/=gcd;
				yfar/=gcd;//現在xfar和yfar代表的是兩點之間下x，y距離的最小整數比
				//如果這根線的左端點往左移動一個最小距離還是在圖形的范圍內的話就排除
				if(list[i].x-xfar>=0 && list[i].y-yfar>=0 && list[i].y-yfar<n)continue;
				//如果這根線的右端點往右移動一個最小距離還是在圖形的范圍內的話就排除
				if(list[j].x+xfar<m && list[j].y+yfar>=0 && list[j].y+yfar<n)continue;
				//這樣保證每根線只有圖形中最長的那根會被計算進去，中間短的線會被continue
				
//				System.out.println((i+1)+" "+(j+1)+" "+xfar+" "+yfar);
//				System.out.println(list[i]+" "+list[j]);
//				System.out.println("------------------");
				ans++;
			}
		}
		ans+=(m+n);
		System.out.println(ans);
	}
	public static int gcd(int a,int b){//求最大公約數
		int mid=a;
		a = Math.abs(a);
		b = Math.abs(b);
		if(b>a) {a=b;b=mid;}
	    if(b == 0)return a;
	    return gcd(b,a%b);
	}
	
}
class Node{
	int x;
	int y;
	public Node(int x,int y) {
		// TODO Auto-generated constructor stub
		this.x = x;
		this.y = y;
	}
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return x+" "+y;
	}
}

控制臺輸出的資料：
11
20
40257
以第二組資料為例：3，3，把中間注解的部分取消在控制臺可以得到：

1 6 1 2      1表示起始點，6表示終止點，1表示xfar，2表示yfar
0 0 1 2      0，0是起始點的坐標，1，2是終止點的坐標
------------------
1 8 2 1
0 0 2 1
------------------
1 9 1 1
0 0 2 2
------------------
2 4 1 -1
0 1 1 0
------------------
2 6 1 1
0 1 1 2
------------------
2 7 2 -1
0 1 2 0
------------------
2 9 2 1
0 1 2 2
------------------
3 4 1 -2
0 2 1 0
------------------
3 7 1 -1
0 2 2 0
------------------
3 8 2 -1
0 2 2 1
------------------
4 8 1 1
1 0 2 1
------------------
4 9 1 2
1 0 2 2
------------------
6 7 1 -2
1 2 2 0
------------------
6 8 1 -1
1 2 2 1
------------------
20

16、18、19、24、26、27、29、34、37、38、48、49、67、68
再加上垂直的三條和水平的三條一共20條，其中15，57等線段因為不是所屬直線上在該圖形內的最長的線段所以沒被記錄，

最后答案為：

ans = 40257

試題 D: 貨物擺放

小藍有一個超大的倉庫，可以擺放很多貨物，
現在，小藍有 n 箱貨物要擺放在倉庫，每箱貨物都是規則的正方體，小藍規定了長、寬、高三個互相垂直的方向，每箱貨物的邊都必須嚴格平行于長、寬、高，
小藍希望所有的貨物最終擺成一個大的立方體，即在長、寬、高的方向上分別堆 L、W、H 的貨物，滿足 n = L × W × H，
給定 n，請問有多少種堆放貨物的方案滿足要求，
例如，當 n = 4 時，有以下 6 種方案：1×1×4、1×2×2、1×4×1、2×1×2、2 × 2 × 1、4 × 1 × 1，
請問，當 n = 2021041820210418 （注意有 16 位數字）時，總共有多少種方案？
提示：建議使用計算機編程解決問題，

long idx = 2021041820210418l;
for(int i=1;i<100000000l;i++) {
	if(idx%i==0) {
		idx/=i;
		System.out.println(i);
	}
}

先因式分解得到他的因數有：
1
2
3
9
17
131
2857
5882353
然后dfs求
（待完善）

試題 E: 路徑

小藍學習了最短路徑之后特別高興，他定義了一個特別的圖，希望找到圖中的最短路徑，
小藍的圖由 2021 個結點組成，依次編號 1 至 2021，
對于兩個不同的結點 a, b，如果 a 和 b 的差的絕對值大于 21，則兩個結點之間沒有邊相連；如果 a 和 b 的差的絕對值小于等于 21，則兩個點之間有一條長度為 a 和 b 的最小公倍數的無向邊相連，
例如：結點 1 和結點 23 之間沒有邊相連；結點 3 和結點 24 之間有一條無向邊，長度為 24；結點 15 和結點 25 之間有一條無向邊，長度為 75，
請計算，結點 1 和結點 2021 之間的最短路徑長度是多少，
提示：建議使用計算機編程解決問題，

用輾轉相除法求最大公約數 x%y ? gcd(y, x % y) : y
然后用最大公約數求最小公倍數 x * y / gcd(x, y)
這樣就可以得到一個2021*2021的無向圖，用鄰接矩陣存盤這張圖，然后dijkstra演算法求最短路徑
關于dijkstra的內容不熟悉的可以看這篇博文
dijkstra演算法求最短路徑

import java.text.DecimalFormat;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		int map[][] = new int[2050][2050];//存大點下面初始化的時候不用考慮資料越界

		for(int i=1;i<=2021;i++) {
			for(int j=i;j<=i+21;j++) {
				//大的數放前面，或者在求最大公約數的時候加一個交換操作
				map[i][j] = lcm(j,i);
			}
		}
		boolean bj[] = new boolean[2050];//用來表示該點是否已經是最短
		int dis[] = new int[2050];//用來存盤源點到其他頂點的初始路徑
		for(int i=1;i<=2021;i++)dis[i]=map[1][i];
		
		int min,minIdx=0;
		while(!bj[2021]) {//如果2021點的最短路徑還沒求到就一直回圈
			min = Integer.MAX_VALUE;
			for(int i=2;i<=2021;i++) {
				if(!bj[i] && dis[i]!=0 && dis[i]<min) {
					min = dis[i];
					minIdx = i;
				}
			}
			bj[minIdx]=true;
			for(int i=minIdx+1;i<=minIdx+21;i++) {
				if(map[minIdx][i]!=0) {//我初始化的時候沒有把鄰接矩陣的初始值賦一個大的數，所以這里要特判一下
					if(dis[i]==0)dis[i] = dis[minIdx]+map[minIdx][i];
					else{
						if(dis[minIdx]+map[minIdx][i]<dis[i])dis[i]=dis[minIdx]+map[minIdx][i];
					}
				}
			}
		}
		System.out.println(dis[2021]);
		
	}
	public static int gcd(int x,int y) {//歐幾里得演算法
	    return x%y!=0 ? gcd(y, x % y) : y;
	}
	
	public static int lcm(int x,int y) {//最小公倍數
	    return x * y / gcd(x, y);
	}
}

試題 F: 時間顯示

小藍要和朋友合作開發一個時間顯示的網站，在服務器上，朋友已經獲取了當前的時間，用一個整數表示，值為從 1970 年 1 月 1 日 00:00:00 到當前時刻經過的毫秒數，
現在，小藍要在客戶端顯示出這個時間，小藍不用顯示出年月日，只需要顯示出時分秒即可，毫秒也不用顯示，直接舍去即可，
給定一個用整數表示的時間，請將這個時間對應的時分秒輸出，

【輸入格式】
輸入一行包含一個整數，表示時間，
【輸出格式】
輸出時分秒表示的當前時間，格式形如 HH:MM:SS，其中 HH 表示時，值
為 0 到 23，MM 表示分，值為 0 到 59，SS 表示秒，值為 0 到 59，時、分、秒
不足兩位時補前導 0，
【樣例輸入 1】
46800999
【樣例輸出 1】
13:00:00
【樣例輸入 2】
1618708103123
【樣例輸出 2】
01:08:23
【評測用例規模與約定】
對于所有評測用例，給定的時間為不超過 10^18 的正整數，

import java.text.DecimalFormat;
import java.util.Scanner;

public class Main{
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		DecimalFormat df = new DecimalFormat("00");
		long time = sc.nextLong()/1000;
		int hour,minute,cecond;
		
		time %= 3600*24;
		hour = (int)time/3600;
		time %= 3600;
		minute = (int)time/60;
		cecond = (int)time%60;
		
		System.out.println(df.format(hour)+":"+df.format(minute)+":"+df.format(cecond));
	}
	

}

試題 G: 砝碼稱重

你有一架天平和 N 個砝碼，這 N 個砝碼重量依次是 W1, W2, · · · , WN，請你計算一共可以稱出多少種不同的重量？
注意砝碼可以放在天平兩邊，

【輸入格式】
輸入的第一行包含一個整數 N，
第二行包含 N 個整數：W1, W2, W3, · · · , WN，
【輸出格式】
輸出一個整數代表答案，
【樣例輸入】
3
1 4 6
【樣例輸出】
10
【樣例說明】
能稱出的 10 種重量是：1、2、3、4、5、6、7、9、10、11，
1 = 1；
2 = 6 ? 4 (天平一邊放 6，另一邊放 4)；
3 = 4 ? 1；
4 = 4；
5 = 6 ? 1；
6 = 6；
7 = 1 + 6；
9 = 4 + 6 ? 1；
10 = 4 + 6；
11 = 1 + 4 + 6，
【評測用例規模與約定】
對于 50% 的評測用例，1 ≤ N ≤ 15，
對于所有評測用例，1 ≤ N ≤ 100，N 個砝碼總重不超過 100000，

原題題解：長沙理工大學第十二屆ACM大賽

物品可以放左邊也可以放在右邊
其實可以看成一個物品可以作為重量 a i ai ai
也可以作為 ? a i -ai ?ai
那么看成 2 n 2n 2n個物品來一次 01 01 01背包即可
但是這里稍微有點變化,物品的價值可能是負數
那么如果負數也按照我們倒序列舉會有問題,負數應該正序列舉
負數正序列舉能保證狀態沒有重復使用一個物品
當然如果你用的是二維陣列來 d p dp dp就不需要分兩次了

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int dp[N], a[N], n, m, sum;
int main() {
  while (scanf("%d", &n) != EOF) {
    memset(dp, 0, sizeof dp);
    sum = 0;
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      sum += a[i];
    }
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {//01背包，如何直接湊得我們想要的值，
      for (int j = sum; j >= a[i]; j--) {
        dp[j] |= dp[j - a[i]];
      }
    }
    for (int i = 1; i <= n; i++) {
    //01背包, 從后往前做一個01背包洗掉a[i]，通過得到一個差值，來湊得我們想要的值，
      for (int j = 1; j <= sum - a[i]; j++) {
        dp[j] |= dp[j + a[i]];
      }
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
      int x;
      scanf("%d", &x);
      puts(x <= sum && dp[x] ? "YES" : "NO");
    }
  }
  return 0;
}

來自牛客id：issue是云哥的小迷×呀

這道題統計數量的話直接遍歷dp[i]記錄有多少true就行了

試題 H: 楊輝三角形

下面的圖形是著名的楊輝三角形：
如果我們按從上到下、從左到右的順序把所有數排成一列，可以得到如下數列：
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …
給定一個正整數 N，請你輸出數列中第一次出現 N 是在第幾個數？

【輸入格式】
輸入一個整數 N，
【輸出格式】
輸出一個整數代表答案，
【樣例輸入】
6
【樣例輸出】
13
【評測用例規模與約定】
對于 20% 的評測用例，1 ≤ N ≤ 10；
對于所有評測用例，1 ≤ N ≤ 1000000000，

//暴力模擬？沒啥思路
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n;
		while(sc.hasNext()) {
			System.out.println(solve(sc.nextLong()));
		}
	}
	public static long solve(long n) {
		int san[] = new int[100000];
		san[1]=1;
		if(n==1)return 1;
		long cur=2l;
		for(int i=2;i<100000;i++) {
			for(int j=i;j>=1;j--) {
				san[j] = san[j-1]+san[j];
				if(san[j]==n)return cur;
				cur++;
			}
		}
		return -1;
	}

}

還是能騙過一些比較大的資料的，但這時候陣列再開大也無濟于事了，期待有人能給出正確的解法，

試題 I: 雙向排序

給定序列 (a1, a2, · · · , an) = (1, 2, · · · , n)，即 ai = i，
小藍將對這個序列進行 m 次操作，每次可能是將 a1, a2, · · · , aqi 降序排列，或者將 aqi, aqi+1, · · · , an 升序排列，
請求出操作完成后的序列，

【輸入格式】
輸入的第一行包含兩個整數 n, m，分別表示序列的長度和操作次數，接下來 m 行描述對序列的操作，其中第 i 行包含兩個整數 pi
, qi 表示操作型別和引數，當 pi = 0 時，表示將 a1, a2, · · · , aqi 降序排列；當 pi = 1 時，表示
將 aqi, aqi+1, · · · , an 升序排列，
【輸出格式】
輸出一行，包含 n 個整數，相鄰的整數之間使用一個空格分隔，表示操作
完成后的序列，
【樣例輸入】
3 3
0 3
1 2
0 2
【樣例輸出】
3 1 2
【樣例說明】
原數列為 (1, 2, 3)，
第 1 步后為 (3, 2, 1)，
第 2 步后為 (3, 1, 2)，
第 3 步后為 (3, 1, 2)，與第 2 步操作后相同，因為前兩個數已經是降序了，
【評測用例規模與約定】
對于 30% 的評測用例，n, m ≤ 1000；
對于 60% 的評測用例，n, m ≤ 5000；
對于所有評測用例，1 ≤ n, m ≤ 100000，0 ≤ ai ≤ 1，1 ≤ bi ≤ n，

sort騙分

試題 J: 括號序列

給定一個括號序列，要求盡可能少地添加若干括號使得括號序列變得合法，當添加完成后，會產生不同的添加結果，請問有多少種本質不同的添加結果，兩個結果是本質不同的是指存在某個位置一個結果是左括號，而另一個是右括
號，
例如，對于括號序列 ((()，只需要添加兩個括號就能讓其合法，有以下幾種不同的添加結果：()()()、()(())、(())()、(()()) 和 ((()))，

【輸入格式】
輸入一行包含一個字串 s，表示給定的括號序列，序列中只有左括號和
右括號，
【輸出格式】
輸出一個整數表示答案，答案可能很大，請輸出答案除以 1000000007 (即
10^9 + 7) 的余數，
【樣例輸入】
((()
【樣例輸出】
5
【評測用例規模與約定】
對于 40% 的評測用例，|s| ≤ 200，
對于所有評測用例，1 ≤ |s| ≤ 5000，