Educational Codeforces Round 57

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

2018.12.28 22：30

看着CF升高的曲线，摸了摸自己的头发，我以为我变强了，直到这一场Edu搞醒了我。。

从即将进入2018年末开始，开启自闭场集合，以纪念(dian)那些丢掉的头发

留坑睡觉。。明天看题解再补

A.Find Divisible

题意：输出[l,r]中满足x|y的x,y，保证有解

思路：直接输出x, 2x即可

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<functional>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

#define lowbit(x) ((x)&(-x)) 

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = 1e9+;

const int maxn = 2e6+;

const int maxm = 2e6+;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

int main() {

    int t;

    scanf("%d", &t);

    while(t--){

        ll x, y;

        scanf("%lld %lld", &x, &y);

        printf("%lld %lld\n", x,*x);

    }

    return ;

}

B.Substring Removal

题意：删除一个子串，使得剩下的串只有一种字符，问你方案数

思路：分a[1]是否==a[n]两种情况讨论，

等于的时候根据要删除的子串区间端点范围决定方案数

不等于的时候相当于一个端点固定

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<functional>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

#define lowbit(x) ((x)&(-x)) 

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = ;

const int maxn = 2e6+;

const int maxm = 2e6+;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

char a[maxn];

int main() {

    int n;

    scanf("%d", &n);

    getchar();

    scanf("%s", a+);

    ll ans = ;

    if(a[]==a[n]){

        char c = a[];

        int l , r;

        for(int i = ; i <= n; i++){

            if(a[i]!=c){l=i;break;}

        }

        for(int i = n; i >= ; i--){

            if(a[i]!=c){r=i;break;}

        }

        l = l;

        r = n-r+;

        ans = 1ll*l*r;

        ans%=mod;

    }

    else{

        int l,r;

        char c = a[];

        for(int i = ; i <= n; i++){

            if(a[i]!=c){l=i;break;}

        }

        c = a[n];

        for(int i = n; i >= ; i--){

            if(a[i]!=c){r=i;break;}

        }

        ans = n-r;

        ans += l;

        ans%=mod;

    }

    printf("%lld", ans);

    return ;

}

C.Polygon for the Angle

题意：问你一个角度最少存在于正几边形中

思路：看代码。。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<functional>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

#define lowbit(x) ((x)&(-x)) 

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = ;

const int maxn = 2e6+;

const int maxm = 2e6+;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

int main() {

    int t;

    scanf("%d", &t);

    while(t--){

        int ag;

        scanf("%d", &ag);

        int g = __gcd(ag,);

        int n = /g;

        int m = ag/g;

        while(m>n-){n*=;m*=;}

        printf("%d\n", n);

    }

    return ;

}

D.Easy Problem

题意：给你一个字符串，每个字符都有权重，问你删掉多少权重和的字符，使得剩下的字符没有"hard"子序列，并且这个权重和最小

思路：dp[i][j]为前i个字符最多拥有j状态的子序列需要删除的最小权重

其中 j=0代表空，j=1代表"h"，j=2代表"ha"，j=3代表"har"

转移方程在代码里

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<functional>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

#define lowbit(x) ((x)&(-x)) 

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = ;

const int maxn = 2e6+;

const int maxm = 2e6+;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

char s[maxn];

ll dp[maxn][];

//dp[i][j]表示前i个字符最多有prej作为子序列要删多少

int a[maxn];

int n;

int main() {

    scanf("%d", &n);

    getchar();

    scanf("%s", s+);

    for(int i = ; i <= n; i++){

        scanf("%d", &a[i]);

    }

    mem(dp,);

    //dp[0][0] = 0;

    for(int i = ; i <= n; i++){

        for(int j = ; j < ; j++){

            dp[i][j] = dp[i-][j];

        }

        if(s[i]=='h')dp[i][]+=a[i];

        if(s[i]=='a')dp[i][]=min(dp[i-][],dp[i][]+a[i]);

        if(s[i]=='r')dp[i][]=min(dp[i-][],dp[i][]+a[i]);

        if(s[i]=='d')dp[i][]=min(dp[i-][],dp[i][]+a[i]);

    }

    ll ans = 0x7f7f7f7f7f7f7f7f;

    for(int i = ; i <=  ;i++){

        ans = min(ans, dp[n][i]);

    }printf("%lld", ans);

    return ;

}