跳了前 4 个。
E
题意：给你无限多个土豆，每个的质量是以 \(n\) 为循环节的循环数列，有一堆箱子，每个箱子可以装刚好大于等于的质量的土豆，\(Q\) 个询问，每次问第 \(k\) 个箱子装了多少个土豆。
就是不管第几个箱子，只要从循环数列中第 \(i\) 个开始装，那么之后的装法都是一样的，然后就是循环节。循环节长度不会大于 \(n\) 所以解决了。
求每个箱子装了多少个土豆用二分。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,Q;
const int maxn=200030;
ll W[maxn],w[maxn],vis[maxn],sum[maxn],cyc,st[maxn],ed[maxn];int idx[maxn];ll X;
int findpos(int p,int num)
{
num%=n;
if(num<=n-p+1) return p+num-1;
else return num-n+p-1;
}
ll calc(int p,int num)
{
ll ret=0;
if(num>=n) ret+=w[n]*(num/n);
num%=n;
if(num<=n-p+1) ret+=w[num+p-1]-w[p-1];
else ret+=w[n]-w[p-1]+w[num-n+p-1];
return ret;
}
ll solve(int p)
{
int l=1,r=1000000000,ans;
while(l<=r)
{
int mid=(l+r)>>1;
if(calc(p,mid)>=X) ans=mid,r=mid-1;
else l=mid+1;
}
ed[p]=findpos(p,ans);
return ans;
}
int main()
{
//freopen("p.in","r",stdin);
scanf("%d%d%lld",&n,&Q,&X);
for(int i=1;i<=n;i++)
{
scanf("%lld",&W[i]);
w[i]=w[i-1]+W[i];
}
int op=1;
while(!vis[op])
{
cyc++;
st[cyc]=op; idx[op]=cyc;
vis[op]=1; sum[op]=solve(op);
op=ed[op]%n+1;
}
int start=idx[op];
while(Q--)
{
ll K;scanf("%lld\n",&K);
if(K>=start) K=((K-start+1)%(cyc-start+1)==0?(cyc-start+1):(K-start+1)%(cyc-start+1))+start-1;
printf("%lld\n",sum[st[K]]);
}
}
F
题意：网格图，其中行号为 \(B\) 的整数次倍的行，和列号为 \(B\) 的整数次倍的列为大道，每走一单位长度耗时 \(1\) 否则耗时 \(K\)，给出起点和终点，求最小耗时。
枚举起点从上下左右哪个方向进入的大道，再枚举终点从上下左右哪个方向离开的大道。总共16种情况。还要再算上不走大道的耗时，取最小值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll B,K,sx,sy,gx,gy;
pair<ll,ll> solve(ll x,ll y,ll opt)
{
if(opt==1) x-=x%B;
if(opt==2) x+=B-(x%B);
if(opt==3) y-=y%B;
if(opt==4) y+=B-(y%B);
return make_pair(x,y);
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld%lld%lld%lld",&B,&K,&sx,&sy,&gx,&gy);
ll ans=abs(sx-gx)*K+abs(sy-gy)*K;
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)
{
pair<ll,ll> p,q;
p=solve(sx,sy,i); q=solve(gx,gy,j);
ll px,py,qx,qy,cnt=0;
px=p.first; py=p.second; qx=q.first; qy=q.second;
cnt=abs(sx-px)*K+abs(sy-py)*K+abs(gx-qx)*K+abs(gy-qy)*K;
if(px%B==0&&qx%B==0&&qy/B==py/B)
{
if(px!=qx)
cnt+=abs(px-qx)+min(qy%B+py%B,2*B-(qy%B+py%B));
else cnt+=abs(py-qy);
}
else if(py%B==0&&qy%B==0&&px/B==qx/B)
{
if(py!=qy)
cnt+=abs(py-qy)+min(px%B+qx%B,2*B-(px%B+qx%B));
else cnt+=abs(px-qx);
}
else cnt+=abs(px-qx)+abs(py-qy);
//fprintf(stderr,"(%lld,%lld) (%lld %lld) : %lld\n",px,py,qx,qy,cnt);
ans=min(ans,cnt);
}
}
printf("%lld\n",ans);
}
}
G
给个邻接矩阵，求三元环的数量。点数不超过 \(3000\)。
经典 bitset 板子。
就是把每个点能到达的其他点用 bitset存起来，然后枚举前两个点，第三个点的数量就是前两个点与起来之后 \(1\) 的数量。
#include <bits/stdc++.h>
using namespace std;
char s[3002][3002];int n;
bitset<3002> b[3002];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]+1);
for(int j=1;j<=n;j++)
if(s[i][j]=='1')
b[i][j]=1;
}
long long ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(s[i][j]=='1')
ans+=(b[i]&b[j]).count();
}
}
printf("%lld\n",ans/6ll);
}
H
奇妙转化。
假设前缀和数组为 \(c\)，那么它有一个奇妙的性质：相邻两数的奇偶性不同。
而且前缀和天生必须是单调递增的。
如果值域不太大的话就可以设这么个 DP
设 \(f_{i,0/1}\) 表示结尾的数字不超过 \(i\)，且这个数与 \(i\) 的奇偶性不相同或相同。
然后方程就是 \(f_{i,1}=f_{i-1,1}(i可选)+f_{i-1,0},f_{i,0}=f_{i-1,1}\)
然后发现可以矩乘，所以对于特殊的 \(i\) 不可选的点，就以他们为界，分成 \(n\) 段，然后对每一段矩阵快速幂。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll a[200030],S;
const int mod=998244353;
struct Martix
{
ll x[3][3];
Martix(){memset(x,0,sizeof(x));}
Martix operator *(const Martix &a)const{
Martix ret;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
ret.x[i][j]=(ret.x[i][j]+x[i][k]*a.x[k][j]%mod)%mod;
return ret;
}
};
Martix ksm(Martix x,ll y)
{
Martix ret; ret.x[0][0]=ret.x[1][1]=1;
while(y)
{
if(y&1) ret=ret*x;
x=x*x; y>>=1;
}
return ret;
}
int main()
{
scanf("%d%lld",&n,&S);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
Martix cur; cur.x[0][0]=1;
Martix b; b.x[0][0]=b.x[0][1]=b.x[1][0]=1;
for(int i=1;i<=n;i++)
{
Martix c=ksm(b,a[i]-a[i-1]-1);
cur=cur*c;
swap(cur.x[0][0],cur.x[0][1]);
}
Martix c=cur*ksm(b,S-a[n]-1);
printf("%lld\n",c.x[0][0]);
}
我模拟赛出完了。
有卡常题但是不想换了。
标签：int,qx,ll,qy,abs,ABC257,lld From： https://www.cnblogs.com/cc0000/p/16977126.html