solve: 5/8

 

A题：

　　$O(N^2)$暴力一下搜一下两个向量的组合

　　

#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch>'9'; ch = getchar())
        if(ch == '-') f = -f;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

inline void chkmin( int &a, int b ) { if(a > b) a = b; }

inline void chkmax( int &a, int b ) { if(a < b) a = b; }

#define _ read()

#define ln endl

const int N=1005;
int n, x[N], y[N];

int main(){
	n=read();
	for(int i=1; i<=n; i++)
		x[i]=read(), y[i]=read(), x[i]=read()-x[i], y[i]=read()-y[i];
	int X=read(), Y=read(); X=read()-X; Y=read()-Y;
	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==0) return puts("YES"),0;
	puts("NO");
}

　　

B题：

　　暴力找"QAQ"即可（反正是子串）

#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch>'9'; ch = getchar())
        if(ch == '-') f = -f;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

inline void chkmin( int &a, int b ) { if(a > b) a = b; }

inline void chkmax( int &a, int b ) { if(a < b) a = b; }

#define _ read()

#define ln endl

char s[1000006];
int n;

int main(){
	scanf("%s", s+1); n=strlen(s+1);
	for(int i=3; i<=n; i++)
		if(s[i-2]=='Q'&&s[i-1]=='A'&&s[i]=='Q') return cout<<i-2<<ln,0;
}

　

D题：

　　可以发现如果ai是质数， 那么ai乘上一个不等于1的数肯定是合数， 根据这个我们只需要一个区间set

　　可以修改可以不管a1那个数， 但是统计要统计上

　　但是需要考虑ai=1的情况， 此时如果他出现在2， 3， 5， 7……这些质数位置上， 那么有可能变成质数， 于是我们需要一个单点加

　　我的做法是： 搞一个set存所有的可能变成质数的地方， 然后每次查询将set中在L,R中的点提出来， 然后在set中删掉该点， 如果x=1那么给该点暴力+1， 

　　其他的地方按一开始ai是否为质数赋值为0,1， 然后建一棵线段树暴力维护即可

　　效率$O(Nlog_2N)$

#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch>'9'; ch = getchar())
        if(ch == '-') f = -f;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

inline void chkmin( int &a, int b ) { if(a > b) a = b; }

inline void chkmax( int &a, int b ) { if(a < b) a = b; }

#define _ read()

#define ln endl

const int N=5e5+5;
int n, m, vis[N], a[N];
int t[N<<2], lzy[N<<2];
set<int> s;

void up(int x){
	t[x]=t[x<<1]+t[x<<1|1];
}

void build(int l, int r, int rt){
	if(l==r){t[rt]=a[l]; return;}
	int mid=(l+r)>>1;
	build(l, mid, rt<<1); 
	build(mid+1, r, rt<<1|1);
	up(rt);
}

void down(int x){
	if(lzy[x]){
		t[x<<1]=0; t[x<<1|1]=0;
		lzy[x<<1]|=lzy[x]; lzy[x<<1|1]|=lzy[x];
		lzy[x]=0;
	}
}

int query(int L, int R, int l, int r, int rt){
	if(L<=l&&r<=R) return t[rt];
	int mid=(l+r)>>1;
	down(rt);
	int ans=0;
	if(L<=mid) ans+=query(L, R, l, mid, rt<<1);
	if(R>mid)  ans+=query(L, R, mid+1, r, rt<<1|1);
	return ans;
}

void add(int x, int l, int r, int rt){
	if(l==r){t[rt]=1; return;}
	int mid=(l+r)>>1;
	down(rt);
	if(x<=mid) add(x, l, mid, rt<<1);
	else add(x, mid+1, r, rt<<1|1);
	up(rt);
}

void modify(int L, int R, int l, int r, int rt){
	if(L<=l&&r<=R){t[rt]=0; lzy[rt]=1; return;}
	int mid=(l+r)>>1;
	down(rt);
	if(L<=mid) modify(L, R, l, mid, rt<<1);
	if(R>mid)  modify(L, R, mid+1, r, rt<<1|1);
	up(rt);
}

int main(){
	n=read(); m=read();
	for(int i=2; i<=500000; i++)
		vis[i]=1;
	for(int i=2; i<=500000; i++)
		if(vis[i]){
			for(int j=2; i*j<=500000; j++)
				vis[i*j]=0;
		}
	for(int i=1; i<=n; i++)
		a[i]=read();
	for(int i=2; i<=n; i++)
		if(vis[i]&&a[i]==1) s.insert(i);
	for(int i=1; i<=n; i++)
		a[i]=vis[a[i]];
	build(1, n, 1);
	while(m--){
		int opt=read(), l=read(), r=read();
		if(opt==2) printf("%d\n", query(l, r, 1, n, 1));
		else {
			int x=read();
			int L=l, R=r;
			if(L==1) ++L;//L=1修改之后仍然等于本身
			if(L<=R&&x!=0) modify(L, R, 1, n, 1);//一旦修改肯定不是质数
			set<int>::iterator it=s.lower_bound(L);//L..R中间的1
			set<int>::iterator it2=it;
			for(;it!=s.end()&&*it<=R; ++it)
				if(x==1) add(*it, 1, n, 1);
			if(it2!=s.end()&&x!=0) s.erase(it2, it);//为0不用删
			printf("%d\n", query(l, r, 1, n, 1));
		}
	}
}

 

E题：

　　直接分解然后从后往前乘起来即可， 详细看代码

　　

#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch>'9'; ch = getchar())
        if(ch == '-') f = -f;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

inline void chkmin( int &a, int b ) { if(a > b) a = b; }

inline void chkmax( int &a, int b ) { if(a < b) a = b; }

#define _ read()

#define ln endl

int main(){
	int n=read(); ll ans = 0;
	for(int i=1; i<=n; i++){
		int x=read();
		int tmp=0;
		while(x){tmp=tmp*2+x%2; x>>=1;}
		ans=ans+tmp;
	}
	cout<<ans<<ln;
}

　

G题： 

　　根据每个数都可以拆分成若干个质数乘积的唯一分解， 我们可以用每一个数去筛他的倍数， 当然如果用上一点埃筛的思想可以优化到$O(NlnlnN)$， 但是可以暴力$O(NlnN)$干他

　　然后我们只需要对每个质数维护他的后缀和即可， 可以用树状数组方便的实现

　　效率O(Nlog_2N)

#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch>'9'; ch = getchar())
        if(ch == '-') f = -f;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

inline void chkmin( int &a, int b ) { if(a > b) a = b; }

inline void chkmax( int &a, int b ) { if(a < b) a = b; }

#define _ read()

#define ln endl

const int N=3000005;
int f[N], ans[N];

struct node{int n, k, id;}q[N];
bool cmp(node a, node b){return a.n<b.n;}

int t[N];
inline int lowbit(int x){return x&-x;}
inline void add(int x){for(;x; x-=lowbit(x)) t[x]++;}
inline int ask(int x){int res=0; for(;x<=3000000; x+=lowbit(x)) res+=t[x]; return res;}

int main(){
	for(int i=1; i<=3000000; i++) f[i]=i;
	for(int i=2; i<=3000000; i++)
		for(int j=1; i*j<=3000000; j++)
			f[i*j]=min(i, f[i*j]);//质数唯一表示定理， 最小的质数因子
	// cout<<f[100]<<ln;

	int m=read();
	for(int i=1; i<=m; i++)
		q[i].n=read(), q[i].k=read(), q[i].id=i;

	sort(q+1, q+m+1, cmp);
	for(int i=1; i<=m; i++){
		for(int j=q[i-1].n+1; j<=q[i].n; j++)
			if(j!=1) add(f[j]);
		ans[q[i].id]=ask(q[i].k);
	}
	for(int i=1; i<=m; i++)
		printf("%d\n", ans[i]);
}

　

---

 

下面是补题的：

finish： 1/3 

 

H题：

　　假设没有膜法的存在， 我们只需要从左往右贪心地砍小怪， 如果ai没被ai-1和ai-2砍光， 那么必须要砍， 每次取最小的代价

　　但是由于有膜法的存在， 我们需要统计从左往右砍的代价L[i]， 和从右往左砍的代价R[i]

　　那么答案就是min{L[i]+R[i+3]}， 此时i+1和i+2不需要砍到

#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch>'9'; ch = getchar())
        if(ch == '-') f = -f;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

inline void chkmin( int &a, int b ) { if(a > b) a = b; }

inline void chkmax( int &a, int b ) { if(a < b) a = b; }

#define _ read()

#define ln endl

const int N=1e6+5;
int n, a[N];
ll b[N], L[N], R[N], ans;

int main(){
	n=read();
	for(int i=1; i<=n; i++) a[i]=read();//f[i][0/1]表示到i为止， 有没有用过魔法
	// L[0]=R[n+1]=0;
	ans=2e18;
	L[1]=b[1]=a[1];
	for(int i=2; i<=n; i++)//逐个砍
		L[i]=L[i-1]+max(a[i]-b[i-1]-b[i-2], 0ll), b[i]=max(a[i]-b[i-1]-b[i-2], 0ll);
	memset(b, 0, sizeof(b));
	R[n]=b[n]=a[n];
	for(int i=n; i; i--)
		R[i]=R[i+1]+max(a[i]-b[i+1]-b[i+2], 0ll), b[i]=max(a[i]-b[i+1]-b[i+2], 0ll);
	for(int i=0; i<=n; i++)
		ans=min(ans, L[i]+R[i+3]);
	// cout<<R[3]<<ln;
	cout<<ans<<ln;
}
/*
	记录对上一个位置和对前一个位置的斩击
	能确定对当前位置需要使用多少斩击
	max(a[i]-b[i-1]-b[i-2], 0)
*/