牛客小白月赛39题解

题意：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;
}