PAM

发表于 2020-03-17 | 更新于 2020-03-18 | 评论数：

Luogu 3649(注意一下所有回文串个数是咋统计的)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=300005;
char s[N];
ll fa[N],len[N],size[N],ch[N][30],cnt=1,last,ans;
int addnode(int x)
{
	cnt++;
	len[cnt]=x;
	return cnt;
}
void add(int pos,int c)
{
	int u=last;//取出last 
	while(s[pos-len[u]-1]!=s[pos]) u=fa[u]; 
	if(!ch[u][c])
	{
		int now=addnode(len[u]+2);
		int v=fa[u];
		while(s[pos-len[v]-1]!=s[pos]) v=fa[v];
		fa[now]=ch[v][c];
		ch[u][c]=now;
	}
	last=ch[u][c];size[last]++;
}
int main()
{
	fa[0]=1,fa[1]=0;
	len[1]=-1,len[0]=0;
	scanf("%s",s+1);
	ll lenn=strlen(s+1); 
	for(int i=1;i<=lenn;i++) add(i,s[i]-'a');
	for(int i=cnt;i;i--) size[fa[i]]+=size[i],ans=max(ans,len[i]*size[i]);
	printf("%lld",ans);
}

Luogu 4287(注意一下你要知道遍历fail边就是遍历以这个字符为后缀的所有回文串)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500005;
char s[N];
int fa[N],len[N],size[N],ch[N][30],cnt=1,last,ans,pre[N][30],mk[N],re[30],L[N];
int addnode(int x)
{
	cnt++;
	len[cnt]=x;
	return cnt;
}
void add(int pos,int c)
{
	ll u=last;//??last 
	while(s[pos-len[u]-1]!=s[pos]) u=fa[u]; 
	if(!ch[u][c])
	{
		ll now=addnode(len[u]+2);
		ll v=fa[u];
		while(s[pos-len[v]-1]!=s[pos]) v=fa[v];
		fa[now]=ch[v][c];
		ch[u][c]=now;
		if(len[now]%4==0)
		{
			int pp=len[now]/2;
			int ree=L[pos-pp],f=0;
			while(1)
			{
				if(ree==0||ree==1)
				break;
				if(len[ree]==pp)
				{
					f=1;
					break;
				}
				ree=fa[ree];
			}
			if(f) ans=max(ans,len[now]);
		}
//		cout<<now<<" "<<mk[now]<<endl;
	}
	last=ch[u][c];size[last]++,L[pos]=last;
}
int main()
{
	fa[0]=1,fa[1]=0;
	len[1]=-1,len[0]=0;
	ans=0;
	int nn;
	scanf("%d",&nn);
	scanf("%s",s+1);
	ll lenn=strlen(s+1); 
	for(int i=1;i<=lenn;i++) add(i,s[i]-'a');
	printf("%d",ans);
}

JSK Colorful String (https://nanti.jisuanke.com/t/41389)
直接暴力啊，记录一个前缀和数组直接暴力找每个串的不同字符然后记录,因为只有26个小写字母

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=400005;
char s[N];
ll fa[N],len[N],size[N],ch[N][30],cnt=1,last,ans,pre[N][30],mk[N],re[30];
int addnode(int x)
{
	cnt++;
	len[cnt]=x;
	return cnt;
}
void add(int pos,int c)
{
	ll u=last;//??last 
	while(s[pos-len[u]-1]!=s[pos]) u=fa[u]; 
	if(!ch[u][c])
	{
		ll now=addnode(len[u]+2);
		ll v=fa[u];
		while(s[pos-len[v]-1]!=s[pos]) v=fa[v];
		fa[now]=ch[v][c];
		ch[u][c]=now;
		ll jk=0;
		for(int j=0;j<26;j++) re[j]=pre[pos][j]-pre[pos-len[now]][j];
		for(int j=0;j<26;j++) if(re[j]>0) jk++;
		mk[now]=jk;
//		cout<<now<<" "<<mk[now]<<endl;
	}
	last=ch[u][c];size[last]++;
}
int main()
{
	fa[0]=1,fa[1]=0;
	len[1]=-1,len[0]=0;
	ans=0;
	scanf("%s",s+1);
	ll lenn=strlen(s+1); 
	for(int i=1;i<=lenn;i++)
	{
		for(int j=0;j<26;j++) pre[i][j]=pre[i-1][j];
		pre[i][s[i]-'a']++;
	}
	for(int i=1;i<=lenn;i++) add(i,s[i]-'a');
	for(int i=cnt;i;i--) size[fa[i]]+=size[i];
	for(int i=2;i<=cnt;i++) ans+=size[i]*mk[i];
	printf("%lld",ans);
}

一些三分的模板见解

发表于 2020-03-06 | 评论数：

三分的话就是二分多了一点变化，首先要保证三分的东西是具有凸函数性质的，就像二分的东西具有单调性一样.
然后就是整数和浮点了，这里的话板子上是有一些区别的，浮点的话用eps去比，整数缩两边的边界
浮点板子

#include <bits/stdc++.h>
using namespace std;
double a[100005];
int n;
double f(double x)
{
	double ans=0;
	double re=x;
	for(int i=n;i;i--)
	ans+=x*a[i],x*=re;
	ans+=a[n+1];
	return ans;
}
int main()
{
	double l,r,eps=1e-5;
	cin>>n>>l>>r;
	for(int i=1;i<=n+1;i++) cin>>a[i];
	for(int i=1;i<=100;i++)
	{
		double mid=(l+r)/2.0;
		if(f(mid+eps)>f(mid-eps)) l=mid;
		else r=mid;
	}
	printf("%.5f",l);
}

整数板子

#include <bits/stdc++.h>
using namespace std;
long long a[1000005],k,ans=LLONG_MAX;
long long n;
long long f(long long x)
{
	long long ans=0;
	for(int i=1;i<=n;i++) ans+=llabs(x-a[i]),x+=k;
	return ans;
}
int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	sort(a+1,a+1+n);
	long long l=-1000000000000L,r=1000000000000L;
	for(int i=0;i<100;i++)
	{
		long long len=r-l;
		if(f(l+len/3)<f(r-len/3)) ans=min(ans,f(l+len/3)),r-=len/3;
		else l+=len/3,ans=min(ans,f(r-len/3));
	}
	printf("%lld",ans);
}

CF 1288C Two Arrays

发表于 2020-01-17 | 评论数：

N个数里面抽2M个数可以重复有多少种抽法
(n+m-1,n)这个东西可以背过
原先不重复就是(n,m)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll c[2005][2005],mod=ll(1e9)+7;
int main()
{
	c[0][0]=1;
	for(int i=1;i<=2000;i++)
	for(int j=0;j<=i;j++)
	c[i][j]=c[i-1][j-1]%mod+c[i-1][j]%mod,c[i][j]%=mod;
	ll n,m;
	cin>>n>>m;
	cout<<c[n+2*m-1][2*m];
}

CF1285D Dr. Evil Underscores

发表于 2020-01-17 | 评论数：

题目大意是给你一个数列长度为N 1e5 然后让你找到任意一个X使得所有的数异或他之后最大的数最小
3
1 2 3
2
X=3
实际上这个有个规律就是如果当前位数都是1或者都是0那么分组两边再寻找，因为这样可以避免这一位出现，之后如果01都存在那么这一位一定有，那么返回min

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> a;
ll ans(vector<ll> a,ll cur)
{
	if(cur<0) return 0;
	vector<ll> l,r;
	for(auto &i:a) if((i>>cur)&1) l.push_back(i);
	else r.push_back(i);
	if(l.size()==0) return ans(r,cur-1);
	if(r.size()==0) return ans(l,cur-1);
	return min(ans(l,cur-1),ans(r,cur-1))+(1<<cur);
}
int main()
{
	ios::sync_with_stdio(0);
	ll n;
	cin>>n;
	a.resize(n);
	for(auto &i:a) cin>>i;
	cout<<ans(a,30);
}

CodeForces 976E(贪心)

发表于 2020-01-14 | 评论数：

题目大意是给定N个随从的生命与攻击，a张牌能够让生命值翻倍，b张牌能够让生命值与攻击力交换，问最终的场攻和为多少？
首先我们要按照hp-dmg降序排列，然后要知道如果要让场攻最大，那么心火一定是把所有的加在一个随从上，但是这个随从未知。我们算出前k个交换的场攻变化然后枚举心火给谁即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k,sum,ans,jk;
struct node
{
	ll hp,dmg,m;
}a[200005];
bool cmp(node a,node b)
{
	return a.m>b.m;
}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m>>k;
	k=min(k,n);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].hp>>a[i].dmg;
		a[i].m=max(0LL,a[i].hp-a[i].dmg);
		sum+=a[i].dmg;	
	}	
	if(!k) cout<<sum;
	else
	{
		sort(a+1,a+1+n,cmp);
		for(int i=1;i<=k;i++) jk+=a[i].m;
		for(int i=1;i<=n;i++) ans=max(ans,(jk-a[i<=k?i:k].m+(a[i].hp<<m)-a[i].dmg));
		cout<<sum+ans;
	}
}

baccano

一个蒟蒻的小家

RSS