题目列表
赛后感言
本来能 $400\tt{\ pts}$ 的，T3 边界写错扣十分，这个问题不大，加个判断就过了。T4 真的扣的分真伤，打错了两个数字废了。
痛失 U 盘！
比赛点评：一道送分一道板，一道模拟一道原。
四则混合运算
题目很简单，扫描两遍字符串，第一遍处理乘除符号，第二遍处理加减符号。
时间复杂度 $\mathcal O(\left|S\right|)$。
插一句题外话，像这种题最好不要偷懒在字符串中插入最后一起输出。
WXR 巨佬因为这个，VP CSP-J 2020 的时候，T3 因为这个没有 AC 爆空间了.
代码
#include<bits/stdc++.h>
using namespace std;
int a[1919810],Time,n;
string s;
int main()
{
freopen("operation.in","r",stdin);
freopen("operation.out","w",stdout);
cin>>n>>s;
for(int i=0;i<n;i++)
{
if(s[i]=='*'||s[i]=='/')a[i]=++Time;
}
for(int i=0;i<n;i++)
{
if(s[i]=='+'||s[i]=='-')a[i]=++Time;
}
for(int i=0;i<n;i++)
{
cout<<s[i];
if(a[i])printf("(%d)",a[i]);
}
return 0;
}
/*
13
2+2+2*2/2-2*2
5
12345
*/回扣
题意很显然，完全背包板子，对于每个游客做一遍完全背包即可。
这题我竟然赛时感觉是 dp 想不到是什么 dp 先写了个贪心，切完其他三题再回来的。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
struct node
{
int p,q;
}b[120];
int a[50];
bool cmp(node a,node b)
{
return a.p*b.q<b.p*a.q;
}
int f[1000020];
int main()
{
freopen("cicer.in","r",stdin);
freopen("cicer.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>b[i].p>>b[i].q;
}
for(int k=1;k<=n;k++)
{
memset(f,0,sizeof(f));
for(int i=1;i<=m;i++)
{
for(int j=b[i].p;j<=a[k];j++)
{
f[j]=max(f[j],f[j-b[i].p]+b[i].q);
}
}
ans+=f[a[k]];
}
// sort(b+1,b+m+1,cmp);
// for(int i=1;i<=m;i++)
// {
// for(int j=1;j<=n;j++)
// {
// ans+=a[j]/b[i].p*b[i].q;
// a[j]%=b[i].p;
// }
// }
cout<<ans<<endl;
return 0;
}
/*
3
200 300 300
5
12 2
20 4
30 5
50 5
100 18
1
1000
2
499 99
505 101
*/花不在多
这题有个性质，数组中的火元素之和，一定等于 $1$，想到这个就是个模拟题很好做了。
所以我们用个双指针，每次往旁边扫，如果不一样就停止，看一下和走过的路程是否 $\geq m$，$<$ 直接退出，$\geq$ 继续。
但如果和我一样，左右端点一开始不是都在 $x$ 上，那么要注意你另一个端点摆在 $x$ 左边还是 $x$ 右边，当心像我一样越界。
代码
#include<bits/stdc++.h>
using namespace std;
int a[1000020];
int n,m,x,y,l,r;
int main()
{
freopen("eliminate.in","r",stdin);
freopen("eliminate.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&x,&y);
n++;
for(int i=1;i<=n;i++)
{
if(i==x+1)a[i]=y;
else
{
scanf("%d",a+i);
}
}
// for(int i=1;i<=n;i++)
// {
// cout<<a[i]<<' ';
// }
// cout<<endl;
x++;
if(x==n)l=x-1,r=x;
else l=x,r=x+1;
while(1<=l&&r<=n)
{
if(a[l]!=a[r])break;
int tmp=a[l],L=l,R=r;
for(;l>=1;l--)
{
// cout<<l<<" ";
if(a[l]!=tmp)break;
}
for(;r<=n;r++)
{
// cout<<r<<" ";
if(a[r]!=tmp)break;
}
// cout<<endl;
// cout<<(r-R)+(L-l)<<endl;
if((r-R)+(L-l)<m)break;
}
if(l<1&&r>n)
{
puts("pcftxdy");
return 0;
}
for(int i=1;i<=l;i++)printf("%d ",a[i]);
for(int i=r;i<=n;i++)printf("%d ",a[i]);
return 0;
}
/*
7 3 3 2
1 1 1 2 2 1 1
8 3 2 2
1 1 2 2 1 3 3 3
8 3 3 2
1 1 1 2 2 3 3 3
*/密码锁
性质：每个按钮最多转四次，旋转先后顺序没有影响。
实际很简单，最暴力的方法九重循环枚举就能过。
像我一样 dfs 也可以，dfs 还可以用于 $n$ 个锁的情况。
bfs 也可以，但当心队列 push 过多爆空间。
代码
#include<bits/stdc++.h>
using namespace std;
int a[20];
int n,ans=INT_MAX;
vector<int>b[20];
int f[20];
void dfs(int dep)
{
if(dep>9)
{
int tmp[20],cnt=0;
for(int i=1;i<=9;i++)
{
tmp[i]=a[i];
}
for(int i=1;i<=9;i++)
{
if(f[i])
{
cnt+=f[i];
for(int j:b[i])
{
tmp[j]+=f[i];
tmp[j]%=4;
}
}
}
for(int i=1;i<=9;i++)
{
if(tmp[i]!=0)
{
return;
}
}
// cout<<endl;
// for(int i=1;i<=9;i++)
// {
//// if(tmp[i])
//// {
//// cout<<endl;return;
//// }
// cout<<f[i]<<' ';
// }
// cout<<endl;
ans=min(ans,cnt);
return;
}
f[dep]=1;
dfs(dep+1);
f[dep]=2;
dfs(dep+1);
f[dep]=3;
dfs(dep+1);
f[dep]=0;
dfs(dep+1);
}
int main()
{
freopen("lock.in","r",stdin);
freopen("lock.out","w",stdout);
b[1].push_back(1);b[1].push_back(2);b[1].push_back(4);b[1].push_back(5);
b[2].push_back(1);b[2].push_back(2);b[2].push_back(3);
b[3].push_back(2);b[3].push_back(3);b[3].push_back(5);b[3].push_back(6);
b[4].push_back(1);b[4].push_back(4);b[4].push_back(7);
b[5].push_back(2);b[5].push_back(4);b[5].push_back(5);b[5].push_back(6);b[5].push_back(8);
b[6].push_back(3);b[6].push_back(6);b[6].push_back(9);
b[7].push_back(4);b[7].push_back(5);b[7].push_back(7);b[7].push_back(8);
b[8].push_back(7);b[8].push_back(8);b[8].push_back(9);
b[9].push_back(5);b[9].push_back(6);b[9].push_back(8);b[9].push_back(9);
for(int i=1;i<=9;i++)
{
cin>>a[i];
}
dfs(1);
cout<<ans<<endl;
return 0;
}
/*
3 3 0 2 2 2 2 1 2
1 1245
2 123
3 2345
4 147
5 24568
6 369
7 4578
8 789
9 5689
1、每个按钮最多只需按多少次？
2、按钮的按动次序是否会影响结果？ 0
3、每种状态在无多余按键和不考虑按键顺序的情况下有多少种开锁方案？
*/