codeforces-白红宇

codeforces

阅读量：4114 次

发布时间：2019-05-25

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

A. Palindromic Twist

题意：

给你一个有偶数个字符的字符串，其中字符串里面的字符可以进行一些变化，每个字符只能进行一次变化，而且必须进行变化，其中对每个字符的操作只有一种，每个字符可以变成他前面的或者后面的字符（根据26个字母的顺序，其中a只能变成b，z只能变成他前面的），进行完操作之后问你这个船是不是回文串。

思路：

从第一位开始看他对应位置的字符，看他们俩能否通过变化变成相同的字符，这里要注意，要是对应为的字符对应的字符也相邻，这里变不成的，因为每个字符都需要恰好改变一次，可以发现如果两个字符对应字母表里的位置差不超过二就可以变成。这样遍历一边就行了。

#include 
   
    #include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;char str[200];int main(){ int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); scanf("%s",str); int f=0; for(int i=0;i

B. Weakened Common Divisor

题意：给你一个n*n的矩阵，在里面填上1-n*m这几个数，（x,y）表示在棋盘中的位置，当（x+y）是偶数时，从矩阵的左上到右下填上1-（n*n+1）/2个数字，为奇数时，从左上到右下填上（n*n）/2+1—n*m,现在有一些询问，给出一个坐标，问你现在这个格子里面填的是什么数。

思路：填数填的很有规律，分一下奇偶，分类讨论一下就好了。

#include 
   
    #include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;char str[200];long long n;void slove1(int x,int y){ long long ans=0; long long temp=(n*n+1)/2;// if((x+y)%2==0) //even { ans=(n)*(x-1)/2+(y+1)/2; }// else// {//// } if((x+y)%2) ans+=temp; printf("%lld\n",ans);}void slove2(int x,int y){ long long ans=0; long long temp=(n*n+1)/2; if((x+y)%2==0) { int d=(x)/2; int s=x-d-1; ans=(n+1)/2*d+(n)/2*s+(y+1)/2; } else { int s=(x)/2; int d=x-s-1; ans=(n+1)/2*d+(n)/2*s+(y+1)/2; ans+=temp; } printf("%lld\n",ans);}int main(){ long long q; scanf("%lld%lld",&n,&q); while(q--) { int x,y; scanf("%d%d",&x,&y); if(n%2==0) slove1(x,y); else slove2(x,y); } return 0;}

C. Minimum Value Rectangle

题意:给你一些木棍，让你从中挑选四根，构成一个矩形，要求矩形周长的平方除矩形的面积这个比值最小。

思路：我们可以先统计一下木棍的个数，这里的统计有一个技巧，因为如果想要构成一个矩形肯定要求其中两根木棍的长度要相同，这样我们统计成对的木棍，设选出的木棍的长宽为a，b，题目需要比较的值可以表示为如下：

$4*(a+b)*(a+b)/(a*b)=4*(2+a/b+b/a)$

我们可以把后面的a/b+b/a当做对号函数来看，当a接近b的时候值更小。

很奇怪的是我统计每个数出现次数，对出现过的数进行操作，竟然超时了，我个人感觉自己的代码时间复杂度更小。

#include 
   
    #include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;int a[1000000+10];int b[1000000+10];int main(){ int T; scanf("%d",&T); while(T--) { int n; int maxx=0; scanf("%d",&n); for(int i=0; i
             
              pp*s) { p=pp; s=ss; aa=b[i]; bb=b[i+1]; } }// int a=0,b=0;// double res=200000000;// int minn=maxx;// for(int i=maxx; i>=0; i--)// {// if(num[i]<0) continue;// aa[i]=minn;// if(num[i]>=2) minn=min(minn,i);// }// for(int i=0; i<=maxx; i++)// {// if(num[i]<2) continue;// if(num[i]>=4)// {// double temp=4.0*(1.0*i+i)*(1.0*i+i)/(i*i);// if(temp
              
               =2)// {// int j=aa[i];// double temp=4.0*(1.0*i+j)*(1.0*i+j)/(i*j);// if(temp

D. Mouse Hunt

题意：一个人想抓老鼠，现在有n个房间，在每个房间里面布置陷阱都有一个费用，如果老鼠现在i房间，那么下一秒他会进入a[i]这个房间，现在问你不管老鼠在哪个房间，这个人想抓住老鼠需要的最少费用。

思路：根据老鼠的路线，如果老鼠现在在i下一秒年进入a[i]房间，我们就在他们之间连一条边，这样我们就可以得到一些链，一些环，一些孤立的点，对于链而言，我们肯定要选链尾，孤立点选他自己，环就选一个环里面费用最少的一个点。

#include 
   
    #include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;const int maxn=2e5+50;int de[maxn];int vis[maxn];int a[maxn];int to[maxn];vector
             
               sg;int n;int dfs(int u,int c){ if(vis[u]) return c; vis[u]=1; int x=to[u]; c=min(c,a[u]); c=min(c,dfs(x,c)); return c;}int main(){ scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%d",&a[i]); } memset(vis,0,sizeof(vis)); memset(to,0,sizeof(to)); int ans=0; for(int i=1; i<=n; i++) { int x; scanf("%d",&x); to[i]=x; if(i!=x) de[x]++; if(i==x) ans+=a[i]; } queue
              
                p; for(int i=1; i<=n; i++) { if(de[i]==0) p.push(i); } while(!p.empty()) { int x=p.front(); p.pop(); int t=to[x]; if(x==t) continue; de[t]--; if(de[t]==0) { p.push(t); } } for(int i=1; i<=n; i++) { if(!vis[i]&&de[i]) { ans+=dfs(i,a[i]); } } printf("%d\n",ans); return 0;}

转载地址：http://sbgsi.baihongyu.com/

你可能感兴趣的文章