头像

像风一样დ

204




在线 


最近来访(18)
用户头像
墨染樱飞
用户头像
潘潘_the_panda
用户头像
ranok
用户头像
我想要桃
用户头像
沙烬
用户头像
XUGUOHAO
用户头像
choumm
用户头像
asdber

活动打卡代码 AcWing 4083. 最大公约数

#include<iostream>
#include<string>
#include<limits.h>
#include<algorithm>
#include<cmath>
using namespace std;
 int cnt[100010];
 int main(){
    int n,res=1;cin>>n;
     for(int i=1;i<=n;i++){
        int x;cin>>x;cnt[x]++;
     } 
     for(int i=2;i<=100000;i++){
        int ans=0;
        for(int j=i;j<=100000;j+=i)
            ans+=cnt[j];
        res=max(res,ans);
     }
     cout<<res;
 }


活动打卡代码 AcWing 4082. 子序列

#include<iostream>
#include<string>
#include<limits.h>
using namespace std;

int dp[26];
string s; 
int cnt = 0;

int main()
{
    string s;//QSQAQAAQAQAQ21SSADASQSQ;
    cin >>s;
    for(int i=0;i<s.length();i++)
   {
    if(s[i]=='Q')
    {
        for(int j=i+1;j<s.length();j++)
        {
         if(s[j]=='A')
         {
            for(int k=j+1;k<s.length();k++)
              if(s[k]=='Q')
              cnt++;
         }
        }

    }


   }
     cout<<cnt<<endl;
    return 0;
 } 



题目描述

给定一个由小写字母构成的字符串 s。

字符 c 被称为字符串 s 的 k 显性字符,当且仅当字符串 s 的所有长度不小于 k 的子串都包含字符 c。

对于给定的字符串 s,请你找到一个最小的 k,使得 s 中至少存在一个 k 显性字符。

样例

输入样例1:
abacaba
输出样例1:
2
输入样例2:
zzzzz
输出样例2:
1
输入样例3:
abcde
输出样例3:
3

C++ 代码

/寻找相同字符的非连续间隔、该字符首次出现的位置与串头的距离和该字符最后出现的位置与字符串尾的距离 中的最大值
再找到所有字符的此值的最小值
/

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

int dp[26];
string s;
int main()
{
int flag=0;
cin>>s;
int l=s.length()-1;
int ress=INT_MAX,cnt=0;
for(int i=0;i<=25;i)
{
dp[i]=0;
int t=0;
for(int j=0;j<s.length();j
)
{
if(s[j]==i+’a’)
{
if(dp[i]==0) //如果是第一次发现此字符 记录串头到此字符下标的距离。
{
cnt++; // 记录是否所有字符都相同
dp[i]=j+1;
t=j;
continue;
}
else
{
flag=1; //记录是否所有字符都不相同
if(j-t!=1)
dp[i]=max(dp[i],j-t); //记录相同字符 非连续的间隔的最小值
t=j;
}
}
}
dp[i]=max(dp[i],l-t+1); // 此字符最后出现的位置 到字符串尾的距离也要参与DP
ress=min(dp[i],ress);
}

if(cnt<=1)  cout<<1<<endl;                     //如果所有字符相同输出1

else if(flag==0) cout<<(l+1)/2+1<<endl; //如果所有字符都不相同 则输出字符串长度的一半 向上取整
else cout<<ress<<endl; //正常情况则输出结果
return 0;
}



活动打卡代码 AcWing 4077. k显性字符

ddddddddd

#include<iostream>
#include<string>
#include<limits.h>
using namespace std;

int dp[26];
string s; 
int main()
{
    cin>>s;
    int l=s.length()-1;
    int ress=INT_MAX,cnt=0,flag2=0;
    for(int i=0;i<=25;i++)
    {
        dp[i]=0;
        int t=0;
        for(int j=0;j<s.length();j++) 
         {
               if(s[j]==i+'a')
               {
                    if(dp[i]==0)
                    {
                        cnt++; 
                        dp[i]=j+1;
                        t=j;
                        continue;
                    }
                   else
                   {
                       flag2=1;
                       if(j-t!=1)
                       dp[i]=max(dp[i],j-t);
                       t=j;
                    }
               } 
         }
          dp[i]=max(dp[i],l-t+1);       
          ress=min(dp[i],ress);
    }
    if(cnt<=1)  cout<<1<<endl;
   else if(flag2==0)  cout<<(l+1)/2+1<<endl;
       else         cout<<ress<<endl; 
    return 0;
 } 


活动打卡代码 AcWing 1024. 装箱问题

#include<iostream>
#include<algorithm>
#include<limits.h>

using namespace std;

const int  N =20002;

int dp[N]={INT_MIN},v[N];
int V,n;
int main()
{
    cin>>V>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i];

    dp[0]=0;
     for(int i=1;i<=n;i++)
      for(int j=V;j>=v[i];j--)
             dp[j]=max(dp[j],dp[j-v[i]]+v[i]);





    cout<<V-dp[V]<<endl;




    return 0;
}


活动打卡代码 AcWing 423. 采药

#include<iostream>
#include<algorithm>
#include<limits.h>

using namespace std;

const int N=1010;

int dp[N][N]={INT_MIN},t[N],w[N];

int T,M ;
int main()
{
    cin>>T>>M; 
    for(int i=1;i<=M;i++)
      cin>>t[i]>>w[i];
     dp[0][0]=0;  
    for(int i=1;i<=M;i++)
        for(int j=0;j<=T;j++)
            {
              dp[i][j]=dp[i-1][j];
              if(j>=t[i])
              dp[i][j]=max(dp[i][j],dp[i-1][j-t[i]]+w[i]);

            }
        int res =0;
        for(int i=0;i<=T;i++)
          res=max(res,dp[M][i]);

    cout<<res<<endl;
    return 0;
}


新鲜事 原文

AcWing 1097. 池塘计数 还是设置两个方向数组来深搜来的实在 y总的pair<>型和队列操作多少写的不太习惯 #include<iostream> #include<algorithm> #include<limits.h> #include<cstring> /* 还是设置两个方向数组来深搜来的实在 y总的pair<>型和队列操作多少写的不太习惯 */ using namespace std; const int N = 1111; const int M =N*N; int n,m; char map[N][N]; int dx[8]={-1,-1,-1,0,1,1,1,0},dy[8]={-1,0,1,1,1,0,-1,-1}; void dfs(int x,int y) { map[x][y]='.'; for(int i=0;i<8;i++) { if(x+dx[i]<0 || x+dx[i]>=n || y+dy[i]<0 || y+dy[i]>=m) continue; if(map[x+dx[i]][y+dy[i]]=='W') { map[x+dx[i]][y+dy[i]]='.'; // printf("坐标 %d %d 已被BLOODFILL\n",x+dx[i],y+dy[i]); dfs(x+dx[i],y+dy[i]); } } } int main() { cin>>n>>m; for(int i=0;i<n;i++) cin>>map[i]; int count=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { if(map[i][j]=='W') { // printf("发现一处未被处理的坐标 %d %d\n",i,j); count++; //cout<<count<<endl; dfs(i,j); } } cout<<count<<endl; return 0; }


活动打卡代码 AcWing 1010. 拦截导弹

优化一下代码 上个代码 在求第二问的代码中 在贪心时 对于每个大于等于当前数的子序列中 还额外循环求解了一个最小值 但其实在贪心的过程中dp数组就是单调递增的 所以第一个大于等于当前数的子系列的最后一个数就是最小的 故可以省去求最小值那几步

#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;
const int N =1111;
int dp[N],a[N],dp2[N];
int main()
{
  int n=0,res=0;
  while(cin>>a[n])  
  {
   dp[n]=1;
   n++;
  }
  for(int i=0;i<n;i++)
      for(int j=0;j<i;j++)
  {
      if(a[j]>=a[i])
        dp[i]=max(dp[i],dp[j]+1);
      res = max(dp[i],res);
  }
  int t=0;
  dp2[++t]=a[0];
  for(int i=1;i<n;i++)
  {
     int flag=1;
        for(int j=1;j<=t;j++)
           if(a[i]<=dp2[j])
               {
                  dp2[j]= a[i];
                  flag=0;
                  break;
               }
          if(flag)
          dp2[++t]=a[i];
    }

  cout<<res<<endl<<t<<endl;
  return 0; 

 } 


活动打卡代码 AcWing 1010. 拦截导弹

对于第二问
遍历导弹数组﹐ 枚举当前所有子序列 将当前导弹高度插入到满足以下条件的序列中:1.该子序列的最后一个数大于当前高度,
2.是满足条件1的所有子序列中最后一个数最小的一个序列
只用到一维dp数组 我们只记录并更新每个子序列的最后一个数 最后的dp数组长度即是最后的结果
```

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int N =1111;
int dp[N],a[N],dp2[N];
int main()
{
int n=0,res=0;
while(cin>>a[n])
{
dp[n]=1;
n;
}
for(int i=0;i[HTML_REMOVED]=a[i])
dp[i]=max(dp[i],dp[j]+1);
res = max(dp[i],res);
}
int t=0;
dp2[
t]=a[0];
for(int i=1;i<n;i)
{
int flag=0,min=INT_MAX;
for(int j=1;j<=t;j
)
if(a[i]<=dp2[j])
if(dp2[j]<=min)
{
min=dp2[j];
flag=j;
}
if(flag)
dp2[flag]=a[i];
else
dp2[++t]=a[i];
}

cout<<res<<endl<<t<<endl;
return 0;

}
```



活动打卡代码 AcWing 1010. 拦截导弹

#include<iostream>
#include<algorithm>
using namespace std;
const int N =1111;
int dp[N],a[N],dp2[N];
int main()
{
  int n=0,res=0;
  while(cin>>a[n])  
  {
   dp[n]=1;
   n++;
  }
  for(int i=0;i<n;i++)
      for(int j=0;j<i;j++)
  {
      if(a[j]>=a[i])
        dp[i]=max(dp[i],dp[j]+1);
      res = max(dp[i],res);
  }
  int count=0;
  for(int i=0;i<n;i++)
  {
      int k=0;
      while(k<count && dp2[k]<a[i])
      k++;
      dp2[k]=a[i];
      if(k>=count)  count ++;

   } 
  cout<<res<<endl<<count<<endl;
  return 0; 

 }