24年CCPC郑州邀请赛VP
24年CCPC郑州邀请赛暨第六届CCPC河南省赛
A. Once In My Life
题意：一个数的数位包含 1~9 并且至少两个数位是 d 的十进制正整数都是幸运数。给出 d 和一个正整数 n，输出一个 k 使得 n*k 是幸运数。
题解：我们需要先构造出乘积。1234567890 满足包含1~9的条件，再加上 d 满足幸运数。但是这个数不一定是 n 的倍数，无法通过乘积获得。为了不影响这个数幸运数的性质，我们可以在这个数后面添加几位使得这个数变成 n 的倍数。
我们先在 123456789d 后面添加 n 位数个 0，因为我们必定可以通过更改后面的 0 使得这个数变为 n 的倍数，即取模同余的性质。这个数不能减去与n的余数，因为这可能改变幸运数的性质，所以加上 \(n-c%n\) 也是同理。（也可后面加9，然后减去余数，也不会影响前面数位而变成倍数）。
这个数除以 n 即可得到 k。
void solve(){
ll n,d;cin>>n>>d;
ll len=to_string(n).size();//求n的位数
ll c=1234567890ll+d;//构造幸运数
c=c*pow(10,len);//后面添0
c+=(n-c%n);//使这个数变成n的倍数
ll ans=c/n;
cout<<ans<<"\n";
}
B. 扫雷 1
签到，排序+贪心。
C. 中二病也要打比赛
题意：给定一个序列A，元素范围在 1~n 内。使用某个映射将序列A变为一个单调不降的序列。这个映射的代价为 \(f(x)≠x\) 的数量。求最小代价。
题解：
如果序列中数字没有相同的话，就是一个LIS。
若 \(l<r\) 且 \(a_l=a_r\) 则 \(\forall l<i<r\) 有 \(a_i=a_r\)。即如果某两个数值相等，则这两数之间所有的数也全部相等，考虑这一段数字变成一个联通块，必须使这一个连通块都变为一个数字。。
可以仅保留某个数的第一次出现和最后一次出现（如果只出现一次，可以认为它在这个点出现了两次）。
问题就转化为每一段取一个数，求 LIS ，此处由于每一段中包含的数互不相同，认为是严格上升的。
将每一段中的数降序排列，求出最长严格上升子序列后即得。这是由于段内是降序排列的，不会被选取两次。
然后用数组总长度减去LIS长度就是答案。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n,m,ans,num,tot=0;
int a[N],rd[N],sum[N];
int bk[N],fst[N],lst[N];
int dp[N];
void solve(){
cin>>n;
ans=0,num=1,tot=0;
for(int i=1;i<=n;i++) fst[i]=2*n;
for(int i=1;i<=n;i++){
cin>>a[i];
fst[a[i]]=min(fst[a[i]],i);//求a[i]最左出现位置
lst[a[i]]=i;//a[i]最右出现位置
}
for(int i=1;i<=n;i++){
sum[i]=sum[i-1];
if(i==fst[a[i]]) ++sum[i];
if(i==lst[a[i]]) --sum[i];
if(sum[i]==0) bk[++tot]=i;//记录段内区间
}
for(int i=1;i<=tot;i++)
sort(a+bk[i-1]+1,a+bk[i]+1,greater<int>());//段内降序排序
int maxx=0;
for(int i=1;i<=n;i++){
int pos=lower_bound(dp+1,dp+maxx+1,a[i])-dp;
dp[pos]=a[i];
maxx=max(maxx,pos);
}
for(int i=1;i<=n;i++)//记录
if(lst[i]) --maxx;
cout<<-maxx<<"\n";
}
int main(){
//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
solve();
return 0;
}
K.树上问题
题意：有一颗 n 个节点组成的无根树，编号从 1 到 n ，每个节点有正整数点权。一个节点是美丽节点的充要条件为以这个节点做根所有节点的点权不小于其父亲节点的一半。有多少个美丽节点？
题解：先以任意结点做根，构成一棵树。然后对于每个节点，搜索其子树，记录以点 i 为根节点的子树的不合法边的数量，采用递归从下往上记录。
对于相连的结点如 u 和 v ，以 u 和 v 为根时，红蓝区域的边方向都没变，对答案贡献相同，只有 u，v 这条边的方向发生变化。因此我们给 \(ans_u\) 减去 \(v->u\) 的恭喜，加上 \(u->v\) 的贡献，就得到了 \(ans_v\)。
邻接表写法
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N];
vector<int> vt[N];
int cnt[N];//以u为根的子树不合法边的个数
void dfs1(int u,int fa){//当前节点，父节点
int sum=0;
for(int i=0;i<vt[u].size();i++){//遍历子节点
int v=vt[u][i];//相连的点
if(v==fa) continue;
dfs1(v,u);//往下搜
sum+=cnt[v]+(a[v]*2<a[u]);
}
cnt[u]=sum;
}
int ans[N];//记录每个节点为总根不合法边数量
void dfs2(int u,int fa){
for(int i=0;i<vt[u].size();i++){
int v=vt[u][i];
if(v==fa) continue;
ans[v]=ans[u]-(a[v]*2<a[u])+(a[u]*2<a[v]);
dfs2(v,u);
}
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++) vt[i].clear();
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
vt[u].push_back(v);//加双向边
vt[v].push_back(u);
}
dfs1(1,-1);
ans[1]=cnt[1];
dfs2(1,-1);
int sum=0;
for(int i=1;i<=n;i++) sum+=(ans[i]==0);//统计合法的数量
cout<<sum<<"\n";
}
int main(){
int T;cin>>T;
while(T--) solve();
return 0;
}
链式前向星写法
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],head[N],ent;//head数组和ent用来辅助链式前向星
struct edge{
int v,nxt;//目的节点，上一个指向
}e[N<<1];
void add(int u,int v){//链式前向星加边
e[++ent]={v,head[u]};
head[u]=ent;
}
int cnt[N];//以u为根的子树不合法边的个数
void dfs1(int u,int fa){//当前节点，父节点
int sum=0;
for(int i=head[u];i;i=e[i].nxt){//遍历子节点
int v=e[i].v;//相连的点
if(v==fa) continue;
dfs1(v,u);//往下搜
sum+=cnt[v]+(a[v]*2<a[u]);
}
cnt[u]=sum;
}
int ans[N];//记录每个节点为总根不合法边数量
void dfs2(int u,int fa){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa) continue;
ans[v]=ans[u]-(a[v]*2<a[u])+(a[u]*2<a[v]);
dfs2(v,u);
}
}
void solve(){
cin>>n;
ent=0;
memset(head,0,sizeof(head));
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
add(u,v),add(v,u);//加双向边
}
dfs1(1,-1);
ans[1]=cnt[1];
dfs2(1,-1);
int sum=0;
for(int i=1;i<=n;i++) sum+=(ans[i]==0);//统计合法的数量
cout<<sum<<"\n";
}
int main(){
int T;cin>>T;
while(T--) solve();
return 0;
}
L. Toxel 与 PCPC II
题意：有 n 行代码和 m 行出现bug，给定出bug的具体行数可以修复。可以选择一个 i，从第一行执行到 i 行，需要 i 秒，并且修复这 i 行内的所有bug，但是需要额外的时间，即再加上bug数量的4次方。问最少时间修复所有bug。
题解：简单DP。
状态：\(dp[i]\) 表示修复前 i 个bug所需的最少时间。
转移方程： \(dp[i]=min_{1≤j≤i}(dp[j]+a_i+(i-j)^4)\) 时间复杂度为 \(O(m^2)\)，会TLE。
如果我们多运行一次代码，最大花费为 2e5，但是 \(38^4-37^4>2e5\)，这意味着选了38个bug不如先选一个bug，再选37个bug。
所以枚举 j 时，不必枚举所有bug，只需要向下枚举四五十行即可。时间复杂度可为 \(O(40m)\)。
typedef long long ll;
const int N=2e5+10;
int n,m;
ll a[N],dp[N];
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>a[i],dp[i]=1e18;//初始化
dp[1]=1+a[1];//初始化
for(int i=1;i<=m;i++){//枚举m
for(int j=max(0,i-40);j<=i;j++){//枚举1~i并且优化
dp[i]=min(dp[i],dp[j]+a[i]+(ll)pow(i-j,4));
}
}
cout<<dp[m]<<"\n";
}
