Codeforces Round #685 (Div. 2)

目录：

A. Subtract or Divide

签到

• 题设：t个用例，输入一个数n(1≤n≤109)。定义两种操作：
  1.n（n>1）自减1。
  2.n除以一个n和1以外的因数。
  求将数n变成1的最小操作数。
• 思路：粗略考虑：只要n为偶数，操作数必为2，n为奇数时，先自减成偶数，则操作数必为3。对n=1,2,3特判为0,1,2即可。
  ——AC代码

B. Non-Substring Subsequence

思维

• 题设：t个用例，输入字符串长度n，查询次数q，和字符串s。每次查询输入两个数L，R，代表待检测的字符串为母串的[ L , R ]区间内元素。定义查询规则：查询母串中是否存在长度大于2且不连续的子串，与带检测字符串相等，存在输出Yes，反之No。
• 思路：在带检测子串的左右两段遍历查询是否存在s[ L ]和s[ R ]即可。即遍历母串的[ 1 , L-1 ]中是否存在待检测串的首元素。或者[ R+1 , n ]中是否存在待检测串的尾元素。
  ——AC代码

C. String Equality

思维

• 题设：t个用例，输入字符串长度n，特殊值k，和两段长度相等字符串a，b。定义两种操作：
  1.交换：选定字符串a的两相邻字符进行交换，即swap（a[ i ],a[ i+1 ]）。
  2.替换：选定长度为k且全是某一字符c的字段，全部替换成c+1，即a[ i ] ~ a[ i-k+1 ] 替换为 a[ i ]+1 ~ a[ i-k+1 ]+1。
  （因输入字符全为小写字母，则z不可替换只能交换）
  若字符串a可通过若干操作变成字符串b，输出Yes，反之No。
• 思路：（来自jiangly）分别将字符串a，b中元素计数后，按字母序遍历，累计a，b串的元素个数suma，sumb。若出现1.suma<sumb，2.当前字母下两字符串中出现的数量，对k取摸的余数不相等。两种情况都说明b串中存在a串无法通过+1替换成的字符，判为No。
  ——AC代码

#include<bits/stdc++.h>
#define ll long long
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b/(__gcd(a,b))
#define rep(i,s,e) for(int i=s;i<e;i++)
#define fep(i,s,e) for(int i=s;i<=e;i++)
#define mem(a,n) memset(a, n ,sizeof(a))
#define Fill(a,n,b) fill(a,a+n,b)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
priority_queue <int,vector<int>,less<int> > Q;
const int INF= 0x3f3f3f3f;
const int maxn= 1e6+5;
char a[maxn],b[maxn];
int na[27],nb[27];
int main()
{
	IOS;
	int t,n,k;
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		cin>>a+1>>b+1;
		mem(na,0),mem(nb,0);
		for(int i=1;i<=n;i++)
		{
			na[a[i]-'a']++;
			nb[b[i]-'a']++;
		}
		int flag=1,sa=0,sb=0;
		for(int i=0;i<26;i++)
		{
			sa+=na[i];
			sb+=nb[i];
			if(sa<sb || na[i]%k!=nb[i]%k)
			{
				flag=0;
				break;
			}
		}
		if(!flag)	cout<<"No"<<endl;
		else		cout<<"Yes"<<endl;
	}
	return 0;
}

D. Circle Game

数学

• 题设：t个用例，输入d（d×d大小的正方形区域内圆的半径，圆域为1/4πd*d），k（每次移动的距离）(1≤k≤d≤105)。定义移动：（x , y）=> (x+k , y） 或 （x , y+k），不能出1/4圆的区域。两个玩家从原点依次进行移动，直到下一个玩家无法移动时获胜。
• 思路：思维，必赢问题。需要尽可能的靠近圆的边缘，且让总步数为奇（p1赢）偶（p2赢）。因为移动方式是正上和右，不能斜向，那么无论谁想靠近边缘，进行上或右的移动，对方都可以采取相反的移动方式，即让点重新回到了y=x这条直线上，可近似的看为“重新开始”，但是相比初态是少了一行一列，圆域半径也改变。
  所以可通俗化为，无论谁想赢，对方都可以采取相反的移动方式来抵消他上一步的移动，那么到最后，就是n次的抵消对面操作，类似阶梯式走法后，在最后一个方格中，看圆域是否包含此方格的三点，包含三点，则可行动两次，p2必赢，反之p1必赢。（如下图两种情况）
  

同样可引申到一个棋盘问题，若给一个行列都是偶数的正方形棋盘，双方下棋，无论谁开始，后手的一方都按中心对称复制上一方的操作，那么到最后，必是后手的一方获胜。但若此棋盘是奇数，存在绝对中心位置，那先手的一方第一步直接下在此最中心的点，后续同上，则最后必是先手的一方获胜。
——AC代码

#include<bits/stdc++.h>
#define ll long long
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b/(__gcd(a,b))
#define rep(i,s,e) for(int i=s;i<e;i++)
#define fep(i,s,e) for(int i=s;i<=e;i++)
#define mem(a,n) memset(a, n ,sizeof(a))
#define Fill(a,n,b) fill(a,a+n,b)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
priority_queue <int,vector<int>,less<int> > Q;
const int INF= 0x3f3f3f3f;
const int maxn= 1e5+5;
ll d,k;
int main()
{
	IOS;
	int t;
	cin>>t;
	while(t--)
	{
		cin>>d>>k;
		ll x=0;
		while((x+k)*(x+k)*2 <= d*d)
			x+=k;
		ll y=x+k;
		if(x*x+y*y <= d*d)
			cout<<"Ashish"<<endl;
		else		cout<<"Utkarsh"<<endl;
	}
	return 0;
}