A.区间最大值
https://ac.nowcoder.com/acm/contest/30896/A
https://ac.nowcoder.com/acm/contest/30896/A
由题目中的n%i容易想到整除分块,也就是n/i,再次发现由于我们按照n/i的值对数组进行分块,每一块的元素的n%i的余数都是递减的(很容易证明,因为n/i结果相等的区间,n不变而i递增,会导致n%i下降),然后每次我们对于每次询问去暴力遍历每一块的的左端点(最大值).取最大值即可.(建议学一学整除分块).
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
using namespace std;
int arr[200005];
map<int,int>ma;
int main()
{
int t,n,cnt=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
scanf("%d",&t);
for(int i=0;i<n;i++)
{
if(!ma.count(arr[i]/t))
{
ma[arr[i]/t]=1;
cnt++;
}
}
printf("%d",cnt);
return 0;
}B.模块改造
https://ac.nowcoder.com/acm/contest/30896/Bhttps://ac.nowcoder.com/acm/contest/30896/B
签到模拟.
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<string>
using namespace std;
void print(int st,int en)
{
int sth,enh;
sth=st/2;
enh=en/2;
if(sth<10)
printf("0");
printf("%d:",sth);
if(st%2==0)
printf("00");
else
printf("30");
printf(" - ");
if(enh<10)
printf("0");
printf("%d:",enh);
if(en%2==0)
printf("00");
else
printf("30");
printf("\n");
}
int main()
{
string str;
int flag=0,st=-1,en=-1,cont=0;
cin>>str;
for(int i=0;i<str.size();i++)
{
if(cont==0&&str[i]=='1')//未开始
{
cont=1;
flag=1;
st=i,en=i+1;
}
else if(cont==1&&str[i]=='1')
{
en++;
}
if(cont==1&&str[i]=='0')
{
print(st,en);
st=-1,en=-1;
cont=0;
}
}
if(st!=-1&&en!=-1)
print(st,en),flag=1;
if(flag==0)
printf("00:00 - 00:00");
return 0;
}E.爬塔
https://ac.nowcoder.com/acm/contest/30896/Ehttps://ac.nowcoder.com/acm/contest/30896/E我们可以用一个长度为10的set去存每对满足题目条件的区间左右的端点,set[i]中i的含义是区间的长度.这样记录自动排序后,用lower_bound去查找即可.
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#include <utility>
using namespace std;
set<pair<int,int>>se[12];
void solve()
{
int l,r;
scanf("%d%d",&l,&r);
for(int i=10;i>=1;i--)
{
auto it=se[i].lower_bound({l,l});
if(it->first>=l&&it->second<=r)
{
cout<<i<<"\n";
return ;
}
}
cout<<"0"<<"\n";
return ;
}
int main()
{
int n,m;
string str;
scanf("%d",&n);
cin>>str;
str="1"+str;
for(int i=1;i<=n;i++)
{
int ans=1;
for(int j=i;j<=min(n,i+9);j++)
{
if(str[j]=='1')
ans++;
else if(str[j]=='0')
ans--;
if(ans<=0)
break;
//cout<<i<<" "<<j<<" "<<ans<<"\n";
if(ans==1)
{
se[j-i+1].insert({i,j});
//cout<<i<<" "<<j<<"\n";
}
}
}
scanf("%d",&m);
while(m--)
solve();
return 0;
}F.一个很大的数
登录—专业IT笔试面试备考平台_牛客网https://ac.nowcoder.com/acm/contest/30896/F
?如图,我们可以将原有的每一种情况和新的情况相乘组合出新的情况,新的情况和老的情况不会重复,一起构成已有情况,继续循环下去即可.按照循环计算ans=ans+(ans*2*y)(y是每个素数的次数,乘以2是因为每次可以组成(1,k)和(k,1)两种组合).
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define int long long
using namespace std;
int qmi(int x,int y,int mod)
{
int res=1;
while(y)
{
if(y&1)
res=res*x%mod;
y>>=1;
x=x*x%mod;
}
return res;
}
signed main()
{
int t,n,x,y;
scanf("%lld",&t);
while(t--)
{
int ans=1;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&x,&y);
ans=((ans%1000000007+(ans*2%1000000007*y%1000000007))%1000000007);
}
printf("%lld\n",ans);
}
return 0;
}H.变换01串
登录—专业IT笔试面试备考平台_牛客网https://ac.nowcoder.com/acm/contest/30896/H读题,其实题目说可以两个方向操作,只需要从一个方向进行即可,其实是一样的.用线段树的方法来进行区间操作.首先解决最初始的查询问题,查询时利用线段树,线段树维护每个区间的左右范围,左右端点的值,还有贡献值,在计算两个区间的父节点的值时,需要将两个区间合并,那么看左边区间的右端点和右间左端点是否相同,若相同则表明这两个区间可以合并,直接将两者相加.而当不相等时,说明此时需要进行取反操作,则在两区间贡献相加的情况下还要多加1.然后就是区间修改,因为是区间修改,所以想到懒人标记,只是这里是每次修改将左右端点的值和懒人标记的值^=1即可.
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
struct node
{
int l,r;
int sum,lz;
int lval,rval;
}tree[400005];
int arr[100005];
int n,m;
void push_down(int node)
{
if(tree[node].lz)
{
tree[node<<1].lval^=1;
tree[node<<1|1].lval^=1;
tree[node<<1].rval^=1;
tree[node<<1|1].rval^=1;
tree[node<<1].lz^=1;
tree[node<<1|1].lz^=1;
tree[node].lz=0;
}
return ;
}
void push_up(int node)
{
if(tree[node<<1].rval==tree[node<<1|1].lval)
tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum;
else
tree[node].sum=tree[node<<1].sum+tree[node<<1|1].sum+1;
tree[node].lval=tree[node<<1].lval;
tree[node].rval=tree[node<<1|1].rval;
return ;
}
void build_tree(int l,int r,int node)
{
tree[node].l=l;
tree[node].r=r;
if(l==r)
{
tree[node].sum=0;
tree[node].lval=arr[l];
tree[node].rval=arr[l];
tree[node].lz=0;
return ;
}
int mid=(l+r)/2;
build_tree(l,mid,node<<1);
build_tree(mid+1,r,node<<1|1);
push_up(node);
}
int query(int l,int r,int node)
{
int res=0,flag=0;
if(l<=tree[node].l&&tree[node].r<=r)
return tree[node].sum;
int mid=(tree[node].l+tree[node].r)/2;
push_down(node);
if(l<=mid)
res+=query(l,r,node<<1),flag=1;
if(r>mid)
{
if(flag==1)
{
if(tree[node<<1].rval==tree[node<<1|1].lval)
res+=query(l,r,node<<1|1);
else
res+=(query(l,r,node<<1|1)+1);
}
else if(flag==0)
res+=query(l,r,node<<1|1);
}
return res;
}
void update(int l,int r,int node)
{
if(l<=tree[node].l&&tree[node].r<=r)
{
tree[node].lz^=1;
tree[node].lval^=1;
tree[node].rval^=1;
return ;
}
int mid=(tree[node].l+tree[node].r)/2;
push_down(node);
if(l<=mid)
update(l,r,node<<1);
if(r>mid)
update(l,r,node<<1|1);
push_up(node);
}
int main()
{
int op;
scanf("%d%d",&n,&m);
string s;
cin>>s;
for(int i=1;i<=n;i++)
arr[i]=(s[i-1]-'0');
build_tree(1,n,1);
while(m--)
{
int l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==1)
printf("%d\n",query(l,r,1));
else if(op==2)
update(l,r,1);
}
return 0;
}I.V字钩爪
登录—专业IT笔试面试备考平台_牛客网https://ac.nowcoder.com/acm/contest/30896/I思维题,题意是不限操作次数,也就是尽量取完.我们可以把石头按照间隔来进行分组,将i,i+k,i+2*k......i+n*k(k为间隔大小,i为初始序号,i+n*k<=石头总数)分为一组.分组后,为了尽量让答案更大,只需要尽量取完即可.我们必须尽量让石头都是能够在距离一定的情况下成对.当某组里面的石头为偶数个时,就可以全部取完.为奇数个时,一定有一个取不了,为了让贡献最大,那么这一个肯定是在这一组的奇数位置上,去奇数位置上最小的减去,因为这样才能使剩下的石头在题目给定距离下成对.
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define int long long
using namespace std;
int arr[1000006];
signed main()
{
int n,k,ans=0;
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%lld",&arr[i]);
ans+=arr[i];
}
for(int i=1;i<=k;i++)
{
int minn=1e9,tt=0;
for(int j=0;i+j*k<=n;j++)
{
tt++;
if(j%2==0)
minn=min(minn,arr[i+j*k]);
}
if(tt%2==1)
ans-=minn;
}
printf("%lld",ans);
return 0;
}继续努力