[无标题]

好久没写blog了。。。。
以后就写点游记或者题解什么的吧。。。
觉得以前写的东西好sb。。。。
认真写写题吧,毕竟水了一年,要有梦想啊!

luogu四月计划

发现自己好久没写博客了。。。于是准备记录一下在洛谷刷水题的做题思路。
1510
裸的背包,可以看成一个体积为c,装n个物体,每个物体的价值和体积分别是物体的体积和物体的体力。最后再判断一下。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <sstream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define dep(i,a,b) for(register int i = (a); i >= (b); --i)
const int maxn = 100050;
int val[maxn],f[maxn],q[maxn],v,n,c,res=0,flag=0;
int main(){
    memset(f,0,sizeof(f));
    scanf("%d%d%d",&v,&n,&c);
    rep(i,1,n) scanf("%d%d",&val[i],&q[i]);
    rep(i,1,n)
    dep(j,c,q[i]){
        f[j] = max(f[j],f[j-q[i]]+val[i]);
        if(f[j] >= v)
        res = max(res,c-j),flag = 1;
    }
    if(flag) printf("%d\n",res);
    else printf("Impossible\n");
    return 0;
}

1466
dp,状态为f[i][j],表示考虑前i个数和为j的方案数。所以转移的话只有选或选不了。
f[i][j]=f[i-1][j]+f[i-1][j-i]

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <sstream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define dep(i,a,b) for(register int i = (a); i >= (b); --i)
const int maxn = 1005;
LL f[maxn][maxn],N,sum;
int main(){
	scanf("%lld",&N);
	sum=(N*(N+1))>>1;
	if(sum%2==1){printf("0\n");return 0;}
	f[1][0]=f[1][1]=1;
	rep(i,2,N)
	rep(j,0,sum){
		if(j>i)
		f[i][j]=f[i-1][j]+f[i-1][j-i];
		else f[i][j]=f[i-1][j];
	}
	printf("%lld\n",f[N][sum>>1]);
	return 0;
}
	

1352
在树上进行dp,用前向星存图,自底向上dp;

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <sstream>
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define dep(i,a,b) for(register int i = (a); i >= (b); --i)
using namespace std;
const int maxn = 6e3+10;
int head[maxn],c[maxn],h[maxn],f[maxn][2],rot,cnt = 0;
struct Edge{
	int ne,to;
}ed[maxn];
inline int max(int x,int y){
	return x>y?x:y;
}
inline void add1(int x,int y){
	ed[++cnt].to = y; ed[cnt].ne = head[x]; head[x] = cnt;
}
void dfs(int x){
	f[x][1] = h[x];
	for(register int i = (head[x]); i; i = ed[i].ne){
		int start = ed[i].to;
		dfs(start);
		f[x][1] += f[start][0];
		f[x][0] += max(f[start][0],f[start][1]);
	}
}
 int main(){
	int N;scanf("%d",&N);
	rep(i,1,N) scanf("%d",&h[i]);
	rep(i,1,N-1){
		int A,B;
		scanf("%d%d",&A,&B);
		++c[A];
		add1(B,A);
	}
	rep(i,1,N){
		if(!c[i]) {rot = i;break;}
	}
	dfs(rot);
	printf("%d",max(f[rot][0],f[rot][1]));
	return 0;
}
	

区间信息的维护与查询

做题

————分鸽线

莫队算法

莫队主要是用于离线处理一类只有查询不带修改的区间信息问题。
什么?这不Segment_tree?
Segment_tree处理此类问题时是通过拉分别拉一棵左右子树来进行合并,所以掐指一算o(ls+rs)
注意是子树。所以线段树在此类问题中会挂掉。
那怎么办?
考虑暴力,枚举每一个区间然后存储信息,复杂度是o(nm)其中m是询问次数。
显然易炸。
这时我们考虑优化一下,如果我们已求出[L,R]的信息,那我们是不是可以在o(1)的时间内知道[L+1,R][L-1,R][L,R+1][L,R-1]的信息?然后我们慢慢扩张到所求区间。复杂度是平面上的曼哈顿距离的最小生成树。
可跟暴力好像没什么区别呀?
我们把序列分块,询问左端点所在的分块的序号为第一关键字,右端点的大小为第二关键字进行排序,按照排序好的顺序计算,复杂度就会大大降低。
– 块相同时,r单调递增,所以r是O(n)的。共有n^{0.5}块,所以这一部分时间复杂度是O(n^{1.5})
– 块转移时,r最多变化n,由于有n^{0.5}块,所以这一部分时间复杂度是n^{1.5}
– 块相同时,左端点变化最多变化n^{0.5},而转移时,不会超过2 \sqrt{n}。由于有m次询问(和n同阶),所以时间复杂度是n^{1.5}
于是就是总复杂度就是O(n^{1.5})了。

一些乱七八糟的优化

  • 分块优化:听说分成\frac{n} { \sqrt {m\times\frac{2}{3} }}更快哦
    原来

    	int block = int (sqrt(n));
    	rep(1,m) pos[i] = (i-1)/block+1;
    

    优化

    	int block = n/sqrt(m*(2/3));
    	//每个块的编号是a[i].l / block;
    
  • 奇偶排序优化
    在原来的排序中,分块相同时,右指针是按从小到大排的。这样在转移时会走多余的路程。
    所以我们为了让右指针一直单调递增or递减,这样就会快的多。
    莫队本身是个暴力,就是靠分块才能维持的了生活。而如果是正常排序的话,右指针路程会重复。而只要让相邻两个快保持单调就会快很多
    原来

    	return pos[a.l] ^ pos[b.l]?a.l < b.l:a.r < b.r;
    

    优化

    	return (a.l / block) ^ (b.l /block) ?a.l < b.l:((a[i].l / block) &1) ?a.r <b.r:a.r>b.r)
    

    「」

train

「BZOJ2038」[2009国家集训队] 小Z的袜子(hose)
「Luogu1972」「SDOI2009HH的项链」
「Luogu2709」「小B的询问」

单调队列

学了一些有关单调队列的知识,这里放一些代码和一些需要注意的细节。
head=1,tail=0;这样可以防未进队就出队。
注意头部出队时可能为空。
而因为一系列操作,队列中的序号也是单调的。
但是需要注意的是head与tail也可以等于1,这样可以在决策单调性时可以使用。具体见以下例1与例3.

//fzu p 1894
#include <stdio.h>
const int MAX = 1000010;

using namespace std;

typedef long long LL;

char name[10],order[20];
LL value[MAX];
int T,q[MAX],head,tail;
int main(){
	scanf("%d",&T);
	scanf("%s",order);
	while(T--)
	{
	    int n=0,g=0;
		head=1,tail=0;
		while(scanf("%s",order)&&order[0]!='E')
		{
			if(order[0]=='C')
			{
			scanf("%s%d",name,&value[++n]);
			while(head<=tail&&value[q[tail]]<value[n])--tail;
			q[++tail]=n;
			}
			else if(order[0]=='Q'){if(head<=tail)printf("%d\n",value[q[head]]);else printf("-1\n");}
			else if(order[0]=='G'){++g;if(head<=tail&&q[head]==g)++head;}
		}
	}
	return 0;
}

poj 2823 g++
#include <cstring>
#include <cstdlib>
#include <stdio.h>
using namespace std;
const int MAX = 1000010;
inline int read(){
  int x=0,f=1;
  char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  return x*f;
}
int v[MAX],q[MAX],head,tail,n,k;
int main()
{
  int i;
  n=read();k=read();
  for(i=1;i<=n;++i)
    v[i]=read();
  if (k==1)
  {
    for (int i = 1; i <= n; ++i)
    {
      printf("%d ",v[i] );
    }
    printf("\n");
    for (int i = 1; i <= n; ++i)
    {
      printf("%d ",v[i] );
    }
    return 0;
  }
  head=1,tail=0;
  for(i=1;i<=n;++i)
  {
    while(head<=tail&&q[head]<i-k+1)
      ++head;
    while(head<=tail&&v[q[tail]]>=v[i])
      --tail;
    q[++tail]=i;
    if (i>=k)
    {
      printf("%d ",v[q[head]]);
    }
  }
    printf("\n");
    memset(q,0,sizeof(q));
  head=1,tail=0;
  for (i=1;i<=n;++i)
  {
    while(head<=tail&&q[head]<i-k+1)
      ++head;
    while(head<=tail&&v[q[tail]]<=v[i])
      --tail;
      q[++tail]=i;
    if(i>=k)
    {
      printf("%d ",v[q[head]]);
    }
  }
  return 0;
}
#include <bits/stdc++.h>

const int MAX = 1000010;

using std::scanf;
using std::printf;

inline int min(int x,int y){
	return x<y?x:y;
}

int f[MAX],q[MAX];
int main(){
	int n,m,i,j,head,tail,best = MAX;
	scanf("%d%d",&n,&m);
	head=tail=1;
	for(i=1;i<=n;++i)
	{ 
		int w;scanf("%d",&w);
		while(head<=tail&&q[head]<i-m)++head;
		f[i]=f[q[head]]+w;
		while(head<=tail&&f[q[tail]]>f[i])--tail;
		q[++tail]=i;
	}
	for(j=n-m+1;j<=n;j++)best=min(best,f[j]);
	printf("%d\n",best);
	return 0;
}

泛刷水题

luogu P1019
一道不错的深搜入门题,字符串细节要注意,调了很久结果发现读入时少了个’=’(T_T)

#include<string.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,length = 0,use[30];
string s[30];
int canlink(string s1,string s2)
{
    for(int i=1;i<min(s1.length(),s2.length());i++)
    {
        int flag=1;
        for(int j=0;j<i;j++)
            if(s1[s1.length()-i+j]!=s2[j]) flag = 0;
        if(flag)return i;
    }
    return 0;
}
void search(string str,int mlong)
{
    length = max(mlong,length);
    for(int i=0;i<n;i++)
    {
        if(use[i]>=2) continue;
        int c = canlink(str,s[i]);
        if(c>0)
        {
            use[i]++;
        search(s[i],mlong+s[i].length()-c);
            use[i]--;
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<=n;i++)
    {
    use[i]=0;
    cin>>s[i];
    }
    search(' '+s[n],1);
    cout<<length;
    return 0;
}

一些零零散散的字符串的常识

字符串是存储在内存的连续字节中的一系列字符。而字符在计算机中的表示则是根据ASCII表来的。而ASCII中数字的ASCII码<大写字母的ASCII码<小写字母的ASCII码。
接下来我介绍一些关于字符串的基本常识,想看AC自动机的自行绕开。
首先我们要明白字符在计算机中是以字节的形式存储的。而在C中,字符串是以空字符结尾的,即‘\0’;
所以字符数组后总有这个东西。而且”表示的是字符,””表示的是字符串,后面有\0结尾的。
好啦,那在实践中如何操作呢?
平常我们写字符串时用C风格是这样写的

char bird[11] = "Mr. Cheeps";

用引号括起来的字符串隐式地包括结尾的空字符,因此不用显式地包括它。注意,在确定字符串所需的最短数组时,别忘了将结尾的空字符计算在内。
可是有时候我们要根据字符串的字典序比较怎么破?

#include<string.h>
std::strcmp(s1,s2);

strcmp是个有返回值的函数,它根据字符串的ASCII值来比较,如果返回0,则证明s1==s2;返回负数,s1<s2;返回正数,s1>s2;。
拼接呢?

#include<string.h>
std::strcpy(s1,s2);

strcpy将s2的内容拷贝到足够长的s1里,注意’\0’也进去了。
长度呢?

#include<string.h>
std::strlen(s1);

它返回的是存储在数组中字符串的长度,不包括空字符。
这就是一些常用的字符串函数。
那说了这么多,怎么读入输出呢?
读入

cin>>a;
scanf("%s",s1);

这个的话它遇到空白就不读了。

getline(cin,s1);

它读入一整行,碰到换行结束。

gets(s1);

这个貌似风评不是很好?但也是读入一整行。
输出

printf("%s",s1);
puts(s1);

你有没有觉得太麻烦?连这么简单的操作都要调用函数,效率还低。。。。
CPP给我们提供了一个类string,你可以像操作数值数组一样。

string s1;
string s2;
string s3;
cin>>s2>>s3;
s1=s2;//拷贝
s3+=s1;//合并

具体的自己去看吧。

凯凯刚写了一篇美妙的作文,请问这篇作文的标题中有多少个字符? 注意:标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字 符数时,空格和换行符不计算在内。

输入输出格式
输入格式:
输入文件只有一行,一个字符串 ss。
输出格式:
输出文件只有一行,包含一个整数,即作文标题的字符数(不含空格和换行符)。

#include<string.h>
#include<stdio.h>
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
	freopen("title.in","r",stdin);  
    freopen("title.out","w",stdout);
    string s;
    getline(cin,s);
    int n=s.length(),ans=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]>='0' && s[i]<='9')
            ans++;
        if(s[i]>='a' && s[i]<='z')
            ans++;
        if(s[i]>='A' && s[i]<='Z')
            ans++;
    }
    printf("%d",ans);
    return 0;
}

排序专题

终于把数据排序写完了,肝了几天emmmm,首先声明一下有些题我知道可以用很简单的写法,但是写这些题本身就不是为了过题,而是为了提升码力,因为我码力太差了,所以可能写得有点复杂。
下文所有题目来自一本通OJ数据排序专题,部分贴加的来自luogu。
1.冒泡排序

#include<iostream>
const int INF =10000;
using namespace std;
int main(){
    int N,a[INF]={0},temp,tot=0;
    cin>>N;
    for(int i=1;i<=N;i++)cin>>a[i];
	for(int i=1;i<=N-1;i++)
	for(int j=1;j<=N-i;j++)
	{
		if(a[j+1]<a[j]){
			swap(a[j],a[j+1]);
		tot++;
	}
	}
    cout<<tot<<endl;
    return 0;
}

2.归并

#include<iostream>
using namespace std;
const int N =1000010;
long long  cnt=0,A[N],t[N];
void m(int l,int r){
  if(r-l>1){
  int mid=l+(r-l)/2;
  int x=l,y=mid,i=l;
  m(l,mid);
  m(mid,r);
  while(x<mid || y<r){
    if(y>=r || (x<mid && A[x]<=A[y])) t[i++]=A[x++];
    else {t[i++]=A[y++];cnt+=mid-x;}
  }
  for(int i=l;i<r;i++)A[i]=t[i];
}
}
int main(){
  int n;cin>>n;
  for(int i=1;i<=n;i++)cin>>A[i];
  m(1,n+1);
  std::cout << cnt << '\n';
  return 0;
}

3.结构体加快速选择作法 O(n)

#include<iostream>
using namespace std;
struct node{
  int xh;
  double fs;
}A[100];
int k,n,ans;
void qs(int a,int b){
  if(a>=b)
  {ans=a;return ;}
  int l=a,r=b;
  double mid=A[l].fs;
  int tempxh=A[l].xh;
  while(l<r){
    while(l<r && A[r].fs<=mid) r--;
    A[l].fs=A[r].fs;
    A[l].xh=A[r].xh;
  while(l<r && A[l].fs>=mid) l++;
    A[r].fs=A[l].fs;
    A[r].xh=A[l].xh;
  }
   A[l].xh=tempxh;
   A[l].fs=mid;
  if(l==k)ans=l;
  else if(l>k)qs(a,l-1);
  else qs(l+1,b);
}
int main(){
  cin>>n>>k;
  for(int i=1;i<=n;i++)
  {std::cin >> A[i].xh>>A[i].fs;}
  qs(1,n);
  std::cout <<A[ans].xh<<" " <<A[ans].fs <<" ";
  return 0;
}

4.sort

#include<iostream>
#include<algorithm>
using namespace std;
int n,a[500],ans[500],cnt=0;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]%2!=0)
		{
			ans[++cnt]=a[i];
		}
	}
	sort(ans+1,ans+cnt+1);
	for(int i=1;i<=cnt;i++)
	{
		if(i!=cnt)
	cout<<ans[i]<<",";
	else cout<<ans[i]<<"\n";
	}
	return 0;
}

5.归并加结构题

#include<iostream>
#include<cstring>
using namespace std;
struct student{
	char name[30];
	int fs;
}A[20],temp[20];
void m(int a,int b)
{
	if(b-a>1)
	{
		int mid=a+(b-a)/2;
		int l=a,r=mid,cnt=a;
		m(a,mid);
		m(mid,b);
		while(l<mid || r<b)
		{
			if(r>=b ||(l<mid && A[l].fs>=A[r].fs)) 
			{
				if(A[l].fs==A[r].fs&&strcmp(A[l].name,A[r].name)>0){student Temp;
				strcpy(Temp.name,A[l].name);
				strcpy(A[l].name,A[r].name);
				strcpy(A[r].name,Temp.name);
				}
				strcpy(temp[cnt].name,A[l].name);
				temp[cnt++].fs=A[l++].fs;
			}
			else{
				strcpy(temp[cnt].name,A[r].name);
				temp[cnt++].fs=A[r++].fs;
						}
		}
		for(int i=a;i<b;i++)
		{
			strcpy(A[i].name,temp[i].name);
			A[i].fs=temp[i].fs;
		}
	}
}
int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>A[i].name>>A[i].fs;
	}
	m(1,n+1);
	for(int i=1;i<=n;i++)
		{
		cout<<A[i].name<<" "<<A[i].fs<<"\n";
		}
	return 0;
}

6.结构体+sort的用法

#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct student{
	int chinese,math,English,total,n;
}A[310];
bool camp(student a,student b){
	if(a.total>b.total) return true;
	else if(a.total<b.total) return false;
	else{
		if(a.chinese>b.chinese) return true;
		else if(a.chinese<b.chinese) return false;
		else{
			if(a.n<b.n) return true;
			else return false;
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		A[i].n=i;
		cin>>A[i].chinese>>A[i].math>>A[i].English;
		A[i].total=A[i].chinese+A[i].math+A[i].English;
	}
	sort(A+1,A+n+1,camp);
	for(int i=1;i<=5;i++)
	{
		cout<<A[i].n<<" "<<A[i].total<<"\n";
	}
	return 0;
}

7.冒泡

#include<iostream>
using namespace std;
int n,m,id[10010],s[10010],lqrs=0,lqfs;
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>id[i]>>s[i];
	for(int i=0;i<n-1;i++)
		for(int j=0;j<n-1-i;j++)
		{
			if(s[j]<s[j+1])
			{
				swap(s[j],s[j+1]);
				swap(id[j],id[j+1]);
			}
			if(s[j]==s[j+1]){
			if(id[j]>id[j+1])
			{
				swap(s[j],s[j+1]);
				swap(id[j],id[j+1]);
			}
		}
	}
	m=double(m*1.5);
	lqfs=s[m-1];
	for(int i=0;i<n;i++){
		if(s[i]>=lqfs) ++lqrs;
		else break;
	}
	cout<<lqfs<<" "<<lqrs<<"\n";
	for(int i=0;i<lqrs;i++)
		cout<<id[i]<<" "<<s[i]<<"\n";
	return 0;
}

8.活用冒泡

#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int d[10]={0},j[10]={0},q,x=0,y=0;
	while(cin>>q)
	{
		if(q%2==0)d[x++]=q;
		else j[y++]=q;
	}
	for(int i=0;i<x-1;i++)
		for(int j=0;j<x-1-i;j++)
		{
			if(d[j]>d[j+1])
			swap(d[j],d[j+1]);
		}
	for(int i=0;i<y-1;i++)
			for(int q=0;q<y-1-i;q++)
			{
				if(j[q]<j[q+1])
				swap(j[q],j[q+1]);
			}
	for(int i=0;i<y;i++)cout<<j[i]<<" ";
	for(int i=0;i<x;i++)cout<<d[i]<<" ";
	return 0;
}

9.字符串加冒泡

#include<cstring>
#include<string>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n,q=0,p=0;
	double tall,man[110],girl[110];
	char sex[110];
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>sex>>tall;
		if(strcmp(sex,"male")==0)man[q++]=tall;
		else girl[p++]=tall;
	}
	for(int i=0;i<q-1;i++)
		for(int j=0;j<q-1-i;j++)
		{
			if(man[j]>man[j+1])
				swap(man[j],man[j+1]);
		}
	for(int i=0;i<p-1;i++)
		for(int j=0;j<p-1-i;j++)
		{
			if(girl[j]<girl[j+1])
				swap(girl[j],girl[j+1]);
		}
	for(int i=0;i<q;i++)printf("%.2lf ",man[i]);
	for(int i=0;i<p;i++)printf("%.2lf ",girl[i]);
	return 0;
}

10.结构体加冒泡

#include<cstring>
#include<string>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct ill{
	char ID[20];
	int age;
	int o;
}old[110],young[110],temp;
int main(){
	int n,k=0,p=0,q=0,d;
	char s[20];
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s>>d;
		k++;
		if(d>=60){
			strcpy(old[p].ID,s);
			old[p].age=d;
			old[p].o=k;
			p++;
		}
		else {
			strcpy(young[q].ID,s);
			young[q].age=d;
			young[q].o=k;
			q++;
		}
	}
	for(int i=0;i<p-1;i++)
		for(int j=0;j<p-1-i;j++)
		{
			if(old[j].age<old[j+1].age)
			{
				temp=old[j];
				old[j]=old[j+1];
				old[j+1]=temp;
			}
			else if(old[j].age==old[j+1].age&&old[j].o>old[j+1].o)
			{
				temp=old[j];
				old[j]=old[j+1];
				old[j+1]=temp;
			}
		}
	for(int i=0;i<q-1;i++)
			for(int j=0;j<q-1-i;j++)
			{
				if(young[j].o>young[j+1].o){
					temp=young[j];
					young[j]=young[j+1];
					young[j+1]=temp;
				}
			}
	for(int i=0;i<p;i++)cout<<old[i].ID<<"\n";
	for(int i=0;i<q;i++)cout<<young[i].ID<<"\n";
	return 0;
}

11.set

#include<iostream>
#include<set>
using namespace std;
int main(){
	int n,a[100];
	set<int>ans;
	cin>>n;for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		ans.insert(a[i]);
	}
	cout<<ans.size()<<"\n";
	for(set<int>::iterator it=ans.begin();it!=ans.end();it++)
	{
		cout<<*it<<" ";
	}
	return 0;
}

12.string加sort

#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	string a[110];
	int k=0;
	bool flag;
	while(cin>>a[k]){
		flag=false;
		for(int i=0;i<k;i++)
		{
			if(a[i].compare(a[k])==0)
			{
				flag=true;
				break;
			}
		}
		if(!flag)
			k++;
	}
	sort(a,a+k);
	for(int i=0;i<k;i++)cout<<a[i]<<"\n";
	return 0;
}

13.一些细节

#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a[110]={0};
	int n;
	bool flag=false;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int b;
		cin>>b;
		a[b+50]++;
	}
	for(int i=0;i<100;i++)
	{
		if(a[i]>=(n+1)>>1)
		{
			flag=true;
			cout<<i-50<<" ";
		}
	}
	if(!flag)
		cout<<"no"<<"\n";
	return 0;
}

14.字符串

#include<iostream>
#include<cstring>
using namespace std;
char word[30];
int temp[30],k=0,ans,Max=0;
int main(){
	cin>>word;
	k=strlen(word);
	for(int i=0;i<k;i++)
	{
		temp[word[i]-'a']++;
	}
	for(int i=0;i<26;i++)
	{
		if(temp[i]>Max)
		{
			ans=i;
			Max=temp[i];
		}
	}
	cout<<char('a'+ans)<<' '<<Max<<'\n';
	return 0;
}

luogu
1781.字符串排序

#include<string.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    string s;
    int l;
    int index;
}zt[110];
bool cmp(node a,node b){
    if(a.l>b.l) return 1;
    if(a.l==b.l)
    {
        if(a.s>b.s) return 1;
    }
     return 0;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>zt[i].s;
        zt[i].index=i;
        zt[i].l=zt[i].s.length();
    }
    sort(zt+1,zt+1+n,cmp);
    cout<<zt[1].index<<"\n"<<zt[1].s<<"\n";
    return 0;
}

数论学习笔记

一些废话基础

我们约定用\mathbb{Z}表示整数集,\mathbb{N}表示自然数集,最大公因数和最小公倍数分别用(a,b)[a,b]表示。
唯一分解定理:任一整数N(N>1)都可以唯一地分解为一组质数幂的乘积:
\displaystyle \prod_{k=1}^\infty {p_k}^{e_k}
其中e_k\in\mathbb{N}。我们称这个分解为N的标准分解。
N等价类:对于任意整数a和正整数b,存在唯一整数对(n,r)满足0 \leq r < ba = bn +r

加减乘除

( \left| a \right| , \left| b \right| ) = (a,b) = (b,a)
(a,0) = \left| a \right|
(a,b) = (a \pm b,b)
(na,nb) =n (a,b)
a \equiv b (\mod n)
对于任何\displaystyle a_1 \equiv b_1 (\mod n) \displaystyle a_2 \equiv b_2 (\mod n),无论彼此加减乘除还是整系数多项式都仍同余。
\displaystyle ac \equiv bc (\mod n)
只有当n,c互质时才可直接约掉c。即\displaystyle a \equiv b (\mod \frac{n}{(n,c)})

膜的新世界

完全剩余系:对于一个整数模n的余数,得到n个数的集合。
同余类:一组同余的集合。
缩剩余系\Phi_n:\displaystyle \Phi_n=c_1,c_2,\cdots,c_{\varphi (n)}
欧拉函数\varphi _(n):小于等于n且互质的正整数个数。
\displaystyle \varphi(x) = x\prod_{i=1}^n(1-\frac{1}{P_i})
P_i表示x的第i个质因子,且x \geqq 2,\in \mathbb{Z}。特殊的,\varphi(1)=1
费马小定理:\displaystyle a^{p-1} \equiv 1 (\mod p)
欧拉定理:(a,n)=0,满足
\displaystyle a^{\varphi (n)} \equiv 1 (\mod n)

欧几里得的游戏

辗转相除:\displaystyle (a,b)=(b, a \mod b)
裴蜀定理:扩展欧几里得是在计算最大公约数的同时找到x,y,使得ax + by =d
我们首先解\displaystyle ax + by =(a,b)
我们假设已经找到了一组解x^{‘} , y^{‘}使得
\displaystyle bx^{‘} + (a \mod b)y^{‘} = (b,a \mod b)
我们根据积可以知道这两代数式恒等。
因为
\displaystyle a \mod b = a -[\frac{a}{b}]b
所以化简得
\displaystyle ax+by=ay^{‘}+b(x^{‘}-[\frac{a}{b}]y^{‘})
最终
最终\displaystyle x = y^{‘},y = x^{‘} -[\frac{a}{b}]y^{‘}

后话

本文部分内容来自一些blog还有<<初等数论>>。
文中大多数简单的证明已匿去,如有需要可私信。

公式代码试用

a^2+b^2=c^2
a^2+b^2=c^2

  
#include<stdio.h>
using namespace std;
int main()
{
	puts("Hello,World");
}

Hello world!

Welcome to WordPress. This is your first post. Edit or delete it, then start writing!