---

链接:

来源:蓝桥杯

---

文章目录

---

算法训练 审美课(位运算)

审美课:神仙解法,位运算(自行百度题解)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long LL;const int Max_n=(1<<20)+5;int a[Max_n],cnt[Max_n];int main(){
        int n,m;    scanf("%d%d",&n,&m);    for(int i=0;i
        
       
      
     
    

---

算法训练 素因子去重(数论(素数))

素因子去重:类似于欧拉函数,因为数据类型错了三次.(刚开始用素数筛来做此题,发现想法过于复杂,后来把类型改的乱七八糟.)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;const int Max_n=1000005;LL get_ans(LL n){ //数据类型 LL ans=1; for(LL i=2;i<=n;i++){ //此处需要注意数据类型 if(n%i==0){ //这里一直用n是因为我们找的素数一直不可能大于n while(n%i==0) n/=i;//选出每一个素数,类似于欧拉函数 ans*=i; } } return ans;}int main(){ LL n; scanf("%lld",&n); LL ans=get_ans(n); printf("%lld\n",ans); return 0;}
         
        
       
      
     
    

---

算法训练 P0505(高精度 * 单精度(模板),离线计算)

P0505:高精度*单精度模板(详解见博客,附链接)

?大数模板(C/C++)地址: ?

?大数模板(Java)地址: ?

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;const int Max_n=105;struct BigNum{ int s[3*Max_n],l;}c[Max_n];BigNum operator *(BigNum a,int b){ for(int i=0;i
         
        
       
      
     
    

---

算法训练 最大最小公倍数(贪心)

  容易想到的就是n·(n-1)·(n-2)/gcd(n,n-2)和n·(n-1)·(n-3)/gcd(n,n-3),一开始想到的是,n为奇数的时候一定是第一种,为偶数的时候就是第二种情况.但是此时我们只能通过60%的数据,我们还可以发现n是偶数的时候,n和n-3可能还有公因子,那么此时就要和(n-1)·(n-2)·(n-3)再次比较因为这三个数是没有公因子的.

LL gcd(LL a,LL b){
    	return b==0?a:gcd(b,a%b);}int main(){
      	LL n;	scanf("%lld",&n);	if(n==1) printf("1\n");	else if(n==2) printf("2\n");	else {
    		LL ans=max(max(n*(n-1)*(n-2)/gcd(n,n-2),n*(n-1)*(n-3)/gcd(n,n-3)),(n-1)*(n-2)*(n-3)/gcd(n-1,n-3));		printf("%lld\n",ans);	}    return 0;}

---

算法训练 关联矩阵(基础概念)

关联矩阵是描述点与边的关系

int main(){
      	int n,m;	scanf("%d%d",&n,&m);	rep(i,1,m){
    		int x,y;		scanf("%d%d",&x,&y);		a[x][i]=1;		a[y][i]=-1;	}	rep(i,1,n)		rep(j,1,m)			printf("%d%c",a[i][j],j==m?'\n':' ');    return 0;}

---

算法训练 Torry的困惑(基本型) (素数筛)

void get_prime(){
    	rep(i,2,Max_n) is_prime[i]=true;	rep(i,2,sqrt(Max_n)){
    		if(is_prime[i]){
    			for(int j=i*i;j<=Max_n;j+=i)				is_prime[j]=false;		}	}	num=1;	rep(i,1,Max_n)		if(is_prime[i])			prime[num++]=i; }int main(){
      	get_prime();	int n; sc(n);	LL ans=1;	rep(i,1,n) ans=(ans*prime[i])%mod;	printf("%lld\n",ans);    return 0;}

---

算法训练 字串统计(STL map,string的应用)

这个代码写的有点乱(我自己都有点乱了?)(水过一把),回来在更新一个思路比较清晰的,STL的应用参考我的ACM_STL应用专题的STL专题总结.

#include
    
     #include
     
      #include
      
        #include
       
      
     
    

---