Codeforces Round#516 Div.1 翻车记-白红宇

Codeforces Round#516 Div.1 翻车记

阅读量：4625 次

发布时间：2019-06-09

本文共 2795 字，大约阅读时间需要 9 分钟。

　　A：开场懵逼。然后发现有人1min过，于是就sort了一下，于是就过了。正经证明的话，考虑回文串两端点一定是相同的，所以最多有Σcnt_i*(cnt_i+1)/2个，cnt_i为第i种字母出现次数。而sort是可以达到这个最大值的。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 100010int n;char s[N];int main(){ n=read(); scanf("%s",s+1);sort(s+1,s+n+1); printf("%s",s+1); return 0;}

View Code

　　B：注意到由一点到另一点向左和向右移动次数的差是固定的，所以只需要最小化他们的和。直接dij即可。实际上有一种01bfs的trick，用来跑边权只有01的最短路，使用一个deque，每次将0边扩展到的点放在队首，1边扩展到的点放在队尾，容易发现这样保证了队列里的点按距离排序。不过普通队列直接bfs的fst了一片。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 2010int n,m,r,c,x,y,p[N*N],t,ans=0;int a[N][N],d[N*N];bool flag[N*N];struct data{ int to,nxt,len;}edge[N*N<<2];void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}int trans(int x,int y){ return (x-1)*m+y;}struct data2 { int x,d; bool operator <(const data2&a) const { return d>a.d; } }; priority_queue
             
               q;void dijkstra(int start){ while (!q.empty()) q.pop(); memset(d,42,sizeof(d));d[start]=0;q.push((data2){start,0}); memset(flag,0,sizeof(flag)); for (int i=1;i<=n*m;i++) { while (!q.empty()&&flag[q.top().x]) q.pop(); if (q.empty()) break; data2 v=q.top();q.pop(); flag[v.x]=1; for (int j=p[v.x];j;j=edge[j].nxt) if (v.d+edge[j].len
              
               1&&a[i-1][j]) addedge(trans(i,j),trans(i-1,j),0); if (j>1&&a[i][j-1]) addedge(trans(i,j),trans(i,j-1),1); if (i

View Code

　　C：将所有点放在一条线上，黑点划在一边白点划在一边，每次取未确定部分的中点，根据所给颜色继续划分。可能需要把第一个点放在最左或最右，不这么干的话最后可能会有重合点。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 35int n,l,r;int main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif cin>>n;l=0,r=1000000000; cout<<1<<' '<<0<
             
              ='a'&&c<='z') c=getchar(); } cout<<0<<' '<
              
               <<' '<<2<<' '<
               
                <

View Code

　　后面的神仙题不管了。

　　本来是手速场结果C想了1h，BC加起来还wa了四发，于是就没救了。

　　result：rank 226 rating +15

转载于:https://www.cnblogs.com/Gloid/p/9788467.html

你可能感兴趣的文章