几个cf水题

109 阅读 0 评论 72 点赞

我是靠谱客的博主有魅力百褶裙，这篇文章主要介绍几个cf水题，现在分享给大家，希望可以做个参考。

1358C 1600
题意：在一个类似于三角形排列的二维数组（即[1,1]->[1,2]->[2,1]->[1,3]->[2,2]->[3,1]这样类似三角形的递增排列）一个起点sx，sy，和终点ex，ey，问你从起点到终点的路径和有多少种可能，且路径的方向只能往下或者往右，
思路：可以模拟一下，从一个点到另一个点路径有多种，而且其中有可能会有虽然然路径不同，但是路径和相同的情况，所以，可以想想路径的最大值和路径的最小值，然后判断在路径的最大值和最小值之间是否会存在遗漏，显然通过分析，是没有遗漏的，那么问题就来了，如何计算路径最大值和最小值的差值呢，如果模拟一下不难发现起点和终点的相对位置和差值有关，其余的都和差值无关，然后得到最后的关系式就ok了

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
int main(){
    IOS;
    int t;
    cin>>t;
    while(t--){
        ll a, b, c, d;
        cin>>a>>b>>c>>d;
        cout<<(c-a)*(d-b)+1<<endl;
    }
    return 0;
}

1352G 1600
题意：给你一棵树，n个结点，n-1条边，然后定义其中一个结点为特殊点（可以为叶子结点），Ashish和Ayush分别对这棵树进行操作，对这棵树减去叶子结点，也就是度为1的点，将与这个结点的边全部剪除。最先剪掉特殊点的人获胜。Ayush先剪
思路：我一开始看到这个题目的时候想到的还是拓扑排序。。没想到。。一样的是模拟一下，如果这个特殊结点就是叶子节点，那么肯定是Ayush获胜，如果这个特殊节点不是叶子结点，那么可以设想每个人的操作都是最优的，那么就肯定不会使得这个特殊结点变为叶子节点，除非是迫不得已，只能剪去一个叶子结点使得这个特殊结点变为叶子结点，所以到最后肯定是剩下两个结点，特殊节点和另外一个结点，之后的久很容易判断了，如果这个树的节点数为偶数那么Ayush获胜，反之Ashish获胜。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int main(){
    IOS;
    int t;
    cin>>t;
    while(t--){
        int n, k;
        cin>>n>>k;
        int flag = 0;
        for(int i = 0; i < n-1; i++){
            int x, y;
            cin>>x>>y;
            if(x==k||y==k){
                flag++;
            }
        }
        if(flag>=2){
            if(n%2==0){
                cout<<"Ayush"<<endl;
            }else cout<<"Ashish"<<endl;
        }
        else cout<<"Ayush"<<endl;
    }
    return 0;
}

1352G 1600
题意：给你一个数n，问你是否存在这么数组a包含1到n，且2<=|a[i]-a[i-1]|<=4,如果存在则打印出这个数组，如果不存在则打印-1
思路：这个题目是真的水，模拟一下，就先跳着来1，3，5 。。。然后在结尾的时候分类讨论，同时对n=4的时候另行分析，因为我假设的数组都是以1为开头。具体实现看代码吧

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int main(){
    IOS;
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        if(n<4){
            cout<<"-1"<<endl;
            continue;
        }else if(n==4){
            cout<<"3 1 4 2"<<endl;
            continue;
        }
        for(int i = 1; i <= n; i+=2){
            cout<<i<<" ";
        }
        if(n%2==0){
            cout<<n-4<<" "<<n<<" "<<n-2<<" ";
            for(int i = n-6; i > 0; i-=2){
                cout<<i<<" ";
            }
        }
        else {
            cout<<n-3<<" "<<n-1<<" ";
            for(int i = n-5; i > 0; i-=2){
                cout<<i<<" ";
            }
        }
        cout<<endl;
    }
    return 0;
}