俩人平分三堆糖果 ， 输出平分后的数量
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ll a , b , c;
int q;
scanf("%d" , &q);
while(q--)
{
ll ans = 0;
scanf("%lld %lld %lld" , &a , &b , &c);
ans = a+b+c;
printf("%lld\n" , ans/2);
}
return 0;
} 将初始数组划分成k个子段 ， 每个子段都有奇数个元素和 ， 输出每个子段最后一个数字的下标。（n一定会输出 ， 属于最后一个子段）
思路：
找到奇数的个数 ， 如果奇数的个数小于k ，很明显不行。如果大于k ，假设每一个奇数都是他的一个子段部分 ， 那么只要判断除去k-1个奇数后剩下的个数是否为奇数即可。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int a[maxn] ;
int main()
{
int q , n , k , num;
scanf("%d" , &q);
while(q--)
{
num = 0;
scanf("%d %d" , &n , &k);
for(int i = 1 ; i <= n ; i++)
{
scanf("%d" , &a[i]);
if(a[i]%2) num++;
}
if(num < k) printf("NO\n");
else
{
if((num-(k-1)) % 2)
{
printf("YES\n");
int cnt = 0;
for(int i = 1 ; i <= n-1 ; i++)
{
if(cnt == k-1) break;
if(a[i] %2)
{
printf("%d " ,i);
cnt++;
}
}
printf("%d\n" , n);
}
else
{
printf("NO\n");
}
}
}
return 0;
} n个机器人的初始坐标为(xi , yi) ， 机器人有四种操作 ， 分别是向左上右下走一步。若表示机器人动作的数字为0则该机器人无法在此方向上继续走 ， 若为1 ，则在该方向上可继续走。找到一个点的坐标使得所有机器人都可以到达该点。并输出此坐标。
思路：定义四个变量minx , maxx , miny , maxy.分别表示x轴y轴可走的边界，最终这四个值可组成一个矩形 ，在矩形内的所有点都符合条件，任意输出一个即可。若无法组成矩形 ，则该点不存在。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+8;
int x[maxn] , y[maxn];
int f1 , f2 , f3 , f4;
int maxx , minx , maxy , miny;
int main()
{
int q , n ;
scanf("%d" , &q);
while(q--)
{
maxy = maxx = 100000;miny = minx = -100000;
scanf("%d" , &n);
for(int i = 1 ; i <= n ; i++)
{
scanf("%d %d %d %d %d %d" , &x[i] , &y[i] , &f1 , &f2 , &f3 , &f4);
if(f1 == 0) minx = max(minx , x[i]);
if(f2 == 0) maxy = min(maxy , y[i]);
if(f3 == 0) maxx = min(maxx , x[i]);
if(f4 == 0) miny = max(miny , y[i]);
}
if((minx > maxx ) || (miny > maxy))
{
printf("0\n");
}
else
{
printf("1 %d %d\n" , maxx , maxy);
}
}
return 0;
} D.RGB Substring (hard version)
给你一个字符串s:BGGGG
标准串：RGBRGBRGBRGB.........
求最少改变S串的个数使得S串中某连续k个是标准串的子串。
思路：
将字符串S与分别以R,G,B开头的标准串一一对应，一样为0不同则为1.
该样例表示：10110
算个前缀和再找连续k个变化值最小的就好了哇~
代码：
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 2e5+10;
int a[maxn] , sum[maxn];
int main()
{
int q , n , k , ans;
string str1 , str;
for(int i = 0 ; i <= maxn ; i+=3)
{
str1 += "R";
str1 += 'G';
str1 += 'B';
}
scanf("%d" , &q);
while(q--)
{
ans = INF;
scanf("%d %d" , &n , &k);
cin >> str;
a[0] = 0;
for(int i = 0 ; i < n ; i++)
{
if(str1[i] == str[i]) a[i+1] = 0;
else a[i+1] = 1;
}
for(int i = 1 ; i <= n ; i++)
{
sum[i] = sum[i-1] + a[i];
}
// for(int i = 1 ; i <= n ; i++)
// {
// printf("sum[%d] = %d\n" , i , sum[i]);
// }
for(int i = 1 ; i <= (n-k+1) ; i++)
{
ans = min(ans , (sum[i+k-1] - sum[i-1]));
}
int t1 = ans;
ans = INF;
memset(sum , 0 , sizeof(sum));
memset(a , 0 , sizeof(a));
for(int i = 0 ; i < n ; i++)
{
if(str1[i+1] == str[i]) a[i+1] = 0;
else a[i+1] = 1;
}
for(int i = 1 ; i <= n ; i++)
{
sum[i] = sum[i-1] + a[i];
}
for(int i = 1 ; i <= (n-k+1) ; i++)
{
ans = min(ans , (sum[i+k-1] - sum[i-1]));
}
int t2 = ans;
ans = INF;
memset(sum , 0 , sizeof(sum));
memset(a , 0 , sizeof(a));
for(int i = 0 ; i < n ; i++)
{
if(str1[i+2] == str[i]) a[i+1] = 0;
else a[i+1] = 1;
}
for(int i = 1 ; i <= n ; i++)
{
sum[i] = sum[i-1] + a[i];
}
for(int i = 1 ; i <= (n-k+1) ; i++)
{
ans = min(ans , (sum[i+k-1] - sum[i-1]) );
}
printf("%d\n" , min(ans , min(t1 , t2)));
}
return 0;
}
京公网安备 11010502036488号