【Week16模拟题】
A题
题意：思路：
分两种情况：
（1）k>10则直接输出n即可
（2）读入ai判断，ai转为数字以后中不同的个数sum，如果sum<k，则ans++。（ans是鸭子的个数）
（要读懂题啊，很关键，我读了半天真的没读懂）
注意： ai在最后面的几次测试超出了Int,要用long long
代码：
#include <iostream>
#include<stack>
using namespace std;
int n,k;
int ans=0;
int sum=0;
bool a[10];
void solve(long long int l);
int main()
{
ios::sync_with_stdio(false);
cin>>n>>k;
if(k>10)
{
cout<<n<<endl;
return 0;
}
for(int i=0;i<n;i++)
{
long long int ai;
cin>>ai;
solve(ai);
}
cout<<ans<<endl;
}
void solve(long long int l)
{
for(int i=0;i<10;i++)
a[i]=0;
sum=0;
while(l)
{
long long int j=l%10;
l=l/10;
if(a[j]==0)
{
a[j]=1;
sum++;
}
}
if(sum<k)
ans++;
}
B题：
题意：
思路：
首先算每个点到其他点的最大距离，然后放进p1数组里用来储存每个点可以到达其他点的最大距离，遍历完所有的点。
然后在遍历p1数组，找到距离最小的点作为原点即可。
注意： 数据处理的时候，初始化最小距离为1e11.
代码：
#include <iostream>
#include<stack>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;
int n;
double mins=1e11;
double maxs=0;
struct point
{
double x;
double y;
}p[1010];
double p1[1010];
double distance(point &p1,point&p2)
{
double x1=pow((p1.x-p2.x),2);
double y1=pow((p1.y-p2.y),2);
double ans=x1+y1;
return ans;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>p[i].x>>p[i].y;
}
//求一个点到其他点的最大距离
for(int i=1;i<=n;i++)
{
maxs=0;
for(int j=1;j<=n;j++)
{
if(j==i)
continue;
double dis=distance(p[i],p[j]);
if(dis>maxs)
{
maxs=dis;
}
}
p1[i]=maxs;
}
double x1,y1;
int j;
for(int i=1;i<=n;i++)
{
if(p1[i]==mins)
{
if(p[i].x<x1)
{
j=i;
continue;
}
else if(p[i].x==x1)
{
if(p[i].y<y1)
{
j=i;
continue;
}
}
}
else if(p1[i]<mins)
{
j=i;
mins=p1[i];
x1=p[i].x;
y1=p[i].y;
}
}
//x1=p[j].x,y1=p[j].y;
cout<<setiosflags(ios::fixed)<<setprecision(2);
cout<<p[j].x<<" "<<p[j].y<<endl;
cout<<mins<<endl;
}
C题
题意：
思路：
令l[i][j]表示以j为根,j的左子树可到i表示这样的BST是否存在，而r[i][j]表示以j为根,i的右子树可到j这样的BST是否存在.
c[i][j]则表示表示这个区间[i,j]合法，即a[i~j]可以组成BST。同等于l[i][k]&r[k][j]=1，k为[i,j]的根。
先计算出(i,j)的gcd即（i,j）的最大公约数，如果gcd>1则g[i][j]=1，否则g[i][j]=0。
接下来开始头疼的区间dp了，外层循环是1—n，第二层区间左端L和右端R，内层是用于状态转移的K。
开始判断：
（1）如果区间[L,R]合法且以K为根，则c[L][R]=1。
（2）如果g[K][L-1]=1（即根K和L-1可以相连），则根K可以作为L-1的右孩子（因为L-1<K）,即r[L-1][R]=1；同理，若g[K][R+1]=1，则根K可以作为R+1的左孩子，即l[L][R+1]=1。
（3）最后c[1][n]就是能否构成BST的答案。
总结：这道题真的不太会做哈.
当初模拟测试的时候，做到这里就卡了，不知道用什么思路来解决。然后去看了别的同学的思路。居然用dp，我dp真的学的不太好。。。得在期末考试以前好好弄弄动态规划
代码：
#include <iostream>
using namespace std;
int t,n;
const int maxn=710;
int a[maxn];
int g[maxn][maxn];
bool l[maxn][maxn];
bool r[maxn][maxn];
bool c[maxn][maxn];
int gcd(int a,int b)
{
return b==0 ? a : gcd(b,a%b);
}
int main()
{
cin>>t;
for(int i=0;i<t;i++)
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
g[i][j]=gcd(a[i],a[j]);
if(g[i][j]==1)
g[i][j]=0;
else
g[i][j]=1;
c[i][j]=0,l[i][j]=0,r[i][j]=0;
}
}
for(int i=1;i<=n;i++)
l[i][i]=r[i][i]=1;
int R;
//头疼的dp
for(int len=1;len<=n;len++)
{
for(int L=1,R=L+len-1;R<=n;L++,R++)
{
for(int K=L;K<=R;K++)
{
if(l[L][K]&&r[K][R])
{
c[L][R]=1;
if(g[K][L-1])
r[L-1][R]=1;
if(g[K][R+1])
l[L][R+1]=1;
}
}
}
}
if(c[1][n])
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}