A-Arithmetic Array
题意：给定一个数组，一次可以给数组增加一个非负的元素，问最少需要增加多少次，可以使数组满足：数组元素之和等于数组的长度
思路：枚举初始给定数组之和。
若小于数组长度，则再增加一个整数即可（肯定存在这样的一个正数）；
若等于数组长度，则不用添加元素；
若大于数组长度，则需要添加（数组之和减数组长度）个0.
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int T; cin>>T;
while(T--)
{
int n; cin>>n;
ll sum = 0, ans;
for(int i = 0; i < n; i++)
{
int x; cin>>x;
sum += x;
}
if(sum < n) ans = 1;
else if(sum == n) ans = 0;
else ans = sum-n;
cout<<ans<<endl;
}
return 0;
}
|
B-Bad Boy
题意：一个人站在n×m的方格中（x, y）处，让你在方格中挑选两个位置放置两个悠悠球，然后这个人去捡悠悠球再回到原位置，问这两个悠悠球放在哪能让他走的路程最大。
思路：第一个球放在离他现在位置最远的地方，第二个球放在离第一个球最远的位置（其实就是某两个顶点处）
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int T; cin>>T;
while(T--)
{
int n, m, xx, yy;
int x1, y1, x2, y2;
cin>>n>>m>>xx>>yy;
if(xx <= (n+1)/2) x1 = n;
else x1 = 1;
if(yy <= (m+1)/2) y1 = m;
else y1 = 1;
if(x1 == n) x2 = 1;
else x2 = n;
if(y1 == m) y2 = 1;
else y2 = m;
cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
}
return 0;
}
|
C-Challenging Cliffs
题意：给定一个数组，每个数组元素代表一座山，值代表高度。从i -> i+1， 如果$h_{i} <= h_{i+1}$，则贡献值加1。让你重新排列数组，找出贡献值最大的排列，同时还要满足数组第一个值和最后一个值的差值是最小的。
思路：排个序。找出最小差值，然后按照排序之后的顺序分段输出即可保证贡献值最大。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int T; cin>>T;
while(T--)
{
int n; cin>>n;
int a[n+1];
for(int i = 1; i <= n; i++) cin>>a[i];
sort(a+1, a+n+1);
int minn = a[2]-a[1], id = 1;
for(int i = 3; i <= n; i++)
{
if(a[i]-a[i-1] < minn)
{
minn = a[i]-a[i-1];
id = i-1;
}
}
cout<<a[id]<<" ";
for(int i = id+2; i <= n; i++) cout<<a[i]<<" ";
for(int i = 1; i < id; i++) cout<<a[i]<<" ";
cout<<a[id+1]<<endl;
}
return 0;
}
|
D-Deleting Divisors
题意：Alice和Bob在玩游戏，Alice和Bob又在玩游戏，Alice和Bob总在玩游戏（o_o）
给定一个数字n，每次可以拿走一个n的除数（不能是1或n），n相应减少。无法再拿走除数时就输。Alice先手。
（参考了这位的博客：链接）
思路：博弈论嘛，先分析出必败态为最后剩下一个质数（质数除了2都是奇数）。然后枚举情况（可以打表观察规律，这样推规律的时候就会方向清晰一点）
一、Alice先手拿到偶数。
（1）这个偶数由奇数*偶数组成：在最优选择下，Alice会减一个奇数的除数，剩下一个奇数给Bob，Bob只能减奇数的除数（因为没有偶数的除数），剩下一个偶数给Alice，开始循环。。。则Alice必胜
（2）这个偶数由偶数*偶数组成（可以表示为$2^{n}$）：在最优选择下，Alice会选择减去$2^{n-1}$，剩下$2^{n-1}$给Bob（不这样减的话，Bob一定拿到奇数*偶数，则Bob就一定赢），Bob也同样会继续选择减去$2^{(n-1)-1}$。那么最终状态就是：如果n是偶数，则Bob拿到2，Bob输；如果n是奇数，则Alice拿到2，Alice输。
二、Alice先手拿到奇数
Alice只能减去一个奇数的除数，则Bob拿到由奇数*偶数组成的偶数，即Alice必输。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int T; cin>>T;
while(T--)
{
int n; cin>>n;
if(n&1) cout<<"Bob"<<endl;
else
{
int cnt = 0;
while(n%2 == 0)
{
n /= 2;
cnt++;
}
if(n != 1) cout<<"Alice"<<endl;
else
{
if(cnt&1) cout<<"Bob"<<endl;
else cout<<"Alice"<<endl;
}
}
}
return 0;
}
|
E-Erase and Extend (Easy Version)
题意：给定一个长度为n的字符串s，可以无限次进行两种操作：删除最后一个元素或者使s = s+s。求通过这两种操作，可以得到的长度为k的最小的字符串。
思路：建议先看一遍代码。最终的答案肯定是s的一个前缀子串的重复。然后证明这种做法的合理性：(cnt代表：从s[0]开始的，最终结果中的前缀子串的长度)。纯证明肯定是没有举栗子更好理解。
（1）s[i] > s[i%cnt]
第i个元素比前缀子串中对应位置的元素大，显而易见该结束了
举个栗子：dcadcb 这种情况就是：目前的最优字串为dca，然后遇到了b，b>a，如果结束，最优字串重复为：dcadcadca，否则就是：dcadcbdca。肯定前面的是要小的，所以说明确实该结束了。
（2）s[i] < s[i%cnt]
第i个元素比最优前缀中对应位置的元素小，那就说明最优字串可以扩充s[i]。
举个栗子：dcbdca 这种情况就是：目前的最优字串为dcb，然后遇到了a，a<b，如果扩充，最优字串重复就是 dcbdcadcbdca，否则就是 dcbdcbdcbdcb，肯定是前面小，所以最优字串应该扩充
（3）s[i] == s[i%cnt]
这种情况是不能break的。因为不知道s[i+1]和s[(i+1)%cnt]的大小情况。
举个栗子：dbda ，等于说现在到了第二个d的位置，现在最优字串是db，如果break，第一种情况的答案就是dbdbdbdb，和dbdadbda的比较，显见是不能break；
再举个栗子：dbdc，和上面差不多，break后就是dbdbdbdb，和dbdcdbdc比较确实是更优的。
综上所述不能break。同样的道理，也不能更新最优字串到s[i]。
大家举举栗子就会发现很好理解。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int n, k; cin>>n>>k;
string s; cin>>s;
int cnt = 1;
for(int i = 0; i < n; i++)
{
if(s[i] > s[i%cnt]) break;
if(s[i] < s[i%cnt]) cnt = i+1;
}
for(int i = 0; i < k; i++) cout<<s[i%cnt];
return 0;
}
|
F-Erase and Extend (Hard Version)
E的代码的时间复杂度是O(n)，可以直接过F。