AtCoder Beginner Contest 345 A - E 题解

A - Leftrightarrow

思路

判断第一个字符是否为，最后一个字符是否为，都满足的话，再判断中间字符是否都为

代码

#include
using namespace std;
#define int long long
 
bool check(string s){
	int n=s.size();
	if(s[0]!='<') return false;
	if(s[n-1]!='>') return false;
	for(int i=1;i-1;i++)
	    if(s[i]!='=') return false;
	return true;
}
 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	string s;
	cin>>s;
	cout<<(check(s)?"Yes":"No")<
	return 0;
}

B - Integer Division Returns

思路

首先，，所以答案可由得到。

但是C++是向0取整的（正数向下取整，负数向上取整），所以为负数且不整除时，答案需要加一。

代码

#include
using namespace std;
typedef long long LL;
int main(){
    LL n;
    cin>>n;
    LL ans=(n+9)/10;
    if((n+9)<0&&(n+9)%10!=0) ans--;
    cout<
    return 0;
}

C - One Time Swap

思路

篇幅问题，直接看官方题解。

注意要开long long

代码

#include
using namespace std;
typedef long long LL;
LL cnt[26];
int main(){
    LL n,ans=0;
    bool flag=false;
    string s;
    cin>>s;
    n=s.size();
    for(int i=0;i'a']++;
    ans=n*n;
    for(int i=0;i<26;i++){
        ans-=cnt[i]*cnt[i];
        if(cnt[i]>1) flag=true;
    }
    cout<2+flag<
    return 0;
}

D - Tiling

思路

由于数据范围很小，我们考虑暴力搜索。

设表示第行第个格子被哪一块瓷砖占用（没有被占用为-1）

为了表示哪些瓷砖可用，可以设二进制数，第位为1表示第块瓷砖可用。

由于瓷砖可以旋转（可以竖着放，也可以横着放），因此搜索时，每块瓷砖有两种情况（除了正方形）。

为了方便编写，我从dfs中分离出两个函数，第一个函数尝试放置瓷砖并判断是否可行。

第二个函数用于回溯操作（由于第一个函数会改变，所以无论是否可行都要复原）。

注意要判断是不是当前瓷砖，否则出现重叠时，会影响其他正常放置的瓷砖。

#include 
using namespace std;
const int N = 12;
int a[N],b[N],c[N][N];
int n,h,w;
bool ans;
 
// 以(x,y)为左上角，贴一块长为a宽为b的瓷砖（编号id），判断是否可行
bool placeTile(int x, int y, int a, int b, int id){
    bool can=true;
    for(int i=x;i
        for(int j=y;j
            if(i// 没有出界限
                if(c[i][j]==-1) c[i][j]=id;    // 可以放，做标记
                else can=false;                // 已经被占用，不能放这块瓷砖
            }else can=false;                   // 超过边界
        }
    return can;
}
 
// 回溯时的操作
void doBacktrace(int x, int y, int a, int b, int id){
    for(int i=x;i
        for(int j=y;j
            if(i-1;
    }
}
 
void dfs(int unused, int x, int y){
    // 找到下一个没贴瓷砖的位置
    while(c[x][y]>=0){
        y++;
        if(y>=w) x++,y=0;
        if(x>=h) break;
    }
    // 贴完了
    if(x>=h){
        ans=true;
        return;
    }
    // 尝试贴所有未使用的瓷砖
    for(int i=0;i
        if(unused&(1<// 未使用
            bool can=placeTile(x,y,a[i],b[i],i);
            if(can) dfs(unused^(1<// 继续搜索
            doBacktrace(x,y,a[i],b[i],i);        // 回溯还原
            // 尝试横着放
            if(a[i]!=b[i]){                // 不是正方形
                bool can=placeTile(x,y,b[i],a[i],i);
                if(can) dfs(unused^(1<
                doBacktrace(x,y,b[i],a[i],i);
            }
        }
    }
}
 
int main(){
    cin>>n>>h>>w;
    for(int i=0;i>a[i]>>b[i];
    for(int i=0;i
        for(int j=0;j-1;
    ans=false;
    dfs((1<-1,0,0);
    cout<<(ans?"Yes":"No")<
    return 0;
}

E - Colorful Subsequence

未完待续