2024 河南萌新联赛 1
A 造数
给定整数 $n$，操作 1：$+1$，操作 2：$+2$，操作 3：$\times 2$，多少次将 $0$ 转化到 $n$
逆向思维，把 $n$ 化为 $0$ 即可
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,cnt=0;
cin>>n;
while(n){
if(n&1)n--,cnt++;
else if(n>2)cnt++,n/=2;
else cnt++,n-=2;
}
cout<<cnt<<endl;
}
|
H 两难抉择
长度为 $n$ 的数组 $a$，两种操作选一个进行一次或不操作。
显然将数组最大值 $\times n$ 后答案最大
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n;
cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++)cin>>a[i];
sort(a.begin(),a.end());
int sum=0;
for(int i=0;i<n;i++){
sum+=a[i];
}
sum=max(sum+n,sum+(n-1)*a[n-1]);
cout<<sum<<endl;
}
|
K 图上计数
构造的两块联通块即为最接近 $n/2$ 的两块
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
}
if(n<=1){
cout<<"0\n";
return 0;
}
cout<<(long long)n/2*(n-n/2)<<endl;
}
|
I 除法移位
$a$ 中最大值位于第一位时即是答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,t;
cin>>n>>t;
vector<int>a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
int mx=0,ans=0;
for(int i=1;i<=min(t,n);i++){
if(a[n-i+1]>mx){
mx=a[n-i+1];
ans=i%n;
}
}
cout<<ans<<endl;
}
|
F 两难抉择新编
与 H 类似，但是操作范围随 $i$ 改变而改变 $O(n^{3/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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n;
cin >> n;
vector<int> a(n + 1);
int sum = 0, ans = 0;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) sum ^= a[i];
ans = sum;
for (int i = 1; i <= n; i++) {
for (int x = 1; x <= n / i; x++) {
int t1 = sum ^ a[i] ^ (a[i] + x);
int t2 = sum ^ a[i] ^ (a[i] * x);
ans = max(ans, max(t1, t2));
}
}
cout << ans << endl;
return 0;
}
|
G 旅途的终点
反悔贪心，前 $k$ 个直接存入 set，后续的小于 set 内第一个元素就替换，否则就正常进行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <bits/stdc++.h>
using namespace std;
#define ll __int128
int main(){
long long n,m,k;
cin>>n>>m>>k;
vector<long long>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
multiset<ll>s;
for(int i=1;i<=n;i++){
s.insert(a[i]);
if(s.size()>k){
m-=*s.begin();
if(m<=0){
cout<<i-1<<endl;
return 0;
}
s.erase(s.begin());
}
}
cout<<n<<endl;
return 0;
}
|
B 爱探险的朵拉
图中可能有环，那么就是要找包含环的最长链，或是无环的最长链
记录每个点的入度，如果某个点的入度为 $0$，他们不会构成环，即可作为链起点，再依次对入度为 $0$ 的点操作，找出他们能构成最长的链有多长。
之后再以每个点为起点找答案，如果前面的过程标记过则跳过，没标记过说明这是环上点，用 dfs 找这个环加上前链有多长，并更新答案
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 <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N],dis[N],cnt[N];
bool vis[N];
deque<int>q;
int dfs(int x){
int sum=0,mx=0;
for(int i=x;;i=a[i]){
if(vis[i])break;
vis[i]=1;
++sum;
mx=max(mx,dis[i]);
}
return mx+sum;
}
int main(){
int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
cnt[a[i]]++;
}
for(int i=1;i<=n;i++)
if(!cnt[i])q.push_back(i);
while(!q.empty()){
int x=q.front();
q.pop_front();
vis[x]=1;
dis[a[x]]=max(dis[a[x]],dis[x]+1);
--cnt[a[x]];
if(!cnt[a[x]])q.push_back(a[x]);
}
for(int i=1;i<=n;i++){
if(vis[i])continue;
int tmp=dfs(i);
ans=max(ans,tmp);
}
cout<<ans<<endl;
}
|
C 有大家喜欢的零食吗
二分图匹配板子，之后学了补
D 小蓝的二进制询问
显然是前缀和，那么重点就是如何计算前 $x$ 个数的 $1$ 的个数
从最低位看起，只有 $0$，$1$，二者循环，再往上 $1$ 位，仍然为 $0$，$1$ 循环，显然每一位上的循环都是一样的，我们对每一位能出现的 $1$ 进行计算，当前位数为 $k$ 时，这一位上就会有 $2^k$ 个 $1$ 和 $2^k$ 个 $0$。
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
ll sum(ll x,int y){
if(x==0) return 0;
ll s=1LL<<y;
ll cnt=x/s;
ll ans=cnt*s/2;
ll d=cnt*s+(1LL<<(y-1));
ll dd=x-d+1;
if(dd>0) ans+=dd;
return ans;
}
int main(){
int t;
cin>>t;
while(t--){
ll ans=0,l,r;
cin>>l>>r;
for(int i=61;i>0;i--){
ll p=(sum(r,i)%MOD-sum(l-1,i)%MOD+MOD)%MOD;
ans=(ans+p)%MOD;
}
cout<<ans<<endl;
}
}
|
J 最大矩阵匹配
将矩阵上下翻转后，变为固定左上一个点，向其他三个方向拓展的问题，用二维前缀和辅助判断三个点是否都为 $1$，来实现 DP 状态转移