A. Vova and Train
题目链接：http://codeforces.com/contest/1066/problem/A
题目大意：给出一个序列，问遮挡了多少
1~n，然后每v个位置有一个数，问除去l~r覆盖了的点，还剩多少个点，
解题：找规律模拟即可
ac：
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
//#include<map>
//#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// ˮӡ
//std::ios::sync_with_stdio(false);
const int MAXN=1e5+5;
const ll INF=0x3f3f3f3f;
const ll mod=1e9+7;
int main()
{
std::ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
ll L,v,l,r;
cin>>L>>v>>l>>r;
ll sum=L/v;
ll sum_l=(l-1)/v,sum_r=r/v;
ll ans=sum-(sum_r-sum_l);
cout<<ans<<endl;
}
}
B. Heaters
题目链接：http://codeforces.com/contest/1066/problem/B
题目大意：输入n（有n个房子），m（每个有暖气的房子覆盖的范围）
然后是这n个房子分别的状态0无暖气，1有暖气
输出最少的让多少房子有暖气能使这些房子都暖和，没可能输出-1
解题：贪心，遍历一遍；
ac：
C. Books Queries
题目链接：http://codeforces.com/contest/1066/problem/C
题目大意：给出n个操作，每次操作可以选择从右或左插入一个数，或者访问数x距离边界的最短距离，输出最短距离。
解题：对于每个数，都记录一下右边有多少个，左边有多少个，然后直接输出即可。
ac：
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
//#include<map>
//#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// ˮӡ
//std::ios::sync_with_stdio(false);
const int MAXN=2e5+55;
const ll INF=0x3f3f3f3f;
const ll mod=1e9+7;
struct node{
int l,r;
}a[MAXN];
int id[MAXN];
int main()
{
std::ios::sync_with_stdio(false);
int n;
while(cin>>n)
{
clean(a,0);
clean(id,0);
char oper;
int data;
cin>>oper>>data;
if(oper!='?')//首先是第一个
id[data]=1;
a[1].l=0,a[1].r=0;
int l=1,r=1;//初始化节点
for(int j=2,i=2;j<=n;++j)//j个操作
{
cin>>oper>>data;
if(oper=='L')//插左边
{
id[data]=i;//他是第i个
a[i].l=a[l].l+1;//是左边的那个+1
a[i].r=-a[i].l;//右边的继续
l=i;//刷新l
i++;
}
else if(oper=='R')//插右边
{
id[data]=i;
a[i].r=a[r].r+1;
a[i].l=-a[i].r;
r=i;
i++;
}
else//访问
{
// cout<<"----------"<<endl;
// cout<<l<<" "<<r<<endl;
// cout<<a[l].l<<" "<<a[r].r<<endl;
// cout<<a[id[data]].l<<" "<<a[id[data]].r<<endl;
// cout<<"----------"<<endl;
int num_l=a[l].l-a[id[data]].l;
int num_r=a[r].r-a[id[data]].r;
int ans=num_l>num_r?num_r:num_l;
cout<<ans<<endl;
}
}
}
}
E. Binary Numbers AND Sum
题目链接：http://codeforces.com/contest/1066/problem/E
题目大意：输入两个n，m分别代表两个字符串的长度，然后输入两个字符串a，b，都是二进制数，然后进行：
ll sum=0;
while(b)
{
sum=sum+a&b;
b=b>>1;
} 运算，知道b表示的二进制数为0；
解题：其实暴力循环肯定超时，因此我们看对于a中的每一位数，它能够和b&多少次，然后记录下来，再遍历一遍a，对于每一位都加起来得到sum
ac：
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
//#include<map>
//#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// ˮӡ
//std::ios::sync_with_stdio(false);
const int MAXN=2e5+15;
const ll INF=1e18;
const ll mod=998244353;
char a[MAXN],b[MAXN];
int rea[MAXN],reb[MAXN],newb[MAXN];
ll take(ll a,ll b)
{
ll res=0;
while(b)
{
if(b&1)
res=(res+a)%mod;
a=(a+a)%mod;
b=b>>1;
}
return res;
}
ll quick(ll a,ll n)
{
ll res=1;
while(n)
{
if(n&1)
res=(res*a)%mod;
a=(a*a)%mod;
n=n>>1;
}
return res;
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
clean(a,'\0');
clean(b,'\0');
clean(rea,0);
clean(reb,0);
clean(newb,0);
scanf("%s%s",&a,&b);
//printf("%s\n%s\n",a,b);
int a_num=0,b_num=0;
for(int i=0;i<m;++i)//��1++
{
if(b[i]=='1')
b_num++;
reb[i]=b_num;
}
for(int i=0;i<n;++i)//
rea[i]=a[n-i-1]-'0';
for(int i=0;i<m;++i)//
newb[i]=reb[m-i-1];//
ll ans=0,res=1;
for(int i=0;i<n;++i)
{
//res=quick(2,i);
if(rea[i])
ans=(ans+(res*newb[i])%mod)%mod;
res=(res<<1)%mod;
}
printf("%lld\n",ans);
}
}
京公网安备 11010502036488号