csp 模测4

A

image.png

分析

其实。。这题很迷惑。k的数据范围。不过也不影响，只是判断每个数字的每一位的值在0-9中占几个。
上代码

#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

分析：多开一个根号，失去一百分系列。。。

这个题其实很简单，每次都找一个点到其他点的最大距离，最后找到这个最大值最小的点。
代码

#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

分析：

其实开始真的没意识到这是一道dp，学长说钱几个点数据很小，所以写了个N！复杂度的模拟。。果然前几个点都没全过。

**区间dp的思想借鉴了其他的博客
先把i j之间是不是gcd计算出来。。然后确定状态
t[i][j][0] 表示以i为根，[j][i-1]为左子树
t[i][j][1] 表示以i为根，[i+1][j]为右子树
状态转移方程
对于区间[i，j]，分别判断i-1与j+1能否加入二叉搜索树（和对应边集求或），其中k属于[i，j]
t[i-1][j][1] |= e[i-1][k]
t[j+1][i][0] |= e[j+1][k]
最后根据t，判断以各个数为根能否组成二叉搜索树
然后上代码：在这个思想指导下比较简单的写出来代码

#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;
        }
            
        //区间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");
    }
}