admin 管理员组文章数量: 887007
week16
A - TT数鸭子
问题描述
TT来到一个小湖边，看到了许多在湖边嬉戏的鸭子，TT顿生羡慕。此时他发现每一只鸭子都不一样，或羽毛不同，或性格不同。TT在脑子里开了一个map<鸭子，整数> tong，把鸭子变成了一些数字。现在他好奇，有多少只鸭子映射成的数的数位中不同的数字个数小于k。
Input
输入第一行包含两个数n,k，表示鸭子的个数和题目要求的k。接下来一行有n个数， a i a_i ai每个数表示鸭子被TT映射之后的值。
Output
输出一行，一个数，表示满足题目描述的鸭子的个数。
注意无行末空格
Example
Input
6 5
123456789 9876543210 233 666 1 114514
1
2
Output
4
1
解题思路
这个问题并不复杂，写这道题主要是因为考试时写的代码在vj中超时了，始终解决不了这个问题，只好用C语言重新写了一个
代码
#include <stdio.h>long long int x;
int n, k, ans = 0;int main()
{scanf("%d%d", &n, &k);for (int i = 0; i < n; i++){scanf("%lld", &x);int y;int a[11] = {0};while (x > 0){y = x % 10;a[y]++;x /= 10;}int tot = 0;for (int i = 0; i < 10; i++)if (a[i] > 0)tot++;if (tot < k)ans++;}printf("%d", ans);return 0;
}C - 宇宙狗的危机
问题描述
在瑞神大战宇宙射线中我们了解到了宇宙狗的厉害之处，虽然宇宙狗凶神恶煞，但是宇宙狗有一个很可爱的女朋友。
最近，他的女朋友得到了一些数，同时，她还很喜欢树，所以她打算把得到的数拼成一颗树。
这一天，她快拼完了，同时她和好友相约假期出去玩。贪吃的宇宙狗不小心把树的树枝都吃掉了。所以恐惧包围了宇宙狗，他现在要恢复整棵树，但是它只知道这棵树是一颗二叉搜索树，同时任意树边相连的两个节点的gcd(greatest common divisor)都超过1。
但是宇宙狗只会发射宇宙射线，他来请求你的帮助，问你能否帮他解决这个问题
补充知识：
GCD：最大公约数，两个或多个整数共有约数中最大的一个 ，例如8和6的最大公约数是2。
一个简短的用辗转相除法求gcd的例子：
int gcd(int a,int b){return b == 0 ? a : gcd(b,a%b);}
1
Input
输入第一行一个t，表示数据组数。
对于每组数据，第一行输入一个n，表示数的个数
接下来一行有n个数 a i a_i ai，输入保证是升序的。
Output
每组数据输出一行，如果能够造出来满足题目描述的树，输出Yes，否则输出No。
无行末空格。
Example
Input
16
3 6 9 18 36 108
Output
Yes
Input
22
7 17
9
4 8 10 12 15 18 33 44 81
Output
思路
这个问题的关键在于要构造的树是二叉搜索树，即对于 a i a_i ai 元素来说，所有比 a i a_i ai 小的都不可能在右子树中，所有比 a i a_i ai 大都不可能在左子树中。根据这一性质，可以使用区间DP来处理。
首先定义两个数组： l e [ i ] [ j ] le[i][j] le[i][j], r i [ i ] [ j ] ri[i][j] ri[i][j] 分别表示以 i i i 为根，向左到 j j j 可以作为 i i i 的左子树，向右到 j j j 可以作为的右子树。
定义状态， d p [ i ] [ j ] dp[i][j] dp[i][j] 表示 i − j i - j i−j可以构成二叉搜索树。
同时根据， l e le le r i ri ri数组的定义，
i f ( l e [ i ] [ k ] = = r i [ k ] [ j ] = = t r u e ) , d p [ i ] [ j ] = t r u e if(le[i][k]==ri[k][j]==true),dp[i][j]=true if(le[i][k]==ri[k][j]==true),dp[i][j]=true
且此时树根为k。
那么， l e le le数组的状态转移方程为，
i f ( d p [ i ] [ j ] = = t r u e ) , l e [ i ] [ j + 1 ] = ∑ k = i j g c d ( a [ k ] , a [ j + 1 ] ) if(dp[i][j]==true),le[i][j+1]=\sum_{k=i}^{j} gcd(a[k],a[j+1]) if(dp[i][j]==true),le[i][j+1]=k=i∑jgcd(a[k],a[j+1])
同理， r i ri ri数组的状态转移方程为
i f ( d p [ i ] [ j ] = = t r u e ) , r i [ i − 1 ] [ j ] = ∑ k = i j g c d ( a [ k ] , a [ i − 1 ] ) if(dp[i][j]==true),ri[i-1][j]=\sum_{k=i}^{j} gcd(a[k],a[i-1]) if(dp[i][j]==true),ri[i−1][j]=k=i∑jgcd(a[k],a[i−1])
输出 d p [ 1 ] [ n ] dp[1][n] dp[1][n]就OK了
No
Yes
代码
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;const int maxn = 700 + 100;
int T, n, a[maxn];bool dp[maxn][maxn], gc[maxn][maxn], le[maxn][maxn], ri[maxn][maxn];int gcd(int _a, int _b) { return _b == 0 ? _a : gcd(_b, _a % _b); }int main()
{cin >> T;while (T--){cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];memset(le, false, sizeof(le));memset(ri, false, sizeof(ri));memset(dp, false, sizeof(dp));for (int i = 1; i <= n; i++){le[i][i] = true;ri[i][i] = true;dp[i][i] = true;for (int j = 1; j <= n; j++)gc[i][j] = gcd(a[i], a[j]) > 1;}for (int l = 1; l <= n; l++){for (int i = 1; i <= n - l + 1; i++){int j = i + l - 1;for (int k = i; k <= j; k++){if (le[k][i] && ri[k][j]){dp[i][j] = true;le[j + 1][i] |= gc[j + 1][k];ri[i - 1][j] |= gc[i - 1][k];}}}}if (dp[1][n])cout << "Yes" << endl;elsecout << "No" << endl;}return 0;
}
本文标签： week16
版权声明：本文标题：week16 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732355250h1534247.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论