题目

http://www.tyvj.cn/p/1001

http://www.tyvj.cn/p/1002

http://www.tyvj.cn/p/1003

http://www.tyvj.cn/p/1004

题解

1001

排序之后, 第n - k + 1位和第k位相减, 然后判断素数, 答案:

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, k, m;
int a[10001];
int i;
bool isprime(int x){
    if(x <= 1) return false;
    for(i = 2; i <= sqrt(x); ++i)
        if(x % i == 0) return false;
    return true;
}

int main(){
    scanf("%d%d", &n, &k);
    for(i = 1; i < n + 1; ++i) scanf("%d", a[i]);
    sort(a + 1, a + n + 1);
    m = a[n - k + 1] - a[k];
    if(isprime(m)) puts("YES");
    else puts("NO");
    printf("%d\n", m);
    return 0;
}

1002

模拟..直接上答案咯(感觉奖学金也太好拿了吧, 手动掀桌!):

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
char ch[105][20], cadre[2], west[2];
int score1, score2, art, tot;
int ans, mx;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%s", ch[i]);
        scanf("%d%d%s%s%d", &score1, &score2, cadre, west, &art);
        int money = 0;
        if(score1 > 80 && art >= 1) money += 8000;
        if(score1 > 85 && score2 > 80) money += 4000;
        if(score1 > 90) money += 2000;
        if(score1 > 85 && west[0] == 'Y') money += 1000;
        if(score2 > 80 && cadre[0] == 'Y') money += 850;
        tot += money;
        if(money > mx) mx = money, ans = i;
    }
    printf("%s\n", ch[ans]);
    printf("%d\n%d\n", mx, tot);
    return 0;
}

1003

看上去有点奇怪, 然而难度很小, 跑一次相当于跑两次.直接上答案:

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int m, t, u, f, d;
char cond[1005][2];
int tot, i;

int main()
{
    scanf("%d%d%d%d%d", &m, &t, &u, &f, &d);
    for(i = 1; i < t + 1; ++i){
        scanf("%s", cond[i]);
        if(cond[i][0] != 'f') tot += (u + d);
        else tot += (2 * f);
        if(tot > m) break;
    }
    printf("%d\n", i - 1);
    return 0;
}

1004

记忆化深搜, 直接动龟+dfs

最主要的是从某个点开始dfs, 查看最大路程, 并且保存最大路程.

转移方程大概可以这样写, 上下左右的最大值+1:

S = max(sl, sr, su, sd) + 1

每次求完上下左右的时候保存当前点的路程, 然后一路dfs就行.

/* 12-19更新

有童鞋问我这个题的题解写的太简单,看不懂代码..

于是我把题解多写一些吧, 当一个动态规划的范例来讲解

(这样以后别人问我动态规划就可以一甩手将这个扔粗去了..)

h[105][105]指的是题目要给的矩阵, f[105][105]指的是每个点出发能走的最大路程, -1表示这个点的还没求, 不为-1表示这个点最大路程已经求出来了, 就是这个值

xx[4]和yy[4]表示x方向上和y方向上的偏移量, 比如x[0] = 0, y[0] = 1 表示向上偏移, 就是辣么简单易懂(- -!)

dfs(int i, int j)是从i行j列的点开始dfs, 找最大路程, 对四个偏移量来讲, 如果偏移后的结果比当前结果小, 就从偏移后结果开始递归, 递归方程就是我上面写的转移方程, 返回值就是求出来的f[i][j], 动态规划思想的主要体现就在于记忆化搜索, 对转移方程来讲:

s = max(sl, sr, su, sd) + 1, 如果sl, sr, su, sd的值不为 -1, 便可以直接返回, 避免了重复计算, 降低了复杂度。

上答案:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int r, c, ans;
int h[105][105], f[105][105];
int xx[4] = {0, 0, 1, -1}, yy[4] = {1, -1, 0, 0};
int dfs(int x, int y){
    if(x < 1 || y < 1 || x > r || y > c) return 0;
    if(f[x][y] != -1) return f[x][y];
    f[x][y] = 1;
    for(int i = 0; i < 4; ++i){
        int tx = x + xx[i], ty = y + yy[i];
        if(h[tx][ty] < h[x][y])
            f[x][y] = max(f[x][y], dfs(tx, ty) + 1);
    }
    return f[x][y];
}

int main()
{
    memset(f, -1, sizeof(f));
    scanf("%d%d", &r, &c);
    for(int i = 1; i <= r; ++i)
        for(int j = 1; j <= c; ++j)
            scanf("%d", &h[i][j]);
    for(int i = 1; i <= r; ++i)
        for(int j = 1; j <= c; ++j)
            if(f[i][j] == -1)
                ans = max(ans, dfs(i, j));
    printf("%d\n", ans);
    return 0;
}