A
image.png
image.png
分析
其實(shí)。害淤。這題很迷惑扇雕。k的數(shù)據(jù)范圍。不過也不影響窥摄，只是判斷每個(gè)數(shù)字的每一位的值在0-9中占幾個(gè)镶奉。
上代碼
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<string.h>
using namespace std;
bool mm[10];
int main()
{
int n;
long long int k;cin>>n>>k;
int ans=0;
long long int a;
while(n--)
{
memset(mm,0,sizeof(mm));
scanf("%lld",&a);
int as=0;
int c;
while(a>0)
{
if(as==10) break;
c=a%10;
if(mm[c]!=1) mm[c]=1,as++;
a/=10;//123
}
if(as<k) ans++;
}
cout<<ans<<endl;
return 0;
}
B
image.png
image.png
分析：多開一個(gè)根號(hào)，失去一百分系列崭放。哨苛。。
這個(gè)題其實(shí)很簡(jiǎn)單币砂，每次都找一個(gè)點(diǎn)到其他點(diǎn)的最大距離建峭，最后找到這個(gè)最大值最小的點(diǎn)。
代碼
#include<iostream>
#include<algorithm>
#include <iomanip>
#include<cmath>
using namespace std;
struct zuob
{
double x;double y;
double m;
};
bool cmp(zuob& a,zuob& b)
{
if(a.m==b.m)
{
if(a.x==b.x)
{
return a.y<b.y;
}
else
{
return a.x<b.x;
}
}
else return a.m<b.m;
}
zuob s[1010];
int main()
{
int n;cin>>n;
for(int i=0;i<n;i++)
{
cin>>s[i].x>>s[i].y;
}
for(int i=0;i<n;i++)
{
s[i].m=0;
double m1;
for(int j=0;j<n;j++)
{
if(j==i) continue;
m1=(s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y);
if(m1>s[i].m) s[i].m=m1;
}
}
sort(s,s+n,cmp);
cout << setiosflags(ios::fixed) << setprecision(2) << s[0].x << " " << s[0].y << endl;
cout << setiosflags(ios::fixed) << setprecision(2) << s[0].m << endl;
//a1=s[0].x;b1=s[0].y;c1=s[0].m;
// printf("%lld.00 %lld.00\n%lld.00",s[0].x,s[0].y,s[0].m);
return 0;
}
image.png
image.png
image.png
分析：
其實(shí)開始真的沒意識(shí)到這是一道dp决摧，學(xué)長說錢幾個(gè)點(diǎn)數(shù)據(jù)很小亿蒸，所以寫了個(gè)N！復(fù)雜度的模擬掌桩。边锁。果然前幾個(gè)點(diǎn)都沒全過。
**區(qū)間dp的思想借鑒了其他的博客
先把i j之間是不是gcd計(jì)算出來波岛。茅坛。然后確定狀態(tài)
t[i][j][0] 表示以i為根，[j][i-1]為左子樹
t[i][j][1] 表示以i為根则拷，[i+1][j]為右子樹
狀態(tài)轉(zhuǎn)移方程
對(duì)于區(qū)間[i贡蓖，j]，分別判斷i-1與j+1能否加入二叉搜索樹（和對(duì)應(yīng)邊集求或）煌茬，其中k屬于[i斥铺，j]
t[i-1][j][1] |= e[i-1][k]
t[j+1][i][0] |= e[j+1][k]
最后根據(jù)t，判斷以各個(gè)數(shù)為根能否組成二叉搜索樹
然后上代碼：在這個(gè)思想指導(dǎo)下比較簡(jiǎn)單的寫出來代碼
#include <iostream>
#include <cstring>
#include<cstdio>
using namespace std;
int a[720];
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }
int t[720][720][2];
bool gong[720][720];
int main()
{
int t1; cin>>t1;
int n;
bool ok;
while (t1--)
{
memset(t, 0, sizeof(t));
ok=0;
cin >> n;
for (int i = 1; i <= n; i++)
{
// cout<<"?";
scanf("%d",&a[i]);
// cin>>a[i];
}
for(int i=1;i<=n;i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j) gong[i][j] = 0;
else
{
if(gcd(a[i], a[j]) > 1) gong[i][j]=1;
else gong[i][j]=0;
}
}
}
for (int i = 1; i <= n; i++)
{
t[i][i][0] = t[i][i][1] = 1;
}
//區(qū)間dp
for(int j=1;j<=n;j++)
{
for(int i=j;i>=1;i--)
{
for (int k = i; k <= j; k++)
{
if (t[k][i][0] && t[k][j][1])
{
if(gong[i -1 ][k]) t[i - 1][j][1]=1;
if(gong[j + 1][k]) t[j + 1][i][0]=1;
}
}
}
}
for (int i = 1; i <= n; i++)
{
if (t[i][1][0] && t[i][n][1])
{
printf("Yes\n");
ok=1;
break;
}
}
if (!ok) printf("No\n");
}
}
