CF Round #579(div3)前七題

1203A Circle of Students

題意：給 n n n個數，把這 n n n個數圍成一圈，問能不能從其中一個位置開始沿順時針或者逆時針方向走都是單調遞或者單調遞減且兩兩相差不超過1，（除了1和 n n n相差 n − 1 n-1 n−1）

思路：直接周遊一遍，記錄相差1或者相差 n − 1 n-1 n−1的個數

#include <stdio.h>
    #include <time.h>
    #include <string.h>
    #include <algorithm>
    #include <stack>
    #include <vector>
    #include <set>
    #include <iostream>
    #include <queue>
    #include <string>
    #include <math.h>
    typedef long long LL;
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    #define mid(l,r) (( l + r ) / 2)
    #define lowbit(x) (( x & ( - x )))
    #define lc(root) ((root * 2))
    #define rc(root) ((root * 2 + 1))
    #define me(array,x) (memset( array , x , sizeof( array ) ) )
    const int maxn = 1e5;
    int num[maxn];
    int main()
    {
        int q;
        scanf("%d",&q);
        while(q--){
            int n;scanf("%d",&n);
            int flag = 0;
            scanf("%d",&num[1]);
            for(int i=2;i<=n;i++){
                scanf("%d",&num[i]);
                if(abs(num[i]-num[i-1])==1||abs(num[i]-num[i-1])==n-1){
                    flag++;
                }
            }
            if(flag==n-1)printf("YES\n");
            else printf("NO\n");
        }
        return 0;
    }

1203B Equal Rectangles

題意：給 4 ∗ n 4*n 4∗n個木棒，問能不能将這些木棒拼起來使得每個矩形面積一樣

思路：先排序，然後再分别從數組的兩端取出元素判斷即可

#include <stdio.h>
        #include <time.h>
        #include <string.h>
        #include <algorithm>
        #include <stack>
        #include <vector>
        #include <set>
        #include <iostream>
        #include <queue>
        #include <string>
        #include <math.h>
        typedef long long LL;
        using namespace std;
        const int inf = 0x3f3f3f3f;
        const int mod = 1e9 + 7;
        #define mid(l,r) (( l + r ) / 2)
        #define lowbit(x) (( x & ( - x )))
        #define lc(root) ((root * 2))
        #define rc(root) ((root * 2 + 1))
        #define me(array,x) (memset( array , x , sizeof( array ) ) )
        const int maxn = 1e5;
        int num[maxn];
        int main()
        {
            int q;
            scanf("%d",&q);
            while(q--){
                int n;scanf("%d",&n);
                for(int i=1;i<=n*4;i++)
                scanf("%d",&num[i]);
                sort(num+1,num+1+4*n);
                int flag = 1;
                int ans = num[1] * num[4*n];
                for(int i = 1 , j = 4*n ; i <= 2*n-1 ; i += 2 , j -= 2){
                    if((num[i] != num[i+1])||(num[j] != num[j-1])){//相鄰的兩個數不相同肯定不行
                        flag=0;
                        break;
                    }
                    if(num[i] * num[j] != ans){
                        flag=0;
                        break;
                    }
                }
                if(flag)printf("YES\n");
                else printf("NO\n");
            }
            return 0;
        }

1203C Common Divisors

題意：給 n n n個數，找這 n n n個數的公因子個數最多是多少

思路：找到 n n n個數的最大公約數，再找最大公約數的因子個數，用 set 記錄因子個數

#include <stdio.h>
    #include <time.h>
    #include <string.h>
    #include <algorithm>
    #include <stack>
    #include <vector>
    #include <set>
    #include <iostream>
    #include <queue>
    #include <string>
    #include <math.h>
    typedef long long LL;
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    #define mid(l,r) (( l + r ) / 2)
    #define lowbit(x) (( x & ( - x )))
    #define lc(root) ((root * 2))
    #define rc(root) ((root * 2 + 1))
    #define me(array,x) (memset( array , x , sizeof( array ) ) )
    const int maxn = 4e5+10;
    LL num[maxn];
    set<LL>s;
    int main()
    {
        int n;
        scanf("%d",&n);
        scanf("%lld",&num[1]);
        LL gcd = num[1];
        for(int i = 2 ; i <= n ; i++){
            scanf("%lld",&num[i]);
            gcd = __gcd(num[i],gcd);
        }
        for(LL i = 1 ; i * i <= gcd ; i++){
            if(gcd % i == 0){
                 s.insert(i);
                 s.insert(gcd/i);
            }
        }
        printf("%d\n",s.size());
        return 0;
    }

1203D1 Remove the Substring (hard version)

1203D2 Remove the Substring (hard version)

題意：給一個字元串 s s s，再給一個 s s s中的子序列 t t t，問從 s s s中删除最長子串，使得 t t t任然是 s s s的子序列。求最長子串的長度

思路：三種情況：子序列 t t t的第一個字元在 s s s中位置、最後一個字元在 s s s中的位置、還有子序列中間的每個空隙在原序列中夾着多少字元，取上述三者最大就行了。對于第三種情況，由于子序列在 s s s中的位置可能有多種情況，那麼就用兩個數組來分别來存子序列每個字元在 s s s中的位置，一個數組從 s s s的正序開始周遊（簡稱字首數組），一個從 s s s的逆序開始周遊（簡稱字尾數組），最後再周遊字尾數組的第 i i i個元素減去字首數組的第 i − 1 i-1 i−1個元素的最大值就行了。

#include <stdio.h>
    #include <time.h>
    #include <string.h>
    #include <algorithm>
    #include <stack>
    #include <vector>
    #include <set>
    #include <iostream>
    #include <queue>
    #include <string>
    #include <math.h>
    typedef long long LL;
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    #define mid(l,r) (( l + r ) / 2)
    #define lowbit(x) (( x & ( - x )))
    #define lc(root) ((root * 2))
    #define rc(root) ((root * 2 + 1))
    #define me(array,x) (memset( array , x , sizeof( array ) ) )
    const int maxn = 1e6;
    int a[maxn],b[maxn];
    char s[maxn],t[maxn];
    int main()
    {
        scanf("%s%s",s+1,t+1);
        int n = strlen(s+1);
        int m = strlen(t+1);
        for(int i = 1 , j = 1 ; i <= n ;){
            while(s[i] != t[j])
                i++;
            a[j] = i;
            if(j == m)break;
            j++;i++;
        }
        a[m + 1] = n + 1 ; a[0] = 0;
        for(int i = n , j = m ; i >= 1 ;){
            while(s[i] != t[j])
                i--;
            b[j] = i;
            if(j == 1)break;
            j--;i--;
        }
        b[m + 1] = n + 1 ; b[0] = 0;
        int ans1 = a[1] - 1;
        for(int i = 1 ; i <= m+1 ; i++)
            ans1 = max(b[i] - a[i-1] - 1 , ans1);
        printf("%d\n",ans1);
        return 0;
    }

1203E Boxers

題意：給n個數，每個數可以加一、減一、或者不變，但是每個數必須大于零，問在對一些數操作之後，最多有多少不同的數

思路：先排序，最好的情況就是從最小的數開始每次增加一，是以就從小的開始周遊，用按-1、0、+1的順序往set裡加。看代碼，一看就懂。

#include <stdio.h>
        #include <time.h>
        #include <string.h>
        #include <algorithm>
        #include <stack>
        #include <vector>
        #include <set>
        #include <iostream>
        #include <queue>
        #include <string>
        #include <math.h>
        typedef long long LL;
        using namespace std;
        const int inf = 0x3f3f3f3f;
        const int mod = 1e9 + 7;
        #define mid(l,r) (( l + r ) / 2)
        #define lowbit(x) (( x & ( - x )))
        #define lc(root) ((root * 2))
        #define rc(root) ((root * 2 + 1))
        #define me(array,x) (memset( array , x , sizeof( array ) ) )
        const int maxn = 1e6;
        int num[maxn];
        int main()
        {
            int n ; scanf("%d",&n);
            for(int i = 1 ; i <= n ; i++){
                scanf("%d",&num[i]);
            }
            sort(num+1,num+n+1);
            set<int>q;
            for(int i = 1 ; i <= n ; i++){
                int x = num[i];
                if(!q.count(x - 1) && x != 1)
                    q.insert(x - 1);
                else if(!q.count(x))
                    q.insert(x);
                else if(!q.count(x + 1))
                    q.insert(x + 1);
            }
            printf("%d\n",q.size());
            return 0;
        }

1203F1 Complete the Projects (easy version)

題意：小明最初有 m m m點活力值，現在有 n n n個任務，每個任務有兩個參數 a a a、 b b b分别代表完成該任務需要一個最基礎的活力值 a a a(小明的活力值必須大于等于 a a a才能做這個任務)，做完這個任務之後的活力值會增加（或減少） b b b，問小明能否做完所有任務。

思路：對于 b b b是正的來說，就按照 a a a小的來排序就行了，這樣活力值就會一直增加，直到開始做 b b b時負的；那麼對于 b b b是負的來說，需要 a a a較大的并且消耗活力值較小的排在前面（也就是 b b b大的），是以就按照 a + b a+b a+b大的排在前面就行了。

{ x . a > y . a x . b > y . b \begin{cases} x.a>y.a \\ x.b>y.b \end{cases} {x.a>y.ax.b>y.b

合并不等式：

x . a + x . b > y . a + y . b x.a+x.b>y.a+y.b x.a+x.b>y.a+y.b

#include <stdio.h>
#include <time.h>
#include <string.h>
#include <algorithm>
#include <stack>
#include <vector>
#include <set>
#include <iostream>
#include <queue>
#include <string>
#include <math.h>
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define mid(l,r) (( l + r ) / 2)
#define lowbit(x) (( x & ( - x )))
#define lc(root) ((root * 2))
#define rc(root) ((root * 2 + 1))
#define me(array,x) (memset( array , x , sizeof( array ) ) )
const int maxn = 1e3;

struct node {int a,b;}s[maxn];

int cmp (node a,node b){
    if(a.b >= 0 && b.b >= 0)
        return a.a < b.a;
    else if(a.b < 0 && b.b < 0)
        return a.a + a.b > b.a + b.b;
    else
        return a.b > b.b;//對于b有一個是正的另一個是負的來說，就把正的排在前面
}
int main()
{
    int n,r;
    scanf("%d%d",&n,&r);
    for(int i = 1 ; i <= n ; i++){
        scanf("%d%d",&s[i].a,&s[i].b);
    }
    sort(s+1,s+1+n,cmp);
    int ans = r;
    int flag = 0;
    for(int i = 1 ; i <= n ; i++){
        if(s[i].a > ans){
            flag = 1;
            break;
        }
        ans += s[i].b;
    }
    if(flag || ans < 0)printf("NO\n");
    else printf("YES\n");
    return 0;
}

1203F2 Complete the Projects (easy version)

題意：和F1差不多，但問的是最多能做幾個任務

思路：不會

CF Round #579(div3)前七題

1203A Circle of Students

1203B Equal Rectangles

1203C Common Divisors

1203D1 Remove the Substring (hard version)

1203D2 Remove the Substring (hard version)

1203E Boxers

1203F1 Complete the Projects (easy version)

1203F2 Complete the Projects (easy version)

繼續閱讀

二進制優化多重背包

STL建立二叉堆

二分圖判定：染色法

HDU 4619 Warm up 2（最大獨立集）

記憶化搜尋 HDU FatMouse and Cheese