Codeforces Round 883 (Div. 3)
A. Rudolph and Cut the Rope
题意：有一颗糖果在连在绳子上，求剪短多少根绳子，他能落地
思路：只要绳子长度比钉子高度大就不用减
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, res = 0;
cin >> n;
while (n--) {
int a, b;
cin >> a >> b;
if (a > b) {
res++;
}
}
cout << res << "\n";
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
B. Rudolph and Tic-Tac-Toe
题意：井字棋判断谁赢谁输
思路：8种情况，判断就行
#include <bits/stdc++.h>
using namespace std;
char mp[4][4];
void solve() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cin >> mp[i][j];
}
}
for (int i = 0; i < 3; i++) {
bool x = true, y = true;
for (int j = 1; j < 3; j++) {
if (x && mp[i][j] != mp[i][j - 1]) {
x = false;
}
if (y && mp[j][i] != mp[j - 1][i]) {
y = false;
}
if (!x && !y) break;
}
if (x && mp[i][0] != '.') {
cout << mp[i][0] << "\n";
return;
}
if (y && mp[0][i] != '.') {
cout << mp[0][i] << "\n";
return;
}
}
bool w = true;
for (int i = 1; i < 3; i++) {
if (mp[i][i] != mp[i - 1][i - 1]) {
w = false;
break;
}
}
if (w && mp[1][1] != '.') {
cout << mp[1][1] << "\n";
return;
}
w = true;
for (int i = 1; i < 3; i++) {
if (mp[i][2 - i] != mp[i - 1][3 - i]) {
w = false;
break;
}
}
if (w && mp[1][1] != '.') {
cout << mp[1][1] << "\n";
return;
}
cout << "DRAW\n";
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
C. Rudolf and the Another Competition
题意：判断这个人在第几名
思路：优先级：题目数>罚时(重写cmp)老顽固真不喜欢运算符重载
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Stu {
int num;//题数
int time;//罚时
int c;//那个b
};
bool cmp(Stu c, Stu b) {
if (c.num != b.num) {
return c.num > b.num;
}
if (c.time != b.time) {
return c.time < b.time;
}
return c.c > b.c;
}
void solve() {
int n, m, h;
cin >> n >> m >> h;
vector<Stu> a(n + 1);
for (int i = 1; i <= n; i++) {
vector<int> b(m + 1);
for (int j = 1; j <= m; j++) cin >> b[j];
sort(b.begin() + 1, b.end());
int cnt = 0, sum = 0, cur = 0;
for (int j = 1; j <= m; j++) {
if (cur + b[j] <= h) {
cnt++;
cur += b[j];
sum += cur;
}
}
a[i] = {cnt, sum, 0};
if (i == 1) a[i].c = 1;
}
sort(a.begin() + 1, a.end(), cmp);
for (int i = 1; i <= n; i++) {
if (a[i].c == 1) {
cout << i << endl;
return;
}
}
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
D. Rudolph and Christmas Tree
题意：有n个等腰三角形，有重叠，求他们的面积
思路：总面积-重叠的面积
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 10;
int a[MAX];
void solve() {
int n;
double h, d;
cin >> n >> d >> h;
double s = h * n * d / 2;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
double res = 0;
for (int i = 0; i < n - 1; i++) {
if (a[i] + h > a[i + 1]) {
res += (double) (a[i] + h - a[i + 1]) * (a[i] + h - a[i + 1]) * d / (2 * h);
}
}
printf("%.6lf\n", s - res);
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
E1. Rudolf and Snowflakes (simple version)
题意：求n=k1+k2+..+k^x
思路：简单版直接爆爆爆爆力
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
int n;
cin>>n;
for(int i=2;i<=n;i++){
int sum = 1+i+i*i ;
int temp = i*i ;
if (sum > n) break;
while (sum < n)
{
temp *= i;
sum += temp;
}
if (sum == n)
{
cout << "YES\n" ;
return;
}
}
cout<<"NO\n";
}
signed main()
{
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
E2. Rudolf and Snowflakes (hard version)
他甚至爆unsigned long long 只能开int_128(shu)
题意：求n=k1+k2+..+k^x（变的是n的范围，所以暴力直接达咩）
$$
很明显等比数列求和:n=a_1*(1-k^x)/(1-q);
$$
思路：n<2e18最大也就2^64,x遍历[2,64],k遍历[2,1e9] (二分遍历)
二分板子：
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
#include <bits/stdc++.h>
using namespace std;
#define int long long
int check(int k, int x) {//k底数x指数
__int128 cur = 1, res = 1;
for (int i = 1; i <= x; i++) {
cur *= k;
res += cur;
if (res >= 2e18) return 2e18;
}
return (int) (res);
}
void solve() {
int n;
cin >> n;
for (int x = 2; x <= 63; x++) {
int l = 2, r = 1e9;
while (l < r) {
int mid = (l + r) >> 1;
int t = check(mid, x);
if (t >= n)
r = mid;
else
l = mid + 1;
}
if (check(l, x) == n) {
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}