NOWCODER 2020 NOIP #4
T1:
题目大意:
给出一个长度为 $26$ 的序列(不妨记作 $\{w_i\}$ ),其中第 $i$ 个数字表示字母 'a'+i-1
的属性。属性共分为 $A,N,V$ 三种。 若 $w_i \& 1 = 1$,表示 $w_i$ 可以被当成 $A$ 来使用;若 $w_i \& 2 = 1$ ,表示 $w_i$ 可以被当成 $N$ 来使用。若 $w_i \& 4=1$ ,表示 $w_i$ 可以被当作 $V$ 来使用。接下来,给出一个序列 $S$ 。规定 $S$ 合法,当且仅当 $S$ 可以被拆分成以下形式:
$$
S ::= NP_1+V+NP_2
$$
其中, $NP$ 可以是一个 $N$ ,也可以是 $A+N$ ,也可以是$NP’+NP’‘$ (两个合法的 $NP$ 的拼接) 。
想法:
先来考虑 $V$ :
显而易见的是,因为在 $NP$ 中不能出现 $V$ ,所以 $w_i=4$ 的个数最多只有一个。
第二,因为 $NP$ 中的 $A$ 均是以前缀形式出现的,所以 $NP$ 的最后一个部分必定只能是 $N$ 。
因此,我们只需要去统计两个东西:
-
$V$ 的左侧相邻是否为 $N$ 。
-
$S$ 的最后一个是否为 $N$ 。
-
是否有多个固定的 $S$ 。
然后统计答案即可。
代码:
#include <iostream>
#include <string.h>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int T,sign[26],n;char s[N];
bool w[N];
inline void solve()
{
memset(w,false,sizeof(w));
for(int i = 0;i < 26;i++)
scanf("%d",&sign[i]);
scanf("%s",s);n = strlen(s);
for(int i = 0;i < n;i++)
{
if(sign[s[i]-'a'] & 2) w[i] = true;
if(sign[s[i]-'a'] == 4) break;
}
if(!(sign[s[n-1]-'a']&2))
{
printf("No\n");
return ;
}
bool is_true = false;
for(int i = n - 2;i >= 1;i--)
{
if((sign[s[i]-'a'] & 4) && w[i-1])
{
is_true = true;
break;
}
if(sign[s[i]-'a'] == 4) break;
}
if(is_true) printf("Yes\n");
else printf("No\n");
return ;
}
int main()
{
scanf("%d",&T);
while(T--)
solve();
return 0;
}
T2:
题目大意:
有 $n$ 个球和 $n$ 个洞。每个洞都可以装下无数个球。
会进行 $m$ 次操作,操作分别有以下几种:
push x,y,z
:把 $x$ 个颜色为 $y$ 的球放进 $z$ 这个洞。
pop x,y
:把洞 $y$ 中的最上面 $x$ 个球取出来。
put u,v
:把洞 $u$ 中的全部球取出来,放进洞 $v$ 。
对于每次 pop
操作,输出最后一个取出的球的颜色。
想法:
基本想法:
定义结构体 kuai{int col,num;}
存储:把每一次压入的所有球当成一块, col
存储颜色,num
储存这一段连续相同颜色的球的的长度。每次进栈,出栈均暴力解决,期望得分 $50 \%$ 。
#include <iostream>
#include <string.h>
#include <cstring>
#include <stack>
using namespace std;
typedef pair<int,int> pii;//first 表示颜色,second 表示数量
const int N = 2e5 + 10;
stack<pii> bucs[N];
int n,m,x,y,z;
char sign[5];
namespace solve
{
inline void control()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i++)
{
scanf("%s",sign);
if(sign[2] == 's')
{
scanf("%d%d%d",&x,&y,&z);
bucs[z].push({y,x});
}
if(sign[2] == 'p')
{
scanf("%d%d",&x,&y);
int last = 0;
while(x > bucs[y].top().second)//出栈,判断剩余要取的个数是否大于当前块的个数
{
last = bucs[y].top().first;
x -= bucs[y].top().second;
bucs[y].pop();
}
if(x == 0) printf("%d\n",last);
else{bucs[y].top().second -= x;x = 0;printf("%d\n",bucs[y].top().first);}
//进行检查,若还有剩余要取的那么更新栈顶的块的数量。
}
if(sign[2] == 't')
{
scanf("%d%d",&x,&y);
while(!bucs[x].empty())
{
pii top = bucs[x].top();
bucs[y].push(top);
bucs[x].pop();
}
}
}
return ;
}
}
int main()
{
solve::control();
return 0;
}
优化:
可以发现,现在的关键问题是 $1$ 操作和 $3$ 操作需要的操作次数太高:如果暴力取,那么每次的时间复杂度均是块数,也就是最多 $\Theta (n)$ 。那么结合询问的次数,可以得到总体时间复杂度应为 $\Theta (nm)$ 。太高不能接受,考虑优化。我们考虑使用一种可以在不改变内部元素相对位置的情况下改变整段位置的数据结构。这里可以使用双向链表维护:开 $n$ 个双向链表,表示 $n$ 个栈。对于每一个 $1$ 操作,直接在链表 $z$ 的尾部插入块 $\{y,x\}$ ,对于每一个 $3$ 操作,把 $x$ 的链表尾接在 $y$ 的链表尾,然后归零 $x$ 链表。这样就可以了。
#include <iostream>
#include <string.h>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
struct kuai{int col,num,node[2];}w[N];//结构体,内容如上所示,node[0/1]表示这个节点的两个指针(指前指后)
int n,m,x,y,z,hh[N],tt[N],idx; //hh[i],tt[i] 表示第 i 个链表的头和尾。
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i++)
{
char ch[6];
scanf("%s",&ch);//标记
if(ch[2] == 's')
{
scanf("%d%d%d",&x,&y,&z);
w[++idx] = {y,x,hh[z],0};//直接尾部插入
if(hh[z])
w[hh[z]].node[0]?(w[hh[z]].node[1]=idx):(w[hh[z]].node[0]=idx);//尽量用小的下标
else tt[z] = idx;
hh[z] = idx;
}else if(ch[2] == 'p')
{
scanf("%d%d",&x,&y);
while(w[hh[y]].num < x)//判断条件
{
x -= w[hh[y]].num;//减去代价
int tmp = w[hh[y]].node[0]|w[hh[y]].node[1];
if(tmp != 0)//
w[tmp].node[0] == hh[y]?(w[tmp].node[0]=0):(w[tmp].node[1]=0);
hh[y] = tmp;//
}
w[hh[y]].num -= x;
printf("%d\n",w[hh[y]].col);
}else
{
scanf("%d%d",&x,&y);
if(!hh[x]) continue;
if(hh[y])
{
w[hh[y]].node[0]?(w[hh[y]].node[1]=hh[x]):(w[hh[y]].node[0]=hh[x]);
w[hh[x]].node[0]?(w[hh[x]].node[1]=hh[y]):(w[hh[x]].node[0]=hh[y]);
}else tt[y] = hh[x];
hh[y] = tt[x];
hh[x] = tt[x] = 0;
}
}
return 0;
}
T3:
简单化简,可以得到以下信息:
$$
f(S) = \sum_{T \subseteq S}\big({\rm fib}^2(\sum_{s \in T}s)\big) = \sum_{T \subseteq S}\big[\frac{1}{\sqrt{5}} \times {\big(} K {\big)}\big]^2
$$
其中,$K$ 是斐波那契通项式,根据要求的项 ,可以得到:
$$
\because 项数 = \sum_{s \in T}s\\
\therefore K = \{(\frac{1+\sqrt 5}{2}) ^ {\sum_{s \in T} s} - (\frac{1-\sqrt5}{2})^{\sum_{s \in T}s}\}^2\\
\therefore 整体的式子应当为:\sum_{T \subseteq S}\{\frac{1}{\sqrt5} \times {\big [} \big( \frac{1+\sqrt 5}{2}\big)^{\sum_{s \in T}} - \big(\frac{1-\sqrt5}{2} \big)^{\sum_{s \in T}} {\big ]}\}^2\\
我们不妨设中括号中前一项为 a^{k’} ,后一项为b^{k’‘},则原式=\sum_{T \subseteq S}\{{\frac{1}{5} \times \big[a^{k’ - b^{k’‘}}\big]^2}\}\\
利用完全平方公式可以化开,得到:\sum_{T \subseteq S} {\big \{} \frac{1}{5} \times {\big [} a^{2 \times k’} + b ^ {2 \times k’‘} - 2 \times a^{k’} \times b^{k’‘} {\big ]} {\big \}} \\
$$
此时,我们发现如果仅仅使用简单的变化规律,这个式子会很难化简。所以我们不妨利用 $T \subseteq S$ 的性质,求出 $T’ = T \cup S$ ,那么我们可以发现,对于最后的答案,有 $s_i \in T$ 的贡献为 $s_i$ ,$s_i \in T’$ 的贡献本身是 $0$ ,但是这东西放在指数位上,所以实际贡献为 $1$ 。那么,可以得到对于每一个 $s_i \in S$ ,若要枚举集合,则总贡献应为 $s_i+1$ 。那么,总共的式子应为:
$$
\prod_{i = 1} ^ {|S|} (s_i + 1) - 1
$$
可以类似于使用 约数之和 那道题的思路进行思考。乘法原理,一个是 $s_i \in T$ 的,一个是 $s_i \in T’$ 的。最后减去一个不符条件的空集即可。