写在前面?
\(cb\)什么都不会 \(QAQ\)
T1 括号序列
链接 https://www.luogu.org/problem/U89006
Idea
题目要求为子串, 即连续.
即, 当前面出现一个合法的子串, 后面又有一个合法的,\(Ans=1+1\);
同理, 如果前面有 \(n\)个合法的, 后面又有一个合法的,\(Ans=1+n\)
于是每当遇到一个合法的括号对儿时, 看它前面是否有连续的括号对儿
用 \(stack\)记录, 用 \(stack.tmp\)来记录当前括号作为两个连续合法序列是的分隔时, 当前括号后面有多少合法序列.
某机房 \(dalao\)说他就写了个爆搜, 然后.... 他 \(A\)了....
还有个 \(dalao\)写了个双端队列, 然后.... 他 \(MLE\)了....
- Code
- struct Node{
- int x,tmp;
- }b;
- char a[maxn];
- stack<Node>s;
- signed main(){
- // freopen(File".in","r",stdin);
- // freopen(File".out","w",stdout);
- cin>>a+1;
- int len=strlen(a+1);
- int ans=0,sum=0;
- for(int i=1;i<=len;i++){
- if(a[i]=='(') b.x=1;
- else b.x=2;
- if(s.size()){
- if(s.top().x==1&&b.x==2){
- s.pop();
- if(s.empty()){
- ans+=(sum+1);
- sum++;
- }
- else{
- ans+=(s.top().tmp+1);
- s.top().tmp++;
- }
- }
- else s.push(b);
- }
- else s.push(b);
- }
- printf("%lld",ans);
- return 0;
- }
T2 和数检测
链接 https://www.luogu.org/problem/U89008
Idea
这道题..., 看完题我就用了 \(map\)...
不想再多说些什么了... 代码一看就懂...
只有 \(55pts\)....
\(dalao\)们采取了树状数组, 双指针, 二分等操作写了这道题. 果然, 我就是个 \(cb\)
- Code
- int a[maxn];
- signed main(){
- // freopen(File".in","r",stdin);
- // freopen(File".out","w",stdout);
- int T=read();
- while(T--){
- map<int,int>p;
- int flag=1;
- int n=read(),m=read();
- for(int i=0;i<n;i++){
- a[i]=read();
- if(flag){
- if(p[m-a[i]]==1) flag=0;
- if(p[m-a[i]]!=1){
- p[a[i]]=1;
- p[m-a[i]]=2;
- }
- if(p[a[i]]==2) flag=0;
- }
- }
- if(!flag) puts("1");
- else puts("0");
- }
- return 0;
- }
以下正解
- const int maxx=10000010;
- int n,flag,m;
- int a[maxn],f[maxx];
- int main(){
- // freopen(File".in","r",stdin);
- // freopen(File".out","w",stdout);
- int T=read();
- for(int k=1;k<=T;k++){
- if(k!=1)for(int i=1;i<=n;i++)if(a[i]<=maxx-10)f[a[i]]=0;
- n=read();m=read();flag=0;
- for(int i=1;i<=n;i++){
- a[i]=read();
- if(a[i]<=maxx)f[a[i]]=1;
- }
- if(m<=10000000){
- for(int i=1;i<=n;i++){
- if(a[i]>m)continue;
- if(f[m-a[i]]){flag=1;break;}
- }
- if(flag)puts("1");
- else puts("0");
- }
- else{
- sort(a+1,a+1+n);
- int j=n,w;
- for(int i=1;i<=n;++i){
- if(a[i]>m)break;
- w=m-a[i];
- while(a[j]>w&&j) j--;
- if(!j)break;
- if(a[j]==w){flag=1;break;}
- }
- if(flag)puts("1");
- else puts("0");
- }
- }
- return 0;
- }
T3 与
链接 https://www.luogu.org/problem/U89011
Idea
考场上, 我一直在琢磨样例一咋搞, 结果还是没搞出来. 我太菜了 \(QAQ\)
到最后还是没搞出来,
看看题解的说法
考虑容斥, 则 \(Ans= \displaystyle \sum_{c=0}^{131071} (-1)^c \times f(c)\)
其中, 变量 \(c\)枚举的是子集, 代表需要限制为不符合要求的二进制位 (即这些位一定得一边是 0 一边是 1).\(f(c)\) 指在 \(c\)的限制下的方案数.
由于有一些位一定得一边是 0 一边是 1, 所以这些位为 1 的元素一定得归一边, 可以考虑把它们合并为一个元素. 如果有多个位有限制, 那就用并查集来合并元素. 合并后, 剩余的这些元素可以被任意分到左侧或右侧, 则 \(f(c) = 2^k ? 2\), 其中 \(k\)表示合并后的元素个数, 减去 2 是为了避免有一侧没有分配到元素. 具体的 \(-2\)是因为你在枚举的时候并不能全部枚举完, 要删除两种情况, 就是枚举所有的枚举 0 种的情况
如果 \(n\)个数的某个二进制位全部为 0 或为 1, 则可以直接把这一位去掉. 这样可以避免在后续计算时的特殊讨论.
- Code?
- int n,ans;
- int a[maxn],b[maxn],fa[maxn];
- inline int find(int x){
- if(x==fa[x]) return x;
- return fa[x]=find(fa[x]);
- }
- signed main(){
- // freopen(File".in","r",stdin);
- // freopen(File".out","w",stdout);
- n=read();
- for(int i=1;i<=n;i++) a[i]=read();
- b[0]=1;
- for(int i=1;i<=maxn;i++) b[i]=b[i-1]*2;
- for(int d=0;d<=131071;d++){
- int d1=d,cnt=1,s;// 容斥
- for(int i=1;i<=n;i++) fa[i]=i;
- for(int i=0;i<17;i++,(d1>>=1),s=i)// 枚举 d 的位置
- if(d1&1){
- cnt=-cnt;// 容斥
- int j1=b[i],j2=0,flag=0;//j1 的初始值就是 i 满位的时候
- for(int j=1;j<=n;j++)// 枚举所有的数
- if(!(a[j]&j1)){// 如果这个数没有超过满位的 j1
- flag=1;// 标记一下, 如果是有的数大于现在的限制了, 就直接扩大限制而不必是仅仅跳出次循环了
- if(!j2) j2=find(j);// 向上找到他的父亲节点, 就是在比他位数少的数中有 1 的
- else fa[find(j)]=j2;// 要是之前都没有就把他直接赋成根节点, 这样就会得到好多集合
- }
- if(!flag) break;
- }
- if(s!=17) continue;
- int num=0;
- for(int i=1;i<=n;i++) if(i==find(i)) num++;// 记录集合个数
- ans+=cnt*(b[num]-2);
- }
- printf("%lld",ans);
- return 0;
- }
- \[ The\quad End \]
\[ \texttt{多幸运, 爱你这件事情; 成为我, 今生最对的决定 -《多幸运》} \]
来源: http://www.bubuko.com/infodetail-3216500.html