ABC071

[ABC071B] Not Found

题面翻译

给出由小写字母组成的字符串\(S\)。 查找未出现在\(S\)中且字母顺序最小的小写字母。如果所有小写字母都出现在\(S\)中，则输出"None"。

题目描述

英小文字からなる文字列 $ S $ が与えられます． $ S $ に現れない英小文字であって，最も辞書順（アルファベット順）で小さいものを求めてください． ただし，$ S $ にすべての英小文字が現れる場合は，代わりに None を出力してください．

输入格式

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

$ S $

输出格式

$ S $ に現れない英小文字であって，最も辞書順で小さいものを出力せよ． ただし，$ S $ にすべての英小文字が現れる場合は，代わりに None を出力せよ．

样例 #1

样例输入 #1

atcoderregularcontest

样例输出 #1

b

样例 #2

样例输入 #2

abcdefghijklmnopqrstuvwxyz

样例输出 #2

None

样例 #3

样例输入 #3

fajsonlslfepbjtsaayxbymeskptcumtwrmkkinjxnnucagfrg

样例输出 #3

d

提示

制約

• $ 1  |S|  10^5 $ ($ |S| $ は文字列 $ S $ の長さ)
• $ S $ は英小文字のみからなる．

Sample Explanation 1

atcoderregularcontest という文字列には a は現れますが b は現れません．

Sample Explanation 2

この文字列には，すべての英小文字が現れます．

思路

使用map处理即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
map<int,int> m;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin>>s;
    for(int i=0;i<s.length();i++){
        m[s[i]-'a']++;			//记录每个字母出现的次数
    }
    for(int i=0;i<26;i++){
        if(m[i]==0){
            cout<<char('a'+i);	//从小到大遍历寻找即可
            return 0;
        }
    }
    cout<<"None";
    return 0;
}

[ABC071C] Make a Rectangle

题面翻译

有N根可以忽视粗细的棒。第i棒的长度是a_i。 有人想从这些棒子中选出4个不同的棒子，用这些棒子做个矩形(包括正方形)。求最大可以制作的矩形面积。

题目描述

太さが無視できる棒が $ N $ 本あります． $ i $ 番目の棒の長さは $ A_i $ です．

すぬけ君は，これらの棒から $ 4 $ 本の異なる棒を選び，それらの棒を辺として長方形（正方形を含む）を作りたいです． 作ることができる最大の長方形の面積を求めてください．

输入格式

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

$ N $ $ A_1 $ $ A_2 $ ... $ A_N $

输出格式

すぬけ君が作ることのできる最大の長方形の面積を出力せよ． ただし，長方形を作れない場合は，$ 0 $ を出力せよ．

样例 #1

样例输入 #1

6
3 1 2 4 2 1

样例输出 #1

2

样例 #2

样例输入 #2

4
1 2 3 4

样例输出 #2

0

样例 #3

样例输入 #3

10
3 3 3 3 4 4 4 5 5 5

样例输出 #3

20

提示

制約

• $ 4  N  10^5 $
• $ 1  A_i  10^9 $
• $ A_i $ は整数

Sample Explanation 1

$ 1  2 $ の長方形を作ることができます．

Sample Explanation 2

長方形を作ることはできません．

思路

不难想到用桶来记录，用优先队列来找最大值。

可以这样实现：我们每次需要的是两根相同长度的木棒，只要找到两根相同的，那么就将这种木棒加入到有限队列中，注意需要清空原来的桶。否则可能记录混乱。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
ll a[MAXN];
map<ll,int> m;
priority_queue<ll> q;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(m[a[i]]){
            q.push(a[i]);
            m[a[i]]=0;		//注意需要进行清空
        }
        else m[a[i]]++;
    }
    if(q.empty()){		//如果没有成对的木棒，则无解
        cout<<0;
        return 0;
    }
    ll x=q.top();		//取最大和第二大的木棒
    q.pop();
    ll y=q.top();
    cout<<x*y;
    return 0;
}

[ABC071D] Coloring Dominoes

题面翻译

Snuke有一个\(2\times N\)的矩阵,以及\(N\)个多米诺骨牌,每一个骨牌是\(1\times 2\)或者\(2 \times 1\)的
现在Snuke决定用红色、浅蓝色和绿色三种颜色来绘制这些骨牌,要保证每一个骨牌与其周围相邻的骨牌颜色都不一样
问一共有多少种不同的方案,答案对\(1e9+7\)取模

• 每一个骨牌都会用一个英文字母表示
  
• 保证每一个骨牌的字母都不一样

题目描述

$ 2  N $ のマス目があります． すぬけ君は，このマス目に $ N $ 個のドミノを，重ならないように敷き詰めました． ここで，ドミノは，$ 1  2 $ または $ 2  1 $ のマス目を覆うことができます．

すぬけ君は，赤色，水色，緑色の $ 3 $ 色を使って，これらのドミノを塗ることにしました． このとき，辺で接しているドミノは異なる色で塗るようにします． ここで，必ずしも $ 3 $ 色すべてを使う必要はありません．

このような塗り方が何通りあるかを mod $ 1000000007 $ で求めてください．

ただし，ドミノの敷き詰め方は，文字列 $ S_1, S_2 $ を用いて，次のようにして与えられます．

• 各ドミノは，それぞれ異なる英小文字または英大文字で表される．
• $ S_i $ の $ j $ 文字目は，マス目の上から $ i $ 番目，左から $ j $ 番目のマスにどのドミノがあるかを表す．

输入格式

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

$ N $ $ S_1 $ $ S_2 $

输出格式

ドミノを塗る方法の数を mod $ 1000000007 $ で出力せよ．

样例 #1

样例输入 #1

3
aab
ccb

样例输出 #1

6

样例 #2

样例输入 #2

1
Z
Z

样例输出 #2

3

样例 #3

样例输入 #3

52
RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn
RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn

样例输出 #3

958681902

提示

制約

• $ 1  N  52 $
• $ |S_1| = |S_2| = N $
• $ S_1, S_2 $ は英小文字または英大文字からなる
• $ S_1, S_2 $ は正しいドミノの敷き詰め方を表している

Sample Explanation 1

次の $ 6 $ 通りあります． 

Sample Explanation 2

必ずしもすべての色を使わなくてもよいことに注意してください．

思路

找规律递推解决。可以发现不是摆放的情况只有以下两种：

aa			//		a
bb			//		a

并且颜色互不相同，发现情况都是循环重复的，所以使用递推解决。

先找出初始情况：可能是上面的前者，也可能是后者。

如果是前者，那么初始情况有6种，反之只有3种，注意下标要更新。

因为要考虑颜色互不相同，所以每次确定新的多米诺骨牌的颜色时，除了像上面一样考虑当前的颜色，还需要考虑前面的牌的颜色。具体看代码实现。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;cin>>n;
    string a,b;cin>>a>>b;
    ll ans=0,s=0;
    if(a[0]==b[0])ans=3,s=1;	//对应第二种情况，注意下标的更新
    else ans=6,s=2;				//对应第一种情况，注意下标的更新
    for(int i=s;i<n;){
        if(a[i]==b[i]&&a[i-1]==b[i-1])ans*=2;		//都是竖的
        if(a[i]==b[i]&&a[i-1]!=b[i-1])ans*=1;		//前横后竖
        if(a[i]!=b[i]&&a[i-1]==b[i-1])ans*=2;		//前竖后横
        if(a[i]!=b[i]&&a[i-1]!=b[i-1])ans*=3;		//前横后横
        if(a[i]!=b[i])i+=2;							//下标的更新
        else i++;
        ans%=mod;			//更新ans
    }
    cout<<ans;
    return 0;
}