笔者:wswll
目录
- 补题顺序
- H 题
- J 题
- A 题
- G 题
- E 题
- B 题
- I 题
- F 题
- C 题
- D 题
- K 题
补题顺序
赛时过题：H J A G E B I F C D 赛后补题：**K
H
题意：求背包的中物品价值的最大值 思路： 很容易想到，价值为正的一定加到背包中，价值为负的，将最大的
⌊
n
2
⌋
\\lfloor \\frac{n}{2} \\rfloor
⌊2n⌋个负数取绝对值，再加到背包中。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e6+5;
const int inf=1e18;
const int mod=998244353;
int N[MAXN],cnt=0;
void solve(){
int n;cin>>n;
int ans=0;
for(int i=1;i<=n;i++){
int a;cin>>a;
if(a>0) ans+=a;
else N[++cnt]=–a;
}
int m=n/2;
sort(N+1,N+1+cnt);
for(int i=cnt;i>=1;i—){
if(m==0) break;
m—;
ans+=N[i];
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;//cin>>t;
while(t—) {
solve();
}
return 0;
}
J
题意：求释放魔法的次数和最后的值。
思路：发现第一次的数可能达到
10
64
10^{64}
1064，可以先存为字符串特判一下，之后的数不会超过
640
640
640，正常模拟就行。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e6+5;
const int inf=1e18;
const int mod=998244353;
int f(int x){
int re=0;
while(x>0){
re+=x%10;
x/=10;
}
return re;
}
void solve(){
string s;cin>>s;
if(s.size()==1){
cout<<0<<" "<<s<<"\\n";
return;
}
int ans=1,w=0;
for(int i=0;i<s.size();i++) w+=s[i]–'0';
while(w>=10){
ans++;
w=f(w);
}
cout<<ans<<" "<<w<<"\\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;cin>>t;
while(t—) {
solve();
}
return 0;
}
A
题意：求完成所有任务所需的最小初始能量。
思路：可以将任务分成两类： 第一种，
d
>
=
0
d>=0
d>=0,此时将
h
h
h从小到大排列就行，门槛越低，越优先。 第二种，
d
<
0
d<0
d<0，此时将
(
h
+
d
)
(h+d)
(h+d)从大到小排列, 门槛越高，减的越少，越优先。 代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e6+5;
typedef struct{
int w,v;
} node;
node N[MAXN],M[MAXN];
int cntn=0,cntm=0;
int cmp1(node a,node b){
return a.w < b.w;
}
int cmp2(node a,node b){
return (a.w+a.v)>(b.w+b.v);
}
void solve(){
cntn=0,cntm=0;
int n;cin>>n;
for(int i=1;i<=n;i++){
int a,d;cin>>a>>d;
if(d>=0) {
N[++cntn].v=d;
N[cntn].w=a;
}
else{
M[++cntm].v=d;
M[cntm].w=a;
}
}
sort(N+1,N+1+cntn,cmp1);
int ans=0,w=0;
for(int i=1;i<=cntn;i++){
if(ans+w<N[i].w){
ans += N[i].w – ans – w;
}
w += N[i].v;
}
sort(M+1,M+1+cntm,cmp2);
for(int i=1;i<=cntm;i++){
if(ans+w<M[i].w){
ans += M[i].w – ans – w;
}
w += M[i].v;
}
cout<<ans<<'\\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;//cin>>t;
while(t—) {
solve();
}
return 0;
}
G
题意：按照字典序从小到大输出满足要求的排列。
思路：因为
n
<
=
11
n<=11
n<=11,数据量很小可以考虑暴力搜索，注意第一个数因为前面没有数了，不需要考虑和为质数。 代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e6+5;
const int inf=1e18;
const int mod=998244353;
int n,N[20],book[20];
int f(int x){
if(x==2||x==3||x==5||x==7||x==11||x==13||x==17||x==19||x==23) return 1;
return 0;
}
void dfs(int w){
if(w>n){
for(int i=1;i<=n;i++) cout<<N[i]<<(i!=n?" ":"\\n");
return;
}
for(int i=1;i<=n;i++){
if(book[i]) continue;
if(f(i+N[w–1])){
N[w]=i;book[i]=1;
dfs(w+1);
book[i]=0;N[w]=0;
}
}
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
N[1]=i;book[i]=1;
dfs(2);
N[1]=0;book[i]=0;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;//cin>>t;
while(t—) {
solve();
}
return 0;
}
E
题意：求最终知道消息的人数的最大值
思路：可以使用并查集求解，先求出有多少个连通块，最大的连通块就是答案。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e6+5;
const int inf=1e18;
const int mod=998244353;
int P[MAXN],F[MAXN];
int findmy(int x){
if(P[x]!=x){
P[x]=findmy(P[x]);
}
return P[x];
}
void unionmy(int x,int y){
int rx=findmy(x);
int ry=findmy(y);
if(rx!=ry){
P[rx]=ry;
}
}
void solve(){
int n;cin>>n;
for(int i=1;i<=n;i++){
P[i]=i;
cin>>F[i];
}
for(int i=1;i<=n;i++) unionmy(i,F[i]);
map<int,int>mp;
for(int i=1;i<=n;i++){
int ri=findmy(i);
mp[ri]++;
}
int ans=–1;
for(auto it:mp){
ans=max(ans,it.second);
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;cin>>t;
while(t—) solve();
return 0;
}
B
题意：求最长的平衡字串。
思路：这题需要数学推导，注意到满足平衡的字串需要以下条件：
r
(
0
)
−
l
(
0
)
=
r
(
1
)
−
l
(
1
)
r
(
0
)
−
l
(
0
)
=
r
(
2
)
−
l
(
2
)
\\begin{align*} r(0)-l(0)=r(1)-l(1) \\\\ r(0)-l(0)=r(2)-l(2) \\end{align*}
r(0)−l(0)=r(1)−l(1)r(0)−l(0)=r(2)−l(2) 整理后得到：
r
(
0
)
−
r
(
1
)
=
l
(
0
)
−
l
(
1
)
r
(
0
)
−
r
(
2
)
=
l
(
0
)
−
l
(
2
)
\\begin{align*} r(0)-r(1)=l(0)-l(1) \\\\ r(0)-r(2)=l(0)-l(2) \\end{align*}
r(0)−r(1)=l(0)−l(1)r(0)−r(2)=l(0)−l(2) 此时发现，需要对每个位置
r
r
r,找到和它值相同的最远的
l
l
l,map记录每个位置的二元组。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e6+5;
const int inf=1e18;
const int mod=998244353;
int A[MAXN],B[MAXN],C[MAXN];
map<pair<int,int>,int>mp;
void solve(){
int n;cin>>n;
string s;cin>>s;
int ans=0;
for(int i=1;i<=n;i++){
if(s[i–1]=='0') A[i]+=1;
if(s[i–1]=='1') B[i]+=1;
if(s[i–1]=='2') C[i]+=1;
A[i]+=A[i–1];
B[i]+=B[i–1];
C[i]+=C[i–1];
int a=A[i]–B[i];
int b=B[i]–C[i];
if(a==0&&b==0) ans=max(ans,i);
else if(mp.count({a,b})){
//cout<<i<<" "<<mp[{a,b}]<<endl;
ans=max(i–mp[{a,b}],ans);
}
else mp[{a,b}]=i;
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;//cin>>t;
while(t—) solve();
return 0;
}
I
题意：求X的最小值 思路： 发现
n
n
n个位置，有
n
−
1
n-1
n−1个间隔，求间隔的绝对值并重新排列间隔，取第K大的为X.
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e6+5;
const int inf=1e18;
const int mod=998244353;
int N[MAXN],F[MAXN];
void solve(){
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++) cin>>N[i];
for(int i=1;i<n;i++) F[i]=abs(N[i+1]–N[i]);
sort(F+1,F+1+n–1);
int w=F[n–k];
cout<<w<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;//cin>>t;
while(t—) solve();
return 0;
}
F
题意：求小夏从城市 11 到城市 nn 的最短距离,中间可以使用K次魔法，将一条路径的长度降为
0
0
0.
思路：这题的正解明显是Dijkstra，但笔者赛时看数据量很小，偷懒写了一种bfs的思路。
D
[
x
]
[
y
]
,
表示到达
x
城还剩
y
次，的最短距离。
D[x][y],表示到达x城还剩y次，的最短距离。
D[x][y],表示到达x城还剩y次，的最短距离。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e6+5;
const int inf=1e18;
const int mod=998244353;
int D[MAXN][11];
vector<vector<pair<int,int>>>M(1001);
void solve(){
int n,m,k;cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++) D[i][j]=inf;
}
for(int i=1;i<=m;i++){
int u,v,w;cin>>u>>v>>w;
M[u].push_back({v,w});
M[v].push_back({u,w});
}
queue<pair<int,pair<int,int>>>q;
q.push({1,{0,k}});
D[1][k]=0;
while(!q.empty()){
auto it=q.front();q.pop();
int u=it.first;
auto it1=it.second;
int d=it1.first;
int kk=it1.second;
if(D[u][k]<d) continue;
for(auto it2:M[u]){
int v=it2.first;
int d1=it2.second;
if(d+d1<D[v][kk]){
D[v][kk]=d+d1;
q.push({v,{d+d1,kk}});
}
if(kk>0&&d<D[v][kk–1]){
D[v][kk–1]=d;
q.push({v,{d,kk–1}});
}
}
}
int ans=inf;
for(int i=0;i<=k;i++){
ans=min(ans,D[n][i]);
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;//cin>>t;
while(t—) {
solve();
}
return 0;
}
C
题意：求非空的最短的和整个序列和同余的子串。
思路： 求当前前缀序列的除以
m
m
m的余数
f
f
f，此时可以维护一个数组
P
[
d
]
P[d]
P[d]，记录距离最近的上个前缀与
m
m
m余数为
d
d
d的位置，
d
=
(
d
−
s
u
m
+
m
)
%
m
d=(d-sum+m)\\%m
d=(d−sum+m)%m,
s
u
m
sum
sum是整个序列和
m
m
m的余数，枚举每个位置求最短非空子串。 代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e6+5;
const int inf=1e18;
const int mod=998244353;
int N[MAXN],P[MAXN];
void solve(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++) cin>>N[i];
for(int i=1;i<m;i++) P[i] = –1;
int sum = 0,f = 0,ans = inf;
for(int i=1;i<=n;i++){
sum = (sum + N[i]) % m;
}
for(int i=1;i<=n;i++){
f = (f + N[i]) % m;//当前前缀与m的余数，
int d = (f – sum+m) % m;//想要剩余数之和与m的余数是0，子串的左端点的前缀与m的余数值
if(P[d] != –1){
if(!(P[d] == 0 && i == n)){
ans = min(ans, i – P[d]);
}
}
P[f] = i;//记得更新位置。
}
if(ans == inf){
cout<<–1<<"\\n";
return;
}
cout<<n–ans<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;//cin>>t;
while(t—) solve();
return 0;
}
D
题意：求刻俄柏的位置，
思路：这题初看没有思路，但是模拟一下很容易发现规律，每次"抢夺"蜜饼，都会导致:
P
[
u
]
−
>
2
∗
P
[
v
]
−
P
[
u
]
变化量是：
2
∗
P
[
v
]
−
2
∗
P
[
u
]
\\begin{align*} P[u]->2*P[v]-P[u] \\\\ 变化量是：2*P[v]-2*P[u]\\\\ \\end{align*}
P[u]−>2∗P[v]−P[u]变化量是：2∗P[v]−2∗P[u] 当连续多次“抢夺“会导致中间的所有变化量相互抵消。只剩下
2
∗
P
[
小刻
]
−
2
∗
p
[
火神
]
2*P[小刻]-2*p[火神]
2∗P[小刻]−2∗p[火神] 代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e6+5;
const int inf=1e18;
const int mod=998244353;
int N[MAXN],P[MAXN];
void solve(){
int n; cin>>n;
int sx=0,sy=0,sz=0,sX=0,sY=0,sZ=0;
int x1 =0,y1 =0,z1 =0;
map<tuple<int, int, int>, int> mp;
for (int i = 1; i <= n; i++) {
int x,y,z,X,Y,Z;cin>>x>>y>>z>>X>>Y>>Z;
if (i == 1) {
x1=x; y1=y; z1=z;
}
sx+=x; sy+=y; sz+=z;
sX+=X; sY+=Y; sZ+=Z;
mp[{X, Y, Z}] = i;
}
int rx = (sX – (sx–2*x1))/2;
int ry = (sY – (sy–2*y1))/2;
int rz = (sZ – (sz–2*z1))/2;
cout << mp[{rx, ry, rz}] << "\\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;cin>>t;
while(t—) solve();
return 0;
}
K
题意：现在给出 𝑚次操作，请按顺序执行。操作分为两种：
- 操作 1：输入 1 x z，表示第 𝑥 个小镇商店的资金直接修改为 𝑧
- 操作 2：输入 2 x y z，表示小红初始拥有 𝑧 元资金，从小镇 𝑥 出发，沿唯一路径到达小镇 𝑦（起点和终点也会进行交易），输出小红到达 𝑦 后拥有的最终资金。
思路：首先我们先做一个数链剖分，然后将dfn存为线段树，维护区间AND(&),此时可以通过线段树的性质完成操作1的单点修改。 想要实现
x
x
x到
y
y
y的路径修改，需要先求
L
C
A
(
x
,
y
)
LCA(x,y)
LCA(x,y),对于上升和下降需要分为两个阶段。上升时很简单，只需要从大小找到第一个出现
0
0
0的位置就行。下降时，从大到小找最后一个出现的
0
0
0。 代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e5+5;
const int inf=1e18;
const int mod=998244353;
int fa[MAXN],dep[MAXN],siz[MAXN],son[MAXN];//dfs1数组。
int top[MAXN],dfn[MAXN],sg[MAXN],cnt_dfn=0;//dfs2数组.
typedef struct{
int next,to;
}node;node adge[MAXN*2+5];
int head[MAXN*2+5],cnt=0;//链式前向星。
int V[MAXN];
void in_my(int u,int v){
adge[++cnt].to=v;
adge[cnt].next=head[u];
head[u]=cnt;
}
void dfs1(int u,int f){//设置，fa,dep(深度),siz(子树大小),son(重儿子)
fa[u]=f;
dep[u]=dep[f]+1;
siz[u]=1;
son[u]=0;
for(int i=head[u];i>0;i=adge[i].next){
if(adge[i].to!=f) dfs1(adge[i].to,u);
}
for(int i=head[u];i>0;i=adge[i].next){
if(adge[i].to!=f){
siz[u]+=siz[adge[i].to];
if(son[u]==0||siz[son[u]]<siz[adge[i].to]) son[u]=adge[i].to;
}
}
}
void dfs2(int u,int t){//top(重链的头节点),dfn(遍历重链的序列号,深搜保证一个节点和它的子节点是连续的),sg(和dfn相对，方便查询)
top[u]=t;
dfn[u]=++cnt_dfn;
sg[cnt_dfn]=u;
if(son[u]==0) return;//叶子，返回
dfs2(son[u],t);//重儿子
for(int i=head[u];i>0;i=adge[i].next){
int v=adge[i].to;
if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
}
int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
struct segtree{
int TR[MAXN*4];
void push_up(int w){
TR[w]=TR[w*2]&TR[w*2+1];
}
void build(int w,int l,int r){
if(l==r){
TR[w]=V[sg[l]];
return;}
int mid=(l+r)/2;
build(w*2,l,mid);build(w*2+1,mid+1,r);
push_up(w);
}
void update(int w,int l,int r,int cnt_w,int v){//单点修改。
if(l==r){
TR[w]=v;
return;
}
int mid=(l+r)/2;
if(cnt_w<=mid) update(w*2,l,mid,cnt_w,v);
else update(w*2+1,mid+1,r,cnt_w,v);
push_up(w);
}
int query(int w,int l,int r,int cnt_w){//单点查询
if(l==r) return TR[w];
int mid=(l+r)/2;
if(cnt_w<=mid) return query(w*2,l,mid,cnt_w);
else return query(w*2+1,mid+1,r,cnt_w);
}
int find_down(int w,int l,int r,int L,int R,int k){//区间[L,R]找第一个第k位为0的dfn下标，找不到返回-1
if(r<L||l>R) return –1;
if( (TR[w] & (1LL << k)) ) return –1;
if(l==r) return l;
int mid=(l+r)/2;
int re=–1;
if(L<=mid){//先左
re = find_down(w*2,l,mid,L,R,k);
if(re != –1) return re;
}
if(R>mid){
re = find_down(w*2+1,mid+1,r,L,R,k);
if(re != –1) return re;
}
return –1;
}
int find_up(int w,int l,int r,int L,int R,int k){//区间[R,L]找第一个第k位为0的dfn下标，找不到返回-1
if(r<L||l>R) return –1;
if( (TR[w] & (1LL << k)) ) return –1;
if(l==r) return l;
int mid=(l+r)/2;
int re=–1;
if(R>mid){//先右
re = find_up(w*2+1,mid+1,r,L,R,k);
if(re != –1) return re;
}
if(L<=mid){
re = find_up(w*2,l,mid,L,R,k);
if(re != –1) return re;
}
return –1;
}
}seg;
int query_up(int u,int f,int k){// u向上爬到最近祖先,找第一个bit k=0的dfn下标
while(top[u] != top[f]){
int p = seg.find_up(1,1,cnt_dfn, dfn[top[u]], dfn[u], k);
if(p!=–1){//找到最先遇到的点，直接返回，不再往上
return p;
}
u=fa[top[u]];
}
int p=seg.find_up(1,1,cnt_dfn,dfn[f],dfn[u],k);//同一条链，特判一下
if(p!=–1) return p;
return –1;
}
int query_down(int u,int f,int k){
int re=–1;
while(top[u] != top[f]){
int p = seg.find_down(1,1,cnt_dfn, dfn[top[u]], dfn[u], k);
if(p!=–1){
re=p;
}
u=fa[top[u]];
}
int p=seg.find_down(1,1,cnt_dfn,dfn[f],dfn[u],k);
if(p!=–1) re=p;
return re;
}
void solve(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++) cin>>V[i];
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
in_my(u,v);
in_my(v,u);
}
dfs1(1,0);
dfs2(1,1);
seg.build(1,1,n);
for(int i=1;i<=m;i++){
int f;cin>>f;
if(f==1){
int x,z;cin>>x>>z;
seg.update(1,1,n,dfn[x],z);
}
else{
int x,y,z;cin>>x>>y>>z;
int f=lca(x,y);
int ans = 0;
for(int k=0;k<11;k++){
if(!(z&(1LL<<k))) continue;
int w=query_up(x,f,k);
if(w==–1){
w=query_down(y,f,k);
}
if(w!=–1){
int v=seg.query(1,1,cnt_dfn,w);
seg.update(1,1,cnt_dfn,w,v|(1LL<<k));
}else{
ans|=(1LL<<k);
}
}
cout << ans << '\\n';
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;//cin>>t;
while(t—){
solve();
}
return 0;
}
