正文

squarewords（codevs3301）

Cola  Cola  2022-08-05  170

关键词：

题目描述 Description

定义square words为：

1.长度为偶数。

2.前一半等于后一半。

比如abcabc和aaaa都是square words，但是abcabcab和aaaaa都不是。

现在有一个长度为n的字符串，求至少要删掉多少个字符，使得剩下的字符串是square words。

输入描述 Input Description

第一行包含一个正整数n。

第二行一个长度为n的字符串，仅包含小写字母

输出描述 Output Description

仅包含一个整数，表示最少需要删掉的字符数

样例输入 Sample Input

abaccdaabcd

样例输出 Sample Output

数据范围及提示 Data Size & Hint

【样例说明】

abaccdaabcd

【数据规模】

对于40%的数据，n ≤ 20；

对于100%的数据，n ≤ 500。

/*
  ，枚举断点，求最长公共子序列
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#define M 510
using namespace std;
char s[M],a[M],b[M];
int n,n1,n2,f[M][M],ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      cin>>s[i];
    for(int k=1;k<n;k++)
    {
        memset(f,0,sizeof(f));
        n1=0,n2=0;
        for(int i=1;i<=k;i++)
          a[++n1]=s[i];
        for(int i=k+1;i<=n;i++)
          b[++n2]=s[i];
        for(int i=1;i<=n1;i++)
          for(int j=1;j<=n2;j++)
          {
              if(a[i]==b[j])f[i][j]=max(f[i-1][j-1]+1,f[i]

[j]);
              f[i][j]=max(f[i][j],max(f[i-1][j],f[i][j-1]));
              ans=max(ans,f[i][j]);
          }
    }
    printf("%d",n-ans*2);
    return 0;
}

View Code

前端学习（3301）：类组件的ref

查看详情

poj3301：texastrip（计算几何+三分）

http://poj.org/problem?id=3301题意：在二维平面上有n个点，每个点有一个坐标，问需要的正方形最小面积是多少可以覆盖所有的点。思路：从第二个样例可以看出，将正方形旋转45°的时候，面积是最小的。因此考虑旋转正方形，就... 查看详情

[loj3301]魔法商店(代码片段)

令$A=\\a_1,a_2,...,a_s\\$，若$k\\not\\inA$，那么恰存在一个$A\'\\subseteqA$使得$c_k=\\bigoplus_x\\inA\'c_x$存在性：若不存在，将$k$加入$A$中仍然为合法的集合，与$|A|$最大矛盾唯一性：若存在多个，将其中两个集合异或（即保留在这两个集合... 查看详情

p3301[sdoi2013]方程(代码片段)

P3301[SDOI2013]方程题意：题解：插板法介绍首先要先讲组合数学的一个方法：插板法问题引出：把10个球放进三个盒子，每个箱子至少一个有多少种分法？10个球就有9个空隙，我们可以考虑在这个9个空隙... 查看详情

bzoj3301:[usaco2011feb]cowline

新姿势康托展开。。------------------------------------裸的康托展开&逆康托展开　　康托展开就是一种特殊的hash，且是可逆的……　　康托展开计算的是有多少种排列的字典序比这个小，所以编号应该+1；逆运算同理（-1）。　　... 查看详情

poj3301--texastrip（最小正方形覆盖）

题目链接：点击打开链接题目大意：给出n个点的坐标。如今要求一个正方形，全然包围n个点。而且正方形面积最小，求最小的正方形面积。表示不能理解为什么面积随着角度的变化是一个单峰的函数，等待大牛告诉一下，，。... 查看详情

loj3301「联合省选2020a」魔法商店-拟阵-保序回归

题目传送门　　传送门　　整个联考的区分度主要在会不会保序回归，次要在常数，有毒。。。　　关于以下使用的定理和结论的证明以及定义，请自行翻2018集训队论文。因为我都不会证。　　显然问题是给定一个拟阵$M$和两... 查看详情

嵌套的 while 语句仅在内部运行 SQL

...下行的表：DateValue01/01/20211.001/02/20210.501/02/20210.501/03/20210.3301/03/20210.3301/03/20210.3301/04/202 查看详情

p3301[sdoi2013]方程(代码片段)

思路容斥的挺好的练习题对于第二个条件，可以直接使m减去suma2，使得第二个条件舍去，然后m再减去n，使得问题转化成有n1个变量要满足小于等于某个数的条件，其他的随便取，求整数解的个数对n1，以2^n的复杂度枚举至少哪些... 查看详情

codevs4189字典

二次联通门:codevs4189字典 /*codevs4189字典Trie树裸题用指针写的..*/#include<cstdio>#include<cstring>#include<cstdlib>voidread(int&now){now=0;registercharword=getchar();while(word<‘0‘ 查看详情

[bzoj4326][codevs4632][codevs5440][uoj#150][noip2015]运输计划

[BZOJ4326][codevs4632][codevs5440][UOJ#150][NOIP2015]运输计划试题描述公元2044年，人类进入了宇宙纪元。L国有 n 个星球，还有 n?1 条双向航道，每条航道建立在两个星球之间，这 n?1 条航道连通了 L 国的所有星... 查看详情

codevs1086栈

http://codevs.cn/problem/1086/ (题目链接)题意　　给出1~n总共n个数，对它们进行入栈出栈操作，问一共有多少种不同的方案。Solution　　找规律手玩前4个发现是卡特兰数，再见。代码//codevs1086#include<algorithm>#include<iostream>#i... 查看详情

codevs1106篝火晚会

http://codevs.cn/problem/1106/ (题目链接)题意　　将1~n顺序排列的环改成另一个环，问n-不动点数。Solution　　啊智障啦，不会做×＿×　　左转hzwer代码//codevs1106#include<algorithm>#include<iostream>#include<cstdlib># 查看详情

codevs2115数集分割

codevs1080质数环

codevs1052

题目地址：http://codevs.cn/problem/1053/分析：模拟代码：vars:string;a:array[‘a‘..‘z‘]oflongint;i,j,t,n:longint;k:char;d:array[1..100000]oflongint;functioncf(x:longint):boolean;vari,y:longint;beginy:=0;fori:=2totru 查看详情

codevs3289花匠

题目：codevs3289花匠链接：http://codevs.cn/problem/3289/ 这道题有点像最长上升序列，但这里不是上升，是最长“波浪”子序列。用动态规划可以解决，方程类似最长上升子序列：f[i]=max(f[j]) (1≤j≤i-1&&((f[j]%2=1&&　A[j... 查看详情

codevs1296营业额统计

http://codevs.cn/problem/1296/ (题目链接)题意　　给出一个序列，对于每一个数，找出之前与它相差最小的数，两者相减取绝对值加入答案。Solution　　最近bzoj炸了，无奈只能上codevs刷题了。。好久没上过codevs了，实在是里面题目... 查看详情