1 #include
      
        2 using namespace std; 3 int n,m,num[105],a[105][105]; 4 int main() 5 { 6     scanf("%d%d",&n,&m); 7     for(int i=1;i<=m;i++) 8     { 9         int item=1;10         for(int j=1;j<=n;j++)11         {12             scanf("%d",&a[i][j]);13             if(a[i][item]
       
        num[item]) item=i;19     printf("%d\n",item);20     return 0;21 }
       
      

 

没注意输出最小的WA了一次。。。

1 #include
      
        2 using namespace std; 3 int main() 4 { 5     int n,a; scanf("%d%d",&n,&a); 6     if(n==1) 7     { 8         puts("1"); 9         return 0;10     }11     else if(a==n)12     {13         printf("%d\n",a-1);14         return 0;15     }16     else if(a==1)17     {18         printf("%d\n",a+1);19         return 0;20     }21     int ans1=a-1,ans2=a+1;22     printf("%d\n",ans1-1>=n-ans2 ? ans1:ans2);23     return 0;24 }
      

 

题目大意：给你一个字符串，每次操作将两个相邻的点变成一个。 现在有m个操作，每个操作有一个 pos，一个c

是将pos位的字符变成c，问你这样需要几次操作。

 

思路：我们要知道一个串需要几次操作只需要知道这个串有多少个点 ，有多少段点，如果有m个点，有n段点，那么需要的操作数为m-n，然后改变字符的时候分类讨论一下就好啦。

1 #include
      
        2 using namespace std; 3 const int N=3e5+5; 4 char s[N]; 5 int n,m,num,cnt; 6 int main() 7 { 8     scanf("%d%d",&n,&m); 9     scanf("%s",s+1);10     for(int i=1;i<=n;i++)11     {12         if(s[i-1]!='.' && s[i]=='.') cnt++;13         if(s[i]=='.') num++;14     }15     while(m--)16     {17         int pos; char ss[3];18         scanf("%d%s",&pos,ss);19         if(ss[0]=='.')20         {21             if(s[pos]!='.')22             {23                 num++;24                 if(s[pos-1]=='.' && s[pos+1]=='.') cnt--;25                 else if(s[pos-1]!='.' && s[pos+1]!='.') cnt++;26             }27             s[pos]=ss[0];28         }29         else30         {31             if(s[pos]=='.')32             {33                 num--;34                 if(s[pos-1]=='.' && s[pos+1]=='.') cnt++;35                 else if(s[pos-1]!='.' && s[pos+1]!='.') cnt--;36             }37             s[pos]=ss[0];38         }39         //printf("%d %d\n",num,cnt);40         printf("%d\n",num-cnt);41     }42     return 0;43 }
      

 

题目大意：给你一棵树，每个节点对应一个字符，有m个询问，每个询问里边有一个v，一个h，v表示一个节点，h表示深度

问你在以v为根的子树中所有深度为h的点对应的字符能不能构成回文串。

 

在线：先对树进行dfs，过程中用dfs序找出每个节点的子树区间，将每个节点的dfs序放入对应的f[ i ][ j ]中，f[ i ][ j ]表示深度为i，对应字符为j+'a'。

然后对于每次询问，我们在f[ i ][ h ] (0<=i<26) 中二分找出l[v]-r[v]之间有多少个数，记录有多少个是奇数。

如果奇数的个数>1 则NO 否则 YES。

1 #include
      
        2 using namespace std; 3 const int N=5e5+5; 4 vector
       
         f[N][26]; 5 struct edge 6 { 7     int to,nx; 8 }e[N]; 9 int l[N],r[N],n,m,dfn,head[N],tot;10 char s[N];11 void add(int f,int t)12 {13     e[tot].to=t; e[tot].nx=head[f];14     head[f]=tot++;15 }16 void dfs(int v,int deep)17 {18     l[v]=++dfn;19     f[deep][s[v]-'a'].push_back(dfn);20     for(int i=head[v];~i;i=e[i].nx)21     {22         int u=e[i].to;23         dfs(u,deep+1);24     }25     r[v]=dfn;26 }27 int main()28 {29     memset(head,-1,sizeof(head));30     scanf("%d%d",&n,&m);31     for(int i=2;i<=n;i++)32     {33         int fa; scanf("%d",&fa);34         add(fa,i);35     }36     scanf("%s",s+1);37     dfs(1,1);38     while(m--)39     {40         int v,h,cnt=0,sum=0; scanf("%d%d",&v,&h);41         for(int i=0;i<26;i++)42         {43             int pos1=lower_bound(f[h][i].begin(),f[h][i].end(),l[v])-f[h][i].begin();44             int pos2=lower_bound(f[h][i].begin(),f[h][i].end(),r[v]+1)-f[h][i].begin();45             if((pos2-pos1)&1) cnt++;46             if(cnt>1) break;47         }48         if(cnt>1) puts("No");49         else puts("Yes");50     }51     return 0;52 }
       
      

 

离线：对树进行dfs，将询问按深度分层，点按深度分成再按字符分类。然后用树状数组维护节点个数。

1 #include
      
        2 #define pii pair
       
         3 #define fi first 4 #define se second 5 #define mk make_pair 6 using namespace std; 7 const int N=5e5+5; 8 int n,m,dfn,l[N],r[N],up,ans[N],head[N],tot; 9 char s[N];10 vector
        
          Q[N];11 vector
         
           D[26][N];12 struct BIT13 {14     int a[N];15     void modify(int x,int v)16     {17         for(int i=x;i<=n;i+=i&-i) a[i]+=v;18     }19     int query(int x)20     {21         int ans=0;22         for(int i=x;i>0;i-=i&-i) ans+=a[i];23         return ans;24     }25 }bit;26 struct edge27 {28     int to,nx;29 }e[N];30 void add(int f,int t)31 {32     e[tot].to=t; e[tot].nx=head[f];33     head[f]=tot++;34 }35 void dfs(int v,int deep)36 {37     up=max(up,deep); l[v]=++dfn;38     D[s[v]-'a'][deep].push_back(dfn);39     for(int i=head[v];~i;i=e[i].nx) dfs(e[i].to,deep+1);40     r[v]=dfn;41 }42 int main()43 {44     memset(head,-1,sizeof(head));45     scanf("%d%d",&n,&m);46     for(int i=2;i<=n;i++)47     {48         int fa; scanf("%d",&fa);49         add(fa,i);50     }51     scanf("%s",s+1);52     dfs(1,1);53     for(int i=1;i<=m;i++)54     {55         int v,h; scanf("%d%d",&v,&h);56         Q[h].push_back(mk(v,i));57     }58     for(int i=1;i<=up;i++)59     {60         for(int k=0;k<26;k++)61         {62             for(int j:D[k][i]) bit.modify(j,1);63             for(pii j:Q[i])64             {65                 int cur=bit.query(r[j.fi])-bit.query(l[j.fi]-1);66                 if(cur&1) ans[j.se]++;67 68             }69             for(int j:D[k][i]) bit.modify(j,-1);70         }71     }72     for(int i=1;i<=m;i++) printf("%s\n",ans[i]<=1 ? "Yes":"No");73     return 0;74 }
         
        
       
      

 

题目大意：给你一个n*m的图(1<=n,m<=500) ，图由字符构成，现在你在(1,1)的位置，想走到(n,m)的位置，问你有多少种走法使路径构成回文串。

 

思路：动态规划题，其实题目相当于两个人分别从(1,1),(n,m)开始走，且只能走向字符相同的位置，我们可以用dp[cnt][x1][y1][x2][y2]表示第cnt步的时候，第一个点在(x1,y1)，第二个点在(x2,y2)时的方案数。但是很明显空间开不下，我们可以用滚动数组来进行优化，这样就变成了dp[2][x1][y1][x2][y2]。还是过大，其实如果我们知道了步数，知道了x的坐标就能推出y的坐标，最后变成了dp[2][x1][x2]。    状态转移方程为:

dp[cnt][x1][y1][x2][y2]+=dp[cnt-1][x1-1][y1][x2+1][y2]

dp[cnt][x1][y1][x2][y2]+=dp[cnt-1][x1-1][y1][x2][y2+1]

dp[cnt][x1][y1][x2][y2]+=dp[cnt-1][x1][y1-1][x2+1][y2]

dp[cnt][x1][y1][x2][y2]+=dp[cnt-1][x1][y1-1][x2][y2+1]

最后路径长度为奇数偶数的时候分类一下就好啦。

#include
      
       using namespace std;const int N=505;const int mod=1e9+7;char s[N][N];int n,m,dp[2][N][N];inline void MOD(int &x){
    if(x>=mod) x-=mod;}int solve(){    if(s[1][1]!=s[n][m]) return 0;    dp[1][1][m]=1; int c=1,up=(n+m)>>1,ans=0;    for(int k=1;k
       
        n || y1>n || y2<1 || y1>y2) continue;                if(s[y1][x1]!=s[y2][x2]) continue;                if(x1>1 && x2
        
         1 && y2
         
          1 && x2
          
           1 && y2