【比賽記錄】2025CSP-S模擬賽22
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 80 | 0 | 15 | - | 95 | 7/21 |
A. 草莓列車(train)
我們需要 \(O(1)\) 修改的數(shù)據(jù)結(jié)構(gòu)，這讓我們聯(lián)想到考慮把 ST 表倒過來做。于是做法就很顯然了，將修改區(qū)間拆成兩個(gè)區(qū)間賦值，最后再 \(O(n\log n)\) 下傳即可。
剩下的全在代碼里了：
Code
SB 數(shù)據(jù) a 根本不是 1e5，m 也根本不是 1e7
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define ui unsigned int
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,T,Log[maxn];
ui st[maxn][22];
namespace Maker{
ui x0,seed;
il void init() {cin>>x0>>seed;}
il ui getnum(){
x0=(x0<<3)^x0;
x0=((x0>>5)+seed)^x0;
return x0;
}
}
int main(){
// system("fc train2.out my.out");
// freopen("train2.in","r",stdin);
// freopen("my.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>T;
for(int i=2;i<=n;i++){
Log[i]=Log[i>>1]+1;
}
// for(int i=1;i<=n;i++){
// cout<<Log[i]<<" ";
// }
// puts("");
for(int i=1;i<=n;i++){
cin>>st[i][0];
}
Maker::init();
for(int i=1; i<=m; ++i){
int l=Maker::getnum()%n+1,r=Maker::getnum()%n+1;
ui v=Maker::getnum();
if(l>r) swap(l,r);
if(T==1) l=1;
int p=Log[r-l+1];
ui &t1=st[l][p],&t2=st[r-(1<<p)+1][p];
t1=max(t1,v),t2=max(t2,v);
}
for(int j=Log[n];j;j--){
for(int i=1;i+(1<<j)-1<=n;i++){
ui &t1=st[i][j-1],&t2=st[i+(1<<(j-1))][j-1];
t1=max(t1,st[i][j]),t2=max(t2,st[i][j]);
}
}
for(int i=1;i<=n;i++){
cout<<st[i][0]<<" ";
}
return 0;
}
}
int main(){return asbt::main();}
B. 草莓路徑(path)
C. 草莓城市(city)
考慮二分，注意到此時(shí)對(duì)于每個(gè)點(diǎn)都有四種狀態(tài)，于是這是一個(gè) 4-sat 問題。進(jìn)一步發(fā)現(xiàn)這四個(gè)三角形都是由兩個(gè)小三角形組成的，也就是左上的小三角形和右下的選一個(gè)，左下的和右上的選一個(gè)，于是變成 2-sat 問題。
于是此時(shí)問題變?yōu)槿绾闻袛鄡蓚€(gè)三角形是否相交。可以想到一個(gè)充要條件是至少有兩條邊相交（當(dāng)然此時(shí)有 bug，如果兩個(gè)三角形重合那么會(huì)被判作不相交，這種情況特判即可）。那么這個(gè)其實(shí)是簡單的，如果線段 \(AB\) 與線段 \(CD\) 相交，那么有：
\[(\overrightarrow{AB}\times\overrightarrow{AC})\cdot(\overrightarrow{AB}\times\overrightarrow{AD})<0\land(\overrightarrow{CD}\times\overrightarrow{CA})\cdot(\overrightarrow{CD}\times\overrightarrow{CB})<0
\]
也就是說，\(C\) 和 \(D\) 分布在 \(AB\) 的兩側(cè)。于是遍歷三角形的邊即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e3+5;
const double eps=1e-4;
int n,m,kk,xx[205],yy[205],tot,hao[205][2][2];
int cnt,top,scn,dfn[maxn],low[maxn],stk[maxn],scc[maxn];
bool ins[maxn];
vector<int> e[maxn];
struct vec{
double x,y,z;
vec(double x=0,double y=0,double z=0):x(x),y(y),z(z){}
il vec operator+(const vec &p)const{
return vec(x+p.x,y+p.y,z+p.z);
}
il vec operator-(const vec &p)const{
return vec(x-p.x,y-p.y,z-p.z);
}
il double operator^(const vec &p)const{ // 點(diǎn)乘
return x*p.x+y*p.y+z*p.z;
}
il vec operator*(const vec &p)const{ // 叉乘
return vec(y*p.z-z*p.y,z*p.x-x*p.z,x*p.y-y*p.x);
}
};
struct sjx{
vec a,b,c;
il bool xj(const sjx &p)const{
#define xj(a1,b1,a2,b2) ((((a2-a1)*(b1-a1))^((b2-a1)*(b1-a1)))<0&&(((a1-a2)*(b2-a2))^((b1-a2)*(b2-a2)))<0)
return xj(a,b,p.a,p.b)||xj(a,b,p.b,p.c)||xj(a,b,p.c,p.a)||xj(b,c,p.a,p.b)||xj(b,c,p.b,p.c)||xj(b,c,p.c,p.a)||xj(c,a,p.a,p.b)||xj(c,a,p.b,p.c)||xj(c,a,p.c,p.a);
#undef xj
}
}dyk[205][2][2];
il void tarjan(int u){
dfn[u]=low[u]=++cnt,stk[++top]=u,ins[u]=1;
for(int v:e[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
int v=0;
scn++;
do{
v=stk[top--];
ins[v]=0,scc[v]=scn;
}while(v!=u);
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>kk;
for(int i=1;i<=kk;i++){
cin>>xx[i]>>yy[i];
hao[i][0][0]=++tot; // 左上
hao[i][0][1]=++tot; // 右下
hao[i][1][0]=++tot; // 左下
hao[i][1][1]=++tot; // 右上
}
double l=0,r=1e9;
while(r-l>eps){
double mid=(l+r)/2,t=mid/2;
for(int i=1;i<=kk;i++){
dyk[i][0][0].a=dyk[i][0][1].a=dyk[i][1][0].a=dyk[i][1][1].a=vec(xx[i],yy[i]);
dyk[i][0][0].b=dyk[i][1][0].b=vec(xx[i]-t,yy[i]);
if(xx[i]-t<0){
e[hao[i][0][0]].pb(hao[i][0][1]);
e[hao[i][1][0]].pb(hao[i][1][1]);
}
dyk[i][0][1].b=dyk[i][1][1].b=vec(xx[i]+t,yy[i]);
if(xx[i]+t>n){
e[hao[i][0][1]].pb(hao[i][0][0]);
e[hao[i][1][1]].pb(hao[i][1][0]);
}
dyk[i][0][0].c=dyk[i][1][1].c=vec(xx[i],yy[i]+t);
if(yy[i]+t>m){
e[hao[i][0][0]].pb(hao[i][0][1]);
e[hao[i][1][1]].pb(hao[i][1][0]);
}
dyk[i][0][1].c=dyk[i][1][0].c=vec(xx[i],yy[i]-t);
if(yy[i]-t<0){
e[hao[i][0][1]].pb(hao[i][0][0]);
e[hao[i][1][0]].pb(hao[i][1][1]);
}
}
for(int i=1;i<=kk;i++){
for(int j=i+1;j<=kk;j++){
if(xx[i]==xx[j]&&yy[i]==yy[j]){
for(int x:{0,1}){
for(int y:{0,1}){
e[hao[i][x][y]].pb(hao[j][x][y^1]);
e[hao[j][x][y]].pb(hao[i][x][y^1]);
}
}
}
for(int x1:{0,1}){
for(int y1:{0,1}){
for(int x2:{0,1}){
for(int y2:{0,1}){
if(dyk[i][x1][y1].xj(dyk[j][x2][y2])){
e[hao[i][x1][y1]].pb(hao[j][x2][y2^1]);
e[hao[j][x2][y2]].pb(hao[i][x1][y1^1]);
}
}
}
}
}
}
}
cnt=top=scn=0;
for(int i=1;i<=tot;i++){
if(!dfn[i]){
tarjan(i);
}
}
for(int i=1;i<=kk;i++){
for(int j:{0,1}){
if(scc[hao[i][j][0]]==scc[hao[i][j][1]]){
r=mid;
goto togo;
}
}
}
l=mid;
togo:;
for(int i=1;i<=tot;i++){
dfn[i]=low[i]=scc[i]=ins[i]=0;
e[i].clear();
}
}
printf("%.2f",l);
return 0;
}
}
int main(){return asbt::main();}
D. 草莓之歌(easy)
設(shè) \(f_{i,j}\) 表示 \(i\) 為第 \(j\) 段的末尾的最小交換次數(shù)，考慮從 \(f_{k,j-1}\) 到 \(f_{i,j}\) 的轉(zhuǎn)移，我們需要將第 \(k+1\) 到第 \(i\) 個(gè) \(B\) 都移動(dòng)到第 \(i\) 個(gè) \(A\) 后面，于是有轉(zhuǎn)移：\(f_{i,j}=\min_{k=0}^{i-1}f_{k,j-1}+\sum_{x=k+1}^{i}\max(a_x-k,0)\)，其中 \(a_x\) 表示第 \(x\) 個(gè) \(A\) 前面 \(B\) 的數(shù)量。看到要求分 \(k\) 段這樣的限制，不妨考慮 wqs 二分，可以發(fā)現(xiàn) \(f_{i,j}\) 關(guān)于 \(j\) 是一個(gè)下凸函數(shù)。于是 DP 變成 \(f_i=f_j-mid+\sum_{k=j+1}^{i}\max(a_k-j,0)\)。設(shè) \(b_j\) 表示 \(j\) 右邊第一個(gè)滿足 \(a_k\ge j\) 的 \(k\)，再給 \(a\) 做個(gè)前綴和，于是轉(zhuǎn)移變成 \(f_i=f_j+sa_i-sa_{b_j-1}-j\times(i-b_j+1)-mid\)，斜率優(yōu)化即可。時(shí)間復(fù)雜度線性對(duì)數(shù)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lwrb lower_bound
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e6+5;
int n,m,tot,cnt,a[maxn],b[maxn],f[maxn],g[maxn],q[maxn];
string s;
vector<int> c[maxn];
il bool check(int x){
int hd=1,tl=0;
#define X(i) (i)
#define Y(i) (f[i]-a[b[i]-1]+i*b[i]-i)
#define K(i,j) ((Y(j)-Y(i))*1.0l/(X(j)-X(i)))
for(int i=1;i<=n;i++){
for(int j:c[i]){
while(hd<tl&&K(q[tl-1],q[tl])>K(q[tl],j)){
tl--;
}
q[++tl]=j;
}
while(hd<tl&&K(q[hd],q[hd+1])<i){
hd++;
}
f[i]=f[q[hd]]+a[i]-a[b[q[hd]]-1]-q[hd]*(i-b[q[hd]]+1)-x;
g[i]=g[q[hd]]+1;
}
#undef X
#undef Y
#undef K
return g[n]<=m;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>s;
s=" "+s;
for(int i=1;i<=n<<1;i++){
if(s[i]=='A'){
a[++cnt]=tot;
}
else{
tot++;
}
}
for(int i=0;i<=n;i++){
b[i]=lwrb(a+i+1,a+n+1,i)-a;
c[b[i]].pb(i);
}
for(int i=1;i<=n;i++){
a[i]+=a[i-1];
}
int l=-1e12,r=0;
while(l<r){
int mid=(l+r+1)>>1;
if(check(mid)){
l=mid;
}
else{
r=mid-1;
}
}
check(l);
// cout<<l<<'\n';
cout<<f[n]+m*l;
return 0;
}
}
signed main(){return asbt::main();}
浙公網(wǎng)安備 33010602011771號(hào)