HZNU 2019 Summer training 4-白红宇

HZNU 2019 Summer training 4

阅读量：5151 次

发布时间：2019-06-13

本文共 4082 字，大约阅读时间需要 13 分钟。

A - Little C Loves 3 I

CodeForces - 1047A

题意：一个数分成三份，每一个都不是3的倍数

题解：分成 (1, 1, n - 2) 或者分成(1, 2, n - 3 )

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define INF 0x3f3f3f3f#define lowbit(x) (x&(-x))using namespace std;typedef long long ll;const int maxn = 1e3+7;int main(){ ll n; scanf("%lld",&n); if((n - 2) % 3 == 0) printf("1 2 %lld\n",n - 3); else printf("1 1 %lld\n",n - 2);}

View Code

B - Cover Points

CodeForces - 1047B

题意：平面上有n个点，用一个顶点在原点，两直角边分别在x轴和y轴的等腰直角三角形覆盖这些点，问能将这些点全部覆盖的三角形的直角边最短是多长

题解：求解max(x + y)

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define INF 0x3f3f3f3f#define lowbit(x) (x&(-x))using namespace std;typedef long long ll;const int maxn = 1e3+7;int main(){ int n; scanf("%d",&n); int maxx = 0; while(n--) { int a,b; scanf("%d %d",&a,&b); maxx = max(maxx,a + b); } printf("%d\n",maxx);}

View Code

C - Enlarge GCD

CodeForces - 1047C

题意：n个数的gcd是k，要你删掉最少的数使得删完后的数组的gcd > k

题解：先求出k，然后每个数除以k。然后找出出现次数最多的质因数即可。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define INF 0x3f3f3f3f#define lowbit(x) (x&(-x))using namespace std;typedef long long ll;const int maxn = 3e5 + 10;const int M = 1.5e7 + 10;int pn;int gcd(int a,int b){ return b == 0 ? a : gcd(b,a % b);}int a[maxn];int num[M];int p[4000],prime[4000];void init(){ pn = 0; memset(p,0,sizeof p); for(int i=2;i<4000;i++) { if(!p[i]) prime[pn++] = i; for(ll j =0 ;j < pn && i * prime[j] < 4000; j++){ p[i * prime[j]] = 1; if(i % prime[j] == 0) continue; } } //cout<
               
                <
                
                  1) { num[a[i]]++; ans = max(ans,num[a[i]]); } } printf("%d\n", ans == -1 ? ans : n - ans);}

View Code

D - Little C Loves 3 II

CodeForces - 1047D

题意：给你n*m得棋盘，让你找两点之间距离为3的点的个数，不能重复使用，距离定义，两坐标差绝对值之和、

题解：找规律，找特殊样例即可

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define INF 0x3f3f3f3f#define lowbit(x) (x&(-x))using namespace std;typedef long long ll;const int maxn = 1e3+7;int gcd(int a,int b){ return b == 0 ? a : gcd(b,a % b);}int main(){ ll n,m; ll ans; scanf("%lld %lld",&n,&m); if(n > m) swap(n,m); if(n == 1) { if(m % 6 == 0) ans = n * m; else if(m % 6 <= 3) ans = m - m % 6; else ans = m - (6 - m % 6); } else if(n == 2) { if(m == 2) ans = 0; else if(m == 3) ans = 4; else if(m == 7) ans = 12; else ans = n * m; } else { if(n * m % 2 == 1) ans = n * m - 1; else ans = n * m; } printf("%lld\n",ans);}

View Code

E - Region Separation

CodeForces - 1047E

题意：给定一棵大小为n的树，点有点权，在一个方案中可以将整棵树划分多次，要求每次划分后各个联通块的权值和相等，问有多少种划分方案

转自：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define LL long longconst int MAXN = 1e6 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;LL s[MAXN];LL f[MAXN],p[MAXN],ans[MAXN];LL gcd(LL a,LL b){ return b == 0 ? a : gcd(b,a % b);}int main(){ int n; LL tot = 0; scanf("%d",&n); for(int i = 1; i <=n; i++) scanf("%lld",&s[i]); for(int i = 2; i <= n; i++) scanf("%lld",&p[i]); for(int i = n; i;i--) s[p[i]] += s[i]; for(int i = n; i;i--) s[i] = s[1] / gcd(s[1],s[i]); for(int i = 1; i <= n; i++) { if (s[i] <= n) { f[s[i]]++; } } for(int i = n; i; i--) for(int j = 2 * i; j <= n; j += i){ f[j] = (f[j] + f[i]) % MOD; } for(int i=ans[1]=1;i<=n;i++) if(f[i]>=i) for(int j=i*2;j<=n;j+=i) ans[j] = (ans[j] + ans[i]) % MOD; for(int i=1;i<=n;i++) if(f[i]>=i) tot = (tot + ans[i]) % MOD; printf("%lld\n",tot);}

View Code

转载于:https://www.cnblogs.com/smallhester/p/11155896.html

你可能感兴趣的文章

2018-2019-1 20165231《信息安全系统设计基础》第二周学习总结