备战蓝桥杯---刷杂题1

发布于:2024-04-05 ⋅ 阅读:(155) ⋅ 点赞:(0)

1.来个小定理(上次DP的青蛙过河用过)

事实上,假如他们的gcd!=1,那么P,q都可以表示成gcd的倍数,因此假如一个数不是gcd的倍数就不可以表示,若互质由裴蜀定理大于一定时一定可以表示出。

事实上为(p-1)(q-1)-1.(p,q互质)

2.

模拟+单链表式并查集:

p[i]表示单链表的下一个节点,i所在树的根节点为从i开始向右找第一个没有被用的位置。

一开始都是自环,假如后面2被用过,那么2连3,假如1用了,1连2,这样子通过路径压缩就可以高效的实现。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1100010;
int p[N];
int find(int x){
    if(p[x]==x) return x;
    return p[x]=find(p[x]);
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<N;i++) p[i]=i;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        x=find(x);
        printf("%d ",x);
        p[x]=x+1;
    }
}

3.组合数问题求最值-背包:

我们令f[i][j][k]表示从前i个数选j个,总和余数为k的选法集合的max

易得状态转移方程:

f[i][j][k]=max(f[i-1][j][k],f[i-1][j-1][((k-ai)%K+K)%K]),但是复杂度太大了。

同时,我们可以得到一个结论,对于余数相同的,我们只要保证存最大值前3就可以了,这样复杂度就可以了

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,f[4][N];
vector<int> a[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        a[x%m].push_back(x);
    }
    memset(f,-0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=0;i<m;i++){
        sort(a[i].begin(),a[i].end());
        reverse(a[i].begin(),a[i].end());
        for(int u=0;u<3&&u<a[i].size();u++){
            int x=a[i][u];
            for(int j=3;j>=1;j--){
                for(int k=0;k<m;k++){
                    f[j][k]=max(f[j][k],f[j-1][(k-x%m+m)%m]+x);
                }
            }
        }
    }
    cout<<f[3][0];
}

4.数学

恶心到了,直接放图:

下面是矩阵快速幂以及龟速乘的代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL p;
LL qmul(LL a,LL b){
	LL res=0;
	while(b){
		if(b&1) res=(res+a)%p;
		a=(a+a)%p;
		b>=1;
	}
	return res;
} 
LL t[2][2];
void mul(LL c[][2],LL a[][2],LL b[][2]){
	memset(t,0,sizeof(t));
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++){
				t[i][j]=(t[i][j]+qmul(a[i][k],b[k][j]))%p;
			}
		}
	}
	memcpy(c,t,sizeof(t));
}
LL F(LL n){
	if(!n) return 0;
	LL f[2][2]={1,1};
	LL a[2][2]={{0,1},{1,1}};
	for(LL k=n-1;k;k>=1){
		if(k&1) mul(f,f,a);
		mul(a,a,a);
	}
	return f[0][0];
}


网站公告

今日签到

点亮在社区的每一天
去签到