【比赛】CSP提高组模拟1
和初三学长们一起打的比赛，被人家爆杀了。
T1 最短路 20Pts
原题 Cow Toll Paths G。
正解是按点权排序后跑一遍 Floyd，歪解是多迭代几遍。
赛时没开 long long \(80 \to 20\)。
点击查看代码
#include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=305;
pii a[N][N];
int n,m,v[N],x,y,q,s,t,w;
main(){
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)a[i][j]={0,0};
else a[i][j]={0x3f3f3f3f3f3f3f3f,0};
}
}
for(int i=1;i<=n;i++)cin>>v[i];
for(int i=1;i<=m;i++){
cin>>x>>y>>w;
w=min(w,a[x][y].first);
a[x][y].first=a[y][x].first=w;
a[x][y].second=a[y][x].second=max(v[x],v[y]);
}
int T=3;
while(T--)
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
if(i==k)continue;
for(int j=1;j<=n;j++){
if(j==k||i==j)continue;
if(a[i][j].first+a[i][j].second>a[i][k].first+a[k][j].first+max(a[i][k].second,a[k][j].second)){
a[i][j].first=a[i][k].first+a[k][j].first;
a[i][j].second=max(a[i][k].second,a[k][j].second);
}
}
}
}
while(q--){
cin>>x>>y;
if(a[x][y].first==0x3f3f3f3f3f3f3f3f)cout<<"-1\n";
else cout<<a[x][y].first+a[x][y].second<<"\n";
}
return 0;
}
T2 方格取数 40Pts
原题 KUP-Plot purchase。
首先判掉在 \([k,2k]\)（直接输出） 和 \((2k,+\infty)\)（一定不选）的数，剩下的数就都在 \((1,k-1)\) 之间了；
此时如果我们能找出一个总和大于 \(2k\) 的矩阵，那么一定有解，因为其一定包括了一个总和在 \([k,2k]\) 之间的矩阵。
所以我们先找出一个总和大于 \(2k\) 的极大矩阵，然后每次删去一行，如果这一行的和大于 \(k\) 就在这一行中一个一个删，否则继续在大矩阵中进行。
单调栈找最大矩阵即可。
赛时想到了单调栈，但是没打出来，随机化 40。
点击查看代码
#include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
const int N=2005;
int n,k,a[N][N],sum[N][N],l[N][N],r[N][N],s[N][N],mp[N][N];
int get(int x,int y,int xx,int yy){
return sum[xx][yy]-sum[x-1][yy]-sum[xx][y-1]+sum[x-1][y-1];
}
main(){
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
if(a[i][j]>=k&&a[i][j]<=k*2){
cout<<i<<" "<<j<<" "<<i<<" "<<j;
return 0;
}
else mp[i][j]=(a[i][j]<k);
sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mp[i][j])s[i][j]=s[i-1][j]+1;
else s[i][j]=0;
}
}
for(int i=1;i<=n;i++){
stack<int> ss;
for(int j=1;j<=n+1;j++){
while(!ss.empty()&&s[i][j]<s[i][ss.top()]){
r[i][ss.top()]=j-1;
ss.pop();
}
ss.push(j);
}
while(!ss.empty())ss.pop();
for(int j=n;j>=0;j--){
while(!ss.empty()&&s[i][j]<s[i][ss.top()]){
l[i][ss.top()]=j+1;
ss.pop();
}
ss.push(j);
}
for(int j=1;j<=n;j++){
int now=get(i-s[i][j]+1,l[i][j],i,r[i][j]);
if(now>=k){
if(now<=k*2){
cout<<i-s[i][j]+1<<" "<<l[i][j]<<" "<<i<<" "<<r[i][j];
return 0;
}
else{
for(int h=l[i][j]+1;h<=r[i][j];h++){
int noww=sum[i][h]-sum[i][l[i][j]-1];
if(noww>=k&&noww<=2*k){
cout<<i<<" "<<l[i][j]<<" "<<i<<" "<<h;
return 0;
}
}
}
}
}
}
cout<<-1;
return 0;
}
T3 数组 0Pts
原题 Please, another Queries on Array?。
对于欧拉函数，有式子 \(\varphi(x)=x \ \cdot \ \prod_{i=1}^n\limits (\frac{p_i-1}{p_i})\)，其中 \(p_i\) 为 \(x\) 的所有质因数。
区间积可以用线段树维护，难点在于质因子的维护。
通过一些技术手段，我们发现，在 300 以内只有 62 个质因子，刚好可以用一个 long long 来状压。
同样丢到线段树里即可。
赛时因为 1<<62 爆零了。
1<<62 \(\to\) 1ll<<62 \(0 \to 100\)
点击查看代码
#include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
const int N=4e5+5;
int n,a[N],l,r,x,q;
string op;
int prim[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293};
inline int qp(int a,int b,int mod=mod){
int ans=1;
while(b){
if(b&1)ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
inline int getp(int x){
int p=0;
for(int i=0;i<62;i++){
if(x%prim[i]==0)p|=(1ll<<i);
}
return p;
}
struct tree{
int l,r,mul,lzm;
int p,lzp;
int len(){return r-l+1;}
}t[N<<2];
void pushup(int k){
t[k].mul=t[k<<1].mul*t[k<<1|1].mul%mod;
t[k].p=t[k<<1].p|t[k<<1|1].p;
}
void build(int k,int l,int r){
t[k]={l,r,a[l],1};
if(l==r){
int p=getp(a[l]);
t[k].p=p;t[k].lzp=0;
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
pushup(k);
}
void pushdown(int k){
if(t[k].lzm!=1){
t[k<<1].mul=t[k<<1].mul*qp(t[k].lzm,t[k<<1].len())%mod;
t[k<<1].lzm=t[k<<1].lzm*t[k].lzm%mod;
t[k<<1|1].mul=t[k<<1|1].mul*qp(t[k].lzm,t[k<<1|1].len())%mod;
t[k<<1|1].lzm=t[k<<1|1].lzm*t[k].lzm%mod;
t[k].lzm=1;
}
if(t[k].lzp!=0){
t[k<<1].p|=t[k].lzp;
t[k<<1].lzp|=t[k].lzp;
t[k<<1|1].p|=t[k].lzp;
t[k<<1|1].lzp|=t[k].lzp;
t[k].lzp=0;
}
}
void update(int k,int l,int r,int val,int p){
if(l<=t[k].l&&t[k].r<=r){
t[k].mul=t[k].mul*qp(val,t[k].len())%mod;
t[k].lzm=t[k].lzm*val%mod;
t[k].p|=p;
t[k].lzp|=p;
return;
}
pushdown(k);
int mid=(t[k].l+t[k].r)>>1;
if(l<=mid)update(k<<1,l,r,val,p);
if(r>mid)update(k<<1|1,l,r,val,p);
pushup(k);
}
pii query(int k,int l,int r){
if(l<=t[k].l&&t[k].r<=r){
return {t[k].mul,t[k].p};
}
pushdown(k);
int mid=(t[k].l+t[k].r)>>1;
pii ans={1,0};
if(l<=mid){
pii L=query(k<<1,l,r);
ans.first=ans.first*L.first%mod;
ans.second|=L.second;
}
if(r>mid){
pii R=query(k<<1|1,l,r);
ans.first=ans.first*R.first%mod;
ans.second|=R.second;
}
return ans;
}
int inv[500];
main(){
freopen("array.in","r",stdin);
freopen("array.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
for(int i=1;i<=400;i++)inv[i]=qp(i,mod-2);
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
while(q--){
cin>>op;
if(op=="1"){
cin>>l>>r>>x;
int p=getp(x);
update(1,l,r,x,p);
}
else{
cin>>l>>r;
pii tmp=query(1,l,r);
int ans=tmp.first,p=tmp.second;
for(int i=0;i<62;i++){
if((p>>i)&1){
ans=ans*(prim[i]-1)%mod*inv[prim[i]]%mod;
}
}
cout<<ans<<"\n";
}
}
return 0;
}
T4 树 30Pts
原题 ODW。
根号分治。
设块长为 \(T\)。
预处理出步长为 \([1,\sqrt T]\) 时每个点向上跳到根的点权和以及每个点的 \(1 \backsim \sqrt T\)
大于 \(T\) 则暴力跳，否则树上差分。
这题数据很水，暴力有 70，能过除了链以外的所有点；加个对链的暴力就过了。
但赛时树剖 LCA 打锅了导致 \(100 \to 30\)
后记
还是学到了很多的，也确实是技不如人。
之后要注意代码细节问题，尽量不要在不该挂的地方挂分。