7.4LGJ测试
T1
排队打水，经典贪心题，尽量让打水时间少的人在前面打水。
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1010;
ll n,m,a[N],ans,t[N];
int main()
{
scanf("%lld %lld",&n,&m);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
sort(a+1,a+n+1);
for(ll i=1;i<=n;i++)
{
ans=ans+t[i%m]+a[i];
t[i%m]+=a[i];
}
printf("%lld\n",ans);
return 0;
}
T2
考察扩欧，因为左闭右开的区间有点麻烦，我们可以将开始时间定为\(1\)，最后再将答案减\(1\)，我们发现\(y\)和\(q\)很小，我们可以枚举\(y\)和\(q\)代表在车停在\(B\)站的第\(i\)秒的下车，清醒的第\(j\)秒，可以列出不定方程：\(a(2x+2y)+x+i=b(p+q)+p+j\)
转换一下变成\(b(p+q)-a(2x+2y)=x+i-p-j\)
若\(x=i-p-j|gcd(2x+2y,p+q)\)，则求出最小的正整数\(b\)，再取\(min(ans,b(p+q)+p+j)\)即可
否则枚举下一组\(y,q\)，若都不满足，则输出\(infinity\)
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll G,x,y,p,q;
ll d,an1,an2;
bool flag=false;
void exgcd(ll a,ll b)
{
if(b==0)
{
d=a;
an1=1;
an2=0;
return ;
}
exgcd(b,a%b);
ll tzy=an2;
an2=an1-(a/b)*an2;
an1=tzy;
}
ll t1,t2,t3,t4;
ll ans;
int main()
{
scanf("%lld",&G);
while(G--)
{
scanf("%lld %lld %lld %lld",&x,&y,&p,&q);
if(x==p)
{
printf("%lld\n",x);
continue;
}
exgcd(p+q,2*x+2*y);
flag=false;
for(ll i=1;i<=y;i++)
{
for(ll j=1;j<=q;j++)
{
if(p+j==x+i)
{
if(flag) ans=min(ans,p+j-1);
else ans=p+j-1;
flag=true;
continue;
}
t1=x+i-p-j;
if(t1%d!=0) continue;
t2=an1,t3=an2;
t2=t2*(t1/d),t3=t3*(t1/d);
t4=t2/((2*x+2*y)/d);
t2=t2-t4*((2*x+2*y)/d);
t3=t3+t4*((p+q)/d);
if(t2<0) t2=t2+((2*x+2*y)/d),t3=t3-((p+q)/d);
if(flag) ans=min(ans,(p+q)*t2+p+j-1);
else ans=(p+q)*t2+p+j-1;
flag=true;
}
}
if(flag) printf("%lld\n",ans);
else puts("infinity");
}
return 0;
}
T3
原题传送门
一个很经典的\(trick\)：将边权转化为点权，一个点的点权为所有与该点的相连的边的异或和
如果这么做，那么如果选择两个点\(u,v\)，将以两个点为端点的链异或\(x\)，那么改变点权的点只有\(u,v\)，他们新的点权等于原来的点权异或\(x\)，那么原来的问题就改变成了每次选择两个点，将两个点的点权都异或\(x\)，求所有点的点权变为\(0\)的最小操作数
如果两个点的点权一样，直接都异或成\(0\)，这样绝对是最优的。
那么剩下的点的点权两两不相同，因为点权很小，只有\(16\)个，考虑状压DP：\(f_i\)表示剩余状态为\(i\)全都变成\(0\)的最少操作数：
\(1\)、\(f_i\)的值为\(i\)中\(1\)的个数减一
\(2\)、若\(i\)的状态包含\(j\)，\(f_i=min(f_i,f_j+f_{i\wedge j})\)
\(3\)、若\(i\)的状态中的点权异或和不为\(0\)，\(f_i\)为\(INF\)
一个小\(trick\)：若\(i\)的状态包含\(j\)
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+50,M=(1<<15);
ll n,u,v,w,ans,re;
ll a[N],gs[20],f[M],can[M];
int main()
{
scanf("%lld",&n);
for(ll i=1;i<n;i++)
{
scanf("%lld %lld %lld",&u,&v,&w);
a[u]^=w;
a[v]^=w;
}
for(ll i=0;i<n;i++)
gs[a[i]]++;
for(ll i=1;i<=15;i++)
ans=ans+gs[i]/2,re=(re|((gs[i]&1)<<(i-1)));
for(ll i=1;i<M;i++) f[i]=f[i>>1]+(i&1);
for(ll i=1;i<M;i++) f[i]--;
for(ll i=1;i<M;i++)
for(ll j=1;j<=15;j++)
if(((1<<(j-1))&i)!=0) can[i]^=j;
for(ll i=1;i<M;i++)
{
if(can[i]!=0) continue;
for(ll j=((i-1)&i);j;j=((j-1)&i))
if(can[j]==0) f[i]=min(f[i],f[j]+f[i^j]);
}
printf("%lld\n",ans+f[re]);
return 0;
}
T4
有一个\(h\)行\(w\)列的二维棋盘，棋子可以攻击同一行内且距离不超过\(d\)的棋子。
你可以在棋盘放任意多个棋子，但任意两个棋子都不能相互攻击。
问有多少种不同的方案，答案模\(100003\)。
限制只在行，分行列考虑，算出每一行的方案，最后用快速幂就可以了
设\(f_i\)表示第\(i\)个位置放棋子，后面都不放的方案数，有
定义\(s_i=\sum\limits_{j=0}^if_j=s_{i-1}+f_j=s_{i-1}+s_{max(j-d-1,0)}\)
我们要求\(s_w\)
但是因为数据范围有点大，我们可以考虑优化，下面介绍阈值分治：
\(1\)、若\(d\leq 100\)，考虑矩阵快速幂优化，因为\(s_0=1\)，所以初始矩阵全定\(1\)即可，全都表示\(s_0\)
\(2\)、若\(d\geq 100\)，考虑组合数优化，考虑将\(1-w\)全都向右移动\(d\)位，然后就会有\(s_{1-d}=1\)，从\(s_{d+1}\)开始计算，这样我们就可以将原式解释成从\(0\)开始跳，要么跳\(1\)步，要么跳\(d+1\)步，求跳到\(w+d\)的位置的方案数，枚举跳多少次\(d+1\)步，剩余全为跳\(1\)步，然后乘组合数即可
\(tips:\)因为组合数较大，而模数为质数且较小，考虑卢卡斯定理
证明：
考虑\(\dbinom{p}{n}\bmod p\)取值，\(\dbinom{n}{m}\bmod p=\dfrac{p!}{n!(p-n)!}\)，分子在质因子分解中\(p\)的次数恰好为\(1\)，因此只有当\(n=0\)或\(n=p\)时分母中含有\(p\)，因此\(\dbinom{p}{n}\bmod p=[n=0\vee n=p]\)，进而可以得出
考虑二项式\((1+x)^n \bmod p\)，那么\(\dbinom{n}{m}\)就是求其在\(x^m\)的取值。使用上述引理，我们可以得到
注意前者只有在\(p\)的倍数位置才有取值，而后者最高次项为\(n\bmod p \le p-1\)，因此这两部分的卷积在任何一个位置只有最多一种方式贡献取值，即在前者部分取\(p\)的倍数次项，后者部分取剩余项，即
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=100003,N=100500;
ll d,h,w,m,ans;
ll sum[N],inv[N];
ll an1,an2;
ll ksm(ll ds,ll zs)
{
ll base=1;
while(zs)
{
if(zs&1) base=(base*ds)%mod;
ds=(ds*ds)%mod;
zs=zs/2;
}
return base;
}
ll C(ll x,ll y)
{
if(x<y) return 0;
if(y==0||x==y) return 1;
ll re=sum[x];
re=re*inv[x-y]%mod;
re=re*inv[y]%mod;
return re;
}
void exgcd(ll a,ll b)
{
if(b==0)
{
an1=1;
an2=0;
return ;
}
exgcd(b,a%b);
ll tzy=an2;
an2=an1-(a/b)*an2;
an1=tzy;
}
void init()
{
sum[0]=1;
for(ll i=1;i<=mod;i++)
{
sum[i]=(sum[i-1]*i)%mod;
exgcd(sum[i],mod);
inv[i]=(an1%mod+mod)%mod;
}
}
struct jgt
{
ll a[110][110];
}A,B,dw;
jgt operator *(const jgt t1,const jgt t2)
{
jgt t3=dw;
for(ll i=1;i<=d+1;i++)
for(ll j=1;j<=d+1;j++)
for(ll k=1;k<=d+1;k++)
t3.a[i][j]=(t3.a[i][j]+t1.a[i][k]*t2.a[k][j]%mod)%mod;
return t3;
}
void jzksm(ll zs)
{
while(zs)
{
if(zs&1) A=A*B;
B=B*B;
zs=zs/2;
}
}
int main()
{
scanf("%lld %lld %lld",&d,&h,&w);
init();
if(d<=100)
{
for(ll i=1;i<=d+1;i++)
for(ll j=1;j<=d+1;j++)
dw.a[i][j]=0;
for(ll i=1;i<=d+1;i++)
A.a[1][i]=1;
for(ll i=1;i<=d;i++)
B.a[i][i+1]=1;
B.a[d+1][d+1]=1;
B.a[d+1][1]=1;
jzksm(w);
ans=A.a[1][d+1];
}
else
{
m=w+d;
for(ll i=0;i<=m/(d+1);i++)
ans=(ans+C((m-i*d)/mod,i/mod)*C((m-i*d)%mod,i%mod))%mod;
}
ans=ksm(ans,h);
printf("%lld\n",ans-1);
return 0;
}