[CFGym101028] 2016 Al-Baath University Training Camp Contest-1

比赛链接：http://codeforces.com/gym/101028/

由于实习，几乎没有时间刷题了。今天下午得空，断断续续做了这一套题，挺简单的。

A.读完题就能出结果。

 1 /*
 2 ━━━━━┒ギリギリ♂ eye！
 3 ┓┏┓┏┓┃キリキリ♂ mind！
 4 ┛┗┛┗┛┃＼○／
 5 ┓┏┓┏┓┃ /
 6 ┛┗┛┗┛┃ノ)
 7 ┓┏┓┏┓┃
 8 ┛┗┛┗┛┃
 9 ┓┏┓┏┓┃
10 ┛┗┛┗┛┃
11 ┓┏┓┏┓┃
12 ┛┗┛┗┛┃
13 ┓┏┓┏┓┃
14 ┃┃┃┃┃┃
15 ┻┻┻┻┻┻
16 */
17 #include <algorithm>
18 #include <iostream>
19 #include <iomanip>
20 #include <cstring>
21 #include <climits>
22 #include <complex>
23 #include <cassert>
24 #include <cstdio>
25 #include <bitset>
26 #include <vector>
27 #include <deque>
28 #include <queue>
29 #include <stack>
30 #include <ctime>
31 #include <set>
32 #include <map>
33 #include <cmath>
34 using namespace std;
35 #define fr first
36 #define sc second
37 #define cl clear
38 #define BUG puts("here!!!")
39 #define W(a) while(a--)
40 #define pb(a) push_back(a)
41 #define Rint(a) scanf("%d", &a)
42 #define Rll(a) scanf("%I64d", &a)
43 #define Rs(a) scanf("%s", a)
44 #define Cin(a) cin >> a
45 #define FRead() freopen("in", "r", stdin)
46 #define FWrite() freopen("out", "w", stdout)
47 #define Rep(i, len) for(LL i = 0; i < (len); i++)
48 #define For(i, a, len) for(LL i = (a); i < (len); i++)
49 #define Cls(a) memset((a), 0, sizeof(a))
50 #define Clr(a, w) memset((a), (w), sizeof(a))
51 #define Fuint(a) memset((a), 0x7f7f, sizeof(a))
52 #define lrt rt << 1
53 #define rrt rt << 1 | 1
54 #define pi 3.14159265359
55 #define RT return
56 #define lowbit(w) w & (-w)
57 #define onenum(w) __builtin_popcount(w)
58 typedef long long LL;
59 typedef long double LD;
60 typedef unsigned long long Uint;
61 typedef pair<LL, LL> pii;
62 typedef pair<string, LL> psi;
63 typedef map<string, LL> msi;
64 typedef vector<LL> vi;
65 typedef vector<LL> vl;
66 typedef vector<vl> vvl;
67 typedef vector<bool> vb;
68 
69 const int maxn = 150;
70 int n;
71 int x;
72 int rk;
73 
74 int main() {
75     // FRead();
76     int T;
77     Rint(T);
78     W(T) {
79         Rint(n); Rint(rk);
80         int cur = 1500;
81         W(n) {
82             Rint(x);
83             cur += x;
84         }
85         if(cur == rk) cout << "Correct" << endl;
86         else cout << "Bug" << endl;
87     }
88     RT 0;
89 }
A

B.读完提就能出结果。

 1 /*
 2 ━━━━━┒ギリギリ♂ eye！
 3 ┓┏┓┏┓┃キリキリ♂ mind！
 4 ┛┗┛┗┛┃＼○／
 5 ┓┏┓┏┓┃ /
 6 ┛┗┛┗┛┃ノ)
 7 ┓┏┓┏┓┃
 8 ┛┗┛┗┛┃
 9 ┓┏┓┏┓┃
10 ┛┗┛┗┛┃
11 ┓┏┓┏┓┃
12 ┛┗┛┗┛┃
13 ┓┏┓┏┓┃
14 ┃┃┃┃┃┃
15 ┻┻┻┻┻┻
16 */
17 #include <algorithm>
18 #include <iostream>
19 #include <iomanip>
20 #include <cstring>
21 #include <climits>
22 #include <complex>
23 #include <cassert>
24 #include <cstdio>
25 #include <bitset>
26 #include <vector>
27 #include <deque>
28 #include <queue>
29 #include <stack>
30 #include <ctime>
31 #include <set>
32 #include <map>
33 #include <cmath>
34 using namespace std;
35 #define fr first
36 #define sc second
37 #define cl clear
38 #define BUG puts("here!!!")
39 #define W(a) while(a--)
40 #define pb(a) push_back(a)
41 #define Rint(a) scanf("%d", &a)
42 #define Rll(a) scanf("%I64d", &a)
43 #define Rs(a) scanf("%s", a)
44 #define Cin(a) cin >> a
45 #define FRead() freopen("in", "r", stdin)
46 #define FWrite() freopen("out", "w", stdout)
47 #define Rep(i, len) for(LL i = 0; i < (len); i++)
48 #define For(i, a, len) for(LL i = (a); i < (len); i++)
49 #define Cls(a) memset((a), 0, sizeof(a))
50 #define Clr(a, w) memset((a), (w), sizeof(a))
51 #define Fuint(a) memset((a), 0x7f7f, sizeof(a))
52 #define lrt rt << 1
53 #define rrt rt << 1 | 1
54 #define pi 3.14159265359
55 #define RT return
56 #define lowbit(w) w & (-w)
57 #define onenum(w) __builtin_popcount(w)
58 typedef long long LL;
59 typedef long double LD;
60 typedef unsigned long long Uint;
61 typedef pair<LL, LL> pii;
62 typedef pair<string, LL> psi;
63 typedef map<string, LL> msi;
64 typedef vector<LL> vi;
65 typedef vector<LL> vl;
66 typedef vector<vl> vvl;
67 typedef vector<bool> vb;
68 
69 const int maxn = 110;
70 char a[maxn], b[maxn];
71 
72 int main() {
73     // FRead();
74     int T;
75     Rint(T);
76     W(T) {
77         Rs(a); Rs(b);
78         for(int i = 0; a[i]; i++) {
79             if(a[i] >= 'A' && a[i] <= 'Z') a[i] = a[i] - 'A' + 'a';
80             if(a[i] == 'p') a[i] = 'b';
81             else if(a[i] == 'i') a[i] = 'e';
82         }
83         for(int i = 0; b[i]; i++) {
84             if(b[i] >= 'A' && b[i] <= 'Z') b[i] = b[i] - 'A' + 'a';
85             if(b[i] == 'p') b[i] = 'b';
86             else if(b[i] == 'i') b[i] = 'e';
87         }
88         if(strcmp(a, b) == 0) cout << "Yes" << endl;
89         else cout << "No" << endl;
90     }
91     RT 0;
92 }
B

C.已知式子A|C=B，给你A和B，求C的可能的数量。可以利用或的性质求解，讨论A和B中某位都是1时，C中这一位可以是0也可以是1。注意特判无解情况：AB中某位组合为1 0的情况。

 1 /*
 2 ━━━━━┒ギリギリ♂ eye！
 3 ┓┏┓┏┓┃キリキリ♂ mind！
 4 ┛┗┛┗┛┃＼○／
 5 ┓┏┓┏┓┃ /
 6 ┛┗┛┗┛┃ノ)
 7 ┓┏┓┏┓┃
 8 ┛┗┛┗┛┃
 9 ┓┏┓┏┓┃
10 ┛┗┛┗┛┃
11 ┓┏┓┏┓┃
12 ┛┗┛┗┛┃
13 ┓┏┓┏┓┃
14 ┃┃┃┃┃┃
15 ┻┻┻┻┻┻
16 */
17 #include <algorithm>
18 #include <iostream>
19 #include <iomanip>
20 #include <cstring>
21 #include <climits>
22 #include <complex>
23 #include <cassert>
24 #include <cstdio>
25 #include <bitset>
26 #include <vector>
27 #include <deque>
28 #include <queue>
29 #include <stack>
30 #include <ctime>
31 #include <set>
32 #include <map>
33 #include <cmath>
34 using namespace std;
35 #define fr first
36 #define sc second
37 #define cl clear
38 #define BUG puts("here!!!")
39 #define W(a) while(a--)
40 #define pb(a) push_back(a)
41 #define Rint(a) scanf("%d", &a)
42 #define Rll(a) scanf("%I64d", &a)
43 #define Rs(a) scanf("%s", a)
44 #define Cin(a) cin >> a
45 #define FRead() freopen("in", "r", stdin)
46 #define FWrite() freopen("out", "w", stdout)
47 #define Rep(i, len) for(LL i = 0; i < (len); i++)
48 #define For(i, a, len) for(LL i = (a); i < (len); i++)
49 #define Cls(a) memset((a), 0, sizeof(a))
50 #define Clr(a, x) memset((a), (x), sizeof(a))
51 #define Fuint(a) memset((a), 0x7f7f, sizeof(a))
52 #define lrt rt << 1
53 #define rrt rt << 1 | 1
54 #define pi 3.14159265359
55 #define RT return
56 #define lowbit(x) x & (-x)
57 #define onenum(x) __builtin_popcount(x)
58 typedef long long LL;
59 typedef long double LD;
60 typedef unsigned long long Uint;
61 typedef pair<LL, LL> pii;
62 typedef pair<string, LL> psi;
63 typedef map<string, LL> msi;
64 typedef vector<LL> vi;
65 typedef vector<LL> vl;
66 typedef vector<vl> vvl;
67 typedef vector<bool> vb;
68 
69 const int maxn = 222;
70 const LL mod = 1000000007;
71 int n;
72 LL ret;
73 char a[maxn], b[maxn];
74 
75 int main() {
76 //    FRead();
77     int T;
78     Rint(T);
79     W(T) {
80         Rint(n);
81         ret = 1;
82         Rs(a); Rs(b);
83         bool exflag = 0;
84         Rep(i, n) {
85             if(a[i] == '1' && b[i] == '0') exflag = 1;
86         }
87         if(exflag == 1) {
88             cout << "IMPOSSIBLE" << endl;
89             continue;
90         }
91         Rep(i, n) {
92             if(a[i] == '1' && b[i] == '1') ret = (ret * 2) % mod;
93         }
94         cout << ret << endl;
95     }
96     RT 0;
97 }
C

D.模拟，数据很小随便写就行了。

 1 /*
 2 ━━━━━┒ギリギリ♂ eye！
 3 ┓┏┓┏┓┃キリキリ♂ mind！
 4 ┛┗┛┗┛┃＼○／
 5 ┓┏┓┏┓┃ /
 6 ┛┗┛┗┛┃ノ)
 7 ┓┏┓┏┓┃
 8 ┛┗┛┗┛┃
 9 ┓┏┓┏┓┃
10 ┛┗┛┗┛┃
11 ┓┏┓┏┓┃
12 ┛┗┛┗┛┃
13 ┓┏┓┏┓┃
14 ┃┃┃┃┃┃
15 ┻┻┻┻┻┻
16 */
17 #include <algorithm>
18 #include <iostream>
19 #include <iomanip>
20 #include <cstring>
21 #include <climits>
22 #include <complex>
23 #include <cassert>
24 #include <cstdio>
25 #include <bitset>
26 #include <vector>
27 #include <deque>
28 #include <queue>
29 #include <stack>
30 #include <ctime>
31 #include <set>
32 #include <map>
33 #include <cmath>
34 using namespace std;
35 #define fr first
36 #define sc second
37 #define cl clear
38 #define BUG puts("here!!!")
39 #define W(a) while(a--)
40 #define pb(a) push_back(a)
41 #define Rint(a) scanf("%d", &a)
42 #define Rll(a) scanf("%I64d", &a)
43 #define Rs(a) scanf("%s", a)
44 #define Cin(a) cin >> a
45 #define FRead() freopen("in", "r", stdin)
46 #define FWrite() freopen("out", "w", stdout)
47 #define Rep(i, len) for(LL i = 0; i < (len); i++)
48 #define For(i, a, len) for(LL i = (a); i < (len); i++)
49 #define Cls(a) memset((a), 0, sizeof(a))
50 #define Clr(a, x) memset((a), (x), sizeof(a))
51 #define Fuint(a) memset((a), 0x7f7f, sizeof(a))
52 #define lrt rt << 1
53 #define rrt rt << 1 | 1
54 #define pi 3.14159265359
55 #define RT return
56 #define lowbit(x) x & (-x)
57 #define onenum(x) __builtin_popcount(x)
58 typedef long long LL;
59 typedef long double LD;
60 typedef unsigned long long Uint;
61 typedef pair<LL, LL> pii;
62 typedef pair<string, LL> psi;
63 typedef map<string, LL> msi;
64 typedef vector<LL> vi;
65 typedef vector<LL> vl;
66 typedef vector<vl> vvl;
67 typedef vector<bool> vb;
68 
69 const int maxn = 110;
70 char G[maxn][maxn];
71 int n, m, q;
72 int a, b, c, d;
73 char s[2];
74 
75 int main() {
76 //    FRead();
77     int T;
78     Rint(T);
79     W(T) {
80         scanf("%d%d%d",&n,&m,&q);
81         Cls(G);
82         For(i, 1, n+1)For(j, 1, m+1) G[i][j] = '.';
83         W(q) {
84             scanf("%d%d%d%d%s",&a,&b,&c,&d,s);
85             For(i, a, c+1) For(j, b, d+1) G[i][j] = s[0];
86         }
87         For(i, 1, n+1) {
88             For(j, 1, m+1) {
89                 printf("%c", G[i][j]);
90             }
91             printf("
");
92         }
93     }
94     RT 0;
95 }
D

E.看样例秒懂，取所有数的GCD，然后把所有数与GCD的商加起来就行了。

 1 /*
 2 ━━━━━┒ギリギリ♂ eye！
 3 ┓┏┓┏┓┃キリキリ♂ mind！
 4 ┛┗┛┗┛┃＼○／
 5 ┓┏┓┏┓┃ /
 6 ┛┗┛┗┛┃ノ)
 7 ┓┏┓┏┓┃
 8 ┛┗┛┗┛┃
 9 ┓┏┓┏┓┃
10 ┛┗┛┗┛┃
11 ┓┏┓┏┓┃
12 ┛┗┛┗┛┃
13 ┓┏┓┏┓┃
14 ┃┃┃┃┃┃
15 ┻┻┻┻┻┻
16 */
17 #include <algorithm>
18 #include <iostream>
19 #include <iomanip>
20 #include <cstring>
21 #include <climits>
22 #include <complex>
23 #include <cassert>
24 #include <cstdio>
25 #include <bitset>
26 #include <vector>
27 #include <deque>
28 #include <queue>
29 #include <stack>
30 #include <ctime>
31 #include <set>
32 #include <map>
33 #include <cmath>
34 using namespace std;
35 #define fr first
36 #define sc second
37 #define cl clear
38 #define BUG puts("here!!!")
39 #define W(a) while(a--)
40 #define pb(a) push_back(a)
41 #define Rint(a) scanf("%d", &a)
42 #define Rll(a) scanf("%I64d", &a)
43 #define Rs(a) scanf("%s", a)
44 #define Cin(a) cin >> a
45 #define FRead() freopen("in", "r", stdin)
46 #define FWrite() freopen("out", "w", stdout)
47 #define Rep(i, len) for(LL i = 0; i < (len); i++)
48 #define For(i, a, len) for(LL i = (a); i < (len); i++)
49 #define Cls(a) memset((a), 0, sizeof(a))
50 #define Clr(a, x) memset((a), (x), sizeof(a))
51 #define Fuint(a) memset((a), 0x7f7f, sizeof(a))
52 #define lrt rt << 1
53 #define rrt rt << 1 | 1
54 #define pi 3.14159265359
55 #define RT return
56 #define lowbit(x) x & (-x)
57 #define onenum(x) __builtin_popcount(x)
58 typedef long long LL;
59 typedef long double LD;
60 typedef unsigned long long Uint;
61 typedef pair<LL, LL> pii;
62 typedef pair<string, LL> psi;
63 typedef map<string, LL> msi;
64 typedef vector<LL> vi;
65 typedef vector<LL> vl;
66 typedef vector<vl> vvl;
67 typedef vector<bool> vb;
68 
69 const int maxn = 1010;
70 int n;
71 int a[maxn];
72 int p;
73 
74 int main() {
75 //    FRead();
76     int T;
77     Rint(T);
78     W(T) {
79         Rint(n);
80         Rep(i, n) {
81             Rint(a[i]);
82         }
83         p = a[0];
84         For(i, 1, n) {
85             p = __gcd(p, a[i]);
86         }
87         int ret = 0;
88         Rep(i, n) {
89             a[i] /= p;
90             ret += a[i];
91         }
92         printf("%d %d
", p, ret);
93     }
94     RT 0;
95 }
E

F.两个字符串AB，B只有4个字符，问B是否是A的子串。如果不是的话，有一次机会可以在A中拆成两部分，这两部分中间只有一个字符，分别输出结果。一个flag标记就行。

  1 /*
  2 ━━━━━┒ギリギリ♂ eye！
  3 ┓┏┓┏┓┃キリキリ♂ mind！
  4 ┛┗┛┗┛┃＼○／
  5 ┓┏┓┏┓┃ /
  6 ┛┗┛┗┛┃ノ)
  7 ┓┏┓┏┓┃
  8 ┛┗┛┗┛┃
  9 ┓┏┓┏┓┃
 10 ┛┗┛┗┛┃
 11 ┓┏┓┏┓┃
 12 ┛┗┛┗┛┃
 13 ┓┏┓┏┓┃
 14 ┃┃┃┃┃┃
 15 ┻┻┻┻┻┻
 16 */
 17 #include <algorithm>
 18 #include <iostream>
 19 #include <iomanip>
 20 #include <cstring>
 21 #include <climits>
 22 #include <complex>
 23 #include <cassert>
 24 #include <cstdio>
 25 #include <bitset>
 26 #include <vector>
 27 #include <deque>
 28 #include <queue>
 29 #include <stack>
 30 #include <ctime>
 31 #include <set>
 32 #include <map>
 33 #include <cmath>
 34 #include <set>
 35 
 36 using namespace std;
 37 #define fr first
 38 #define sc second
 39 #define cl clear
 40 #define BUG puts("here!!!")
 41 #define W(a) while(a--)
 42 #define pb(a) push_back(a)
 43 #define Rint(a) scanf("%d", &a)
 44 #define Rll(a) scanf("%I64d", &a)
 45 #define Rs(a) scanf("%s", a)
 46 #define Cin(a) cin >> a
 47 #define FRead() freopen("in", "r", stdin)
 48 #define FWrite() freopen("out", "w", stdout)
 49 #define Rep(i, len) for(LL i = 0; i < (len); i++)
 50 #define For(i, a, len) for(LL i = (a); i < (len); i++)
 51 #define Cls(a) memset((a), 0, sizeof(a))
 52 #define Clr(a, x) memset((a), (x), sizeof(a))
 53 #define Fuint(a) memset((a), 0x7f7f, sizeof(a))
 54 #define lrt rt << 1
 55 #define rrt rt << 1 | 1
 56 #define pi 3.14159265359
 57 #define RT return
 58 #define lowbit(x) x & (-x)
 59 #define onenum(x) __builtin_popcount(x)
 60 typedef long long LL;
 61 typedef long double LD;
 62 typedef unsigned long long Uint;
 63 typedef pair<LL, LL> pii;
 64 typedef pair<string, LL> psi;
 65 typedef map<string, LL> msi;
 66 typedef vector<LL> vi;
 67 typedef vector<LL> vl;
 68 typedef vector<vl> vvl;
 69 typedef vector<bool> vb;
 70 
 71 const int maxn = 111111;
 72 char a[maxn], b[maxn];
 73 int n;
 74 
 75 int main() {
 76 //    FRead();
 77     int T;
 78     Rint(T);
 79     W(T) {
 80         Rs(a); Rs(b);
 81         n = strlen(a);
 82         int ret = 0;
 83         bool ff = 0;
 84         bool exflag = 0;
 85         Rep(i, n-3) {
 86             if(exflag) break;
 87             int tmp = 0;
 88             bool flag = 0;
 89             int k = i;
 90             Rep(j, 4) {
 91                 if(a[k+j] == b[j]) tmp++;
 92                 else if(!flag) {
 93                     tmp++;
 94                     k--;
 95                     flag = 1;
 96                 }
 97             }
 98             if(tmp > ret) {
 99                 ret = tmp;
100                 ff = flag;
101             }
102             if(ret == 4 && !flag) {
103                 exflag = 1;
104                 puts("good");
105                 break;
106             }
107         }
108         if(exflag) continue;
109         if(ff && ret == 4) puts("almost good");
110         else if(ret == 4) {
111             puts("good");
112         }
113         else puts("none");
114     }
115     RT 0;
116 }
F

G.每w-1个为一组，分情况讨论就可以。

  1 /*
  2 ━━━━━┒ギリギリ♂ eye！
  3 ┓┏┓┏┓┃キリキリ♂ mind！
  4 ┛┗┛┗┛┃＼○／
  5 ┓┏┓┏┓┃ /
  6 ┛┗┛┗┛┃ノ)
  7 ┓┏┓┏┓┃
  8 ┛┗┛┗┛┃
  9 ┓┏┓┏┓┃
 10 ┛┗┛┗┛┃
 11 ┓┏┓┏┓┃
 12 ┛┗┛┗┛┃
 13 ┓┏┓┏┓┃
 14 ┃┃┃┃┃┃
 15 ┻┻┻┻┻┻
 16 */
 17 #include <algorithm>
 18 #include <iostream>
 19 #include <iomanip>
 20 #include <cstring>
 21 #include <climits>
 22 #include <complex>
 23 #include <cassert>
 24 #include <cstdio>
 25 #include <bitset>
 26 #include <vector>
 27 #include <deque>
 28 #include <queue>
 29 #include <stack>
 30 #include <ctime>
 31 #include <set>
 32 #include <map>
 33 #include <cmath>
 34 #include <set>
 35 
 36 using namespace std;
 37 #define fr first
 38 #define sc second
 39 #define cl clear
 40 #define BUG puts("here!!!")
 41 #define W(a) while(a--)
 42 #define pb(a) push_back(a)
 43 #define Rint(a) scanf("%d", &a)
 44 #define Rll(a) scanf("%I64d", &a)
 45 #define Rs(a) scanf("%s", a)
 46 #define Cin(a) cin >> a
 47 #define FRead() freopen("in", "r", stdin)
 48 #define FWrite() freopen("out", "w", stdout)
 49 #define Rep(i, len) for(LL i = 0; i < (len); i++)
 50 #define For(i, a, len) for(LL i = (a); i < (len); i++)
 51 #define Cls(a) memset((a), 0, sizeof(a))
 52 #define Clr(a, x) memset((a), (x), sizeof(a))
 53 #define Fuint(a) memset((a), 0x7f7f, sizeof(a))
 54 #define lrt rt << 1
 55 #define rrt rt << 1 | 1
 56 #define pi 3.14159265359
 57 #define RT return
 58 #define lowbit(x) x & (-x)
 59 #define onenum(x) __builtin_popcount(x)
 60 typedef long long LL;
 61 typedef long double LD;
 62 typedef unsigned long long Uint;
 63 typedef pair<LL, LL> pii;
 64 typedef pair<string, LL> psi;
 65 typedef map<string, LL> msi;
 66 typedef vector<LL> vi;
 67 typedef vector<LL> vl;
 68 typedef vector<vl> vvl;
 69 typedef vector<bool> vb;
 70 
 71 int h, w, d;
 72 #define y puts("Yes");
 73 #define n puts("No");
 74 
 75 int main() {
 76 //    FRead();
 77     int T;
 78     Rint(T);
 79     W(T) {
 80         scanf("%d%d%d",&h,&w,&d);
 81         int p = h / (w - 1);
 82         int q = h % (w - 1);
 83         if(q == 0) {
 84             if(p & 1) {
 85                 if(w - 1 == d) y
 86                 else n
 87             }
 88             else {
 89                 if(d == 2) y
 90                 else n
 91             }
 92         }
 93         else {
 94             if(p & 1) {
 95                 if(d == w - q + 1) y
 96                 else n
 97             }
 98             else {
 99                 if(d == q) y
100                 else n
101             }
102         }
103     }
104     RT 0;
105 }
G

H.一开始我还找规律，结果最后暴力模拟就可以了。

 1 /*
 2 ━━━━━┒ギリギリ♂ eye！
 3 ┓┏┓┏┓┃キリキリ♂ mind！
 4 ┛┗┛┗┛┃＼○／
 5 ┓┏┓┏┓┃ /
 6 ┛┗┛┗┛┃ノ)
 7 ┓┏┓┏┓┃
 8 ┛┗┛┗┛┃
 9 ┓┏┓┏┓┃
10 ┛┗┛┗┛┃
11 ┓┏┓┏┓┃
12 ┛┗┛┗┛┃
13 ┓┏┓┏┓┃
14 ┃┃┃┃┃┃
15 ┻┻┻┻┻┻
16 */
17 #include <algorithm>
18 #include <iostream>
19 #include <iomanip>
20 #include <cstring>
21 #include <climits>
22 #include <complex>
23 #include <cassert>
24 #include <cstdio>
25 #include <bitset>
26 #include <vector>
27 #include <deque>
28 #include <queue>
29 #include <stack>
30 #include <ctime>
31 #include <set>
32 #include <map>
33 #include <cmath>
34 #include <set>
35 
36 using namespace std;
37 #define fr first
38 #define sc second
39 #define cl clear
40 #define BUG puts("here!!!")
41 #define W(a) while(a--)
42 #define pb(a) push_back(a)
43 #define Rint(a) scanf("%d", &a)
44 #define Rll(a) scanf("%I64d", &a)
45 #define Rs(a) scanf("%s", a)
46 #define Cin(a) cin >> a
47 #define FRead() freopen("in", "r", stdin)
48 #define FWrite() freopen("out", "w", stdout)
49 #define Rep(i, len) for(LL i = 0; i < (len); i++)
50 #define For(i, a, len) for(LL i = (a); i < (len); i++)
51 #define Cls(a) memset((a), 0, sizeof(a))
52 #define Clr(a, x) memset((a), (x), sizeof(a))
53 #define Fuint(a) memset((a), 0x7f7f, sizeof(a))
54 #define lrt rt << 1
55 #define rrt rt << 1 | 1
56 #define pi 3.14159265359
57 #define RT return
58 #define lowbit(x) x & (-x)
59 #define onenum(x) __builtin_popcount(x)
60 typedef long long LL;
61 typedef long double LD;
62 typedef unsigned long long Uint;
63 typedef pair<LL, LL> pii;
64 typedef pair<string, LL> psi;
65 typedef map<string, LL> msi;
66 typedef vector<LL> vi;
67 typedef vector<LL> vl;
68 typedef vector<vl> vvl;
69 typedef vector<bool> vb;
70 
71 const int maxn = 100010;
72 int n, d, r;
73 bool a[maxn], b[maxn];
74 
75 int main() {
76 //    FRead();
77     int T;
78     Rint(T);
79     W(T) {
80         scanf("%d%d%d",&n,&d,&r);
81         Cls(a); Cls(b);
82         int aa = 1, bb = 1;
83         int ret = 0;
84         while(1) {
85             ret++;
86             aa = ret * d % n;
87             if(b[aa] == 1) break;
88             a[aa] = 1;
89             bb = ret * r % n;
90             if(a[bb] == 1) break;
91             b[bb] = 1;
92         }
93         printf("%d
", ret);
94     }
95     RT 0;
96 }
H

I.最大值最小的问题，枚举虽有长度判断是否满足k条就行。套路二分。

  1 /*
  2 ━━━━━┒ギリギリ♂ eye！
  3 ┓┏┓┏┓┃キリキリ♂ mind！
  4 ┛┗┛┗┛┃＼○／
  5 ┓┏┓┏┓┃ /
  6 ┛┗┛┗┛┃ノ)
  7 ┓┏┓┏┓┃
  8 ┛┗┛┗┛┃
  9 ┓┏┓┏┓┃
 10 ┛┗┛┗┛┃
 11 ┓┏┓┏┓┃
 12 ┛┗┛┗┛┃
 13 ┓┏┓┏┓┃
 14 ┃┃┃┃┃┃
 15 ┻┻┻┻┻┻
 16 */
 17 #include <algorithm>
 18 #include <iostream>
 19 #include <iomanip>
 20 #include <cstring>
 21 #include <climits>
 22 #include <complex>
 23 #include <cassert>
 24 #include <cstdio>
 25 #include <bitset>
 26 #include <vector>
 27 #include <deque>
 28 #include <queue>
 29 #include <stack>
 30 #include <ctime>
 31 #include <set>
 32 #include <map>
 33 #include <cmath>
 34 #include <set>
 35 
 36 using namespace std;
 37 #define fr first
 38 #define sc second
 39 #define cl clear
 40 #define BUG puts("here!!!")
 41 #define W(a) while(a--)
 42 #define pb(a) push_back(a)
 43 #define Rint(a) scanf("%d", &a)
 44 #define Rll(a) scanf("%I64d", &a)
 45 #define Rs(a) scanf("%s", a)
 46 #define Cin(a) cin >> a
 47 #define FRead() freopen("in", "r", stdin)
 48 #define FWrite() freopen("out", "w", stdout)
 49 #define Rep(i, len) for(LL i = 0; i < (len); i++)
 50 #define For(i, a, len) for(LL i = (a); i < (len); i++)
 51 #define Cls(a) memset((a), 0, sizeof(a))
 52 #define Clr(a, x) memset((a), (x), sizeof(a))
 53 #define Fuint(a) memset((a), 0x7f7f, sizeof(a))
 54 #define lrt rt << 1
 55 #define rrt rt << 1 | 1
 56 #define pi 3.14159265359
 57 #define RT return
 58 #define lowbit(x) x & (-x)
 59 #define onenum(x) __builtin_popcount(x)
 60 typedef long long LL;
 61 typedef long double LD;
 62 typedef unsigned long long Uint;
 63 typedef pair<LL, LL> pii;
 64 typedef pair<string, LL> psi;
 65 typedef map<string, LL> msi;
 66 typedef vector<LL> vi;
 67 typedef vector<LL> vl;
 68 typedef vector<vl> vvl;
 69 typedef vector<bool> vb;
 70 
 71 const int maxn = 100010;
 72 int a[maxn];
 73 int n, k;
 74 
 75 bool check(int x) {
 76     int s = a[1], t = s + x - 1;
 77     int cnt = 1;
 78     For(i, 2, n+1) {
 79         if(a[i] <= t) continue;
 80         else {
 81             s = a[i];
 82             t = s + x - 1;
 83             cnt++;
 84         }
 85     }
 86     if(cnt <= k) return 1;
 87     return 0;
 88 }
 89 
 90 int main() {
 91 //    FRead();
 92     int T;
 93     Rint(T);
 94     W(T) {
 95         Rint(n); Rint(k);
 96         For(i, 1, n+1) Rint(a[i]);
 97         int ll = -12, rr = a[n];
 98         while(rr >= ll) {
 99             int mm = (rr + ll) >> 1;
100             if(check(mm)) rr = mm - 1;
101             else ll = mm + 1;
102         }
103         printf("%d
", rr+1);
104     }
105     RT 0;
106 }
107 close
I

J.先O(n*lgn)扫出所有a的v值，再将a求一遍LIS，价值为v统计就行了。

  1 /*
  2 ━━━━━┒ギリギリ♂ eye！
  3 ┓┏┓┏┓┃キリキリ♂ mind！
  4 ┛┗┛┗┛┃＼○／
  5 ┓┏┓┏┓┃ /
  6 ┛┗┛┗┛┃ノ)
  7 ┓┏┓┏┓┃
  8 ┛┗┛┗┛┃
  9 ┓┏┓┏┓┃
 10 ┛┗┛┗┛┃
 11 ┓┏┓┏┓┃
 12 ┛┗┛┗┛┃
 13 ┓┏┓┏┓┃
 14 ┃┃┃┃┃┃
 15 ┻┻┻┻┻┻
 16 */
 17 #include <algorithm>
 18 #include <iostream>
 19 #include <iomanip>
 20 #include <cstring>
 21 #include <climits>
 22 #include <complex>
 23 #include <cassert>
 24 #include <cstdio>
 25 #include <bitset>
 26 #include <vector>
 27 #include <deque>
 28 #include <queue>
 29 #include <stack>
 30 #include <ctime>
 31 #include <set>
 32 #include <map>
 33 #include <cmath>
 34 #include <set>
 35 
 36 using namespace std;
 37 #define fr first
 38 #define sc second
 39 #define cl clear
 40 #define BUG puts("here!!!")
 41 #define W(a) while(a--)
 42 #define pb(a) push_back(a)
 43 #define Rint(a) scanf("%d", &a)
 44 #define Rll(a) scanf("%I64d", &a)
 45 #define Rs(a) scanf("%s", a)
 46 #define Cin(a) cin >> a
 47 #define FRead() freopen("in", "r", stdin)
 48 #define FWrite() freopen("out", "w", stdout)
 49 #define Rep(i, len) for(LL i = 0; i < (len); i++)
 50 #define For(i, a, len) for(LL i = (a); i < (len); i++)
 51 #define Cls(a) memset((a), 0, sizeof(a))
 52 #define Clr(a, x) memset((a), (x), sizeof(a))
 53 #define Fuint(a) memset((a), 0x7f7f, sizeof(a))
 54 #define lrt rt << 1
 55 #define rrt rt << 1 | 1
 56 #define pi 3.14159265359
 57 #define RT return
 58 #define lowbit(x) x & (-x)
 59 #define onenum(x) __builtin_popcount(x)
 60 typedef long long LL;
 61 typedef long double LD;
 62 typedef unsigned long long Uint;
 63 typedef pair<LL, LL> pii;
 64 typedef pair<string, LL> psi;
 65 typedef map<string, LL> msi;
 66 typedef vector<LL> vi;
 67 typedef vector<LL> vl;
 68 typedef vector<vl> vvl;
 69 typedef vector<bool> vb;
 70 
 71 const int maxn = 110;
 72 int n;
 73 int a[maxn];
 74 int v[maxn];
 75 int dp[maxn];
 76 
 77 int f(int x) {
 78     if(x & 1) return 0;
 79     int p = 0;
 80     int cur = 1;
 81     while(x >= cur && x % cur == 0) {
 82         cur <<= 1;
 83         p++;
 84     }
 85     return p - 1;
 86 }
 87 
 88 int main() {
 89 //    FRead();
 90     int T;
 91     Rint(T);
 92     W(T){
 93         Rint(n);
 94         For(i, 1, n+1) {
 95             Rint(a[i]);
 96             v[i] = f(a[i]);
 97         }
 98         int ret = v[1]; Cls(dp);
 99         For(i, 1, n+1) dp[i] = v[i];
100         For(i, 2, n+1) {
101 //            dp[i] = v[i];
102             For(j, 1, i) {
103                 if(a[i] > a[j]) {
104                     dp[i] = max(dp[i], dp[j]+v[i]);
105                 }
106             }
107             ret = max(ret, dp[i]);
108         }
109         printf("%d
", ret);
110     }
111     RT 0;
112 }
J
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/kirai/p/5730735.html