2015 多校第三场-白红宇

2015 多校第三场

阅读量：4309 次

发布时间：2019-06-06

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

1002

求max（f(a),f(b)）, f为不重复的素因子个数，在数据要求以内，每个数最多有7个，可以打表。

1 /*Author :usedrose  */ 2 /*Created Time :2015/7/29 11:32:09*/ 3 /*File Name :2.cpp*/ 4 #include 
      
        5 #include 
       
         6 #include 
        
          7 #include 
         
           8 #include 
          
            9 #include 
           
            10 #include 
            
             11 #include 
             
              12 #include 
              
               13 #include 
               
                14 #include 
                
                 15 #include 
                 
                  16 #include 
                  
                   17 #include 
                   
                    18 #include 
                    
                     19 #include 
                     20 #define INF 0x3f3f3f3f21 #define eps 1e-822 #define pi acos(-1.0)23 #define MAXN 100001024 #define OK cout << "ok" << endl;25 #define o(a) cout << #a << " = " << a << endl26 #define o1(a,b) cout << #a << " = " << a << " " << #b << " = " << b << endl27 using namespace std;28 typedef long long LL;29 int num[MAXN][10];30 int p[MAXN];31 int f[MAXN];32 33 void init()34 {35 for (int i = 2;i < MAXN;++ i) 36 if (!p[i]) 37 {38 f[i]++;39 for (int j = i+i; j < MAXN; j += i) {40 p[j] = 1;41 f[j] ++;42 }43 }44 45 for (int j = 0;j < 7; ++ j) {46 for (int i = 2;i < MAXN; ++ i) {47 num[i][j] = num[i-1][j] + (f[i] == j + 1);48 } 49 }50 }51 52 int T, l, r;53 54 int main()55 {56 //freopen("data.in","r",stdin);57 //freopen("data.out","w",stdout);58 cin.tie(0);59 ios::sync_with_stdio(false);60 init();61 cin >> T;62 while (T--) {63 cin >> l >> r;64 int k[8];65 memset(k , 0, sizeof(k));66 for (int i = 0;i < 7; ++ i) {67 k[i+1] = num[r][i] - num[l-1][i];68 }69 int gcd = 1;70 if (k[2] + k[4] + k[6] >= 2) gcd = 2;71 if (k[3] + k [6] >= 2) gcd = 3;72 if (k[4] >= 2) gcd = 4;73 if (k[5] >= 2) gcd = 5;74 if (k[6] >= 2) gcd = 6;75 if (k[7] >= 2) gcd = 7;76 cout << gcd << endl;77 }78 return 0;79 }

View Code

1004

一开始题意没看懂，蛋疼。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
                11 #include 
                
                  12 #pragma warning(disable:4996) 13 14 #define Zero(a) memset(a, 0, sizeof(a)) 15 #define Neg(a) memset(a, -1, sizeof(a)) 16 #define All(a) a.begin(), a.end() 17 #define PB push_back 18 #define repf(i,a,b) for(i = a;i <= b; i++) 19 #define lson l,m,rt<<1 20 #define rson m+1,r,rt<<1|1 21 #define root 1,n,1 22 #define ld rt << 1 23 #define rd rt << 1 | 1 24 #define ll long long 25 #define MAXN 200005 26 #define INF 6666666 27 #define mod 10007 28 using namespace std; 29 char mp[110][110]; 30 int mpp[110][110]; 31 int n; 32 int m; 33 int ret(char c){ 34 if (c == 'R') return 1; 35 if (c == 'B') return 2; 36 if (c == 'G') return 3; 37 if (c == '.') return 0; 38 } 39 void init(){ 40 scanf("%d", &n); 41 memset(mpp, 0, sizeof(mpp)); 42 for (int i = 0; i < n; ++i){ 43 scanf("%s", mp[i]); 44 m = strlen(mp[i]); 45 for (int j = 0; j < m; ++j){ 46 mpp[i][j] = ret(mp[i][j]); 47 } 48 } 49 //cout << n << " " << m << endl; 50 } 51 int solve(){ 52 int ans = 0; 53 bool flag = false; 54 for (int k = n - 1; k >= 1 - m; --k){ 55 flag = false; 56 for (int x = 0; x < m; ++x){ 57 int y = x + k; 58 if (x >= 0 && x < m && y >= 0 && y < n){ 59 if ((mpp[y][x] & 1)){ 60 mpp[y][x]-=1; 61 if (!flag){ 62 flag = true; 63 ans++; 64 } 65 }else if ((mpp[y][x] & 1) == 0 && flag) 66 flag = false; 67 } 68 } 69 } 70 flag = false; 71 for (int k = 0; k < n + m ; ++k){ 72 flag = false; 73 for (int x = 0; x < m; ++x){ 74 int y = k - x; 75 if (x >= 0 && x < m && y >= 0 && y < n){ 76 if ((mpp[y][x] & 2)){ 77 mpp[y][x] -= 2; 78 if (!flag){ 79 flag = true; 80 ans++; 81 } 82 }else if ((mpp[y][x] & 2) == 0 && flag) 83 flag = false; 84 } 85 } 86 } 87 return ans; 88 } 89 int main(){ 90 //freopen("data.in","r",stdin); 91 //freopen("data.out","w",stdout); 92 int T; 93 while (~scanf("%d", &T)){ 94 while (T--){ 95 init(); 96 printf("%d\n", solve()); 97 } 98 } 99 return 0;100 }

View Code

1008

搜索。。论读懂题目的重要性 + 合理的思路

1 /*Author :usedrose  */ 2 /*Created Time :2015/7/29 16:44:55*/ 3 /*File Name :2.cpp*/ 4 #include 
      
        5 #include 
       
         6 #include 
        
          7 #include 
         
           8 #include 
          
            9 #include 
           
            10 #include 
            
             11 #include 
             
              12 #include 
              
               13 #include 
               
                14 #include 
                
                 15 #include 
                 
                  16 #include 
                  
                   17 #include 
                   
                    18 #include 
                    
                     19 #include 
                     
                      20 #include 
                      21 #define INF 0x3f3f3f3f22 #define eps 1e-823 #define pi acos(-1.0)24 #define MAXN 111025 #define OK cout << "ok" << endl;26 #define o(a) cout << #a << " = " << a << endl27 #define o1(a,b) cout << #a << " = " << a << " " << #b << " = " << b << endl28 using namespace std;29 typedef long long LL;30 31 LL n;32 33 void dfs(LL l, LL r)34 {35 if (l < 0 || l > r) return;36 if (l == 0) {37 n = min(n, r);38 return;39 }40 LL len = r - l + 1;41 if (l - len < 0) return;42 dfs(l, r + len);43 if (len != 1)44 dfs(l, r + len - 1);45 dfs(l - len, r);46 dfs(l - len - 1, r);47 }48 49 int main()50 {51 //freopen("data.in","r",stdin);52 //freopen("data.out","w",stdout);53 cin.tie(0);54 ios::sync_with_stdio(false);55 LL a, b;56 while (cin >> a >> b) {57 n = INF;58 dfs(a, b);59 cout << ((n == INF) ? -1 : n) << endl;60 }61 return 0;62 }

View Code

1010

按权值建图之后，从权值高到权值低的方向bfs，或者像别人一样DFS

1 /*Author :usedrose  */ 2 /*Created Time :2015/7/29 14:48:09*/ 3 /*File Name :2.cpp*/ 4 #include 
      
        5 #include 
       
         6 #include 
        
          7 #include 
         
           8 #include 
          
            9 #include 
           
            10 #include 
            
             11 #include 
             
              12 #include 
              
               13 #include 
               
                14 #include 
                
                 15 #include 
                 
                  16 #include 
                  
                   17 #include 
                   
                    18 #include 
                    
                     19 #include 
                     20 #define INF 0x3f3f3f3f21 #define eps 1e-822 #define pi acos(-1.0)23 #define MAXN 50011024 #define OK cout << "ok" << endl;25 #define o(a) cout << #a << " = " << a << endl26 #define o1(a,b) cout << #a << " = " << a << " " << #b << " = " << b << endl27 using namespace std;28 typedef long long LL;29 30 int n;31 int w[MAXN];32 vector
                      
                        G[MAXN];33 int du[MAXN], num[MAXN];34 35 int gao()36 {37 queue
                       
                         q;38 for (int i = 1;i <= n; ++ i)39 if (du[i] == 0)40 q.push(i);41 int ans = 0;42 while (!q.empty()) {43 int t = q.front();44 q.pop();45 ans = max(ans, num[t]);46 for (int i = 0;i < G[t].size() ; ++ i) {47 int v = G[t][i];48 num[v] += num[t];49 if (--du[v] == 0)50 q.push(v);51 }52 }53 return ans;54 }55 56 57 void init()58 {59 for (int i = 1;i <= n; ++ i) {60 du[i] = 0;61 num[i] = 1;62 G[i].clear();63 }64 }65 66 int main()67 {68 //freopen("data.in","r",stdin);69 //freopen("data.out","w",stdout);70 cin.tie(0);71 ios::sync_with_stdio(false);72 while (cin >> n) {73 init();74 for (int i = 1;i <= n; ++ i) 75 cin >> w[i];76 int x, y;77 for (int i = 1;i < n; ++ i) {78 cin >> x >> y;79 if (w[x] > w[y]) swap(x, y);80 G[y].push_back(x);81 du[x]++;82 }83 cout << gao() << endl;84 }85 return 0;86 }

View Code

DFS代码转自 http://blog.csdn.net/gaoxiang36999/article/details/47110271

1 /*Author :usedrose  */ 2 /*Created Time :2015/7/29 14:48:09*/ 3 /*File Name :2.cpp*/ 4 #include 
      
        5 #include 
       
         6 #include 
        
          7 #include 
         
           8 #include 
          
            9 #include 
           
            10 #include 
            
             11 #include 
             
              12 #include 
              
               13 #include 
               
                14 #include 
                
                 15 #include 
                 
                  16 #include 
                  
                   17 #include 
                   
                    18 #include 
                    
                     19 #include 
                     20 #define INF 0x3f3f3f3f21 #define eps 1e-822 #define pi acos(-1.0)23 #define MAXN 50011024 #define OK cout << "ok" << endl;25 #define o(a) cout << #a << " = " << a << endl26 #define o1(a,b) cout << #a << " = " << a << " " << #b << " = " << b << endl27 using namespace std;28 typedef long long LL;29 30 int n;31 int w[MAXN];32 vector
                      
                        G[MAXN];33 int du[MAXN], num[MAXN];34 35 int gao()36 {37 queue
                       
                         q;38 for (int i = 1;i <= n; ++ i)39 if (du[i] == 0)40 q.push(i);41 int ans = 0;42 while (!q.empty()) {43 int t = q.front();44 q.pop();45 ans = max(ans, num[t]);46 for (int i = 0;i < G[t].size() ; ++ i) {47 int v = G[t][i];48 num[v] += num[t];49 if (--du[v] == 0)50 q.push(v);51 }52 }53 return ans;54 }55 56 57 void init()58 {59 for (int i = 1;i <= n; ++ i) {60 du[i] = 0;61 num[i] = 1;62 G[i].clear();63 }64 }65 66 int main()67 {68 //freopen("data.in","r",stdin);69 //freopen("data.out","w",stdout);70 cin.tie(0);71 ios::sync_with_stdio(false);72 while (cin >> n) {73 init();74 for (int i = 1;i <= n; ++ i) 75 cin >> w[i];76 int x, y;77 for (int i = 1;i < n; ++ i) {78 cin >> x >> y;79 if (w[x] > w[y]) swap(x, y);80 G[y].push_back(x);81 du[x]++;82 }83 cout << gao() << endl;84 }85 return 0;86 }

View Code

1011

数据量很小随便搞

1 /*Author :usedrose  */ 2 /*Created Time :2015/7/28 11:55:10*/ 3 /*File Name :2.cpp*/ 4 #include 
      
        5 #include 
       
         6 #include 
        
          7 #include 
         
           8 #include 
          
            9 #include 
           
            10 #include 
            
             11 #include 
             
              12 #include 
              
               13 #include 
               
                14 #include 
                
                 15 #include 
                 
                  16 #include 
                  
                   17 #include 
                   
                    18 #include 
                    
                     19 #include 
                     20 #define INF 0x3f3f3f3f21 #define eps 1e-822 #define pi acos(-1.0)23 #define MAXN 11024 #define OK cout << "ok" << endl;25 #define o(a) cout << #a << " = " << a << endl26 #define o1(a,b) cout << #a << " = " << a << " " << #b << " = " << b << endl27 using namespace std;28 typedef long long LL;29 30 vector
                      
                        G[MAXN];31 int n, k;32 int du[MAXN];33 int num[MAXN];34 int vis[MAXN];35 36 int main()37 {38 while (cin >> n >> k) {39 for (int i = 1;i <= n; ++ i) {40 G[i].clear();41 num[i] = 1, du[i] = 0, vis[i] = 0;42 }43 int x, y;44 for (int i = 0;i < n-1; ++ i) {45 cin >> x >> y;46 G[y].push_back(x);47 du[x]++;48 }49 for (int k = 1;k <= n; ++ k) { 50 for (int i = 1;i <= n; ++ i) {51 if (du[i] == 0) {52 for (int j = 0;j < G[i].size(); ++ j) {53 int v = G[i][j];54 du[v]--;55 num[v] += num[i];56 }57 du[i] = -1;58 }59 }60 }61 int ans = 0;62 for (int i = 1; i <= n; ++ i) {63 if (num[i] - 1 == k) ans++;64 }65 cout << ans << endl;66 }67 return 0;68 }