15.03.15湖南省多校对抗赛

http://acm.csu.edu.cn/OnlineJudge/contest.php?cid=2069

A题：说了半天其实问题很简单，就是求 n! - 1 mod p = =!

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, mid
18 #define rson k<<1|1, mid+1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FOPENIN(IN) freopen(IN, "r", stdin)
23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)
24  
25 template<class T> T CMP_MIN(T a, T b) { return a < b; }
26 template<class T> T CMP_MAX(T a, T b) { return a > b; }
27 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
28 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
31  
32 //typedef __int64 LL;
33 typedef long long LL;
34 const int MAXN = 1100;
35 const int MAXM = 2000010;
36 const double eps = 1e-10;
37  
38 LL MOD = 1000000007;
39  
40 LL n, t;
41  
42 int main()
43 {
44     cin >> t;
45     while(t--) {
46         cin>> n;
47         LL ans = 1;
48         for(int i = 1; i <= n; i ++) {
49             ans = ans * i % MOD;
50         }
51         cout<< (ans - 1 + MOD) % MOD<<endl;
52     }
53     return 0;
54 }
55

View Code

E:环形的最大连续子序列

特殊处理跨过了起点（连到终点）的情况，详键代码

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, mid
18 #define rson k<<1|1, mid+1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FOPENIN(IN) freopen(IN, "r", stdin)
23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)
24  
25 template<class T> T CMP_MIN(T a, T b) { return a < b; }
26 template<class T> T CMP_MAX(T a, T b) { return a > b; }
27 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
28 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
31  
32 //typedef __int64 LL;
33 typedef long long LL;
34 const int MAXN = 1100000;
35 const int MAXM = 2000010;
36 const double eps = 1e-12;
37  
38 int a[1100000], n, t;
39 int pre[1100000];
40  
41 int work()
42 {
43     int sum = a[0], ret = 0, suf = 0;
44     pre[0] = max(sum, 0);
45     for(int i = 1; i < n; i ++) {
46         sum += a[i];
47         pre[i] = max(pre[i -1], sum);
48     }
49     sum = 0;
50     for(int i = n - 1; i >= 1; i --) {
51         sum += a[i];
52         suf = max(sum, suf);
53         ret = max(ret, pre[i - 1] + suf);
54     }
55     return ret;
56 }
57  
58 int main()
59 {
60     cin>>t;
61     while(t--) {
62         cin>>n;
63         mem0(a); mem0(pre);
64         int ma = -INF, tmp = 0;
65         for(int i = 0; i < n; i ++) {
66             scanf("%d", a + i);
67         }
68         for(int i = 0; i < n; i ++) {
69             tmp += a[i];
70             if(tmp > ma) {
71                 ma = tmp;
72             }
73             if(tmp < 0) {
74                 tmp = 0;
75             }
76         }
77         cout<< max(ma, work()) << endl;
78     }
79     return 0;
80 }

View Code

F：最后就是找出a的最大的2^i的因子p1,和b的最大的2^i的因子p2，在比较p1 和p2的最小值（假设为2^x）答案就是 n - x + 1

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, mid
18 #define rson k<<1|1, mid+1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FOPENIN(IN) freopen(IN, "r", stdin)
23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)
24  
25 template<class T> T CMP_MIN(T a, T b) { return a < b; }
26 template<class T> T CMP_MAX(T a, T b) { return a > b; }
27 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
28 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
31  
32 //typedef __int64 LL;
33 typedef long long LL;
34 const int MAXN = 4000000+10;
35 const int MAXM = 2000010;
36 const double eps = 1e-12;
37  
38 LL a, n, b;
39  
40 LL get(LL a)
41 {
42     int ret = 0;
43     LL p = 1;
44     while(a % p == 0 && a >= p) {
45         p <<=1;
46         ret ++;
47     }
48     return ret;
49 }
50  
51 int main()
52 {
53     int t;
54     while(cin>>t) while(t--){
55         cin >> n >> a>> b;
56         LL p = min(get(a), get(b));
57         cout << n - p + 1<< endl;
58     }
59     return 0;
60 }

View Code

K:找出上限和下限，判断p是不是在这之间

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <vector>
 8 #include <cstdio>
 9 #include <cctype>
10 #include <cstring>
11 #include <cstdlib>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 #define INF 0x3f3f3f3f
16 #define inf (-((LL)1<<40))
17 #define lson k<<1, L, mid
18 #define rson k<<1|1, mid+1, R
19 #define mem0(a) memset(a,0,sizeof(a))
20 #define mem1(a) memset(a,-1,sizeof(a))
21 #define mem(a, b) memset(a, b, sizeof(a))
22 #define FOPENIN(IN) freopen(IN, "r", stdin)
23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)
24  
25 template<class T> T CMP_MIN(T a, T b) { return a < b; }
26 template<class T> T CMP_MAX(T a, T b) { return a > b; }
27 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
28 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
31  
32 //typedef __int64 LL;
33 typedef long long LL;
34 const int MAXN = 1100000;
35 const int MAXM = 2000010;
36 const double eps = 1e-12;
37  
38 int n, p, c;
39 char s[10000];
40  
41 int main()
42 {
43     while(~scanf("%d %d%*c", &n, &p)) {
44         int ans = 0, k = n / 3;
45         for(int i = 0; i < n; i ++) gets(s);
46         if(n % 3 == 0) ans = (p >= k + 1) && (p <= 2 * k);
47         else ans = (p >= k + 1) && (p <= 2 * k + 1);
48         printf("%s
", ans ? "YES" : "NO");
49     }
50     return 0;
51 }
52

View Code

有待完善。。。