Codeforces Round #533 (Div. 2) ABCD 题解-白红宇

Codeforces Round #533 (Div. 2) ABCD 题解

阅读量：4991 次

发布时间：2019-06-12

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

题目链接

A. Salem and Sticks

分析

暴力就行,题目给的n<=1000,ai<=100,暴力枚举t,t从2枚举到98,复杂度是1e5,完全可行.

代码

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                12 #include 
                 
                   13 using namespace std;14 const int INF=0x3f3f3f3f;15 16 int a[1000];17 18 int main()19 {20 // freopen("in.txt","r",stdin);21 // freopen("out.txt","w",stdout);22 int n;23 cin>>n;24 for(int i=0;i
                  
                   >a[i];25 int ans=INF,res;26 for(int i=2;i<100;i++)27 {28 int sum=0;29 for(int j=0;j
                   
                    1) sum=sum+x-1;34 }35 if(ans>sum) ans=sum,res=i;36 }37 cout<
                    
                     <<' '<
                     
                      <

View Code

B. Zuhair and Strings

分析

暴力题,暴力查找k个相同字母组成的序列就行.

代码

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                12 #include 
                 
                   13 using namespace std;14 const int INF=0x3f3f3f3f;15 16 char a[200000];17 int ans[26];18 19 int main()20 {21 // freopen("in.txt","r",stdin);22 // freopen("out.txt","w",stdout);23 int n,k;24 cin>>n>>k;25 getchar();26 for(int i=0;i

View Code

C. Ayoub and Lost Array

分析

计数dp,算出l到r区间中mod3是0的数a0,mod3是1的数a1,mod3是2的数a2,dp[i][j]表示,i个数的和mod3是j,dp[1][0]=a0,dp[1][1]=a1,dp[1][2]=a3,i从2开始更新,最后dp[n][0]就是答案.

代码

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                12 #include 
                 
                   13 using namespace std;14 const int INF=0x3f3f3f3f;15 16 const int mod=1000000007;17 long long dp[200001][3];18 19 int main()20 {21 // freopen("in.txt","r",stdin);22 // freopen("out.txt","w",stdout);23 int n,l,r;24 cin>>n>>l>>r;25 long long a0,a1,a2;26 a0=r/3-(l-1)/3;27 a1=(r+2)/3-(l+1)/3;28 a2=(r+1)/3-l/3;29 dp[1][0]=a0,dp[1][1]=a1,dp[1][2]=a2;30 for(int i=2;i<=n;i++)31 {32 dp[i][0]=(dp[i-1][0]*a0+dp[i-1][1]*a2+dp[i-1][2]*a1)%mod;33 dp[i][1]=(dp[i-1][0]*a1+dp[i-1][1]*a0+dp[i-1][2]*a2)%mod;34 dp[i][2]=(dp[i-1][0]*a2+dp[i-1][1]*a1+dp[i-1][2]*a0)%mod; 35 }36 cout<
                  
                   <

View Code

D. Kilani and the Game

分析

bfs扩展题,这里的bfs需要控制步数且同时进行,每个玩家的speed就要求控制步数,同时进行是为了防止一个点扩展后把另一个点包住导致另一个点无法扩展,可以用优先队列设置优先级来完成这个bfs,结构体可以设置 a,b坐标,c步数(在一个回合内走了多少步),d回合数,e序数(第几个玩家),优先级设置是 回合数(从小到大)>序列数(从小到大)>步数(从小到大),需要注意的是优先队列的排序方式,优先队列是默认大的在前,小的在后.

代码

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                12 #include 
                 
                   13 using namespace std;14 const int INF=0x3f3f3f3f;15 16 struct N17 {18 int a,b,c,d,e;19 N (){}20 N (int x,int y,int s,int t,int u){a=x,b=y,c=s,d=t,e=u;}21 bool operator < (const N &x)const22 {23 if(d!=x.d) return d>x.d;24 else if(e!=x.e) return e>x.e;25 else return c>x.c; 26 }27 };28 29 char mapp[1000][1000];30 priority_queue
                  
                    que;31 int dx[4]={ 1,-1,0,0},dy[4]={ 0,0,1,-1};32 int ans[10];33 int speed[10];34 int n,m;35 36 void bfs(void)37 {38 while(que.size())39 {40 N p=que.top();que.pop();41 int x=p.a,y=p.b,step=p.c,turn=p.d,s=p.e;42 for(int i=0;i<4;i++)43 {44 int nx=x+dx[i],ny=y+dy[i];45 if(nx>=0&&nx
                   
                    =0&&ny
                    
                     >n>>m>>p;68 for(int i=1;i<=p;i++) cin>>speed[i];69 for(int i=0;i
                     
                      >mapp[i][j];73 if(mapp[i][j]!='#'&&mapp[i][j]!='.')74 {75 int s=mapp[i][j]-'1'+1;76 que.push(N(i,j,0,0,s)),ans[s]++;77 } 78 }79 /* while(que.size())80 {81 N p=que.top();que.pop();82 printf("(%d,%d) step:%d turn:%d i:%d\n",p.a,p.b,p.c,p.d,p.e);83 }84 */85 bfs();86 for(int i=1;i

View Code

转载于:https://www.cnblogs.com/VBEL/p/10668054.html

你可能感兴趣的文章

C#将Word转换成PDF方法总结(基于Office和WPS两种方案)