湖南工业大学个人选拔赛第二场解题报告

贪心题，枚举每一个数字作为结束点。保留前i位的前缀和sum[i]，对于第i为结束的合法序列，其值为sum[i]-sum[i-K]，sum[i]-sum[i-K-1]，...，sum[i]-sum[0]，那么我们只需要对每一个 i 保留sum[0]到sum[i-K]的最小值即可。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 using namespace std;
 5 typedef long long LL;
 6  
 7 const int Max = 1e6 + 5;
 8 const int INF = 0x7fffffff;
 9 int n, k;
10 int a[Max];
11  
12 int Min (int a, int b)
13 {
14     return a < b ? a:b;
15 }
16  
17 int max (int a, int b)
18 {
19     return a > b ? a: b;
20 }
21  
22 int solve()
23 {
24     int ans = INF + 1;
25     int min = INF;
26     for (int i = k; i <= n; i++)
27     {
28         min = Min(min, a[i-k]);
29         ans = max(ans, a[i] - min);
30     }
31     return ans;
32 }
33  
34 int main()
35 {
36     while (~scanf ("%d%d", &n, &k))
37     {
38         a[0] = 0;
39         for (int i = 1; i <= n; i ++)
40         {
41             scanf ("%d", &a[i]);
42             a[i] += a[i-1];
43         }
44         printf ("%d\n", solve());
45     }
46     return 0;
47 }
48 /**************************************************************
49     Problem: 1490
50     User: 12408300128
51     Language: C++
52     Result: Accepted
53     Time:164 ms
54     Memory:5340 kb
55 ****************************************************************/

B：谎言

水题，直接做一个取余操作就可以了，也可以把每一位对应的位权先计算出来乘上系数再加起来。

View Code

 1 // File Name: Problem B: 谎言
 2 // Author: sheng
 3 // Created Time: 2013年04月12日 星期五 20时14分31秒
 4  
 5 #include <stdio.h>
 6 #include <iostream>
 7 #include <string.h>
 8 using namespace std;
 9 #define Max 1010
10  
11 char num[Max];
12  
13 int main()
14 {
15     int k;
16     while (cin>> num >> k)
17     {
18         int len = strlen(num);
19         int temp;
20         temp = 0;
21         for (int i = 0; i < len; i ++)
22         {
23             if (temp >= k)
24             {
25                 temp %= k;
26                 i --;
27             }
28             else
29                 temp = 10*temp + num[i] - '0';
30             //cout << temp << endl;
31         }
32         if (temp%k)
33         {
34             printf ("%d\n", temp%k);
35         }
36         else printf ("YES\n");
37     }
38     return 0;
39 }
40 /**************************************************************
41     Problem: 1491
42     User: 12408300128
43     Language: C++
44     Result: Accepted
45     Time:663 ms
46     Memory:1432 kb
47 ****************************************************************/

C：费马定理

数学题，由于已经告知费马定理的存在，那么可以证明最小的满足要求的x一定是p-1的因子。可以假设如果x不是p-1的因子的话，那么令p-1=k*x+r，那么有a^(k*x) * a^r % p = 1，显然a^(k*x)%p = 1，而由于a^(p-1) % p = 1，所以a^r % p = 1，而0 < r < x并且x是满足条件最小的值，因此假设不成立。

View Code

 1 // File Name: 1492: 费马定理
 2 // Author: sheng
 3 // Created Time: 2013年04月14日 星期日 19时29分19秒
 4  
 5 #include <stdio.h>
 6 #include <iostream>
 7 #include <string.h>
 8 #include <algorithm>
 9 #include <math.h>
10 using namespace std;
11  
12 typedef long long LL;
13 const int INF = 0x7fffffff;
14  
15 int min(int a, int b)
16 {
17     return a < b ? a : b;
18 }
19  
20 int Pow(LL a, int b, int p)
21 {
22     LL ret = 1;
23     while (b)
24     {
25         if (b & 1)
26         {
27             ret *= a;
28             ret %= p;
29         }
30         a *= a;
31         a %= p;
32         b >>= 1;
33     }
34     return ret;
35 }
36 int main()
37 {
38     int a, p;
39     int i, j;
40     int ans;
41     while (~scanf ("%d%d", &a, &p))
42     {
43         ans = INF;
44         int k = (int)sqrt((double)p-1);
45         for (i = 1; i <= k; i ++)
46         {
47             if ((p-1) % i == 0)
48             {
49                 if (Pow(a, i, p) == 1)
50                     ans = min(ans, i);
51                 if(Pow(a, (p-1)/i, p) == 1)
52                     ans = min(ans, (p-1)/i);
53             }
54         }
55         printf ("%d\n", ans);
56     }
57     return 0;
58 }
59 /**************************************************************
60     Problem: 1492
61     User: 12408300128
62     Language: C++
63     Result: Accepted
64     Time:18 ms
65     Memory:1444 kb
66 ****************************************************************/

D：平面划分

推理题：

新加入的一条直线与前面的直线都相交能够得到最多的空间划分。考虑到绿色的线是第三根插入的线，那么标号为1,2,3的线就是新区域的边界。对于如图加入第二个V型线，新增5个区域。如果增加第三个椭圆，新增4个区域。最后推出对于直线f[i] = f[i-1] + i；对于V型线f[i] = f[i-1] + 4*i-3；对于椭圆f[i] = f[i] + 2*i-2。

View Code

 1 // File Name: c2.cpp
 2 // Author: sheng
 3 // Created Time: 2013年04月12日 星期五 20时46分07秒
 4  
 5 #include <stdio.h>
 6 #include <iostream>
 7 #include <math.h>
 8 #include <string.h>
 9 using namespace std;
10 typedef long long LL;
11  
12 int main()
13 {
14     LL n;
15     while (~scanf ("%lld", &n))
16     {
17         printf ("%lld %lld %lld\n", (n*(n+1))/2 + 1, 2*n*n - n + 1, n*n -n +2);
18     }
19     return 0;
20 }
21 /**************************************************************
22     Problem: 1493
23     User: 12408300128
24     Language: C++
25     Result: Accepted
26     Time:131 ms
27     Memory:1432 kb
28 ****************************************************************/

E：连续子串和续

利用第一题的做法加上二分搜索。设一个比例参数p，然后就是解决一个ai-p*bi的序列，至少连续K个，sum{ ai-p*bi } >= 0的问题了，二分枚举这个参数即可。

View Code

 1 // File Name: 1494: 连续子串和续
 2 // Author: sheng
 3 // Created Time: 2013年04月14日 星期日 21时13分17秒
 4  
 5 #include <stdio.h>
 6 #include <iostream>
 7 #include <string.h>
 8 #include <algorithm>
 9 using namespace std;
10  
11 const int Max = 1e6+5;
12 const int INF = 0x7fffffff;
13  
14 int n, k;
15 int a[Max], b[Max];
16 double bz[Max];
17 /*
18 int min(int a, int b)
19 {
20     return a < b ? a:b;
21 }
22 */
23 int ac(double p)
24 {
25     double Min = INF;
26     bz[0] = 0;
27     for (int i = 1; i <= n; i ++)
28         bz[i] = bz[i-1] + a[i] - p*b[i];
29     for (int i = k; i <= n; i ++)
30     {
31         Min = min(Min, bz[i-k]);
32         if (bz[i] - Min >= 0)
33             return 1;
34     }
35     return 0;
36 }
37  
38 double bsearch(double l, double r)
39 {
40     double mid, ret;
41     while (r - l > 1e-8)
42     {
43         mid = (l+r) / 2;
44         if (ac(mid))
45         {
46             ret = mid;
47             l = mid + 1e-8;
48         }
49         else
50             r = mid - 1e-8;
51     }
52     return ret;
53 }
54  
55 int main()
56 {
57     while (~scanf ("%d%d", &n, &k))
58     {
59         for (int i = 1; i <= n; i ++)
60             scanf ("%d", &a[i]);
61         for (int i = 1; i <= n; i ++)
62             scanf ("%d", &b[i]);
63         printf ("%.4lf\n", bsearch(0, 1000));
64     }
65     return 0;
66 }
67 /**************************************************************
68     Problem: 1494
69     User: 12408300128
70     Language: C++
71     Result: Accepted
72     Time:2647 ms
73     Memory:17056 kb
74 ****************************************************************/

湖南工业大学个人选拔赛第二场 解题报告

湖南工业大学个人选拔赛第二场解题报告