Java教程
2022高考集训2
《关于20个人爆零这件事》
tql%%%
T1 交通
题目描述
qjd 所在的城市可以看作有 n个点、 2n 条有向边的有向图，并且满足每个点恰好有两条入边和两条出边。
qjd 觉得这么多岔路造成了交通的堵塞，于是他想动用魔法删掉 n 条边，使得每个点只有一条出边和一条入边（注意边是有编号的，也就是重边视为不同的边）。
qjd 非常擅长数数，他想问你，有多少种删边方式满足要求呢？输出答案模 998244353 的余数。
输入格式
第一行一个正整数 n 。
接下来 2n 行每行两个数 u,v ，表示有一条从 u 到 v 的有向边。保证没有自环（但是可能有重边）。
输出格式
共一行一个整数，表示答案。
样例输入
2 1 2 1 2 2 1 2 1
样例输出
4
样例解释
显然删掉 (1,2) 中的任意一个和 (2,1) 中的任意一个都能满足要求。
数据范围与提示
对于所有数据， 1 ≤ n ≤ 10^5
subtask1(30pts) : n ≤ 10
subtask2(30pts) : n ≤ 1000
subtask3(40pts) : 无特殊限制。
分析
假设一个点的两条出边为i，j ，新建一个图给i,j 连边。如果一个点的两条入边为 i,j，我们也给i,j
连边。
不难发现新图上每个点度数恰好为二，并且只有偶环。（反证法可以证明只有偶环）
1，2，3为边的编号建的图
所以相邻两点为同一个点的入边或出边
设1，2为点①的入边，那么1，2只能是其他点的出边
设2，3为点②的出边，那么3只能是其他点的入边
所以设2是点③的出边，3是点③的入边，与建图原理相矛盾
所以新图上每个点度数恰好为二，并且只有偶环
因此，事实上就是在新图上选 n个不相邻的点，于是答案显然是（2^环数 ），直接并查集即可。
AC 代码
#include <iostream>
using namespace std;
#define ll long long
inline int in(){
int x = 0;
bool f = 1;
char c = getchar();
while(c > '9' || c < '0'){
if(c == '-') f = 0;
c = getchar();
}
while(c <= '9' && c >= '0'){
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
if(f) return x;
else return -x;
}
const int N = 1e5+10;
const int mod = 998244353;
int n,m;
int k;
int fa[N << 1];
int f[N][3],t[N][2];
int head[N],to[N << 1],nxt[N],tot;
ll ans = 1;
inline void add(int u,int v){
to[++tot] = v;
nxt[tot] = head[u];
head[u] = tot;
}
inline int find(int x){
if(fa[x] == x) return x;
else return fa[x] = find(fa[x]);
}
inline void ksm(int k){//2^k
ll a = 2;
while(k){
if(k&1) ans = ans*a%mod;
k >>= 1;
a = (a*a)%mod;
}
printf("%lld",ans);
}
int main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
n = in();
m = n << 1;
int u,v;
for(int i = 1;i <= m;++i){
fa[i] = i;
u = in();
v = in();
if(!t[u][1]) t[u][1] = i;
else t[u][2] = i;
if(!f[v][1]) f[v][1] = i;
else f[v][2] = i;
}
int x,y;
for(int i = 1;i <= n;++i){
x = find(t[i][1]);
y = find(t[i][2]);
if(x == y) k++;
else fa[y] = x;
x = find(f[i][1]);
y = find(f[i][2]);
if(x == y) k++;
else fa[y] = x;
}
ksm(k);
return 0;
}
T2 冒泡排序
题目描述
qjd 什么都擅长，这天他拿来了一个 0~n-1 的排列 A 准备给他冒泡排序。
但是 qjd 的手法注定是不同寻常的，他会生成一个0~n-2的排列 pi ，然后依次交换 A[pi],A[pi+1] （即按照 i 从 0 到 n-2 的顺序）。
他希望知道，有多少合法的排列 pi ，使得能把 A 排好
由于方案数可能很大，你只需要输出它 mod 10^9 + 7结果即可。
输入格式
第一行一个正整数 n 。
接下来一行一个排列 A 。
输出格式
一行一个非负整数，表示答案。
样例输入 1
3 1 2 0
样例输出 1
1
样例解释 1
显然只有唯一的排列 ，即 1,0 。
样例输入 2
4 3 2 0 1
样例输出 2
0
数据范围与提示
对于所有数据，1 ≤ n ≤ 5000 。
subtask1(20pts) : n ≤ 10
subtask2(20pts) : n ≤ 50
subtask3(30pts) : n ≤ 300
subtask4(30pts) : 无特殊限制。
分析
不得不说，这题面一点都不清楚，我理解样例就理解了十分钟
kiritokazuto大佬拿了rank2，考完试竟然还没理解（
题面的意思是：有一个0~n-1的排列A，还有一个0~n-2的排列p
在排列p中从第一个数开始每次取一个数x，然后去排列A中交换x和x+1这两个位置
求有多少个排列p
首先若存在ai = i ，显然无解。
若 ai > i，则我们需要把这个数字从 i 位置向右挪到 ai 位置上。于是就会发现相邻位置的交换顺序有一些限制，限制形如某对相邻的交换必须在它旁边的相邻对交换之前/之后。
若 ai < i，就是把 i 位置向左挪到 ai 的位置上，限制也类似。
于是问题就变成了有若干个形如 bi > bi-1 或 bi < bi-1 的限制，问满足要求的排列 b 有多少个。
直接O(n^2) dp 即可，当然可以容斥+分治 FFT 优化成 O(n(logn)^2)，但由于这是 NOIP 模拟赛就不说
了。
Kaguya大佬的神奇思路：
引入优先级的概念，如果要在 a 之前先把 b 调整那么 b 的优先级大于 a
比如 1423 必须要把 4 在 2 之前调换不然 4 是过不去的
然后可以推 DP 式子
设第一维表示目前到了哪个节点，第二维表示拓扑序，数组存储方案数
对于一个点 i+1 ，如果 i 是依赖于它的，那么
dp[i+1][d]=∑j=d+1ndp[i][j]
这是因为如果 i 依赖于 i+1 那么 i 必然在 i+1 之后才能被遍历到
同理，如果对于一个点 i+1 ，如果它依赖于 i ，那么有
dp[i+1][d]=∑j=1ddp[i][j]
当然如果这两个点没有依赖关系那么
dp[i+1][d]=∑j=1ndp[i][j]
统计答案即可
AC 代码
#include <iostream>
using namespace std;
#define ll long long
inline int in(){
int x = 0;
bool f = 1;
char c = getchar();
while(c > '9' || c < '0'){
if(c == '-') f = 0;
c = getchar();
}
while(c <= '9' && c >= '0'){
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
if(f) return x;
else return -x;
}
const int N = 5100;
const int mod = 1e9+7;
int n;
int a[N];
int t1[N],t2[N];
int st1[N],st2[N];
int f[N][N];
ll ans;
inline void update(int pos,int val,int y){
while(pos <= n){
if(y == 1) t1[pos] += val;
else t2[pos] += val;
pos += pos&(-pos);
}
}
inline int down(int x,int y){
if(y == 1) return t1[x] + st1[x-(x&(-x))];
else return t2[x] + st2[x-(x&(-x))];
}
int main(){
freopen("mp.in","r",stdin);
freopen("mp.out","w",stdout);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
n = in();
for(int i = 1;i <= n;++i){
a[i] = in() + 1;//原数组从零开始,将原数组++
if(a[i] == i){
printf("0");
return 0;
}else if(a[i] > i){
update(i,1,1);
update(a[i]-1,-1,1);
}else{
update(a[i],1,2);
update(i-1,-1,2);
}
}
for(int i = 1;i < n;++i){
st1[i] = down(i,1);
st2[i] = down(i,2);
if(st1[i] && st2[i]){
printf("0");
return 0;
}
}
st1[0] = st2[0] = st1[n] = st2[n] = 0;
f[1][1] = 1;
for(int i = 1;i < n;++i){
if(st1[i]){//i的优先级大于i+1的优先级
for(int k = 2;k <= i+1;++k)
f[i+1][k] = (f[i+1][k-1] + f[i][k-1])%mod;
}else if(st2[i]){
for(int k = i;k > 0;--k)
f[i+1][k] = (f[i+1][k+1] + f[i][k])%mod;
}else{
for(int k = 1;k <= i;++k)
f[i+1][1] = (f[i+1][1] + f[i][k])%mod;
for(int k = 2;k <= i+1;++k)
f[i+1][k] = f[i+1][k-1];
}
}
for(int i = 1;i < n;++i)
ans = (ans + f[n-1][i])%mod;
printf("%lld",ans);
return 0;
}
T3 矩阵
题目描述
qjd 有一个 n×m 的矩阵，矩阵里每个元素都是个整数（可能是负数）。qjd 觉得这个矩阵非常杂乱，因此他让你来清理这个矩阵。
具体的，你可以执行以下三种操作若干次，使得整个矩阵里所有元素都变成 0 。
- 把某一行里的元素全部加上整数 k （可以为负）。
- 把某一列里的元素全部加上整数 k（可以为负）。
- 把某一主对角线里的元素全部加上整数 k （可以为负）。
这里主对角线指行编号和列编号之差为定值的一些格子。
例如 3×4 的矩阵里，(1,1),(2,2),(3,3)是一条主对角线，(1,2),(2,3),(3,4)也是一条，(2,1),(3,2)也是一条（特别的，(3,3)也是一条主对角线）。
你可以执行这些操作总共不超过 6000 次或者报告无解。
输入格式
第一行两个正整数 n,m 。
接下来 n 行每行 m 个整数表示矩阵。
输出格式
第一行一个整数 K 表示操作次数。输出 K = -1 的话表示你认为输入的矩阵无解。
若 K > 0，接下来 K 行每行格式如下：
若执行了操作 1 ，输出一行 1 x k ，其中 x(1 ≤ x ≤ n) 表示行的编号。
若执行了操作 2 ，输出一行 2 x k ，其中 x(1 ≤ x ≤ m) 表示列的编号。
若执行了操作 3 ，输出一行 3 x k ，其中 x(1-n ≤ x ≤ m-1) 表示列编号减行编号（根据主对角线的定义，这是个常数，可以为负）。
上面的 k 都表示操作的参数（即格子加上的数字）。你需要保证 |k| ≤ 10^18。
样例输入1
2 2 1 2 3 4
样例输出1
4 1 2 -3 3 0 -1 1 1 0 3 1 -2
样例输入2
3 3 1 2 3 3 2 1 1 2 3
样例输出2
-1
数据范围与提示
对于所有数据，保证 2 ≤ n,m ≤ 1000，矩阵中的数的绝对值不超过 10^9。
subtask1(20pts) : n = 2
subtask2(20pts) : 保证若有解则不用 3 操作就可以把矩阵全变成 0 。
subtask3(30pts) : n,m ≤ 100
subtask4(30pts) : 无特殊限制。
分析
貌似做法千奇百怪经过机房各位大佬的神奇操作，用大样例的答案操作原图，发现了规律
事实上只需要把前两行和前两列变成 0 即可，如果此时还不能把整个矩阵归零那么必然无解。证明就考
虑任意一个3×3 的矩阵，a1,1 − a1,2 − a2,1 + a2,3 + a3,2 − a3,3 的值在这些操作下永远不变。
于是这样的构造是很容易的，4000 次操作就足够了。
（虽然我不懂怎么证明的，但是，我们可以利用这个结论，考试的时候就听天由命，瞎找规律吧QwQ）
最简单的方法就是利用上述性质直接暴力全消掉
消完两行两列，去扫一遍整个矩阵，如果有不为0的点，输出-1，否则输出答案
一定要读清题面（本人因为没看到操作3是列减行，所以调了一下午TAT。。。。。。）
暴力全消的AC 代码
#include <iostream>
#include <cstring>
using namespace std;
#define ll long long
inline int in(){
int x = 0;
bool f = 1;
char c = getchar();
while(c > '9' || c < '0'){
if(c == '-') f = 0;
c = getchar();
}
while(c <= '9' && c >= '0'){
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
if(f) return x;
else return -x;
}
const int N = 1010;
int n,m;
ll a[N][N];
ll jl[100000][5],tot;
int main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
n = in();
m = in();
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j)
a[i][j] = in();
ll res = a[1][1];
if(res){
jl[++tot][1] = 3;
jl[tot][2] = 0;
jl[tot][3] = -res;
}
int p = 1,q = 1;
while(1){
if(p > n || q > m) break;
a[p][q] -= res;
p++;
q++;
}
for(int i = 2;i <= m;++i){
res = a[2][i];
if(res){
jl[++tot][1] = 2;
jl[tot][2] = i;
jl[tot][3] = -res;
}
for(int j = 1;j <= n;++j) a[j][i] -= res;
res = a[1][i];
if(res){
jl[++tot][1] = 3;
jl[tot][2] = i-1;
jl[tot][3] = -res;
}
p = 1,q = i;
while(1){
if(p > n || q > m) break;
a[p][q] -= res;
p++;
q++;
}
}
res = a[2][1];
if(res){
jl[++tot][1] = 3;
jl[tot][2] = -1;
jl[tot][3] = -res;
}
p = 2,q = 1;
while(1){
if(p > n || q > m) break;
a[p][q] -= res;
p++;
q++;
}
for(int i = 3;i <= n;++i){
res = a[i][2];
if(res){
jl[++tot][1] = 1;
jl[tot][2] = i;
jl[tot][3] = -res;
}
for(int j = 1;j <= m;++j) a[i][j] -= res;
res = a[i][1];
if(res){
jl[++tot][1] = 3;
jl[tot][2] = 1-i;
jl[tot][3] = -res;
}
p = i,q = 1;
while(1){
if(p > n || q > m) break;
a[p][q] -= res;
p++;
q++;
}
}
for(int i = 1;i <= n;++i){
for(int j = 1;j <= m;++j){
if(a[i][j]){
printf("-1");
return 0;
}
}
}
printf("%d\n",tot);
for(int i = 1;i <= tot;++i)
printf("%lld %lld %lld\n",jl[i][1],jl[i][2],jl[i][3]);
return 0;
}
然后，我想办法优化了一下，用数组存行，列，对角线分别减了多少
优化后的AC 代码
#include <iostream>
#include <cstring>
using namespace std;
#define ll long long
inline ll in(){
ll x = 0;
bool f = 1;
char c = getchar();
while(c > '9' || c < '0'){
if(c == '-') f = 0;
c = getchar();
}
while(c <= '9' && c >= '0'){
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
if(f) return x;
else return -x;
}
const int N = 1010;
ll n,m;
ll a[N][N];
ll h[N],l[N];//行列变化量
ll dh[N],dl[N];//h表示对角线dh[1][i],l表示对角线dl[i][1]
ll jl[N*6][5],tot;
int main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
n = in();
m = in();
for(int i = 1;i <= n;++i)
for(int j = 1;j <= m;++j)
a[i][j] = in();
dl[1] = a[1][1];
if(dl[1]){
jl[++tot][1] = 3;
jl[tot][2] = 0;
jl[tot][3] = -dl[1];
}
for(int i = 2;i <= m;++i){
l[i] = a[2][i] - dl[i-1];
if(l[i]){
jl[++tot][1] = 2;
jl[tot][2] = i;
jl[tot][3] = -l[i];
}
dl[i] = a[1][i] - l[i];
if(dl[i]){
jl[++tot][1] = 3;
jl[tot][2] = i-1;
jl[tot][3] = -dl[i];
}
}
dh[2] = a[2][1];
if(dh[2]){
jl[++tot][1] = 3;
jl[tot][2] = -1;
jl[tot][3] = -dh[2];
}
for(int i = 3;i <= n;++i){
h[i] = a[i][2] - dh[i-1] - l[2];
if(h[i]){
jl[++tot][1] = 1;
jl[tot][2] = i;
jl[tot][3] = -h[i];
}
dh[i] = a[i][1] - h[i];
if(dh[i]){
jl[++tot][1] = 3;
jl[tot][2] = 1-i;
jl[tot][3] = -dh[i];
}
}
for(int i = 1;i <= n;++i){
for(int j = 1;j <= m;++j){
int t = min(i,j) - 1;
int ii = i-t;
int jj = j-t;
ll q;
if(ii == 1) q = dl[jj];
else q = dh[ii];
// printf("%lld ",a[i][j] - h[i] - l[j] - q);
if(a[i][j] - h[i] - l[j] - q != 0){
printf("-1");
return 0;
}
}
// printf("\n");
}
printf("%d\n",tot);
for(int i = 1;i <= tot;++i)
printf("%lld %lld %lld\n",jl[i][1],jl[i][2],jl[i][3]);
return 0;
}
虽然看起来没多少变化。。。。。。
T4 花瓶
题目描述
qjd 家里有 n 个花瓶，它们排成了一排。
有的花瓶很好看，而有的花瓶不好看，于是 qjd 给每个花瓶都定义了它的美丽度 ai 。但是 qjd 不舍得把不好看的花瓶扔了，也不想变化它们的位置，于是他就打算把这些花瓶分成若干组，每组都是一个连续段。
假设 qjd 把这些花瓶分成了 k 个连续段，记 Si 表示第 i 个连续段中所有花瓶的美丽度之和，他希望最大化：S1×S2 + S2×S3 + Sk-1×Sk。
特别的，k = 1 时上述结果为 0 。
输入格式
第一行一个正整数 n 。
接下来一行共 n 个整数 ai ，注意这里 ai 可能是负数。
输出格式
共一行一个整数表示答案。
样例输入
6 2 -1 4 3 -1 0
样例输出
13
样例解释
分成 (2,-1),(4),(3),(-1,0)，答案为 1×4 + 4×3 + 3×(-1) = 13 。可以证明这是最优解。
数据范围与提示
对于所有数据，1 ≤ n ≤ 5000，|ai| ≤ 10^3 。
subtask1(10pts) : n ≤ 20
subtask2(20pts) : n ≤ 300
subtask3(20pts) : n ≤ 1500
subtask4(20pts) : ai ＞ 0
subtask5(30pts) : 无特殊限制。
分析
斜率优化
考虑 fi,j 表示当前 dp 到了 i ，上一个区间右端点为 j 时的最优答案。
则有：
显然是个斜率优化的形式(虽然我没看出来)，扔掉只和 i,j 有关的常数项，
则可以写成：
(证明在代码里，LATEX不会用)
若对于 sa < sb 有 ，那么显然：
于是我们枚举 j ，按照 s 排序后暴力维护出一个斜率递减的上凸壳。注意到 t = si - sj，我们再按照si从大到小枚举 i ，就可以贪心地从凸包前面删点了。
于是总复杂度O(n^2) 。
AC 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
inline ll in(){
ll x = 0;
bool f = 1;
char c = getchar();
while(c > '9' || c < '0'){
if(c == '-') f = 0;
c = getchar();
}
while(c <= '9' && c >= '0'){
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
if(f) return x;
else return -x;
}
//dp[i][j]表示dp到了i,上一个区间右端点为j时的最优解
//dp[i][j] = max(dp[j][k])(0<=k<j) + (sum[i]-sum[j])*(sum[j]-sum[k])
//dp[i][j] = max(dp[j][k]) + (si*sj - sj*sj) - (si-sj)*sk
//dp[i][j] = max(dp[j][k]) + p - t*sk;
//dp[j][k] = t*sk - p + dp[i][j]
//因为枚举时,对于同一个i,j ,p,t的值不变
//所以要想让截距dp[i][j]最大,就要让斜率最大
//当sa < sb时,f[j][a] - t*sa < f[j][b] - t*sb
//t < (fja-fjb)/(sa-sb)
//sa < sb,注意变号
const int N = 5100;
ll n;
ll a[N];
ll l,r;
ll q[N];
ll sum[N];
ll f[N][N];
ll ans = 0;
inline bool cmp(ll x,ll y){
return sum[x] < sum[y];
}
int main(){
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
n = in();
for(int i = 1;i <= n;++i){
ll x = in();
sum[i] = sum[i-1] + x;
a[i] = i;
}
sort(a,a+n+1,cmp);
memset(f,-0x3f,sizeof(f));
for(int i = 0;i <= n;++i) f[i][0] = 0;
for(int i = 1;i <= n;++i){
l = 1;
r = 0;
for(int j = 0;j <= n;++j){
if(a[j] < i){
while(l < r && (f[i][q[r]]-f[i][q[r-1]])*(sum[a[j]]-sum[q[r-1]]) <= (f[i][a[j]]-f[i][q[r-1]])*(sum[q[r]]-sum[q[r-1]])) r--;
q[++r] = a[j];
}
}
for(int j = n;j >= 0;--j){
if(a[j] > i){
while(l < r && (sum[a[j]]-sum[i])*(sum[q[l+1]]-sum[q[l]]) <= (f[i][q[l+1]]-f[i][q[l]])) l++;
f[a[j]][i] = max(f[a[j]][i],f[i][q[l]]+(sum[a[j]]-sum[i])*(sum[i]-sum[q[l]]));
}
}
}
for(int i = 0;i < n;++i) ans = max(ans,f[n][i]);
printf("%lld",ans);
return 0;
}
-
Java中定时任务实现方式及源码剖析11-24
-
Java中定时任务实现方式及源码剖析11-24
-
鸿蒙原生开发手记：03-元服务开发全流程（开发元服务，只需要看这一篇文章）11-24
-
细说敏捷：敏捷四会之每日站会11-24
-
Springboot应用的多环境打包入门11-23
-
Springboot应用的生产发布入门教程11-23
-
Python编程入门指南11-23
-
Java创业入门：从零开始的编程之旅11-23
-
Java创业入门：新手必读的Java编程与创业指南11-23
-
Java对接阿里云智能语音服务入门详解11-23
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
