2021.7.19模擬賽C組總結

這次的題做的不怎么樣，剛學的exgcd居然忘了…

在這里插入圖片描述

題解

T1

題目描述：

? 丁丁最近沉迷于一個數字游戲之中，這個游戲看似簡單，但丁丁在研究了許多天之后卻發覺原來在簡單的規則下想要贏得這個游戲并不那么容易，游戲是這樣的，在你面前有一圈整數（一共n個），你要按順序將其分為m個部分，各部分內的數字相加，相加所得的m個結果對10取模后再相乘，最終得到一個數k，游戲的要求是使你所得的k最大或者最小，

? 例如，對于下面這圈數字（n=4，m=2）：

在這里插入圖片描述

? 當要求最小值時，((2-1) mod 10)×((4+3) mod 10)=1×7=7，要求最大值時，為((2+4+3) mod 10)×(-1 mod 10)=9×9=81，特別值得注意的是，無論是負數還是正數，對10取模的結果均為非負值，

? 丁丁請你撰寫程式幫他贏得這個游戲，

比賽思路：

? 想過佇列，貪心之類的解法，但是都不行，沒想到其他的方法，喜提0分

正解：

? 用區間動態規劃，由于這個序列會形成一個環，所以可以將用于存盤原序列的a陣列進行預處理，使得a[i]=a[i+n],即將陣列a[1...n]復制到a[n+1...n×2]中，便于使用陣列模擬環，再預處理一個前綴和陣列sum[1...n×2]，設f1[i][j][k]表示在原序列a中區間[i,j]被分為k個部分時，所能求得的最小值，f2[i][j][k]則表示最大值，動態轉移方程如下：
f 1 i , j , k = m i n ( f 1 i , j , k , f 1 i , p , k ? 1 × ( s u m j ? s u m p ) m o d 10 ) f1{i,j,k}=min(f1_{i,j,k},f1_{i,p,k-1}×(sum_j-sum_p) mod 10) f1i,j,k=min(f1i,j,k?,f1i,p,k?1?×(sumj??sump?)mod10)

f 2 i , j , k = m a x ( f 2 i , j , k , f 2 i , p , k ? 1 × ( s u m j ? s u m p ) m o d 10 ) f2{i,j,k}=max(f2_{i,j,k},f2_{i,p,k-1}×(sum_j-sum_p) mod 10) f2i,j,k=max(f2i,j,k?,f2i,p,k?1?×(sumj??sump?)mod10)

最后用變數存盤最大值與最小值即可

Code：

#include<bits/stdc++.h>
#define in scanf
#define out printf
#define rint register int
using namespace std;
const int inf=2e9;
int n,m,a[101],sum[101];
int f1[101][101][101],f2[101][101][101];
int md(int x)
	{return((x%10+10)%10);}
int main() {
	in("%d%d",&n,&m);
	for(rint i=1;i<=n;i++) {
		in("%d",&a[i]);
		a[i+n]=a[i];//處理環
		sum[i]=sum[i-1]+a[i];//前綴和陣列
	}
	for(rint i=n+1;i<=n*2;i++) sum[i]=sum[i-1]+a[i];
	int maxn=-inf;
	int minn=inf;
	for(rint i=1;i<=n;i++) {
		for(rint j=1;j<=2*n;j++)
			for(rint k=1;k<=2*n;k++) {
				f1[i][j][k]=inf;
				f2[i][j][k]=-inf;
			}
			for(rint j=i;j<=i+n-1;j++) {
				f1[i][j][1]=md(sum[j]-sum[i-1]);
				f2[i][j][1]=md(sum[j]-sum[i-1]);
			}
			for(rint j=i;j<=i+n-1;j++)
				for(rint k=2;k<=min(m,j-i+1);k++)
					for(rint p=k+i-2;p<=j-1;p++) {
						f1[i][j][k]=min(f1[i][j][k],f1[i][p][k-1]*md(sum[j]-sum[p]));
						f2[i][j][k]=max(f2[i][j][k],f2[i][p][k-1]*md(sum[j]-sum[p]));//DP
					}
		minn=min(minn,f1[i][i+n-1][m]);
		maxn=max(maxn,f2[i][i+n-1][m]);
	}
	out("%d\n%d",minn,maxn);
	return 0;
}

顯然，f1和f2陣列的第一維是不影響結果的，可以直接去掉，優化空間復雜度

#include<bits/stdc++.h>
#define in scanf
#define out printf
#define rint register int
using namespace std;
const int inf=2e9;
int n,m,a[101],sum[101];
int f1[101][101],f2[101][101];
int md(int x)
	{return((x%10+10)%10);}
int main() {
	in("%d%d",&n,&m);
	for(rint i=1;i<=n;i++) {
		in("%d",&a[i]);
		a[i+n]=a[i];
		sum[i]=sum[i-1]+a[i];
	}
	for(rint i=n+1;i<=n*2;i++) sum[i]=sum[i-1]+a[i];
	int maxn=-inf;
	int minn=inf;
	for(rint i=1;i<=n;i++) {
		for(rint j=1;j<=2*n;j++)
			for(rint k=1;k<=2*n;k++) {
				f1[j][k]=inf;
				f2[j][k]=-inf;
			}
			for(rint j=i;j<=i+n-1;j++) {
				f1[j][1]=md(sum[j]-sum[i-1]);
				f2[j][1]=md(sum[j]-sum[i-1]);
			}
			for(rint j=i;j<=i+n-1;j++)
				for(rint k=2;k<=min(m,j-i+1);k++)
					for(rint p=k+i-2;p<=j-1;p++) {
						f1[j][k]=min(f1[j][k],f1[p][k-1]*md(sum[j]-sum[p]));
						f2[j][k]=max(f2[j][k],f2[p][k-1]*md(sum[j]-sum[p]));
					}
		minn=min(minn,f1[i+n-1][m]);
		maxn=max(maxn,f2[i+n-1][m]);
	}
	out("%d\n%d",minn,maxn);
	return 0;
}

T2

題目描述：

? Beny 想要用蛋糕填飽肚子，Beny 一共想吃體積為 c 的蛋糕，他發現有兩種蛋糕可以吃，一種體積為 a，一種體積為 b，但兩種蛋糕各有特色，Beny 想知道他一共有多少種不同吃法，使得他恰好可以填飽肚子，

比賽思路：

? 知道用exgcd，但是基礎不牢，不會實作，打了暴力得30分

正解：

? 用exgcd求方程ax+by=c整數解中y最大的一組解，解的組數=最大的y/a+1

Code:

注：要用long long 資料型別

#include<bits/stdc++.h>
#define in scanf
#define out printf
#define lon long long
using namespace std;
lon gcd(lon a,lon b)
	{return a%b==0?b:gcd(b,a%b);}
void exgcd(lon a,lon b,lon&x,lon&y) {
	if(b==0) {
		x=1; y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
	return;
}
signed main() {
	lon t,a,b,x,y,c,k;
	in("%lld",&t);
	for(register int i=1;i<=t;i++) {
		in("%lld%lld%lld",&a,&b,&c);
		k=gcd(a,b);
		if(c%k!=0) {
			out("0\n");
			continue;
		}
		exgcd(a,b,x,y);
		a/=k; b/=k; c/=k;
		x=((x%b+b)%b*(c%b)%b+b)%b;
		y=(c-a*x)/b;
		if(y<0) {
			out("0\n");
			continue;
		}
		else out("%lld\n",y/a+1);
	}
	return 0;
}

T3

題目描述：

? 惡魔獵手尤迫安野心勃勃.他背叛了暗夜精靈，率深藏在海底的那加企圖叛變：守望者在與尤迪安的交鋒中遭遇了圍殺.被困在一個荒蕪的大島上，為了殺死守望者，尤迪安開始對這個荒島施咒，這座島很快就會沉下去，到那時，島上的所有人都會遇難：守望者的跑步速度，為17m/s，以這樣的速度是無法逃離荒島的，慶幸的是守望者擁有閃爍法術，可在1s內移動60m，不過每次使用閃爍法術都會消耗魔法值10點，守望者的魔法值恢復的速度為4點/s，只有處在原地休息狀態時才能恢復，

? 現在已知守望者的魔法初值M，他所在的初始位置與島的出口之間的距離S，島沉沒的時間T，你的任務是寫一個程式幫助守望者計算如何在最短的時間內逃離荒島，若不能逃出，則輸出守望者在剩下的時間內能走的最遠距離，注意:守望者跑步、閃爍或休息活動均以秒(s)為單位，且每次活動的持續時間為整數秒，距離的單位為米(m)，

比賽思路：

? 想到了貪心正解，結果不知為什么WA了50分，賽后按原先的想法重新打了一遍就AC了，可能是細節沒弄好

正解：

? 貪心，先用已有的魔法值用完法術，再列舉時間 i(from 1 to T)，判斷在第 i 秒時跑和停哪個距離遠，盡量停下來存魔法值，魔法值一超過10就用法術，當已走距離不小于原距離時，直接輸出 i 并 break，如果時間到了還沒走到，則輸出目前走了的路程

Code:

#include<bits/stdc++.h>
#define in scanf
#define out printf
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;  
int m,s,t,s1,s2;
int main() {
	fre(escape);
	in("%d%d%d",&m,&s,&t);
	for(int i=1;i<=t;i++) {
		s1+=17;//跑
		if(m>=10) {
			m-=10;
			s2+=60;//用法術  
		}
		else m+=4;  
		if(s2>s1) s1=s2;
		if(s1>=s) {
			out("Yes\n%d",i);
			return 0;
		}
	}
	out("No\n%d",s1);
	return 0;
}

T4

題目描述：

? 給定A,B,C三根足夠長的細柱，在A柱上放有2n個中間有空的圓盤，共有n個不同的尺寸，每個尺寸都有兩個相同的圓盤，注意這兩個圓盤是不加區分的(下圖為n=3的情形），現要將這些國盤移到C柱上，在移動程序中可放在B柱上暫存，要求:

在這里插入圖片描述

(1)每次只能移動一個圓盤；

(2) A、B、C三根細柱上的圓盤都要保持上小下大的順序；

任務:設An為2n個圓盤完成上述任務所需的最少移動次數，對于輸入的n，輸出An

比賽思路：

? 這題就是個高精度的模板題，只要推出公式就可做

正解：

? 首先我們要了解漢諾塔問題：有3個柱子A,B,C,一開始A柱上有N個盤子，按照從小到大的順序插在A柱上，要求把這N個盤子從A柱上移動到C柱上，移動程序中必須保證不能把大盤子放置在小盤子之上，請你根據盤子數，計算出最少的移動次數，

? 我們發現：

? 當N=1時，次數=1

? 當N=2時，可以先用N=1的方法將A柱上的1個盤子移到B柱，再將最下面的1個移到C柱，最后把B柱上的1個盤子移到C柱，整個程序用了兩次N=1的操作和移動最下面的盤子的1次操作，因此最少移動次數=1×2+1=3

? 當N=3時，可以先用N=2的方法將A柱上的2個盤子移到B柱，再將最下面的1個移到C柱，最后把B柱上的2個盤子移到C柱，整個程序用了兩次N=2的操作和移動最下面的盤子的1次操作，因此最少移動次數=3×2+1=7

? 當N=4時，可以先用N=3的方法將A柱上的3個盤子移到B柱，再將最下面的1個移到C柱，最后把B柱上的3個盤子移到C柱，整個程序用了兩次N=3的操作和移動最下面的盤子的1次操作，因此最少移動次數=7×2+1=15

? …

? 當N=k時，可以先用N=k-1的方法將A柱上的k-1個盤子移到B柱，再將最下面的1個移到C柱，最后把B柱上的k-1個盤子移到C柱，整個程序用了兩次N=k-1的操作和移動最下面的盤子的1次操作，因此最少移動次數=(k-1)×2+1

歸納，得當N=k時，
最少移動次數 = 2 k ? 1 最少移動次數=2^k-1 最少移動次數=2k?1
理解了漢諾塔問題，這道題便迎刃而解了，由于有2N個盤子且按同樣方式排列，所以
最少移動次數 = 2 × ( 2 k ? 1 ) = 2 k + 1 ? 2 最少移動次數=2×(2^k-1)=2^{k+1}-2 最少移動次數=2×(2k?1)=2k+1?2
直接用高精度求出答案即可

Code：

#include<bits/stdc++.h>
#define in scanf
#define out printf
#define rint register int
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
const int D=1<<15;
int t,len,answer[100001]={0,1};
void ps(int f) {
	int jw=0,k=1;
	while(jw!=0 or k==1 or k<len) {//高精度
		answer[k]=answer[k]*f+jw; 
		jw=answer[k]/10;
		answer[k]%=10;
		k++;
	}
	len=max(len,k);
	return;
}
int main() {
	fre(hanoi);
	in("%d",&t);
	for(rint i=1;i<=(t+1)/15;i++) ps(D);//優化時間復雜度
	for(rint i=1;i<=(t+1)%15;i++) ps(2);
	for(rint i=len-1;i>=2;i--)
		out("%d",answer[i]);
	out("%d",answer[1]-2);
	return 0;
}

End

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/289395.html

標籤：其他

上一篇：就這樣寫個像樣的郵件系統，趕緊收藏

下一篇：unity 常見的置灰處理