https://codeforces.com/contest/1371

D. Grid-00100

 

题意:要求构造一个含有k个1的n*n的01矩阵,设R为各行的和,C为各列的和,要求最小化 f(A)=(max(R)min(R))2+(max(C)min(C))2f(A) = (\max(R)-\min(R))^2 + (\max(C)-\min(C))^2

构造

平均分配就好了。先算出每行有几个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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 3e5 + 10;
int T;
int a[400][400];
int main() {
scanf("%d", &T);
while (T--) {
int n, k;
scanf("%d%d", &n, &k);
int c = 0, r = 0;
for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)a[i][j] = 0;
int u = (int)ceil(1.0*k / n), d = k / n, rs = k % n;
for (int i = 0; i < n; i++) {
int nd;
if (i < rs)nd = u;
else nd = d;
for (int j = 0; j < nd; j++) {
a[i][c] = 1;
c = (c + 1) % n;
}
}
int ans;
if (k%n == 0)ans = 0;
else ans = 2;
printf("%d\n", ans);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)printf("%d", a[i][j]);
puts("");
}
}
return 0;
}

 

E1. Asterism (Easy Version)

 

题意:给定一个数组,对它重新排列,初始有一个数 x ,要满足每次都比数组中对应位置大,每次比较完手里的数+1。f(x) 为初始数为 x 时有多少个可行的排列。要求找出所有 f(x) mod p 不为 0 的 x 。(2pn2000),(1ai2000)(2 \le p \le n \le 2000),(1 \le a_i \le 2000)

本题可以枚举x,只要O(n)计算 f(x)。

对于第一个位置,可以选择小于等于 x 的数;第二个位置可以选择剩下的小于等于 x+1 的数。以此类推。

所以维护一个前缀和记录小于等于 i 的数的个数。由于每次比较完会少一个,所以乘 cnt[x+j]jcnt[x+j]-j

注意前缀和要初始化2*2000个,因为 x+jx+j 最大为2*2000 !!!

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 3e5 + 10;
int n, p;
int cnt[N];
int a[N];
vector<int>vc;
int main() {
scanf("%d%d", &n, &p);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
cnt[a[i]]++;
}
for (int i = 1; i <= 4010; i++)cnt[i] += cnt[i - 1];
for (int x = 1; x <= 2000; x++) {
int tmp = 1;
for (int j = 0; j < n; j++) {
if (cnt[x + j] - j <= 0) {
tmp = 0;
break;
}
tmp = tmp * (cnt[x + j] - j) % p;
}
if (tmp != 0)vc.push_back(x);
}
printf("%d\n", (int)vc.size());
for (int u : vc)printf("%d ", u);
puts("");
return 0;
}

 

E2. Asterism (Hard Version)

 

(2pn2000),(1ai2000)(2 \le p \le n \le 2000),(1 \le a_i \le 2000)

乱搞+滑动窗口

由于必须要每一位都不小于,所以 x<max(a[i])n+1x<max(a[i])-n+1 时是不可行的。而 xmax(a[i])x\ge max(a[i]) 时就是 n 的阶乘,模 p 一定为0,也不用考虑。所以 x 的范围是 O(n)的,所以本题同样要枚举 x ,但是本题只能 O(1)计算了。

s[i]s[i] 为小于等于 i 的数的个数,这可以upperbound出来。

则对于一个 x ,如果在某次比较时乘上的那个数 s[x+j]j=0modps[x+j]-j=0\mod p。则 x 不可行,其中 j[0,n)j\in[0,n)

考虑枚举 s[i] 中的 i ,所以把 x+jx+j 设为 tt,则式子变为 s[t](tx)=0modps[t]-(t-x)=0\mod p,移项整理得 x=ts[t]modpx=t-s[t]\mod p,所以只要枚举 tt,把不符合条件的 x 删掉即可。

但是删的话复杂度还是不够,所以考虑滑动窗口,从后向前枚举x,最大的 x 受到 t[mx,mx+n)t\in [mx,mx+n) 这一段的影响,倒数第二个受到 t[mx1,mx+n1)t\in [mx-1,mx+n-1) 的影响,每次滑动时只要改变2位。对于当前的 x,判断是否有与 x 同余的 ts[t]t-s[t]

注意枚举 x 的下界要大于 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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 3e5 + 10;
int n, p;
int cnt[N];
int a[N], vis[N], mx;
vector<int>vc;
int s(int x) {
return upper_bound(a + 1, a + n + 1, x) - a - 1;
}
int main() {
scanf("%d%d", &n, &p);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
mx = max(mx, a[i]);
}
sort(a + 1, a + n + 1);
for (int i = mx; i <= mx + n - 1; i++) {
vis[((i - n) % p + p) % p]++;
}
for (int x = mx - 1; x >= max(1, mx - n + 1); x--) {
vis[((x - s(x)) % p + p) % p]++;
vis[((x + n - s(x + n)) % p + p) % p]--;
if (!vis[x%p])vc.push_back(x);
}
sort(vc.begin(), vc.end());
printf("%d\n", (int)vc.size());
for (int u : vc)printf("%d ", u);
puts("");
return 0;
}

 

F. Raging Thunder

 

题意:有一个传送带,类似 ><>>< ,每个箭头右边有一个洞,最左边也有一个洞,箭头指向相同的会顺着滑,相对的会落入中间的洞,多次询问,每次指定一个区间翻转箭头,并在区间内所有箭头出放一个球,问含有最多的球的洞里的球数。

丧心病狂的分类讨论。。在补了。。