首页 > 代码库 > Codeforces 106 DIV2 ACD

Codeforces 106 DIV2 ACD

B表示完全看不懂。。就不弄了。。

E字符串先不管了。到时候系统学下字符串再处理

A

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}int src[13];int main(){    int K;    scanf("%d",&K);    for (int i = 0; i < 12; i++) scanf("%d",&src[i]);    sort(src,src+12);    int ans  = 0 ,sum  = 0, cas = 11;    while (true)    {        if (sum >= K) break;        if (ans == 13) break;        sum += src[cas];        cas--;        ans++;    }    if (ans == 13) puts("-1");    else printf("%d\n",ans);    return 0;}
View Code

C

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 100005int N;struct node{    int id;    int val;    friend bool operator < (const node & a,const node &b)    {        return a.val < b.val;    }}src[MAXN];LL sum[MAXN];node stl[MAXN],str[MAXN];int main(){    scanf("%d",&N);    sum[0] = 0;    for (int i = 1; i <= N; i++)    {        scanf("%d",&src[i].val);        src[i].id = i ;        sum[i] = sum[i - 1] + src[i].val;    }    sort(src + 1, src + 1 + N);    int topl = 1 ,topr = 1;    if (N % 2 == 0)    {       for (int i = 1; i  <= N; i++)        {            if (i % 2 == 0)  stl[topl++] =src[i];            else str[topr++] = src[i];        }        printf("%d\n",N / 2);        for (int i = 1; i < topl; i++) printf("%d ",stl[i].id);        putchar(\n);        printf("%d\n",N / 2);        for (int i = 1; i < topr; i++) printf("%d ",str[i].id);        putchar(\n);    }    else    {        for (int i = 1; i <= N; i += 2)            stl[topl++] =src[i];        for (int i = 2; i <= N; i += 2)            str[topr++] = src[i];        printf("%d\n",N / 2 + 1);        for (int i = 1; i < topl; i++ ) printf("%d ",stl[i].id);        putchar(\n);        printf("%d\n", N / 2);        for (int i = 1; i < topr; i++) printf("%d ",str[i].id);        putchar(\n);    }    return 0;}
View Code

D

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MOD 1000000007char input[720];struct node{        char res;        int id;}src[720];int G[720];node sta[720];LL dp[720][720][4][4];void calcu(int l ,int r){        if (l >= r) return ;        if (l  + 1 == r)        {                dp[l][r][0][1] = 1;                dp[l][r][1][0] = 1;                dp[l][r][2][0] = 1;                dp[l][r][0][2] = 1;        }        if (G[l] == r)        {                calcu(l + 1,r - 1);                for (int i = 0 ; i < 3; i++)                        for (int j = 0; j < 3; j++)                {                        if (j != 1) dp[l][r][0][1] = (dp[l][r][0][1] + dp[l + 1][r - 1][i][j]) % MOD;                        if (j != 2) dp[l][r][0][2] = (dp[l][r][0][2] + dp[l + 1][r - 1][i][j]) % MOD;                        if (i != 1) dp[l][r][1][0] = (dp[l][r][1][0] + dp[l + 1][r - 1][i][j]) % MOD;                        if (i != 2) dp[l][r][2][0] = (dp[l][r][2][0] + dp[l + 1][r - 1][i][j]) % MOD;                }                return ;        }        else        {                 int t = G[l];                 calcu(l,t);                 calcu(t + 1, r);                 for (int i = 0 ; i < 3; i++)                        for (int j = 0 ; j < 3; j++)                           for (int m = 0; m < 3; m++)                               for (int n = 0 ; n < 3; n++)                 {                         if (!( (m == 1 && n == 1) || (m == 2 && n == 2)))                             dp[l][r][i][j] = (dp[l][r][i][j] + (dp[l][t][i][m] * dp[t + 1][r][n][j]) % MOD) % MOD;                 }        }}int main(){        while (scanf("%s",input + 1) != EOF)        {                int len = strlen(input + 1);                int top = 1;                for (int i = 1; i <= len; i++)                {                        if (input[i] == ()                        {                                node tmp;                                tmp.id = i;                                tmp.res = input[i];                                sta[top++] = tmp;                        }                        else                        {                                if (sta[top - 1].res == ()                                {                                        G[i] = sta[top - 1].id;                                        G[sta[top - 1].id] = i;                                        top--;                                }                                else                                {                                        node tmp;                                        tmp.id = i;                                        tmp.res = input[i];                                        sta[top++] = tmp;                                }                        }                }                memset(dp,0,sizeof(dp));                calcu(1,len);                LL ans = 0;                for (int i = 0 ; i < 3; i++)                        for (int j = 0 ; j < 3; j++)                        ans = (ans + dp[1][len][i][j]) % MOD;                printf("%I64d\n",ans % MOD);        }        return 0;}
View Code

 

Codeforces 106 DIV2 ACD