CSP M4 （A - TT数鸭子）（B - ZJM要抵御宇宙射线）（C - 宇宙狗的危机）

A - TT数鸭子

思路

给你n个很多未的数，然后有个k表示最大能有k-1位数是不一样的，输出符合的数的个数（大概就这个意思）

因为是位数（十位百位千位），所以k最大就是10（0-9），然后去遍历每个数（字符串存储）判断一下就可以了。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<bitset>
#define llong long long
#define For(i,a,n) for(register int i=a;i<=n;i++)
#define RF(i,a,n) for(register int i=a;i>=n;i--)
#pragma GCC optimize(2)
using namespace std;

const int maxn = 100005;
int n, k, cnt, ans;
int b[15];
string s;

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k;
    For(i,1,n){
    	memset(b,0,sizeof(b));
    	cnt = 0;
    	cin>>s;
    	int len = s.length();
    	For(j,0,len-1){
    		int t = s[j]-'0';
    		if(!b[t]){
    			cnt++;
    			b[t] = 1;
    		}
    	}
    	if(cnt<k) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

B - ZJM要抵御宇宙射线

思路

给你n个点，然后求圆心（在这些点中）而且包含全部点的最小半径的平方
暴力就完事了，主要还是题目没仔细看导致0分。。。

• 圆心在这些点中
• 遍历每个点，求每个点与其他点的最大距离。
• 答案取所有点当圆心中半径距离最小的。
• 输出半径的平方

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#define llong long long
#define For(i,a,n) for(register int i=a;i<=n;i++)
#define RF(i,a,n) for(register int i=a;i>=n;i--)
#pragma GCC optimize(2)
using namespace std;

const int maxn = 100005;
struct node{
	double x, y;
	bool operator < (const node& b) const{
		if(x==b.x) return y<b.y;
		return x<b.x;
	}
}v[maxn];
int n, tot, idx;
double maxd = 1e15, maxt;

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    For(i,1,n){
    	cin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+1+n);
    For(i,1,n){
    	maxt = 0;
    	For(j,1,n){
    		if(i==j) continue;
    		double t = (v[i].x-v[j].x)*(v[i].x-v[j].x)+(v[i].y-v[j].y)*(v[i].y-v[j].y);
    		if(t>maxt){
    			maxt = t;
    		}
    	}
    	if(maxt<maxd){
    		maxd = maxt;
    		idx = i;
    	}
    }
    cout<<fixed<<setprecision(2)<<v[idx].x<<" "<<v[idx].y<<endl<<maxd<<endl;
    return 0;
}

C - 宇宙狗的危机

思路

给你个n个数的升序数组，问是否能构成一颗二叉搜索树。
刚开始想着用分段去做，但是没想到是区间dp。。。

• 用一个数组b记录一下a[i]和a[j]的gcd是否大于1，方便转移
• 用两个数组LEFT、RIGHT记录左右子树的情况
• 区间LEFT[L, k]和区间RIGHT[k,R]可以，区间FINAL[L, R]才可以
• 用LEFT[L, R]更新RIGHT[L-1, R]，用RIGHT[L, R]更新LEFT[L, R+1]

区间dp的核心代码

for(int i=1; i<=n; i++){	//枚举长度
	for(int l = 1, r = l+i-1; r<=n; l++, r++){	//枚举起点
		for(int k=l; k<=r; k++){	//枚举分割点
			if(lf[l][k] && rg[k][r]){
				m[l][r] = 1;
				if(b[l-1][k]) rg[l-1][r] = 1; 
				if(b[k][r+1]) lf[l][r+1] = 1;
			}
		}
	}
}

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#define llong long long
#define For(i,a,n) for(register int i=a;i<=n;i++)
#define RF(i,a,n) for(register int i=a;i>=n;i--)
#pragma GCC optimize(2)
using namespace std;

const int maxn = 705;
int t, n;
int a[maxn], m[maxn][maxn], b[maxn][maxn];
int lf[maxn][maxn], rg[maxn][maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        memset(m,0,sizeof(m));
        memset(lf,0,sizeof(lf));
        memset(rg,0,sizeof(rg));
        cin>>n;
        For(i,1,n){
            cin>>a[i];
            lf[i][i] = rg[i][i] = m[i][i] = 1;
        }
        For(i,1,n){
            For(j,i+1,n){
                b[i][j] = __gcd(a[i],a[j])>1;
            }
        }
        For(i,1,n){
            for(int l = 1, r = l+i-1; r<=n; l++, r++){
                For(k,l,r){
                    if(lf[l][k] && rg[k][r]){
                        m[l][r] = 1;
                        if(b[l-1][k]) rg[l-1][r] = 1; 
                        if(b[k][r+1]) lf[l][r+1] = 1;
                    }
                }
            }
        }
        if(m[1][n]) 
            cout<<"Yes"<<endl;
        else 
            cout<<"No"<<endl;
    }
    return 0;
}