558A

水题

题解

尽管题目水但不妨碍我的代码丑陋无比

#include<iostream> #include<algorithm> using namespace std; const int Maxn=1000; int n,m,v; struct A { int id,v; }a1[Maxn],a2[Maxn]; int cmp1(A x,A y) { return x.id<y.id; } int cmp2(A x,A y) { return x.id>y.id; } int he1(int m) { int ans=0; for(int i=1;i<=m;i++){ ans+=a1[i].v; } return ans; } int he2(int m) { int ans=0; for(int i=1;i<=m;i++){ ans+=a2[i].v; } return ans; } int main() { cin>>n; int l=0,r=0,ans=0; for(int i=1;i<=n;i++){ scanf("%d%d",&m,&v); if(m<0){ a1[++l].id=m; a1[l].v=v; } else{ a2[++r].id=m; a2[r].v=v; } } sort(a1+1,a1+l+1,cmp2); sort(a2+1,a2+r+1,cmp1); if(l==r){ ans+=he1(l)+he2(r); } else{ if(l>r){ ans+=he1(r+1)+he2(r); } else{ ans+=he1(l)+he2(l+1); } } cout<<ans<<endl; }

558B

题目

求数列中出现最多数字的出现区间（如果有多个最多数字，选择最短的那个，如果最短的有很多，选择左端点最靠左的那个）

题解

一开始我想的是一遍遍历，找到最多的数字的个数，和每个数字出现的个数，然后再来一遍遍历，对于每一个数字出现个数等于最多的，遍历找到左端点与右端点，计算区间长度，最后找到最短区间长度，但是TL了 然后看了一个AC代码，发现自己还是太年轻了，这个水题完全可以一遍遍历就完成所有的操作

#include<iostream> using namespace std; const int Maxv=1e6+5; int n,z,y,l[Maxv],r[Maxv],v[Maxv],ans,len,m; int main() { cin>>n; for(int i=1;i<=n;i++){ scanf("%d",&m); v[m]++; if(!l[m]) l[m]=i; r[m]=i; len=r[m]-l[m]; if(v[m]>ans){ ans=v[m]; z=l[m];y=r[m]; } else{ if(v[m]==ans&&len<y-z){ z=l[m];y=r[m]; } } } cout<<z<<' '<<y<<endl; }

558C

题目

对一个数可以*2，也可以/2（整数除法），问将数列变成一样的最少需要多少次操作 听说可以用LCA做，好像挺有道理的，但我看见数据很少，就直接暴力了 但仍然还有一个想错的地方，我以为最终数列变成的那个数一定小于等于数列最大的数，而且想了好久没想到反例，结果过了68个case，挂在69,70case上了，只能说CF tql，Hack的数据实在太奇怪了，完全想不到

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int Maxn=1e6+5,Maxv=1e6; int n,m,l,ci,c[Maxv],a[Maxn],v[Maxv],M; void up(int x,int cnt) { x=x<<1;cnt++; while(x<=1e5){ //cout<<"up:"<<x<<' '<<cnt<<endl; v[x]++; c[x]+=cnt; x=x<<1;cnt++; } } int main() { cin>>n; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ m=a[i]; l=0;ci=0; up(m,ci); while(m>0){ if(l==1) up(m,ci); l=m%2; //cout<<m<<' '<<ci<<endl; v[m]++;c[m]+=ci; m=m>>1;ci++; } } int ans=0x3f3f3f3f; for(int i=1;i<=1e5;i++){ if(v[i]==n){ ans=min(ans,c[i]); } } cout<<ans<<endl; }

558D

未完待续

558E