AtCoder 2041
TT有一个A×B×C的长方体。这个长方体是由A×B×C个1×1×1的小正方体组成的。
现在TT想给每个小正方体涂上颜色。
需要满以下三点条件：
每个小正方体要么涂成红色，要么涂成蓝色。
所有红色的小正方体组成一个长方体。
所有蓝色的小正方体组成一个长方体。
现在TT想知道红色小正方体的数量和蓝色小正方体的数量的差异。
你需要找到红色正方体的数量与蓝色正方体的数量差值的绝对值的最小值。
即min{|红色正方体数量 - 蓝色正方体数量|}。
输入
输入仅一行，三个数A B C (2≤A,B,C≤10^9)。
3 3 3
输出
输出一个数字。
即差值绝对值的最小值。
9
思路
这题的意思是，在长宽高中选择一条边，然后在这条边上把这个长方体给成两个，而且要求两个的体积相差是最小的。如果是这样的话，就是选择最长的那条边了，因为如果不选最长边的话，最长边和其他边的相乘得到的体积，会扩大两个分出来的长方体的体积差距。同时，分成尽可能一样的两份是体积相差最小的方法，刚好，因为int形变量的除法会下取整，把最长边除2以后再乘上剩下的两条边就是小的那份的体积，剩下的大份就是大的那份的体积，剩下的只需要他们两个相减就行了。
代码
#include<stdio.h>
#include<algorithm>
using namespace std;
int main() {
long long a[3]; scanf("%lld %lld %lld", &a[0], &a[1], &a[2]);
sort(a, a + 3);
printf("%lld", a[0] * a[1] * (a[2] - a[2] / 2 * 2));
}
| 团 队 聚 会 （不支持C++11）
TA团队每周都会有很多任务，有的可以单独完成，有的则需要所有人聚到一起，开过会之后才能去做。但TA团队的每个成员都有各自的事情，找到所有人都有空的时间段并不是一件容易的事情。
给出每位助教的各项事情的时间表，你的任务是找出所有可以用来开会的时间段。
输入
第一行一个数T（T≤100），表示数据组数。
对于每组数据，第一行一个数m（2 ≤ m ≤ 20），表示TA的数量。
对于每位TA，首先是一个数n（0≤ n≤100），表示该TA的任务数。接下来n行，表示各个任务的信息，格式如下
YYYY MM DD hh mm ss YYYY MM DD hh mm ss "some string here"
每一行描述的信息为：开始时间的年、月、日、时、分、秒；结束时间的年、月、日、时、分、秒，以及一些字符串，描述任务的信息。
数据约定：
所有的数据信息均为固定位数，位数不足的在在前面补前导0，数据之间由空格隔开。
描述信息的字符串中间可能包含空格，且总长度不超过100。
所有的日期时间均在1800年1月1日00:00:00到2200年1月1日00:00:00之间。
为了简化问题，我们假定所有的月份（甚至2月）均是30天的，数据保证不含有不合法的日期。
注意每件事务的结束时间点也即是该成员可以开始参与开会的时间点。
2
3
3
2020 06 28 15 00 00 2020 06 28 18 00 00 TT study
2020 06 29 10 00 00 2020 06 29 15 00 00 TT solving problems
2020 11 15 15 00 00 2020 11 17 23 00 00 TT play with his magic cat
4
2020 06 25 13 30 00 2020 06 25 15 30 00 hrz play
2020 06 26 13 30 00 2020 06 26 15 30 00 hrz study
2020 06 29 13 00 00 2020 06 29 15 00 00 hrz debug
2020 06 30 13 00 00 2020 06 30 15 00 00 hrz play
1
2020 06 01 00 00 00 2020 06 29 18 00 00 zjm study
2
1
1800 01 01 00 00 00 2200 01 01 00 00 00 sleep
0
输出
对于每一组数据，首先输出一行"Scenario #i:"，i即表明是第i组数据。
接下来对于所有可以用来开会的时间段，每一个时间段输出一行。
需要满足如下规则：
在该时间段的任何时间点，都应该有至少两人在场。
在该时间段的任何时间点，至多有一位成员缺席。
该时间段的时间长度至少应该1h。
所有的成员都乐意一天24h进行工作。
举个例子，假如现在TA团队有3位成员，TT、zjm、hrz。
那么这样的时间段是合法的：会议开始之初只有TT和zjm，后来hrz加入了，hrz加入之后TT离开了，此后直到会议结束，hrz和zjm一直在场。
要求：
输出满足条件的所有的时间段，尽管某一段可能有400年那么长。
时间点的格式为MM/DD/YYYY hh:mm:ss。
时间段的输出格式为"appointment possible from T0 to T1"，其中T0和T1均应满足时间点的格式。
严格按照格式进行匹配，如果长度不够则在前面补前导0。
按时间的先后顺序输出各个时间段。
如果没有合适的时间段，输出一行"no appointment possible"。
每组数据末尾须打印额外的一行空行。
Scenario #1:
appointment possible from 01/01/1800 00:00:00 to 06/25/2020 13:30:00
appointment possible from 06/25/2020 15:30:00 to 06/26/2020 13:30:00
appointment possible from 06/26/2020 15:30:00 to 06/28/2020 15:00:00
appointment possible from 06/28/2020 18:00:00 to 06/29/2020 10:00:00
appointment possible from 06/29/2020 15:00:00 to 01/01/2200 00:00:00
Scenario #2:
no appointment possible
思路
所有TA的空闲时间，都会在所有TA的时间段两端的时间点中组合产生，基于这个思想，我先把所有的时间点都存在一个数组t中，然后每个TA的开始时间段开始和结束的时间都分别存在他们对应的二维数组的mybegin 和 myend中，先把存了TA所有时间点的数组t给排序，然后设置两个游标l和r，r一定要大于l，这就开始在t中扫描所有的数据，每次用l和r挑出两个数据，每一次的挑出数据，都去存了TA时间段的二维数组中看，是不是至少有两个TA和最少只有一位缺席，并且，移动r的时候，尽量往右移动，这样就能找到最大的满足题意的区间。
代码
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<cmath>
using namespace std;
struct time {
int tim[6];//存储年月日时分秒
time(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0) {
tim[0] = a, tim[1] = b, tim[2] = c, tim[3] = d, tim[4] = e, tim[5] = f;
}
bool operator < (const time &t)const {
for (int i = 0; i < 5; i++)
if (tim[i] != t.tim[i])
return tim[i] < t.tim[i];
return tim[5] < t.tim[5];
}
bool operator > (const time &t)const {
for (int i = 0; i < 5; i++)
if (tim[i] != t.tim[i])
return tim[i] > t.tim[i];
return tim[5] > t.tim[5];
}
bool operator <= (const time& t)const {
for (int i = 0; i < 5; i++)
if (tim[i] != t.tim[i])
return tim[i] <= t.tim[i];
return tim[5] <= t.tim[5];
}
bool operator >= (const time& t)const {
for (int i = 0; i < 5; i++)
if (tim[i] != t.tim[i])
return tim[i] >= t.tim[i];
return tim[5] >= t.tim[5];
}
bool operator == (const time& t)const {
for (int i = 0; i < 5; i++)
if (tim[i] != t.tim[i])
return tim[i] == t.tim[i];
return tim[5] == t.tim[5];
}
}mystart[25][105], myend[25][105], t[4010], start_time(1800, 1, 1, 0, 0, 0), end_time(2200, 1, 1, 0, 0, 0);
int T, m, num_of_time, num_of_task[25];//数据组数，TA人数，时间点的个数，每个TA的任务量
bool judge_right(int x) {
int num = 0;
for (int i = 1; i <= m; i++) {//扫描所有的TA，看是不是在这个时间的左边有空闲时间,时间上是在检查一个区间右端点
if (num_of_task[i] == 0 || (t[x] <= mystart[i][1] && t[x] > start_time) || t[x] > myend[i][num_of_task[i]]) {
num++;
continue;
}
if (t[x] == myend[i][num_of_task[i]]) continue;//这个时间是这个TA的最大时间，如果等于这个时间，说明这个区间的左边这个TA有任务，不能使用这个区间
for (int j = 1; j <= num_of_task[i]; j++) {
if (t[x] > mystart[i][j] && t[x] <= myend[i][j])break;//如果这个时间点是在一个TA的工作中间的话，那么不需要计数
if (j + 1 <= num_of_task[i] && t[x] > myend[i][j] && t[x] <= mystart[i][j + 1]) { num++; break; }//符合这个情况的时候，那么就是在一个TA的空闲时间内
}
}
if (num >= 2 && m - num <= 1)
return true;//至少有两个人在场，至多有一个人缺席
return false;
}
bool judge_1h(int l, int r) {//判断两个时间点是大于一小时的
time left = t[l], right = t[r];
if (right.tim[0] > left.tim[0] + 1)return true;
right.tim[1] += 12 * (right.tim[0] - left.tim[0]);
if (right.tim[1] > left.tim[1] + 1)return true;
right.tim[2] += 30 * (right.tim[1] - left.tim[1]);
if (right.tim[2] > left.tim[2] + 1)return true;
right.tim[3] += 24 * (right.tim[2] - left.tim[2]);
if (right.tim[3] > left.tim[3] + 1)return true;
right.tim[4] += 60 * (right.tim[3] - left.tim[3]);
right.tim[5] += 60 * (right.tim[4] - left.tim[4]);
if (right.tim[5] - left.tim[5] >= 3600)return true;
return false;
}
bool judge_left(int x) {
int num = 0;//有空的TA人数
for (int i = 1; i <= m; i++) {
if (num_of_task[i] == 0 || t[x] < mystart[i][1] || (t[x] >= myend[i][num_of_task[i]] && t[x] < end_time)) {
num++;
continue;
}
for (int j = 1; j <= num_of_task[i]; j++) {
if (t[x] >= mystart[i][j] && t[x] < myend[i][j])break;
if (j + 1 <= num_of_task[i] && t[x] >= myend[i][j] && t[x] < mystart[i][j + 1]) { num++; break; }
}
}
if (num >= 2 && m - num <= 1)return true;
return false;
}
int main() {
// freopen("C:\\Users\\Lenovo\\Desktop\\1.txt","a",stdout);
scanf("%d", &T);
for (int count = 1; count <= T; count++) {
bool flag = false;
memset(num_of_task, 0, sizeof num_of_task);
memset(mystart, 0, sizeof mystart);
memset(myend, 0, sizeof myend);
memset(t, 0, sizeof t);
num_of_time = 0;//用来记录现在已经有了多少个时间点
t[++num_of_time] = start_time, t[++num_of_time] = end_time;//插入时间 点，用于后面的判断
scanf("%d", &m);//TA的人数
for (int i = 1; i <= m; i++) {
scanf("%d", &num_of_task[i]);//输入每个TA的任务数量
for (int j = 1; j <= num_of_task[i]; j++) {
for (int h = 0; h < 6; h++) scanf("%d", &mystart[i][j].tim[h]);
for (int h = 0; h < 6; h++) scanf("%d", &myend[i][j].tim[h]);
t[++num_of_time] = mystart[i][j], t[++num_of_time] = myend[i][j];//记录每一个时间点，后面分段使用
string str; getline(cin, str);
}
}
sort(t + 1, t + 1 + num_of_time);//把所有的时间点排序，TA空闲的时间肯定在这些时间点的中间
printf("Scenario #%d:\n", count);
int l = 1, r = 1;//两个游标，每次取出t中适合的时间
while (l <= num_of_time && r <= num_of_time) {
r++;
if (r > num_of_time)break;
while (r <= num_of_time && judge_right(r))
r++;//找到尽量向右的时间点
r--;
if (judge_1h(l, r)) {
flag = true;
printf("appointment possible from ");
printf("%02d/%02d/%d ", t[l].tim[1], t[l].tim[2], t[l].tim[0]);
printf("%02d:%02d:%02d", t[l].tim[3], t[l].tim[4], t[l].tim[5]);
printf(" to ");
printf("%02d/%02d/%d ", t[r].tim[1], t[r].tim[2], t[r].tim[0]);
printf("%02d:%02d:%02d\n", t[r].tim[3], t[r].tim[4], t[r].tim[5]);
}
l = r + 1;
//找到了之后第一个l
while (l <= num_of_time && !judge_left(l)) l++;
r = l;
}
if (!flag) printf("no appointment possible\n");
printf("\n");
}
return 0;
}
