题目1 : 数位翻转
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个数 n，你可以进行若干次操作，每次操作可以翻转 n 的二进制表示下的某一位，即将 0 变成 1，1 变成 0
现在小 Hi 想知道，至少需要多少次操作，才能将 n 变成 n-1
输入
一个正整数 n
1 ≤ n ≤ 109
输出
输出最少的操作次数
- 样例输入
10
- 样例输出
2
// 2018-07-29
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long using namespace std; int main()
{
ll n;
while(cin>>n){
ll ans = n^(n-);
int cnt = ;
while(ans){
if(ans&1LL){
cnt++;
}
ans>>=;
}
cout<<cnt<<endl;
} return ;
}
题目2 : 最短公共子序列
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个 01 串 A，你需要找一个和它等长的01串 B，使得 A 和 B 的最长公共子序列最短
为了方便，你不需要输出 B，你只需要输出 A 和 B 的最长公共子序列的长度
输入
第一行一个 01 串 A
1 ≤ |A| ≤ 105
输出
输出最短的长度
- 样例输入
000111
- 样例输出
3
// 2018-07-29
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; string str; int main()
{
cin>>str;
int len = str.length();
int zero = , one = ;
for(int i = ; i < len; i++)
if(str[i] == '')zero++;
else one++;
cout<<min(zero, one)<<endl; return ;
}
题目3 : 拼三角形
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
给定 n 根木棍，第 i 根长度为 ai
现在你想用他们拼成尽量多的面积大于 0 的三角形，要求每根木棍只能被用一次，且不能折断
请你求出最多能拼出几个
输入
第一行一个正整数 n
第二行 n 个正整数 a1 … an
1 ≤ n ≤ 15
1 ≤ ai ≤ 109
输出
输出最多能拼出几个三角形
- 样例输入
6
2 2 3 4 5 6- 样例输出
2
// 2018-07-29
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long using namespace std; ll arr[];
int n, ans;
bool vis[]; void dfs(int step){
for(int i = ; i <= n; i++){
for(int j = i+; j <= n; j++){
for(int k = j+; k <= n; k++){
if(!vis[i] && !vis[j] && !vis[k] && arr[i]+arr[j]>arr[k]){
vis[i] = vis[j] = vis[k] = true;
ans = max(ans, step);
dfs(step+);
vis[i] = vis[j] = vis[k] = false;
}
}
}
}
return;
} int main()
{
cin>>n;
for(int i = ; i <= n; i++)
cin>>arr[i];
ans = ;
sort(arr+, arr++n);
memset(vis, , sizeof(vis));
dfs();
cout<<ans<<endl; return ;
}