1.CF 1550C 2.CF 1551D1 3.CF 1551D2 4.CF 1203C 5.CF 1203B
这几篇题解都是我从自己的CSDN里搬来的，不然显得我没打过ACM www
求一个数组中满足 (从目标数组里任选三点，满足三个曼哈顿距离没有加减关系) 的连续子区间数量，定义长度为1和2的数组也满足这一条件
从上面可以知道如果有三个点满足中间的点不被两边的点包含就符合 另外讨论三个以上的点 四个点的时候 可以看成三个点再加上一个点 所以前面三个点是满足关系的 然后我们只要关注最后一个点怎么插
可以看出要满足的话只有边上两个点把中间两个点包起来的时候。四个点以上我就不画了，因为无论如何都是找不到满足这一条件的情况，所以我们就直接暴力枚举首个点 判断后续长度为3和4子区间是否满足这一条件即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int d[maxn];
int main(){
int t,n,tmp,i,j,k,ans;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
ans=2*n-1;
for(i=0;i<n;i++){
scanf("%d",&d[i]);
}
for(i=0;i<n-3;i++){
if((d[i+1]>d[i]&&d[i+1]>d[i+2])||(d[i+1]<d[i]&&d[i+1]<d[i+2])){
ans++;
if( ((d[i+3]<d[i+1]&&d[i+3]>d[i+2])||(d[i+3]>d[i+1]&&d[i+3]<d[i+2])) && ((d[i]<d[i+1]&&d[i]>d[i+2])||(d[i]>d[i+1]&&d[i]<d[i+2])) )
ans++;
}
}
if(n>=3){
if((d[n-2]>d[n-3]&&d[n-2]>d[n-1])||(d[n-2]<d[n-3]&&d[n-2]<d[n-1]))
ans++;
}
printf("%d\n",ans);
}
return 0;
}
在NxM的棋盘上摆1x2的多米诺骨牌，判断是否能在摆下k的水平块的前提下摆满整个棋盘
刚刚开始的思路是用某些小块固定出大块，然后发现思路不对，很难考虑完全。然后我就去看官方题解了... 题解的大致意思是按n和m的奇偶分成四种情况
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
scanf("%d",&t);
int n,m,k;
int kk;
while(t--){
scanf("%d%d%d",&n,&m,&k);
kk=n*m/2-k;
if(n%2&&m%2){
printf("NO\n");
continue;
}
else if(n%2){
k-=m/2;
}
else if(m%2){
kk-=n/2;
}
if(k<0||k%2||kk<0){
printf("NO\n");
continue;
}
printf("YES\n");
}
return 0;
}
上一道题目的构造版本。
思路和上面以提是一样的，但是构造思路很麻烦，看代码吧，以为涉及到字符串，所以用了我比较熟悉的python写，写的是十分的冗长...
t=int(input())
h1="ac"
h2="bd"
s1="ef"
s2="gh"
for aslkfjalkfj in range(t):
n,m,k=[int(i) for i in input().split()]
kk=n*m//2-k
if(n%2 and m%2):
print("NO")
continue
elif n%2:
k-=m//2
elif m%2:
kk-=n/2
if(k<0 or k%2 or kk<0):
print("NO")
continue
print("YES")
mp=['']*n
x=0
y=0
tmp=0
if(n%2):
while k>0:
mp[y]+=h1[tmp]+h1[tmp]
mp[y+1]+=h2[tmp]+h2[tmp]
tmp=1-tmp
x+=2
k-=2
if(x==m):
x=0
y+=2
while kk>0:
if y>0:
if mp[y-1][x]==s1[tmp]:
tmp=1-tmp
mp[y]+=s1[tmp]+s2[tmp]
mp[y+1]+=s1[tmp]+s2[tmp]
tmp=1-tmp
x+=2
kk-=2
if(x==m):
x=0
y+=2
mp[n-1]='xxyy'*(m//4)+'x'*(m%4)
if(m%2):
while k>0:
mp[y]+=h1[tmp]+h1[tmp]
mp[y+1]+=h2[tmp]+h2[tmp]
tmp=1-tmp
x+=2
k-=2
if(x==m-1):
x=0
y+=2
while kk>0:
if y>0:
if mp[y-1][x]==s1[tmp]:
tmp=1-tmp
mp[y]+=s1[tmp]+s2[tmp]
mp[y+1]+=s1[tmp]+s2[tmp]
tmp=1-tmp
x+=2
kk-=2
if(x==m-1):
x=0
y+=2
x="xy"
for i in range(0,n,2):
mp[i]+=x[tmp]
mp[i+1]+=x[tmp]
tmp=1-tmp
else:
while k>0:
mp[y]+=h1[tmp]+h1[tmp]
mp[y+1]+=h2[tmp]+h2[tmp]
tmp=1-tmp
x+=2
k-=2
if(x==m):
x=0
y+=2
while kk>0:
if y>0:
if mp[y-1][x]==s1[tmp]:
tmp=1-tmp
mp[y]+=s1[tmp]+s2[tmp]
mp[y+1]+=s1[tmp]+s2[tmp]
tmp=1-tmp
x+=2
kk-=2
if(x==m):
x=0
y+=2
for i in mp:
print(i)
找到输入n个数的最大公因子，再求出这个公因子又几个因数
div3水题，连续gcd就可以求出最大公因子 然后因数分解只需要用试除法即可 时间复杂度是够的(不会分析gcd的时间复杂度
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b){
return b==0?a:gcd(b,a%b);
}
int main(){
int n;
scanf("%d",&n);
long long i,j,k;
long long tmp,igcd;
scanf("%lld",&igcd);
for(i=1;i<n;i++){
scanf("%lld",&tmp);
igcd=gcd(igcd,tmp);
}
long long ans=0;
// qiu igcd de yin shu
for(i=1;i<=sqrt(igcd);i++){
if(igcd%i==0){
ans+=2;
if(i*i==igcd)
ans--;
}
}
printf("%lld",ans);
return 0;
}
给一组边，判断是否能用所给边构造出的所有矩形面积相等。
贪心，要想所有矩形面积相等，必须从最长和最短边里选
#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
struct node{
int val,num;
};
vector<node>vtmp;
int main(){
int t;
scanf("%d",&t);
int n,i,j,k,tmp,flag;
while(t--){
mp.clear();
vtmp.clear();
scanf("%d",&n);
for(i=0;i<4*n;i++){
scanf("%d",&tmp);
mp[tmp]++;
}
flag=1;
for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){
if(it->second%2){
flag=0;
printf("NO\n");
break;
}
vtmp.push_back({it->first,it->second});
}
if(flag){
int S=vtmp[0].val*vtmp[vtmp.size()-1].val;
if(vtmp[0].num!=vtmp[vtmp.size()-1].num){
printf("NO\n");
continue;
}
for(i=1,j=vtmp.size()-2;i<=j;i++,j--){
if(vtmp[i].val*vtmp[j].val!=S){
printf("NO\n");
flag=0;
break;
}
if(vtmp[i].num!=vtmp[j].num){
printf("NO\n");
flag=0;
break;
}
}
if(flag)
printf("YES\n");
}
}
return 0;
}