Problem A. Alice and Bob
题意：告诉你两堆石子的数量，每次可以从一堆拿k（k>0）个且从另一堆那s*k（可为0）个。每个人都采取最优的方法，问最后谁赢。
思路：这个题想了一会就是去找必败态，脑跑找了几组后发现没规律就准备打表，但是找错了一组（14，19），正解应该是（14，20），导致打表都打错了。。。
假设（x,y）是一个必败态，那么可由（x,y）->(x1,y1)就不是必败态，所以由题意可得非必败态就是（x+k,y+s*k）或者（x+s*k，y+k），打表即可。
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 5e3 + 10;
bool sg[N][N];
int main() {
//打表
for (int i = 0; i <= 5000; i++) {
for (int j = 0; j <= 5000; j++) {
if (!sg[i][j]) {
for (int k = 1; k + i <= 5000; k++) {
for (int s = 0; s * k + j <= 5000; s++) {
sg[k + i][s * k + j] = 1;
}
}
for (int k = 1; k + j <= 5000; k++) {
for (int s = 0; s * k + i <= 5000; s++) {
sg[s * k + i][k + j] = 1;
}
}
}
}
}
int t;
cin >> t;
int n, m;
while (t--) {
cin >> n >> m;
if (sg[n][m]) cout << "Alice" << endl;
else cout << "Bob" << endl;
}
return 0;
} Problem B. Ball Dropping
题意：告诉你半径r、上底a、下底b、高度h，问是否会被卡住，否输出Drop，是输出Stuck和圆心到下底的距离。
思路：首先，2*r<b不会被卡住。如果卡住了，我们通过圆心向右做一条辅助线到等腰梯形腰上，并通过相似三角形求出这段长度，再通过相似求出圆心到下底的距离。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3 + 5;
const double eps = 1e-6;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
double r, a, b, h;
cin >> r >> a >> b >> h;
if(2*r<b) {
cout << "Drop" << endl;
}
else {
double c=sqrt((a-b)/2*(a-b)/2+h*h);
double d = c * r / h;
double e = d - b / 2;
double H = h * e / ((a - b) / 2);
cout << "Stuck" << endl;
if(H>=eps) printf("%.10lf\n", H);
}
return 0;
} Problem C. Cut the Tree Problem D. Determine the Photo Position
题意：给你n*n的区域，0代表空位，1代表学生，现在有m个老师，问这m个老师加入这片区域有多少种方法，前提m个老师必须是横着连续一排。
思路：这场的签到题，没啥好说的。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3 + 5;
char a[N][N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n;i++){
for (int j = 1; j <= n;j++){
cin >> a[i][j];
}
}
string s;
cin >> s;
ll sum = 0;
for (int i = 1; i <= n;i++){
int cnt = 0;
for (int j = 1; j <= n;j++){
if(a[i][j]=='1') {
cnt = 0;
}
else {
cnt++;
if(cnt>=m) {
sum++;
}
}
}
}
cout << sum << endl;
return 0;
} Problem E. Escape along Water Pipe Problem
Problem F. Find 3-friendly Integers
题意：给你一个区间[L,R]，问这个区间内有多少个数能被3整除或者这个数的子串能被3整除，其中0 mod 3 = 0。
思路：通过观察可以发现当这个数大于等于100那它必定满足题目要求，那么我们只要判断一下小于100的即可。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3 + 5;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t; cin >> t;
while(t--)
{
ll l, r;
cin >> l >> r;
ll sum = 0;
if(r<=100)
{
for (ll i = l; i <= r;i++) {
int temp=i;
if(temp%3==0) {
sum++;
//cout << temp << endl;
continue;
}
while (temp)
{
if(temp%3==0) {
sum++;
break;
}
ll tmp = i % 10;
if (tmp == 0 || (tmp % 3 == 0))
{
sum++;
//cout << i << endl;
break;
}
temp/=10;
}
}
}
else {
if(l<=100) {
sum += r - 100;
for (ll i = l; i <= 100;i++) {
int temp=i;
if(temp%3==0) {
sum++;
continue;
}
while (temp)
{
if(temp%3==0) {
sum++;
break;
}
ll tmp = i % 10;
if (tmp == 0 || (tmp % 3 == 0))
{
sum++;
break;
}
temp/=10;
}
}
}
else {
sum += r - l + 1;
}
}
cout << sum << endl;
}
return 0;
} Problem G. Game of Swapping Numbers
题意：给你长度为n的序列a和b，你可以任意交换a中两个数k次，问所有ai-bi的绝对值和的最大值是多少。
思路：先去掉绝对值，那ai和bi一定有一正一负，因为是计算绝对值，交换对应的ai和bi不影响他们的结果，所以我们先通过交换优先保证ai>bi，计算出当前差值。然后我们通过对a序列从小到大排序，对b序列从大到小排序，将a中最小的与b中最大的交换位置，此时结果变优了2*(b[i]-a[i])，因为我们相当于改变了他们的符号，从正变负从负变正，所以要乘上2。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
const double eps = 1e-6;
int a[N], b[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];
ll ans = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] < b[i])
swap(a[i], b[i]);
ans += abs(a[i] - b[i]);
}
if (n == 2)
{
if (k % 2)
cout << abs(a[1] - b[2]) + abs(a[2] - b[1]) << endl;
else
cout << abs(a[1] - b[1]) + abs(a[2] - b[2]) << endl;
return 0;
}
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + n, greater<int>());
for (int i = 1; i <= n && i <= k; i++)
{
if (b[i] < a[i])
break;
ans += 2 * (b[i] - a[i]);
}
cout << ans << endl;
return 0;
} Problem H. Hash Function Problem I. Increasing Subsequence
Problem J. Journey among Railway Stations
Problem K. Knowledge Test about Match
京公网安备 11010502036488号