第六屆藍橋杯省賽C/C++B組（倒序）

10.生命之樹

在X森林裡，上帝建立了生命之樹。

他給每棵樹的每個節點（葉子也稱為一個節點）上，都标了一個整數，代表這個點的和諧值。

上帝要在這棵樹内選出一個非空節點集 S，使得對于 S 中的任意兩個點 a,b，都存在一個點列 {a,v1,v2,…,vk,b} 使得這個點列中的每個點都是 S 裡面的元素，且序列中相鄰兩個點間有一條邊相連。

在這個前提下，上帝要使得 S 中的點所對應的整數的和盡量大。

這個最大的和就是上帝給生命之樹的評分。

經過 atm 的努力，他已經知道了上帝給每棵樹上每個節點上的整數。

但是由于 atm 不擅長計算，他不知道怎樣有效的求評分。

他需要你為他寫一個程式來計算一棵樹的分數。

輸入格式
第一行一個整數 n 表示這棵樹有 n 個節點。

第二行 n 個整數，依次表示每個節點的評分。

接下來 n−1 行，每行 2 個整數 u,v，表示存在一條 u 到 v 的邊。

由于這是一棵樹，是以是不存在環的。

樹的節點編号從 1 到 n。

輸出格式
輸出一行一個數，表示上帝給這棵樹的分數。

資料範圍
1≤n≤105,
每個節點的評分的絕對值均不超過 106。

輸入樣例：
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5
輸出樣例：
8
           

思路

利用樹形dp，應該是樹形dp吧hh。

f[u]表示的是以u為根節點的子樹的最大分數。

f[u]=w[u]+f[j] j表示子結點 f[j]需要大于0，否則就不要

對樹進行一遍dfs，dfs的過程中求解即可。

代碼

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 100010,M = 2*N;
int h[N],e[M],ne[M],w[N],idx;
int n;
LL f[N];
void add(int a,int b)
{
	e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int u,int father)
{
	f[u]=w[u];
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j!=father)
		{
			dfs(j,u);
			f[u]+=max(0ll,f[j]);//加上子樹的大于0的值
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i)cin>>w[i];
	memset(h,-1,sizeof h);
	for(int i=0;i<n-1;++i)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	dfs(1,-1);
	LL ans = f[1];
	for(int i=1;i<=n;++i)
		ans = max(f[i],ans);
	cout<<ans<<endl;
	return 0;	
}
           

9.壘骰子

賭聖atm晚年迷戀上了壘骰子，就是把骰子一個壘在另一個上邊，不能歪歪扭扭，要壘成方柱體。

經過長期觀察，atm 發現了穩定骰子的奧秘：有些數字的面貼着會互相排斥！

我們先來規範一下骰子：1 的對面是 4，2 的對面是 5，3 的對面是 6。

假設有 m 組互斥現象，每組中的那兩個數字的面緊貼在一起，骰子就不能穩定的壘起來。

atm想計算一下有多少種不同的可能的壘骰子方式。

兩種壘骰子方式相同，當且僅當這兩種方式中對應高度的骰子的對應數字的朝向都相同。

由于方案數可能過多，請輸出模 109+7 的結果。

輸入格式
第一行包含兩個整數 n,m，分别表示骰子的數目和排斥的組數。

接下來 m 行，每行兩個整數 a,b，表示 a 和 b 數字不能緊貼在一起。

輸出格式
共一個數，表示答案模 109+7 的結果。

資料範圍
1≤n≤109,
1≤m≤36,
1≤a,b≤6
輸入樣例：
2 1
1 2
輸出樣例：
544
           

思路

這個題目比較難，我也講不清楚。簡單說一下知識點。

首先我們考慮dp f[i][j]為壘i個骰子，第i個骰子j點朝上的情況數。如果一層一層求，鐵定逾時。

那麼這個時候考慮矩陣乘法，尋求f[n][i]和f[n+1][j]的關系（這樣表示似乎不對，就是第n層的六面和第n+1層的六面的關系），這個時候就可以找到關系矩陣A。然後由于排斥的組數，把某些位置改為0即可。

快速矩陣乘。

代碼

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 6,mod = 1e9+7;
int f[N][N];
int a[N][N];
int get_op(int x)
{
	if(x<3)return x+3;
	return x-3;
}
void mul(int c[][N],int a[][N],int b[][N])
{
	static int t[N][N]={0};
	memset(t,0,sizeof t);
	for(int i=0;i<N;++i)
	{
		for(int j=0;j<N;++j)
		{
			for(int k=0;k<N;++k)
			{
				t[i][j]=(t[i][j]+1ll*a[i][k]*b[k][j])%mod;//不能+= 因為加上6個1e9會爆int
			}
		}
	}
	memcpy(c,t,sizeof t);	
} 
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<N;++i)
	{
		for(int j=0;j<N;++j)
		{
			a[i][j]=4;
		}
	}
	for(int i=0;i<m;++i)
	{
		int x,y;
		cin>>x>>y;
		x--;y--;
		a[x][get_op(y)]=0;
		a[y][get_op(x)]=0;
	}
	for(int i=0;i<N;++i)
	{
		f[0][i]=4;
	}
	n--;
	while(n)
	{
		if(n&1)mul(f,f,a);
		n>>=1;
		mul(a,a,a);
	}
	LL res = 0;
	for(int i=0;i<N;++i)
	{
		res = (res+f[0][i])%mod;
	}
	cout<<res<<endl;
	return 0;
} 
           

8.移動距離

X星球居民小區的樓房全是一樣的，并且按矩陣樣式排列。其樓房的編号為1,2,3...
當排滿一行時，從下一行相鄰的樓往反方向排号。
比如：當小區排号寬度為6時，開始情形如下：
1   3  4  5  6
12 11 10 9  8  7
13 14 15 .....
我們的問題是：已知了兩個樓号m和n，需要求出它們之間的最短移動距離（不能斜線方向移動）
輸入為3個整數w m n，空格分開，都在1到10000範圍内
w為排号寬度，m,n為待計算的樓号。
要求輸出一個整數，表示m n 兩樓間最短移動距離。
例如：
使用者輸入：
6 8 2
則，程式應該輸出：
4
再例如：
使用者輸入：
4 7 20
則，程式應該輸出：
5
資源約定：
峰值記憶體消耗 < 256M
CPU消耗  < 1000ms
           

思路

把編号變為0 1 2 3…

然後處理x,y坐标

代碼

#include<iostream>
#include<cmath>
using namespace std;
int w,m,n;
int main()
{
	cin>>w>>m>>n;
	m--;n--;
	int x1,y1,x2,y2;
	x1=m/w;
	x2=n/w;
	y1=m%w;
	y2=n%w;
	if(x1%2)
		y1=w-1-y1;
	if(x2%2)
		y2=w-1-y2;
	cout<<abs(x1-x2)+abs(y1-y2)<<endl;
	return 0;
}
           

7.牌型種類

小明被劫持到X賭城，被迫與其他3人玩牌。
一副撲克牌（去掉大小王牌，共52張），均勻發給4個人，每個人13張。
這時，小明腦子裡突然冒出一個問題：
如果不考慮花色，隻考慮點數，也不考慮自己得到的牌的先後順序，自己手裡能拿到的初始牌型組合一共有多少種呢？
請填寫該整數，不要填寫任何多餘的内容或說明文字。
           

思路

dfs即可 每種牌可選0-4張，然後從第一種搜到第13種就行了

代碼

#include<iostream>
#include<cmath>
using namespace std;
int ans;
void dfs(int n,int m)
{
	if(m==0)
	{
		ans++;
		return;
	}
	if(n==13||m<0)
	{
		return;
	}
	for(int i=0;i<=4;++i)
		dfs(n+1,m-i);
}
int main()
{
	dfs(0,13); 
	cout<<ans<<endl;
	return 0;
}
           

6.加法變乘法

我們都知道：1+2+3+ ... + 49 = 1225
現在要求你把其中兩個不相鄰的加号變成乘号，使得結果為2015
比如：
1+2+3+...+10*11+12+...+27*28+29+...+49 = 2015
就是符合要求的答案。
請你尋找另外一個可能的答案，并把位置靠前的那個乘号左邊的數字送出（對于示例，就是送出10）。
注意：需要你送出的是一個整數，不要填寫任何多餘的内容。
           

思路

這個思路看代碼吧

代碼

#include<iostream>
#include<cmath>
using namespace std;

int main()
{
	for(int i=2;i<=49;++i)
	{
		for(int j=i+2;j<=49;++j)
		{
			if((1225+i*(i-1)+j*(j-1))-i-(i-1)-j-(j-1)==2015)
				cout<<i-1<<" "<<j-1<<endl;
		}
	}
	return 0;
}
           

答案

16

5.九數組分數

1,2,3...9 這九個數字組成一個分數，其值恰好為1/3，如何組法？
下面的程式實作了該功能，請填寫劃線部分缺失的代碼。
           

思路

複制粘貼；讀代碼；填空，運作正确；完成。

代碼

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

答案

t=x[k]; x[k]=x[i]; x[i]=t;

4.格子中輸出

StringInGrid函數會在一個指定大小的格子中列印指定的字元串。
要求字元串在水準、垂直兩個方向上都居中。
如果字元串太長，就截斷。
如果不能恰好居中，可以稍稍偏左或者偏上一點。
下面的程式實作這個邏輯，請填寫劃線部分缺少的代碼。
           

思路

複制粘貼；讀代碼；填空，運作正确；完成。

printf("%*s",10,“abc”) 表示以10寬度來顯示abc

我們可能知道scanf裡用*修飾符，是起到過濾讀入的作用。比如一個有三列數值的資料，我隻想得到第2列數值，可以在循環裡用scanf(“%*d%d%*d”, a[i])來讀入第i行的第2個數值到a[i]。 
　　但是* 修飾符在printf中的含義完全不同。如果寫成printf(“%6d”, 123)，很多童鞋應該就不會陌生了，這是設定域寬的意思。同理，%6s也是域寬。* 修飾符正是用來更靈活的控制域寬。使用%*s，表示這裡的具體域寬值由後面的實參決定，如printf(“%*s”, 6, “abc”)就是把”abc”放到在域寬為6的空間中右對齊
　　來源:https://www.cnblogs.com/darklights/p/5296377.html
           

代碼

#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",(width-2-strlen(buf))/2,"",buf,(width-2-strlen(buf))/2,"");  //填空
 
	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,"abcd123gjdjgdddddddddddddd4");
	return 0;
}
           

答案

(width-2-strlen(buf))/2,"",buf,(width-2-strlen(buf))/2,""

3.三羊獻瑞

觀察下面的加法算式：

      祥 瑞 生 輝   // 0 1 2 3
  +   三 羊 獻 瑞   // 4 5 6 1
-------------------
   三 羊 生 瑞 氣   // 4 5 2 1 7

(如果有對齊問題，可以參看【圖1.jpg】)

其中，相同的漢字代表相同的數字，不同的漢字代表不同的數字。

請你填寫“三羊獻瑞”所代表的4位數字（答案唯一），不要填寫任何多餘内容。
           

思路

全排列+簡單的判斷

代碼

#include<iostream>
#include<vector>
using namespace std;
//8
int ans;
vector<int> vec;
bool st[10];
int get(int a[],int n)
{
	int res = 0;
	for(int i=0;i<n;++i)
	{
		res = res*10+vec[a[i]];
	}
	return res;
}
bool check()
{
	int a[] = {0,1,2,3};
	int b[] = {4,5,6,1};
	int c[] = {4,5,2,1,7};
	if(vec[0]==0||vec[4]==0)
		return false;
	int A = get(a,4);
	int B = get(b,4);
	int C = get(c,5);
	if(A+B==C)
	{
		//cout<<ans<<endl;
		cout<<A<<" "<<B<<" "<<C<<endl;
		for(int i=0;i<4;++i)
		{
			cout<<vec[b[i]]<<" ";
		}
		cout<<endl; 
		return true;
	}
	return false;//必須傳回 
}
void dfs(int n)
{
	if(n==8)
	{
		if(check())
			ans++;
		return;
	}
	for(int i=0;i<=9;++i)
	{
		if(!st[i])
		{
			st[i]=true;
			vec.push_back(i);
			dfs(n+1);
			st[i]=false;
			vec.pop_back();
		}
	}
}
int main()
{
	dfs(0);
	cout<<ans<<endl;
	return 0;
}
           

答案

1085

2.星系炸彈

思路

日期加法

代碼

#include<iostream>
using namespace std;
int days[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
bool isleap(int x)
{
	if((x%4==0&&x%100!=0)||(x%400==0))
		return true;
	return false;
}
int modify(int x)
{
	int year = x/10000;
	int month = x%10000/100;
	int day = x%100;
	day++;
	int t = days[month];
	if(month==2&&isleap(year))
		t++;
	if(day>t)
	{
		month++;
		day=1;
	}
	if(month>12)
	{
		year++;
		month=1;
	}
	return year*10000+month*100+day;
}
int main()
{
	//2000 08 04
	int year,month,day,t;
	cin>>year>>month>>day>>t;
	int ans = year*10000+month*100+day;
	while(t--)
	{
		ans = modify(ans);
	}
	printf("%04d-%02d-%02d",ans/10000,ans%10000/100,ans%100);
	return 0;
}
           

答案

2017-08-05

1.獎券數目

有些人很迷信數字，比如帶“4”的數字，認為和“死”諧音，就覺得不吉利。
雖然這些說法純屬無稽之談，但有時還要迎合大衆的需求。某抽獎活動的獎券号碼是5位數（10000-99999），要求其中不要出現帶“4”的号碼，

主辦機關請你計算一下，如果任何兩張獎券不重号，最多可發出獎券多少張。


請送出該數字（一個整數），不要寫任何多餘的内容或說明性文字。
           

思路

無

代碼

#include<iostream>
using namespace std;
bool check(int x)
{
	while(x)
	{
		int t=x%10;
		x/=10;
		if(t==4)return false;
	}
	return true;
}
int main()
{
	int ans = 0;
	for(int i=10000;i<=99999;++i)
	{
		if(check(i))
			ans++;
	}
	cout<<ans<<endl;
	return 0;
}
           

答案

52488