AtCoder Beginner Contest 345 A

AtCoder Beginner Contest 345 A - E 题解

A - Leftrightarrow

思路

判断第一个字符是否为 $\texttt{<}$ ，最后一个字符是否为 $\texttt{>}$ ，都满足的话，再判断中间字符是否都为 $\texttt{=}$

代码

#include<iostream>
using namespace std;
#define int long longbool check(string s){int n=s.size();if(s[0]!='<') return false;if(s[n-1]!='>') return false;for(int i=1;i<n-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")<<endl;return 0;
}

B - Integer Division Returns

思路

首先， $\left\lceil \dfrac{a}{b} \right\rceil = \left\lfloor \dfrac{a+b-1}{b} \right\rfloor$ ，所以答案可由 $\left\lfloor \dfrac{X+9}{10} \right\rfloor$ 得到。

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

代码

#include<iostream>
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<<ans<<endl;return 0;
}

C - One Time Swap

思路

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

注意要开long long

代码

#include<bits/stdc++.h>
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<n;i++) cnt[s[i]-'a']++;ans=n*n;for(int i=0;i<26;i++){ans-=cnt[i]*cnt[i];if(cnt[i]>1) flag=true;}cout<<ans/2+flag<<endl;return 0;
}

D - Tiling

思路

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

设 $C_{i,j}$ 表示第 $i$ 行第 $j$ 个格子被哪一块瓷砖占用（没有被占用为-1）

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

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

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

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

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

#include <iostream>
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<x+a;i++)for(int j=y;j<y+b;j++){if(i<h&&j<w){                      // 没有出界限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<x+a;i++){for(int j=y;j<y+b;j++) if(i<h&&j<w&&c[i][j]==id) c[i][j]=-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<n;i++){if(unused&(1<<i)){   // 未使用bool can=placeTile(x,y,a[i],b[i],i);if(can) dfs(unused^(1<<i),x,y);    // 继续搜索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<<i),x,y);doBacktrace(x,y,b[i],a[i],i);}}}
}int main(){cin>>n>>h>>w;for(int i=0;i<n;i++) cin>>a[i]>>b[i];for(int i=0;i<h;i++)for(int j=0;j<w;j++) c[i][j]=-1;ans=false;dfs((1<<n)-1,0,0);cout<<(ans?"Yes":"No")<<endl;return 0;
}