年前最后一场，最 ♥ 水题欢乐赛.
┬┴┬┌─ ●─┬─ │─┼─┐ ●├─┤○
┴┬┴├┬ ┌─┼─ │◎ │ │ ○└┬┘●
─┼─││ │ │ ││─┴─┴ ──┼──
●│○││ ┴─┼─ │○ ● ／ │ ＼
A - Easy Marks
题意：给出 科目数量 n 和 平均分 k ，求下一门考多少分才能达到 k.
分析：暴力 暴力 暴力！暴力水鸭
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long int
using namespace std;
int main()
{
int T;
int tot = 0;
scanf("%d", &T);
while(T--)
{
int n, k;
int data;
int sum = 0;
scanf("%d %d", &n, &k);
for(int i = 0; i < n; ++i)
{
scanf("%d", &data);
sum += data;
}
for(int i = 1; i <= 100; ++i)
{
int t = (sum + i) / (n + 1);///考 i 分后的平均分.
if(t >= k)
{
printf("Case %d: %d\n", ++tot, i);
break;
}
}
}
return 0;
}
B - Candy I
题意：有 n 个袋子，里面装着糖糖，若能均分则输出最少需要移动几颗糖，否则输出 -1.
分析：先求糖糖的 sum ，如果 sum 为 n 的倍数，记 t = sum / n，然后统计每个袋子里有多少糖是 ＞ t 的，
要是不能被整除，就print -1 喽.
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long int
using namespace std;
int a[10010];
int main()
{
int n;
while(scanf("%d", &n))
{
if(n == -1)
break;
int sum = 0;
for(int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
sum += a[i];
}
if(sum % n)
{
printf("-1\n");
continue;
}
int t = sum / n;
int ans = 0;
for(int i = 0; i < n; ++i)
{
if(a[i] > t)
ans += a[i] - t;
}
printf("%d\n", ans);
}
return 0;
}
C - Rectangles
题意：问由 1 - n 个小正方形能构成多少个长方形.
分析：暴力 AC，其实就是看 n 是否能被另一个数（1 ~ sqrt(n)）整除.
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long int
using namespace std;
int main()
{
int n;
int ans = 0;
scanf("%d",&n);
for(int i = 1; i <= n; ++i)
{
int t = i;
for(int j = 1; j <= sqrt(t); ++j)
{
if(!(t % j))
ans++;
}
}
printf("%d\n", ans);
return 0;
}
D - Alchemy
题意：冗长的英文体面....
有 3 个袋子，分别装着 B, R, Y 颜色数量的试剂，给出一个整数 n，接着 n 行颜色试剂，用这些试剂来配药水，
问有几种配法.
分析：直接看代码吧 ｡◕ᴗ◕｡.
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long int
using namespace std;
int main()
{
int b, r, y;
scanf("%d %d %d", &b, &r, &y);
int n;
scanf("%d", &n);
string s;
int ans = 1;
for(int i = 0; i < n; ++i)
{
cin >> s;
if(s == "Red")
ans *= r;
else if(s == "Blue")
ans *= b;
else if(s == "Yellow")
ans *= y;
}
printf("%d\n", ans);
return 0;
}
E - Genealogical Tree
题意：火星人在 papa 关系上很混乱，现有 n 位火星人，并给出这 n 位火星人的孩子，试确定这 n 位
火星人的父子关系.
分析：拓扑排序水题
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long int
using namespace std;
const int M = 110;
int in[M];
vector <int> v[M];
vector <int> ans;
queue <int> q;
int main()
{
int n;
scanf("%d", &n);
int data;
for(int i = 1; i <= n; ++i)
{
while(1)
{
scanf("%d", &data);
if(!data)
break;
v[i].push_back(data);
in[data]++;
}
}
for(int i = 1; i <= n; ++i)
{
if(!in[i])
q.push(i);
}
while(!q.empty())
{
int p = q.front();
ans.push_back(p);
q.pop();
int len = v[p].size();
for(int i = 0; i < len; ++i)
{
in[v[p][i]]--;
if(!in[v[p][i]])
q.push(v[p][i]);
}
}
int len = ans.size();
bool flag = 0;
for(int i = 0; i < len; ++i)
{
if(flag)
printf(" ");
printf("%d", ans[i]);
flag = 1;
}
printf("\n");
return 0;
}
F - GCD The Largest
题意：给出 n （2 ≤ n ≤ 
分析：妈耶！这数据范围！那就安安静静的找规律吧.
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long int
using namespace std;
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
ll n;
scanf("%lld", &n);
printf("%lld\n", n / 2);
}
return 0;
} G - Peter's Smokes
题意：Peter 有 n 只烟，k 个烟头能换 1 只烟，问 Peter 最多能有几支烟.
分析：简单模拟，暴力水题.
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long int
using namespace std;
int main()
{
int n, k;
while(~scanf("%d %d", &n, &k))
{
int t = 0;
int ans = 0;
while(1)
{
if(n)
{
t += n;
ans += n;;
n = 0;
}
if(t >= k)
{
n += t / k;
t -= (t / k) * k;
}
if(n == 0 && t < k)
break;
}
printf("%d\n", ans);
}
return 0;
} H - Blown Garland
题意：有 4 种颜色的灯 —— R，B，Y，G. 有一组灯串，周期为 4，有某些盏灯灭掉了，
求各种颜色的灯各有多少种.
分析：遇到灭掉的灯，就向前或前后找，周期为 4.
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long int
using namespace std;
int main()
{
string s;
cin >> s;
int len = s.size();
map <char, int> mp;
mp['R'] = 0;
mp['Y'] = 0;
mp['B'] = 0;
mp['G'] = 0;
for(int i = 0; i < len; ++i)
{
if(s[i] == '!')
{
bool flag = 1;
for(int j = i; j < len; j += 4)
{
if(s[j] != '!')
{
flag = 0;
mp[s[j]]++;
break;
}
}
if(flag)
{
for(int j = i; j >= 0; j -= 4)
{
if(s[j] != '!')
{
mp[s[j]]++;
break;
}
}
}
}
}
printf("%d %d %d %d\n", mp['R'], mp['B'], mp['Y'], mp['G']);
return 0;
}
I - Pythagorean Theorem II
题意：给出一个数 n（1 ≤ n ≤ 
求能构成直角三角形的个数.
分析：这题暴力 O(
条件 1 ：
条件 2 ：1 ≤ a ≤ b ≤ c ≤ n.
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long int
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int ans = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = i + 1; j <= n; ++j)
{
int c1 = i * i + j * j;
int c2 = (int)sqrt(c1);
if(c2 * c2 == c1 && c2 <= n && c2 >= j)
{
ans++;
}
}
}
printf("%d\n", ans);
return 0;
}
J - Calendar
题意：计算两个日期间的天数.
分析：先计算第一个日期是这一年的第几天，第二个日期是这一年的第几天，
然后再统计这两年隔了多少天.
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define PI acos(-1.0)
#define ll long long int
using namespace std;
int a1[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int a2[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
struct node
{
int y;
int m;
int d;
};
int cmp(node a, node b)
{
if(a.y != b.y)
return a.y < b.y;
if(a.m != b.m)
return a.m < b.m;
return a.d < b.d;
}
bool runnian(int year)
{
if(year % 4 == 0 && year % 100 != 0 || year % 400 == 0)
return 1;
return 0;
}
int time_gap(int y, int m, int d)
{
int ans = 0;
if(runnian(y))
{
for(int i = 1; i < m; ++i)
ans += a1[i];
}
else
{
for(int i = 1; i < m; ++i)
ans += a2[i];
}
ans += d;
return ans;
}
int main()
{
struct node s[5];
scanf("%d:%d:%d", &s[1].y, &s[1].m, &s[1].d);
scanf("%d:%d:%d", &s[2].y, &s[2].m, &s[2].d);
sort(s + 1, s + 3, cmp);
int ans1 = time_gap(s[1].y, s[1].m, s[1].d) - 1;///此日期在 s[1].y 年的第 ans1 天.
int ans2 = time_gap(s[2].y, s[2].m, s[2].d) - 1;///此日期在 s[2].y 年的第 ans2 天.
int ans = ans2 - ans1;
for(int i = s[1].y; i < s[2].y; ++i)///统计年
{
if(runnian(i))
ans += 366;
else
ans += 365;
}
printf("%d\n", ans);
return 0;
}
京公网安备 11010502036488号