C/C++教程
“山大地纬杯”第十二届山东省ICPC大学生程序设计竞赛部分个人题解
本文主要是介绍“山大地纬杯”第十二届山东省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大学生程序设计竞赛部分个人题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
怎么切换 Git 项目的远程仓库地址？-icode9专业技术文章分享12-24
-
怎么更改 Git 远程仓库的名称？-icode9专业技术文章分享12-24
-
更改 Git 本地分支关联的远程分支是什么命令？-icode9专业技术文章分享12-24
-
uniapp 连接之后会被立马断开是什么原因？-icode9专业技术文章分享12-24
-
cdn 路径可以指定规则映射吗？-icode9专业技术文章分享12-24
-
CAP：Serverless?+AI?让应用开发更简单12-24
-
新能源车企如何通过CRM工具优化客户关系管理，增强客户忠诚度与品牌影响力12-23
-
原创tauri2.1+vite6.0+rust+arco客户端os平台系统|tauri2+rust桌面os管理12-23
-
DevExpress 怎么实现右键菜单（Context Menu）显示中文？-icode9专业技术文章分享12-23
-
怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享12-22
-
el-tabs 组件只被引用了一次，但有时会渲染两次是什么原因？-icode9专业技术文章分享12-22
-
wordpress有哪些好的安全插件？-icode9专业技术文章分享12-22
-
wordpress如何查看系统有哪些cron任务？-icode9专业技术文章分享12-22
-
Svg Sprite Icon教程：轻松入门与应用指南12-21
-
Excel数据导出实战：新手必学的简单教程12-20
栏目导航
