當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

浙江理工大学2019年1月赛

發(fā)布時間：2024/10/5 编程问答 28 豆豆

生活随笔收集整理的這篇文章主要介紹了浙江理工大学2019年1月赛小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

Problem A?LZDFDSMLL吃批薩（easy）

http://murphyc.fun/contest/5/problem/A

Description

LZDFDSMLL最近收到了一個批薩，這個批薩可以表示成n行m列的矩形，已知這個批薩上有k塊被吃掉了。

LZDFDSMLL一定要吃一塊完整的正方形的批薩，請問他有多少種不同的批薩可以吃。

不同批薩的定義：

兩個正方形批薩只要左上角的點不一樣，或者正方形批薩的邊長不一樣就算不同。

Input

第一行兩個正數(shù)n，m, k, 分別表示矩陣的行數(shù)、矩陣的列數(shù)、被吃掉的塊數(shù)。

接下來有k行，每行有兩個數(shù)x， y，表示在x行y列的那塊批薩被吃掉了。

(1 <= n, m <= 500, k <= min(500, n*m))

Output

一個整數(shù)表示LZDFDSMLL有多少種不同的正方形批薩可以吃。

Sample Input 1?

3 3 0

Sample Output 1

Sample Input 2?

3 3 1 2 2

Sample Output 2

題意：

題解：

動態(tài)規(guī)劃，狀轉(zhuǎn)方程：

if (a[i][j]==1) f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;

說明：

f[i][j]表示以節(jié)點i,j為右下角，可構(gòu)成的最大正方形的邊長。

只有a[i][j]==1時，節(jié)點i,j才能作為正方形的右下角；

對于一個已經(jīng)確定的f[i][j]=x，它表明包括節(jié)點i，j在內(nèi)向上x個節(jié)點，向左x個節(jié)點掃過的正方形中所有a值都為1；

對于一個待確定的f[i][j]，我們已知f[i-1][j]，f[i][j-1]，f[i-1][j-1]的值，如下：

f數(shù)組:

? ? ? ?

? ? 2 1

? ? 3??

? ? ? ?

則說明原a數(shù)組：

1 1 1 0

1 1 1 1

1 1 1?1

? ? ? ?

由此得出狀態(tài)轉(zhuǎn)移方程：

if (a[i][j]==1) f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;

for example:

a[i][j]:

0 0 0 1

1 1 1 1

0 1 1 1

1 1 1 1

f[i][j]:

0 0 0 1

1 1 1 1

0 1 2 2

1 1 2 3

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=5000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,q,x,y; ll ans,cnt,flag,temp; int a[N][N]; int l[N][N]; int c[N][N]; int dp[N][N]; char str; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifscanf("%d%d%d",&n,&m,&k);//scanf("%d",&t);//while(t--){}for(int i=1;i<=k;i++){scanf("%d%d",&x,&y);a[x][y]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(!a[i][j])dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;//cout<<dp[i][j]<<endl;ans+=dp[i][j];}}cout<<ans<<endl;//cout << "Hello world!" << endl;return 0; }

Problem B?duxing201606的日期薄

http://murphyc.fun/contest/5/problem/B

Description

眾所周知，duxing哥愛出去旅游。眾所周知，duxing哥會各地臟話。

duxing哥有一個日期薄，上面有1,2,3...x代表了日期。每次duxing哥出去旅游或者回家的時候，都會在日期本上打一個標(biāo)記，而且duxing哥有個習(xí)慣，就是不會在同一天出去和回來，這意味著一個日期上不會出現(xiàn)兩個標(biāo)記。duxing哥是這樣計算日期的，假如在第a天有一個標(biāo)記，在第b天有一個標(biāo)記（b>a)，那么a到b有b-a天。通過這樣打標(biāo)記，duxing哥很容易就能知道自己在這x天中有幾天在外面玩耍，有幾天在家學(xué)習(xí)。

例如duxing哥的日期薄可以是這個樣子的：

其中第1,4,7,9,10,11打上了標(biāo)記，那么第1天早上，duxing哥出去，第4天回家，那么這段時間內(nèi)duxing哥都在玩耍，所以這段時間他玩了3天，同理之后的標(biāo)記也可以這樣理解，這樣duxing哥一共玩了3+2+1=6天

可惜duxing哥有時會忘掉打標(biāo)記。在第x天，duxing哥恰好旅游完回到了家，他打上了標(biāo)記，在查看日期薄的時候，他看到在日期薄上有n個標(biāo)記，可是duxing哥明明記得自己打了k+n個標(biāo)記。duxing哥便打算把這k個標(biāo)記補(bǔ)上，而duxing哥認(rèn)為自己是一個非常貪玩的人，所以他希望在補(bǔ)上標(biāo)記以后，自己玩耍的時間盡可能的多。

duxing哥很聰明，因為今天是第x天，所以他不可能把補(bǔ)上的標(biāo)記打到x之后的日期，同時他也會遵循自己的習(xí)慣，不會在打過標(biāo)記的日期位置再打一次。

但是duxing哥還有好多題目要驗，所以他決定懸賞高達(dá)136948的v金來幫他解決這個問題。

Input

第一行輸入兩個數(shù)字，n，k，分別代表duxing哥已經(jīng)有的標(biāo)記數(shù)，duxing哥需要補(bǔ)的標(biāo)記數(shù)，保證(n+k)%2=0 (1<=n<=1000,0<=k<=1000)

第二行輸入n個數(shù)字,a1,a2,a3...an，其中a1<a2<a3...<an，并且a1=1,an=x，x為最后一天的標(biāo)記，保證 n+k<=x (2<=x<=3000)

Output

輸出一個數(shù)字，代表duxing哥在補(bǔ)上標(biāo)記后玩了多少天

Sample Input 1?

6 0 1 4 7 9 10 11

Sample Output 1

Sample Input 2?

5 1 1 3 6 8 13

Sample Output 2

Sample Input 3?

5 3 1 3 6 8 13

Sample Output 3

Hint

樣例1就是上面的圖片樣

例2中：標(biāo)記在2或者4最優(yōu)樣

例3中：標(biāo)記在2,7,9最優(yōu)

題意：

題解：

C++版本一

Problem C?duxing201606的原味雞樹

http://murphyc.fun/contest/5/problem/C

Description

眾所周知，duxing哥非常喜歡原味雞。眾所周知，原味雞是長在原味雞樹上的。

duxing哥因為是水產(chǎn)巨子，所以就購買了一棵原味雞樹。原味雞樹是一顆有n個節(jié)點的完全二叉樹（節(jié)點編號從1開始），每個節(jié)點會長出一個原味雞。每當(dāng)duxing哥想吃原味雞的時候，他就會在原味雞樹上挑選一個節(jié)點，然后將這個節(jié)點的子樹上的原味雞都吃掉（包括選中的那個節(jié)點）。

因為duxing哥害怕摘下的雞不夠他吃，所以現(xiàn)在duxing哥想知道當(dāng)他選擇某個節(jié)點的時候能吃到多少原味雞。

Input

第一行n,m，其中n代表這顆樹有多少個節(jié)點，m代表duxing哥的詢問次數(shù)(1<=n<=1e9,1<=m<=100000)

接下來m行，每行一個數(shù)字x，代表duxing哥詢問的節(jié)點編號

Output

對于duxing哥的每次詢問，輸出一個數(shù)字代表他能吃到多少原味雞

Sample Input 1?

10 4 5 3 6 2

Sample Output 1

2 3 1 6

Hint

如圖5號節(jié)點的子樹包括5,6，所以答案為2

3號節(jié)點的子樹包括3,6,7,所以答案為3

6號節(jié)點的子樹包括6,所以答案為1

2號節(jié)點的子樹包括2,4,5,8,9,10,所以答案為6

題意：

題解：

C++版本一

Problem D?LZDFDSMLL吃批薩

http://murphyc.fun/contest/5/problem/D

Description

LZDFDSMLL最近收到了一個批薩，這個批薩可以表示成n行m列的矩形，已知這個批薩上有k塊被吃掉了。

LZDFDSMLL一定要吃一塊完整的正方形的批薩，請問他有多少種不同的批薩可以吃。

不同批薩的定義：

兩個正方形批薩只要左上角的點不一樣，或者正方形批薩的邊長不一樣就算不同。

Input

第一行兩個正數(shù)n，m, k, 分別表示矩陣的行數(shù)、矩陣的列數(shù)、被吃掉的塊數(shù)。

接下來有k行，每行有兩個數(shù)x， y，表示在x行y列的那塊批薩被吃掉了。

(1 <= n, m <= 5000, k <= min(5000, n*m))

Output

一個整數(shù)表示LZDFDSMLL有多少種不同的正方形批薩可以吃。

Sample Input 1?

3 3 0

Sample Output 1

Sample Input 2?

3 3 1 2 2

Sample Output 2

C++版本一

題解：DP

Problem E?

題意：

題解：

C++版本一

Problem F?

題意：

題解：

C++版本一

Problem G?plw的骰子

http://murphyc.fun/contest/5/problem/G?

Description

duxing2016有一個神奇的骰子，投出1-6的概率為（p1,p2...p6）

現(xiàn)在他投n次骰子，問投出點數(shù)和大于等于m的概率是多少

Input

第一行，兩個正整數(shù)n,m

第二行，六個浮點數(shù) p1,p2,p3,p4,p5,p6

n <= 1000, n <= m <= 6 * n

0<=pi<=1, (p1+p2+p3+p4+p5+p6) = 1

Output

投出點數(shù)和大于m的概率p,你的答案與std的誤差要<=1e-5

Sample Input 1?

2 7 0 0 0.5 0 0 0.5

Sample Output 1

0.75

題解：

設(shè)dp[i][j]為扔完i次骰子后得到的點數(shù)和為j的概率，那么很顯然轉(zhuǎn)移方程
?

dp[i + 1][j + k] = dp[i][j] * p[k], 1<=k<=6

初始條件也十分的顯然，扔0次骰子得到點數(shù)和為0概率是1
第一維可以讓k從大到小枚舉而省去，因為每次肯定是從小的點數(shù)轉(zhuǎn)移到大的點數(shù)

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=1000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,q; double ans,cnt,flag,temp; double a[N]; double dp[N][N*6]; char str; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifscanf("%d",&n);scanf("%d",&t);for(int i=1;i<=6;i++)scanf("%lf",&a[i]),dp[1][i]=a[i];dp[1][0]=1;for(int i=2;i<=n;i++){for(int j=1;j<=6;j++){for(int k=6*(i-1);k>=i-1;k--){dp[i][k+j]=dp[i][k+j]+dp[i-1][k]*a[j];}}}ans=0;for(int j=6*n;j>=t;j--){ans+=dp[n][j];// cout<<dp[n][j]<<endl;}//while(t--){}printf("%.6f\n",ans);//cout << "Hello world!" << endl;return 0; }

Problem H?duxing201606的圖靈獎

題意：

題解：

C++版本一

Problem I?duxing201606玩游戲

http://murphyc.fun/contest/5/problem/I

Description

duxing201606喜歡看一款叫sc2的游戲,他發(fā)現(xiàn)在zvt時,經(jīng)常會有拉狗引雷的操作,但是他自己操作不來,所有他想問問你:假設(shè)每顆雷的爆炸范圍可能不一樣,但是都是一個圓,只要狗走到圓內(nèi)雷就會爆炸,最少需要拉幾條狗引雷才能使雷全部爆炸?注意:因為兩圓可能相交,所以有時候一條狗能引好幾顆雷,雷和雷之間不會相互引爆.數(shù)據(jù)采用如下代碼生成(rand()會產(chǎn)生一個0到2147483647的隨機(jī)數(shù)):

第i個雷坐標(biāo)為(xi,yi),爆炸范圍是ri,n為地雷數(shù).

Input

多組測試,一個數(shù)n(n<=10).接下來n行,每行三個數(shù)x,y,z,表示坐標(biāo)(x,y)和半徑r

Output

最少的小狗數(shù)

Sample Input 1?

2 692314992 977213841 56 2140129659 884284570 108

Sample Output 1

題解：暴力解決一切問題

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,q; int ans,cnt,flag,temp; struct node{ll x,y,r; }e[N]; char str; double dist(ll x,ll y,ll x2,ll y2){return sqrt((x-x2)*(x-x2)+(y-y2)*(y-y2)); } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifwhile(~scanf("%d",&n)){ans=0;for(int i=1;i<=n;i++){scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].r);flag=1;for(int j=1;j<i;j++){if(dist(e[i].x,e[i].y,e[j].x,e[j].y)<=e[i].r+e[j].r){flag=0;break;}}ans+=flag;}cout<<ans<<endl;}//scanf("%d",&t);//while(t--){}//cout << "Hello world!" << endl;return 0; }

Problem J?

題意：

題解：

C++版本一

Problem K?你真的會貪心嗎？

題意：

題解：

C++版本一

Problem L?plw的晚餐

http://murphyc.fun/contest/5/problem/L

Description

plw吃完午飯之后，馬上又覺得肚子餓了。他決定馬上從美食區(qū)離開，趕往下一個吃飯地點"香香雞"。但是在plw離開離開美食區(qū)之前，需要按美食區(qū)的規(guī)矩畫一個特殊符號，并且如果是這是第k次離開美食區(qū)，就需要畫k倍大小的圖形.

Input

多組測試

第一行輸入T (T <= 10)

接下來T行，每一行輸入一個k(k<=1000)，代表這是第k次離開美食區(qū)。

Output

對于每次輸入要求輸出k倍大小的標(biāo)準(zhǔn)圖形。

每2組測試數(shù)據(jù)之間輸出一個空行。

注意不要輸出多余的空行或者行末空格。

Sample Input 1?

2 1 2

Sample Output 1

___ / \ \___/ _| |_ |___|______/ \ / \ \ /\______/| | __| |__ | | |________|

C++版本一

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,q; int ans,cnt,flag,temp; int a[N]; char str; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifwhile(~scanf("%d",&t))while(t--){scanf("%d",&n);for(int i=1;i<=n;i++)printf(" ");for(int i=1;i<=3*n;i++)printf("_");printf("\n");for(int i=1;i<=n;i++){for(int j=1;j<=n-i;j++){printf(" ");}printf("/");for(int j=1;j<=2*(i-1)+3*n;j++){printf(" ");}printf("\\\n");}for(int i=1;i<=n;i++){for(int j=1;j<i;j++){printf(" ");}printf("\\");for(int j=1;j<=2*(n-i)+3*n;j++){if(i==n)printf("_");elseprintf(" ");}printf("/\n");}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==n)printf("_");elseprintf(" ");}printf("|");for(int j=1;j<=3*n-2;j++){printf(" ");}printf("|");for(int j=1;j<=n;j++){if(i==n)printf("_");}printf("\n");}for(int i=1;i<=n;i++){printf("|");for(int j=1;j<=5*n-2;j++){if(i==n)printf("_");elseprintf(" ");}printf("|");printf("\n");}if(t)printf("\n");}//cout << "Hello world!" << endl;return 0; }

Problem M?

題意：

題解：

C++版本一

Problem N?

題意：

題解：

C++版本一

總結(jié)

以上是生活随笔為你收集整理的浙江理工大学2019年1月赛的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

上一篇：最小公倍数(Least_Common_M
下一篇：字典树(Trie)