前言
- 比赛链接。
这次和高中一起打的，排名一次比一次低了，差点出前一半了……
主要是 T1 \(dijkstra\) 唐氏复杂度打假了，T2 挂分，T3 没想出来压位，T4 题都没看。
T1 最短路
本题考察对 \(Floyed\) 的理解，\(Floyed\) 数组在没有优化之前实际是有三维的，\(f_{k,i,j}\) 表示从 \(i\) 到 \(j\) 的路径中只可能经过 \(1\sim k\) 作为中转点时的最短路，也就是说不可能以 \(k+1\sim n\) 为中转点，其中 \(k\) 这一维可以省略。
那么将 \(k\) 这一维按照点权从小到大排序，于是有 \(a_k=\max\limits_{i=1}^k\{a_i\}\)，所以对于 \(f_{k,i,j}\)，其路径最大点权为 \(\max(a_i,a_j,a_k)\)。
可以开两个数组 \(f,g\) 分别表示只计算边权和包括点权的，于是有：
\[\begin{cases} f_{i,j}=\min\limits_{k=1}^n\{f_{i,k}+f_{k,j}\} \\ g_{i,j}=\min\limits_{k=1}^n\{f_{i,k}+f_{k,j}+max(a_i,a_j,a_k)\} \end{cases}\]\(g_{s,t}\) 即为所求。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=310,M=1e4+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');}
void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);}
int n,m,q,f[N][N],g[N][N],a[N];
struct aa {int a,id;}e[N];
bool cmp(aa a,aa b) {return a.a<b.a;}
signed main()
{
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
read(n),read(m),read(q);
for(int i=1;i<=n;i++)
read(e[i].a),e[i].id=i,a[i]=e[i].a;
memset(f,0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
for(int i=1;i<=n;i++) f[i][i]=0,g[i][i]=a[i];
for(int i=1,x,y,z;i<=m;i++)
read(x),read(y),read(z),
f[x][y]=f[y][x]=min(f[x][y],z),
g[x][y]=g[y][x]=f[x][y]+max(a[x],a[y]);
sort(e+1,e+1+n,cmp);
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
if(i!=e[k].id)
for(int j=1;j<=n;j++)
{
if(i==j||e[k].id==j) continue;
g[i][j]=min(g[i][j],f[i][e[k].id]+f[e[k].id][j]+max({e[k].a,a[i],a[j]}));
f[i][j]=min(f[i][j],f[i][e[k].id]+f[e[k].id][j]);
}
for(int i=1,s,t;i<=q;i++)
read(s),read(t),
write(g[s][t]>=0x7f7f7f7f7f?-1:g[s][t]),puts("");
}
T2
-
部分分 \(100pts\)，唐氏做法：
这是一个舍弃部分正确性换取复杂度的做法，在随机的大数据下几乎不可能卡掉，小数据下极容易死，但是小数据可以暴力冲过去。
对于大数据，现在预处理时符合答案的直接结束，以增加部分正确性。
只考虑正方形的答案，之后二分边长即可。
复杂度 \(O(n^2\log(n))\)。
考虑到学校 OJ 数据向来比较水且没有捆绑，可以通过此题。
然后赛时加了点优化想增加点正确性，结果挂了 \(60pts\)。点击查看代码
#include<bits/stdc++.h> #define int long long #define endl '\n' #define sort stable_sort using namespace std; const int N=2010; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');} void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);} int n,k,a[N][N],sum[N][N]; bool check(int mid) { int x1=1,y1=1,x2=mid,y2=mid,minn=0x7f7f7f7f,nowx=0,nowy=0; while(x2<=n&&y2<=n) { int ans=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]; if(ans>=k&&ans<=2*k) { cout<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<endl; exit(0); } minn=min(minn,ans); if(y2==n) { x2++,y2=mid; x1=x2-mid+1,y1=y2-mid+1; nowy=0; } else { y2++; x1=x2-mid+1,y1=y2-mid+1; } } return minn<k; } signed main() { freopen("matrix.in","r",stdin); freopen("matrix.out","w",stdout); read(n),read(k); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { read(a[i][j]); if(a[i][j]>=k&&a[i][j]<=2*k) { cout<<i<<' '<<j<<' '<<i<<' '<<j<<endl; return 0; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]; if(sum[i][j]>=k&&sum[i][j]<=2*k) { cout<<1<<' '<<1<<' '<<i<<' '<<j<<endl; return 0; } } if(n<=200) { for(int x2=1;x2<=n;x2++) for(int y2=1;y2<=n;y2++) for(int x1=1;x1<=x2;x1++) for(int y1=1;y1<=y2;y1++) { int ans=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]; if(ans>=k&&ans<=2*k) { cout<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<endl; return 0; } } puts("-1"); return 0; } int l=1,r=n; while(l<=r) { int mid=(l+r)>>1; if(check(mid)) l=mid+1; else r=mid-1; } puts("-1"); } -
正解：
暂无。
T3 数组
-
部分分 \(20pts\)：暴力。
-
部分分 \(10pts\)：对于没有修改的操作，主席树，详见 BZOJ4026 dC Loves Number Theory。
-
正解：
和主席树的思想一样，根据公式 \(\varphi(n)=n\prod\limits_{p\in\mathbb{p},p|n}\frac{p-1}{p}\)，只需要处理出区间 \([l,r]\) 的乘积和其所包含的质因数即可。
根据 \(a_i,x\le 300\)，所以只可能有 \(62\) 个质因数，考虑压成一个 \(01\) 串，类似状压处理。
让后赛时虽然看到了 \(300\) 的数据范围但是想他乘上好几次数值就极大了，但是没有想到他乘多少次质因数也是 \(\le 300\) 的，于是没有想到状压，就很唐。
需要略微卡常，提前处理出每个 \(c_i=\dfrac{prime_i-1}{prime_i}\)，不然在本就常数巨大的线段树上再在每次输出再加一个 \(\log(1e9)\) 简直是雪上加霜。
复杂度理论上 \(O(n\log(n))\)。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort #define f t[p] #define ls p<<1 #define rs p<<1|1 using namespace std; const int N=1e5+10,P=1e9+7; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } void wt(int x){if(x>9)wt(x/10);putchar((x%10)+'0');} void write(int x){if(x<0)putchar('-'),x=~x+1;wt(x);} int n,m,a[N],tot,prime[N],c[N]; bool vis[N]; void pre() { vis[1]=1; for(int i=2;i<=300;i++) if(vis[i]==0) { prime[++tot]=i; for(int j=2;j<=300/i;j++) vis[i*j]=1; } } ll qpow(ll a,ll b) { ll ans=1; for(;b;b>>=1) { if(b&1) (ans*=a)%=P; (a*=a)%=P; } return ans; } struct aa { int l,r; ll val,add=1,pri,lazy; }t[N<<2]; void pushup(int p) { f.val=t[ls].val*t[rs].val%P; f.pri=t[ls].pri|t[rs].pri; } void build(int p,int l,int r) { f.l=l,f.r=r; if(l==r) { f.val=a[l]; for(int i=1;i<=tot&&prime[i]<=a[l];i++) if(a[l]%prime[i]==0) f.pri|=(1ll<<(i-1)); return ; } int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r); pushup(p); } void spread(int p) { if(f.add==1&&f.lazy==0) return ; ll &x=f.add,&y=f.lazy; (t[ls].val*=qpow(x,t[ls].r-t[ls].l+1))%=P,(t[ls].add*=x)%=P; (t[rs].val*=qpow(x,t[rs].r-t[rs].l+1))%=P,(t[rs].add*=x)%=P; t[ls].pri|=y,t[ls].lazy|=y; t[rs].pri|=y,t[rs].lazy|=y; x=1,y=0; } void change(int p,int l,int r,ll d) { if(l<=f.l&&r>=f.r) { (f.val*=qpow(d,f.r-f.l+1))%=P; (f.add*=d)%=P; ll dis=0; for(int i=1;i<=tot&&prime[i]<=d;i++) if(d%prime[i]==0) dis|=(1ll<<(i-1)); f.pri|=dis; f.lazy|=dis; return ; } spread(p); int mid=(f.l+f.r)>>1; if(l<=mid) change(ls,l,r,d); if(r>mid) change(rs,l,r,d); pushup(p); } aa ask(int p,int l,int r) { if(l<=f.l&&r>=f.r) return f; spread(p); int mid=(f.l+f.r)>>1; aa ans; ans.val=1,ans.pri=0; if(l<=mid) { aa x=ask(ls,l,r); (ans.val*=x.val)%=P; ans.pri|=x.pri; } if(r>mid) { aa x=ask(rs,l,r); (ans.val*=x.val)%=P; ans.pri|=x.pri; } return ans; } signed main() { freopen("array.in","r",stdin); freopen("array.out","w",stdout); pre(); for(int i=1;i<=tot;i++) c[i]=(prime[i]-1)*(qpow(prime[i],P-2))%P; read(n),read(m); for(int i=1;i<=n;i++) read(a[i]); build(1,1,n); for(int i=1,op,l,r,d;i<=m;i++) { read(op),read(l),read(r); if(op==1) read(d),change(1,l,r,d); else { aa ans=ask(1,l,r); ll val=ans.val; ll sta=ans.pri; for(int j=1;j<=tot;j++) if((sta>>(j-1))&1) val=val*c[j]%P; write(val),puts(""); } } }
T4 树
暂时还没打。
标签：val,rs,int,void,2024,暑假,ans,集训,define From： https://www.cnblogs.com/Charlieljk/p/18299249