首页 > 其他 > 详细

10.22 simulated match

时间:2017-10-22 23:18:46      阅读:431      评论:0      收藏:0      [点我收藏+]

技术分享

 

#include<cstdio>
#include<cstring>
#define init(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout); 
using namespace std;
int T,n,m;char s[30010],t[30010];
int main(){init("string");
    int i,j,k,l,u;scanf("%d",&T);
    while(T--){scanf("%s%s",&s,&t);
       n=strlen(s),m=strlen(t);
       for(i=j=0;i<n;i=k,j=l){u=0;
          for(k=i;k<n &&(s[k]==*||s[k]==s[i]);k++)
            if(s[k]==*)u++;
          for(l=j;l<m&&t[l]==t[j];l++);
          if(!(s[i]==t[j]&&k-i-u<=l-j&&(u||k-i==l-j)))break;
        }i<n||j<m?printf("No\n"):printf("Yes\n");}return 0;
}

 

 


 

 

 

技术分享

 

#include<cstdio>
using namespace std;
int n,m,f[400010],l[100010],r[100010],x[100010],p;
#define init(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout); 
void add(int i,int j,int k,int l,int r,int x){if(l<=j&&k<=r)f[i]|=x;
    else{if(l<=(j+k>>1))add(i<<1,j,j+k>>1,l,r,x);
       if(r>(j+k>>1))add(i<<1|1,(j+k>>1)+1,k,l,r,x);}}
int sum(int i,int j,int k,int l,int r){if(l<=j&&k<=r)return f[i];
    else{int p=(1<<30)-1;if(l<=(j+k>>1))p&=sum(i<<1,j,j+k>>1,l,r);
       if(r>(j+k>>1))p&=sum(i<<1|1,(j+k>>1)+1,k,l,r);
       return p;}}
int main()
{init("or");int i,j,k;scanf("%d%d",&n,&m);
    for(p=1;p<n;p<<=1);
    for(i=1;i<=m;i++)scanf("%d%d%d",&l[i],&r[i],&x[i]),x[i]^=(1<<30)-1,add(1,1,p,l[i],r[i],x[i]);
    for(i=1;i<p;i++)f[i<<1]|=f[i],f[i<<1|1]|=f[i];
    for(i=p-1;i>0;i--)f[i]=f[i<<1]&f[i<<1|1];
    for(i=1;i<=m;i++)if(sum(1,1,p,l[i],r[i])!=x[i])break;
    if(i<=m)printf("No\n");
    else{printf("Yes\n");
       for(i=1;i<=n;i++)printf("%d ",f[p+i-1]^(1<<30)-1);printf("\n");}return 0;}

  

 


 

 

 

技术分享

 

#include<cstdio>
#include<algorithm>
#define L long long
#define O(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout); 
#define fr(i,a,b)  for(int i=a;i<=b;i++)
using namespace std;
int n,m,w[100010];L s[100010];
struct goods{int v,x;}a[100010];
inline bool cmp(goods a,goods b){return a.v<b.v;}
int in(){int x=0,f=1;char c=getchar();
    for(;c<0||c>9;c=getchar())if(c==-)f=-1;
    for(;0<=c&&c<=9;c=getchar())x=(x<<3)+(x<<1)+(c^48);return x*f;}
int main(){O("shop");int i,j,l,r;L k;n=in(),m=in();
    for(i=1;i<=n;i++)a[i].v=in(),a[i].x=in();
    sort(a+1,a+n+1,cmp);
    fr(i,1,n)s[i]=s[i-1]+(L)a[i].v*a[i].x,w[i]=w[i-1]+a[i].x;
    while(m--){scanf("%lld",&k);
       for(i=n,j=0;i>0&&k>=a[1].v;){
          for(l=1,r=i;l<r;)k>=a[l+r+1>>1].v?l=(l+r+1>>1):r=(l+r+1>>1)-1;
          i=l;if(k>=s[i]){j+=w[i];break;}
          for(l=1,r=i;l<r;)k>=s[i]-s[l+r>>1]?r=(l+r>>1):l=(l+r>>1)+1;
          k-=s[i]-s[l];j+=w[i]-w[l]+k/a[l].v;k%=a[l].v;i=l-1;}
       printf("%d\n",j);}return 0;
}

 

10.22 simulated match

原文:http://www.cnblogs.com/muzu/p/7712153.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!