A. 李时珍的皮肤衣
看不出规律就打表
点击查看代码
#include <bits/stdc++.h>
#define ll __int128
using namespace std;
long long n;
void p(ll x)
{
if(!x)return;
p(x/10);
cout<<int(x%10);
}
ll qpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)ans=ans*a%n;
a=a*a%n;
b>>=1;
}
return ans;
}
int main()
{
freopen("lsz.in","r",stdin);
freopen("lsz.out","w",stdout);
cin>>n;
ll pp=(qpow(2,n-1)+1+n)%n;
if(!pp)cout<<0;
else p(pp);
return 0;
}
B. 马大嘴的废话
首先如果用hash话会T
Hash
#include <bits/stdc++.h>
#define ll long long
#define ull long long
using namespace std;
const int N =1e4+5,B=233;
int n,m,len[N];ull ha[N][25],p[25];
string s,x;
void get(int d)
{
len[d]=s.size();
for(int i=1;i<=len[d];i++)
{
ha[d][i]=ha[d][i-1]*B+s[i-1];
}
}
ull Hash(int l,int r,int i)
{
return ha[i][r]-ha[i][l-1]*p[r-l+1];
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
freopen("mdz.in","r",stdin);
freopen("mdz.out","w",stdout);
cin>>n;
p[0]=1;
for(int i=1;i<=20;i++)p[i]=p[i-1]*B;
for(int i=1;i<=n;i++)
{
cin>>s;
get(i);
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>x;
ull has=0;
int l=x.size();
for(int i=1;i<=l;i++)
{
has=has*B+x[i-1];
}
int ans=0;
for(int j=1;j<=n;j++)
{
if(len[j]<l)continue;
else
{
for(int st=1;st<=len[j]-l+1;st++)
{
if(Hash(st,st+l-1,j)==has)
{
ans++;
break;
}
}
}
}
cout<<ans<<endl;
}
return 0;
}
我们可以考虑字典树,如何在树中插入呢，当输入一个字符串时，不能只插入一个整串，这样不方便查找，必须把这个字符串的子串插入，方便查找,用一个数组同步记录每个字符出现次数
然后需要用数组记录一下当前子串属于那个整串，防止记重
优化后
#include <bits/stdc++.h>
#define ll long long
#define ull long long
using namespace std;
const int N =1e4+5,B=233;
int n,m;int son[N*50][27],num[N*50][27],cnt=1;int vis[N*50][27];
string s,x;
void insert(const string &s,int id)
{
int len=s.size()-1,now=1;
for(int i=0;i<=len;i++)
{
int ch=s[i]-'a';
if(!son[now][ch])
{
son[now][ch]=++cnt;
vis[now][ch]=id;
num[now][ch]++;
}else
{
if(vis[now][ch]!=id)num[now][ch]++,vis[now][ch]=id;
}
now=son[now][ch];
}
}
int query(const string &s)
{
int len=s.size()-1,now=1;
int ans=0;
for(int i=0;i<=len;i++)
{
int ch=s[i]-'a';
if(!son[now][ch])
{
return 0;
}
ans=num[now][ch];
now=son[now][ch];
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
freopen("mdz.in","r",stdin);
freopen("mdz.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s;
int len=s.size()-1;
for(int k=0;k<=len;k++)
{
string tmp=s.substr(k,len-k+1);
insert(tmp,i);
}
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>x;
cout<<query(x)<<endl;
}
return 0;
}
/*
*/
D. 清理牛棚
用DP
E. 历史研究
- 开longlong
- 注意细节
- 要离散化
先说分块的做法,首先分块，按块预先处理处每个元素出现次数的前缀和,然后预先处理处i~j块之间的答案编号
查询时,我们用桶记录出现次数与重要度的乘积,散块暴力,整块直接出答案(记的加上分块中的)，然后比较哪个最大即可
点击查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N =1e5+5;
int n,q,sq,st[500],en[500],belong[N],tot,ans[500][500];
ll b[N],a[N],cnt[500][N];map <ll,int> mp;
void init()
{
sq=sqrt(n);
for(int i=1;i<=sq;i++)
{
st[i]=n/sq*(i-1)+1;
en[i]=n/sq*i;
}
en[sq]=n;
for(int i=1;i<=sq;i++)
{
for(int j=st[i];j<=en[i];j++)
{
belong[j]=i;
}
}
for(int i=1;i<=sq;i++)
{
for(int j=1;j<=n;j++)cnt[i][j]=cnt[i-1][j];
for(int j=st[i];j<=en[i];j++)
{
cnt[i][a[j]]++;
}
}
ll res=0,id=0;
for(int i=1;i<=sq;i++)
{
for(int j=i;j<=sq;j++)
{
ans[i][j]=ans[i][j-1];
res=b[ans[i][j]]*(cnt[j][ans[i][j]]-cnt[i-1][ans[i][j]]);
id=ans[i][j-1];
for(int k=st[j];k<=en[j];k++)
{
int p=a[k];
if(res<b[p]*(cnt[j][p]-cnt[i-1][p]))
{
res=b[p]*(cnt[j][p]-cnt[i-1][p]);
id=p;
}
}
ans[i][j]=id;
}
}
}
ll tong[N];
ll query(int l,int r)
{
ll Ans=0;
if(belong[l]==belong[r])
{
for(int i=l;i<=r;i++)
{
tong[a[i]]+=b[a[i]];
Ans=max(Ans,tong[a[i]]);
}
for(int i=l;i<=r;i++)tong[a[i]]=0;
}else
{
int res=ans[belong[l]+1][belong[r]-1];
for(int i=l;i<=en[belong[l]];i++)
{
if(!tong[a[i]]&&a[i]!=res)
{
tong[a[i]]+=b[a[i]]*(cnt[belong[r]-1][a[i]]-cnt[belong[l]][a[i]]);
}
tong[a[i]]+=b[a[i]];
Ans=max(tong[a[i]],Ans);
}
for(int i=st[belong[r]];i<=r;i++)
{
if(!tong[a[i]]&&a[i]!=res)
{
tong[a[i]]+=b[a[i]]*(cnt[belong[r]-1][a[i]]-cnt[belong[l]][a[i]]);
}
tong[a[i]]+=b[a[i]];
Ans=max(tong[a[i]],Ans);
}
Ans=max(Ans,(tong[res]+(cnt[belong[r]-1][res]-cnt[belong[l]][res])*b[res]));
for(int i=l;i<=en[belong[l]];i++)tong[a[i]]=0;
for(int i=st[belong[r]];i<=r;i++)tong[a[i]]=0;
}
return Ans;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen("lsyj_ex.in","r",stdin);
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(!mp[a[i]])
{
mp[a[i]]=++tot;
b[tot]=a[i];
}
a[i]=mp[a[i]];
}
// for(int i=1;i<=n;i++)
// {
// cout<<a[i]<<" ";
// }
// cout<<endl;
int l,r;
init();
for(int i=1;i<=q;i++)
{
cin>>l>>r;
cout<<query(l,r)<<endl;
}
return 0;
}
/*
5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4
*/