A 在一个方格可以多次，那么可以在相邻的两个方格来回走，然后会在左右或者的一个方向剩下几步，判断是否越边界就可以了，除此之外还要特判x1== x2或者y1== y2(刚才那样有一个前提条件，那个方向上得能迈出去，感谢样例）
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
typedef long long ll;
int t,a,b,c,d,x,y,x1,x2,y1,y2;
int main()
{
cin>>t;
while(t--)
{
cin>>a>>b>>c>>d>>x>>y>>x1>>y1>>x2>>y2;
if(x==x1&&x1==x2&&(a||b))
{
puts("No");
continue;
}
if(y==y1&&y==y2&&(c||d))
{
puts("No");
continue;
}
if(a>=b) a=a-b,b=0;
else b=b-a,a=0;
if(c>=d) c=c-d,d=0;
else d=d-c,c=0;
if(x-x1>=a&&x2-x>=b&&y-y1>=c&&y2-y>=d) puts("Yes");
else puts("No");
}
return 0;
}
B 相同颜色的数的gcd必须大于1，那么我们可以给有形同质因子的数全部染上相同的颜色，然后就分解质因子呗，第11个质因子是31,31*37>1000了，所以前11个质质数完全可以处理1000以内的所有合数。给每个出现的质数一个颜色，每个合数中选一个质因数染色
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
typedef long long ll;
int t,n;
int a[N],c[N];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int num[10000]={0},m=1;//num标记质因数的颜色
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
for(int j=2;j*j<=a[i];j++)//分解质因数
{
if(a[i]%j==0)
{
if(num[j]) c[i]=num[j];
else c[i]=num[j]=m++;
break;
}
while(a[i]%j==0) a[i]/=j;
}
}
printf("%d
",m-1);
for(int i=1;i<=n;i++) printf("%d ",c[i]);
puts("");
}
return 0;
}
C 根据定义si=s[k+i],那么就有
s1=s[1+k]=s[1+2k]…
sn=s[n-k]=s[n-2k]…
然后还得是回文串 s1=sn，联立一下这些位置必须相等，找最多的字母次数，总的这些位置的数量减它就是这些位置的最小变化，其他位置一样，k是奇数还需要特判一下。
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
typedef long long ll;
int t,n,k;
int a[N],c[N];
char s[N];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d %d ",&n,&k);
scanf("%s",s+1);
int ans=0;
for(int i=1;i<=(k+1)/2;i++)
{
int num[30]={0};//别忘了清0
if((k&1)&&i==(k+1)/2)//这个时候的i和k-i+1相等，所以得特判
for(int j=i;j<=n;j+=k) num[s[j]-'a']++;
else
{
for(int j=i;j<=n;j+=k) num[s[j]-'a']++;
for(int j=k-i+1;j<=n;j+=k) num[s[j]-'a']++;
}
int sum=0,m=0;
for(int i=0;i<26;i++) m=max(num[i],m),sum+=num[i];
ans+=(sum-m);
}
printf("%d
",ans);
}
return 0;
}
D 他的错误dp是因为&过程中的最大值不一定能使后面的&操作最大
要使最优解与他输出的差值为k，感觉两个值分别等 k和0是比较好构造吧，所以我的目的是使最优解为k，而dp输出0，假设点[n,m]位置为k,为方便构造减少分支情况就把所有情况都从一个方向来，就令[n-1,m]为0,这个方向一定为0。
接下来就是使 dp[n][m-1]&k 等0，而[n,m-1]可以得到的较小的值&k等k，什么值&k等0呢，k按位取反（令他为m）。
然后看一下m的范围是3e5是不是一定比1e5范围的k大，3e5以内的数二进制最多有19位，而1e5以内最多有17位，所以k的18位上一定是0，那么m的18位就一定是1了，所以m一定大于k 。
所以就可构造[n-1,m-1]为m，[n,m-2]为k，令s=2^18-1（二进制下各位都是1，小于3e5的最大值,&任何数的结果都等原数)，其他位所有数都为s，这样两行三列足矣，所以构造的矩阵就是 s m 0
k s k
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
typedef long long ll;
int t,n,k,m,s;
int a[N],c[N];
char s[N];
int main()
{
cin>>k;
for(int i=0;i<20&&(m+(1<<i)<3e5);i++)
{
s+=(1<<i);
if((k&(1<<i))==0&&m+(1<<i)<3e5)
m+=(1<<i);
}
cout<<2<<' '<<3<<endl;
cout<<s<<' '<<k<<' '<<0<<endl;
cout<<m<<' '<<s<<' '<<k;
return 0;
}
第一次过四题体验挺好hh，E太难了，溜了