前行 - CF Round #536(Div2)

只做了前 $5$ 道题……最后一道听说要用 $BSGS$ ;
学都没有学……看来又要填坑了


(Tab. 下列的题意均为根据基础题意进行增添,与原题目背景有出入,但是不影响做题)

『A: Lunar New Year and Cross Counting』 〔传送门〕

「题意」

你得到了一个 $n\times n$ 的棋盘,上面的格子一些画着 “X” (大写),另一些画着 “.”。假如一个格子本身是”X”,且它的左上、左下、右上、右下都是”X”,我们称我们找到了一个“叉”。求棋盘上共有多少个“叉”。

(数据规模:$0<n\leq 500$)

「解析」

数据 $O(n^2)$ 能过,那么我们就按照题意,枚举格子 $(i,j)$ ,如果 $(i,j)$,$(i-1,j-1)$,$(i+1,j-1)$,$(i-1,j+1)$,$(i+1,j+1)$ 都是 “X”,就在答案 tot 里加 $1$。

「源代码」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char str[505][505];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%s",str[i]+1);
int tot=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(str[i][j]=='X' && str[i-1][j-1]=='X' && str[i-1][j+1]=='X' && str[i+1][j-1]=='X' && str[i+1][j+1]=='X')
tot++;
printf("%d\n",tot);
return 0;
}

『B: Lunar New Year and Food Ordering』 〔传送门〕

「题意」

Alice 经营一家餐厅。餐厅有 $n$ 种菜,由于原料不够,Alice 发现第 $i$ 种菜最多只能做出 $a_i$ 份;第 $i$ 种菜的价格为 $c_i$。

将会有 $m$ 个顾客依次来到餐厅(第 $1$ 个顾客最先来),第 $j$ 个顾客会点 $d_j$ 份第 $t_j$ 种菜。如果还能够做出 $d_j$ 份第 $t_j$ 种菜,那么顾客就会买下这些菜;如果不足够做出 $d_j$ 份第 $t_j$ 种菜,餐厅将会先尽可能地给出第 $t_i$ 种菜,然后用尽可能便宜的菜(如果两个菜价格相同,编号小的被优先考虑)补足剩下的菜(也就是说提供的菜的总数还是 $d_j$),如果补足了 $d_j$ 份菜,顾客将会支付餐厅提供的菜;如果最后也没能补足 $d_j$ 份,顾客会非常生气地离开而不支付(注意这个时候提供给这个顾客的菜不能收回)。

「解析」

不得不说题意有点绕。

首先将菜的编号按菜的价格从小到大排序(并且价格相同的菜编号小的排在前面),记为 id[] 。定义指针 pos 指向 id[] ,表示现在可能可以提供的价格最小的菜。计当前第 $i$ 种菜能够做出 $r_i$ 份。

依次处理每一个顾客:
① 如果第 $t_j$ 种菜还能够做出 $d_j$ 份,就输出这些菜的总价格,并且将 $r_{t_j}$ 减掉 $d_j$ ;
② 否则定义 tot 表示提供给该顾客的菜的总价格,首先尽可能地提供给顾客第 $t_j$ 种菜(先 $d_j-=r_{t_j}$ ,再 $tot+=r_{t_j}\times c_{t_j}$,最后 $r_{t_j}=0$ ),然后用第 $id[pos]$ 种菜补足,直到补足 $d_j$ 种菜或不能做出任何菜;如果补足了,就输出 tot,否则输出 $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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=(int)1e5;
struct DISH{
int c,a;
}dis[N+5];
int id[N+7];
int n,m;
bool cmp(int a,int b){
if(dis[a].c!=dis[b].c) return dis[a].c<dis[b].c;
else return a<b;
}
ll sum;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&dis[i].a),sum+=dis[i].a;
for(int i=1;i<=n;i++) scanf("%d",&dis[i].c),id[i]=i;
sort(id+1,id+n+1,cmp);
int pos=1;
for(int i=0;i<m;i++){
int t,d;
scanf("%d%d",&t,&d);
if(dis[t].a>=d) printf("%lld\n",(ll)dis[t].c*d),dis[t].a-=d;
else{
ll tot=0;
tot+=1ll*dis[t].c*dis[t].a;
d-=dis[t].a;dis[t].a=0;
while(d && pos<=n){
if(dis[id[pos]].a<=d)
tot+=1ll*dis[id[pos]].c*dis[id[pos]].a,
d-=dis[id[pos]].a,
dis[id[pos]].a=0,
pos++;
else
tot+=1ll*dis[id[pos]].c*d,
dis[id[pos]].a-=d,
d=0;
}
if(d) printf("0\n");
else printf("%lld\n",tot);
}
}
return 0;
}

『C: Lunar New Year and Number Division』 〔传送门〕

「题意」

过年了,但是你的作业还没有做完……

有这样一道题——给出集合 $A=\{a_1,a_2,…,a_n\}$ 以及集合的大小 $n$ ($n$ 是偶数),将 $A$ 分为 $m$ 个($m$ 由你自己决定)子集 $B_i(1\leq i\leq m)$ (每个元素属于且仅属于一个子集,且每个子集至少有 $2$ 个元素),设子集 $B_i$ 的元素之和为 $s_i$,求 $\sum_{i=1}^ms_i^2$ 的最小值。

作为优秀的 OIer ,你当然想编程解决这个问题啦~

「解析」

一眼看出来贪心……但是严谨的证明我们不如先从 $A=\{a,b,c,d\} (a<b<c<d) $ 这种情况开始:

① 有两种选择 “分成 $1$ 个子集”,“分成 $2$ 个子集”,显然前者更大,选择后者;

② $3$ 种选择 $\{a,b\}\{c,d\}$,$\{a,c\}\{b,d\}$,$\{a,d\}\{b,c\}$:令 $D=a^2+b^2+c^2+d^2$,答案分别为 $A=D+2ab+2cd$,$B=D+2ac+2bd$,$C=D+2ad+2bc$;$A>C$ 且 $B>C$ ;选择 $C$;

综上,推而广之,贪心策略即“将原集合分为多个大小为 $2$ 的集合,越小的元素与越大的元素搭配”。

「源代码」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=(int)3e5;
int num[N+5],n;
ll ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
sort(num+1,num+n+1);
for(int i=1,j=n;i<j;i++,j--)
ans+=1ll*(num[i]+num[j])*(num[i]+num[j]);
printf("%lld\n",ans);
return 0;
}

『D: Lunar New Year and a Wander』 〔传送门〕

「题意」

新年了,你来到公园游玩。公园有 $n$ 个景区,编号为 $1$ ~ $n$,有 $m$ 条无向道路连接两个景区(保证所有景区相连通)。你非常好奇,于是拿了一个笔记本:当你访问一个之前没去过的景区,你在笔记本上记下它的编号。你可以重复经过同一个景区,但当你到过所有的景区后,你会离开公园,此时你的笔记本上记下了一个长度为 $n$ 的序列,你希望知道能够实现的使序列字典序最小的方案,输出该序列。

假设你一开始在景点 $1$。

「解析」

非常经典的题目,而且感觉跟2018年的NOIP提高组的题很像,但是要简单许多。

贪心地想,下一个没去过的景点一定要尽可能去编号小的,假设去过的景点为 $\{A_1,A_2,…,A_k\}$ ,那么我们下一个一定去与 $A_i(1\leq i\leq k)$ 联通的没去过的编号最小的景点。怎么找这个景点?只需要用一个优先队列就可以了~ 定义一个小根堆,每次取出堆顶,记录编号,再将该点相连通的没去过且不在堆中的景点插入堆中,直到堆为空。

「源代码」

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=(int)1e5;
int n,m;
struct GRAPH{
struct NODE{
int to,nxt;
NODE(){}
NODE(int _to,int _nxt):to(_to),nxt(_nxt){};
}edg[N*2+5];
int adj[N+3],cnt;
void AddEdge(int u,int v){
edg[++cnt]=NODE(v,adj[u]);
adj[u]=cnt;
}
void Rebuild(){
cnt=0;
memset(adj,-1,sizeof adj);
}
}grp;
bool vis[N+7],fir;
int main(){
grp.Rebuild();
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++)
scanf("%d%d",&u,&v),
grp.AddEdge(u,v),
grp.AddEdge(v,u);
priority_queue<int,vector<int>,greater<int> > que;
vis[1]=true;
que.push(1);
while(!que.empty()){
int u=que.top();que.pop();
if(fir) printf(" %d",u);
else fir=true,printf("%d",u);
for(int i=grp.adj[u];i!=-1;i=grp.edg[i].nxt){
int v=grp.edg[i].to;
if(!vis[v]) vis[v]=true,que.push(v);
}
}
printf("\n");
return 0;
}

『E: Lunar New Year and Red Envelopes』 〔传送门〕

「题意」

新年了,你收到了很多礼物。

礼物发放的时间是 $1$ ~ $n$。第 $i$ 个礼物的价值为 $w_i$,且只能在 $s_i$ 到 $t_i$ 之间领取($s_i$ 之前还没发放,$t_i$ 之后就被抢完了);为了防止一些手速快的人抢到太多礼物,规定领取第 $i$ 份礼物后直到 $d_i$ 时刻都不能继续领礼物(也就是说 $d_i+1$ 时才能继续领),且每种礼物只能拿一次。

Bob 也参与了,他不怎么聪明,他领取礼物的策略是:如果当前有礼物且他可以领取,他就会领取礼物;如果同一时刻有多个礼物,他会领取价值最大的;如果同一时刻有多个价值最大的礼物,他会领取 $d$ 最大的(我也不知道为什么)。但是他的女儿想趁机捉弄他一番:她可以干扰 Bob 领取礼物 $m$ 次,干扰一次可以使 Bob 某一时刻不能领取任何礼物。她十分聪明,她想要 Bob 领取到的礼物的总价值最小。

求最后 Bob 能领取到总价值为多少的礼物。

(满足$1 \leq s_i \leq t_i \leq d_i \leq n,1 \leq w_i \leq 10^9$ )

「解析」

读了半天才读懂题……根据题目意思我们可以知道按照 Bob 的策略,在某一时刻他领取的是哪一个礼物。这个可以用单调队列维护,具体见代码。记时刻 $i$ Bob 会领取第 $cs[i]$ 份礼物。

接下来可以用 DP 解决。定义 $dp[i][j]$ 表示前 $i$ 个时刻(不包括时刻 $i$ )女儿干扰 $j$ 次 Bob 能够领取到的礼物的价值。由于女儿很聪明,她会让礼物总价值最小(也就是 dp 数组最小),所以转移时我们需要取 min ,则把 dp 数组赋值为 INF。这里我们采用“我为人人”(也就是刷表法)的方法转移,这样的话我们才知道选取哪一份礼物,从而知道什么时候 Bob 能继续领礼物。

那么我们就可以得到转移方程式:

看起来非常没有问题,然后我样例都没过……

才发现有时候没有礼物可以领取,这里还需要转移,也就是:

而且最后女儿不一定要用完所有的 $m$ 次干扰的机会,因此答案在 $dp[n+1][i]$ 里取 min (注意状态定义,结束时应该是 $dp[n+1][i]$)。

「源代码」

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int K=(int)1e5;
typedef long long ll;
int n,m,k;
struct POST{
int val,fal,lef,rig;
}pst[K+5];
bool cmp(POST A,POST B){
if(A.lef==B.lef) return A.rig<B.rig;
return A.lef<B.lef;
}
ll vl[K+3],dp[K+5][205],cs[K+3];
struct QUEUE{
int id,val,d;
QUEUE(int _id,int _val,int _d):id(_id),val(_val),d(_d){}
bool operator <(const QUEUE B)const{
if(val!=B.val) return val<B.val;
return d<B.d;
}
};
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++)
scanf("%d%d%d%d",&pst[i].lef,&pst[i].rig,&pst[i].fal,&pst[i].val);
sort(pst+1,pst+k+1,cmp);
priority_queue< QUEUE > que;
for(int i=1,pos=1;i<=n;i++){
while(pst[pos].lef==i && pos<=k) que.push(QUEUE(pos,pst[pos].val,pst[pos].fal)),pos++;
while(!que.empty() && i>pst[que.top().id].rig) que.pop();
if(!que.empty()) vl[i]=que.top().val,cs[i]=que.top().id;
}
memset(dp,0x3f,sizeof dp);
ll INF=dp[0][0];
dp[0][0]=0;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(dp[i][j]==INF) continue;
if(cs[i]==0){
dp[i+1][j]=min(dp[i][j],dp[i+1][j]);
continue;
}
dp[pst[cs[i]].fal+1][j]=min(dp[pst[cs[i]].fal+1][j],dp[i][j]+pst[cs[i]].val);
if(j<m) dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]);
}
}
ll ans=INF;
for(int i=0;i<=m;i++)
ans=min(ans,dp[n+1][i]);
printf("%lld\n",ans);
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~


0%