UCF Local Programming Contest 2016

A

#include <bits/stdc++.h>
using namespace std;

int n, a, b, c;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d%d%d", &a, &b, &c);
        int cnt = 0;
        if (a >= 10) ++cnt;
        if (b >= 10) ++cnt;
        if (c >= 10) ++cnt;
        if (i != 1) puts("");
        printf("%d %d %d\n", a, b, c);
        if (cnt == 0) puts("zilch");
        else if (cnt == 1) puts("double");
        else if (cnt == 2) puts("double-double");
        else puts("triple-double");
    }
    return 0;
}

B

#include <bits/stdc++.h>
using namespace std;

int t, n;
int f[26];
char a[3], b[3], s[55];

int find(int x)
{
    if (x == f[x]) return x;
    return f[x] = find(f[x]);
}

bool same(int x, int y)
{
    x = find(x), y = find(y);
    return x == y;
}

void unit(int x, int y)
{
    x = find(x), y = find(y);
    f[y] = x;
}

int main()
{
    scanf("%d", &t);
    for (int cas = 1; cas <= t; ++cas)
    {
        if (cas != 1) puts("");
        printf("Test case #%d:\n", cas);
        for (int i = 0; i < 26; ++i) f[i] = i;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
        {
            scanf("%s%s", a + 1, b + 1);
            unit(a[1] - 'a', b[1] - 'a');
        }
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
        {
            scanf("%s", s + 1);
            printf("%s ", s + 1);
            int len = strlen(s + 1), flag = 1;
            for (int i = 1, j = len; i < j; ++i, --j)
                if (!same(s[i] - 'a', s[j] - 'a')) { flag = 0; break; }
            if (flag) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}

C

#include <bits/stdc++.h>
using namespace std;

int h[55], l[55], t, n, k;

int main()
{
    scanf("%d", &t);
    for (int cas = 1; cas <= t; ++cas)
    {
        if (cas != 1) puts("");
        int ans = 0;
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; ++i) h[i] = l[i] = 0;
        for (int i = 1; i <= k; ++i)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            if (h[a] && l[b]) ++ans;
            h[a] = l[b] = 1;
        }
        printf("Strategy #%d: %d\n", cas, ans);
    }
    return 0;
}

D

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int t, n, m, k, g;
ll sum[25];

int main()
{
    scanf("%d", &t);
    for (int cas = 1; cas <= t; ++cas)
    {
        if (cas != 1) puts("");
        printf("CD #%d:\n", cas);
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; ++i) scanf("%d", &m), sum[i] = sum[i - 1] + m;
        scanf("%d", &m);
        for (int i = 1; i <= m; ++i)
        {
            scanf("%d", &g); ll ans = 0;
            for (int j = 1, c; j <= g; ++j)
            {
                int a; scanf("%d", &a);
                if (j & 1) ans += a, c = sum[k] - sum[k - 1] -  a % (sum[k] - sum[k - 1]);
                else
                {
                    if (c == sum[k] - sum[k - 1]) c = 0;
                    if (a <= c) {ans += a; continue;}
                    a -= c, ans += c;
                    ans += a / sum[n] * (sum[k] - sum[k - 1]);
                    a = a % sum[n] - (sum[n] - sum[k] + sum[k - 1]);
                    if (a > 0) ans += a;
                }
            }
            printf("%lld\n", ans);
        }
    }
    return 0;
}

E

#include <bits/stdc++.h>
#define P pair<int, int>
using namespace std;

int n, m, cnt, tot, k, t;
int mp[25][25], d[4][2] = { {0,1}, {0,-1}, {1,0}, {-1, 0} };
char s[105], ans[5] = "RLDU";

bool work(int de, P p)
{
    for (int i = 2; s[i]; ++i)
    {
        p.first += d[de][0], p.second += d[de][1];
        if (p.first < 1) p.first = n;
        else if (p.first > n) p.first = 1;
        if (p.second < 1) p.second = m;
        else if (p.second > m) p.second = 1;
        if (mp[p.first][p.second] != s[i] - 'A') return false;
    }
    return true;
}

int main()
{
    scanf("%d", &t);
    for (int cas = 1; cas <= t; ++cas)
    {
        vector<P> ve[26];
        if (cas != 1) puts("");
        printf("Word search puzzle #%d:\n", cas);
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
            {
                char c = getchar();
                while (c > 'Z' || c < 'A') c = getchar();
                mp[i][j] = c - 'A';
                ve[c - 'A'].push_back({ i, j });
            }
        scanf("%d", &k);
        for (int i = 1; i <= k; ++i)
        {
            scanf("%s", s + 1);
            int ch = s[1] - 'A', flag = 1;
            for (P p : ve[ch])
            {
                for (int de = 0; de < 4; ++de)
                    if (work(de, p))
                    {
                        printf("%c %d %d %s\n", ans[de], p.first, p.second, s + 1);
                        flag = 0;
                        break;
                    }
                if (!flag) break;
            }
        }
    }
    return 0;
}

F(eps用多了误差就大了)

#include <bits/stdc++.h>
#define P pair<double, double>
#define eps 1e-6
using namespace std;

int n, t;
P p[55];

double dis(P a, P b)
{
    return (a.first - b.first) * (a.first - b.first) + 
            (a.second - b.second) * (a.second - b.second);
}

bool same(double a, double b)
{
    return abs(a - b) <= eps;
}

bool same(P a, P b)
{
    return (same(a.first, b.first) && same(a.second, b.second));
}

bool is(P a, P b, P c)
{
    return same(dis(a, c), dis(a, b) + dis(b, c));
}

int main()
{
    scanf("%d", &t);
    for (int cas = 1; cas <= t; ++cas)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%lf%lf", &p[i].first, &p[i].second);
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = i + 1; j <= n; ++j)
                for (int k = 1; k <= n; ++k)
                    if (k != i && k != j)
                    {
                        P mid = { (p[i].first + p[j].first) / 2,
                                 (p[i].second + p[j].second) / 2 };
                        if (!same(mid, p[k])) continue;
                        for (int x = 1; x <= n; ++x)
                            if (x != i && x != j && x != k)
                            {
                                if (same(dis(p[x], p[k]), dis(p[i], p[j])) &&
                                    is(p[i], p[k], p[x])) ++ans;
                            }
                    }
        if (cas != 1) puts("");
        printf("Set #%d: %d\n", cas, ans);
    }
    return 0;
}

H

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 1e7 + 5;

int n, t, a[maxn], x;

int main()
{
      scanf("%d", &t);
    for(int cas = 1; cas <= t; ++cas)
    {
        ll ans=0; int mx = 0;
        scanf("%d",&n);    
        memset(a,0,sizeof(a));
        for(int i = 1; i <= n; ++i) scanf("%d", &x), ++a[x], mx = max(mx, x);
        ans += (ll)a[0] * (n - a[0]) + (ll)a[1] * (n - a[0] - a[1]);
        for(int i = 2; i <= mx; ++i)
            if(a[i])
                for(int j = 2; j <= mx / i; ++j) ans += (ll)a[i] * a[j * i];
        printf("Test case #%d: %lld\n\n", cas, ans);
    } 
    return 0;
}

I

#include <bits/stdc++.h>
#define ll long long
#define P pair<int, int>
using namespace std;

int n, m, k, t, tot;
int mod = 1000000007;
int cnt[20];
P p[20];

ll dfs(int k, int tota)
{
    if (tota == n) { return 1; }
    ll ans = 0;
    for (int i = 1; i <= tot; ++i)
        if (cnt[i] && (p[i].first == k || p[i].second == k))
        {
            ll res = 0;
            --cnt[i];
            res = dfs(p[i].first == k ? p[i].second : p[i].first, tota + 1);
            ++cnt[i];
            ans += res * cnt[i];
        }
    return ans;
}

int main()
{
    scanf("%d", &t);
    for (int cas = 1; cas <= t; ++cas)
    {
        scanf("%d", &n);
        tot = 0;
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d%d", &p[i].first, &p[i].second);
            if (p[i].first > p[i].second) swap(p[i].first, p[i].second);
            cnt[i] = 0;
        }
        sort(p + 1, p + 1 + n);
        for (int i = 1; i <= n; ++i)
        {
            int j = i;
            while (i + 1 <= n && p[i] == p[i + 1]) ++i;
            p[++tot] = p[i], cnt[tot] = i - j + 1;
        }
        ll ans = 0;
        for (int i = 1; i <= tot; ++i)
        {
            --cnt[i];
            ll res = dfs(p[i].first, 1);
            if (p[i].first != p[i].second) res += dfs(p[i].second, 1);
            ++cnt[i];
            ans += res * cnt[i];
        }
        int flag = (tot == 1 && p[1].first != p[1].second);
        printf("%lld", (ans >> flag) % mod);
        if (cas < t) puts("");
    }
    return 0;
}

 

上一篇:分布式事务lcn手动回滚


下一篇:Fireworks 期望 + 概率 ICPC2020 上海