Pre
感谢素不相识的巨佬租酥雨的悉心教导，连我这个蒟蒻到可以明白 \(F\) 题。
A
Solution
签到成功。
Code
#include<cstdio>
using namespace std;
int main(){int a;scanf ("%d", &a);printf("%d\n", 3 * a * a);return 0;}
B
Solution
签到成功
Code
#include<cstdio>
using namespace std;
int main(){
int a, b;
scanf ("%d%d", &a, &b);
int ans = a / (b * 2 + 1);
if (a > ans * (b * 2 + 1)) ans++;
printf ("%d\n", ans);
return 0;
}
C
Solution
可以发现 \(n-1\) 个答案都是一样的，找出最大值和次大值就可以了。
Code
#include<bits/stdc++.h>
#define xx first
#define yy second
#define ll long long
using namespace std;
const int N = 200000 + 5;
int n;
pair<int, int> info[N];
int main () {
scanf ("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf ("%d", &info[i].xx);
info[i].yy = i;
}
sort (info + 1, info + n + 1);
for (int i = 1; i <= n; ++i) {
if (i == info[n].yy) {
printf ("%d\n", info[n - 1].xx);
}
else printf ("%d\n", info[n].xx);
}
return 0;
}
D
Solution
从后往前确定每一个位置的值，先是把后面的异或起来，再和 \(a_i\) 异或起来，就是这个位置的值。
由调和级数可以知道时间复杂度为 \(O(n\ logn)\) 的。
Code
#include<bits/stdc++.h>
#define xx first
#define yy second
#define ll long long
using namespace std;
const int N = 200000 + 5;
int a[N], n, cnt;
int ans[N];
int main () {
scanf ("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf ("%d", &a[i]);
}
for (int i = n; i >= 1; --i) {
int tmp = 0;
for (int j = n / i; j >= 1; --j) {
tmp ^= ans[j * i];
}
ans[i] = tmp ^ a[i];
cnt += ans[i];
}
printf ("%d\n", cnt);
for (int i = 1; i <= n; ++i) {
if (!ans[i]) {continue;}
printf ("%d ", i);
}
return 0;
}
E
Solution
\(Dilworth\) 直接应用，求出多少个上升子序列就可以了。
Code
#include<bits/stdc++.h>
#define xx first
#define yy second
#define ll long long
using namespace std;
const int N = 200000 + 5;
int a[N], n;
int stk[N], top;
int main () {
scanf ("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf ("%d", &a[i]);
}
stk[1] = 1;
top = 1;
for (int i = 2; i <= n; ++i) {
if (a[i] <= a[stk[top]]) {
stk[++top] = i;
}
else {
int l = 1, r = top;
while (l < r) {
int mid = (l + r) / 2;
if (a[stk[mid]] < a[i]) {
r = mid;
}
else {
l = mid + 1;
}
}
stk[l] = i;
}
}
printf ("%d\n", top);
return 0;
}
F
Solution
考虑使用 \(f[i][j][k]\) 来表示前 \(i\) 个数，并且其中有 \(j\) 个是大于 \(i\) 的，并且此时的 \(oddness\) 为 \(k\) 的方案数。
由于统计的是一定有 \(j\) 个大于 \(i\) 的，此时对于每一个大于 \(i\) 的，我们只统计 \(i-j\) 对 \(k\) 的贡献。
所以 \(f[i][j][k]\) 只能对 \(f[i+1][xxxx][k+j]\) 有贡献，所以我们需要讨论对不同的 \(xxxx\) 的贡献。
假设 \(p[i+1]=i+1\) 此时 \(xxxx=j\) 并且系数为 \(1\)
假设 \(p[i+1]\leq i+1\&p[x]=i+1\&x\leq i+1\)，此时的 \(x\) 有 \(j\) 种选择，\(p[j+1]\) 有 \(j\) 种选择，则 \(xxxx=j-1\)，并且系数为 \(j*j\)
假设 \(p[i+1]>i+1\&p[x]=i+1\&x>i+1\)，此时的 \(x\) 有 \(1\) 种选择，\(p[i+1]\) 有 \(j\) 种选择，则 \(xxxx=j+1\) ，并且系数为 \(1\)。
剩下的情况就是\((p[i+1]\leq i+1)\ xor\ (p[x]=i+1\&x\leq i+1)=1\) ，此时有 \(2*j\) 种选择，并且 \(xxxx=j\) ，就可以转移了。
Code
#include <cstdio>
using namespace std;
const int N = 50 + 5, mod = 1000000007;
int f[N][N][N * N];
inline int add (int u, int v) { return u + v >= mod ? u + v - mod : u + v; }
inline int mns (int u, int v) { return u - v < 0 ? u - v + mod : u - v; }
inline int mul (int u, int v) { return 1LL * u * v % mod; }
int main () {
#ifdef chitongz
freopen ("x.in", "r", stdin);
#endif
int n, k;
scanf ("%d%d", &n, &k);
if (k % 2) return puts ("0"), 0;
f[1][1][0] = f[1][0][0] = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
for (int k = 0; k <= i * i / 2; ++k) {
f[i + 1][j][k + j] = add (f[i + 1][j][k + j], mul (2 * j + 1, f[i][j][k]));
f[i + 1][j + 1][k + j] = add (f[i + 1][j + 1][k + j], f[i][j][k]);
if (j) f[i + 1][j - 1][k + j] = add (f[i + 1][j - 1][k + j], mul (j * j, f[i][j][k]));
}
}
}
printf ("%d\n", f[n][0][k / 2]);
return 0;
}
Conclusion
\(F\) 不错，有意思。
总之鸽了这么久才来填坑，我还是太弱了。
转载于:https://www.cnblogs.com/ChiTongZ/p/11391027.html
相关资源：JAVA上百实例源码以及开源项目
