只做了前 $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 #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 #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+=1l l*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+=1l l*dis[id[pos]].c*dis[id[pos]].a, d-=dis[id[pos]].a, dis[id[pos]].a=0 , pos++; else tot+=1l l*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 #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+=1l l*(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 #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 #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 ,欢迎提问~