“山大地纬杯”第十二届山东省ICPC大学生程序设计竞赛部分个人题解
2022/5/26 1:51:16
本文主要是介绍“山大地纬杯”第十二届山东省ICPC大学生程序设计竞赛部分个人题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
A - Seventeen
显然\(n=1,2,3\)时无解，先手算出\(n=4,5,6,7\)时的解，然后根据\(s[i]=s[i-4]+(i-3)+i-(i-2)-(i-1)\)递推即可
code
#include<bits/stdc++.h>
using namespace std;
typedef double db;
const int N=50+10;
string s[N];
int n;
string i2s(int x) {
string s;
for(; x; x/=10)s.push_back(x%10+'0');
reverse(s.begin(),s.end());
return s;
}
int main() {
s[1]=s[2]=s[3]="-1";
s[4]="3*(1+4)+2";
s[5]="(2*5+3+4)*1";
s[6]="6+5+4+3-2+1";
s[7]="(2*5+3+4)+1+6-7";
for(int i=8; i<=50; ++i)s[i]=s[i-4]+"+"+i2s(i-3)+"+"+i2s(i)+"-"+i2s(i-2)+"-"+i2s(i-1);
scanf("%d",&n);
cout<<s[n]<<endl;
return 0;
}
B - Minimum Expression
dp+大数
\(dp[i][j]\)表示前\(i\)个数分成\(j\)段的最小值，从前往后递推即可
由于最优解的长度一般在\(\frac{n}{m}\)左右，因此可以只取\(\frac{n}{m}\)附近的几个长度进行递推（我取的是\([\frac{n}{m}-2,\frac{n}{m}+2]\)）
这样乍一看好像复杂度是\(O(n^3)\)的，但实际上\(m\)越大最优解的长度就越小，因此总复杂度还是\(O(n^2)\)的
代码用的python
code
n,m=input().split()
n=int(n)
m=int(m)
m+=1
s=input()
s='1'+s
dp=[[-1 for j in range(m+1)] for i in range(n+1)]
l1=n//m
l2=l1+1
l=[n//m-2,n//m-1,n//m,n//m+1,n//m+2]
dp[0][0]=0
for i in range(1,n+1):
for j in range(1,m+1):
for l1 in l:
if l1>0 and i-l1>=0 and dp[i-l1][j-1]!=-1:
if dp[i][j]==-1 or dp[i][j]>dp[i-l1][j-1]+int(s[i-l1+1:i+1]):
dp[i][j]=dp[i-l1][j-1]+int(s[i-l1+1:i+1])
print(dp[n][m])
C - Convex
枚举多边形上任意两点之间的连线对A进行切分即可
code
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
const int N=100+10;
const db eps=1e-10;
int n,m;
int sign(db x) {return fabs(x)<eps?0:x<0?-1:1;}
struct P {
db x,y;
P operator+(P b) {return {x+b.x,y+b.y};}
P operator-(P b) {return {x-b.x,y-b.y};}
P operator*(db b) {return {x*b,y*b};}
bool operator==(P b) {return sign(x-b.x)==0&&sign(y-b.y)==0;}
bool operator!=(P b) {return !(*this==b);}
};
db cross(P a,P b) {return {a.x*b.y-a.y*b.x};}
struct Seg {P p,q;} a[N],b[N];
vector<P> Points;
bool LSI(Seg a,Seg b) {
if(sign(cross({a.q-a.p}, {b.q-b.p})==0))return false;
return sign(cross({a.q-a.p}, {b.p-a.p})*cross({a.q-a.p}, {b.q-a.p}))!=1;
}
bool LSI_S(Seg a,Seg b) {return sign(cross((P) {a.q-a.p},(P) {b.p-a.p})*cross((P) {a.q-a.p},(P) {b.q-a.p}))==-1;}
P Intersection(Seg a,Seg b) {
P v=a.q-a.p,w=b.q-b.p,u=a.p-b.p;
db t=cross(w,u)/cross(v,w);
return a.p+v*t;
}
bool is_valiable(Seg s) {
int f=0;
for(int i=1; i<=m; ++i) {
db crs=sign(cross(s.q-s.p,b[i].p-s.p));
if(crs==-1)f|=1;
else if(crs==1)f|=2;
if(f==3)return false;
}
return true;
}
db solve(Seg s) {
vector<int> vec;
if(!is_valiable(s))return 0;
for(int i=1; i<=n; ++i)if(LSI(s,a[i])) {
P p=Intersection(s,a[i]);
if(p!=a[i].p)vec.push_back(i);
}
if(vec.size()<2)return 0;
int l=vec[0],r=vec[1];
P A=Intersection(s,a[l]),B=Intersection(s,a[r]);
vector<P> poly;
poly.push_back(A);
for(int i=l; i!=r; i=i%n+1)poly.push_back(a[i].q);
poly.push_back(B);
db S=0;
for(int i=2; i<=n-1; ++i)S+=cross(a[i].p-a[1].p,a[i].q-a[1].p);
S/=2;
db S2=0;
for(int i=1; i<poly.size()-1; ++i)S2+=cross(poly[i]-poly[0],poly[i+1]-poly[0]);
S2/=2;
int f=0;
for(int i=1; i<=m; ++i) {
db crs=sign(cross(s.q-s.p,b[i].p-s.p));
if(crs==-1)f|=1;
else if(crs==1)f|=2;
}
for(int i=0; i<poly.size(); ++i) {
db crs=sign(cross(s.q-s.p,poly[i]-s.p));
if(crs==-1)f|=1;
else if(crs==1)f|=2;
}
return f==3?S2:S-S2;
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; ++i) {
db x,y;
scanf("%lf%lf",&x,&y);
a[i].p.x=a[(i-2+n)%n+1].q.x=x;
a[i].p.y=a[(i-2+n)%n+1].q.y=y;
Points.push_back({x,y});
}
scanf("%d",&m);
for(int i=1; i<=m; ++i) {
db x,y;
scanf("%lf%lf",&x,&y);
b[i].p.x=b[(i-2+m)%m+1].q.x=x;
b[i].p.y=b[(i-2+m)%m+1].q.y=y;
Points.push_back({x,y});
}
db ans=0;
for(int i=0; i<Points.size(); ++i)
for(int j=i+1; j<Points.size(); ++j)
if(Points[i]!=Points[j])ans=max(ans,solve({Points[i],Points[j]}));
printf("%f\n",ans);
return 0;
}
D - The Matrix
把全部的k个图看成一个图跑kruskal算法即可，区别是每加入一条边需要将边权乘上在整个大图上需要连接的点对数，也就相当于除了要加入的边所在的图以外的其他所有图的连通块乘积之和（因为大图中在某张小图里同属于一个联通块的点，在对应的维度上是互相可达的，因此它们可以缩成一个点）
code
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
const int N=1e6+10,mod=998244353;
int k,n,m,siz[N],inv[N],fa[N],tot,ans;
struct E {
int u,v,c,id;
bool operator<(const E& b)const {return c<b.c;}
} e[N];
int fd(int x) {return fa[x]?fa[x]=fd(fa[x]):x;}
bool mg(int x,int y) {
int fx=fd(x),fy=fd(y);
if(fx==fy)return false;
fa[fx]=fy;
return true;
}
int main() {
inv[1]=1;
for(int i=2; i<N; ++i)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
scanf("%d",&k);
for(int i=1; i<=k; ++i) {
int _n,_m;
scanf("%d %d",&_n,&_m);
for(int j=1; j<=_m; ++j) {
int u,v,c;
scanf("%d %d %d",&u,&v,&c);
u+=n,v+=n;
e[++m]= {u,v,c,i};
}
n+=_n;
siz[i]=_n;
}
tot=1;
for(int i=1; i<=k; ++i)tot=(ll)tot*siz[i]%mod;
ans=0;
sort(e+1,e+1+m);
for(int i=1; i<=m; ++i) {
int u=e[i].u,v=e[i].v,c=e[i].c,id=e[i].id;
if(!mg(u,v))continue;
ans=(ans+(ll)c*tot%mod*inv[siz[id]]%mod)%mod;
tot=(ll)tot*inv[siz[id]]%mod*(siz[id]-1)%mod;
siz[id]--;
}
printf("%d\n",ans);
return 0;
}
E - Subsegments
前缀积+逆元，注意有0的情况需要分段处理
code
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
const int N=5e5+10;
const ll mod=998244353;
int n;
ll a[N],b[N],x;
ll Pow(ll x,ll p) {
ll ret=1;
for(; p; p>>=1,x=x*x%mod)if(p&1)ret=ret*x%mod;
return ret;
}
ll inv(ll x) {return Pow(x,mod-2);}
ll solve(int l,int r) {
if(x==0)return (ll)(r-l+1)*(r-l+2)/2;
ll ret=0;
map<ll,int> mp;
b[l-1]=1;
for(int i=l; i<=r; ++i)b[i]=(a[i]*b[i-1])%mod;
mp[1]++;
for(int i=l; i<=r; ++i) {
ret+=mp[x*inv(b[i])%mod];
mp[inv(b[i])]++;
}
return ret;
}
int main() {
scanf("%d%lld",&n,&x);
a[0]=1;
for(int i=1; i<=n; ++i)scanf("%lld",&a[i]);
ll ans=0;
for(int i=1,j; i<=n; i=j) {
if(a[i]==0) {j=i+1; continue;}
for(j=i+1; j<=n&&a[j]!=0; ++j);
ans+=solve(i,j-1);
}
if(x==0)ans=(ll)n*(n+1)/2-ans;
printf("%lld\n",ans);
return 0;
}
G - Corona Virus
树形dp，设\(dp[u][i]\)表示将结点\(u\)所在的子树进行分割，且分割后结点\(u\)所在的连通块直径为\(i\)的方案数，自底向上依次考虑每条边是否被割掉即可，需要前缀和优化，复杂度\(O(nk)\)
code
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
const int N=1e5+10,mod=1e9+7;
int n,ne,hd[N],k,f[N][101],g[N][101],buf[101];
struct E {int v,nxt;} e[N<<1];
void link(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}
void dfs(int u,int fa) {
f[u][0]=1;
for(int i=0; i<=k; ++i)g[u][i]=1;
for(int i=hd[u]; ~i; i=e[i].nxt) {
int v=e[i].v;
if(v==fa)continue;
dfs(v,u);
for(int i=0; i<=k; ++i)buf[i]=0;
for(int i=0; i<=k; ++i)buf[i]=(buf[i]+(ll)f[u][i]*g[v][k]%mod)%mod;
for(int i=1; i<k; ++i)buf[i]=(buf[i]+(ll)f[u][i]*g[v][min(i-1,k-i-1)]%mod)%mod;//i>=j+1,i+j<k;
for(int j=0; j<k; ++j)buf[j+1]=(buf[j+1]+(ll)g[u][min(j,k-j-1)]*f[v][j]%mod)%mod;//i<=j,i+j<k;
for(int i=0; i<=k; ++i)f[u][i]=buf[i];
g[u][0]=f[u][0];
for(int i=1; i<=k; ++i)g[u][i]=(g[u][i-1]+f[u][i])%mod;
}
}
int main() {
memset(hd,-1,sizeof hd),ne=0;
scanf("%d %d",&n,&k);
for(int i=1; i<n; ++i) {
int u,v;
scanf("%d%d",&u,&v);
link(u,v);
link(v,u);
}
dfs(1,0);
printf("%d\n",g[1][k]);
return 0;
}
H - Counting
暴力即可
审题很关键
code
#include<bits/stdc++.h>
using namespace std;
typedef double db;
const int N=2000+10;
int n,m,k,T,g[N][N],vis[N][N],ans;
struct P {int x,y;} a[N];
string s[N];
int main() {
scanf("%d%d%d%d",&n,&m,&k,&T);
for(int i=1; i<=k; ++i)scanf("%d%d",&a[i].x,&a[i].y);
for(int i=1; i<=k; ++i)cin>>s[i];
for(int i=1; i<=k; ++i)g[a[i].x][a[i].y]++;
ans=0;
for(int i=1; i<=k; ++i) {
int x=a[i].x,y=a[i].y;
if(!vis[x][y]) {
vis[x][y]=1;
ans+=(g[x][y]*(g[x][y]-1))/2;
}
}
for(int i=1; i<=k; ++i) {
int x=a[i].x,y=a[i].y;
vis[x][y]=0;
}
printf("%d\n",ans);
for(int j=0; j<T; ++j) {
for(int i=1; i<=k; ++i) {
char c=s[i][j];
int dx,dy;
if(c=='L')dx=0,dy=-1;
if(c=='R')dx=0,dy=1;
if(c=='U')dx=-1,dy=0;
if(c=='D')dx=1,dy=0;
int old_x=a[i].x,old_y=a[i].y;
int new_x=a[i].x,new_y=a[i].y;
new_x+=dx;
new_y+=dy;
g[old_x][old_y]--;
g[new_x][new_y]++;
a[i].x=new_x;
a[i].y=new_y;
}
ans=0;
for(int i=1; i<=k; ++i) {
int x=a[i].x,y=a[i].y;
if(!vis[x][y]) {
vis[x][y]=1;
ans+=(g[x][y]*(g[x][y]-1))/2;
}
}
for(int i=1; i<=k; ++i) {
int x=a[i].x,y=a[i].y;
vis[x][y]=0;
}
printf("%d\n",ans);
}
return 0;
}
J - Football Match
解析几何+坐标系变换，关键是求出F点的坐标，解方程或者二分都可以，然后通过旋转求出其他点的坐标，最后对整体进行缩放、旋转和平移
code
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
const int N=1e5+10,mod=1e9+7;
const db pi=acos(-1);
struct P {
db x,y;
P mov(db dx,db dy) {return {x+=dx,y+=dy};}
P rot(db r) {return {x*cos(r)-y*sin(r),x*sin(r)+y*cos(r)};}
P scale(db p) {return {x*p,y*p};}
} p[N],p2[N];
db dis(P a,P b) {return hypot(abs(a.x-b.x),abs(a.y-b.y));}
db bi(db l,db r) {
for(int i=1; i<200; ++i) {
db m=(l+r)/2;
P t= {m,p[4].y};
if(dis(t,p[2])<dis(t,p[4]))l=m;
else r=m;
}
return l;
}
int main() {
p[0]= {15.0,10.0}; //C
p[1]= {15.0,-10.0}; //D
p[2]= {0.0,6.0}; //E
p[4]=p[2].rot(-2*pi/5);//G
p[3]= {bi(0,p[4].x),p[4].y};//F
p[5]=p[3].rot(-2*pi/5);//H
p[7]=p[5].rot(-2*pi/5);//J
p[9]=p[7].rot(-2*pi/5);//L
p[11]=p[9].rot(-2*pi/5);//N
p[6]=p[4].rot(-2*pi/5);//I
p[8]=p[6].rot(-2*pi/5);//K
p[10]=p[8].rot(-2*pi/5);//M
for(int i=0; i<12; ++i)p[i]=p[i].mov(15,10);
int T;
for(scanf("%d",&T); T--;) {
db x1,y1,x2,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
db scale=hypot(abs(x1-x2),abs(y1-y2))/20;
db dx=x1,dy=y1;
db r=atan2(y2-y1,x2-x1)-atan2(1,0);
for(int i=0; i<12; ++i)p2[i]=p[i].scale(scale).rot(r).mov(dx,dy);
for(int i=0; i<12; ++i)printf("%f %f%c",p2[i].x,p2[i].y," \n"[i==11]);
}
return 0;
}
K - Coins
x小的时候dp，x大的时候直接输出A
code
#include<bits/stdc++.h>
using namespace std;
typedef double db;
const int N=1e6+50;
int dpa[N],dpb[N],n;
const int a[]= {2,3,17,19};
const int b[]= {5,7,11,13};
int main() {
memset(dpa,0x3f,sizeof dpa);
memset(dpb,0x3f,sizeof dpb);
dpa[0]=dpb[0]=0;
for(int i=0; i<4; ++i)
for(int j=0; j<N-50; ++j) {
dpa[j+a[i]]=min(dpa[j+a[i]],dpa[j]+1);
dpb[j+b[i]]=min(dpb[j+b[i]],dpb[j]+1);
}
int T;
for(scanf("%d",&T); T--;) {
int x;
scanf("%d",&x);
if(x==1)printf("-1");
else if(x>100000)printf("A");
else {
int t=dpa[x]-dpb[x];
if(t<0)printf("A");
else if(t==0)printf("both");
else printf("B");
}
printf("\n");
}
return 0;
}
M - Travel Round the Grid
毒瘤题，思路不难，但实现起来巨麻烦，有多种边界情况需要考虑
先假设起点在左上角，逐行往下扩充，之后平移到合法的位置即可（可能还需要上下翻转）
code
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
const int N=1e6+10;
int n,m,X,Y,k,tl,row,offset;
char s[N];
void mov() {
int x=X,y=Y,lx=X,rx=X,ly=Y,ry=Y;
for(int i=0; i<tl; ++i) {
if(s[i]=='L')y--;
else if(s[i]=='R')y++;
else if(s[i]=='U')x--;
else if(s[i]=='D')x++;
lx=min(lx,x);
rx=max(rx,x);
ly=min(ly,y);
ry=max(ry,y);
}
int dx=max(0,1-lx)-max(0,rx-n);
int dy=max(0,1-ly)-max(0,ry-m);
x=X+dx,y=Y+dy;
offset=-1;
for(int i=0; i<tl; ++i) {
if(s[i]=='L')y--;
else if(s[i]=='R')y++;
else if(s[i]=='U')x--;
else if(s[i]=='D')x++;
if(x==X&&y==Y) {
offset=(i+1)%tl;
break;
}
}
if(!~offset) {
for(int i=0; i<tl; ++i) {
if(s[i]=='U')s[i]='D';
else if(s[i]=='D')s[i]='U';
}
x=X,y=Y,lx=X,rx=X,ly=Y,ry=Y;
for(int i=0; i<tl; ++i) {
if(s[i]=='L')y--;
else if(s[i]=='R')y++;
else if(s[i]=='U')x--;
else if(s[i]=='D')x++;
lx=min(lx,x);
rx=max(rx,x);
ly=min(ly,y);
ry=max(ry,y);
}
int dx=max(0,1-lx)-max(0,rx-n);
int dy=max(0,1-ly)-max(0,ry-m);
x=X+dx,y=Y+dy;
for(int i=0; i<tl; ++i) {
if(s[i]=='L')y--;
else if(s[i]=='R')y++;
else if(s[i]=='U')x--;
else if(s[i]=='D')x++;
if(x==X&&y==Y) {
offset=(i+1)%tl;
break;
}
}
}
}
int main() {
int T;
for(scanf("%d",&T); T--;) {
scanf("%d%d%d%d%d",&n,&m,&X,&Y,&k);
tl=0;
row=(k+m-1)%m;
if(k==2) {
if(m>1)s[tl++]='R',s[tl++]='L';
else s[tl++]='D',s[tl++]='U';
} else if(m==2) {
s[tl++]='R';
for(int i=1; i<=k/m-1; ++i)s[tl++]='D';
s[tl++]='L';
for(int i=1; i<=k/m-1; ++i)s[tl++]='U';
} else if((n&1)&&(k+m-1)/m==n) {
s[tl++]='R';
for(int t=0; t<k/(2*m)-1; ++t) {
for(int i=1; i<=m-2; ++i)s[tl++]='R';
s[tl++]='D';
for(int i=1; i<=m-2; ++i)s[tl++]='L';
s[tl++]='D';
}
for(int i=1; i<=m-2; ++i)s[tl++]='R';
s[tl++]='D';
if(k==n*m) {
s[tl++]='D';
for(int t=0; t<m/2-1; ++t) {
s[tl++]='L';
s[tl++]='U';
s[tl++]='L';
s[tl++]='D';
}
s[tl++]='L';
s[tl++]='U';
} else {
for(int t=0; t<m-1-k%m; ++t)s[tl++]='L';
for(int t=0; t<k%m/2; ++t) {
s[tl++]='L';
s[tl++]='D';
s[tl++]='L';
s[tl++]='U';
}
}
for(int i=1; i<=n-2; ++i)s[tl++]='U';
} else if(k%(2*m)==2) {
s[tl++]='R';
int cnt=0;
for(int t=0; t<(k-1)/(2*m); ++t) {
for(int i=1; i<=m-2; ++i)s[tl++]='R';
s[tl++]='D';
for(int i=1; i<=m-2; ++i)s[tl++]='L';
s[tl++]='D';
cnt++;
}
s[tl++]='L';
for(int i=1; i<=k/m; ++i)s[tl++]='U';
} else {
s[tl++]='R';
for(int t=0; t<(k-1)/(2*m); ++t) {
for(int i=1; i<=m-2; ++i)s[tl++]='R';
s[tl++]='D';
for(int i=1; i<=m-2; ++i)s[tl++]='L';
s[tl++]='D';
}
for(int i=1; i<=((k-1)%(2*m)+1)/2-2; ++i)s[tl++]='R';
s[tl++]='D';
for(int i=1; i<=((k-1)%(2*m)+1)/2-2; ++i)s[tl++]='L';
s[tl++]='L';
for(int i=1; i<=((k-1)/(2*m))*2+1; ++i)s[tl++]='U';
}
mov();
for(int t=offset; t<offset+tl; ++t)putchar(s[t%tl]);
puts("");
}
return 0;
}
这篇关于“山大地纬杯”第十二届山东省ICPC大学生程序设计竞赛部分个人题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-23增量更新怎么做？-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些？-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗？-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
- 2024-11-23oss直传有什么好处？-icode9专业技术文章分享
- 2024-11-23如何将oss直传封装成一个组件在其他页面调用时都可以使用？-icode9专业技术文章分享
- 2024-11-23怎么使用laravel 11在代码里获取路由列表？-icode9专业技术文章分享
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享
