Codeforces Round #498 (Div. 3) （A+B+C+D+E+F）-白红宇

Codeforces Round #498 (Div. 3) （A+B+C+D+E+F）

阅读量：801 次

发布时间：2019-03-25

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

A题（签到）

思路：根据题意，最终操作后，奇数不会变，偶数都会减1

#pragma comment(linker, "/STACK:102400000,102400000")///手动扩栈#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                using namespace std;#define LL long long#define ULL unsigned long longconst int INF=0x3f3f3f;const double eps=1e-5;const int maxn=2e5+50;int main(){ // ios::sync_with_stdio(false);// cin.tie(0);// cout.tie(0); int n; scanf("%d",&n); for(int i=1;i<=n;i++) { int t; scanf("%d",&t); if(t&1) printf("%d ",t); else printf("%d ",t-1); } // system("pause"); return 0;}

B题（签到）

题意：把一个数组分成k段，每段贡献为区间最大值，求总贡献最大值

思路：找出前k大的元素下标,然后下标按递增排序

PS:这题自己属实脑瘫= =、，在输出区间长度的时候，总是细节出问题，wa了三发

#pragma comment(linker, "/STACK:102400000,102400000")///手动扩栈#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                using namespace std;#define LL long long#define ULL unsigned long longconst int INF=0x3f3f3f;const double eps=1e-5;const int maxn=2e5+50;//题意：把一个数组分成k段，每段贡献为区间最大值，求总贡献最大值//思路：找出前k大的元素下标struct node{ int index,v; friend bool operator < (const node &f1,const node &f2) { if(f1.v!=f2.v) return f1.v>f2.v;//大的在前面 else return f1.index>f2.index; }};vector
                
                 a;int n,k;vector
                 
                   divd;int main(){ // ios::sync_with_stdio(false);// cin.tie(0);// cout.tie(0); scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { int t; scanf("%d",&t); a.push_back({ i,t}); } sort(a.begin(),a.end()); int sum=0; for(int i=0;i

C题（双指针+坑）

题意：给定一个数列，把它分成3段，可以是空段。记每段的区间和为a b c，（a区间从首项开始 b为中间段 c末项结束）问满足a==c 且a最大的分法下，a为多少。（a c有可能取0）

思路：双指针,p1 p2刚开始分别指向首项和末项，代表左区间和右区间的最远扩展点。然后不断向中间扩展，细节判断见代码

#pragma comment(linker, "/STACK:102400000,102400000")///手动扩栈#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                using namespace std;#define LL long long#define ULL unsigned long longconst int INF=0x3f3f3f;const double eps=1e-5;const int maxn=2e5+50;LL a[maxn];int n;int p1,p2;int main(){ // ios::sync_with_stdio(false);// cin.tie(0);// cout.tie(0); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld",a+i); } p1=1,p2=n;//分别指首 末位置 LL l=a[p1],r=a[p2];//l表示左段的和 r表示右段的和 LL mmax=0;//记录最大答案 while(p1
                
                 r) { p2--; r+=a[p2]; } else { p1++; l+=a[p1]; } } cout<

D题（字符串水题）

题意：给定两个字符串，我们能进行三种操作：第一种，将 a[i] 和 b[i] 的单个字符交；第二种，将 a[i] 和 a[n-i+1] 的单个字符交换；第三种，将 b[i] 和 b[n-i+1] 的单个字符交换。但是题目的要求是，让我们先做预处理替换a中的字符，再进行如上三种操作，能让字符串 a == b ，求预处理的次数。

思路：其实看懂了样例就不难，纯粹的模拟题。

我们每次需要比较a[i] a[n+1-i] b[i] b[n+1-i] 这4个元素。看它们能不能两两配对相等。出现诸如 a a b b / a b a b /这些情况，因为这些位置其实是互通的。

我们分两种情况讨论：

1、 b[i]==b[n-i+1]: 此时如果 a[i]!=a[n-i+1] ,操作次数就+1，否则+0

（这里我真傻，第一次写的时候不等的情况次数+2去了 = =、又是因为太傻逼wa了）

2、 b[i]！=b[n-i+1] : 先看a[i] 会不会跟两个都不相等，如果会，次数+1 ；再看a[n-i+1] 会不会跟两个都不相等，如果会，次数+1。这里有个特殊情况，如果a[i] a[n-i+1]都跟其中一个相等，可能是 a a /a b这种情况，操作次数得加1.

#pragma comment(linker, "/STACK:102400000,102400000")///手动扩栈#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                using namespace std;#define LL long long#define ULL unsigned long longconst int INF=0x3f3f3f;const double eps=1e-5;const int maxn=1e5+50;char s1[maxn],s2[maxn];int len;int ans;bool cmp(int &a,int &b){ return a>b;}int main(){ // ios::sync_with_stdio(false);// cin.tie(0);// cout.tie(0); scanf("%d%s%s",&len,s1+1,s2+1); int p1=1,p2=len; while(p1

E题（DFS）

这应该是写过最水的E题了…

题意：给定一棵n顶点的有根树，1为根。给出q个询问，每次询问以u为根的子树，dfs序第k个节点编号。 dfs过程优先遍历序号小的孩子节点。若不存在输出-1

(1<=n,q<=2e5)

思路：按照题目要求dfs一遍，order存dfs序，Hash[i]存第i个顶点在dfs序数组中的下标。num[i]存以i为根的树，有几个顶点。

#pragma comment(linker, "/STACK:102400000,102400000")///手动扩栈#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                using namespace std;#define LL long long#define ULL unsigned long longconst int INF=0x3f3f3f;const double eps=1e-5;const int maxn=2e5+50;struct { int to,next;}edge[maxn];int head[maxn],cnt=1;int n,q;int order[maxn];//dfs序int cont=0;int Hash[maxn];//第i个顶点在order中的下标int num[maxn];//以i为根的树 搜到几个点void add(int from,int to){ edge[cnt].to=to; edge[cnt].next=head[from]; head[from]=cnt++;}int dfs(int rt){ int ans=1; order[++cont]=rt; vector
                
                  a; for(int i=head[rt];i;i=edge[i].next) { int to=edge[i].to; a.push_back(to); } sort(a.begin(),a.end());//递增排序 for(auto i:a) { ans+=dfs(i); } num[rt]=ans; return ans;}int main(){ // ios::sync_with_stdio(false);// cin.tie(0);// cout.tie(0); scanf("%d%d",&n,&q); for(int i=2;i<=n;i++) { int fa; scanf("%d",&fa);//建有向边 add(fa,i); } num[1]=dfs(1); for(int i=1;i<=cont;i++) { Hash[order[i]]=i; } while(q--) { int u,k; scanf("%d%d",&u,&k); if(k>num[u]) { puts("-1"); } else printf("%d\n",order[Hash[u]+k-1]); }// system("pause"); return 0;}

F题（双向dfs搜索+记忆化搜索）

题意：输入n,m,k,给出一个n*m的矩阵网格，每个格子有权值，从（1,1）一路异或到（n,m），只能向右或向下走，求到达(n,m)时，异或值等于k有多少种路径。

(1<=n,m<=20 0<=a[i][j],k<=1e18 )

异或性质：

1、a ^ b ^ a=b ^ a ^ a=b ( 一个数对另一个数异或2次得原数）

2、a^ b^ c^ d^ e…进行异或运算，顺序不影响结果

3、若a ^ b=c 则 a ^ c=b 且 b ^ c=a

//扩展 a^bc^d…x=y 则y替换左边任何一个等式都成立

PS：这题一开始联想到AC自动机上状压dp，也想用类似的状压dp方法做。

但是这里的状态有1e18，太大了，所以考虑用map. 感觉思路没啥问题。

没想到提交后mle了淦。后来用滚动数组优化了一维，居然还是mle。太草了！可能是map耗内存太大了吧。

AC思路：dp不行，那只能记忆化搜索了。但是朴素的搜索估计会tle或mle 。大佬的题解里用了一个高级的玩意儿，双向搜索。以知了出发点和目的点的状态，分别从出发点开始dfs，搜到中间位置则停下。再从目的点开始dfs，带着状态搜到中间点记录答案。

关于这里双向搜索，我说一下自己的理解：从起点到终点，假设得到k的异或路径经过的数依次是x1,x2,x3,x4…xf 。那么只要在搜索过程中让这些数参与异或就一定可以得到k，我们假设在中间点经过的数为Xm,根据异或性质，x1,x2,x3…k…xf参与异或得到的一定是Xm ,所以双向搜索过程中，搜到中间的时候用k去参与异或得出这个Xm就可以了。

//#pragma comment(linker, "/STACK:102400000,102400000")///手动扩栈#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                using namespace std;#define LL long long#define ULL unsigned long longconst int INF=0x3f3f3f;const double eps=1e-5;const int maxn=2e5+50;map
                
                  dp[24*24];LL g[25][25];int n,m;LL K;LL ret=0;int Hash(int i,int j){ return i*23+j;}void dfs1(int x,int y,LL now)//now 现在的状态{ if(x+y==(n+m+2)/2)//到中间点 { dp[Hash(x,y)][now]++; return; } if(x
                 
                  1) dfs2(x-1,y,now^g[x-1][y]); if(y>1) dfs2(x,y-1,now^g[x][y-1]);}int main(){ // ios::sync_with_stdio(false);// cin.tie(0);// cout.tie(0); scanf("%d%d%lld",&n,&m,&K); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%lld",&g[i][j]); } } dfs1(1,1,g[1][1]); dfs2(n,m,g[n][m]); cout<

上mle的代码，思路我感觉是ok 的qaq

//#pragma comment(linker, "/STACK:102400000,102400000")///手动扩栈#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                using namespace std;#define LL long long#define ULL unsigned long longconst int INF=0x3f3f3f;const double eps=1e-5;const int maxn=2e5+50;unordered_map
                
                  dp[2][21];//滚动数组优化一维LL g[25][25];int n,m;LL K;int main(){ // ios::sync_with_stdio(false);// cin.tie(0);// cout.tie(0); scanf("%d%d%lld",&n,&m,&K); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%lld",&g[i][j]); } } dp[1][1][g[1][1]]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(auto k:dp[i%2][j])//枚举出目前的全部状态，以得到下一个状态 { if(i+1<=n) { LL now1=k.first^g[i+1][j]; dp[(i+1)%2][j][now1]+=k.second; } if(j+1<=m) { LL now2=k.first^g[i][j+1]; dp[i%2][j+1][now2]+=k.second; } } } if(i!=n) { for(int j=1;j<=m;j++) dp[i%2][j].clear(); } } cout<

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

你可能感兴趣的文章