反思
- 一定要看数据范围,参考,利用他估计复杂度,也要注意是否为负,是否取0的细节
- 预处理有时挺香的
- 哈希有时挺香的
题目简述
T1 置换
给出的代码部分最好直接复制粘贴,要不抄错爆零两行泪qaq(有一个模数是\(99824353\),只有一个\(4\),还好这次是复制的
然后暴力一位一位算可以拿到90分
给\(2s\)的话\(n=25\)要\(O(2^n)\)的算法才能过去,所以必须做到\(O(1)\)询问
考虑\(O(2^n)\)预处理,还是比较好想的
(以后一定要注意数据范围啊qaq瞎打肯定A不了题的
code:
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
int n,k,Seed;
int tmp,res;
int my_rand()
{
Seed=(214013LL*Seed+2531011)&((1<<k)-1);
return Seed;
}
int ans=0;
void my_hash(int x)
{
ans=((long long)ans*233+x)%99824353;
}
void print(int x)
{
for(int i=k-1;i>=0;i--)
{
if(x&(1<<i))putchar('1');
else putchar('0');
}
cout<<endl;
}
int rev[1<<25];
int main()
{
scanf("%d%d%d",&n,&k,&Seed);
ans=0;
for(int i=1;i<=(1<<k)-1;i++)
{
rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
//cout<<i<<' ';print(i);cout<<' ';print(rev[i]);cout<<endl;
}
//tmp=my_rand();
for(int i=1;i<=n;i++)
{
my_hash(rev[my_rand()]);
//print(tmp);cout<<' ';print(rev[tmp]);cout<<endl;
}
printf("%d",ans);
return 0;
}
T2 字符串
感觉前60分的数据有一点点水……把考场上\(hack\)掉的错解交上去照样60……
正解是哈希或者\(manacher\)
哈希:正反做哈希,然后枚举每一个位置,如果大于一半就查他到结尾那么长,否则查他到开头那么长,并需要右面拓展到的位置是已经记录的答案
code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define S 1000005
const ull base=11;
ull po[S];
char s[S];
void pp()
{
po[0]=1;
for(int i=1;i<=S;i++)po[i]=po[i-1]*base;
}
ull hf[S],hb[S];
ll len;
void gethash()
{
len=strlen(s+1);
hf[0]=hb[len+1]=0;
for(int i=1;i<=len;i++)hf[i]=hf[i-1]*base+(s[i]-'a');
for(int i=len;i>=1;i--)hb[i]=hb[i+1]*base+(s[i]-'a');
}
ull F(ll l,ll r)
{
return hf[r]-hf[l-1]*po[r-l+1];
}
ull B(ll l,ll r)
{
return hb[l]-hb[r+1]*po[r-l+1];
}
ll T;
ll ans[S];
ll vis[S];
ll cnt=0;
int main()
{
scanf("%lld",&T);
pp();
while(T--)
{
cnt=0;
memset(vis,0,sizeof vis);
scanf("%s",s+1);
gethash();
for(int i=len;i>len/2;i--)
{
//cout<<F(i,len)<<' '<<B(i*2-len,i)<<endl;
if(F(i,len)==B(i*2-len,i))
{
ans[++cnt]=i;
vis[i]=1;
}
}
for(int i=len/2;i>=1;i--)
{
if(vis[i*2-1])
{
//cout<<F(i,i*2-1)<<' '<<B(1,i)<<endl;
if(F(i,i*2-1)==B(1,i))
{
//cout<<i<<' '<<i*2-1<<endl;
ans[++cnt]=i;
vis[i]=1;
}
}
}
for(int i=cnt;i>=1;i--)printf("%lld ",ans[i]);
puts("");
}
return 0;
}
T3 饼干
考场上列了一个方程,然后想到了前几天的扩欧,然后不会了……
正解:有三种饼干:\(a,b,a+b\),如果放第三种,就相当于一个格子里同时放了前两种饼干,因此其实我们可以分开考虑,两种饼干的摆放是互不影响的
所以我们可以枚举饼干\(a\)的数量\(i\),看这时放适量的\(b\)是否能得到\(k\),如果可以,那么答案加上\(C_n^i\cdot C_n^{n-k\cdot i}\)(注意组合数里不能为负,且
这道题的\(n\)开到\(1e7\),线性求逆元耗时较长,可以先把阶乘求出来,再用费马小定理求阶乘逆元
注意数据范围,\(a,b,k\)都可能等于\(0\),所以这道题有很多细节要处理……
- a,b,k=0:随便放,答案为\(4^n\)
- a,b=0,k不为0:无解
- a,b中一个=0,k=0:只能放那个=0的,答案为\(2^n\)
- a,b中一个=0,k不为0:只能放那个不为0的,然后乘上另一个随便放的\(2^n\)种
- a,b都不为0,k=0:答案为\(1\)
- a,b,k都不为0:正常处理答案
code(仅供参考
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mod 998244353
#define N 10000005
ll n,a,b,k;
ll ans=0;
ll fac[N];
void pp()
{
fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
}
ll ksm(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll inv(ll x)
{
return ksm(x,mod-2);
}
ll C(ll n,ll m)
{
//cout<<n<<' '<<m<<' '<<fac[m]*ksm(n,mod-2)%mod*ksm(m-n,mod-2)%mod<<endl;
return fac[m]*inv(fac[n])%mod*inv(fac[m-n])%mod;
}
int main()
{
scanf("%lld%lld%lld%lld",&n,&a,&b,&k);
pp();
if(a==0||b==0)
{
if(a==0&&b==0)
{
if(k!=0)
{
puts("0");
return 0;
}
else
{
printf("%lld",ksm(4,n));
return 0;
}
}
if(k==0)
{
printf("%lld",ksm(2,n));
return 0;
}
if(b!=0)swap(a,b);
for(int i=0;i<=n;i++)
{
if(k-a*i<0)break;
if(k-a*i==0)
{
printf("%lld",C(i,n)*ksm(2,n)%mod);
return 0;
}
}
}
if(k==0)
{
printf("1");
return 0;
}
for(int i=0;i<=n;i++)
{
if((k-a*i)<0)break;
if((k-a*i)%b==0)
{
if((k-a*i)/b<=n)ans=(ans+C(i,n)*C((k-a*i)/b,n)%mod)%mod;//注意!
}
}
printf("%lld",ans);
return 0;
}
T4 空间宝石
考场上想骗\(S=1\)的\(20\)分,但是写挂了……
正解:\(floyd\)+矩阵运算+线段树(似乎还有倍增做法)
以后看到\(a_{i,j}=f(a_{i,k},a_{k,j})\)的时候应该往矩阵这块想
\(floyd\)的柿子跟这个就很为相似,所以可以用矩阵来转,重载下运算符就可以了(同学说这是套路,可能我见过的套路太少了吧qaq
注意:矩阵运算没有交换律,所以用线段树维护时一定要注意运算顺序(这块和线段树哈希有一点像
(为什么这几天天天写线段树啊qaq
读入以后,在每个优先级里跑\(floyd\),放进矩阵里
用线段树维护这些矩阵,不需要修改,每个叶子节点代表一个优先级的矩阵
注意到题中优先级是单调不减的,所以线段树查询运算的时候必须左在前,右在后
询问的时候把区间排序,然后建一个ans矩阵,把询问的区间依次“乘”进去,最后在得到的ans矩阵里直接查询就是最终答案了
几点注意:
- 传送门是单向边
- 可能有重边,所以读入时要取\(min\)
- 一共九个点,编号是\(0~8\)
code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define N 100005
#define P 2005
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define ls rt<<1
#define rs rt<<1|1
#define pll pair<ll,ll>
#define inf 100000000000
ll n,S;
ll p,u,v,w;
ll q;
ll z,t,s,ql,qr;
struct mat
{
ll a[9][9];
mat()
{
for(int i=0;i<9;i++)for(int j=0;j<9;j++)a[i][j]=inf;
for(int i=0;i<9;i++)a[i][i]=0;
}
mat operator*(mat b)
{
mat res;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
for(int k=0;k<9;k++)
{
res.a[i][j]=min(res.a[i][j],a[i][k]+b.a[k][j]);
}
}
}
return res;
}
void clear()
{
for(int i=0;i<9;i++)for(int j=0;j<9;j++)a[i][j]=inf;
for(int i=0;i<9;i++)a[i][i]=0;
}
void print()
{
for(int i=0;i<9;i++){for(int j=0;j<9;j++)cout<<a[i][j]<<' ';cout<<endl;}cout<<endl;
}
}tr[P<<2],dis[P],ans;
void up(ll rt)
{
tr[rt]=tr[ls]*tr[rs];
}
void build(ll rt,ll l,ll r)
{
if(l==r)
{
tr[rt]=dis[l];
//tr[rt].print();
return;
}
ll m=(l+r)>>1;
build(lson);
build(rson);
up(rt);
}
mat query(ll rt,ll l,ll r,ll nl,ll nr)
{
if(nl<=l&&r<=nr)
{
return tr[rt];
}
ll m=(l+r)>>1;
if(m>=nl&&m<nr)return query(lson,nl,nr)*query(rson,nl,nr);
else if(m>=nl)return query(lson,nl,nr);
else if(m<nr)return query(rson,nl,nr);
}
ll mxp=0;
vector<pll >g;
bool cmp(pll a,pll b)
{
if(a.first!=b.first)return a.first<b.first;
else return a.second<b.second;
}
int main()
{
freopen("owo.in","r",stdin);
//cout<<inf<<endl;
scanf("%lld%lld",&n,&S);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld%lld%lld",&p,&u,&v,&w);
dis[p].a[u][v]=min(dis[p].a[u][v],w);
//dis[p].a[v][u]=min(dis[p].a[v][u],w);
mxp=max(mxp,p);
}
for(int l=1;l<=mxp;l++)
{
for(int k=0;k<9;k++)
{
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
dis[l].a[i][j]=min(dis[l].a[i][j],dis[l].a[i][k]+dis[l].a[k][j]);
}
}
}
}
build(1,1,mxp);
scanf("%lld",&q);
for(int i=1;i<=q;i++)
{
scanf("%lld%lld%lld",&z,&t,&s);
g.clear();
ans.clear();
for(int j=1;j<=s;j++)
{
scanf("%lld%lld",&ql,&qr);
g.push_back(make_pair(ql,qr));
}
sort(g.begin(),g.end(),cmp);
for(int j=0;j<s;j++)
{
//cout<<g[j].first<<' '<<g[j].second<<endl;
ans=ans*query(1,1,mxp,g[j].first,g[j].second);
//for(int k=0;k<9;k++){for(int l=0;l<9;l++)cout<<ans.a[i][j]<<' ';cout<<endl;}
}
if(ans.a[z][t]!=inf)printf("%lld\n",ans.a[z][t]);
else puts("-1");
}
return 0;
}
前几天学的\(vector\)和\(pair\)派上用场了,的确很好用啊qaq