6 5
123456789 9876543210 233 6661 114514
4
这道题最大的难点，在于读懂题目！！
数位中不同的数字是？比如12345，将每位数字看做独立的，有1个1、1个2、1个3、1个4、1个5，因此有5个不同的数字；
233中，有1个2、2个3，有3个不同的数字；666中，有3个6，只有1个不同的数字。
然后把整个一串数字当成字符串处理就好了，对每个数位的数进行统计。
#include<iostream>
#include<string>
using namespace std;
int n, k, num = 0;
string s;
bool a[10];
int main()
{
cin >> n >> k;
for (int j = 0; j < 10; j++) a[j] = 0;
for (int i = 0; i < n; i++)
{
cin >> s;
int m = s.length();
for (int j = 0; j < m; j++)
a[s[j] - '0'] = 1;
int nn = 0;
for (int j = 0; j < 10; j++)
{
if (a[j] == 1) {
a[j] = 0;
nn++;
}
}
if (nn < k) num++;
}
cout << num;
//system("Pause");
}
5
0 0
0 1
1 0
0 -1
-1 0
0.00 0.00
1.00
5
0 1
0 -7
-3 0
3 0
-3 -3
3 -3-3.00 -3.00
45.00
考虑暴力算法（想过用任一个点找直径的方法，但问题有二：一、求出直径不知道怎么寻找点；二、无法证明方法正确性，模拟的时候也没时间证明，不过感觉不大对？）。
暴力算法的话，时间复杂度在O（n^2）左右，1000的数据量计算量在1e6，不会超时。
要保留小数点，类型直接用的double。
首先，算出两点之间距离的平方，存储在二维数组中，然后对每个点，找到其最长距离（即如果以该点为圆心，半径最小为？）
然后在所有的最小半径中找到最小的，即为答案。
所以既然要输出半径的平方为什么输出小数点呢（小声吐槽）……
#include<iostream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
double x[1005], y[1005];
double dis[1005][1005];
double mm[1005];
const double inf = 1e11;
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> x[i] >> y[i];
double maxx = 0;
for (int i = 0; i < n; i++) {
dis[i][i] = 0;
for (int j = i + 1; j < n; j++) {
double u = x[i] - x[j];
double v = y[i] - y[j];
dis[j][i] = dis[i][j] = u * u + v * v;
}
}
double minn = inf;
for (int i = 0; i < n; i++) {
double maxx = 0;
for (int j = 0; j < n; j++){
maxx = max(maxx, dis[i][j]);
}
mm[i] = maxx;
if (minn > maxx) minn = maxx;
}
double ansx = 1e5, ansy = 1e5;
for (int i = 0; i < n; i++) {
if (mm[i] == minn)
{
if (x[i] < ansx || (x[i] == ansx && y[i] < ansy))
ansx = x[i], ansy = y[i];
}
}
//double ans = sqrt(minn);
cout << setiosflags(ios::fixed) << setprecision(2) << ansx << " " << ansy << endl;
cout << setiosflags(ios::fixed) << setprecision(2) << minn;
system("Pause");
}
1
6
3 6 9 18 36 108Yes2
2
7 17
9
4 8 10 12 15 18 33 44 81No
Yes
一个dp问题。
lef [ i ][ k ] = 1，表示存在一个满足条件的树，根节点是k，i ~ （k - 1）是它的左后代，这棵树没有右子树；
righ [ k ][ j ] = 1，表示存在一个满足条件的树，根节点是k，（k + 1） ~ j 是它的右后代，这棵树没有左子树；
如果存在一个k，使得lef [ i ][ k ] & righ [ k ][ j ]，那么在[ i, j ]区间上，可以以 k 根节点作一颗满足条件的树。
状态转移来了：
如果存在一个k，使得lef [ i ][ k ] & righ [ k ][ j ]，如果（i - 1）与 k 连线满足条件，可以将合并后的树整个作为（i - 1）的右子树，（i - 1）作为根节点，因为 i ~ j 是有序的，（i - 1）比合并后树的任意一个节点都小，即righ[ i - 1 ][ j ] = 1；
同理，如果（j + 1）与 k 连线满足条件，lef[ i ][ j + 1 ] = 1。
初始化，lef 与 right 对角线元素为1。
先计算小区间，再计算大区间，状态转移每一次向左右分别扩展1格，在写循环是要格外注意。
剪枝
是一个三重循环，但是在状态转移的时候实际上转移后与k没什么关系，因此如果将 righ[ i - 1 ][ j ] = 1 与 lef[ i ][ j + 1 ] = 1均标记成1了，那么就可以直接跳出 k 循环了，否则就要对每个 k 进行判断。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 705;
int num[maxn];
bool lef[maxn][maxn], righ[maxn][maxn], is[maxn][maxn];
int n, t;
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a%b);}
void init()
{
for (int i = 1; i <= n; i++){
for (int j = i; j <= n; j++) {
if (gcd(num[i], num[j]) > 1) is[i][j] = is[j][i] = 1;
else is[i][j] = is[j][i] = 0;
}
}
}
bool solve()
{
for (int j = 1; j <= n; j++) {
for (int i = j; i >= 1; i--) {
bool u = 0, v = 0;
for (int k = i; k <= j; k++) {
if (lef[i][k] && righ[k][j]) {
if (is[k][j + 1]){
lef[i][j + 1] = 1;
u = 1;
}
if (is[i - 1][k]) {
righ[i - 1][j] = 1;
v = 1;
}
if (u && v) break;
}
}
}
}
bool ans = 0;
for (int k = 1; k <= n; k++)
if (lef[1][k] && righ[k][n]) {
ans = 1;
break;
}
return ans;
}
int main()
{
cin >> t;
while (t--) {
cin >> n;
memset(lef, 0, sizeof lef);
memset(righ, 0, sizeof righ);
for (int i = 1; i <= n; i++) {
cin >> num[i];
lef[i][i] = righ[i][i] = 1;
}
//sort(num + 1, num + n + 1);
init();
if (solve()) cout << "Yes" << endl;
else cout << "No" << endl;
}
system("Pause");
}