A.

题目大意:

   x坐标上1~L有L个点都是整数,每v个长度就有一个灯亮着,但是有 [ l , r ] 这段区间上有列火车挡住了,问你能看到多少亮灯。

解题报告:

   大水题啊,找几个样例就会发现需要特殊处理一下左边界恰好有灯的情况。

AC代码:

#include<bits/stdc++.h>

using namespace std;
int L,v,l,r,ans;
int main()
{
	int t;
	cin>>t;
	while(t--) {
		scanf("%d%d%d%d",&L,&v,&l,&r);
		ans = (L/v) - (r/v - l/v);
		if(l%v==0) ans--;
		printf("%d\n",ans);
	}
	return 0 ;
}

 


B.

题目大意:

    一个大小为n的数组代表n个房间,数组第i个元素为1代表在第i个房间有一个热水器,可以热给范围为[i-r+1,i+r-1]范围的房间热水,问最少需要多少热水器,可以供给所有房间。

解题报告:

   模拟一下过程就好了,记得终点不是在n,而是要加一个常数。因为有那一步i=cur,所以时间不是线性的,而是近似o(n^2)了。

AC代码:

#include<bits/stdc++.h>

using namespace std;
int a[100005];
int main()
{
	int n,r,flag=1;
	cin>>n>>r;
	r--;
	for(int i = 1; i<=n; i++) scanf("%d",a+i);
	int cur = 0,now = 0,cnt = 0;
	int pos = 1;
	for(int i = 1; i<=n+2000; i++) {
		if(pos > n) break;
		if(a[i] == 1) {
			if(i-pos <= r) {
				now = i;
			}
		}
		if(i-pos > r) {
			if(now == cur) {
				flag=0;break;
			}
			cnt++;
			cur=now;
			pos = cur + r + 1;
			i=cur;
		}
	}
	if(flag == 0) puts("-1");
	else printf("%d\n",cnt);
	
	return 0 ;
}

另附一种模拟思路:(就是彻彻底底的o(n^2)了,每次都从末尾开始找,找到的第一个满足条件的一定是我们喜欢的,不过反正n很小,n^2也不怂,主要是这种思路不容易写萎了啊)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 1e3+5;
int n,r;
int a[MAX];
int main() 
{
	scanf("%d%d",&n,&r);
	for(int i=1; i<=n; i++)scanf("%d",&a[i]);
	int last = 0,num = 0;
	bool flag;
	int pos;
	while(1) {
		if(last>=n) break; 
		flag = false;
		int pp = max(last-r+1,0);
		for(int i=n; i>pp; i--) {
			if(a[i]) {
				if(i-r<=last) {
					pos = i;
					flag = true;
					break;
				}
			}
		}
		if(!flag) {
			printf("-1\n");
			return 0;
		}
		last = pos+r-1;
		num++;
	}
	printf("%d\n",num);
	return 0;
}

wjh的代码:

#include<bits/stdc++.h>
#include<queue>
using namespace std;
int a[2000];
int main() {
	int n,r;
	scanf("%d%d",&n,&r);
	for(int i=1; i<=n; i++) {
		scanf("%d",&a[i]);
	}
	int d=r;
	int flag=0;
	for(int i=r; i>=1; i--) {
		if(a[i]==1) {
			flag=i;
			break;
		}
	}
	int ans=1;
	if(flag==0) {
		printf("-1\n");
	} else {
		int wi=flag;
		int ff=0;
		while(wi+r-1<n) {
			d=wi+r+r-1;
			ff=0;
			for(int i=d; i>wi; i--) {
				if(a[i]==1) {
					ff=1;
					wi=i;
					ans++;
					break;
				}

			}
			if(ff==0)
				break;
		}
		if(wi+r-1>=n)
			printf("%d\n",ans);
		else {
			printf("-1\n");
		}
	}
	return 0;
}

 刚开始   在最后判断的时候写成了if(ff=0),就错了,因为满足不了第一次就完成的  就进不去while了 


C.

题目大意:

开始空队列,三种操作,可以进行前插和后插,查询使某个数的为最左或最右需要去掉的最少数字(其实也就是距离队列最左端或者最右端哪个更近)。

解题报告:

   这题如果想着,每次加入一个答案都去维护之前的所有的值,那就走远了。这题完全可以记录一下位置然后中间完全不用维护,最后直接输出结果就可以了。

#include<bits/stdc++.h>

using namespace std;
int q,l,r,tmp;
char op[5];
int a[500005];
int main()
{
	cin>>q;
	l = 0,r = 0;
	for(int i = 1; i<=q; i++) {
		scanf("%s",op);
		if(op[0] == 'L') {
			scanf("%d",&tmp);
			a[tmp] = --l;
			if(i == 1) r--;
		}
		else if(op[0] == 'R') {
			scanf("%d",&tmp);
			a[tmp] = ++r;
			if(i == 1) l++;
		}
		else {
			scanf("%d",&tmp);
			printf("%d\n",min(r-a[tmp],a[tmp]-l));
		}
	}
	return 0 ;
}

 


D.

题目大意:

有n个物品,、第一给物品开始往右边挑选,对于每一个物品,如果可以放得下的就直接放进盒子,若目前的盒子放不下,那就要另外开一个盒子来放物品了,若目前还有可用的盒子,那就继续选取下去,若目前已经没有可用的盒子了,说明这次选取是不对的,那么选取的第一个物品退回去,看是否有剩余的空间放下该物品,如果还是放不下的话,继续把第二个拿的物品退回去,直至可以放下该物品为止,然后继续选取下去。

解题报告:

  读懂题了就很简单,就是往盒子里按照给定的顺序放东西,如果放满了就新开一个盒子放东西,如果都满了,那就把最早放入的物品拿出来,然后继续放后面的物品,直到放到最后一个物品。问你盒子中最多有多少物品?。。。就是这一句话,好有迷惑性,一般都会感觉是中间过程也会算上,而且不能打乱顺序放,所以不能排序,就是必须按照他的algorithm放东西,所以就不好模拟了啊!但是其实题意是就问你最后盒子中物品的数量,而不是中间某个过程就算物品很多,也被拿出来了,那也 白搭,所以只和最终状态有关,,这样正着还是不好模拟,所以采用时光倒流法,,,倒着模拟,就简单多了,或者先二分从第几个盒子开始装,然后再验证是否可行即可(也可以二分最终装了多少个物品,不过其实一样的因为反正都是倒着装)。不过这个题的二分没啥乱用,,因为直接模拟就出结果了。

#include <bits/stdc++.h>
#define ll long long

using namespace std;
int n,box,siz;
int a[200005];

bool ok(int mid){
    int k=1,rem=siz;

    for(int i = mid; i<=n; i++){
        if(rem<a[i]){rem=siz;k++;}
        if(k>box) return 0;
        rem-=a[i];
    }

    return 1;
}
int main()
{
    cin>>n>>box>>siz;
    for(int i = 1; i<=n; i++) cin>>a[i];
    int mid,l=1,r=n,ans;
    while(l<=r){
        mid=(l+r)/2;
        if(ok(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout << n + 1 -ans << endl;
    return 0;
}

 


E.

题目大意:

   给你长度分别为n,m的二进制串,当b>0时,对a,b,&运算结果为tmp,然后b右移一位,把每次a&b的10进制结果(tmp)累加得到sum,结果输出sum对998244353取余的值。

解题报告:

  模拟过程不难发现,a的每一个位置做出的贡献次数,就是b对应位置前缀1的个数,于是维护一下就好了。(因为b字符串一直在变,但是a是固定不变的啊!所以我们预处理一下a字符串)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
const ll mod = 998244353;
char op[5];
char a[500005],b[500005];
ll ans[500005];
ll qpow(ll a,ll k) {
	ll res = 1;
	while(k) {
		if(k&1) {
			res *= a;
			res %= mod;
		}
		k>>=1;
		a=(a*a)%mod;
	}
	return res;
}
int main()
{
	ll cha = 0;
	cin>>n>>m;
	cin>>(a+1);
	cin>>(b+1);
	ll lena = strlen(a+1);
	ll lenb = strlen(b+1);
	ll cur = 0;
	if(strlen(a+1) < strlen(b+1)) {
		cha = strlen(b+1) - strlen(a+1);
		for(ll i = 1; i<=cha; i++) {
			if(b[i] == '1') cur++;
		}
		for(ll i = 1; i<=strlen(a+1); i++) {
			if(b[i+cha]=='1') ans[i] = ++cur;
			else ans[i]=cur;
		}
	}
	else {
		cha = strlen(a+1) - strlen(b+1);
		for(ll i = 1; i<=strlen(b+1); i++) {
			if(b[i] == '1') ans[i+cha] = ++cur;
			else ans[i+cha] = cur;
		}
		
		
	}
	ll out = 0;
	for(ll i = 1; i<=strlen(a+1); i++) {
		if(a[i] == '1') {
			out += (ll)ans[i] * qpow(2,lena-i);
			out %= mod;
		}
	}
	printf("%lld\n",out%mod);
	return 0 ;
}

比赛的时候忘记考虑a比b长的情况了、、不然这场比赛完美了啊。 最后压哨失败很难受。。

这道题还有更精彩更简洁的解法,把两个字符串处理成相同长度的,再去维护,岂不是美滋滋?正好用到了string类,重载 ' + ' 焦作人啊!另外,这个代码中预处理了2^n,做到了o(1)出结果,比快速幂的log要好一些。

AC代码2:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const ll N=2e5+10;
ll one[N],pw[N];
int main()
{
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0); 
    ll i,j,k,n,m;
    string a,b;
    cin>>n>>m;
    cin>>a>>b;
    //使位数一致在位数少的前面加0 
    if(n<m){
        a=string(m-n,'0')+a;
    }
    else if(m<n){
        b=string(n-m,'0')+b;
    }
    n=max(n,m);
    one[0]=(b[0]=='1');
    for(i=1;i<n;i++) one[i]=one[i-1]+(b[i]=='1');//b高位开始的前缀和 
    pw[0]=1;
    for(i=1;i<N;i++) pw[i]=pw[i-1]*2ll%mod;//计算2的幂次预处理 
    ll ans=0;
    for(i=0;i<n;i++){
        ll res=(a[i]=='1');
        res=res*pw[n-i-1]%mod;//计算a这个位置的10进制值 
        ans=(ans+res*one[i]%mod)%mod;//之所以*one[i],是因为b右移的过程,a[i]对应的次数就是b高位开始的前缀和,注意取余mod 
    }
    cout<<ans<<endl;
    return 0;
}