12-20 tyvj水题记录(1010-1012)

Dec 20, 2016


“明明说好的已弃ACM了么?”

“然而看到水题根本控制不住双手T^T…正好c语言考试马上要来了, 没事刷刷水题”

tyvj是不兹词Chrome了么..登录不上, 于是手动评测(AC滑稽脸), 发现AC不了的话千万不要来找我(逃)

题目

(╯‵□′)╯︵┻━┻ 第9题是什么鬼, 不做了!, 有兴趣童鞋可以看一下第九题..

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

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

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

题解

1010

没什么好说的..主要思路就是对每个字母出现一次就映射到相应的一个计数器里面加1, 然后对计数器排个序, 用最后一个减去第一个不为0的数字就是m的值, 然后判断质数就行.

//然而tyvj提交了一发…部分数据时间炸了…有更好答案请联系我..

开始以为数据炸了…后来发现是评测延时的问题, 所以下面的代码就是答案没错了~

答案:

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
int i;
int cnt[30], maxm, minm, m;
char w[30];

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("%s", w);
    for(i = 0; w[i] != '\0'; ++i)
        cnt[w[i] - 'a']++;
    sort(cnt, cnt + 26);
    for(i = 0; i < 26; ++i)
        if(cnt[i] != 0){
            m = cnt[25] - cnt[i];
            break;
        }
    if(isprime(m)) printf("Lucky Word\n%d\n", m);
    else printf("No Answer\n0\n");
    
    return 0;
}


1011

这题做了很久..感觉如果竞赛的时候写这么久早就被拖出去xxxx了..

双线程dp, 然鹅第一眼没有看出来 (╯‵□′)╯︵┻━┻, 后来才慢慢缕清了思路.

思路在下面, 状态有四种转移情况

开一个f[i][j][k][w], 表示:

两条不相交叉的路径, 从0, 0到达第i, j 点(路径1) 和 k, w点(路径2)所能得到的最大权值

第一个点和第二个点都从上面下来到该点 f[i][j - 1][k][w - 1] + a[i][j] + a[k][w]

第一个点从左边和第二个点从上面到该点 f[i - 1][j][k][w - 1] + ……………..

第一个点从上边和第二个点从左边到该点 f[i][j - 1][k - 1][w] + ……………..

第一个点从左边和第二个点从左边到该点 f[i - 1][j][k - 1][w] + ……………..

当且仅当 两条路径除了起始点和终点, 没有交叉, 即四个for下面的那个if里的判断条件

答案:

#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;
int m, n;
int a[55][55];
int f[55][55][55][55];


int i, j, k, w;
int main(){
    scanf("%d%d", &m, &n);
    for(i = 1; i <= m; ++i)
        for(j = 1; j <= n; ++j)
            scanf("%d", &a[i][j]);

    for(i = 1; i <= m; ++i)
        for(j = 1; j <= n; ++j)
            for(k = 1; k <= m; ++k)
                for(w = 1; w <= n; ++w){
                    if((i < m || j < n) && i <= k && j <= w)continue;
                    f[i][j][k][w] = max(f[i][j][k][w], f[i][j - 1][k][w - 1]);
                    f[i][j][k][w] = max(f[i][j][k][w], f[i - 1][j][k][w - 1]);
                    f[i][j][k][w] = max(f[i][j][k][w], f[i][j - 1][k - 1][w]);
                    f[i][j][k][w] = max(f[i][j][k][w], f[i - 1][j][k - 1][w]);
                    f[i][j][k][w] += a[i][j];
                    f[i][j][k][w] += a[k][w];
                }

    printf("%d\n", f[m][n][m][n]);
    return 0;
}


1012

暴力搜索, 然而 提交之后还是有部分答案超时了, 只得了66分, (╯‵□′)╯︵┻━┻

说好的水题呢? 拖走..

开一大堆for循环, 前面三个表示可以表示出来的数字, 后面两个表示需要A和B的火柴数, 剩下那个C的直接用n减就行。

我的答案:

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n, r, ans;
int i, j, k, w, m, l;
int c[25] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
bool can(int y, int x){
    if(x == c[y]) return true;
    else return false;
}

int main()
{
    scanf("%d", &n);
    n = n - 4;
    for(i = 10; i <= 24; ++i){
        c[i] = c[i % 10] + c[i / 10];
    }
    for(i = 0; i <= 24; ++i)
        for(j = 0; j <= 24; ++j)
            for(k = 0; k <= 24; ++k)
                for(w = 1; w < n; w++)
                    for(m = 1; m < (n - w); m++)
                        if(can(i, w) && can(j, m) && can(k, n - w - m) && (i + j == k))
                            ans ++;
    printf("%d", ans);
    return 0;
}

全AC答案:

#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int n,ans;
int cnt[10]={6,2,5,5,4,5,6,3,7,6};
int get(int x)
{
    if(x==0)return 6;
    int tot=0;
    while(x)
    {
        tot+=cnt[x%10];
        x/=10;
    }
    return tot;
}
int main()
{
    scanf("%d",&n);
    n-=4;
    for(int i=0;i<=1000;i++)
        for(int j=0;j<=1000;j++)
            if(get(i)+get(j)+get(i+j)==n)
                ans++;
    printf("%d\n",ans);
    return 0;
}