牛客小白月赛39题解
A
题意：n个向量中是否有两个向量相加与给出向量平行
解： O（N^2）暴力枚举相加是否能够与已知向量平行即可 可以把向量平移到（反向）到一二象限，只需要判断同向就可以了
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n;
int x[N],y[N];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i = 1;i <= n; ++i)
{
int xx,yy;
cin>>xx>>yy>>x[i]>>y[i];
if(x[i] < xx) swap(xx,x[i]),swap(yy,y[i]);
x[i] -= xx;
y[i] -= yy;
}
int xx,yy,X,Y;
cin>>xx>>yy>>X>>Y;
if(X < xx) swap(xx,X),swap(yy,Y);
X -= xx; Y -= yy;
for(int i = 1;i <= n; ++i)
for(int j = i + 1;j <= n; ++j)
{
if((x[i] + x[j]) * Y == (y[i] + y[j]) * X)
{
cout<<"YES\n";
return 0;
}
}
cout<<"NO\n";
return 0;
}
B题
题意：找出字符串中第一个‘QAQ’的位置
解：O（N）枚举‘QAQ'的位置即可
#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>s;
int n = s.size();
for(int i = 0;i < n - 2; ++i)
{
if(s[i] == 'Q' && s[i + 1] == 'A' && s[i + 2] == 'Q')
{
cout<<(i + 1)<<'\n';
return 0;
}
}
return 0;
}
C题
题意：给定保证非降的两个长度为 n 序列 a,b，有两个变量 A,B，初始均为 0。
四种操作：
1） A=an,B=bn，退出。
2）否则，如果存在t，at=A,bt>B,将B+1
3）否则，如果存在t，bt=B,at=A,将A+1
4）否则，A或B加一
每次操作后，A=B则ans++，问最大的ans
解：模拟每次操作可以发现，
当A=a[i],B=b[i]时，存在的t一定大于i，
那么A从a[i]加到a[i+1],B从b[i]加到b[i+1]时，ans最大能加max(0,min(a[i+1],b[i+1]) - max(a[i],b[i])),如果a[i]!=b[i],那么最后ans还要加上1，
模拟操作即可O（N）实现
#include<bits/stdc++.h>
using namespace std;
const int N = 3e6 + 10;
int a[N],b[N];
int n;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n;
int ans = 0;
for(int i = 1;i <= n; ++i)
{
cin>>a[i]>>b[i];
int l = min(a[i],b[i]);
int r = max(a[i - 1],b[i - 1]);
if(l >= r)
{
ans += l - r;
if(a[i - 1] != b[i - 1]) ans++;
}
}
cout<<ans<<endl;
return 0;
}
D题
题意：一个序列a，每次两种操作
1 l r x ,将l-r的a[i]乘上i^x,输出l-r有多少个质数
2 l r ，询问l-r有多少质数
解：很显然,是需要分类讨论的，讨论清楚就可以了。
E题
题意：给定n个数，求他们的二进制表示翻转后的和。定义翻转为：将一个数二进制表示，再将其翻转，去掉前导零后读数。 举个例子，44二进制下101100，翻转后为001101，去掉前导零为1101，即13
解：对于每个数字，把他变成二进制表示，然后反向，还原成10进制即可，因为ai<=2 * 10 ^ 9,所以每次操作不会超过O(70),对这n个数字操作求和即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n;
ll x,ans;
int a[50];
ll solve(int x)
{
int tot = 0;
while(x)
{
a[++tot] = x % 2;
x /= 2;
}
ll s = 0;
ll k = 1;
for(int i = tot;i >= 1; --i)
s += a[i] * k,k *= 1LL * 2;
return s;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i = 0;i < n; ++i)
{
cin>>x;
ans += solve(x);
}
cout<<ans<<'\n';
return 0;
}
G题
题意：q 次询问。每次询问给定 n 和 K，问 1 ~ n 中有多少数可以表示为大于等于 K 的质数的乘积（一个数可以乘多次）。
解：可以发现，每个数字的最小的质因数可以通过线性筛直接预处理出来，存在a数组中，那么问题就变成了：q次询问，每次询问1-n这个区间内有多少x满足a[x]>=k 将所有操作输入按照n从小到大排序，每次将<=n的a[i]加入树状数组中去，然后对1-（k-1）求一个区间和，就是不满足最小质因子大于等于k的数。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e6;
int a[N + 10],p[N + 10],ans[N + 10];
bool vis[N + 10];
int n,k,tot;
struct node
{
int x,y,id;
}s[N + 10];
void init()
{
for(int i = 1;i <= N; ++i) a[i] = i;
for(int i = 2;i <= N; ++i)
{
if(!vis[i]) p[++tot] = i;
for(int j = 1;j <= tot && i * p[j] <= N; ++j)
{
vis[p[j] * i] = 1;
a[p[j] * i] = min(a[i],p[j]);
if(i % p[j] == 0) break;
}
}
}
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void write(int x)
{
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
bool cmp(node k,node l)
{
return k.x < l.x;
}
int tt[N + 10];
int lowbit(int x)
{
return x & (-x);
}
void add(int x)
{
for(int i = x;i <= N; i += lowbit(i)) tt[i]++;
}
int query(int x)
{
int si = 0;
for(int i = x;i > 0; i -= lowbit(i)) si += tt[i];
return si;
}
int main()
{
init();
int q = read();
for(int i = 0;i < q; ++i)
{
s[i].x = read();
s[i].y = read();
s[i].id = i;
}
sort(s,s + q,cmp);
int n = 1;
for(int i = 0;i < q; ++i)
{
while(n <= s[i].x) add(a[n++]);
if(s[i].y == 1) s[i].y++;
ans[s[i].id] = s[i].x - query(s[i].y - 1);
}
for(int i = 0;i < q; ++i) cout<<ans[i]<<'\n';
return 0;
}
H题
题意：一排n个数字，每次可以选择相邻3个数字减1，花费为1，或者可以动用一次魔法，选择相邻的两个数字使其变成0，花费为0，问所有数小于等于0的最小花费
解：首先考虑没有魔法的情况，从前a[x],假定a[1]-a[x-1]都已经小于等于0，那么肯定是将a[x],a[x+1],a[x+2]减少最优。 有魔法的情况下，可以O（N）预处理出li，ri表示i之前和之后都小于等于0的花费，枚举魔法用在哪两个数字上即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll a[N],b[N],l[N],r[N];
int n;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i = 1;i <= n; ++i) cin>>a[i],b[i] = a[i];
for(int i = 2;i <= n + 1;++i)
{
l[i] = l[i - 1] + a[i - 1];
a[i] = max(0ll,a[i] - a[i - 1]);
a[i + 1] = max(0ll,a[i + 1] - a[i - 1]);
}
for(int i = n - 1;i >= 0;--i)
{
r[i] = r[i + 1] + b[i + 1];
b[i] = max(0ll,b[i] - b[i + 1]);
b[max(0,i - 1)] = max(0ll,b[max(0,i - 1)] - b[i + 1]);
}
ll ans = 1e18;
for(int i = 1;i < n;++i) ans = min(ans,l[i] + r[i + 1]);
cout<<ans<<'\n';
return 0;
}
阿里巴巴一面144人在聊