题目列表

1.CF 1550C
2.CF 1551D1
3.CF 1551D2
4.CF 1203C
5.CF 1203B

这几篇题解都是我从自己的CSDN里搬来的，不然显得我没打过ACM www

1. CF1550C

原题链接

题目大意

求一个数组中满足 (从目标数组里任选三点，满足三个曼哈顿距离没有加减关系) 的连续子区间数量，定义长度为1和2的数组也满足这一条件

解题思路

从上面可以知道如果有三个点满足中间的点不被两边的点包含就符合 另外讨论三个以上的点 四个点的时候 可以看成三个点再加上一个点 所以前面三个点是满足关系的 然后我们只要关注最后一个点怎么插

可以看出要满足的话只有边上两个点把中间两个点包起来的时候。四个点以上我就不画了，因为无论如何都是找不到满足这一条件的情况，所以我们就直接暴力枚举首个点 判断后续长度为3和4子区间是否满足这一条件即可。

AC代码

#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;
}

2. CF1551D1

原题链接
#### 题目大意
在NxM的棋盘上摆1x2的多米诺骨牌，判断是否能在摆下k的水平块的前提下摆满整个棋盘
#### 解题思路
刚刚开始的思路是用某些小块固定出大块，然后发现思路不对，很难考虑完全。然后我就去看官方题解了…
题解的大致意思是按n和m的奇偶分成四种情况
1. n奇m奇:不用考虑，肯定是不可能。
2. n偶m偶:k不会超过 m * n / 2 所以肯定可以做到。
3. n偶m奇:既然n偶m偶能过，那就想办法让m的一行填掉。
4. n奇m偶:原理同上，看看能不能填掉n的一行。
#### AC代码
cpp #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; }

3 . CF1551D2

原题链接
#### 题目大意
上一道题目的构造版本。
#### 解题思路
思路和上面以提是一样的，但是构造思路很麻烦，看代码吧，以为涉及到字符串，所以用了我比较熟悉的python写，写的是十分的冗长…
#### AC代码
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)

4. CF 1203C

原题链接

题目大意

找到输入n个数的最大公因子，再求出这个公因子又几个因数
#### 解题思路
div3水题，连续gcd就可以求出最大公因子 然后因数分解只需要用试除法即可 时间复杂度是够的(不会分析gcd的时间复杂度
#### AC代码
cpp #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; }

5. CF 1203B

原题链接

题目大意

给一组边，判断是否能用所给边构造出的所有矩形面积相等。

解题思路

贪心，要想所有矩形面积相等，必须从最长和最短边里选

AC代码

#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;
}