2025牛客寒假算法基础集训营5(无F,G,H,K)
打的晕晕的
A
减法时注意数据范围
1
2
3
4
5
6
7
8
9
10
11
12
13
| void solve(){
int n;cin>>n;
char c;cin>>c;
if(c=='+'){
cout<<1<<" "<<n-1;
}
if(c=='*'){
cout<<1<<" "<<n;
}
if(c=='-'){
cout<<n*2<<" "<<n;
}
}
|
B
注意限制间隔
1
2
3
4
| void solve(){
int n,k,t;cin>>n>>t>>k;
cout<<min(((n-k)/t),k+1)<<"\n";
}
|
C
贪心，已经合法的位我们不对其进行二次操作，且每个非法位我们操作且仅执行一次操作，无论是对a执行还是对b执行
注意到四种非法情况
a=0,b=0,c=1;
a=0,b=1,c=0;
a=1,b=0,c=0;
a=1,b=1,c=1;
每两种情况都可以通过交换操作使得两个非法位合法，无非是交换a/b的区别；
所以思路就是，最大化两两配对四种非法位，自身不能和自身配对
配对过程就是很典的思路：当最大值大于剩下的所有数，非配对数为最大值-其他所有数之和；否则非配对数为所有数字之和为偶数?0:1
ans=min(全用反置操作，配对数$\times$y+非配对数$\times$x)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void solve(){
int n,x,y,ans=0;cin>>n>>x>>y;
string s1,s2,s3;cin>>s1>>s2>>s3;
int pos=0;
vector<int>v(4);
for(int i=0;i<n;i++){
if((s1[i]-'0')^(s2[i]-'0')!=(s3[i]-'0')){
if(s1[i]=='0'&&s2[i]=='0') v[0]++;
if(s1[i]=='1'&&s2[i]=='1') v[1]++;
if(s1[i]=='0'&&s2[i]=='1') v[2]++;
if(s1[i]=='1'&&s2[i]=='0') v[3]++;
pos++;
}
}
sort(v.begin(),v.end());
if(v[3]>v[0]+v[1]+v[2]){
ans=(v[3]-v[1]-v[2]-v[0])*x+(v[1]+v[2]+v[0])*y;
}else{
int sum=(v[0]+v[1]+v[2]+v[3]);
ans=(sum%2)*x+(sum-(sum%2))/2*y;
}
cout<<min(ans,x*pos);
}
|
D
贪心的想，我们构造字符串一定是某段中为连续的0和连续的1，前面一段的字符串如果为11…00，那么下一段字符串就应该是从0开始，即0…01…1，两段拼接起来并删除重复串后为101，也就是说这样每一段最多只会贡献1
考虑什么时候执行区间反置操作，当前一段的字符串为01时，若下一段全是1则该段对答案没有贡献，也就是说当该段全是0时，我们执行区间反置操作；同理，前一段是10时，下一段全是1，我们执行反置操作
用前缀和维护，调和级数复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void solve(){
int n;cin>>n;
string s;cin>>s;
s=" "+s;
int ans=0;
vector<int>pre(n+1,0);
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+(s[i]=='0');
}
for(int k=1;k<=n;k++){
int tem=0;
for(int j=k;j<=n;j+=k){
int cnt0=pre[j]-pre[j-k],cnt1=k-cnt0;
if(cnt0!=0&&cnt1!=0) tem++;
if(j+k>n){
cnt0=pre[n]-pre[j],cnt1=n-j-cnt0;
if(cnt0!=0&&cnt1!=0) tem++;
}
}
ans^=(tem+1);
}
cout<<ans<<"\n";
}
|
E
可以想到胜利方式有两种，直接胜利和间接胜利
直接胜利就是在下两步之后，横/竖/对角线直接连成三个
间接胜利就是下两步之后，我们有两行/两列/一行一列/一行一对角/一列一对角连成两个且第三个空位没有O阻挡，这样的话无论炸鸡去阻挡哪个，小L都能取得胜利
我检查间接胜利的方式就是遍历所有可能的组合判断是否符合
复杂度最高为O(300T)
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
| void solve(){
vector<vector<char>>g(10,vector<char>(10));
vector<array<int,2>>pos;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
cin>>g[i][j];
if(g[i][j]=='G'){
pos.push_back({i,j});
}
}
}
auto check1=[&](char c){
return c=='G'||c=='X';
};
auto check2=[&](char c){
return c=='X';
};
int ok=0;
for(int i=1;i<=3;i++){
int num1=check1(g[i][1])+check1(g[i][2])+check1(g[i][3]);
int num11=check2(g[i][1])+check2(g[i][2])+check2(g[i][3]);
int num2=check1(g[1][i])+check1(g[2][i])+check1(g[3][i]);
int num22=check2(g[1][i])+check2(g[2][i])+check2(g[3][i]);
if((num11>=1&&num1==3)||(num22>=1&&num2==3)) ok=1;
}
int num1=check1(g[1][1])+check1(g[2][2])+check1(g[3][3]);
int num11=check2(g[1][1])+check2(g[2][2])+check2(g[3][3]);
int num2=check1(g[1][3])+check1(g[2][2])+check1(g[3][1]);
int num22=check2(g[1][3])+check2(g[2][2])+check2(g[3][1]);
if((num1==3&&num11>=1)||(num2==3&&num22>=1)) ok=1;
for(auto i:pos){
for(auto j:pos){
if(i[0]==j[0]&&i[1]==j[1]) continue;
g[i[0]][i[1]]='X';g[j[0]][j[1]]='X';
int op=0;
for(int x=1;x<=3;x++){
int num1=check1(g[x][1])+check1(g[x][2])+check1(g[x][3]);
if(num1==3) op++;
int num2=check1(g[1][x])+check1(g[2][x])+check1(g[3][x]);
if(num2==3) op++;
}
int num11=check1(g[1][1])+check1(g[2][2])+check1(g[3][3]);
if(num11==3) op++;
int num22=check1(g[1][3])+check1(g[2][2])+check1(g[3][1]);
if(num22==3) op++;
if(op>=2) ok=1;
g[i[0]][i[1]]='G';g[j[0]][j[1]]='G';
}
}
cout<<(ok?"Yes\n":"No\n");
}
|
I
想复杂了，最后结论就是除非n为0，通过若干次两种操作组合可以操作出来任何数
应该是可以证出来的，这里放个伪证明
给定一个目标m>=1，我们只需要使得n最终的值在$[m^2,(m+1)^{2})$之间即可通过开方得到m，这中间有2m+1个数字，在m<=1e9时，任何2m+1个连续数字之间一定存在2的幂次
1
2
3
4
5
6
7
8
9
10
11
12
| void solve(){
int n,m,ok=0;cin>>n>>m;
if(m==0||n==0){
if(n==m){
cout<<"Yes\n";
}else{
cout<<"No\n";
}
return;
}
cout<<("Yes\n");
}
|
J
没啥说的，模拟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void solve(){
int n;cin>>n;
string s;cin>>s;
int v=0,ans=0;
for(auto i:s){
if(i=='0'){
v+=10;
ans+=v;
}else if(i=='1'){
v-=5;v=max(v,0LL);
ans+=v;
}else{
ans+=max(v-10,0LL);
}
}
cout<<ans;
}
|
L
构造题，可以很贪心的想到答案除了n==3之外就是n/3
想到互质，联想两个连续的数一定互质，自然的想到构造多组连续的三元组，即
1 2 3
4 5 6
7 8 9
10 11 12
可以观察到有的符合题意，有的不符合（每个三元组是三对质数），要想方法缩减质数的对数
可以发现每两个数就会出现一个偶数，每三个数就会出现一个整除3的数，无论是两个偶数/两个是3的倍数的数都会使得质数的对数-1，初步构造方法如下
x x+1 x+1+2
x+2 x+2+2 x+2+2+1
即1 2 4
3 5 6
这样每行都能出现两个偶数/两个3的倍数，缺点就是当n%3==0且为奇数的时候，右下角的数==n+1，即
1 2 4
3 5 6
7 8 10
考虑将10调整为9的方法即可，swap（6，10）可以轻松的满足条件，构造完成
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
| void solve(){
int n;cin>>n;
if(n==3){
cout<<0<<"\n";
return;
}
cout<<n/3<<"\n";
if((n/3)*3==n){
vector<vector<int>>a(n+1,vector<int>(4));
for(int i=1;i<=n/3;i++){
if(i&1){
a[i][1]=(i-1)*3+1;a[i][2]=(i-1)*3+2;a[i][3]=(i-1)*3+4;
}else{
a[i][1]=(i-1)*3;a[i][2]=(i-1)*3+2;a[i][3]=(i-1)*3+3;
}
}
a[n/3][3]=n;
if(n&1) swap(a[n/3][3],a[n/3-1][3]);
for(int i=1;i<=n/3;i++){
cout<<a[i][1]<<" "<<a[i][2]<<" "<<a[i][3]<<"\n";
}
}else{
for(int i=1;i<=n/3;i++){
if(i&1) cout<<(i-1)*3+1<<" "<<(i-1)*3+2<<" "<<(i-1)*3+4<<"\n";
else cout<<(i-1)*3<<" "<<(i-1)*3+2<<" "<<(i-1)*3+3<<"\n";
}
}
}
|