JinxiSui - SDUST ACMer

2017-2018 CTU Open Contest

2018-10-22  本文已影响0人  JinxiSui

官方题解 - Presentation of solutions

A - Amusement Anticipation

Gym - 101670A
题意：找一个位置的下标使得从该位置到数组末尾是一个等差数列。
思路：签到题。倒着往前找即可。
AC代码：

# include <iostream>
# include <algorithm>

using namespace std;

const int MAX = 1e3 + 5;

int number[MAX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    while(cin >> n)
    {
        for(int i = 1; i <= n; I++)
        {
            cin >> number[I];
        }

        int ans = 1;
        for(int i = n - 2; i > 0; I--)
        {
            if(number[i] - number[i + 1] != number[i + 1] - number[i + 2])
            {
                ans = i + 1;
                break;
            }
        }
        cout << ans << endl;
    }
}

B - Pond Cascade

Gym - 101670B

AC代码：

# include <iostream>
# include <cstdio>
# include <queue>

using namespace std;

const int MAX = 1e5 + 5;

struct Node
{
    void init(long long s, int pr, int no, int ne)
    {
        finish = false;
        speed = s;
        baseTime = 0;
        finishTime = value / speed;
        prev = pr;
        now = no;
        next = ne;
    }

    bool finish;
    double value;
    long long speed;
    double baseTime;
    double finishTime;
    int prev, now, next;

    friend bool operator < (Node a, Node b)
    {
        return a.finishTime > b.finishTime;
    }
};

Node node[MAX];

priority_queue<Node> order;

int main()
{
    int n;
    long long f;
    while(~scanf("%d%lld", &n, &f))
    {
        for(int i = 0; i < n; i++)
        {
            scanf("%lf", &node[i].value);
            node[i].init(f, i - 1, i, (i == n - 1? -1: i + 1));
            order.push(node[i]);
        }

        int now, next, prev;
        while(!order.empty())
        {
            now = order.top().now;
            order.pop();

            if(node[now].finish)
                continue;

            node[now].finish = true;
            next = node[now].next;
            prev = node[now].prev;

            if(prev != -1)
                node[prev].next = next;
            if(next != -1)
                node[next].prev = prev;

            if(next != -1)
            {
                node[next].value -= 1.0 * node[next].speed * (node[now].finishTime - node[next].baseTime);
                node[next].baseTime = node[now].finishTime;
                node[next].speed += node[now].speed;
                node[next].finishTime = node[next].baseTime + node[next].value / node[next].speed;

                order.push(node[next]);
            }
        }

        double finishTime = 0, lastTime = node[n - 1].finishTime;
        for(int i = 0; i < n; i++)
            finishTime = max(finishTime, node[i].finishTime);

        printf("%.8f %.8f\n", lastTime, finishTime);
    }
}

C - Chessboard Dancing

Gym - 101670C

题意：在n*n的棋盘上摆放舞蹈队伍，不同类型摆放要求不同
思路：画一下就能发现规律了
主要是Knight这个，容易不太好想，其实只要交错填入1、2，就可以了（如下图）

Knight(N)
AC代码： 
# include <iostream>
# include <algorithm>

using namespace std;

int main()
{
    int n;
    char ch;
    while(cin >> n >> ch) {
        if(ch == 'B' || ch == 'R')
            cout << n << endl;
        else if(ch == 'K') {
            if(n == 1)
                cout << 1 << endl;
            else
                cout << 4 << endl;
        }
        else if(ch == 'N'){
            if(n == 1 || n == 2)
                cout << 1 << endl;
            else
                cout << 2 << endl;
        }
    }
    return 0;
}

D - Equinox Roller Coaster

Gym - 101670D

E - Forest Picture

Gym - 101670E
题意：画森林，m*m的画布，n条绘画指令。指令为s, x, y。s表示树高，x,y是坐标，树可能在画布外面，也有可能一部分在画布外，如果s == 0， 该位置为"_o_"（树墩），若s > 1，表示树高，有高度的树，树根是"_|_"，树干是"/|\"，树顶" ^ "。
思路：由于1 ≤ M ≤ 100, 1 ≤ N ≤ 10^5，0≤S≤9, −10^9 ≤ X, Y ≤10^9，比较有意思的是x，y虽然很大，但是树高S很小，而且绘图纸的大小也很小，所以直接模拟即可
AC代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 150;
char mp[maxn][maxn];
int m, n;
int s, x, y;

void init() {
   for(int i = 0; i < m; ++i) {
       for(int j = 0; j < m; ++j) {
           mp[i][j] = '.';
       }
       mp[i][m] = '\0';
   }
}

bool judge(int x, int y) {
   if(x >= 0 && x < m && y >= 0 && y < m)
       return true;
   return false;
}

bool judgexy(int x) {
   if(x >= 0 && x < m)
       return true;
   return false;
}

void draw() {
   if(judge(x-1, y))  mp[y][x-1] = '_';
   if(judge(x+1, y))  mp[y][x+1] = '_';
   if(s == 0) {
       if(judge(x, y))    mp[y][x] = 'o';
   }
   else {
       if(x >= 0 && x < m) {
           for(int i = 0; i < s+1; ++i) {  //mid
               if(y+i >= 0 && y+i < m) {
                   mp[y+i][x] = '|';
               }
           }
       }
       if(judge(x, y+s+1)) {
           mp[y+s+1][x] = '^';
       }
       if(judgexy(x-1)) {
           for(int i = 0; i < s; ++i) {
               if(judgexy(y+1+i)) {
                   mp[y+1+i][x-1] = '/';
               }
           }
       }
       if(judgexy(x+1)) {
           for(int i = 0; i < s; ++i) {
               if(judgexy(y+1+i)) {
                   mp[y+1+i][x+1] = '\\';
               }
           }
       }
   }
}

int main() {
   while(scanf("%d%d", &m, &n) == 2) {
       init();
       for(int i = 0; i < n; ++i) {
           scanf("%d%d%d", &s, &x, &y);
           draw();
       }
       for(int i = 0; i < m+2; ++i)
           printf("*");
       printf("\n");
       for(int i = m-1; i >= 0; --i) {
           printf("*");
           printf("%s", mp[i]);
           printf("*\n");
       }
       for(int i = 0; i < m+2; ++i)
           printf("*");
       printf("\n\n");
   }
   return 0;
}

F - Shooting Gallery

Gym - 101670F

G - Ice cream samples

Gym - 101670G

题意：n种售卖，k种冰淇淋品牌，每一种售卖有L个冰淇淋，品牌分别为a[0], a[1], a[2], ..., a[k-1]。现在要从一个位置开始买，买尽量少的冰淇淋来集齐k种品牌，问最少要买多少个冰淇淋，如果无法集齐k种品牌，输出-1。
思路：尺取（双指针法）。由于必须连续买，所以就是在确定一个购买起点和一个终点。

H - Dark Ride with Monsters

Gym - 101670H

题意：给出一个1-n的序列，问交换多少次才能得到1-n的正序序列
思路：将给出的序列和正序序列比较，找闭合的环，答案为n-闭合环数量
AC代码：

# include <iostream>
# include <algorithm>
# include <cstring>

using namespace std;

const int MAX = 2e5 + 5;
int number[MAX];
bool used[MAX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    while(cin >> n)
    {
        memset(used, false, sizeof(used));
        for(int i = 1; i <= n; i++)
        {
            cin >> number[i];
        }

        int ans = 0;
        for(int i = 1; i <= n; i++)
        {
            if(!used[i])
            {
                int now = i, base = i;
                used[now] = true;

                while(number[now] != base)
                {
                    now = number[now];
                    used[now] = true;
                }

                ans++;
            }
        }

        cout << n - ans << endl;
    }
}

I - Go Northwest!

Gym - 101670I

AC代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
    long long n, x, y;
    while(~scanf("%lld", &n)) {
        map<long long, long long> mp1, mp2;
        for(long long i = 0; i < n; ++i) {
            scanf("%lld %lld", &x, &y);
            mp1[x + y]++;
            mp2[y - x]++;
        }
        long long sum = 0;
        for(map<long long, long long>::iterator it = mp1.begin(); it != mp1.end(); ++it) {
            sum += (it->second - 1) * it->second;
        }
        for(map<long long, long long>::iterator it = mp2.begin(); it != mp2.end(); ++it) {
            sum += (it->second - 1) * it->second;
        }
        printf("%.8f\n", (double)sum / ((double)n * (double)n));
    }
    return 0;
}

J - Punching Power

Gym - 101670J

题意：给出一些点的坐标，选尽量多的点使得剩下的点两两之间的距离都大于1.3
思路：将不满足距离 > 1.3的点建边跑二分图匈牙利匹配，答案 = 点数 - 匹配数。
建图：奇偶匹配，根据每个点 坐标x+y的奇偶（每个点和与它相临距离 < 1.3 的坐标x+y奇偶性肯定不同） 化为二分图，距离<1.3的（其实就是距离==1的）之间连边，跑匈牙利即可。
AC代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>

using namespace std;
const int maxn = 2000 + 5;
int n;
int tot;
vector<int> g[maxn];
int match[maxn];
bool used[maxn];
map<pair<int, int>, int> mp;
int turn[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
struct node {
    int x, y;
}p[maxn];

void addedge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

bool dfs(int v) {
    used[v] = true;
    for(int i = 0; i < g[v].size(); ++i) {
        int u = g[v][i];
        int w = match[u];
        if(w < 0 || !used[w] && dfs(w)) {
            match[v] = u;
            match[u] = v;
            return true;
        }
    }
    return false;
}

int solve() {
    int res = 0;
    memset(match, -1, sizeof match);
    for(int v = 1; v <= n; ++v) {
        if(match[v] < 0) {
            memset(used, false, sizeof used);
            if(dfs(v)) {
                ++res;
            }
        }
    }
    return res;
}

void init() {
    tot = 0;
    for(int i = 1; i <= n; ++i)
        g[i].clear();
    mp.clear();
}

int main() {
    while(scanf("%d", &n) == 1) {
        init();
        for(int i = 0; i < n; ++i) {
            scanf("%d%d", &p[i].x, &p[i].y);
            mp[make_pair(p[i].x, p[i].y)] = ++tot;
        }
        int xx, yy;
        int id1, id2;
        bool flag;
        for(int i = 0; i < n; ++i) {
            flag = false;
            id1 = mp[make_pair(p[i].x, p[i].y)];
            if( (p[i].x+p[i].y) % 2 == 0 )
                flag = 1;
            else flag = 0;
            for(int k = 0; k < 4; ++k) {
                xx = p[i].x + turn[k][0], yy = p[i].y + turn[k][1];
                id2 = mp[make_pair(xx, yy)];
                if(id2) {
                    if(((xx + yy) % 2 == 0 && flag == 0)||((xx + yy) % 2 == 1 && flag == 1)) {
                        addedge(id1, id2);
                    }
                }
            }
        }
        printf("%d\n", n - solve());
    }
    return 0;
}

K - Treetop Walkway

Gym - 101670K

上一篇 下一篇

猜你喜欢

热点阅读