暑假集训CSP提高模拟12
\(T1\) P171. 黑客 \(40pts\)
-
将式子进行二维差分。
-
考虑枚举 \(\frac{i+j}{\gcd(i,j)}=t\) ，并统计它能对答案产生的贡献。令 \(\gcd(i,j)=1\) ，这样的话才会不重不漏。
-
推式子，有 \(\begin{aligned} &\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\frac{i+j}{\gcd(i,j)} \le 999] \times \frac{i+j}{\gcd(i,j)} \\ &=\sum\limits_{t=2}^{\min(n+m,999)}\sum\limits_{i=max(t-m,1)}^{\min(t-1,n)}[\gcd(i,t-i)=1] \sum\limits_{k=1}^{\min(\left\lfloor \frac{n}{i} \right\rfloor,\left\lfloor \frac{m}{t-i} \right\rfloor)}t \end{aligned}\) 。
点击查看代码
const ll p=1000000007; ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } ll ask(ll n,ll m) { ll ans=0; for(ll t=2;t<=min(n+m,999ll);t++) { for(ll i=max(t-m,1ll);i<=min(t-1,n);i++) { if(gcd(i,t-i)==1) { ans=(ans+t*min(n/i,m/(t-i))%p)%p; } } } return ans; } int main() { ll a,b,c,d; cin>>a>>b>>c>>d; cout<<(ask(b,d)-ask(a-1,d)-ask(b,c-1)+ask(a-1,c-1)+2*p)%p<<endl; return 0; }
\(T2\) P133. 密码技术 \(0pts\)
-
不难发现，行的交换并不会影响列的交换，列的交换并不会影响行的交换。
-
暴力处理出能互相交换的行和列，并将其看作连通块，并查集维护大小。
-
最终，各连通块大小的阶乘的乘积即为所求。
点击查看代码
const ll p=998244353; ll a[100][100],jc[100]; struct DSU { ll fa[100],siz[100]; void init(ll n) { for(ll i=1;i<=n;i++) { fa[i]=i; siz[i]=1; } } ll find(ll x) { return (fa[x]==x)?x:fa[x]=find(fa[x]); } void merge(ll x,ll y) { x=find(x); y=find(y); if(x!=y) { fa[y]=x; siz[x]+=siz[y]; siz[y]=0; } } }D; bool check1(ll x,ll y,ll n,ll k) { for(ll i=1;i<=n;i++) { if(a[x][i]+a[y][i]>k) { return false; } } return true; } bool check2(ll x,ll y,ll n,ll k) { for(ll i=1;i<=n;i++) { if(a[i][x]+a[i][y]>k) { return false; } } return true; } int main() { ll n,k,ans=1,i,j; cin>>n>>k; jc[0]=1; for(i=1;i<=n;i++) { jc[i]=jc[i-1]*i%p; for(j=1;j<=n;j++) { cin>>a[i][j]; } } D.init(n); for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { if(check1(i,j,n,k)==true) { D.merge(i,j); } } } for(i=1;i<=n;i++) { ans=ans*jc[D.siz[i]]%p; } D.init(n); for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { if(check2(i,j,n,k)==true) { D.merge(i,j); } } } for(i=1;i<=n;i++) { ans=ans*jc[D.siz[i]]%p; } cout<<ans<<endl; return 0; }
\(T3\) P151. 修水管 \(0pts\)
\(T4\) P163. 货物搬运 \(20pts\)
-
观察到 \(a_{i},k \le n\) 且强制在线，启示我们从值域入手。
-
分块
- 考虑分块，设 \(cnt_{i,j}\) 表示 \(j\) 在 \(i\) 中出现的次数，整块仅有首尾两个元素发生了改变，散块则需要实现任意位置插入和删除，首段散块多了一个元素，尾端散块少了一个元素，使用
deque和list维护即可。 - 块长取 \(\sqrt{n}\) 。
点击查看代码
int a[100010],pos[100010],L[330],R[330],cnt[330][100010],klen,ksum; deque<int>q[330]; void init(int n) { klen=sqrt(n); ksum=n/klen; for(int i=1;i<=ksum;i++) { L[i]=R[i-1]+1; R[i]=R[i-1]+klen; } if(R[ksum]<n) { ksum++; L[ksum]=R[ksum-1]+1; R[ksum]=n; } for(int i=1;i<=ksum;i++) { for(int j=L[i];j<=R[i];j++) { pos[j]=i; q[i].push_back(a[j]); cnt[i][a[j]]++; } } } void update(int l,int r) { if(pos[l]==pos[r]) { ll x=q[pos[l]][r-L[pos[l]]]; q[pos[l]].erase(q[pos[l]].begin()+(r-L[pos[l]])); q[pos[l]].insert(q[pos[l]].begin()+(l-L[pos[l]]),x); } else { q[pos[l]].insert(q[pos[l]].begin()+(l-L[pos[l]]),q[pos[r]][r-L[pos[r]]]); cnt[pos[l]][q[pos[r]][r-L[pos[r]]]]++; cnt[pos[r]][q[pos[r]][r-L[pos[r]]]]--; q[pos[r]].erase(q[pos[r]].begin()+(r-L[pos[r]])); for(int i=pos[l]+1;i<=pos[r];i++) { q[i].push_front(q[i-1].back()); cnt[i][q[i-1].back()]++; cnt[i-1][q[i-1].back()]--; q[i-1].pop_back(); } } } int query(int l,int r,int k) { int ans=0; if(pos[l]==pos[r]) { for(int i=l;i<=r;i++) { ans+=(q[pos[l]][i-L[pos[l]]]==k); } } else { for(int i=l;i<=R[pos[l]];i++) { ans+=(q[pos[l]][i-L[pos[l]]]==k); } for(int i=pos[l]+1;i<=pos[r]-1;i++) { ans+=cnt[i][k]; } for(int i=L[pos[r]];i<=r;i++) { ans+=(q[pos[r]][i-L[pos[r]]]==k); } } return ans; } int main() { int n,m,pd,l,r,k,ans=0,i; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; } init(n); cin>>m; for(i=1;i<=m;i++) { cin>>pd>>l>>r; l=(l+ans-1)%n+1; r=(r+ans-1)%n+1; if(l>r) { swap(l,r); } if(pd==1) { update(l,r); } else { cin>>k; k=(k+ans-1)%n+1; ans=query(l,r,k); cout<<ans<<endl; } } return 0; } - 考虑分块，设 \(cnt_{i,j}\) 表示 \(j\) 在 \(i\) 中出现的次数，整块仅有首尾两个元素发生了改变，散块则需要实现任意位置插入和删除，首段散块多了一个元素，尾端散块少了一个元素，使用
总结
- 赛时历程：溜了一眼题后， \(T1,T2,T3\) 都不太可做， \(T4\) 一眼数据结构且有思路。开场直接开 \(T4\) ，敲暴力时因为不会用
vector的erase和insert单独又开了个程序实验了一下，想了 \(1h\) 就想出了线段树套平衡树的高级做法，莫名自信告诉我区间修改可以差分，区间查询实际上是单点查询（查询区间和查询点搞混了），主席树代码并不长，一会儿就码完了，调代码时因为终端有延迟导致以为大样例过了的代码其实没过，中间有一份代码是过大样例了的但跑了 \(2.3s\) ，卡常和调空间（空间很紧张）途中测了发小样例直接 \(WA\) 了，然后就开始四处乱调。一直持续到 \(9:40\) ，突然意识到差分的做法是假的，此刻我主席树的复杂度甚至不如暴力，赛后发现交的代码 \(RE\) 了，心态崩了。然后开始写树套树，因还觉得差分有一定正确性所以先写的树状数组套主席树，发现没过样例后开始写线段树套主席树，觉得 \(O(n \log^{2}n)\) 的时间复杂度加上主席树的巨大常数估计过不去，这还没有算空间复杂度的影响。 \(10:30\) 弃了 \(T4\) ，把暴力交上去了。然后开始写 \(T1,T2,T3\) 的部分分，部分分不会打后又滚回去打 \(T4\) 的线段树套主席树了，发现还要线段树合并，这样的话空间复杂度就假了，心态又崩了。尝试写 \(T1\) ，推出式子后仅剩 \(3\min\) 了。赛后发现 \(T3\) 读假题了。 - \(T1\)
- 由于惯性思维，直接就往莫反上想了，最后才想到利用 \(x+y \in [0,999]\) 的性质。
- \(T2\)
- 因为着急所以没发现行、列间不会相互影响。
- \(T3\)
- 被题面绕晕了。
- \(T4\)
- 以为最终得到的差分数组的前缀和能直接转化到主席树的前缀关系上，说明对差分的本质认识不清。
- 赛时假的思路
- 操作 \(1\) 本质上是将现 \([l,r)\) 中的数的前缀中原 \(a_{r}\) 的出现次数加一，现 \(l\) 的前缀原 \(a_{l}\) 的出现次数少一。
- 对每个位置开一棵权值线段树，为节省空间使用主席树代替。
- 区间修改和区间查询的话外层套线段树维护即可。