3.6

[蓝桥杯2016初赛]密码脱落

题目描述
X星球的考古学家发现了一批古代留下来的密码。这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

输入
输入存在多组测试数据，对于每组测试数据输入一行，表示现在看到的密码串（长度不大于1000）

输出
对于每组测试数据要求输出一个正整数，表示至少脱落了多少个种子。

样例输入
ABCBA
ABDCDCBABC

样例输出
0
3

题意：
给一个字符串，原本是回文串，现在脱落了几个字母，问最少脱落了多少个字母，使得回文串成现在的字符串。

思路：
最大公共子序列..
字符串a为题目输入的字符串，字符串b为a的reverse。
求得a和b的最大公共子序列，然后a.size()减去最大公共子序列的长度即为答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e5+5;

string a,b;
int dp[1005][1005];


int main (){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	while(cin>>a){
		memset(dp,0,sizeof(dp));
		b=a;
		reverse(b.begin(),b.end());
		for(int i=0;i<a.size();i++){
			for(int j=0;j<b.size();j++){
				if(a[i]==b[j]){
					dp[i+1][j+1]=dp[i][j]+1;
				}
				else{
					dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
				}
			}
		}
		cout<<(a.size()-dp[a.size()][b.size()])<<endl;
	}
	
	return 0;
}

[蓝桥杯2016初赛]四平方和

题目描述
四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去，就正好可以表示为4个数的平方和。
比如：
5 = $0^2 + 0^2 + 1^2 + 2^2$
7 = $1^2 + 1^2 + 1^2 + 2^2$（^符号表示乘方的意思）
对于一个给定的正整数N，可能存在多种平方和的表示法。
要求你对4个数排序：0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法

输入
输入存在多组测试数据，每组测试数据输入一行为一个正整数N (N<5000000)

输出
对于每组测试数据，要求输出4个非负整数，按从小到大排序，中间用空格分开

样例输入
5
12
773535

样例输出
0 0 1 2
0 2 2 2
1 1 267 838

暴力…

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e5+5;
 
 
int N; 
int a,b,c,d;
int temp;
 
void solve(int n){
    for( a=0;a<=temp;a++){
        for( b=0;b<=temp;b++){
            for( c=0;c<=temp;c++){
                d=sqrt(n-a*a-b*b-c*c);
                if(n==a*a+b*b+c*c+d*d){
                    return ;
                }
            }
        }
    } 
}
int main (){
    while(scanf("%d",&N)!=EOF){
        temp=sqrt(N);
        solve(N);
        printf("%d %d %d %d\n",a,b,c,d);
    }
    return 0;
}