Problem A LZDFDSMLL吃批萨（easy）
http://murphyc.fun/contest/5/problem/A
Description
LZDFDSMLL最近收到了一个批萨，这个批萨可以表示成n行m列的矩形，已知这个批萨上有k块被吃掉了。
LZDFDSMLL一定要吃一块完整的正方形的批萨，请问他有多少种不同的批萨可以吃。
不同批萨的定义：
两个正方形批萨只要左上角的点不一样， 或者正方形批萨的边长不一样就算不同。
Input
第一行两个正数n，m, k, 分别表示矩阵的行数、矩阵的列数、被吃掉的块数。
接下来有k行，每行有两个数x， y， 表示在x行y列的那块批萨被吃掉了。
(1 <= n, m <= 500, k <= min(500, n*m))
Output
一个整数表示LZDFDSMLL有多少种不同的正方形批萨可以吃。
Sample Input 1
3 3 0 Sample Output 1
14 Sample Input 2
3 3 1
2 2 Sample Output 2
8 题意：
题解：
DP
动态规划，状转方程：
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]表示以节点i,j为右下角，可构成的最大正方形的边长。
只有a[i][j]==1时，节点i,j才能作为正方形的右下角；
对于一个已经确定的f[i][j]=x，它表明包括节点i，j在内向上x个节点，向左x个节点扫过的正方形中所有a值都为1；
对于一个待确定的f[i][j]，我们已知f[i-1][j]，f[i][j-1]，f[i-1][j-1]的值，如下：
f数组:
? ? ? ?
? ? 2 1
? ? 3 ?
? ? ? ?
则说明原a数组：
1 1 1 0
1 1 1 1
1 1 1 1
? ? ? ?
由此得出状态转移方程：
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 DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
scanf("%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哥出去旅游或者回家的时候，都会在日期本上打一个标记，而且duxing哥有个习惯，就是不会在同一天出去和回来，这意味着一个日期上不会出现两个标记。duxing哥是这样计算日期的，假如在第a天有一个标记，在第b天有一个标记（b>a)，那么a到b有b-a天。通过这样打标记，duxing哥很容易就能知道自己在这x天中有几天在外面玩耍，有几天在家学习。
例如duxing哥的日期薄可以是这个样子的：
其中第1,4,7,9,10,11打上了标记，那么第1天早上，duxing哥出去，第4天回家，那么这段时间内duxing哥都在玩耍，所以这段时间他玩了3天，同理之后的标记也可以这样理解，这样duxing哥一共玩了3+2+1=6天
可惜duxing哥有时会忘掉打标记。在第x天，duxing哥恰好旅游完回到了家，他打上了标记，在查看日期薄的时候，他看到在日期薄上有n个标记，可是duxing哥明明记得自己打了k+n个标记。duxing哥便打算把这k个标记补上，而duxing哥认为自己是一个非常贪玩的人，所以他希望在补上标记以后，自己玩耍的时间尽可能的多。
duxing哥很聪明，因为今天是第x天，所以他不可能把补上的标记打到x之后的日期，同时他也会遵循自己的习惯，不会在打过标记的日期位置再打一次。
但是duxing哥还有好多题目要验，所以他决定悬赏高达136948的v金来帮他解决这个问题。
Input
第一行输入两个数字，n，k，分别代表duxing哥已经有的标记数，duxing哥需要补的标记数，保证(n+k)%2=0 (1<=n<=1000,0<=k<=1000)
第二行输入n个数字,a1,a2,a3...an，其中a1<a2<a3...<an，并且a1=1,an=x，x为最后一天的标记，保证 n+k<=x (2<=x<=3000)
Output
输出一个数字，代表duxing哥在补上标记后玩了多少天
Sample Input 1
6 0
1 4 7 9 10 11
Sample Output 1
6
Sample Input 2
5 1
1 3 6 8 13 Sample Output 2
9 Sample Input 3
5 3
1 3 6 8 13 Sample Output 3
9 Hint
样例1就是上面的图片样
例2中：标记在2或者4最优样
例3中：标记在2,7,9最优
题意：
题解：
C++版本一
Problem C duxing201606的原味鸡树
http://murphyc.fun/contest/5/problem/C
Description
众所周知，duxing哥非常喜欢原味鸡。众所周知，原味鸡是长在原味鸡树上的。
duxing哥因为是水产巨子，所以就购买了一棵原味鸡树。原味鸡树是一颗有n个节点的完全二叉树（节点编号从1开始），每个节点会长出一个原味鸡。每当duxing哥想吃原味鸡的时候，他就会在原味鸡树上挑选一个节点，然后将这个节点的子树上的原味鸡都吃掉（包括选中的那个节点）。
因为duxing哥害怕摘下的鸡不够他吃，所以现在duxing哥想知道当他选择某个节点的时候能吃到多少原味鸡。
Input
第一行n,m，其中n代表这颗树有多少个节点，m代表duxing哥的询问次数(1<=n<=1e9,1<=m<=100000)
接下来m行，每行一个数字x，代表duxing哥询问的节点编号
Output
对于duxing哥的每次询问，输出一个数字代表他能吃到多少原味鸡
Sample Input 1
10 4
5
3
6
2 Sample Output 1
2
3
1
6 Hint
如图5号节点的子树包括5,6，所以答案为2
3号节点的子树包括3,6,7,所以答案为3
6号节点的子树包括6,所以答案为1
2号节点的子树包括2,4,5,8,9,10,所以答案为6
题意：
题解：
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=100000000+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 main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
scanf("%d",&n);
cnt=0;
for(int i=1;i<=n;i*=2){
cnt++;
}
//cout<<cnt;
//build(1,pow(2,cnt-1),1);
scanf("%d",&t);
while(t--){
scanf("%d",&k);
int a=k;
int b=k;
q=1;
while(a<pow(2,cnt-1))
a*=2,q++;
while(b<pow(2,cnt-1))
b=2*b+1;
if(n<a)
ans=pow(2,q-1)-1;
else if(b<n)
ans=pow(2,q)-1;
else
ans=pow(2,q-1)+n-a;
cout << ans << endl;
}
//cout << "Hello world!" << endl;
return 0;
}
Problem D LZDFDSMLL吃批萨
http://murphyc.fun/contest/5/problem/D
Description
LZDFDSMLL最近收到了一个批萨，这个批萨可以表示成n行m列的矩形，已知这个批萨上有k块被吃掉了。
LZDFDSMLL一定要吃一块完整的正方形的批萨，请问他有多少种不同的批萨可以吃。
不同批萨的定义：
两个正方形批萨只要左上角的点不一样， 或者正方形批萨的边长不一样就算不同。
Input
第一行两个正数n，m, k, 分别表示矩阵的行数、矩阵的列数、被吃掉的块数。
接下来有k行，每行有两个数x， y， 表示在x行y列的那块批萨被吃掉了。
(1 <= n, m <= 5000, k <= min(5000, n*m))
Output
一个整数表示LZDFDSMLL有多少种不同的正方形批萨可以吃。
Sample Input 1
3 3 0 Sample Output 1
14 Sample Input 2
3 3 1
2 2 Sample Output 2
8 C++版本一
题解：DP
/*
*@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 DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
scanf("%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 E
题意：
题解：
C++版本一
Problem F
题意：
题解：
C++版本一
Problem G plw的骰子
http://murphyc.fun/contest/5/problem/G
Description
duxing2016有一个神奇的骰子，投出1-6的概率为（p1,p2...p6）
现在他投n次骰子，问投出点数和大于等于m的概率是多少
Input
第一行，两个正整数n,m
第二行，六个浮点数 p1,p2,p3,p4,p5,p6
n <= 1000, n <= m <= 6 * n
0<=pi<=1, (p1+p2+p3+p4+p5+p6) = 1
Output
投出点数和大于m的概率p,你的答案与std的误差要<=1e-5
Sample Input 1
2 7
0 0 0.5 0 0 0.5 Sample Output 1
0.75 题解：
设dp[i][j]为扔完i次骰子后得到的点数和为j的概率，那么很显然转移方程
dp[i + 1][j + k] = dp[i][j] * p[k], 1<=k<=6
初始条件也十分的显然，扔0次骰子得到点数和为0概率是1
第一维可以让k从大到小枚举而省去，因为每次肯定是从小的点数转移到大的点数
/*
*@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 DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
scanf("%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的游戏,他发现在zvt时,经常会有拉狗引雷的操作,但是他自己操作不来,所有他想问问你:假设每颗雷的爆炸范围可能不一样,但是都是一个圆,只要狗走到圆内雷就会爆炸,最少需要拉几条狗引雷才能使雷全部爆炸?注意:因为两圆可能相交,所以有时候一条狗能引好几颗雷,雷和雷之间不会相互引爆.数据采用如下代码生成(rand()会产生一个0到2147483647的随机数):
第i个雷坐标为(xi,yi),爆炸范围是ri,n为地雷数.
Input
多组测试,一个数n(n<=10).接下来n行,每行三个数x,y,z,表示坐标(x,y)和半径r
Output
最少的小狗数
Sample Input 1
2
692314992 977213841 56
2140129659 884284570 108 Sample Output 1
2 题解：暴力解决一切问题
/*
*@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 DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
while(~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吃完午饭之后，马上又觉得肚子饿了。他决定马上从美食区离开，赶往下一个吃饭地点"香香鸡"。但是在plw离开离开美食区之前，需要按美食区的规矩画一个特殊符号，并且如果是这是第k次离开美食区，就需要画k倍大小的图形.
Input
多组测试
第一行输入T (T <= 10)
接下来T行，每一行输入一个k(k<=1000)，代表这是第k次离开美食区。
Output
对于每次输入要求输出k倍大小的标准图形。
每2组测试数据之间输出一个空行。
注意不要输出多余的空行或者行末空格。
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 DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
while(~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("_");
else
printf(" ");
}
printf("/\n");
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==n)
printf("_");
else
printf(" ");
}
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("_");
else
printf(" ");
}
printf("|");
printf("\n");
}
if(t)
printf("\n");
}
//cout << "Hello world!" << endl;
return 0;
}
Problem M
题意：
题解：
C++版本一
Problem N
题意：
题解：
C++版本一
京公网安备 11010502036488号