Всем привет, добро пожаловать в тему codeforces.
Выбранный сегодня вопрос — это вопрос D Конкурса 1451, интересный и простой.Теория псевдоигрВопрос, через аудиторию проходит 3203 человека. Сложность не слишком высокая, все еще думает, думает, яма не большая, очень дружелюбная.
Ссылка на тему: https://codeforces.com/contest/1451/problem/D
Без лишних слов, перейдем непосредственно к проблеме.
смысл названия
Жили-были два человека, одного звали Уткарш, а другого Ашиш. Эти два имени выглядят немного странно. Я думаю, это из-за Лао Мао-цзы. Эти два имени часто появляются в вопросах Лао Мао-цзы. Может быть, это похоже на наши имена Сяохун и Сяомин.
Эти двое играют в игру с перемещением фигур на 2D-доске, начиная с исходной точки, причем Ашиш идет первым. Вы можете переместить пешку вверх или вправо на расстояние k единиц за раз. Оба ходят попеременно, и в игре оговаривается, что расстояние между пешками и началом координат должно быть меньше d. Проиграл, когда кто-то не может переместить кусок.
Теперь дайте d и k и спросите, кто победит, если у них обоих высокий IQ.
Образец
Сначала введите целое число t, которое представляет количество групп тестовых данных. Затем введите t строк, каждая строка представляет образец. Введите два целых числа в каждую строку, обозначающие d () и к ().
Попросите вывести имя победителя.
Пояснение к первому примеру:
Мы видим, что, когда два по очереди совершают раунд, пепел, должно быть, некуда идти, поэтому победитель - уткарш.
отвечать
Как только мы получим это в свои руки, мы, естественно, подумаем, что это проблема теории игр.
На самом деле, это выглядит очень похоже, два человека по очереди играют в игру, включая некоторые детали игры,Ходы по очереди и проигрыш тех, кто не может сделать ход, соответствуют характеристикам задач теории игр.. Если мы начнем с теории игр, мы подумаем о преобразовании между определенным проигрышным состоянием и определенным выигрышным состоянием.
Если мы проанализируем это дальше, нетрудно придумать идеи. Мы представляем себе эту плоскость как область, покрытую веерной формой.Для точек, близких к веерообразной границе, только зная координаты, мы можем вычислить количество шагов, необходимых, чтобы добраться сюда из начала координат, и мы знаем число шагов, естественно. Какой из них оказался в этой точке.
так что мыПосле первого определения результата границы мы можем постепенно вернуться к внутреннему слою.и, наконец, решить исходное состояние. Переход этого вывода очень легко понять.Для каждой точки он имеет не более двух путей вправо и вверх.Для человека, который принимает решение в этой точке, до тех пор, пока одно из этих двух решений может привести к его победе состояние, то эта точка, естественно, является обязательным состоянием. На самом деле это немного идеи динамического программирования, С помощью этого метода мы можем решить состояние каждой достижимой точки на плоскости.
Кажется, что эта задача решена, очень простая, но после небольшого анализа мы обнаружим, что это невозможно. Причина очень проста, потому чтоСложность слишком велика, истечет время ожидания.
В крайних случаях, когда величина d равна 1e5 и k=1, количество точек, которые нам необходимо учитывать, должно быть порядка 1e10, что, очевидно, неприемлемо. Есть ли другой способ, кроме этого?
Много раз кажется, что проблему трудно решить, и часто мы идем по неверному пути. Мы долго думали, как сделать рекурсию и как получить статус каждой точки, но на самом деле эта идея изначально была неправильной. В это время нам нужно отложить эти мысли в сторону и вернуться к самой проблеме.
Ставим себя на место первого игрока, какую стратегию придумываем? Вы обнаружите, что кажется, что на какое-то время нет особенно хорошей стратегии? Но что, если мы запасной игрок? Вы обнаружите, что хороших стратегий может и не быть, но существуют плохие рутины. Поскольку этот сектор представляет собой четверть круга, он симметричен. так что мы можемИспользование опоздавшего, чтобы отразить действие первопроходца, так что мы можем гарантировать, что наша точка всегда попадает на диагональ. Таким образом, пока первая рука может двигаться вперед, вторая рука должна двигаться. То есть следуйте маршруту, показанному ниже.
Не будет ли он первым, кто проиграет? Не совсем так, есть исключения. То есть, когда задняя рука не может вернуться к косой черте, то есть ((x+1)k, xk) меньше, чем d от начала координат, и ((x+1)k, (x+1)k ) больше, чем d.
Таким образом, мы можем легко написать код:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include "time.h"
#include <functional>
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
const int N=1000050;
const long long Mod=1000000007;
using namespace std;
int main() {
int t;
scanf("%d", &t);
rep(z, 0, t) {
long long d, k;
scanf("%lld%lld", &d, &k);
int n = d / (sqrt(2) * k);
long long x = (n+1) * k;
long long y = n * k;
// 判断是否会出现((x+1)k, xk)可行的情况
if (x * x + y * y > d * d) {
puts("Utkarsh");
}else {
puts("Ashish");
}
}
return 0;
}
Здесь есть небольшая яма, т.к. диапазон d равен 1e5, то когда мыПри вычислении расстояния квадрат превысит диапазон int из-за использования квадратов., поэтому его нужно изменить на long long.
На этом проблема заканчивается, и мы также видим, что сама задача несложная, но решение не так просто придумать. Я лично нахожу это довольно интересным, и я надеюсь, что вам всем это тоже понравится.
Вот и все, что касается сегодняшней статьи, и я искренне желаю вам удачи каждый день. Если вам все еще нравится сегодняшний контент, пожалуйста, зайдите на одинТройная поддержкабар~(Нравится, подписывайтесь, делайте репост)