D - 特兰西瓦尼亚
CodesForces - 9A
题目：
Yakko，Wakko和Dot，世界著名的狂欢三宝，哈哈，不知道你是否看过这个动画片。
某一天，过年了，他们决定暂定卡通表演，并去某些地方旅游一下。Yakko梦想去宾夕法尼亚州，那是他的故乡。Wakko想过塔斯马尼亚，它的海滩，阳光和大海。Dot选择去特兰西瓦尼亚，她认为这个地方最神秘莫测。
但他们非常遗憾，由于休假的时间很短，所以只能去其中一个地方。聪明的Yakko，有了一个想法：拿一个六面分别写着1-6数字的骰子，每个人轮流掷骰子，谁的点数大，就去谁想要去的地方。
Yakko掷出了y点，Wakko掷出了w点，现在轮到Dot掷了，但她并没有急着。Dot想知道她有多少机会去参观特兰西瓦尼亚。
由于，Yakko和Wakko是真正的绅士，他们决定如果Dot和他们的点数一样，就让她获胜。
Input
输入只有一行两个正整数，分别表示y和w。
Output
输出Dot获胜的可能性，用不能化简的分数表示，如果可能性是0，就输出“0/1"(不包含双引号），如果可能性是100%，就输出“1/1"(不包含双引号）。
Sample Input
4 2
Sample Output
1/2
Hint
Dot会去特兰西瓦尼亚，如果她是幸运的滚4，5或6分。
分析：
这道题应该算是一道概率题
思路：
输入两个数y和w,但是第三个人赢的几率为>=max(y,w)，然后求概率
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int y,w;
cin>>y>>w;
y=max(y,w);
if(y==1) cout<<"1/1"; else if (y==2) cout<<"5/6";
else if (y==3) cout<<"2/3"; else if (y==4) cout<<"1/2";
else if (y==5) cout<<"1/3"; else if (y==6) cout<<"1/6";
return 0;
}
后记：
感觉这道题挺简单的…所以我当时是干嘛不去看它…傻了傻了hhh
E - 最小公倍数
HDU - 1108
分析：
这题算是一道很经典的题目了，难度不大，关键在于细节，很容易超时，时间炸掉，要注意方法
AC代码：
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
return b == 0 ? a: gcd(b,a%b);
}
int main()
{
int a,b;
while(cin>>a>>b)
{
long long ans=a*b;
long long ac=ans/gcd(a,b);
cout<<ac<<endl;
}
return 0;
}
后记：
hhh从我这段代码里定义的ac就可以看出…WA的次数太多，已经不耐烦了，只想AC了hhh
F - 滑雪
UVA - 10285 / (类似）AcWing 901
题目：
先来放个原题（纯英文版的）：
Michael likes snowboarding. That’s not very surprising, since snowboarding is really great. The bad thing is that in order to gain speed, the area must slide downwards. Another disadvantage is that when you’ve reached the bottom of the hill you have to walk up again or wait for the ski-lift.
? Michael would like to know how long the longest run in an area is. That area is given by a grid of numbers, defining the heights at those points. Look at this example:
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
? One can slide down from one point to a connected other one if and only if the height decreases. One point is connected to another if it’s at left, at right, above or below it. In the sample map, a possible slide would be 24-17-16-1 (start at 24, end at 1). Of course if you would go 25-24-23-. . . -3-2-1, it would be a much longer run. In fact, it’s the longest possible.
Input
The first line contains the number of test cases N. Each test case starts with a line containing the name (it’s a single string), the number of rows R and the number of columns C. After that follow R lines with C numbers each, defining the heights. R and C won’t be bigger than 100, N not bigger than 15 and the heights are always in the range from 0 to 100.
Output
For each test case, print a line containing the name of the area, a colon, a space and the length of the longest run one can slide down in that area.
Sample Input
2
Feldberg 10 5
56 14 51 58 88
26 94 24 39 41
24 16 8 51 51
76 72 77 43 10
38 50 59 84 81
5 23 37 71 77
96 10 93 53 82
94 15 96 69 9
74 0 62 38 96
37 54 55 82 38
Spiral 5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output
Feldberg: 7
Spiral: 25
看完上面的英文版题目，我只想说…我英语好烂…555有道翻译也不太好用55555我哭的更惨了hhh
既然如此，我们不如先来看一看与这题很相似的AcWing上的一道题（AcWing 901.滑雪），题目应该算是一模一样的，但是这两题的输入和输出的格式不太一样。
AcWing 901.滑雪
题目：
给定一个 RR 行 CC 列的矩阵，表示一个矩形网格滑雪场。
矩阵中第 ii 行第 jj 列的点表示滑雪场的第 ii 行第 jj 列区域的高度。
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
在给定矩阵中，一条可行的滑行轨迹为 24?17?2?124?17?2?1。
在给定矩阵中，最长的滑行轨迹为 25?24?23?…?3?2?125?24?23?…?3?2?1，沿途共经过 2525 个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
输入格式
第一行包含两个整数 RR 和 CC。
接下来 RR 行，每行包含 CC 个整数，表示完整的二维矩阵。
输出格式
输出一个整数，表示可完成的最长滑雪长度。
数据范围
1≤R,C≤3001≤R,C≤300,
0≤矩阵中整数≤100000≤矩阵中整数≤10000
输入样例：
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
输出样例：
25
题意：
一位同学去一个矩形的滑雪场滑雪，而矩形的每一个点表示这个点的高度（滑雪从高往低处滑），这位同学可以先从这个矩形中选出一个点当作自己的起点，而每一次只能向上下左右四个格子中选择一个低于我当前格子的高度滑去，问：这位同学可以滑过的最大的长度是多少（最多可以滑过多少个格子)
分析：
?
实现方式：递归
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 310;
int w[N][N], f[N][N];
int n, m;
int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
int dfs(int x, int y)
{
if (f[x][y])
{
return f[x][y];
}
f[x][y] = 1;
for (int i = 0; i < 4; i ++ )
{
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && w[nx][ny] < w[x][y])
{
f[x][y] = max(f[x][y], dfs(nx, ny) + 1);
}
}
return f[x][y];
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
scanf("%d", &w[i][j]);
}
}
int res = 0;
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
res = max(res, dfs(i, j));
}
}
cout << res << endl;
return 0;
}
回归上题——UVA-滑雪-AC代码：
#include <iostream>
#include <cstring>
using namespace std;
const int N=105;
int mp[N][N],n,m,s[N][N];
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
int dfs(int i,int j){
if(s[i][j]) return s[i][j];
else {
for(int k=0;k<4;k++){
int nx=i+dx[k];
int ny=j+dy[k];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&mp[nx][ny]<mp[i][j])
{
dfs(nx,ny);
s[i][j]=max(s[i][j],s[nx][ny]+1);
}
}
}
return s[i][j];
}
int main(){
int T;
cin>>T;
while(T--){
int ans=0;
string name;
cin>>name;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>mp[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=max(ans,dfs(i,j));
cout<<name<<": "<<ans+1<<endl;
memset(s,0,sizeof(s));
}
return 0;
}
G - 完美立方
计蒜客 - T1193
题目：
形如 a3=b3+c3+d3a3=b3+c3+d3 的等式被称为完美立方等式。
例如 123=63+83+103123=63+83+103。
编写一个程序，对任给的正整数 N(N≤100)N(N≤100)，寻找所有的四元组 (a,b,c,d)(a,b,c,d)，使得 a3=b3+c3+d3a3=b3+c3+d3，其中 a,b,c,da,b,c,d 大于 11，小于等于 NN，且 b≤c≤db≤c≤d。
输入格式
一个正整数 N(N≤100)N(N≤100)。
输出格式
每行输出一个完美立方。输出格式为：
Cube = a, Triple = (b,c,d)
其中 a,b,c,da,b,c,d 所在位置分别用实际求出四元组值代入。
请按照 aa 的值，从小到大依次输出。当两个完美立方等式中 aa 的值相同，则 bb 值小的优先输出；仍相同则 cc 值小的优先输出；再相同则 dd 值小的先输出。
Sample Input
24
Sample Output
Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)
Cube = 18, Triple = (2,12,16)
Cube = 18, Triple = (9,12,15)
Cube = 19, Triple = (3,10,18)
Cube = 20, Triple = (7,14,17)
Cube = 24, Triple = (12,16,20)
分析：
暴力暴力暴力!!!
AC代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,a,b,c,d;
scanf("%d",&n);
for(a=2;a<=n;a++){
for(b=2;b<a;b++){
for(c=b;c<a;c++){
for(d=c;d<a;d++){
if(a*a*a==b*b*b+c*c*c+d*d*d)
printf("Cube = %d, Triple = (%d,%d,%d)\n",a,b,c,d);
}
}
}
}
return 0;
}
H - 选数
计蒜客 - T2116
题目：
已知 nn 个整数 x1,x2,?,xnx1,x2,?,xn，以及一个整数 kk（k<nk<n）。从 nn 个整数中任选 kk 个整数相加，可分别得到一系列的和。例如当 n=4n=4，k=3k=3，44 个整数分别为 33，77，1212，1919 时，可得全部的组合与它们的和为：
3+7+12=223+7+12=22
3+7+19=293+7+19=29
7+12+19=387+12+19=38
3+12+19=343+12+19=34
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3+7+19=293+7+19=29。
输入格式
输入格式为：nn，kk（1≤n≤20,k<n1≤n≤20,k<n）。
x1,x2,?,xnx1,x2,?,xn（1≤xi≤50000001≤xi≤5000000）。
输出格式
输出格式为：一个整数（满足条件的种数）。
Sample Input
4 3
3 7 12 19
Sample Output
1
分析：
DFS深搜，素数筛
AC代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000000+10;
typedef long long ll;
ll n = 0, k = 0;
ll arr[100];
bool is_prime(ll n) {
if (n < 2) return false;
for (ll i = 2; i*i <= n; i++) {
if (n%i == 0) return false;
}
return true;
}
int cnt = 0;
void dfs(ll dp, ll num, ll sum) {
if (dp > n || num > k) return;
if (num == k) {
if (is_prime(sum)) cnt++;
return;
}
dfs(dp+1, num+1, sum+arr[dp]);
dfs(dp+1, num, sum);
}
int main() {
cin >> n >> k;
for (ll i = 0; i < n; i++) cin >> arr[i];
dfs(0, 0, 0);
cout << cnt << endl;
return 0;
}
注：8.8热身赛终于完结！撒花！以后写题解可得写快一点了，按我之前的速度…永远都写不完hhh