NEFU 10.9(SWERC2020)

A.Gratitude

题意

给定 3 n 3n 3n个字符串和参数 K K K，输出这些字符串中出现次数最多的前 K K K个；出现次数相同的字符串，输出最后一次出现最晚的一个。
1 ≤ K ≤ 3 N ≤ 100 , 000 1le Kle 3Nle 100,000 1≤K≤3N≤100,000

思路
我自己是用了map反复横跳存储信息，但是我的队友赛后又给出了一套比我简洁n倍的代码
代码

#include 
using namespace std;
struct sa {
    int id;
    int num;
};
bool cmp(const sa& a, const sa& b)
{
    if (a.num != b.num)
        return a.num > b.num;
    return a.id > b.id;
}
sa a[100005];
int n, k, cnt1;
string s;
set se;
map m1;
map m2;
int cnt[100005];
int main()
{
    memset(cnt, 0, sizeof(cnt));
    cin >> n >> k;
    getchar();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 3; j++) {
            getline(cin, s);
            if (se.find(s) == se.end()) {
                se.insert(s);
                m1[s] = ++cnt1;
                m2[cnt1] = s;
                cnt[cnt1]++;
            } else {
                cnt[++cnt1] = cnt[m1[s]] + 1;
                cnt[m1[s]] = 0;
                m1[s] = cnt1;
                m2[cnt1] = s;
            }
        }
    }
    for (int i = 1; i <= cnt1; i++)
        a[i] = { i, cnt[i] };
    sort(a + 1, a + 1 + cnt1, cmp);
    // for (int i = 1; i <= cnt1; i++)
    //     cout << a[i].id << ' ' << a[i].num << "n";
    for (int i = 1; i <= k && i <= cnt1; i++)
        if (a[i].num)
            cout << m2[a[i].id] << "n";
    return 0;
}

在此附上dalao的代码

#include 
using namespace std;
#define LL long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            
    ios::sync_with_stdio(false);                                                                                       
    cin.tie(0);                                                                                                        
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair PII;
const int INF = 0x3f3f3f3f;

unordered_map xianhou;
unordered_map cnt;

struct sa
{
    string s;
    int xianhou, cnt;

    bool operator<(const sa &a) const
    {
        if (cnt != a.cnt)
            return cnt > a.cnt;
        else
            return xianhou > a.xianhou;
    }
    sa(string s, int xianhou, int cnt) : s(s), xianhou(xianhou), cnt(cnt){};
};

signed main()
{
    IOS;
    int n, k;
    string s;
    cin >> n >> k;
    getline(cin, s);
    for (int i = 1; i <= 3 * n; ++i){
        getline(cin, s);
        cnt[s]++;
        xianhou[s] = i;
    }
    vector v;
    for (auto [a, b] : xianhou)
        v.emplace_back(sa(a, b, cnt[a]));
    sort(v.begin(), v.end());

    for (int i = 0; i < min(k, SZ(v)); ++i)
        cout << v[i].s << 'n';
    return 0;
}

C.Safe Distance

题意

给定 x O y xOy xOy平面和平面上的若干个点，要从 ( 0 , 0 ) (0,0) (0,0)出发到达 ( X , Y ) (X,Y) (X,Y)，要求路径距离给出的点尽可能远，求出路径与最近的点的距离的最大值
1 ≤ X , Y ≤ 1 0 6 1le X,Yle 10^6 1≤X,Y≤106
1 ≤ n ≤ 1000 1le n le 1000 1≤n≤1000

思路
考虑二分答案
假设我们二分得到的答案为 m i d mid mid，对其检查可行性
在平面上以所有的点为圆心画半径为 m i d mid mid的圆，那么路径不应该与这些圆有交点
想象将这些圆在平面上挖去，那么如果 m i d mid mid为可行答案， ( 0 , 0 ) (0,0) (0,0)与 ( X , Y ) (X,Y) (X,Y)应仍连通
接下来考虑如何表示 ( 0 , 0 ) (0,0) (0,0)与 ( X , Y ) (X,Y) (X,Y)的连通性
假设我们要将平面沿一条线（可以是曲线）切开，使得 ( 0 , 0 ) (0,0) (0,0)与 ( X , Y ) (X,Y) (X,Y)不连通，这条线应当与平面的左边界和下边界、或左边界和右边界、或上边界和右边界、或上边界和下边界同时存在交点
那么如果我们画的圆的并能够包含这样的一条线， ( 0 , 0 ) (0,0) (0,0)与 ( X , Y ) (X,Y) (X,Y)就是不连通的
我们可以以所有的点为顶点（称为平面点），点之间的距离为边权建立无向图，同时设置四个顶点 u t , u b , u l , u r u_t,u_b,u_l,u_r ut,ub,ul,ur（称为边界点）分别代表上、下、左、右边界，平面点与边界点间的边的边权为点到对应边界的距离
那么，如果在图上存在一条路径分别以 u l , u b u_l,u_b ul,ub、或 u l , u r u_l,u_r ul,ur、或 u t , u r u_t,u_r ut,ur、或 u t , u b u_t,u_b ut,ub为起点和终点，满足边界点到平面点的边的边权小于等于 m i d mid mid，平面点之间的边的边权小于等于 2 ∗ m i d 2*mid 2∗mid，那么 ( 0 , 0 ) (0,0) (0,0)与 ( X , Y ) (X,Y) (X,Y)就是不连通的
复杂度 O ( n log ⁡ ( X + Y ) ) O(nlog (X+Y)) O(nlog(X+Y))
代码

#include 
using namespace std;
#define ll long long
const int MAXN = 1e3 + 9, MOD = 1e9 + 7;
ll n, m;

double a[MAXN], b[MAXN];
int f[MAXN];
int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[x]);
}
bool check(double mid)
{
    for (int i = 1; i <= n + 4; i++)
        f[i] = i;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n + 4; j++) {
            if (i == j)
                continue;
            if (j == n + 1 || j == n + 2)
                a[j] = a[i];
            if (j == n + 3 || j == n + 4)
                b[j] = b[i];
            double dis = sqrt(pow(a[j] - a[i], 2) + pow(b[j] - b[i], 2));
            if (j <= n && dis < 2 * mid || j > n && dis < mid) {
                int pa = find(i), pb = find(j);
                f[pa] = pb;
            }
        }
    }
    if (find(n + 1) == find(n + 2))
        return 0;
    if (find(n + 1) == find(n + 3))
        return 0;
    if (find(n + 3) == find(n + 4))
        return 0;
    if (find(n + 2) == find(n + 4))
        return 0;
    return 1;
}
int x, y;
void solve()
{
    cin >> x >> y >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    b[n + 1] = a[n + 3] = 0;
    b[n + 2] = y;
    a[n + 4] = x;
    double l = 0, r = 1e6;
    for (int i = 1; i <= 40; i++) {
        double mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    cout << l << endl;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

D.Jogging

题意

定义一个跑步路径为一条从0号顶点出发再回到0号顶点的路径，跑步路径上允许出现重边，允许在一条边上的任意位置折返。如果一条跑步路径经过了之前未出现过的边，那么这条跑步路径就是“有趣的”。
给定 I I I个点 S S S条边的简单无向带权图，下界 L L L和上界 U U U。现要求每天都要有一条”有趣的"跑步路径，且长度在上界和下界之间，问最多可以跑步多少天。
1 ≤ I , S ≤ 100000 1le I,Sle 100000 1≤I,S≤100000
1 ≤ L ≤ U ≤ 42195 1le Lle Ule 42195 1≤L≤U≤42195（一次马拉松的长度）
1 ≤ 边权 ≤ 1000 1le 边权le 1000 1≤边权≤1000

思路
由于我们可以在一条边上来回摩擦，所以不需要关心下界
如果每条跑步路径不原路返回，会使答案更劣，所以原路返回一定是最佳策略
那么题目可以转化成从顶点 0 0 0出发，行走不大于 U 2 frac{U}{2} 2U的距离，最多可以到达多少条边
代码

#include 
using namespace std;
#define ll long long
#define pa pair
const int N = 1e5 + 5;
int n, m, L, U;
struct edge {
    int u, v, w, next;
} g[N * 2];
int head[N], cnt;
void add(int u, int v, int w)
{
    g[++cnt].u = u;
    g[cnt].v = v;
    g[cnt].w = w;
    g[cnt].next = head[u];
    head[u] = cnt;
}
int dist[N], vis[N];
void djs()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[0] = 0;
    priority_queue q;
    q.push({ -dist[0], 0 });
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = g[i].next) {
            int v = g[i].v;
            if (!vis[v] && dist[u] + g[i].w < dist[v]) {
                dist[v] = dist[u] + g[i].w;
                q.push({ -dist[v], v });
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> L >> U;
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    djs();
    int ans = 0;
    for (int i = 1; i <= cnt; i += 2)
        if (min(dist[g[i].u], dist[g[i].v]) * 2 < U)
            ans++;
    cout << ans << "n";
    return 0;
}

E.Cakes

题意

n种原料，给定制作一个蛋糕所需要的各种原料的量 a i a_i ai和现有的量 b i b_i bi，求最多能做多少个蛋糕
n ≤ 10 nle 10 n≤10

思路
输出 m i n { b i a i } min{frac{b_i}{a_i}} min{aibi}
代码

#include 
using namespace std;
#define LL long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            
    ios::sync_with_stdio(false);                                                                                       
    cin.tie(0);                                                                                                        
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair PII;
const int INF = 0x3f3f3f3f;

signed main()
{
    IOS;
    int n;
    cin >> n;
    int mn = INF;
    for (int i = 1; i <= n; ++i)
    {
        int a, b;
        cin >> a >> b;
        mn = min(b / a, mn);
    }
    cout << mn << 'n';
    return 0;
}

NEFU 10.9(SWERC2020)

C/C++/C#相关栏目本月热门文章