并没有第四题。（还不会矩阵乘法加速线性数列）
题目1 : 数位翻转
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个数 n，你可以进行若干次操作，每次操作可以翻转 n 的二进制表示下的某一位，即将 0 变成 1，1 变成 0
现在小 Hi 想知道，至少需要多少次操作，才能将 n 变成 n-1
输入
一个正整数 n
1 ≤ n ≤ 109
输出
输出最少的操作次数
签到题，模拟一下取出各位二进制数即可，极水，怒A。
#include<cstdio>
#include<algorithm> using namespace std; int n,m,lena,lenb,ans;
int a[],b[]; int main()
{
scanf("%d",&n);
m=n-;
while(n)
{
a[++lena]=n%;
n/=;
}
while(m)
{
b[++lenb]=m%;
m/=;
}
int len=max(lena,lenb);
for(int i=;i<=len;i++)
if(a[i]!=b[i]) ans++;
printf("%d",ans);
return ;
}
题目2 : 最短公共子序列
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个 01 串 A，你需要找一个和它等长的01串 B，使得 A 和 B 的最长公共子序列最短
为了方便，你不需要输出 B，你只需要输出 A 和 B 的最长公共子序列的长度
输入
第一行一个 01 串 A
1 ≤ |A| ≤ 105
输出
输出最短的长度
- 样例输入
-
000111
- 样例输出
-
3
这个题啊，看起来有点唬人。一看到“最长公共子序列最短”，我上来就是一顿二分敲。后来发现check函数没法写，在固有的（我的）惯性思维中，把带字符串背景的都考虑成公共子串（中间不能有不同），而本题恰好反其道而行之，问子序列（子序列中间可间隔不同的）。
我们再冷静分析一下，状态要么是0，要么是1，手动模拟几组答案，可以发现答案正是A串中出现最少元素的个数。
抱着试试看的心态交了上去，竟然A了。qwq。
-
#include<cstdio>
#include<algorithm>
#include<cstring> using namespace std; char py[];
int c,d,ans;
int a[],b[]; int main()
{
scanf("%s",py+);
int len=strlen(py+);
for(int i=;i<=len;i++) a[i]=(int)py[i]-'';
for(int i=;i<=len;i++)
if(a[i]==) c++;else d++;
ans=min(c,d);
printf("%d",ans);
return ;
} -
题目3 : 拼三角形
时间限制:20000ms单点时限:1000ms内存限制:256MB描述
给定 n 根木棍，第 i 根长度为 ai
现在你想用他们拼成尽量多的面积大于 0 的三角形，要求每根木棍只能被用一次，且不能折断
请你求出最多能拼出几个
输入
第一行一个正整数 n
第二行 n 个正整数 a1 … an
1 ≤ n ≤ 15
1 ≤ ai ≤ 109
输出
输出最多能拼出几个三角形
学长表示：一道暴搜题！巧了！我就不会写暴搜！qwq！
再和学长学习一下qwq。
由于最多有15根棒，所以顶多也就5个三角形。
然后我们就搜就行了qwq。我的模拟&贪心只能拿75分。
注释写在码里qwq。
#include<cstdio>
#include<algorithm> using namespace std;
typedef long long ll; int n;
ll ans;
int a[];
bool flag[]; void dfs(int cnt,int a1,int a2,int pre)
{//cnt->当前已经选到第几个三角形
//a1->三角形中最短边，a2->三角形中最长边。
//pre->上一个选到哪了（下标）
if(cnt==ans+)
{
printf("%d",ans);
exit();//void函数中想直接return 0结束程序用exit
}
if(!a1)
{
for(int i=pre+;i<=n;i++)
{
if(flag[i]) continue;
flag[i]=;
dfs(cnt,a[i],,i);
flag[i]=;
}
}
else if(a1>&&a2<=)
{
for(int i=pre+;i<=n;i++)
{
if(flag[i]) continue;
flag[i]=;
dfs(cnt,a1,a[i],i);
flag[i]=;
}
}
else
{
for(int i=pre+;i<=n;i++)
{
if(flag[i]) continue;
if(a1+a2<=a[i]) return ;
flag[i]=;
dfs(cnt+,,,);
flag[i]=;
}
}
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
sort(a+,a++n);
for(int i=n/;i>=;i--)
{
ans=i;//要几个 当前在哪 现在已经有几个边
dfs(,,,);
}
printf("%d",ans);
return ;
}