牛客小白月赛22补题
难度体验
签到：E.模拟、F.思维
简单：D.爆搜、G.暴力、J.大数模板
中级：A.STL、B.树形DP
困难：C.记忆化搜索、H.差分
压轴：I.计算几何
A.操作序列
题意
给出一个长度无限的数列，初始全部为零，有三种操作：
- 增加操作：给下标为 $t$ 的数加 $c$。特别注意，如果在下标$[t-30,t+30]$
内有不为零的数，增加操作无效。 - 削减操作：让数列中下标最小的不为零数变为零。
- 查询操作：查询数列中下标为$t$的数字是多少。
思路
STL模拟，用map维护实际数组，set维护非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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
map<int,int>mp;
set<int>st;//维护范围内非0数
map<int,int>::iterator it;
set<int>::iterator it2;
void add(int x,int c)
{
bool flag=1;
it2=st.lower_bound(x-30);
for(set<int>::iterator it3=it2;it3!=st.end();it3++)
{
if(*it3<=x+30)
return;
else
break;
}
if(mp[x]+c==0)
{
mp.erase(x);
st.erase(x);
}
st.insert(x);
mp[x]+=c;
}
int sub()
{
if(st.empty())
return 0;
it=mp.begin();
int ret=it->second;
st.erase(st.begin());
mp.erase(mp.begin());
return ret;
}
int query(int x)
{
it2=st.find(x);
if(it2==st.end())//不在
return 0;
return mp[x];
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int n,t,c;
scanf("%d",&n);
while(n--)
{
char ch='?';
scanf("%d%c",&t,&ch);
if(ch==' ')
{
scanf("%d",&c);
add(t,c);//a[t]+=c
continue;
}
if(t==-1)
{
if(st.empty())
printf("skipped\n");
else{
printf("%d\n",sub());
}
}
else
printf("%d\n",query(t));
}
return 0;
}B.树上子链
题意
给定一棵树 T ，树 T 上每个点都有一个权值。
定义一颗树的子链的大小为：这个子链上所有结点的权值和 。
请在树 T 中找出一条最大的子链并输出。思路
前缀和，树形DP。
通过DFS维护根节点到节点x的前缀和，以及x节点到叶子结点的最大值与次大值。代码
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
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
vector<int>G[maxn];
ll val[maxn],sum[maxn],dp[maxn],dp2[maxn],ans;
void dfs(int x,int fa)
{
sum[x]=sum[fa]+val[x];
dp[x]=val[x];
dp2[x]=-inf;
for(auto &v:G[x])
{
if(v==fa)
continue;
dfs(v,x);
if(dp[v]+val[x]>dp[x])
{
dp2[x]=dp[x];
dp[x]=dp[v]+val[x];
}
else
dp2[x]=max(dp2[x],dp[v]+val[x]);
}
ans=max(ans,max(sum[fa]+dp[x],dp[x]+dp2[x]-val[x]));
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int n,u,v;
cin>>n;
for(int i=1;i<=n;i++)
cin>>val[i];
for(int i=1;i<n;i++)
{
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
ans=val[1];
dfs(1,0);
cout<<ans<<endl;
return 0;
}C.交换游戏
题意
有12个孔，有些孔上面有障碍。
若如果相邻的三个孔有两个孔被遮挡，并且被遮挡的两个孔相邻，则可以将中间的障碍拿掉，并将一端的遮挡物移到另一端没有被遮挡的孔上面。
简单来说：将这三个孔的状态反转。
例如记x为障碍遮住的孔，o为未遮住的孔
oxx -> xoo，xxo -> oox思路
记忆化搜索
将状态看作二进制，枚举计算每一种组合的答案，$O(1)$查询。代码
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
52
53
54
55
56
57
58
59
60
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
bool vis[1<<13];
int ans[1<<13];
void dfs(int x)
{
if(vis[x])
return;
vis[x]=1;
int cnt=0;
for(int i=1;i<=(1<<11);i<<=1)
if(x&i)
cnt++;
ans[x]=cnt;
for(int i=3,t1=1,t2=2,t3=4;i<=12;i++,t1<<=1,t2<<=1,t3<<=1)
{//分别为这三个位的状态
if((x&t2)&&!((x&t1)&&(x&t3))&&((x&t1)||(x&t3)))
{
if(x&t1)
{
dfs(x-t2-t1+t3);
ans[x]=min(ans[x],ans[x-t2-t1+t3]);
}
else{
dfs(x-t2-t3+t1);
ans[x]=min(ans[x],ans[x-t2-t3+t1]);
}
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
for(int i=0;i<(1<<12);i++)//预处理
dfs(i);
int t;
string s;
cin>>t;
while(t--)
{
cin>>s;
int now=0;
for(auto &ch:s)
{
now<<=1;
if(ch=='o')
now|=1;
}
cout<<ans[now]<<endl;
}
return 0;
}D.收集纸片
题意
我们把房间按照笛卡尔坐标系进行建模之后，每个点就有了一个坐标。
假设现在房子里有些纸片需要被收集，收集完纸片你还要回归到原来的位置，你需要制定一个策略来使得自己行走的距离最短。
你只能沿着 x 轴或 y 轴方向移动：从位置 (i,j) 移动到相邻位置 (i+1,j)，(i-1,j)，(i,j+1) 或 (i,j-1) 距离增加 1。思路
范围不大，爆搜即可代码
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
52
53
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
struct node
{
int x,y;
} a[15];
int n,sx,sy,ans;
int dis(int x1,int y1,int x2,int y2)
{
return abs(x1-x2)+abs(y1-y2);
}
int dis(int s,int t)
{
if(s==0)//s是起点
return abs(sx-a[t].x)+abs(sy-a[t].y);
return abs(a[s].x-a[t].x)+abs(a[s].y-a[t].y);
}
bool vis[maxn];
//queue<int>q;
void dfs(int t,int tim,int tot)
{
if(tim==n)
{
ans=min(ans,tot+dis(sx,sy,a[t].x,a[t].y));
return;
}
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
vis[i]=1;
dfs(i,tim+1,tot+dis(t,i));
vis[i]=0;
}
}
}
int main()
{
int t,r,c;
cin>>t;
while(t--)
{
cin>>r>>c>>sx>>sy>>n;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
ans=inf;
dfs(0,0,0);
cout<<"The shortest path has length "<<ans<<endl;
}
return 0;
}E. 方块涂色
签到题1
2
3
4
5
6
7
8
9
10
11
12
using namespace std;
typedef long long ll;
int main()
{
ll n,m,r,c;
while(cin>>n>>m>>r>>c)
{
cout<<(n-r)*(m-c)<<endl;
}
return 0;
}F. 累乘数字
签到题，有点小思维代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
int main()
{
string n;
ll d;
while(cin>>n>>d)
{
cout<<n;
while(d--)
cout<<"00";
cout<<endl;
}
return 0;
}G.仓库选址
思路
比赛时没开这题……$O(n^4)$无脑暴力做代码
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
using namespace std;
typedef long long ll;
const int maxn=105,inf=0x3f3f3f3f,mod=1000000007;
int mp[maxn][maxn];
int dis(int x1,int y1,int x2,int y2)
{
return abs(x1-x2)+abs(y1-y2);
}
int main()
{
int t,n,m;
cin>>t;
while(t--)
{
cin>>m>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>mp[i][j];
int ans=inf;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int now=0;
for(int k=1;k<=n;k++)
for(int l=1;l<=m;l++)
now+=mp[k][l]*dis(i,j,k,l);
ans=min(ans,now);
}
cout<<ans<<endl;
}
return 0;
}H.货物种类
比赛时看了题目想了树套树的假做法，觉得空间复杂度炸裂+难写就没继续想……题意
n个仓库，编号从1到n。
当购进某种货物的时候，商家会把货物分散的放在编号相邻的几个仓库中。
当所有货物购买完毕，存放货物种类最多的仓库编号为多少？思路
离散化，差分，看代码代码
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
52
53
54
55
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
struct ope
{
int l,r,g;
ope(int l,int r,int g):
l(l),r(r),g(g){}
};
vector<int>des,be[maxn],ed[maxn];
int res[maxn];
int main()
{
vector<ope>op;
int n,m,l,r,d,cnt=0;
cin>>n>>m;
while(m--)
{
cin>>l>>r>>d;//[l,r]存入货物d
op.push_back(ope(l,r,d));
des.push_back(d);
}
sort(des.begin(),des.end());//对货物去重
des.erase(unique(des.begin(),des.end()),des.end());
for(auto &i:op)
{
i.g=lower_bound(des.begin(),des.end(),i.g)-des.begin()+1;
be[i.l].push_back(i.g);
ed[i.r].push_back(i.g);
}
int ans=0,num=0,now=0;
for(int i=1;i<=n;i++)
{//now维护i的货物种类数
for(int j:be[i])//[i,?]范围的货物j
{
if(!res[j])//该区域初次被j覆盖
now++;
res[j]++;//res是一个差分数组
}
if(now>ans)
{
ans=now;
num=i;//种类最多的货舱
}
for(int j:ed[i])//[?,i]范围的货物
{
res[j]--;
if(!res[j])//该区域不再被j覆盖
now--;
}
}
cout<<num<<endl;
return 0;
}I.工具人
思路
一句话题解+玄学代码看了我一晚上……
计算出每个点可以被射中的角度范围，放到循环数组里按角度排序。
枚举所有点作为起点，贪心地求出最小开枪数。还是不很理解
下面这个代码大概就是照着题解敲了一遍并加上自己的理解，并且在核心代码有这么一行如果换成1
cnt+=rec.size();//这里写成cnt+=rec.size()?1:0更好理解
同样可以过，而且更好理解。1
2if(rec.size())
cnt++;
比较疑惑为什么按题解的写法可以保证最后数组中元素数量不大于1，如果有大佬会的话请务必在下面留言教教本菜鸡QAQ代码
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
const double eps= 1e-8,pi=acos(-1);
//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
x=0; int ch=getchar(),f=0;
while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
if(f)x=-x;
read(oth...);
}
struct node
{
int type,id;
double angle;
node (int a,double b,int c):
type(a),id(c),angle(fmod(b+2*pi,2*pi)){}
bool operator <(const node &b)
{
if(abs(angle-b.angle)>eps)//角不相等
return angle<b.angle;
else
return type<b.type;
}
};
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int t,n,d,c;
cin>>t;
while(t--)
{
cin>>n>>d;//数量n,有效半径d
vector<node> v;
for(int i=c=0;i<n;i++)
{
double x,y;
cin>>x>>y;
if(x*x+y*y<=d*d+eps)
continue;//随便开一枪就能打中
double a=atan2(y,x);//(x,y)弧度角
double t=asin(d/sqrt(x*x+y*y));//确定角度范围
v.push_back(node(0,a-t,c));//角度在[a-t,a+t]即可打中
v.push_back(node(1,a+t,c++));
}
if(c==0)
{//所有的点都能随便开一枪就打中
cout<<1<<endl;
continue;
}
sort(v.begin(),v.end());
int ans=c;//当前至少开c枪
for(int i=0;i<v.size();i++)
{//枚举第一枪位置
int cnt=0;
vector<bool>vis(c,0);
vector<int>rec;
for(int k=0;k<v.size();k++)//贪心求开多少枪
{//以i开始向后的k个元素为j
int j=(i+k)%v.size();
if(v[j].type==0)//进入点j区域
{
vis[v[j].id]=1;
rec.push_back(v[j].id);
}
else if(vis[v[j].id])//j区域结束
{//要离开该点范围了,必须开一枪,同时击中rec中所有元素
cnt++;
for(int l:rec)
vis[l]=0;
rec.clear();
}
}
cnt+=rec.size();//这里写成cnt+=rec.size()?1:0更好理解
//如果有剩余元素就要开一枪崩掉,没有的话就不必开枪
//至于为什么题解可以这么写,我也想知道...
ans=min(ans,cnt);
}
cout<<ans<<endl;
}
return 0;
}J.计算A+B
题目没啥好说的，一个裸的大数板子思路
大数加法代码
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
52
53
54
55
56
57
58
59
60
61
62
63
64
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
x=0; int ch=getchar(),f=0;
while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
if(f)x=-x;
read(oth...);
}
const int Length=10005;
string add(const string &a,const string &b)//加
{
string ans;
int na[Length]={0},nb[Length]={0};
int la=a.size(),lb=b.size();
for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0';
for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0';
int lmax=la>lb?la:lb;
for(int i=0;i<lmax;i++) na[i]+=nb[i],na[i+1]+=na[i]/10,na[i]%=10;
if(na[lmax]) lmax++;
for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0';
return ans;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int n;
string s;
cin>>n;
while(n--)
{
cin>>s;
string a,b;
bool flag=0;
for(auto &ch:s)
{
if(ch=='+')
{
flag=1;
continue;
}
if(!flag)
a+=ch;
else
b+=ch;
}
if(a.empty()||b.empty())
cout<<"skipped"<<endl;
else{
cout<<add(a,b)<<endl;
}
}
return 0;
}