ABC066

[ABC066B] ss

题面翻译

如果某个串可以由两个一样的串前后连接得到，我们就称之为“偶串”。比如说“xyzxyz”和“aaaaaa”是偶串，而“ababab”和“xyzxy”则不是偶串。

输入一个字符串S，查找可以通过从S的末尾删除一个或多个字符获得的最长偶数字符串的长度。确保给定输入存在这样的非空字符串。

输出这个非空字符串的长度

题目描述

同じ文字列を $ 2 $ つ並べてできる文字列のことを偶文字列と呼ぶことにします。 例えば、 xyzxyz や aaaaaa は偶文字列ですが、ababab や xyzxy は偶文字列ではありません。

アルファベットの小文字からなる偶文字列 $ S $ が与えられます。 $ S $ の末尾の文字を $ 1 $ 文字以上消して作れる偶文字列のうち、最も長い偶文字列の長さを求めて下さい。 与えられる入力では、条件を満たす $ 1 $ 文字以上の文字列が存在することが保証されています。

输入格式

入力は以下の形式で標準入力から与えられる。

$ S $

输出格式

答えとなる文字列の長さを出力せよ。

样例 #1

样例输入 #1

abaababaab

样例输出 #1

6

样例 #2

样例输入 #2

xxxx

样例输出 #2

2

样例 #3

样例输入 #3

abcabcabcabc

样例输出 #3

6

样例 #4

样例输入 #4

akasakaakasakasakaakas

样例输出 #4

14

提示

制約

• $ 2  |S|  200 $
• $ S $ は小文字のアルファベットのみからなる偶文字列である。
• $ S $ に対して、条件を満たす $ 1 $ 文字以上の文字列が存在する。

Sample Explanation 1

abaababaab は偶文字列ですが、 $ 1 $ 文字も消していないので条件を満たしません。 abaababaa は偶文字列ではありません。 abaababa は偶文字列ではありません。 abaabab は偶文字列ではありません。 abaaba は偶文字列です。よって、答えは abaaba の長さである $ 6 $ です。

Sample Explanation 2

xxx は偶文字列ではありません。 xx は偶文字列です。

Sample Explanation 3

条件を満たす文字列は abcabc なので、答えは $ 6 $ です。

Sample Explanation 4

条件を満たす文字列は akasakaakasaka なので、答えは $ 14 $ です。

思路

我们直接每次删去一个字符，暴力判断是否是偶字符串即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=3e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin>>s;
    int n=s.length();
    int flag=0;
    while(1){
        n--;
        if(n%2==0){
            if(n==2&&s[0]==s[1]){
                cout<<2;
                return 0;
            }
            for(int i=0,j=n/2;i<=n/2-1,j<=n-1;){
                if(s[i]==s[j]){
                    i++;
                    j++;
                    if(i==n/2-1){
                        flag=n;
                        break;
                    }
                }
                else break;
            }
        }
        if(flag){
            cout<<flag;
            return 0;
        }
    }
    return 0;
}

使用STL的写法

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=14e4;
string s;
int num;
int main()
{
    cin>>s;
    for(int i=s.length()-2;i>=0;i-=2)
    {
        if(s.substr(0,i>>1)==s.substr(i>>1,i>>1))//STL大法
        {
            num=i;//满足直接退出循环并输出
            break;
        }
    }
    cout<<num;
    return 0;
}

[ABC066C] pushpush

题面翻译

输入N，后面有N个数，代表:\(a1,a2,a3, ... ,aN\)，我们将会对\(b\)这个空序列进行N个操作

第i个操作进行如下处理：

• 在b序列的末尾加入a[i]

• 翻转b序列

感谢@RioBlu的翻译

题目描述

長さ $ n $ の数列 $ a_1, ... , a_n $ が与えられます。 空の数列 $ b $ に対して、以下の操作を $ n $ 回行うことを考えます。

$ i $ 回目には

1. 数列の $ i $ 番目の要素 $ a_i $ を $ b $ の末尾に追加する。
2. $ b $ を逆向きに並び替える。

この操作をしてできる数列 $ b $ を求めて下さい。

输入格式

入力は以下の形式で標準入力から与えられる。

$ n $ $ a_1 $ $ a_2 $ $ ... $ $ a_n $

输出格式

$ n $ 個の整数を空白区切りで $ 1 $ 行に出力せよ。 $ i $ 番目には、 $ b_i $ を出力せよ。

样例 #1

样例输入 #1

4
1 2 3 4

样例输出 #1

4 2 1 3

样例 #2

样例输入 #2

3
1 2 3

样例输出 #2

3 1 2

样例 #3

样例输入 #3

1
1000000000

样例输出 #3

1000000000

样例 #4

样例输入 #4

6
0 6 7 6 7 0

样例输出 #4

0 6 6 0 7 7

提示

制約

• $ 1  n  2 10^5 $
• $ 0  a_i  10^9 $
• $ n,a_i $ は整数である。

Sample Explanation 1

$ 1 $ 回目の操作 $ 1 $ の後、 $ b $ は $ 1 $ となります。 $ 1 $ 回目の操作 $ 2 $ の後、 $ b $ は $ 1 $ となります。 $ 2 $ 回目の操作 $ 1 $ の後、 $ b $ は $ 1, 2 $ となります。 $ 2 $ 回目の操作 $ 2 $ の後、 $ b $ は $ 2, 1 $ となります。 $ 3 $ 回目の操作 $ 1 $ の後、 $ b $ は $ 2, 1, 3 $ となります。 $ 3 $ 回目の操作 $ 2 $ の後、 $ b $ は $ 3, 1, 2 $ となります。 $ 4 $ 回目の操作 $ 1 $ の後、 $ b $ は $ 3, 1, 2, 4 $ となります。 $ 4 $ 回目の操作 $ 2 $ の後、 $ b $ は $ 4, 2, 1, 3 $ となります。 よって、答えは 4 2 1 3 です。

Sample Explanation 2

出力例 1 の説明の通り、 $ 3 $ 回目の操作 $ 2 $ の後、 $ b $ は $ 3, 1, 2 $ となるので、 答えは 3 1 2 です。

思路

可以利用deque来实现。

反转本质上可以转化为数字的前后插入问题

比如说，第一次是向最后插入，反转后第二次就是在最前插入

所以用deque来存储数字（特别好用）,需要注意考虑最后是奇数串还是偶数串，注意输出顺序。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=3e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
ll a[MAXN],q1[MAXN],q2[MAXN];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;cin>>n;
    deque<ll> d;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        //判断是前还是后输入
        if(i&1){
            d.push_back(a[i]);
        }
        else d.push_front(a[i]);
    }
    if(n&1){//从后输出
        while(d.size()){
            cout<<d.back()<<" ";
            d.pop_back();
        }
    }
    else{//从前输出
        while(d.size()){
            cout<<d.front()<<" ";
            d.pop_front();
        }
    }
    return 0;
}

[ABC066D] 11

题面翻译

长度为n+1的序列a.其中[1..n]每个数都至少出现一次. （n<=1e5）,对每个k从1到n，询问长度为k的不同的子序列有多少个?

题目描述

$ 1,...,n $ の $ n $ 個の整数からなる長さ $ n+1 $ の数列 $ a_1,a_2,...,a_{n+1} $ が与えられます。 この数列には $ 1,...,n $ のどの整数もかならず $ 1 $ 回以上出現することが分かっています。

$ k=1,...,n+1 $ のそれぞれについて、与えられた数列の長さ $ k $ の（連続とは限らない）部分列の個数を求め、 $ 10^9+7 $ で割ったあまりを出力して下さい。

输入格式

入力は以下の形式で標準入力から与えられる。

$ n $ $ a_1 $ $ a_2 $ ... $ a_{n+1} $

输出格式

答えを $ n+1 $ 行に出力せよ。 $ k $ 行目には、長さ $ k $ の部分列の個数を $ 10^9+7 $ で割ったあまりを出力せよ。

样例 #1

样例输入 #1

3
1 2 1 3

样例输出 #1

3
5
4
1

样例 #2

样例输入 #2

1
1 1

样例输出 #2

1
1

样例 #3

样例输入 #3

32
29 19 7 10 26 32 27 4 11 20 2 8 16 23 5 14 6 12 17 22 18 30 28 24 15 1 25 3 13 21 19 31 9

样例输出 #3

32
525
5453
40919
237336
1107568
4272048
13884156
38567100
92561040
193536720
354817320
573166440
818809200
37158313
166803103
166803103
37158313
818809200
573166440
354817320
193536720
92561040
38567100
13884156
4272048
1107568
237336
40920
5456
528
33
1

提示

注意

• $ 2 $ つの部分列が数列として同じであれば、元の数列での位置が異なっていたとしても、$ 1 $ 通りと数えます。
• 数列 $ a $ の長さ $ k $ の部分列とは、$ a $ の要素のうち $ k $ 個を選んで、 それらを順番を変えずに取り出して並べた数列のことを指します。 例えば、数列 $ 1,2,3,4,5 $ の長さ $ 3 $ の部分列には、 $ 1,3,5 $ や $ 1,2,3 $ などがあります。 一方で、$ 3,1,2 $ や $ 1,10,100 $ はこの数列の部分列ではありません。

制約

• $ 1  n  10^5 $
• $ 1  a_i  n $
• $ 1,...,n $ のどの整数も必ず数列に出現する。
• $ n,a_i $ は整数である。

Sample Explanation 1

長さ $ 1 $ の部分列は $ 1 \(、\) 2 \(、\) 3 $ の $ 3 $ 通りです。 長さ $ 2 $ の部分列は $ 1,1 \(、\) 1,2 \(、\) 1,3 \(、\) 2,1 \(、\) 2,3 $ の $ 5 $ 通りです。 長さ $ 3 $ の部分列は $ 1,1,3 \(、\) 1,2,1 \(、\) 1,2,3 \(、\) 2,1,3 $ の $ 4 $ 通りです。 長さ $ 4 $ の部分列は $ 1,2,1,3 $ の $ 1 $ 通りです。

Sample Explanation 2

長さ $ 1 $ の部分列は $ 1 $ の $ 1 $ 通りです。 長さ $ 2 $ の部分列は $ 1,1 $ の $ 1 $ 通りです。

Sample Explanation 3

$ 10^9+7 $ で割ったあまりを出力することに注意して下さい。

思路

这是一道排列组合的问题。

可以发现只有一个数会出现两次，其他数都只会出现一次。

先考虑不重复的情况，那么就是\(C_{n+1}^{k}\)即可。

但是得除掉重复的情况，思考一下，假设出现两次的数字，出现的位置分别记作\(left,right\)。

如果交换它们两个的位置，那么得到的序列还是一样的，也就是说，位于它们两者之间的数字是对可能的序列情况是没有任何影响的。

那么我们只需要考虑在\(left\)左边，\(right\)右边的序列情况即可，可以得到是\(C_{(l-1)+(n-r+1)}^{k}\)。

那么两者相减就是答案。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=3e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
ll fac[MAXN],vis[MAXN];
//费马小定理求组合数
ll qpower(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1)ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}

ll C(ll n,ll m){
    if(n<=0||m<=0||n<m)return 0;
    return fac[n]*qpower(fac[n-m]*fac[m]%mod,mod-2)%mod;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;cin>>n;
    n++;
    ll start=0,last=0;
    for(int i=1;i<=n;i++){
        ll x;cin>>x;
        //得到重复出现的数字
        if(vis[x]){
            start=vis[x];
            last=i;
            break;
        }
        //vis数组记录数字出现的位置
        vis[x]=i;
    }
    fac[0]=1;
    cout<<n-1<<"\n";
    for(int i=1;i<=n;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    for(int i=2;i<=n;i++){
        ll ans=C(n,i)-C(start+n-last-1,i-1);
        //这里+mod，防止结果为负数
        ans=(ans+mod)%mod;
        cout<<ans<<"\n";
    }
    return 0;
}