链接：https://www.nowcoder.com/acm/contest/156/C
来源：牛客网 题目描述
托米完成了1317的上一个任务，十分高兴，可是考验还没有结束
说话间1317给了托米 n 个自然数 a1... an, 托米可以选出一些带回家，但是他选出的数需要满足一些条件
设托米选出来了k 个数 b1,b2... bk, 设这个数列 b 的给值为 b 中所有数按位与的结果，如果你能找到一个整除 b 的最大的 2v,(v≥ )， 则设定 v 为这个数列的给价，如果不存在这样的 v，则给价值为 -, 希望托米在最大化给价的情况下，最大化 k
输入描述:
第一行输入一个整数 n, 第二行输入 a1...an
输出描述:
第一行输出最大的整数 k, 第二行输出 k 个整数 b1... bk, 按原数列的相对顺序输出 (如果行末有额外空格可能会格式错误)
示例1
输入 复制 输出 复制 备注:
n≤ , a1... an <
整除2v换成2进制不存在位数小于 2v的最高位，用lowbit返回
#include <iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define ll long long
int a[];
int num[];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
long long int ans=;
for(int i=;i<=;i++)
ans=ans|(1ll )<<i;
int sz=;
for(int i=;i>=;i--)
{
ll p=ans; sz=;
for(int j=;j<=n;j++)
{
if(1ll<<i&a[j])
{p=p&a[j];
num[sz++]=j;
}
}
if((p&(-p))>=(1ll<<i))
break;
}
cout<<sz<<endl;
for(int i=;i<sz;i++)
{
if(i)
cout<<" ";
cout<<a[num[i]];
}
cout<<endl;
return ;
}
D
链接：https://www.nowcoder.com/acm/contest/156/D
来源：牛客网 托米没有完成上一个任务，准备施展黑魔法推倒 黑魔法咒语被描述为一个 长为 n 的，仅包含小写英文字母 'a'...'i' 的字符串，在托米所在的星球，魔法造成的每次有效伤害都是来自他的一个子序列，对于每一个 'a'... 'i' 的排列(共 ! 种)，若作为咒语的子序列出现, 就会造成 的伤害 而咒语的总伤害为所有 'a'... 'i' 的排列造成的伤害值之和，托米能打出多少点的伤害，是否能击败 呢？
输入描述:
一行输入一个字符串 s
输出描述:
一行输出一个数，表示伤害值
示例1
输入 复制
aabcdefghi
输出 复制 备注:
|s| ≤
保存位子，二分查找
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
char a[];
vector<int >g[];
int b[];
int main()
{
cin>>a;
int t=strlen(a);
for(int i=;i<t;i++)
{
g[a[i]-'a'].push_back(i);
}
for(int i=;i<;i++) b[i]=i;
int ans=;
do
{
int flag=;
int now=-;
for(int i=;i<;i++)
{ if(g[b[i]].size()==||g[b[i]][g[b[i]].size()-]<=now)
{
flag=;
break;
}
int to=lower_bound(g[b[i]].begin(),g[b[i]].end(),now) - g[b[i]].begin();
now=g[b[i]][to];
}
if(flag)
ans++; }while(next_permutation(b,b+));
cout<<ans<<endl;
return ;
}