资讯 安全 论坛 下载 读书 程序开发 数据库 系统 网络 电子书 微信学院 站长学院 QQ 考试
频道栏目
其他| 安全资讯| 安全公告| 病毒预警| 人物| 企业招聘| 其他综合|
登录注册
首页 > 资讯 > 其他 > 正文

CodeForces Gym100935 水题专场

16-09-06        来源：[db:作者]  
收藏   我要投稿
比赛链接：CodeForces Gym100935

A Time

水题~
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define FIN             freopen("input.txt","r",stdin)
#define FOUT            freopen("output.txt","w",stdout)
#define fst             first
#define snd             second
#define lson            l, mid, rt << 1
#define rson            mid + 1, r, rt << 1 | 1

typedef __int64  LL;
//typedef long long LL;
typedef unsigned int uint;
typedef pair PII;
typedef pair PLL;

const double PI = 3.1415926536;
const double eps = 1e-6;
const int MAXN = 300 + 5;

int T;
int H, M, S;
int h, m, s;
int A, B;


int main() {
#ifndef ONLINE_JUDGE
    FIN;
    // FOUT;
#endif // ONLINE_JUDGE
    int cas = 0;
    scanf ("%d", &T);
    while (T --) {
        scanf ("%d %d %d", &H, &M, &S);
        scanf ("%d %d %d", &h, &m, &s);
        A = H * 3600 + M * 60 + S;
        B = h * 3600 + m * 60 + s;
        printf ("Case %d: %s\n", ++cas, A == B ? "Yes" : "No");
    }
    return 0;
}

B. Weird Cryptography

题意描述：给定N个单词，你可以把他们组成若干个集合，每个集合不能有相同的单词。然后呢，取第i个集合的大小比如为|Si|，|Si| <= 9，让所有集合的大小组成一个十进制数字。让这个数字最小， 求出这个数。
解题思路：首先， 要让数字最小， 就必须让这个数位数最少。然后就是肯定是要让最大的那个集合尽可能的大，最小的那个集合尽可能的小。
先用map 对每个字符串标记一下。然后cnt数组记录一下每个元素出现的次数。然后，遍历每个cnt，对应打好一个标记，最好前缀和搞一下。
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define FIN             freopen("input.txt","r",stdin)
#define FOUT            freopen("output.txt","w",stdout)
#define fst             first
#define snd             second
#define lson            l, mid, rt << 1
#define rson            mid + 1, r, rt << 1 | 1

typedef __int64  LL;
//typedef long long LL;
typedef unsigned int uint;
typedef pair PII;
typedef pair PLL;

const double PI = 3.1415926536;
const double eps = 1e-6;
const int MAXN = 10000 + 5;

int T, N;
map Hash;
char buf[110];
int cnt[MAXN];
int res[MAXN];

int main() {
#ifndef ONLINE_JUDGE
    FIN;
//     FOUT;
#endif // ONLINE_JUDGE
    int cas = 0;
    while (~scanf ("%d", &N) && N) {
        Hash.clear();
        int id = 0, M = 0;
        memset (cnt, 0, sizeof (cnt) );
        for (int i = 0; i < N; i++) {
            scanf ("%s", buf);
            int x = Hash[buf];
            if (!x) {
                x = Hash[buf] = ++ id;
            }
            cnt[x] ++;
            M = max (M, cnt[x]);
        }
        memset (res, 0, sizeof (res) );
        for (int i = 1; i <= id; i ++) {
            res[M - cnt[i] + 1] ++;
        }
        for (int i = 2; i <= M; i ++) {
            res[i] += res[i - 1];
        }
        printf ("Case %d: ", ++cas);
        for (int i = 1; i <= M; i++) {
            printf ("%d", res[i]);
        }
        printf ("\n");
    }
    return 0;
}

C. OCR

字符串水题
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define FIN             freopen("input.txt","r",stdin)
#define FOUT            freopen("output.txt","w",stdout)
#define fst             first
#define snd             second
#define lson            l, mid, rt << 1
#define rson            mid + 1, r, rt << 1 | 1

typedef __int64  LL;
//typedef long long LL;
typedef unsigned int uint;
typedef pair PII;
typedef pair PLL;

const double PI = 3.1415926536;
const double eps = 1e-6;
const int MAXN = 300 + 5;
int T;
int N, M;
char G[MAXN][MAXN];

int main() {
#ifndef ONLINE_JUDGE
    FIN;
    // FOUT;
#endif // ONLINE_JUDGE
    int cas = 0;
    scanf ("%d", &T);
    while (T--) {
        scanf ("%d %d", &N, &M);
        for (int i = 0; i < N; i++) {
            scanf ("%s", G[i]);
        }
        int x1, y1, x2, y2;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (G[i][j] == '*') {
                    x1 = i;
                    y1 = j;
                    goto F1;
                }
            }
        }
F1:
        ;
        for (int i = N - 1; i >= 0; i--) {
            for (int j = M - 1; j >= 0; j--) {
                if (G[i][j] == '*') {
                    x2 = i;
                    y2 = j;
                    goto F2;
                }
            }
        }
F2:
        ;
        int res = 0;
        for (int i = x1 + 1; i < x2; i++) {
            if (G[i][y1 + 1] == '*') res = 1;
        }
        if (res) printf ("Case %d: Eight\n", ++cas);
        else printf ("Case %d: Zero\n", ++cas);
    }
    return 0;
}

D. Enormous Carpet

裸的快速幂
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define FIN             freopen("input.txt","r",stdin)
#define FOUT            freopen("output.txt","w",stdout)
#define fst             first
#define snd             second
#define lson            l, mid, rt << 1
#define rson            mid + 1, r, rt << 1 | 1

typedef __int64  LL;
//typedef long long LL;
typedef unsigned int uint;
typedef pair PII;
typedef pair PLL;

const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int MAXN = 100 + 5;

LL N, K, A, C;
LL P[MAXN];

LL quick_pow (LL a, LL b, LL mod) {
    LL ret = 1LL;
    while (b) {
        if (b & 1LL) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1LL;
    }
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    FIN;
    // FOUT;
#endif // ONLINE_JUDGE
    LL cas = 0LL;
    while (~scanf ("%I64d %I64d %I64d %I64d", &N, &K, &A, &C) && N) {
        printf ("Case %I64d:\n", ++cas);
        for (LL i = 0; i < C; i++) {
            scanf ("%I64d", &P[i]);
//            cout << quick_pow (K, N, INF) * A << endl;
            printf ("%I64d%c", A % P[i] * quick_pow (K, N, P[i]) % P[i], i == C - 1 ? '\n' : ' ');
        }
    }
    return 0;
}

E. Pairs

题意描述： 有5个数字(X1, X2, X3, X4, X5) ，他们两两组成可以组成10个数对。现在一直这每个数对中两个数之和，让你还原这5个数字。
解题思路：水题~枚举。
首先对这个10数字进行排序，然后
已经确定的是有(X1, X2) (X1, X3), (X3,X5), (X4,X5) 这四个数对 对应的和是多少。
然后只需要枚举 (X2, X3) 和 (X3, X4) 这两个数对的和就Ok了。
X[1] = (X1 + X2) + (X1 + X3) - (X2 + X3)
其他的同理。
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define FIN             freopen("input.txt","r",stdin)
#define FOUT            freopen("output.txt","w",stdout)
#define fst             first
#define snd             second
#define lson            l, mid, rt << 1
#define rson            mid + 1, r, rt << 1 | 1

typedef __int64  LL;
//typedef long long LL;
typedef unsigned int uint;
typedef pair PII;
typedef pair PLL;

const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int MAXN = 10 + 5;

int T, cas;
int S[MAXN];
int X[MAXN];
int G[MAXN][MAXN];
int F[MAXN];

bool check() {
//    for (int i = 1; i <= 5; i++) {
//        if (X[i] <= 0) return false;
//    }
//    for (int i = 2; i <= 5; i++) {
//        if (X[i - 1] > X[i]) return false;
//    }
    int k = 0;
    for (int i = 1; i <= 5; i++) {
        for (int j = i + 1; j <= 5 ; j++) {
            F[++ k] = X[i] + X[j];
        }
    }
    sort (F + 1, F + 10 + 1);
    for (int i = 1; i <= 10; i++) {
        if (S[i] != F[i]) return false;
    }
    return true;
}
int main() {
#ifndef ONLINE_JUDGE
    FIN;
    // FOUT;
#endif // ONLINE_JUDGE
    scanf ("%d", &T);
    while (T --) {
        for (int i = 1; i <= 10; i ++) {
            scanf ("%d", &S[i]);
        }
        sort (S + 1, S + 10 + 1);
        G[1][2] = S[1];
        G[1][3] = S[2];

        G[3][5] = S[9];
        G[4][5] = S[10];
        bool suc = false;
        for (int i = 3; i <= 8; i++) {
            if (suc) break;
            G[2][3] = S[i];
            for (int j = 8; j > i; j--) {
                G[3][4] = S[j];

                X[1] = G[1][2] + G[1][3] - G[2][3];
                if (X[1] & 1) continue;

                X[1] >>= 1;

                X[5] = G[3][5] + G[4][5] - G[3][4];
                if (X[5] & 1) continue;
                X[5] >>= 1;

                X[2] = G[1][2] - X[1];
                X[3] = G[2][3] - X[2];
                X[4] = G[4][5] - X[5];

                if (check() ) {
                    suc = true;
                    break;
                }
                if (suc) break;
            }
        }
        sort(X + 1, X + 5 + 1);
        printf ("Case %d: %d %d %d %d %d\n", ++ cas, X[1], X[2], X[3], X[4], X[5]);
    }
    return 0;
}

F. A Poet Computer

题意描述：给定N个单词，这些单词中，如果有三个或者三个以上单词尾部相同，则就定义为"Common Suffix"， 求"Common Suffix"最长的长度，以及出现的次数。
解题思路： 很显然，直接将单词逆序加入到字典树中，然后直接统计就好了。
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define FIN             freopen("input.txt","r",stdin)
#define FOUT            freopen("output.txt","w",stdout)
#define fst             first
#define snd             second
#define lson            l, mid, rt << 1
#define rson            mid + 1, r, rt << 1 | 1

typedef __int64  LL;
//typedef long long LL;
typedef unsigned int uint;
typedef pair PII;
typedef pair PLL;

const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int MAXN = 100 * 1000 + 5;

int T, cas, N;
struct Node {
    int cnt;
    Node* pNext[26];
} *pRoot;
Node Mem[MAXN];
int SIZE;
int MaxLen, Times;
Node* new_node() {
    Node* p = &Mem[SIZE ++];
    p->cnt = 0;
    for (int i = 0; i < 26; i++) p->pNext[i] = NULL;
    return p;
}
void init_trie() {
    SIZE = 0;
    pRoot = new_node();
}

void add_word (char s[], int len) {
    Node* p = pRoot;
    int pos;
    for (int i = len - 1, k = 1; i >= 0; i--, k++) {
        pos = s[i] - 'a';
        if (p->pNext[pos] == NULL) {
            p->pNext[pos] = new_node();
        }
        p->pNext[pos]->cnt ++;
        p = p->pNext[pos];
        if (p->cnt >= 3) {
            if (MaxLen < k) {
                MaxLen = k;
                Times = p->cnt;
            } else if (MaxLen == k) {
                Times = max (Times, p->cnt);
            }
        }
    }
}

char buf[110];
int main() {
#ifndef ONLINE_JUDGE
    FIN;
    // FOUT;
#endif // ONLINE_JUDGE
    scanf ("%d", &T);
    while (T--) {
        init_trie();
        MaxLen = Times = 0;
        scanf ("%d", &N);
        for (int i = 0; i < N; i++) {
            scanf ("%s", buf);
            for (int i = 0; i < strlen (buf); i++) {
                if (buf[i] >= 'A' && buf[i] <= 'Z') buf[i] = buf[i] - 'A' + 'a';
            }
            add_word (buf, strlen (buf) );
        }
        printf ("Case %d:\n", ++cas);
        if (N < 3) {
            printf ("0 0");
            continue;
        }
        printf ("%d %d\n", MaxLen, Times);
    }
    return 0;
}

H. Bend Test

题目描述：有P部手机需要进行压力测试（每部手机的耐压值是一样的），压力值从1~M，(P∈[1, 50], M ∈[1, 1000])， 当压力值大于手机的耐压值时，这部手机就被摧毁了，不能继续进行测试了， 现在要你求出，在最坏的情况下，最少需要多少次可以测出压力值。
解题思路：裸DP。
用dp[p][m] 表示 p部手机 最大压力值为m 的答案。
然后有，dp[p][m] = min (dp[p][m], (dp[p - 1][x - 1], dp[p][m - x]) + 1);
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define FIN             freopen("input.txt","r",stdin)
#define FOUT            freopen("output.txt","w",stdout)
#define fst             first
#define snd             second
#define lson            l, mid, rt << 1
#define rson            mid + 1, r, rt << 1 | 1

typedef __int64  LL;
//typedef long long LL;
typedef unsigned int uint;
typedef pair PII;
typedef pair PLL;

const int INF = 0x3f3f3f3f;
const int MAXP = 50 + 5;
const int MAXM = 1000 + 5;

int T, cas;
int M, P;
int dp[MAXP][MAXM];
// 求log2 的 值
int F (int x) {
    int ret = 0, y = 1;
    while (y < x) y <<= 1, ret++;
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    FIN;
#endif // ONLINE_JUDGE

    for (int p = 1; p < MAXP; p++) dp[p][1] = 1, dp[p][p] = F (p + 1);
    for (int m = 1; m < MAXM; m++) dp[1][m] = m;
    for (int p = 2, t; p < MAXP; p++) {
        for (int m = 2; m <= p; m++) dp[p][m] = dp[m][m];
        for (int m = p + 1; m < MAXM; m++) {
            dp[p][m] = INF;
            for (int x = 2; x < m; x++) {
                t = max (dp[p - 1][x - 1], dp[p][m - x]);
                dp[p][m] = min (dp[p][m], t + 1);
            }
        }
    }
    scanf ("%d", &T);
    while (T --) {
        scanf ("%d %d", &P, &M);
        printf ("Case %d: %d\n", ++cas, dp[P][M]);
    }
    return 0;
}

I. Farm

题目描述： 求矩形与圆相交的面积。已知矩形长宽>圆的半径，矩形左上角在圆中。
解题思路：刚开始没有好好看题，没看到矩形左上角在圆中 结果就想 要根据矩形的位置分情况考虑，Too Young Too Simple!...
如图， 将矩形和圆的公共部分分割成 两个部分， 一个三角形，和一个弓形( 弦与弧围成的区域)区域。分别求面积即可。
#include 
using namespace std;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define FIN             freopen("input.txt","r",stdin)
#define FOUT            freopen("output.txt","w",stdout)
#define fst             first
#define snd             second
#define lson            l, mid, rt << 1
#define rson            mid + 1, r, rt << 1 | 1
#define fcout(x)        cout << fixed << setprecision(6)

typedef __int64  LL;
typedef pair PII;

const int MAXN = 300 + 5;

int T, N, M;
double XC, YC, R;
double XB, YB, XU, YU;
double X1, X2, Y1, Y2;
double S1, S2, S3;
double alfa, dist;

int main() {
#ifndef ONLINE_JUDGE
    FIN;
//    FOUT;
#endif // ONLINE_JUDGE
    int cas = 0;
    scanf ("%d", &T);
    while (T --) {
        scanf ("%lf %lf %lf", &XC, &YC, &R);
        scanf ("%lf %lf %lf %lf", &XB, &YB, &XU, &YU);

        XU -= XC;
        YU -= YC;
        XB -= XC;
        YB -= YC;

        Y1 = YU;
        X1 = sqrt (R * R - Y1 * Y1);

        X2 = XB;
        Y2 = -sqrt (R * R - X2 * X2);

        dist = sqrt ( (X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2) );
        alfa = acos ( (R * R * 2.0 - dist * dist) / (2.0 * R * R) );

        S1 = 0.5 * fabs (X1 - X2) * fabs (Y1 - Y2);
        S2 = (R * R * 0.5) * (alfa - sin (alfa) );

        S3 = S1 + S2;
        cout << "Case " << ++cas << ": ";
        cout << fixed << setprecision(5) << S3 << endl;
    }
    return 0;
}

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇：ASP.NET CORE 读取配置文件 读取自定义配置文件
下一篇：对排序算法的一些总结（python版本）
相关文章
热门专题推荐 vmware win7激活工具 win10激活工具 excel word office激活 小马激活工具 重装系统 数据恢复 u盘启动工具
图文推荐
文章
推荐
热门新闻
· 锤子坚果Pro发布后，罗永浩哭了
· 想实习的大学党看过来!这些科技巨头最
· 罗永浩锤子发布会抢先消息：锤子科技新
· Google新一代系统Fuchsia OS界面曝光
· 中国唯一连续运营20余年的网络游戏，还
· iPhone都便宜了 为何国产手机越来越贵
· 丢人！谷歌和Facebook竟被虚假企业电邮
· 中国移动支付震惊日本网友 为什么美国

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站