调查员三宝之朋友：
题意：
求有多少个连续的数段，这些数段中的全部数之和为m
双指针做法：
用i，j代表区间的左右端点，sum代表[i,j]这个区间所有数之和
当sum小于目标值M时，将右端点右移（j++），sum会变大
当sum大于目标值M时，将左端点右移（i++），sum会变小
在双指针移动的过程中，如果有sum==M的情况ans+1。
因为两个指针都是单调向右移动，也只扫一遍，可以证明时间复杂度为O(n)
左端点大于m/2时即可停止，因为只要长度为2的连续序列和就一定大于m
#include<stdio.h>
int main()
{
int m, ans = 0, sum = 3;
scanf("%d", &m);
for (int i = 1, j = 2; i <= m / 2;)
{
if (sum == m)
{
ans ++ ;
sum -= i;
i ++ ;
}
else if (sum < m)
{
j ++ ;
sum += j;
}
else
{
sum -= i;
i ++ ;
}
}
printf("%d", ans);
return 0;
}
调查员三宝之撬棍：
分析：
一个二进制数变为原来的17倍，相当于这个数乘以16再加上原来的数
二进制下，数的末尾添加一个零，相当于这个数乘以2，所以将这个数的末尾加上4个0，再加上原来的数
N最大是1000位，可以用高精加来进行计算(用数组来模拟加法)
#include<stdio.h>
#include<string.h>
int main()
{
char s[1100] = {0};
scanf("%s", s);
int n = strlen(s);
int t1[1100] = {0}, t2[1100] = {0}; // t1是原本的数，t2是原来的数乘以16
for (int i = 0; i < n; i ++ )
{
t2[i + 4] = t1[i] = s[n - i - 1] - '0';
}
n += 4;
for (int i = 0; i < n; i ++ )
{
t2[i] += t1[i];
if (t2[i] > 1)
{
t2[i] -= 2;
t2[i + 1] += 1;
}
}
while (t2[n] > 1)
{
n ++ ;
}
for (int i = n - 1; i >= 0; i -- )
printf("%d", t2[i]);
return 0;
}
调查员三宝之旧印：
分析：
x <= y <= z，显然七个数中，最小的是x，次小的是y，最大的是x+y+z
将7个数排序后，依次输出最小的，次小的，最大的减去最小的和次小的
#include<stdio.h>
int main()
{
int a[10];
for (int i = 1; i <= 7; i ++ )
{
scanf("%d", &a[i]);
}
for (int i = 1; i <= 7; i ++ )
{
for (int j = i + 1; j <= 7; j ++ )
{
if (a[i] > a[j])
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
printf("%d %d %d", a[1], a[2], a[7] - a[1] - a[2]);
return 0;
}
签到题：
分析：
任意两个相邻的正整数的最大公约数为1
这样的话我们最多只需要进行两次操作（对第n个数和第n-1个数进行操作）就可以让整个数组的最大公约数为1.
接着分情况判断就行：
1.不需要操作，成本为0
2.对第n个数进行操作，成本为1
3.对第n-1个数进行操作，成本为2
4.对第n个数和第n-1个数进行操作，成本为3
#include<stdio.h>
int a[25];
int n;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
}
int g = a[1];
for (int i = 2; i <= n; i ++ )
{
g = gcd(g, a[i]);
}
int ans = 0;
if (g != 1)
{
if (gcd(g, n) == 1) ans = 1;
else if (gcd(g, n - 1) == 1) ans = 2;
else ans = 3;
}
printf("%d", ans);
return 0;
}
签到题·真：
输出就行
#include<stdio.h>
int main()
{
printf("\"a %% b = c\"");
return 0;
}
最大值：
分析：
如果火技能的数量与冰技能的数量相等，则除初始伤害最小的技能外，所有技能的伤害加倍。
否则，设k为两种技能数量的最小值，然后将每种技能中初始伤害最大的k个技能的伤害加倍。
#include<stdio.h>
#include<string.h>
int t[1005], fire[1005], ice[1005], fl, il;
long long ans;
void sort(int a[], int n)
{
for (int i = 1; i <= n; i ++ )
{
for (int j = i + 1; j <= n; j ++ )
{
if (a[i] < a[j])
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &t[i]);
for (int i = 1; i <= n; i ++ )
{
int x;
scanf("%d", &x);
if (t[i])
{
ice[++il] = x;
}
else
{
fire[++fl] = x;
}
ans += x;
}
sort(ice, il);
sort(fire, fl);
int temp = il < fl ? il : fl;
for (int i = 1; i <= temp; i ++ )
{
ans += fire[i] + ice[i];
}
if (fl == il)
{
ans -= ice[il] < fire[fl] ? ice[il] : fire[fl];
}
printf("%lld", ans);
return 0;
}
棋子反转：
题意：
读入表示棋子状态的字符串，要把棋子都翻到1。翻转有一定的规则，如果你要翻第i枚棋子，必须把1~i枚都翻转。问怎么翻才能用最少的次数得到全部为1的棋子序列。
分析：
从左往右扫,如果这个棋子与下个棋子状态不同,就说明要翻一次。最后还得判断最后一个是不是0,如果是0还要再翻一次,因为题目说要全部正面朝上,就是全部为1,最后一位为0就说明翻完后全是0,还要再翻一次。
#include<stdio.h>
#include<string.h>
char s[1000005];
int main()
{
scanf("%s", s);
int ans = 0;
int n = strlen(s);
for (int i = 0; i < n - 1; i ++ )
{
if (s[i] != s[i + 1])
ans ++ ;
}
if (s[n - 1] == '0') ans ++ ;
printf("%d", ans);
return 0;
}
神之天平：
分析：
用i，j分别表示左端点和右端点，suml，sumr表示目前左托盘和右托盘的灵魂重量。
ans为答案，res为距离上一次天平平衡，左右托盘新增灵魂数量
两个指针相遇前，进行循环，每次循环进行判断：
1.suml<sumr
将指针i右移，suml加上w[i]
2.suml>sumr
将指针j左移，sumr加上w[j]
3.suml=sumr
更新ans和res，且将指针i右移，suml加上w[i]或将指针j左移，sumr加上w[j]
#include<stdio.h>
int w[100005];
int n;
int ans;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &w[i]);
}
long long suml = w[1], sumr = w[n], res = 2;
for (int i = 1, j = n; i < j; )
{
while (suml < sumr && i < j)
{
i ++ ;
suml += w[i];
res ++ ;
}
while (suml > sumr && i < j)
{
j -- ;
sumr += w[j];
res ++ ;
}
if (suml == sumr)
{
i ++ ;
suml += w[i];
ans += res;
res = 1;
}
}
printf("%d\n", ans);
return 0;
}
京公网安备 11010502036488号