精华内容
下载资源
问答
  • 优秀的拆分

    2020-11-18 18:59:16
    题目 一般来说,一个正整数可以拆分成若干个正整数的和。例如, 1 = 1, 10 =1 + 2 + 3 + 4 等。...例如, 10 = 8 + 2 = 23 + 21 是一个优秀的拆分。但是, 7 = 4 + 2 + 1 =22 + 21 + 20 就不是一个优

    题目

    一般来说,一个正整数可以拆分成若干个正整数的和。例如, 1 = 1, 10 =1 + 2 + 3 + 4 等。

    对于正整数 𝑛 的一种特定拆分,我们称它为“优秀的”,当且仅当在这种拆分下, 𝑛 被分解为了若干个不同的 2 的正整数次幂。注意, 一个数 𝑥 能被表示成 2 的正整数次幂,当且仅当 𝑥 能通过正整数个 2 相乘在一起得到。

    例如, 10 = 8 + 2 = 23 + 21 是一个优秀的拆分。但是, 7 = 4 + 2 + 1 =22 + 21 + 20 就不是一个优秀的拆分,因为 1 不是 2 的正整数次幂。现在,给定正整数 𝑛,你需要判断这个数的所有拆分中,是否存在优秀的拆分。 若存在, 请你给出具体的拆分方案。

    温馨提示

    freopen别忘了

    代码

    #include<cstdio>
    #include<cmath>
    #include<iostream> 
    using namespace std;
    int main(void)
    {
    	freopen("power.in","r",stdin);
    	freopen("power.out","w",stdout);
    	int n;
    	cin>>n;
    	//二进制做题 
    	if(n%2==1){
    		printf("-1");	
    	}else{
    		for(int i=23;i>=1;i--){//从大到小
    			if(n>=(int)pow(2,i)){
    				cout<<(int)pow(2,i)<<" ";//高位开始
    				n-=(int)pow(2,i);//输出了,就减去他	
    			}
    		}
    	}
    	return 0; 
    }
    

    递归

    #include<cstdio>
    #include<cmath>
    #include<iostream> 
    using namespace std;
    int n;
    //递归(先返回,在输出,从大到小)if(i=1||i=2)return; n==0,回归(return) 
    //递推(从小往高位走) a[1]=a[2]=1从小开始,a[1]+a[2]=a[3] 
    void gui(int n){//从小到大 
    	if(n==0) return;//结束条件
    	int i=1;//i每次从一开始 
    	while(n/2>=i){//从大往小输,n不变,算i成了多少次 
    		i*=2;//2的几次方,刚好比n小着一次方的数 
    	} 
    	cout<<i<<" ";//先输出 
    	return gui(n-i);//再递进 
    }
    int main(void)
    {
    	freopen("power.in","r",stdin);
    	freopen("power.out","w",stdout);
    	int n;
    	cin>>n;
    	if(n%2==1){
    		cout<<-1;
    	}else{
    		gui(n);
    	}
    	return 0; 
    }
    

    谢谢大家

    展开全文
  • 优秀的拆分(位运算)

    2020-11-08 16:35:32
    一般来说,一个正整数可以拆分成若干个正整数的和。 例如,1=1,10=1+2+3+41=1,10=1+2+3+4 等。...例如,10=8+2=23+2110=8+2=23+21 是一个优秀的拆分。 但是,7=4+2+1=22+21+207=4+2+1=22+21+20 就不是

    一般来说,一个正整数可以拆分成若干个正整数的和。

    例如,1=1,10=1+2+3+41=1,10=1+2+3+4 等。

    对于正整数 nn 的一种特定拆分,我们称它为“优秀的”,当且仅当在这种拆分下,nn 被分解为了若干个不同的 22 的正整数次幂。

    注意,一个数 xx 能被表示成 22 的正整数次幂,当且仅当 xx 能通过正整数个 22 相乘在一起得到。

    例如,10=8+2=23+2110=8+2=23+21 是一个优秀的拆分。

    但是,7=4+2+1=22+21+207=4+2+1=22+21+20 就不是一个优秀的拆分,因为 11 不是 22 的正整数次幂。

    现在,给定正整数 nn,你需要判断这个数的所有拆分中,是否存在优秀的拆分。

    若存在,请你给出具体的拆分方案。

    本题暂时采用AcWing数据。

    输入格式
    输入文件只有一行,一个正整数 nn,代表需要判断的数。

    输出格式
    如果这个数的所有拆分中,存在优秀的拆分。

    那么,你需要从大到小输出这个拆分中的每一个数,相邻两个数之间用一个空格隔开。

    可以证明,在规定了拆分数字的顺序后,该拆分方案是唯一的。

    若不存在优秀的拆分,输出 “-1”(不包含双引号)。

    数据范围
    对于 20%20% 的数据,n≤10n≤10。
    对于另外 20%20% 的数据,保证 nn 为奇数。
    对于另外 20%20% 的数据,保证 nn 为 22 的正整数次幂。
    对于 80%80% 的数据,n≤1024n≤1024。
    对于 100%100% 的数据,1≤n≤1×1071≤n≤1×107。

    输入样例1:
    6
    输出样例1:
    4 2
    样例1解释
    6=4+2=22+216=4+2=22+21 是一个优秀的拆分。
    注意,6=2+2+26=2+2+2 不是一个优秀的拆分,因为拆分成的 33 个数不满足每个数互不相同。
    输入样例2:
    7
    输出样例2:
    -1

    #include <iostream>
    
    using namespace std;
    
    int main()
    {
        int n;
        cin >> n;
        if (n % 2) puts("-1");
        else
        {
            for (int i = 25; i >= 0; i -- )
                if (n >> i & 1)//看看那一位是否为1
                    printf("%d ", 1 << i);
            puts("");
        }
        return 0;
    }
    
    展开全文
  • [Noi2016]优秀的拆分

    2017-09-24 14:50:00
    [Noi2016]优秀的拆分 题目 如果一个字符串可以被拆分为 AABB的形式,其中 AA 和 BB 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。例如,对于字符串 aabaabaa,如果令 A=aab,B=a,我们就找到了这个字符...

    [Noi2016]优秀的拆分

    题目

    如果一个字符串可以被拆分为 AABB的形式,其中 AA 和 BB 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。例如,对于字符串 aabaabaa,如果令 A=aab,B=a,我们就找到了这个字符串拆分成 AABB的一种方式。一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 A=a,B=baa,也可以用 AABB表示出上述字符串;但是,字符串 abaabaa 就没有优秀的拆分。现在给出一个长度为 n 的字符串 S,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续的一段。
     
    以下事项需要注意:
     
    出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。在一个拆分中,允许出现 A=B。例如 cccc 存在拆分 A=B=c。字符串本身也是它的一个子串。

    INPUT

    每个输入文件包含多组数据。输入文件的第一行只有一个整数 T,表示数据的组数。保证 1≤T≤10。接下来 T 行,每行包含一个仅由英文小写字母构成的字符串 S,意义如题所述。N30000

    OUTPUT

    输出 T 行,每行包含一个整数,表示字符串 S 所有子串的所有拆分中,总共有多少个是优秀的拆分。

    SAMPLE

    INPUT

    4

    aabbbb

    cccccc

    aabaabaabaa

    bbaabaababaaba

    OUTPUT

    3

    5

    4

    7

    解题报告

    $SA$的力量= =

    显然我们不用处理什么$AABB$,只需要去处理所有$AA$形式,再去统计答案即可

    设$pre[i]$表示以$i$这个字符开头的$AA$型子串的数目

    设$nxt[i]$表示以$i$这个字符结尾的$AA$型子串的数目

    则答案$ans=\sum _{i=1}^{n-1}pre[i+1]\times nxt[i]$

    所以问题就转化成了求$AA$型的子串

    我们可以枚举找的$AA$型子串长度的一半,去判断$lcp$与$lcs$

    枚举$i=k*len$,$j=i+len$

    设$x=lcp(suffix(i),suffix(j))$,$y=lcs(pre(i-1),pre(j-1))$

    若$x+y\geqslant len$,那么我们就找到了$x+y-len+1$个长度为$2\times len$的$AA$串

    差分一下就$GG$了

      1 #include<iostream>
      2 #include<cstring>
      3 #include<cstdio>
      4 using namespace std;
      5 #define mem(x) memset((x),0,sizeof((x)))
      6 struct SA{
      7     char s[60005];
      8     int n,m;
      9     int t1[60005],t2[60005],t3[60005],buc[60005];
     10     int sa[60005],Rank[60005],height[60005],mn[60005][20];
     11     SA(){}
     12     inline void clear(){
     13         m=130;
     14         mem(t1),mem(t2),mem(t3),mem(buc),mem(sa),mem(Rank),mem(height),mem(mn);
     15     }
     16     inline void init(){
     17         scanf("%s",s+1);
     18         n=strlen(s+1);
     19     }
     20     inline void Suffix(){
     21         int i,j,k(0),p(0),*x(t1),*y(t2),*t;
     22         for(i=0;i<=m;++i)buc[i]=0;
     23         for(i=1;i<=n;++i)++buc[x[i]=s[i]];
     24         for(i=1;i<=m;++i)buc[i]+=buc[i-1];
     25         for(i=n;i>=1;--i)sa[buc[x[i]]--]=i;
     26         for(j=1;p<n;j<<=1,m=p){
     27             for(p=0,i=n-j+1;i<=n;++i)y[++p]=i;
     28             for(i=1;i<=n;++i)
     29                 if(sa[i]>j)
     30                     y[++p]=sa[i]-j;
     31             for(i=0;i<=m;++i)buc[i]=0;
     32             for(i=1;i<=n;++i)t3[i]=x[y[i]];
     33             for(i=1;i<=n;++i)++buc[t3[i]];
     34             for(i=1;i<=m;++i)buc[i]+=buc[i-1];
     35             for(i=n;i>=1;--i)sa[buc[t3[i]]--]=y[i];
     36             for(t=x,x=y,y=t,x[sa[1]]=1,p=1,i=2;i<=n;++i)
     37                 x[sa[i]]=((y[sa[i]]==y[sa[i-1]])&&(y[sa[i]+j]==y[sa[i-1]+j]))?p:++p;
     38         }
     39         for(i=1;i<=n;++i)Rank[sa[i]]=i;
     40         for(i=1;i<=n;height[Rank[i++]]=k)
     41             for(k?--k:0,j=sa[Rank[i]-1];s[i+k]==s[j+k];++k);
     42     }
     43     inline void ST(){
     44         for(int i=1;i<=n;++i)mn[i][0]=height[i];
     45         for(int i=1;(1<<i)<=n;++i)
     46             for(int j=1;j+(1<<i)-1<=n;++j)
     47                 mn[j][i]=min(mn[j][i-1],mn[j+(1<<i-1)][i-1]);
     48     }
     49     inline int lcp(int x,int y){
     50         if(y>n)return 0;
     51         x=Rank[x],y=Rank[y];
     52         if(x>y)swap(x,y);
     53         ++x;
     54         int k(0),len(y-x+1);
     55         while((1<<k)<=len)++k;
     56         --k;
     57         return min(mn[x][k],mn[y-(1<<k)+1][k]);
     58     }
     59     inline void work(){
     60         Suffix();
     61         ST();
     62     }
     63 }a,b;
     64 inline void inv(){
     65     b.n=a.n;
     66     for(int i=1;i<=a.n;++i)
     67         b.s[i]=a.s[a.n-i+1];
     68 }
     69 typedef long long L;
     70 L ans;
     71 L cnt1[30005],cnt2[30005];
     72 inline void doit(){
     73     ans=0;
     74     mem(cnt1),mem(cnt2);
     75     int edge(a.n>>1);
     76     for(int l=1;l<=edge;++l)
     77         for(int i=l,j=l<<1;j<=a.n;i+=l,j+=l){
     78             int x(min(a.lcp(i,j),l));
     79             int y(min(b.lcp(a.n-(i-1)+1,a.n-(j-1)+1),l-1));
     80             int tmp(x+y-l+1);
     81             if(x+y>=l){
     82                 ++cnt1[i-y];--cnt1[i-y+tmp];
     83                 ++cnt2[j+x-tmp];--cnt2[j+x];
     84             }
     85         }
     86     for(int i=1;i<=a.n;++i)
     87         cnt1[i]+=cnt1[i-1],cnt2[i]+=cnt2[i-1];
     88     for(int i=1;i<=a.n;++i)
     89         ans+=cnt1[i+1]*cnt2[i];
     90     printf("%lld\n",ans);
     91 }
     92 int main(){
     93     int T;
     94     scanf("%d",&T);
     95     while(T--){
     96         a.clear(),b.clear();
     97         a.init();
     98         a.work();
     99         inv();
    100         b.work();
    101         doit();
    102     }
    103 }
    View Code

     

    转载于:https://www.cnblogs.com/hzoi-mafia/p/7587221.html

    展开全文
  • [NOI 2016]优秀的拆分

    2018-07-06 21:45:00
    给你一个长度为 \(n\) 的只含小写字母的字符串 \(S\) ,计算其子串有多少优秀的拆分。 如果一个字符串能被表示成 \(AABB\) 的形式,其中 \(A,B\) 非空,那么称 \(AABB\) 是一个优秀的拆分。一个子串可能有多个优秀的...

    Description

    题库链接

    给你一个长度为 \(n\) 的只含小写字母的字符串 \(S\) ,计算其子串有多少优秀的拆分。

    如果一个字符串能被表示成 \(AABB\) 的形式,其中 \(A,B\) 非空,那么称 \(AABB\) 是一个优秀的拆分。一个子串可能有多个优秀的拆分。

    多组询问,询问组数 \(T\)

    \(1\leq n\leq 30000,1\leq T\leq 10\)

    Solution

    会用这题的方法的话,应该不难想。

    如果记 \(s_{1_i}\) 为以 \(i\) 结尾的 \(AA\) 串个数,记 \(s_{2_i}\) 为以 \(i\) 开头的 \(BB\) 串个数。

    那么答案就是 \(\sum\limits_{i=2}^n s_{1_{i-1}}\times s_{2_i}\)

    考虑如何求 \(s_1\)\(s_2\)

    我们可以枚举 \(A\) 的长度 \(l\) ,用 \(i,i+l\) 这两个点可以将所有的长度为 \(2l\)\(AA\) 并且同一个长度为 \(2l\)\(AA\) 不会被不同的一组 \(i,i+l\) 固定。

    这样对于每一组 \(i,i+l\) ,我们设法去计算它所固定的长度为 \(2l\)\(AA\)

    可以求出 \(i,i+l\) 的最长公共前缀 \(x\)\(i,i+l\) 的最长公共后缀 \(y\) ,如果 \(x+y\geq l\) ,那么存在长度为 \(2l\)\(AA\) 经过 \(i,i+l\)

    求出区间左端点 \(L=\max\{i-x+1, i-l+1\}\) ,右端点 \(R=\min\{i-l+y+1, i\}\)

    显然这一段区间都是能够对答案产生贡献的,差分一下即可。

    下发的几个样例字符串长度都是递增的...大样例过了自信 AC ,结果因为没清空数组 wa 成苟

    Code

    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int N = 30000+5;
    
    int bin[35], lgn[N], t, n, m, x[N<<1], y[N<<1], c[N];
    ll s1[N], s2[N];
    
    struct SA {
        char ch[N];
        int sa[N], rk[N], height[N], f[30][N];
        void get() {
            for (int i = 1; i <= n*2; i++) x[i] = y[i] = 0;
            for (int i = 1; i <= m; i++) c[i] = 0;
            for (int i = 1; i <= n; i++) c[x[i] = ch[i]]++; 
            for (int i = 2; i <= m; i++) c[i] += c[i-1];
            for (int i = n; i >= 1; i--) sa[c[x[i]]--] = i;
            for (int k = 1; k <= n; k <<= 1) {
                int num = 0;
                for (int i = n-k+1; i <= n; i++) y[++num] = i;
                for (int i = 1; i <= n; i++) if (sa[i] > k) y[++num] = sa[i]-k;
                for (int i = 1; i <= m; i++) c[i] = 0;
                for (int i = 1; i <= n; i++) c[x[i]]++;
                for (int i = 2; i <= m; i++) c[i] += c[i-1];
                for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];
                swap(x, y); x[sa[1]] = num = 1;
                for (int i = 2; i <= n; i++)
                    x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k]) ? num : ++num;
                if ((m = num) == n) break;
            }
            for (int i = 1; i <= n; i++) rk[sa[i]] = i;
            for (int i = 1, k = 0; i <= n; i++) {
                if (rk[i] == 1) continue;
                if (k) --k; int j = sa[rk[i]-1];
                while (i+k <= n && j+k <= n && ch[i+k] == ch[j+k]) ++k;
                height[rk[i]] = k;
            }
        }
        void rmq() {
            int t = lgn[n];
            for (int i = 1; i <= n; i++) f[0][i] = height[i];
            for (int i = 1; i <= t; i++)
                for (int j = 1; j+bin[i-1] <= n; j++)
                    f[i][j] = min(f[i-1][j], f[i-1][j+bin[i-1]]);
        }
        int lcp(int a, int b) {
            a = a > n ? 0 : rk[a], b = b > n ? 0 : rk[b];
            if (a > b) swap(a, b); ++a;
            int t = lgn[b-a+1];
            return min(f[t][a], f[t][b-bin[t]+1]);
        }
    }b, f;
    void work() {
        bin[0] = 1; for (int i = 1; i <= 25; i++) bin[i] = (bin[i-1]<<1);
        lgn[0] = -1; for (int i = 1; i < N; i++) lgn[i] = lgn[i>>1]+1;
        scanf("%d", &t);
        while (t--) {
            memset(s1, 0, sizeof(s1)), memset(s2 ,0, sizeof(s2));
            scanf("%s", f.ch+1); n = strlen(f.ch+1);
            for (int i = 1; i <= n; i++) b.ch[n-i+1] = f.ch[i];
            m = 255; f.get(); f.rmq(); m = 255; b.get(); b.rmq();
            for (int l = 1; l <= n; l++)
                for (int i = 1; i+l <= n; i += l) {
                    int x = b.lcp(n-i+1, n-(i+l)+1), y = f.lcp(i+1, i+l+1);
                    if (x+y < l) continue;
                    int L = max(i-x+1, i-l+1), R = min(i-l+y+1, i);
                    if (L > R) continue;
                    s1[L+l*2-1]++, s1[R+l*2]--;
                    s2[L]++, s2[R+1]--;
                }
            for (int i = 2; i <= n; i++) s1[i] += s1[i-1], s2[i] += s2[i-1];
            ll ans = 0;
            for (int i = 2; i <= n; i++) ans += 1ll*s1[i-1]*s2[i];
            printf("%lld\n", ans);
        }
    }
    int main() {work(); return 0; }

    转载于:https://www.cnblogs.com/NaVi-Awson/p/9275608.html

    展开全文
  • 【NOI 2016】优秀的拆分 Problem Description 如果一个字符串可以被拆分为 \(AABB\) 的形式,其中 \(A\) 和 \(B\) 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。 例如,对于字符串 ...
  • [NOI2016]优秀的拆分

    千次阅读 2020-01-20 20:33:34
    优秀的拆分 题解 看到题目,数据范围有点怪异。 对于95%的数据, 对于100%的数据,。 意思是只有5分是正解。 好吧,95pts的还是很好想的,我们可以维护出a,b两个数组,代表以i为结尾的AA型字符串,代表从i开始...
  • 【NOI2016】优秀的拆分

    2017-07-17 20:51:00
    题目描述 如果一个字符串可以被拆分为 AABB 的形式,其中 A和 B是任意非空...一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 A=a,B=baa,也可以用 AABB表示出上述字符串;但是,字符串 ...
  • 如果一个字符串可以被拆分为 AABB 的形式,其中 A和 B是任意...一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 A=a,B=baa,也可以用 AABB表示出上述字符串;但是,字符串 abaabaa 就没有
  • 题目描述如果一个字符串可以被拆分为 AABB 的形式,其中 A和 ...一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 A=a,B=baa,也可以用 AABB表示出上述字符串;但是,字符串 abaabaa 就没有优
  • NOI2016 优秀的拆分 后缀数组

    千次阅读 2017-01-29 14:52:32
    题目链接:洛谷点我:-) UOJ点我:-) 题目描述: 如果一个字符串可以被拆分为 AABB 的形式,其中 A和 B是任意非空...一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 A=a,B=baa,也可以用 A
  • 题目描述 如果一个字符串可以被拆分为 AABB的形式,其中 A和 B...一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 A=a,B=baa,也可以用 AABB表示出上述字符串;但是,字符串 abaabaa 就没...
  • luogu-P7071-优秀的拆分

    2020-12-01 11:34:01
    题目连接 该题是CSP-J2-2020-T1 题目大意 输入一个整数,求他的二...//T1-优秀的拆分 //CSP-J2-2020 //二进制基础 #include<bits/stdc++.h> using namespace std; int a[110],n; int main(){ cin>>n
  • NOI2016 优秀的拆分(图解)

    千次阅读 2017-12-27 18:53:35
    如果一个字符串可以被拆分为 AABB 的形式,其中 A和 B是任意...一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 A=a,B=baa,也可以用 AABB表示出上述字符串;但是,字符串 abaabaa 就没有优
  • 题目 如果一个字符串可以被拆分为 \text{AABB}AABB 的形式,其中 \text{A}A 和 \text{B}B 是任意非空字符串,则我们称该字符串的这种拆分...一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。 比如我们令
  • 优秀的拆分(power)2020 CSP-J-01【题目描述】 般来说,一个正整数可以拆分成若干个正整数的和。例如,1=1,10=1+2+3+4等。对于正整数n的一种特定拆分,我们称它为“优秀的",当且仅当在这种拆分下,n被分解为了...
  • BZOJ4650: [Noi2016]优秀的拆分 Description 如果一个字符串可以被拆分为 AABBAABB 的形式,其中 AA 和 BB 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。 例如,对于字符串 aabaabaa,如果令 A=aab...
  • 如果一个字符串可以被拆分为 AABBAABB 的形式,其中 AA 和 BB 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。...一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令 A=aA=a,B=...
  • [NOI2016]优秀的拆分 题目描述 如果一个字符串可以被拆分为 \(AABB\) 的形式,其中 A和 B是任意非空字符串,则我们称该字符串的这种拆分是优秀的。 例如,对于字符串 \(aabaabaa\) ,如果令 \(A=aab\) , \(B=a\) ,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 726
精华内容 290
关键字:

优秀的拆分