题面：https://acm.ecnu.edu.cn/contest/113/
A. oxx 的小姐姐们
题意：问是否用若干个$1 \times p$个长方形组成一个$m \times n$的长方形，长方形编号为1至$mn$若可以构成则输出每一个位置上的长方形编号否则输出No
解法：要构成必须满足$p|mn$，又p为质数则$p|n$或者$p|m$，如果都不满足则输出no
否则就先将可以整除的部分填满，剩下的不能整除的部分用边长为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
using namespace std;
const int maxn = 2e5 + 10;
int gcd(int a, int b)
{
if(a % b == 0)
return b;
return gcd(b, a % b);
}
int a[200][200];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, p;
cin >> n >> m >> p;
if(n % p && m % p)
cout << "No" << endl;
else
{
cout << "Yes" << endl;
if(n % p == 0)
{
int idx = 1;
int t = m / p;
for(int i = 0; i < n; i++)
for(int k = 0; k < t; k++,idx++)
for(int j = k * p; j < (k + 1) * p; j++)
a[i][j] = idx;
t = m % p;
for(int i = m / p * p; i < m; i++)
for(int k = 0; k < n / p; k++, idx++)
for(int j = k * p; j < (k + 1) * p; j++)
a[j][i] = idx;
}
else
{
int idx = 1;
int t = m / p;
for(int i = 0; i < n; i++)
for(int k = 0; k < t; k++,idx++)
for(int j = k * p; j < (k + 1) * p; j++)
a[i][j] = idx;
t = m % p;
for(int i = m / p * p; i < m; i++)
for(int k = 0; k < n / p; k++, idx++)
for(int j = k * p; j < (k + 1) * p; j++)
a[j][i] = idx;
}
for(int i = 0; i < n; i++, cout << endl)
for(int j = 0; j < m; j++)
cout << a[i][j] << ' ';
}
return 0;
}
B. 莫干山奇遇
题意：给一个长度为$n$的序列 $a_1,a_2,…,a_n$，求一个长度为$m$的序列$b_1,b_2,…,b_m$使得：
$a_1,a_2,…,a_n$是$b_1,b_2,…,b_m$的子序列（不一定连续），且存在常数$p>0$使得$b_1,b_2,…,b_m$是一个 p-莫干山序列。
序列$s_1,s_2,…,s_n$是$p$-莫干山序列，当且仅当：存在$0 ≤i x < p $对于$1≤i≤n$满足$s_i=(x+i)modp$。
解法：首先注意到 p 的取值应该就是 $max a_i+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
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn];
int n, m;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int mmax = 0;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> a[i];
mmax = max(mmax, a[i]);
}
ll cnt = 0;
int idx = 0;
for(int i = 1; i < n; i++)
{
if(a[i] - a[i - 1] == 1) continue;
else
{
if(a[i] - a[i - 1] > 1)
{
cnt += a[i] - a[i - 1] - 1;
continue;
}
else
{
cnt += mmax - a[i - 1];
cnt += a[i];
continue;
}
}
}
cout << cnt + n << endl;
}
C. 痛苦的 01 矩阵
题意：现有一个$n\times n$的 01 矩阵 M。
定义$cost(i,j)$为：把第$i$行和第$j$列全部变成1最少需要改动多少个元素。
定义矩阵的痛苦值$pain(M)$为：
求出初始矩阵的痛苦值和每次修改操作之后的痛苦值。
每次操作是将原先位置上的数字翻转。
解法：用一个数学式子将每次需要计算的痛苦值进行替换。
用 ri 表示第 i 行有多少个 0，用 ci 表示第 j 列有多少个 0，bij 表示第 i 行第 j 列是否为 0。则cost(i,j)=ri+cj−bij 。
对痛苦值的式子进行展开得到
其中 C 为整个矩阵中 0 的个数。
只需要计算每次修改带来的列和行和总数的变化即可。
计算的时候需要注意取模计算不要溢出或者减多了即可。
给一个tip(经验教训)如果需要取模计算减的话可以先加一个模的东西再减。
如果相乘爆long long了可以按位进行计算、给出了模板(虽然没用到)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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
using namespace std;
const int maxn = 2e5 + 10;
const int MOD = 1e9 + 7;
ll r[maxn], b[maxn];
ll C;
map<pii, int> Q;
ll mul(ll a, ll b)
{
ll ans = 0, step = a % MOD;
while (b)
{
if (b & 1L) ans += step;
if (ans >= MOD) ans %= MOD;
step <<= 1L;
if (step >= MOD) step %= MOD;
b >>= 1L;
}
return ans % MOD;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("in.txt", "r", stdin);
ll n, k, q;
cin >> n >> k >> q;
C = n * n - k;
C mo;
while(k--)
{
int x, y;
cin >> x >> y;
Q[mp(x, y)] = 1;
r[x]++, b[y]++;
}
for(int i = 1; i <= n; i++)
{
r[i] = n - r[i];
b[i] = n - b[i];
}
ll ans = 0;
for(int i = 1; i <= n; i++)
{
ans += (r[i] * r[i] % MOD + b[i] * b[i] % MOD);
ans mo;
}
ans mo;
ans = ans * (n - 2);
ans += 2 * C * C + C;
ans mo;
cout << ans << endl;
while(q--)
{
int u, v;
cin >> u >> v;
if(Q[mp(u, v)] == 0)
{
Q[mp(u, v)] = 1;
ans = ans + 1 + MOD - 4 * C % MOD;
C--;
ans = ans + MOD - (n - 2) * (2 * r[u] - 1) % MOD;
r[u]--;
ans = ans + MOD - (n - 2) * (2 * b[v] - 1) % MOD;
b[v]--;
ans mo;
cout << ans << endl;
}
else
{
Q[mp(u, v)] = 0;
ans = ans + 1 + 4 * C + 2;
C++;
ans = ans + (n - 2) * (2 * r[u] + 1) % MOD;
ans mo;
r[u]++;
ans = ans + (n - 2) * (2 * b[v] + 1) % MOD;
ans mo;
b[v]++;
ans mo;
cout << ans << endl;
}
}
return 0;
}