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;
}
京公网安备 11010502036488号