今天是2021.10.1，国庆节。祝福伟大的祖国。
上午刷了两道，下午刷了一道，晚上刷了三道。
507.B. Amr and Pins （思维） 题意：
一个圆形，可沿边缘的一点任意角度旋转。问最少旋转几次，能将圆心从(a1,a2)旋转至(b1,b2)。
思考：圆心在(x,y)点的圆，圆心可以旋转至2r范围内的任意一点。
所以将沿目标圆心和当前圆心的连线旋转，每次走2r。就是看2r的多少倍能够不小于两点间的距离。
注意int相乘加ll。
Code：const int N = 200010, mod = 1e9+7;
int T, n, m;
int main(){
int r,a1,a2,b1,b2;
cin>>r>>a1>>a2>>b1>>b2;
double dis=(ll)(a1-b1)*(a1-b1)+(ll)(a2-b2)*(a2-b2); //int类型相乘加ll
int cnt=0;
double t=0;
while(t*t
1370.C. Number Game （博弈论）
题意：
给出一个数n，两个人轮流操作，不能操作者败。
操作1：将n除以一个不为1的奇因数（包括其本身）；
操作2：将大于1的n减1。
A先手，两者操作都最优，问最终谁能胜？
思考：
如果n是奇数，那么直接除以其本身，所得为1，B无法再操作，A胜；
否则n为偶数：
- 若n没有奇因子，即n为2^x次方（特判n=2），那A只能进行1操作，将n变为奇数，B胜；
- 否则，n含奇因子：
因为 奇数*奇数=奇数，所以可以一次将n的所有奇因子都拿完。
1、如果去掉奇因子后，n变成2^x，即若n%4=0，那么A胜；
2、去掉奇因子，n不能变成2^x，即n变成2，n=2*p（p为奇数）：
如果p为质数的话，B胜；
但是如果p不为质数，那么p就可以分解为 质数p' * 奇数，把奇数拿去，A胜。
Code：
const int N = 200010, mod = 1e9+7;
int T, n, m, a[N];
bool prim(int n)
{
if(n==1||n==0) return 0;
for(int i=2;i<=n/i;i++){
if(n%i==0) return 0;
}
return 1;
}
int main(){
cin>>T;
while(T--)
{
cin>>n;
if(n%2||n==2||n==1){
if(n==1) cout<<"FastestFingern";
else cout<<"Ashishgupn";
continue;
}
int t=1,flag=0;
for(int i=1;i<=31;i++){
t*=2;
if(t==n) flag=1;
if(t>n) break;
}
if(flag) cout<<"FastestFingern";
else{
if(n%4==0) cout<<"Ashishgupn";
else{
if(prim(n/2)) cout<<"FastestFingern";
else cout<<"Ashishgupn";
}
}
}
return 0;
}
1363.B. Subsequence Hate （思维，前缀和）
题意：
给出一个01串，经过若干次01转换后，要求最终的01串不含有如下子序列：010,101。
求最少的转换次数。
思考：
不要去想着如何替换成目标序列，而是从最终的序列形式出发：
如果最终的01串不含有010,101这样的子序列，那么最终的序列形式一定是这样的：00001111…或111110000…或111111…或00000…。
于是题目就完全转化了！
就是把原来的01串转化成这样的01串，求最小的操作次数。
前缀和维护当前位置前面1的个数，遍历所有位置就行了。
Code：
const int N = 200010, mod = 1e9+7;
int T, n, m;
string a;
int s[N];
int main(){
cin>>T;
getline(cin,a);
while(T--)
{
getline(cin,a);
n=a.size();
for(int i=1;i<=n;i++)
{
s[i]=s[i-1];
if(a[i-1]=='1') s[i]++;
}
int ans=1e9;
for(int i=0;i<=n;i++)
{
ans=min(ans,s[i]+n-i-(s[n]-s[i]));
ans=min(ans,i-s[i]+s[n]-s[i]);
}
cout<
1324.D. Pair of Topics （思维，二分）
题意：
给出长度为n的两个序列
a
,
b
a,b
a,b，问有多少对
i
,
j
i,j
i,j，满足
i
<
j
i
b
i
+
b
j
ai+aj>bi+bj
ai+aj>bi+bj ？
思考：
a
i
+
a
j
>
b
i
+
b
j
ai + aj > bi + bj
ai+aj>bi+bj
→
a
i
−
b
i
+
a
j
−
b
j
>
0
→ ai-bi + aj-bj > 0
→ai−bi+aj−bj>0
将两个序列合并成一个：
c
i
=
a
i
−
b
i
ci = ai - bi
ci=ai−bi，那么题目就转化为：
有多少对
i
,
j
i,j
i,j，满足
i
<
j
i
0
ci + cj >0
ci+cj>0 ？
先将c数组从小到大排序，遍历每个位置，二分找到第一个满足的位置，那么此位置后面的所有位置都满足了，ans累加后面的位置数。
Code：
const int N = 200010, mod = 1e9+7;
int T, n, m, a[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
int x;cin>>x;
a[i]-=x;
}
sort(a+1,a+n+1);
a[n+1]=1e9;
ll ans=0;
for(int i=1;i<=n;i++)
{
int l=i+1,r=n+1;
while(l>1;
if(a[mid]+a[i]>0) r=mid;
else l=mid+1;
}
if(l==n+1) continue;
ans+=n-l+1;
}
cout<
1365.C. Rotation Matching （思维）
题意：
给出长度为n的两个n的全排列，可以将两个序列像齿轮一样左右转动任意位置。问最多能使多少位置上下相同？
思考：
序列长度n<2e5，暴力做法不可行。
我们可以只转动下面的序列，使之与上面的序列匹配。
记录下a序列中的每个数在b序列中的位置。遍历计算b中的所有位置要向右转动转到其对应位置所需要的转动次数。
所有转动次数中出现最多的出现次数就是最大匹配数。
Code：
const int N = 200010, mod = 1e9+7;
int T, n, m, a[N];
int f[N];
int main(){
Ios;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
int x;cin>>x;
mp[x]=i;
}
int ans=0;
for(int i=1;i<=n;i++)
{
a[i]=mp[a[i]];
f[(i-a[i]+n)%n]++;
ans=max(ans,f[(i-a[i]+n)%n]);
}
cout<
1374.D. Zero Remainder Array （思维）
题意：
给出长度为n的序列，一个数x（初始为0），可以执行以下操作：
1.选择一个位置i，将 ai 加上 x，同时 x++（每个位置最多执行一次该操作）；
2.只是将x++。
给出整数k，问最少执行多少次操作，能够使得序列a中的所有元素都是k的倍数？
思考：
无论执行那种操作，x都会++。
因为操作1每个元素最多只能执行一次，而x始终在增加，最终要变成k的倍数，所以如果有与最近的倍数差值相等的元素，需要变成下一个倍数。
所需要的最大的x就是最终需要的操作数。
注意：
因为有多组数据，所以每次的map需要初始化。如果用unordered_map的话，建立的时候太耗时了，就T掉了。而map的建立所用的时间较短些。
所以如果有多组测试数据需要初始化map的题，都用map较好。
Code：
const int N = 200010, mod = 1e9+7;
int T, n, m, a[N];
signed main(){
Ios;
cin>>T;
while(T--)
{
int k;
cin>>n>>k;
map f;
ll ans=0;bool flag=0;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
if(x%k==0) continue;
flag=1;
int p=k-x%k;
if(f[p]) f[p]+=k;
else f[p]=p;
ans=max(ans,f[p]);
}
cout<
这几个题都有一个特点，就是将原本的题意转化，挖掘深层的含义。
明天加油！
