2023.08.13百度之星（大失败）
大失败，哭；
放个链接，有空来补：码蹄集 (matiji.net)
前面两题写的还挺顺手，然后开始写4和6，然后寄了，两个题加起来大概交了十发吧，算法没什么大问题，但是写挂了，都只能过一半的样例，悲；
总结：沉淀，提升码力；
1记录把每个参数都调成同一个值的代价和把每个参数调成一段连续的数的代价，比较相加最小值即可；
调成同一个值的代价应该是其他点排序后到最中间的点的距离之和，因此大胆猜想调成一段连续的数是写成以中间的点为中心的一段数的距离和（不会证明）；
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 int read(){ 5 char ch=getchar();int x=0,f=1; 6 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 7 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 8 return x*f; 9 } 10 const int maxn=1e5+5; 11 int N; 12 int x[maxn],y[maxn],z[maxn]; 13 int main(){ 14 N=read(); 15 for(int i=1;i<=N;i++){ 16 x[i]=read();y[i]=read();z[i]=read(); 17 } 18 sort(x+1,x+N+1); 19 sort(y+1,y+N+1); 20 sort(z+1,z+N+1); 21 int t=(N+1)/2; 22 ll ans1=0,ans2=0,ans3=0; 23 for(int i=1;i<=N;i++){ 24 ans1+=abs(x[i]-x[t]); 25 ans2+=abs(y[i]-y[t]); 26 ans3+=abs(z[i]-z[t]); 27 } 28 ll s1=0,s2=0,s3=0; 29 30 if(N%2==1){ 31 int a=x[t]-t; 32 int b=y[t]-t; 33 int c=z[t]-t; 34 for(int i=1;i<=N;i++){ 35 a++;b++;c++; 36 s1+=abs(x[i]-a); 37 s2+=abs(y[i]-b); 38 s3+=abs(z[i]-c); 39 } 40 cout<<min(min(ans1+ans2+s3,ans1+s2+ans3),s1+ans2+ans3)<<endl; 41 return 0; 42 } 43 ll ans; 44 if(N%2==0){ 45 int a=x[t]-t; 46 int b=y[t]-t; 47 int c=z[t]-t; 48 s1=0,s2=0,s3=0; 49 for(int i=1;i<=N;i++){ 50 a++;b++;c++; 51 s1+=abs(x[i]-a); 52 s2+=abs(y[i]-b); 53 s3+=abs(z[i]-c); 54 } 55 ans=min(min(ans1+ans2+s3,ans1+s2+ans3),s1+ans2+ans3); 56 t++;s1=0;s2=0;s3=0; 57 a=x[t]-t; 58 b=y[t]-t; 59 c=z[t]-t; 60 for(int i=1;i<=N;i++){ 61 a++;b++;c++; 62 s1+=abs(x[i]-a); 63 s2+=abs(y[i]-b); 64 s3+=abs(z[i]-c); 65 } 66 ans=min(min(min(ans1+ans2+s3,ans1+s2+ans3),s1+ans2+ans3),ans); 67 } 68 cout<<ans<<endl; 69 return 0; 70 }
3建边跑最短路即可；
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 char ch=getchar();int x=0,f=1; 5 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 6 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 7 return x*f; 8 } 9 const int maxn=2e5+5; 10 const int maxm=1e6+5; 11 int N,tot; 12 int A[maxn],t[maxm],head[maxn],d[maxn],v[maxn]; 13 struct node{ 14 int u,v,next; 15 }e[maxm]; 16 void add(int u,int v){ 17 tot++; 18 e[tot].u=u;e[tot].v=v; 19 e[tot].next=head[u];head[u]=tot; 20 } 21 priority_queue<pair<int,int>>q; 22 void dij(){ 23 memset(d,0x3f,sizeof(d)); 24 memset(v,0,sizeof(v)); 25 d[1]=0; 26 q.push(make_pair(0,1)); 27 while(q.size()){ 28 int x=q.top().second;q.pop(); 29 if(v[x])continue; 30 v[x]=1; 31 for(int i=head[x];i;i=e[i].next){ 32 int y=e[i].v; 33 if(d[y]>d[x]+1){ 34 d[y]=d[x]+1; 35 q.push(make_pair(-d[y],y)); 36 } 37 } 38 } 39 } 40 41 int main(){ 42 N=read(); 43 for(int i=1;i<=N;i++){ 44 A[i]=read(); 45 if(t[A[i]]){ 46 add(t[A[i]],i); 47 } 48 t[A[i]]=i; 49 if(i<N){ 50 add(i,i+1);add(i+1,i); 51 } 52 } 53 dij(); 54 cout<<d[N]<<endl; 55 return 0; 56 }
4看出来是exgcd，大概就是(n2-n1)*x + (n3-n1)*y = q - n1*p，且x+y<=p，0<=x<=p，0<=y<=p，要求y能取到的最小值与最大值；写了，挂了，回想了一下应该是判断最小值最大值无解那段写挂了；（有空补）
6一眼排序然后比较速度大小；
对于两只猫a，b:
1.a.p==b.p那么a.v=b.v=min(a.v,b.v)；
2.a.p<b.p&&a.v<=b.v不可能追上；
3.a.p<b.p&&a.v>b.v可以追上；
统计有多少只猫一起即可，考场上一直没调出来，但是补题一发过了，真令人寒心；
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 ll N,ans,cnt,now; 5 struct node{ 6 ll p,v; 7 }e[100005]; 8 int cmp(node a,node b){ 9 if(a.p==b.p)return a.v<b.v; 10 return a.p<b.p; 11 } 12 int main( ){ 13 cin>>N; 14 for(int i=1;i<=N;i++){ 15 cin>>e[i].p>>e[i].v; 16 } 17 sort(e+1,e+N+1,cmp); 18 for(int i=1;i<=N-1;i++){ 19 if(e[i].p==e[i+1].p){ 20 e[i].v=e[i+1].v=min(e[i].v,e[i+1].v); 21 } 22 } 23 ans=0;now=N; 24 for(int i=N;i>=1;i--){ 25 if(e[i].v==e[now].v&&e[i].p==e[now].p){ 26 cnt++;ans=max(ans,cnt);continue; 27 } 28 if(e[i].v>e[now].v){ 29 cnt++;ans=max(ans,cnt);continue; 30 } 31 if(e[i].v<=e[now].v&&e[i].p<e[now].p){ 32 cnt=1;ans=max(ans,cnt);now=i;continue; 33 } 34 } 35 cout<<ans<<endl; 36 return 0; 37 }
唉，要学习的还有很多，继续沉淀吧；