22.1.20

一.oj补题

1. Distinct Sub-palindromes

思路借用这位xiongyuqing博主的文章:

Distinct Sub-palindromes_xiongyuqing的博客-CSDN博客22.1.20https://blog.csdn.net/qq_45364953/article/details/107498968?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164264199216780271924000%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=164264199216780271924000&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-107498968.first_rank_v2_pc_rank_v29&utm_term=Distinct+Sub-palindromes&spm=1018.2226.3001.4187
用 x, y , z代表26个英文字母变量
1、当n = 1时:长度为1的字符串s只能有一个字母假设为 x ,然而x有26种取法,所以s的数量为26

2、当n = 2时:长度为2的字符串s类型可以是 xx, xy,它们本质不同的回文子串都只有两种,xx类型的回文子串为x,xx。xy类型的回文子串为x,y。它们构成的字符串s的数量为:26(xx) + 26×25(xy) = 26^2

3、当n = 3时:长度为3的字符串s的类型可以是xxx, xxy, xyx, yxx, xyz,它们本质不同的回文子串的个数都是3,并且找不到回文子串个数更少的字符串s的构造方法。s的数量为:26(xxx) + 26×25×3(xxy,xyx,yxx) + 26×25×24(xyz) = 17576 = 26^3

4、当n = 4时:我们发现在n=3的基础上将这四种类型:xxx,xxy,xyx,yxx本身已经有3种不同的回文子串,不管怎么延长它们的长度到 n ,比如说延长到n = 4,总有4个本质不同的回文子串,但是对于xyz类型将其延长到4时,如果时这样的延长方式:xyzx,就只有3个本质不同的回文子串:x,y,z。所以xyzx是本质不同的回文子串个数最少的字符串类型,有26×25×24(xyzx)种。

5、当n > 4时:可以将xyzxyzxy…不断延长到长度n, 它的回文子串个数始终是3:x,y,z,所以这种类型的字符串的回文子串个数最少,有26×25×24种。

但是他的代码ac不了,会TLE;我选择直接输出答案,这样ac了;

#include<bits/stdc++.h>

using namespace std;

int n,t;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        if(n==1){
            cout<<"26\n";
        }else if(n==2){
            cout<<"676\n";
        }else if(n==3){
            cout<<"17576\n";
        }else if(n>=4){
            cout<<"15600\n";
        }
    }
    return 0;
}

二.数据结构

1.单链表的操作

①头节点插入一个元素

void add_head(int x )
{
	e[idx]=x;
	ne[idx]=head;
	head=idx;
	idx++;
}

②在k节点后插入一个元素;

void add(int k,int x)
{
	e[idx]=x;
	ne[idx]=ne[k];
	ne[k]=idx++;
}

③删除k节点的后的元素;

void remove(int k)
{
	ne[k]=ne[ne[k]];
}

删除头结点:head=ne[head];

2.双链表

与单链表的区别就是没个元素有两个指针,一个指针指向前边的元素,一个指针指向后边的元素;

初始化,0是左端点,1是右端点;

void init()
{
	r[0]=1;
	l[1]=0;
	idx=2;
}

①在节点k的右边插入一个数x;多画图理解:要修改谁的左右指针,就最外层是l[谁]或者r[谁];

void add(int k,int x)
{
	e[idx]=x;①先将x存在idx结点
	l[idx]=k;②然后idx的左指针指向k;
	r[idx]=r[k];③idx的右指针指向k的右指针,即下一个数;
	l[r[k]]=idx;④下一个数的左指针指向idx;
	r[k]=idx++;⑤k的右指针指向idx;然后idx加1;
}

22.1.20

就是完成4条红线的过程; 

注意n=k++;是先将k的值赋给n,然后再k++,虽然查到的资料显示++的运算级比=高。。

②删除节点k;

void remove(int k)
{
	l[r[k]]=l[k];
	r[l[k]]=r[k];
}

3.栈结构

先进先出;

一个操作,1.向栈顶插入一个数;2.从栈顶弹出一个数;3.判断是否为空;4.查询栈顶元素;

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;



int m;
int stk[N], tt;

int main()
{
    cin >> m;
    while (m -- )
    {
        string op;
        int x;

        cin >> op;
        if (op == "push")
        {
            cin >> x;
            stk[ ++ tt] = x;1.向栈顶插入一个数;
        }
        else if (op == "pop") tt -- ;2.从栈顶弹出一个数;
        else if (op == "empty") cout << (tt ? "NO" : "YES") << endl;3.判断是否为空;
        else cout << stk[tt] << endl;4.查询栈顶元素;
    }

    return 0;
}

三.oj训练赛

1. Chess Tourney

题意:输入一个整数n,接着输入2*n个数字,代表2*n个选手的实力。

      实力值大的选手可以赢实力值小的选手,实力值相同则都有可能赢。

      叫你把这2*n个选手分成2个有n个选手的队伍。

      问你是否有一种分法让一个队伍必定会赢。

只要保证1队最弱的强于2对最强的即可;

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;
int a[N];

int n;

int main()
{
	cin>>n;
	for(int i=0;i<n*2;i++)
	{
		scanf("%d",&a[i]);
	}
    sort(a,a+2*n);
    if(a[n-1]<a[n])cout<<"YES";
    else cout<<"NO";
    return 0;
}

2. Game of the Rows

题意:飞机有N排,每排八个座位 12  3456   78,要求不同的队伍不能相邻.

题解:

很坑的一道题目,因为考虑到放在中间的也可以放在两边,而放在两边的不一定能放在中间。所以我们先尽量往中间放。

我们考虑将每一个数分解成4,2,1 的形式,然后先把4往中间放,如果中间放不下了就把4拆成两个2。

然后放2,如果放不下了就把2拆成两个1。

最后判断一下有没有放完就可以了。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n,k,f,t,o,num1,num2;

int main()
{	
	cin>>n>>k;
	num1=n;num2=2*n;
	for(int i=1;i<=k;i++)
	{
		int x;
		scanf("%d",&x);
		f+=x/4;x%=4;
		t+=x/2;x%=2;
		o+=x;
	}
	while(f>0)
	{
		num1--;
		f--;
		if(num1==0||f==0)break;
	}
	t+=f*2;f=0;
	int num=num1+num2;
	while(t>0)
	{
		num--;
		t--;
		if(num==0||t==0)break;
	}
	num+=num1;
	o+=t*2;t=0;
	while(o>0)
	{
		num--;
		o--;
		if(num==0||o==0)break;
	}
	if(t||f||o)cout<<"NO";
	else cout<<"YES";
    return 0;
}

上一篇:Mybatis关联查询


下一篇:c++实现双链表基本操作详解