题解 | #打靶#_牛客博客

模拟，判断y>=x且y<=x+n-m是否成立。

#include<bits/stdc++.h>
using namespace std;
#define maxx 3000
int n,a,b,c,s,m,t,x,y;
map<int,int> M; 
pair<int,int> all[maxx];
int ans=0;
int anss=0;

int main()
{
    cin>>t;
    for(int i=1;i<=t;++i)
    {cin>>n>>m>>x>>y;
     if(y>=x&&y<=x+n-m)
     cout<<"Yes\n";
     else
     cout<<"No\n";


    }
     
   
  
}

设一个合法解为a,b,则gcd(a,b)=x,lcm(a,b)=y,而gcd(a,b)*lcm(a,b)=x*y=a*b。

则a与b是xy的约数，枚举所有约数后判断是否gcd(a,b)=x,从小到大枚举。

#include<bits/stdc++.h>
using namespace std;
#define maxx 3000
#define int long long
int n,a,b,c,s,m,t,x,y;
pair<int,int> all[maxx];
int ans=0;
int anss=0;

signed main()
{
    cin>>t;
    for(int i=1;i<=t;++i)
    {cin>>x>>y;
     int z=x*y;
     for(int i=1;i<=sqrt(z);++i)
     {
       if(z%i!=0) continue;
       if(__gcd(i,z/i)==x)
       {
        cout<<i<<" "<<z/i<<"\n";
        goto h;
       } 
     } 
     cout<<-1<<"\n";
     h:;
   

    }
     
   
  
}

贪心

题目可以转换为bi∈[ai-k,ai+k],且bi非减。

为了减少前数字对后面的影响，每个点尽量向右取和向左取且保证合法，分别判断。

#include<bits/stdc++.h>
using namespace std;
#define maxx 1200000
int n,a,b,c,s,m,t,x,y,k;
int all[maxx];
int ans=0;
int anss=0;

int main()
{
    cin>>t;
    for(int i=1;i<=t;++i)
    {cin>>n>>k;
     for(int i=1;i<=n;++i)
      cin>>all[i];
      int x=all[1]-k;
      int wr=0;
      for(int i=2;i<=n;++i)
      {
        if(all[i]+k<x) 
        {
          ++wr;
          break;
        }
        else if(all[i]-k<=x&&all[i]+k>=x) ;
        else x=all[i]-k;
      }
      x=all[1]+k;
        for(int i=2;i<=n;++i)
      {
        if(all[i]+k<x) 
        {
          ++wr;
          break;
        }
        else x=all[i]+k;
      }
      if(wr==2) cout<<"No\n";
      else cout<<"Yes\n";

    }
     
   
  
}

注意题意:1.是翻转不是反转，2.每次处理独立，而不是逐步修改。

如果1，2均满足后者，需要使用线段树来进行处理，大约如下代码，没做验证。

#include<bits/stdc++.h>
using namespace std;
#define INF 1e18
#define maxx 5080000
#define maxx2 0x3f3f3f3f
int a,b,d,k,m,t,n,ansmax,Smax,x,ans1,ans2,neww,c;
int l,r,q;
string s;
int xmax,ymax;
int pj;
int sum=0;
int all[maxx];
struct point
{
  int sum0,sum1;//连续的个数
  int ld,rd;
  int leng;
  int tag;
}JD[maxx];
int ls(int root)
{
  return 2*root;
}
int rs(int root)
{
  return 2*root+1;
}
void update_from_son(int root,int l,int r)
{
 
  int mid=(l+r)/2;
  JD[root].ld=JD[ls(root)].ld;
  JD[root].rd=JD[rs(root)].rd;
  JD[root].sum0=JD[ls(root)].sum0+JD[rs(root)].sum0;
  JD[root].sum1=JD[ls(root)].sum1+JD[rs(root)].sum1;
  JD[root].leng=JD[ls(root)].leng;
  if(JD[ls(root)].rd==JD[rs(root)].ld&&JD[ls(root)].rd==0)
  --JD[root].sum0;
 
   if(JD[ls(root)].rd==JD[rs(root)].ld&&JD[ls(root)].rd==1)
  --JD[root].sum1;
  if(JD[ls(root)].leng==mid-l+1&&JD[ls(root)].rd==JD[rs(root)].ld)
  JD[root].leng=JD[root].leng+JD[rs(root)].leng;
}
void push_down(int root)
{
  if(JD[root].tag==0) return ;
  JD[ls(root)].tag=(JD[ls(root)].tag+1)%2;
  JD[rs(root)].tag=(JD[rs(root)].tag+1)%2;
 
  JD[ls(root)].ld=(JD[ls(root)].ld+1)%2;
  JD[ls(root)].rd=(JD[ls(root)].rd+1)%2;
  swap(JD[ls(root)].sum0,JD[ls(root)].sum1);
  JD[rs(root)].ld=(JD[rs(root)].ld+1)%2;
  JD[rs(root)].rd=(JD[rs(root)].rd+1)%2;
  swap(JD[rs(root)].sum0,JD[rs(root)].sum1);
}
void build(int root,int l,int r)
{
  if(l==r) 
  {
    if(all[l]==1) JD[root].sum1=1;
    else JD[root].sum0=1;
    JD[root].ld=all[l];
    JD[root].rd=all[l];
    JD[root].leng=1;
    return;
  }
  int mid=(l+r)/2;
  build(ls(root),l,mid);
  build(rs(root),mid+1,r);
  update_from_son(root,l,r);
  
}
void modify(int root,int l,int r,int ql,int qr)
{
  if(l==ql&&r==qr)
  {
  JD[root].ld=(JD[root].ld+1)%2;
  JD[root].rd=(JD[root].rd+1)%2;
  swap(JD[root].sum0,JD[root].sum1);
  JD[root].tag=(JD[root].tag+1)%2;
    return ;
  }
  int mid=(l+r)/2;
  push_down(root);
  if(ql<=mid) modify(ls(root),l,mid,ql,min(qr,mid));
  if(qr>=mid+1) modify(rs(root),mid+1,r,max(mid+1,ql),qr);
  update_from_son(root,l,r);
}
int query(int root,int l,int r)
{
  return JD[1].sum1;
}
  
signed main()
{
    cin>>n>>q>>s; 
    for(int i=0;i<n;++i)
    all[i+1]=s[i]-'0';
     build(1,1,n);
    for(int i=1;i<=q;++i) 
     {
       cin>>l>>r;
       modify(1,1,n,l,r);
       cout<<query(1,1,n)<<"\n";
     }
   
   
   
}

正解为如下

首先处理出所有连续1段的长度，然后翻转在左右端点不一致的时候会影响端点的数值，在端点分类讨论即可。

#include<bits/stdc++.h>
using namespace std;
#define INF 1e18
#define maxx 88
#define maxx2 0x3f3f3f3f
int a,b,d,k,m,t,n,ansmax,Smax,x,ans1,ans2,neww,c;
int q;
string s;
int l,r;
int xmax,ymax;
int pj;
int sum=0;

int all[maxx];
int ans;



signed main()
{
   cin>>n>>q>>s; 
    for(int i=0;i<n;++i)
    all[i+1]=s[i]-'0';
    int x=1;
    for(int i=1;i<=n;)
    {
      x=i;
      while(++i<=n)
      {
        if(all[i]!=all[x]) 
        {
         if(all[x]==1) ++ans;
         x=i;
        break;
        }
      }

    }
    if(all[n]==1)
    ++ans;
    all[0]=all[n+1]=-1;
    for(int i=1;i<=q;++i) 
     {
      cin>>l>>r;
      int qq=ans;

      if(all[l]==0&&all[r]==1&&all[l-1]!=1) ++qq;
      if(all[l]==0&&all[r]==1&&all[r+1]!=1) --qq;
      
      if(all[l]==1&&all[r]==0&&all[l-1]!=1) --qq;
      if(all[l]==1&&all[r]==0&&all[r+1]!=1) ++qq;

    
      cout<<qq<<"\n";
     } 
  
}