A.Stair, Peak, or Neither?
题目大意
根据 a、b、c 的大小关系输出给定字符串
代码
void solve()
{
ll a,b,c;
cin>>a>>b>>c;
if(a<b&&b<c) cout<<"STAIR"<<'\n';
else if(a<b&&b>c) cout<<"PEAK"<<'\n';
else cout<<"NONE"<<'\n';
}
B. Upscaling
题目大意
根据题目给出的 n 构造字符矩阵
代码
void solve()
{
int n;
cin>>n;
for(int i=0;i<2*n;i++) {
char ch=((i/2)%2)?'#':'.';
for(int j=0;j<2*n;j++) {
cout<<((j/2)%2?ch:(ch=='#'?'.':'#'));
}
cout<<'\n';
}
}
C. Clock Conversion
题目大意
将 24 小时制时间改成 12 小时制
代码
void solve()
{
int a,b;
scanf("%d:%d",&a,&b);
if(a<12) printf("%02d:%02d AM\n",a==0?12:a,b);
else if(a==12) printf("%02d:%02d PM\n",a,b);
else printf("%02d:%02d PM\n",a-12,b);
}
D. Product of Binary Decimals
题目大意
给定一个整数,问其是否能够被每位数字都是0或1的十进制数(如1,10,11,101等)整除。
思路
由于 n 最大为 1 0 5 10^5 105 ,可以直接打表能够作为除数的十进制数。
代码
const int _number[]={
1,10,11,100,101,110,111,
1000,1001,1010,1011,1100,1101,1110,1111,
10000,10001,10010,10011,10100,10101,10110,10111,11000,11001,11010,11011,11100,11101,11110,11111,
100000
};
void solve()
{
int n;
cin>>n;
int temp=n;
bool succ=true;
while(temp) {
succ=succ&&(temp%10==0||temp%10==1);
temp/=10;
}
if(succ) {
cout<<"YES"<<'\n';
return;
}
for(int t=1;t<32;t++) {
while(n%_number[t]==0) n/=_number[t];
}
cout<<(n==1?"Yes":"No")<<'\n';
}
E. Nearly Shortest Repeating Substring
题目大意
给定一个字符串 str,问是否存在字符串 k,使得 x 个 k 连接起来与 str 完全相同或者仅有一个字符不同(x值任意),求 k 的最小长度
思路
从小到大枚举划分的长度,对于每个枚举的长度:维护一个总和 sum,sum 为每个划分中相同下标的相同字符数量的最大值之和,判断 sum 是否不小于 n-1,若是,则当前枚举长度为最优解。
代码
void solve()
{
int n;
string line;
cin>>n>>line;
for(int len=1;len<=n;len++) {
if(n%len) continue;
int sum=0;
for(int left=0;left<len;left++) {
int mx=0;
vector<int> cnt(26,0);
for(int i=left;i<n;i+=len) {
cnt[line[i]-'a']++;
mx=max(mx,cnt[line[i]-'a']);
}
sum+=mx;
}
if(sum>=n-1) {
cout<<len<<'\n';
return;
}
}
}
F. 0, 1, 2, Tree!
题目大意
给定三个整数 a、b、c 分别表示树中有两个子节点的节点数量,有一个孩子的节点的数量与叶节点数量,问可以构造的数的最小高度。
思路
根据二叉树性质,若 a + 1 ≠ c a +1 \neq c a+1=c 则无解。否则可用数组维护每层节点的最大数量:2 个孩子的节点放在上面一定是最优解,根据每层节点可以计算下一层节点的数量。
代码
void solve()
{
int a,b,c;
cin>>a>>b>>c;
if(a!=c-1) {
cout<<-1<<'\n';
return;
}
vector<int> tr(1,1);
int ptr=0;
for(int i=1;i<=a+b;i++) {
if(tr[ptr]==0) {
ptr++;
}
if(ptr==int(tr.size()-1)) {
tr.push_back(0);
}
tr[ptr]--;
tr[ptr+1]+=(i<=a?2:1);
}
cout<<int(tr.size()-1)<<'\n';
}
G. Shuffling Songs
题目大意
每首歌由两部分组成:风格g 与 作者w,现在需要列一个清单,要求清单中相邻的两首歌曲要么 g 相同,要么 w 相同,问组成这样一个清单最少需要删除几首歌曲?
思路
状压dp
题目给出的 n 的范围很小 ( ≤ 16 ) (≤ 16) (≤16),可以用邻接矩阵维护每两首歌是否能相邻。考虑维护 dp[state][i] 表示当前选中歌曲为 state (集合) 且最后一首歌为 i 的情况能否组成一个清单,其中 state 使用二进制表示表示每首歌是否选中,不难发现仅选择一首歌的情况是一定满足要求的,对于每个 state ,枚举选中的歌 i(作为最后一首)与未选中的歌 j ,通过邻接矩阵查询 i 、j 是否能够相邻,若能相邻,更新 d p [ s t a t e ∣ ( 1 < < j ) ] [ j ] dp[state | (1 << j)][j] dp[state∣(1<<j)][j] 的值为 true,答案为所有值为true 的 state 的二进制中1数量的最大值。
代码
void solve()
{
int n;
cin>>n;
vector<string> a(n),b(n);
for(int i=0;i<n;i++) cin>>a[i]>>b[i];
vector g(n,vector<bool>(n,false));
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
g[i][j]=g[j][i]=(a[i]==a[j]||b[i]==b[j]);
}
}
vector dp((1<<n),vector<bool>(n,false));
for(int i=0;i<n;i++) {
dp[1<<i][i]=true;
}
int ans=0;
for(int t=1;t<(1<<n);t++) {
for(int i=0;i<n;i++) {
if(dp[t][i]) {
ans=max(ans,__builtin_popcount(t));
for(int j=0;j<n;j++) {
if(!(t&(1<<j))&&(g[i][j])) {
dp[t|(1<<j)][j]=true;
}
}
}
}
}
cout<<n-ans<<'\n';
}