http://codeforces.com/contest/1333
C. Eugene and an array
题意：如果一个数列没有和为0的区间，就是好的，给定一个数列，问有几个子区间是好的。
计数
枚举右端点，每次左端点最左不能包含和为0的区间。
先预处理出每个位置以它为右端点最小的和为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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
const int INF = 0x3f3f3f3f;
ll a[N];
map<ll, int>mp;
ll sum[N], ans;
int pos[N];
int n, mx;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
mp[0] = 0;
for (int i = 1; i <= n; i++)sum[i] = sum[i - 1] + a[i];
for (int i = 1; i <= n; i++) {
if (!mp.count(sum[i]))mp[sum[i]] = i;
else {
pos[i] = mp[sum[i]] + 1;
mp[sum[i]] = i;
}
}
for (int i = 1; i <= n; i++) {
mx = max(mx, pos[i]);
ans += i - mx;
}
printf("%lld\n", ans);
return 0;
}
|
D. Challenges in school №41
题意：n个人，每人头朝左或朝右，每次至少选一对面对面的人让他们都转到反方向。直到每人面对面结束。问怎么选使得次数恰好为k。
先找到最小值和最大值。
贪心找到最小值，每次把能转的都转了，可以知道答案不会更小。
最大值就是每个R右边的L个数，随便怎么算都一样。或者在算最小值的时候一起算了。
每次操作看作一层，这一层的所有转头都可以拆开来分几次，如果把每一层都拆完，就是最大值了。所以只要k在最小最大值之间，一定可以凑出来，方法就是拆，直到剩下的层数满足加上之后恰好为k，就不在拆了，每层完整地输出。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 3e6 + 10;
int n, k, mink, maxk;
char s[N];
vector<int>q[N];
bool cal() {
int cnt = 0;
for (int i = 1; i < n; i++) {
if (s[i] == 'R'&&s[i + 1] == 'L') {
cnt++;
swap(s[i], s[i + 1]);
q[mink].push_back(i);
i++;
}
}
if (cnt)mink++, maxk += cnt;
return cnt;
}
void solve() {
int p = 0, cnt = 0;
while (mink - p < k) {
while (cnt < (int)q[p].size() && mink - p < k) {
printf("1 %d\n", q[p][cnt]);
cnt++;
k--;
}
if (cnt == (int)q[p].size())p++, cnt = 0;
}
for (int i = p; i < mink; i++) {
printf("%d", (int)q[i].size() - cnt);
for (int j = cnt; j < (int)q[i].size(); j++) {
printf(" %d", q[i][j]);
}
puts("");
cnt = 0;
}
}
int main() {
scanf("%d%d", &n, &k);
scanf("%s", s + 1);
while (mink <= k && cal());
if (mink > k || maxk < k) { puts("-1"); return 0; }
solve();
return 0;
}
|
E. Road to 1600
题意：n*n的棋盘上只有车或者皇后，走法同国际象棋，给棋盘上每个格子赋值，不能重复，初始在1，每次在能到的格子里选最小值，并标记目标，如果路线上都标完了，就花一块钱跳到没标记的最小格子上，重复直到都标满了。要求皇后花的钱严格多于车。
构造
n小于3时都能到，所以无解。
n为3时，构造出一个特解，这样皇后一定是从8到9，多花一块钱。
n为4时在最外层加一圈，里面还是n=3时的，只是都增加了一些。
1
2
3
4
| 8+8 7+8 6+8 7
5+8 1+8 2+8 6
4+8 9+8 3+8 5
1 2 3 4
|
n为5时再套一圈。
1
2
3
4
5
| 8+17 7+17 6+17 7+9 1
5+17 1+17 2+17 6+9 2
4+17 9+17 3+17 5+9 3
1+9 2+9 3+9 4+9 4
9 8 7 6 5
|
以此类推。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 3e6 + 10;
int n;
int a[510][510]{ {0},{0,8,7,6},{0,5,1,2},{0,4,9,3} };
int main() {
scanf("%d", &n);
if (n <= 2) { puts("-1"); return 0; }
int cur = 1;
for (int i = n; i > 3; i--) {
if (i & 1) {
for (int j = 1;j <= i; j++)a[j][i] = cur++;
for (int j = i - 1; j >= 1; j--)a[i][j] = cur++;
}
else {
for (int j = 1; j <= i; j++)a[i][j] = cur++;
for (int j = i - 1; j >= 1; j--)a[j][i] = cur++;
}
}
for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)a[i][j] += cur - 1;
for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)
printf("%d%c", a[i][j], " \n"[j == n]);
return 0;
}
|
F. Kate and imperfection
题意：定义一个集合的不完美度为集合中任意两个数的gcd的最大值。对于1到n的序列，求长度为i所有子集的不完美度的最小值。
对于一个数，如果算不完美度时它的因数没有被放入集合中，那么把它的因数放入集合一定优于把它放入集合。
所以一个数被放入集合一定说明它的所有因数也都在集合里。那么结果gcd一定是某个数的最大的不等于自身的因数。
并且每个数的最大因数一定出现且仅作为答案出现了一次（除非有几个数的最大因数相等），因为可以假设每个数在所有因数都加入后马上加入。
且能够发现答案是非递减的，所以可以nlogn筛出所有数的最大因数，再排序后逐个输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 3e6 + 10;
int n;
int vis[N];
int main() {
scanf("%d", &n);
vis[1] = 1;
for (int i = 2; i <= n; i++) {
vis[i] = max(vis[i], 1);
for (int j = i + i; j <= n; j += i)vis[j] = i;
}
sort(vis + 1, vis + n + 1);
for (int i = 2; i <= n; i++)printf("%d%c", vis[i], " \n"[i == n]);
return 0;
}
|
