Codeforces Round #496 (Div. 3) ABCDE1

 //B. Delete from the Left

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <vector>

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int N=2e5+;

 char a[N],b[N];

 int main()

 {

     scanf("%s%s",a,b);

     int lena=strlen(a);

     int  lenb=strlen(b);

     int i=lena-,j=lenb-;

     int sum=;

     while(a[i]==b[j]&&i>=&&j>=)//s[-1]与p[-1]是不确定的

     {   //因此加上i>=0&&j>=0  和下面的D题相似

         sum++;

         i--,j--;

     }

     printf("%d\n",lena+lenb-*sum);

     return  ;

 }

 //C. Summarize to the Power of Two

 /*

2^(n-1) x 2^n 2^(n+1）

因为x<2^n,所以2*x<2^(n+1)，那么x+y(0<x<y)一定位于

2^(n-1)和2^(n+1)之间。若x+y为2的指数幂，那么必定是2^n.

*/
   #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <set>

 #include <map>

 #include <vector>

 #include <cmath>

 using namespace std;

 typedef long long ll;

 const int inf=0x3f3f3f3f;

 const  int  N=;

 ll  n;

 ll  a[N];

 map<ll,ll>mp;

 set<ll>s;

 int  main()

 {

     scanf("%lld",&n);

     for(int  i=;i<n;i++)

     {

         scanf("%lld",&a[i]);

         mp[a[i]]++;

     }

     sort(a,a+n);//为了二分

     s.clear();

     for(int i=;i<n;i++)

     {

         ll ans=log2(a[i]);

         ll ret=pow(,ans+)-a[i];

         if(binary_search(a,a+i,ret))

         {  //二分查找[) ，不会取到自己

             s.insert(a[i]);

             s.insert(ret);//set可以去重

         }

     }

     ll cnt=;

     for(auto it=s.begin();it!=s.end();it++){

         cnt+=mp[*it];

     }

     printf("%lld\n",n-cnt);

     return ;

 }

 /*

 下面是简单的二分查找函数

 scanf("%d",&n);

 for(int  i=0;i<n;i++)

 {

     scanf("%lld",&a[i]);

 }

 ll  m;

 while(~scanf("%lld",&m)){

 if(binary_search(a+1,a+4,m)){//[)

     cout<<"yes\n";

 }

     else{

         cout<<"no\n";

     }

 }

 return 0;

 }

 5

 1 2 3 4 5

 1

 no

 2

 yes

 3

 yes

 4

 yes

 5

 no

 */

 //C. Summarize to the Power of Two

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include  <set>

 #include <map>

 #include <vector>

 #include <cmath>

 using namespace std;

 typedef long long ll;

 const int inf=0x3f3f3f3f;

 ll n;

 map<ll,ll>mp;

 const int M=1.3e5+;

 ll a[M];

 int main()

 {

     scanf("%lld",&n);

     for(ll i=;i<n;i++)

     {

         scanf("%lld",&a[i]);

         mp[a[i]]++;

     }

     ll ans=;

     bool flag;

     for(ll i=;i<n;i++)

     {

         flag=;

         mp[a[i]]--;//将a[i]先取出

         //为了避免a[i]与(1<<j)-a[i]是同位置

         //当然也有其他的方法

         //if(mp[(1<<j)-a[i]]==1&&a[i]!=(1<<j)-a[i]||mp[(1<<j)-a[i]]>1)

        //出现多次，可以互相替换，1次只要两者不等，就一定不是同一位置

         //不相等一定不是同位置

         for(int j=;j<=;j++)

         {

             if(mp[(<<j)-a[i]])

             {

                 flag=;

                 break;

             }

         }

         if(!flag)

             ans++;

         mp[a[i]]++;//再恢复

     }

     printf("%lld\n",ans);

     return ;

 }

 ////D. Polycarp and Div 3

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include  <set>

 #include <map>

 #include <vector>

 #include <cmath>

 using namespace std;

 typedef long long ll;

 const int inf=0x3f3f3f3f;

 const int N=2e5+;

 ll dp[N];

 char s[N];

 int main()

 {

     scanf("%s",s+);

     /*

     if(s[1]=='1'&&s[2]=='1'){

         if(strlen(s+1)==2){

             printf("0\n");

             return 0;

         }

     }

     */

     int lens=strlen(s+);

     memset(dp,,sizeof(dp));

     if((s[]-'')%==){

         dp[]=;

     }

     //int i,j,k,sum;

     for( int i=;i<=lens;i++)

     {

          dp[i]=dp[i-];

         //cout<<"iii"<<i<<endl;

         for( int j=i-;j>=;j--)//起初没加j>=0

         { //如dp[-1]=dp[0]=dp[1]=0 。数组的负下标问题

          //可能令最终的结果有问题，也会时间更长

             if(dp[j]!=dp[i-])

                 break;

             if(s[j+]==''&&i-j>)

                 continue;

             //cout<<dp[j]<<" "<<dp[i-1]<<endl;

             int  sum=;

                for(int  k=i;k>=j+;k--)

                {

                    sum=(sum+(s[k]-''))%;

                }

                //cout<<"sum "<<sum<<endl;

                    if(sum==)

                    {

                        dp[i]=max(dp[i],dp[j]+);

                    }

         }

         //cout<<i<<" "<<dp[i]<<endl;

     }

     printf("%lld\n",dp[lens]);

     return  ;

 }

 //D. Polycarp and Div 3

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include  <set>

 #include <map>

 #include <vector>

 #include <cmath>

 using namespace std;

 typedef long long ll;

 const int inf=0x3f3f3f3f;

 const int N=2e5+;

 int main()

 {

     char s[N];

     scanf("%s",s);

     int sum=,cnt=,tmp;

     int ans=;

     for(int i=;s[i];i++)

     {

         tmp=(s[i]-'')%;

         sum+=tmp;

         cnt++;

         if(tmp==||sum%==||cnt==)

         {

             ans++;

             sum=cnt=;

         }

     }

     printf("%d\n",ans);

     return  ;

 }

 // E1 - Median on Segments (Permutations Edition)

 //区间内大于m的数的个数-小于m的数的个数（sum）==0or1

 //在m出现之前依次记录sum，用map存储每个sum出现的个数

 //等到m出现后，每当遇到一个sum，ans+=(sum出现的次数)+(sum-1出现的次数)

 //sum sum 区间内大于m的数的个数-小于m的数的个数==0

 //sum(前面) sum-1(后面) 区间内大于m的数的个数-小于m的数的个数==1

 //m出现后不再增加sum出现的次数,因为那些区间不会包含m

 //符合条件的区间一定要包含m

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include  <set>

 #include <map>

 #include <vector>

 #include <cmath>

 using namespace std;

 typedef long long ll;

 const int inf=0x3f3f3f3f;

 const int N=2e5+;

 int n,m,a[N];

 map<ll,ll>mp;

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<n;i++)

     {

         scanf("%d",&a[i]);

     }

    ll sum=;

     mp[]=;

     bool flag=;

     ll ans=;

     for(int i=;i<n;i++)

     {

         if(a[i]<m)

             sum--;

         else if(a[i]>m)

             sum++;

         if(a[i]==m)

             flag=;

          if(flag){

              ans+=mp[sum]+mp[sum-];

          }

          else{

              mp[sum]++;

          }

     }

     printf("%lld\n",ans);

     return ;

 }

巴特西

Codeforces Round #496 (Div. 3) ABCDE1

最新文章

热门文章