题解 | #打靶#
打靶
https://ac.nowcoder.com/acm/contest/72389/A
A
模拟，判断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";
}
}
B
设一个合法解为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:;
}
}
C
贪心
题目可以转换为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";
}
}
D
注意题意: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";
}
}
投递虾皮信息等公司10个岗位
