做题笔记[AGC001]
A - BBQ Easy
标签：贪心
难度：★☆☆☆☆
题目大意
将 $2n$ 个数分为 $n$ 组，每个数有值 $L_i$，每组两个数，每个数都被且只被分到一组。一组的权值是两个数值的最小值，分组方案的值就是每组值之和，求分组方案的最大值。
数据范围
$1\le n\le 100,1\le L_i\le 100$。
解题思路
考虑贪心。将数组排序后按顺序两两分组即可。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 205
int n,a[MAXN];
int main(){
cin>>n;
n*=2;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
int ans=0;
for(int i=1;i<=n;i+=2) ans+=a[i];
cout<<ans;
return 0;
}
|
B - Mysterious Light
标签：思维
难度：★★★☆☆
题目大意
有一个边长为 $N$ 的三枚镜子构成的正三角形，顶点为 $A, B, C$。有一束光线，放在 $AB$ 段的 $P$ 点上，使得 $AP=X$。这个步枪将会沿着平行于 $BC$ 的方向发射一道光。
光以直线传播，以镜子的形式反射，也会被自己的轨迹反射，当光回到初始点的时候，光被吸收。
下面的图显示了当 $N=5, x=2$ 时的光轨迹。
给定 $N$ 和 $x$，求出光线的总长度。
数据范围
$2≤N≤10^{12}$，$1≤x≤N-1$。
解题思路
把这个三角形看成被对角线分割的正方形，手动模拟长度，可以发现每一段的长度是一个辗转相减的过程，最后剩下的那一段就是 $(N,x)$。可以得到答案就是 $3(N-(N,x))$。
参考代码
1
2
3
4
5
6
7
8
9
10
| #include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,x;
int main(){
cin>>n>>x;
cout<<3ll*(n-__gcd(x,n));
return 0;
}
|
C - Shorten Diameter
标签：树论、枚举
难度：★★☆☆☆
题目大意
给你一棵 $N$ 个点的无向树，定义点 $u$ 和 $v$ 之间的距离是从 $u$ 到 $v$ 的简单路径上的边数。
你需要删除一些点，使树的直径小于等于 $K$，当且仅当删除某点不会对树的联通性产生影响时才可以删除。
问至少删除多少点才可以满足要求。
数据范围
$2≤N≤2000$，$1≤K≤N-1$。
解题思路
因为 $N$ 比较小，我们考虑枚举每个点，计算以这个点为中心时，最少删去多少个点才能满足要求，具体地：
- 若 $N$ 为偶数，我们设这个点为中心，遍历整张图，删去距离这个点超过 $k/2$ 的点。
- 若 $N$ 为奇数，我们设这个点连接的某一条边为中心（枚举），遍历整张图，删去距离这个点超过 $\lfloor k/2 \rfloor$。
时间复杂度 $O(n^2)$。
参考代码
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
| #include<iostream>
#include<vector>
using namespace std;
#define MAXN 2005
int n,k,cnt,ans=0x3f3f3f3f;
vector<int> g[MAXN];
void dfs(int u,int fa,int dis){
cnt+=(dis>k/2);
for(auto v:g[u]){
if(v==fa) continue;
dfs(v,u,dis+1);
}
}
int main(){
cin>>n>>k;
for(int x,y,i=1;i<n;i++){
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
if(k&1){
for(int u=1;u<=n;u++){
for(auto v:g[u]){
cnt=0;
dfs(v,u,0);
dfs(u,v,0);
ans=min(ans,cnt);
}
}
cout<<ans;
}
else{
for(int u=1;u<=n;u++){
cnt=0;
for(auto v:g[u]){
dfs(v,u,1);
}
ans=min(ans,cnt);
}
cout<<ans;
}
return 0;
}
|
D - Arrays and Palindrome
标签：构造、回文串
难度：★★★★☆
题目大意
给定一个长 $m$ 的序列 $A$，和参数 $n=\sum\limits_{i=1}^m A_i$，构造两个正整数数列 $a,b$，满足：
- $a$ 数列的数字总和是 $N$ 且是 $A$ 序列的一个排列；
- $b$ 数列的数字总和是 $N$；
- 如果存在某个数列 $s$ 满足以下两个条件， 则 $s$ 的所有元素必定相同：
- 对于 $s$ 的最开始的 $a_1$ 个元素，接下来的 $a_2$ 个元素，更后面的 $a_3$ 个，等等，都构成回文串；
- 对于 $s$ 的最开始的 $b_1$ 个元素，接下来的 $b_2$ 个元素，更后面的 $b_3$ 个，等等，都构成回文串。
数据范围
$1\le N,A_i\le 10^5,1\le M\le 100$。
解题思路
一道很好的构造题。
考虑构成一个长度为 $n$ 的回文串，会有 $n/2$ 个相等关系。而让所有元素相等，必须交叉安排两个数组，使得串首尾都留出一个接口，如下图：
不难发现，如果 $A$ 中有大于两个长度为奇数的串，就无法满足制约关系。对于合法的解，不妨将长度为奇数的串转到两边，然后让 $b$ 数组差 $a$ 的空子安排就好。
参考代码
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
| #include<iostream>
using namespace std;
#define MAXN 100005
int n,m,a[MAXN];
int main(){
cin>>n>>m;
int cnt=0;
for(int i=1;i<=m;i++){
cin>>a[i];
cnt+=(a[i]&1);
}
if(cnt>2){
cout<<"Impossible";
return 0;
}
for(int i=1;i<=m;i++) if(a[i]&1){
if(i!=1) swap(a[i],a[1]);
break;
}
for(int i=m;i>1;i--) if(a[i]&1){
if(i!=m) swap(a[i],a[m]);
break;
}
for(int i=1;i<=m;i++) cout<<a[i]<<" ";
cout<<endl;
if(m==1){
if(n!=1) cout<<2<<endl<<a[1]-1<<" "<<1;
else cout<<1<<endl<<1;
return 0;
}
else{
if(a[1]==1) cout<<m-1<<endl;
else{
cout<<m<<endl;
cout<<a[1]-1<<" ";
}
for(int i=2;i<m;i++) cout<<a[i]<<" ";
cout<<a[m]+1;
}
return 0;
}
|
E - BBQ Hard
标签：组合计数、动态规划
难度：★★★★☆
题目大意
有 $n$ 个数对 $(a_i, b_i)$，求
答案对 $10 ^ 9 + 7$ 取模。
数据范围
$2\le N\le 2\times 10^5,1\le A_i,B_i\le 2000$。
解题思路
首先考虑一个组合式 $x+y\choose x$ 的几何意义，就是从点 $(0,0)$ 走到 $(x,y)$，每一步只能向右或向上走的方案数。这个式子是可以转移的：
单独求一次可以在 $O(A_iB_i)$ 的时间求出来。现在考虑题目中的式子，也就是说对于每个 $1\le i<j\le n$，求从 $(0,0)$ 按照上述方案走到 $(a_i+a_j,b_i+b_j)$ 的方案数。
为了简化思考，我们现在改变一下表述方式：对于每个 $1\le i<j\le n$，求从 $(-a_j,-b_j)$ 走到 $(a_i,b_i)$，即向左下平移，但是大小不变。我们以 $(a_i,a_j)$ 为主元，求解其他点（负的）到这个点的方案和即可。
我们考虑动态规划。开始给每个负点 $(-a_i,-b_i)$ $1$ 的权值，设计 $f_{i,j}$ 表示从左下角走到这个点的方案数，求解即可。
注意上述状态求解了所有的 $i,j$ 的解，我们需要删去 $i,i$ 的解，通过组合计数可得这部分要删去的解的个数是 $\sum\limits_{i=1}^n{2a_i+2b_2\choose2a_i}$。因为 $i,j$ 和 $j,i$ 算重，需要将答案数除以 $2$。
参考代码
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
| #include<iostream>
using namespace std;
#define MAXN 200005
#define MAXA 2005
#define mod 1000000007
typedef long long ll;
ll f[MAXA<<1][MAXA<<1],n,a[MAXN],b[MAXN];
ll maxa,maxb,ans;
ll mul[MAXA<<2],inv[MAXA<<2];
int C(int n,int m){
return mul[n]*inv[m]%mod*inv[n-m]%mod;
}
ll qpow(ll a,ll b){
ll w=1;
while(b){
if(b&1) w=w*a%mod;
a=a*a%mod;
b>>=1;
}
return w;
}
void init(){
mul[0]=1;
for(int i=1;i<=4009*2;i++) mul[i]=mul[i-1]*i%mod;
inv[4009*2]=qpow(mul[4009*2],mod-2);
for(int i=4009*2-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int main(){
init();
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
f[2005-a[i]][2005-b[i]]++;
maxa=max(maxa,a[i]);
maxb=max(maxb,b[i]);
}
for(int i=2005-maxa;i<=2005+maxa;i++){
for(int j=2005-maxb;j<=2005+maxb;j++){
f[i][j]=(f[i][j]+f[i-1][j]+f[i][j-1])%mod;
}
}
for(int i=1;i<=n;i++) ans=(ans+f[2005+a[i]][2005+b[i]])%mod;
for(int i=1;i<=n;i++) ans=(ans-C((a[i]+b[i])<<1,a[i]<<1))%mod;
ans=1ll*ans*inv[2]%mod;
ans=(ans%mod+mod)%mod;
cout<<ans;
return 0;
}
|
F - Wide Swap
标签：思维、拓扑排序、线段树
难度：★★★★★
题目大意
给出一个元素集合为 $\{1,2,\dots,N\}$ 的排列 $P$，当有 $i,j$ $(1\leq i<j\leq N)$ 满足 $j-i\geq K$ $(1\leq K\leq N-1)$ 且 $|P_{i}-P_{j}|=1$时，可以交换 $P_{i}$ 和 $P_{j}$。
求：可能排列中字典序最小的排列。
数据范围
$1\leq N\leq 5\times10^5$ 。
解题思路
考虑按照上述方式交换元素有什么特殊性质。
我们建立 $P$ 的反置换 $Q$，即 $P_{Q_i}=i$，将 $P_i$ 的值作为 $Q$ 的下标，$i$ 作为 $Q$ 的值。不难发现，可以交换 $Q_i$ 和 $Q_{i+1}$ 的条件是 $|Q_i-Q_{i+1}|\le K$。
通过人类的智慧思考发现，若存在一组 $1\le iK$，不管怎样交换，这两个数的相对位置不会改变。
这个性质放回到 $P$ 中，等价于：$\forall 1\le i \le N,j\in(i-K,i+k),i\not=j$，若 $P_i$ 和 $P_j$ 满足偏序关系 $P_i<P_j$，则无论怎样交换，最后在 $i,j$ 位置上的数仍满足偏序关系 $P_i<P_j$。
例子 $\quad$ 对于排列 $P=\{4,5,7,8,3,1,2,6\}$，有 $P_2=5,P_3=7$，在 $K=3$ 的情况下，无论怎样交换，两个位置上的数仍满足小于关系。例如交换成 $P’=\{1,2,6,7,5,3,4,8\}$，满足 $2<6$。
这样，我们可以找出所有的偏序关系，建图后通过拓扑排序，就可以知道这些数的最小排列。
例如，我们按照大于关系见图，即找到下标 $(i-K,i+K)$ 内比 $P_i$ 小的数连边，按照拓扑顺序给下标从 $N$ 到 $1$ 赋值。
但是这个图是 $O(NK)$ 大小的，无法建图，我们利用这道题的特殊性质：每个点可能连出边的节点范围是 $(i-K,i+K)$。一开始没有入度的点就是这个范围内的最大值，可以利用线段树查找。然后在左右子区间找区间最大值，再检查是否合法即可（见代码）。
时间复杂度 $O(N\log N)$。
参考代码
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
| #include<iostream>
#include<queue>
using namespace std;
#define MAXN 500005
#define mid ((tree[p].l+tree[p].r)>>1)
#define ls (p<<1)
#define rs (p<<1|1)
#define inf 0x3f3f3f3f
typedef pair<int,int> pii;
int n,k,a[MAXN],ans[MAXN];
struct node{
int l,r,maxx,pos;
}tree[MAXN<<2];
priority_queue<int> q;
void update(int p){
if(tree[ls].maxx>tree[rs].maxx){
tree[p].maxx=tree[ls].maxx;
tree[p].pos=tree[ls].pos;
}
else{
tree[p].maxx=tree[rs].maxx;
tree[p].pos=tree[rs].pos;
}
}
void build(int l,int r,int p){
tree[p].l=l,tree[p].r=r;
if(l==r){
tree[p].maxx=a[l];
tree[p].pos=l;
return;
}
build(l,mid,ls);
build(mid+1,r,rs);
update(p);
}
pii query(int l,int r,int p){
if(l>r) return {-inf,0};
if(l<=tree[p].l&&r>=tree[p].r) return {tree[p].maxx,tree[p].pos};
if(l>mid) return query(l,r,rs);
if(r<=mid) return query(l,r,ls);
pii lc=query(l,r,ls),rc=query(l,r,rs),c;
if(lc.first>rc.first) c=lc;
else c=rc;
return c;
}
void modify(int goal,int p){
if(tree[p].l==tree[p].r){
tree[p].maxx=-inf;
return;
}
if(goal<=mid) modify(goal,ls);
else modify(goal,rs);
update(p);
}
void chk(int p){
if(p==0) return;
pii now=query(max(1,p-k+1),min(p+k-1,n),1);
if(now.second==p&&now.first!=-inf) q.push(p);
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,n,1);
for(int i=1;i<=n;i++) chk(i);
int now=n;
while(q.size()){
int u=q.top();
q.pop();
ans[u]=now--;
modify(u,1);
int lpos=query(max(1,u-k+1),u-1,1).second;
int rpos=query(u+1,min(u+k-1,n),1).second;
chk(lpos);chk(rpos);
}
for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
return 0;
}
|
