A - Number Theory Problem
题意：问有多少个 < ，形如
的，能被7整除的数字
思路：从二进制看，7的二进制为111，的二进制是由k个1组成的，那么个数即n/3.
AC代码：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
vector<int> vec[maxn];
int main() {
int T, n, kase = 0;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
printf("Case #%d: %d\n", ++kase, n/3);
}
return 0;
}
B - Hemi Palindrome
C - Mr. Panda and Strips
题意：有一条彩带，现在要把这条彩带剪成每一段内颜色各不相同的几段，并选取两段粘成一条颜色也各不相同的彩带。问最终这条彩带有多长。
D - Ice Cream Tower
题意：冰淇淋塔。摆放的要求是下一层的冰淇淋球个数必须是上一层的两倍或两倍以上，问最多能组成多少个高度为k的冰淇淋塔。
思路：搜并不是很好搜。想到用二分答案来做。每次通过判断能否组成mid个高度为k的冰淇凌塔来约束答案的范围。
队友忘了注释掉freopen交了发Rutime error可海星…凭空增添罚时233…
AC代码：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 3e5 + 5;
typedef long long ll;
ll a[maxn];
vector<ll> vec[maxn];
int n, k;
bool chek(int mid) {
int cnt = 0;
for(int i = 0; i < mid; ++i) {
vec[i].clear();
vec[i].push_back(a[cnt]);
cnt++;
}
for(int j = 0; j < k-1; ++j) {
for(int i = 0; i < mid; ++i) {
while(cnt < n && a[cnt] < (vec[i][j] * 2))
cnt++;
if(cnt == n)
return false;
vec[i].push_back(a[cnt]);
cnt++;
}
}
return true;
}
int main() {
int T, kase = 0;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &k);
for(int i = 0; i < n; ++i)
scanf("%lld", &a[i]);
sort(a, a+n);
int l = 1, r = n / k, mid;
while( l <= r ) {
mid = (l+r) / 2;
if(chek(mid))
l = mid + 1;
else
r = mid - 1;
}
printf("Case #%d: %d\n", ++kase, r);
}
return 0;
}
E - Bet
题意：n组比赛，你可以赌哪组获胜。若赢，获得c + b / a * c的钱，如果输了，那么你将输c元钱。在确保一定能得到比原来钱数多的前提下，最多可以赌多少个队获胜（你下注的队伍至少有一支会赢得比赛）。
思路：假设有1元钱，在第i组比赛下赌注，要确保比原来钱数多，那么应该下注c元满足式子c + b / a * c > 1 ，即 c > a / (a + b). 在下了赌注c之后，剩余钱数为1-c，问题转化为对a / (a + b) 求和，使sum < 1 的情况下，选择尽可能多的比赛下注，所以只需要把a / (a + b) 求出来排序即可。
还写了几百行的高精度……其实long double就能过，坑。
AC代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
long double p[105];
int main()
{
int T, n;
int kase = 0;
scanf("%d", &T);
long double a, b;
char ch;
while(T--) {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
cin >> a >> ch >> b;
p[i] = a / (a + b);
}
sort(p, p+n);
long double sum = 0;
int ans = 0;
for(int i = 0; i < n; i++) {
sum += p[i];
//cout << p[i] << endl;
if(sum >= (long double)1.0) {
break;
}
ans++;
}
printf("Case #%d: %d\n", ++kase, ans);
}
return 0;
}
F - Mr. Panda and Fantastic Beasts
后缀数组
G - Pandaria
H - Great Cells
I - Cherry Pick
J - Mr.Panda and TubeMaster
K - Justice Rains From Above
L - World Cup
Gym - 101194L
题意：足球比赛得分模拟。
思路：DFS跑出来所有的得分可能的情况，然后对于输入的得分，能找到1个就是“Yes”，找到多个“No”，找不到“Wrong Scoreboard”。队友一开始写搓，让第一位1000，第二位100，第三位*10来存数字，可是如果给不可能出现的比较大的数字就会出问题，改了vector存过了。
AC代码：队友写的，这个花括号有点邪教（ˊ_>ˋ）
# include <iostream>
# include <map>
# include <cstdio>
# include <vector>
using namespace std;
map<vector<int>, int> result;
void init(int, vector<int> );
void ans(int, int, vector<int>);
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
vector<int> vec;
for(int i = 1; i <= 4; i++)
vec.push_back(0);
init(1, vec);
int T, cas = 1, temp;
cin >> T;
while(T--)
{
vector<int> res;
for(int i = 1; i <= 4; i++)
{
cin >> temp;
res.push_back(temp);
}
if(result[res] == 1)
cout << "Case #" << cas++ << ": Yes" << endl;
else if(result[res] == 0)
cout << "Case #" << cas++ << ": Wrong Scoreboard" << endl;
else
cout << "Case #" << cas++ << ": No" << endl;
}
}
void init(int team, vector<int> vec)
{
if(team == 4)
result[vec]++;
else
ans(team, team + 1, vec);
}
void ans(int baseTeam, int team, vector<int> vec)
{
if(team == 4)
{
vec[team - 1] += 3;
init(baseTeam + 1, vec);
vec[team - 1] -= 3;
vec[baseTeam - 1] += 3;
init(baseTeam + 1, vec);
vec[baseTeam - 1] -=3;
vec[baseTeam - 1] += 1;
vec[team - 1] += 1;
init(baseTeam + 1, vec);
vec[baseTeam - 1] -= 1;
vec[team - 1] -= 1;
}
else
{
vec[team - 1] += 3;
ans(baseTeam, team + 1,vec);
vec[team - 1] -= 3;
vec[baseTeam - 1] += 3;
ans(baseTeam, team + 1, vec);
vec[baseTeam - 1] -= 3;
vec[baseTeam - 1] += 1;
vec[team - 1] += 1;
ans(baseTeam, team + 1, vec);
vec[baseTeam - 1] -= 1;
vec[team - 1] -= 1;
}
}
网友评论