题意：给出三堆蜡烛，从第三堆取一些分到前两堆，使前两堆的数量相同。 求这两个堆元素的最大值。
实际上就是三堆数量之和对半分，如果是奇数的话舍去那一个就好。
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
int t; scanf("%d",&t);
while(t--){
long long a[3];
for(int i=0;i<3;i++) scanf("%lld",&a[i]);
sort(a,a+3);
printf("%I64d\n",(a[2]-a[1]+a[0])/2+a[1]);
//实际上直接输出就好，我做的时候脑抽了 printf("%lld\n",(a[0]+a[1]+a[2])/2);
}
return 0;
}
B- Odd Sum Segments
题意：题中给了一个长度为n的序列，要求划分为k个序列，使每个序列元素之和为奇数（必须是连续序列），试判断是否存在这样的划分方法，不存在直接NO
存在的话将划分点的位置依次输出。
要使要使序列元素之和为奇数，前提是该序列中奇数的个数为奇数个（x>0&&x&1）。而要划分为K个，则前提是原序列中奇数个数必须大于等于k。
所以我们统计序列中奇数的个数，如果比K还小，直接输出就可以；在大于等于K的时候，如果假设k个序列一个序列分配一个奇数，由于奇数加奇数为偶数，如果剩余奇数的个数为偶数个，则一定可以想到办法使他们两两想消，分成符合要求的k个序列。如果剩余奇数个数为奇数个则一定有一个不能抵消影响到已经分配好的序列，此时输出NO。
由于为YES是需要输出划分情况，此时不唯一，我们可以k-1个序列的结束位置与前k-1个奇数在数组中的下标值+1一一对应，最后一个序列一定是第n个直接输出n就可以。
#include<stdio.h>
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,k;
int a[200010];
int cnt=0;
scanf("%d %d",&n,&k);
for(int i=0;i<n;i++) {
scanf("%d",&a[i]);
if(a[i]&1) cnt++;
}
if(cnt<k) { //奇数个数小于k
printf("NO\n");
continue ;
}
else if((cnt-k+1)%2==0) { //剩余奇数个数为奇数个
printf("NO\n");
continue ;
}
else { //可以成功划分的情况
int num=0;
printf("YES\n");
if(k==1) { //1的时候需要特判
printf("%d\n",n);
continue;
}
else { // 按顺序输出即可
for(int i=0;i<n;i++){
if(num==k-1) break ;
if(a[i]&1) {
num++;
printf("%d ",i+1);
}
}
printf("%d\n",n);
}
}
}
return 0;
}
C- Robot Breakout
题意：给出一个坐标系中的一些点，给出了这些点所能移动的方向，判断这些点能否移动到同一个点上，能的话输出一个就行。
其实很简单，初步确定点可以存在范围为整个平面上，对每个点的四个方向进行判断，如果不能向哪个方向移动则更新点可能出现的的范围就行。
#include<stdio.h>
int main(){
int q;
scanf("%d",&q);
while(q--){
int n;
scanf("%d",&n);
int maxx=100000,maxy=100000;
int minx=-100000,miny=-100000;
for(int i=0;i<n;i++){
int x,y,a,b,c,d;
scanf("%d %d %d %d %d %d",&x,&y,&a,&b,&c,&d);
if(!a&&x>minx) //4个方向分别判断
minx=x;
if(!b&&y<maxy)
maxy=y;
if(!c&&x<maxx)
maxx=x;
if(!d&&y>miny)
miny=y;
}
if(maxx<minx||maxy<miny) {//这是不存在的情况
printf("0\n");
continue ;
}
else {//直接输出最小的情况
printf("1 %d %d\n",minx,miny);
continue ;
}
}
return 0;
}
D1- RGB Substring (easy version)
D2- RGB Substring (hard version)
题意：这两道题题意都一样，不同的只有数据范围。
要求是在一串只有R，G，B三个字符的字符串中找出长度是k的子串在对某些位做出变化后后得到的字符串是“RGBRGB…………” 的子串。题目要求最少的变化的位数。
我的想法是，最后得到长度为K子串可能从RGB,GBR,BRG这三种开头开始循环，如果，而如果对原字符串从开头对这三种顺序进行模拟，则所有的情况都可以包括其中，其中任意一位是R,G,B可能性都覆盖了。 对三种情况分别枚举，作前缀和数组，分别遍历一次，找出最小的改变次数即可。
超时了两次，第一次把memset换成for 快了点，仔细看才发现数组开小了，改了就过了。
#include<stdio.h>
#include<string.h>
int main(){
int sum1[200100],sum2[200100],sum3[200100];
int q;
scanf("%d",&q);
while(q--){
char s[200010];
int n,k;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++) scanf(" %c",&s[i]);
for(int i=0;i<=n;i++){
sum1[i]=0;
sum2[i]=0;
sum3[i]=0;
}
sum1[0]=0,sum2[0]=0,sum3[0]=0;
for(int i=1;i<=n;i++){
if(i%3==0)
if(s[i]!='R') sum1[i]=sum1[i-1]+1;
else sum1[i]=sum1[i-1];
else if(i%3==1)
if(s[i]!='G') sum1[i]=sum1[i-1]+1;
else sum1[i]=sum1[i-1];
else
if(s[i]!='B') sum1[i]=sum1[i-1]+1;
else sum1[i]=sum1[i-1];
}
for(int i=1;i<=n;i++){
if(i%3==0)
if(s[i]!='G') sum2[i]=sum2[i-1]+1;
else sum2[i]=sum2[i-1];
else if(i%3==1)
if(s[i]!='B') sum2[i]=sum2[i-1]+1;
else sum2[i]=sum2[i-1];
else
if(s[i]!='R') sum2[i]=sum2[i-1]+1;
else sum2[i]=sum2[i-1];
}
for(int i=1;i<=n;i++){
if(i%3==0)
if(s[i]!='B') sum3[i]=sum3[i-1]+1;
else sum3[i]=sum3[i-1];
else if(i%3==1)
if(s[i]!='R') sum3[i]=sum3[i-1]+1;
else sum3[i]=sum3[i-1];
else
if(s[i]!='G') sum3[i]=sum3[i-1]+1;
else sum3[i]=sum3[i-1];
}
int min1=200000;
for(int i=k;i<=n;i++){ /*三个前缀和数组分别遍历，找出长度为k的区间中最小那个*/
if(sum1[i]-sum1[i-k]<min1) min1=sum1[i]-sum1[i-k];
if(sum2[i]-sum2[i-k]<min1) min1=sum2[i]-sum2[i-k];
if(sum3[i]-sum3[i-k]<min1) min1=sum3[i]-sum3[i-k];
}
printf("%d\n",min1);
}
return 0;
}
E,F留待后补
