找机会填F题的坑w
C - Count Order
#题意简述
给出两个排列$P$与$Q$($2≤N≤8$)，求出它们字典序之差的绝对值。
#简要做法
法1：观察到N很小，可以直接求暴力全排列求字典序。这里补上自己之前不会用的stl做法
Code1
|
|
using namespace std; |
const int maxn = 10; |
int n; |
int p[maxn] , q[maxn] , t[maxn]; |
inline void init() { |
for(register int i = 1; i <= n; ++i) |
t[i] = i; |
} |
inline bool check(int *a) { |
for(register int i = 1; i <= n; ++i) |
if(a[i] != t[i]) return false; |
return true; |
} |
int main() { |
cin >> n; |
for(register int i = 1; i <= n; ++i) cin >> p[i]; |
for(register int i = 1; i <= n; ++i) cin >> q[i]; |
init(); |
int cnt1 = 0 , cnt2 = 0; |
while(!check(p)) { |
cnt1++; |
next_permutation(t + 1 , t + n + 1); |
} |
init(); |
while(!check(q)) { |
cnt2++; |
next_permutation(t + 1 , t + n + 1); |
} |
cout << abs(cnt1 - cnt2) << endl; |
return 0; |
} |
法2：若N比较大，则可以用康托展开求序：
康托展开：在排列$P$中，对第$k$位而言，使前$k-1$位相同，则其一定大于$(小于p[k]且尚未出现的数字个数)\cdot(n-k)!$，因此答案为$\sum_{i=1}^nC(p[i])\cdot(n-i)! + 1$。其中C(p[i])为排列中小于p[i]但是尚未出现的数字个数。时间复杂度$O(N^2)$，用树状数组优化为$O(NlogN)$ 反正不知道比n!复杂度高到哪里去了
Code2
|
|
|
|
using namespace std; |
const int maxn = 10; |
int n; |
int p[maxn] , q[maxn] , tree[maxn]; |
ll f[maxn]; |
void init() { |
f[0] = 1; |
for(register int i = 1; i <= n; ++i) |
f[i] = i * f[i - 1]; |
} |
inline void update(int x) { |
for(register int i = x; i <= n; i += lowbit(i)) |
tree[i] += 1; |
} |
inline ll query(int x) { |
ll ret = 0; |
for(register int i = x; i; i -= lowbit(i)) |
ret += tree[i]; |
return ret; |
} |
ll cantor(int *a) { |
memset(tree , 0 , sizeof(tree)); |
ll ret = 0; |
for(register int i = 1; i <= n; ++i) { |
ll cnt = query(a[i]); //求出已经有多少个小于a[i]的数已经出现了 |
update(a[i]); |
ret += (a[i] - cnt - 1) * f[n - i]; |
} |
return ret + 1; //由于字典序从1开始，所以加1 |
} |
int main() { |
ios::sync_with_stdio(false); |
cin.tie(nullptr); |
cin >> n; |
for(register int i = 1; i <= n; ++i) cin >> p[i]; |
for(register int i = 1; i <= n; ++i) cin >> q[i]; |
init(); |
ll a = cantor(p) , b = cantor(q); |
cout << abs(a - b) << endl; |
return 0; |
} |
D - Semi Common Multiple
#题意简述
给定一个偶数序列$A(a_i≤10^9)$，长度为$N(N≤10^5)$。试求$1至M(M≤10^9)$中，有多少个整数X可以由任意序列A中的数以$X=a_k\cdot(p+0.5)$表现出来。
#简要做法
由于$a_k$都是偶数，可以整理得$X=\frac{a_k}{2}\cdot(2p+1)$，即X为一切$\frac{a_k}{2}$的奇数倍。因此求出序列$A$的一半的最小公倍数，如果其不是所有元素一半的奇数倍或者大于M，则不合法。所有满足条件的X一定是X的奇数倍，所以答案为M/X/2，如果M/X为奇数则答案再自加1。
Code
|
|
using namespace std; |
ll n , m; |
const int maxn = 1e5 + 5; |
ll a[maxn]; |
inline ll gcd(ll a , ll b) { |
return b == 0 ? a : gcd(b , a % b); |
} |
inline ll lcm(ll a , ll b) { |
return a / gcd(a , b) * b; |
} |
int main() { |
ios::sync_with_stdio(false); |
cin.tie(nullptr); |
cin >> n >> m; |
ll minx; |
bool valid = 1; |
for(register int i = 1; i <= n; ++i) { |
cin >> a[i]; a[i] >>= 1; |
if(i == 1) minx = a[1]; |
minx = lcm(minx , a[i]); |
if(minx > m) valid = 0; |
} |
for(register int i = 1; i <= n; ++i) |
if(!(minx / a[i] & 1)) { |
valid = 0; |
break; |
} |
if(!valid) |
cout << 0 << endl; |
else { |
ll ans = m / minx; |
if(ans & 1) ans++; |
ans /= 2; |
cout << ans << endl; |
} |
return 0; |
} |
E - Change a Little Bit
Problem Statement
For two sequences $S$ and $T$ of length $N$ consisting of 0 and 1, let us define $f(S,T)$ as follows:
- Consider repeating the following operation on $S$ so that $S$ will be equal to $T$. $f(S,T)$ is the minimum possible total cost of those operations.
- Change $S_i$ (from 0 to 1 or vice versa). The cost of this operation is $D×C_i$, where $D$ is the number of integers $j$ such that $S_j≠T_j(1≤j≤N)$just before this change.
There are $2N×(2N−1)$pairs $(S,T)$ of different sequences of length $N$ consisting of $0$ and $1$. Compute the sum of $f(S,T)$ over all of those pairs, modulo $(10^9+7)$.
Constraints
- $1≤N≤2×10^5 1≤N≤2×10^5$
- $1≤C_i≤10^9 1≤C_i≤10^9$
- All values in input are integers.
#简要做法
由排序不等式可知，想要有最小的代价，必须最后处理大的数。假设一对完全不同的$(S,T)$，令$C_i$递减，则$f(S,T)=\sum_{i=1}^NC_i\cdot i$。现在已知有$2^{2N}$对$(S,T)$，对于任意一个$C_i$当它和对应的一位不同时才会被计算上，它前面的$(i-1)$为各自有$\frac{1}{2}$的概率和已有序列不同，因此期望计算$\frac{i-1}{2}$次，合计期望$\frac{i+1}{2}$次，又该位本身有$\frac{1}{2}$的概率被计算，因此合计期望为$\frac{i+1}{4}$次，可推导出答案为$2^{2N-2}\cdot\sum_{i=1}^NC_i\cdot(i+1))$。
Code
|
|
using namespace std; |
const ll maxn = 2e5 + 5 , mod = 1e9 + 7; |
int n; |
ll c[maxn]; |
ll fpow(ll x , ll k) { |
ll ans = 1 , base = x; |
while(k) { |
if(k & 1) ans = ans * base % mod; |
base = base * base % mod; |
k >>= 1; |
} |
return ans; |
} |
inline bool cmp(ll a , ll b){ return a > b; } |
int main() { |
ios::sync_with_stdio(false); |
cin.tie(nullptr); |
cin >> n; |
for(register int i = 1; i <= n; ++i) cin >> c[i]; |
sort(c + 1 , c + n + 1 , cmp); |
ll ans = 0; |
for(register int i = 1; i <= n; ++i) |
ans = (ans + c[i] * (i + 1) % mod) % mod; |
ans = ans * fpow(2 , 2 * n - 2) % mod; |
cout << ans << endl; |
return 0; |
} |