您的位置: 首页  >  IT文章  >  2020牛客暑期多校训练营（第二场）

2020牛客暑期多校训练营（第二场）

分类: IT文章 • 2023-11-18 11:20:42

目录

Contest Info

传送门

Solved A B C D E F G H I J K
11 / 11 Ø Ø O O Ø O Ø Ø Ø O Ø
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • - 没有尝试

Solutions

A. All with Pairs

题意：
定义(f(s,t))为最大的(i)满足(s)串前(i)个与(t)串后(i)个相匹配。
现给出(n)个串，计算

[sum_{i=1}^nsum_{j=1}^mf(s_i,s_j)^2 ]

(displaystyle nleq 10^5,sum |s_i|leq 10^6)。

思路：
计算两个串相匹配一般可以用hash，注意到所有后缀个数的和最多为(10^6)级别，我们首先保存所有后缀的hash值。
对于每一个串的每一个前缀，很容易计算出(cnt[i])即多少个后缀与其匹配。但是这样并不能直接统计入答案，可能会出现重复计算，比如(aba)，显然(a)和(aba)不能一起算，只能算后面的。
上例给了我们启示，通过字符串的next数组去重即可，具体就是从小到大枚举(i)，(cnt[next[i]]-cnt[i])。这样去重过后剩下的(cnt[i])才是符合要求的。
我代码因为用map存了hash值，所以时间复杂度多了个log。实际上可以通过AC自动机+KMP做到线性复杂度，也即是通过fail树计算出cnt数组再通过next去重。
hash代码如下：

Code
// Author : heyuhhh
// Created Time : 2020/07/14 09:32:51
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e6 + 5, MOD = 998244353;
void err(int x) {cerr << x;}
void err(long long x) {cerr << x;}
void err(double x) {cerr << x;}
void err(char x) {cerr << '"' << x << '"';}
void err(const string &x) {cerr << '"' << x << '"';}
void _print() {cerr << "]
";}
template<typename T, typename V>
void err(const pair<T, V> &x) {cerr << '{'; err(x.first); cerr << ','; err(x.second); cerr << '}';}
template<typename T>
void err(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), err(i); cerr << "}";}
template <typename T, typename... V>
void _print(T t, V... v) {err(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef Local
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
typedef unsigned long long ull;
template <unsigned mod, unsigned base>
struct rolling_hash {
    unsigned int pg[N], val[N]; // val:1,2...n
    rolling_hash() {
        pg[0] = 1;
        for(int i = 1; i < N; i++) pg[i] = 1ull * pg[i - 1] * base % mod;
        val[0] = 0;
    }
    void build(const char *str) {
        for(int i = 0; str[i]; i++) {
            val[i + 1] = (str[i] + 1ull * val[i] * base) % mod;
        }
    }
    unsigned int operator() (int l, int r) {
        ++r; //
        return (val[r] - 1ull * val[l] * pg[r - l] % mod + mod) % mod;
    }
};
struct dm_hasher {
    //str:0,1...len-1
    rolling_hash<997137961, 753> h1;
    rolling_hash<1003911991, 467> h2;
    void build(const char *str) {
        h1.build(str); h2.build(str);
    }
    ull operator() (int l, int r) {
        return ull(h1(l, r)) << 32 | h2(l, r);
    }
}hasher;
 
int nxt[N];
 
void Get_next(const char *s) {
    int j, L = strlen(s);
    nxt[0] = j = -1;
    for(int i = 1; i < L; i++) {
        while(j >= 0 && s[i] != s[j + 1]) j = nxt[j] ;
        if(s[i] == s[j + 1]) j++;
        nxt[i] = j;
    }
}
 
int n;
string str[N];
unordered_map<ll, int> cnt;
 
void run() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> str[i];
        hasher.build(str[i].c_str());
        int len = str[i].length();
        for (int j = len - 1; j >= 0; j--) {
            cnt[hasher(j, len - 1)]++;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        Get_next(str[i].c_str());
        hasher.build(str[i].c_str());
        int len = str[i].length();
        for (int j = 0; j < len; j++) {
            if (nxt[j] >= 0) {
                cnt[hasher(0, nxt[j])] -= cnt[hasher(0, j)];
            }
        }
        for (int j = 0; j < len; j++) {
            dbg(i, j, cnt[hasher(0, j)]);
            ans += 1ll * cnt[hasher(0, j)] % MOD * (j + 1) % MOD * (j + 1) % MOD;
            if (ans >= MOD) ans -= MOD;
        }
        for (int j = len - 1; j >= 0; j--) {
            if (nxt[j] >= 0) {
                cnt[hasher(0, nxt[j])] += cnt[hasher(0, j)];
            }
        }
    }
    cout << ans << '
';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

B. Boundary

枚举两个点确定出圆心直接计数即可。
这里通过sort来计数，比直接map来要快一些。

Code
// Author : heyuhhh
// Created Time : 2020/07/14 17:06:09
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2000 + 5;
const double eps = 1e-10;
typedef pair<double, double> pdd;
int n;
struct Point {
    int x, y;
} a[N];
pdd solve(Point a, Point b, Point c) //三点共圆圆心公式
{
    double fm1=2 * (a.y - c.y) * (a.x - b.x) - 2 * (a.y - b.y) * (a.x - c.x);
    double fm2=2 * (a.y - b.y) * (a.x - c.x) - 2 * (a.y - c.y) * (a.x - b.x);
    if (fm1 == 0 || fm2 == 0) {
        return MP(1e18, 1e18);
    }
    double fz1=a.x * a.x - b.x * b.x + a.y * a.y - b.y * b.y;
    double fz2=a.x * a.x - c.x * c.x + a.y * a.y - c.y * c.y;
 
    double X = (fz1 * (a.y - c.y) - fz2 * (a.y - b.y)) / fm1;
    double Y = (fz1 * (a.x - c.x) - fz2 * (a.x - b.x)) / fm2;
    return MP(X, Y);
}
 
bool operator == (pdd A, pdd B) {
    return fabs(A.fi - B.fi) <= eps && fabs(A.se - B.se) <= eps;
}
 
void run() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
    }
    vector<pdd> res;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            pdd now = solve({0, 0}, a[i], a[j]);
            if (now == MP(1e18, 1e18)) continue;
            res.push_back(now);
        }
    }
    if (sz(res) == 0) {
        cout << 1 << '
';
        return;
    }
    sort(all(res));
    int ans = 1, t = 1;
    pdd now = res[0];
    for (int i = 1; i < sz(res); i++) {
        if (res[i] == now) {
            ++t;
        } else {
            ans = max(ans, t);
            now = res[i];
            t = 1;
        }
    }
    ans = max(ans, t);
    for (int i = 2; i <= n; i++) {
        if (i * (i - 1) == 2 * ans) {
            cout << i << '
';
            return;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

C. Cover the Tree

设叶子结点个数为(x)，那么答案下界即为(lceilfrac{x}{2} ceil)。
实际上可以通过构造达到该下界，首先我们找到一个度数大于(1)的结点作为根，然后要使叶子结点尽量不在某颗子树内匹配完，否则会多出一条边。所以感受一下就会发现把叶子结点划为两部分，之后对应相匹配就行。

Code
// Author : heyuhhh
// Created Time : 2020/07/13 12:22:14
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5;

vector<int> G[N];
int n;
vector<int> v;
void dfs(int u, int fa) {
    int sons = 0;
    for (auto v : G[u]) {
        if (v != fa) {
            dfs(v, u);
            ++sons;
        }
    }
    if (sons == 0) {
        v.push_back(u);
    }
}

int d[N];

void run() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v; 
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
        ++d[u], ++d[v];
    }
    int rt = 1;
    for (int i = 1; i <= n; i++) {
        if (d[i] > 1) {
            rt = i;
        }
    }
    dfs(rt, 0);
    int len = sz(v);
    int t = (len + 1) / 2;
    vector<pii> ans;
    for (int i = 0; i + t < len; i++) {
        ans.push_back(MP(v[i], v[i + t]));
    }
    if (len & 1) {
        if (v[len / 2] != rt) {
            ans.push_back(MP(v[len / 2], rt));
        }
    }
    cout << sz(ans) << '
';
    for (auto it : ans) {
        cout << it.fi << ' ' << it.se << '
';
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

D. Duration

签到。

Code
import datetime
def foo():
    a = 200
    print(a)
     
def minNums(startTime, endTime):
     
     
    startTime1 = startTime
    endTime1 = endTime
     
    startTime2 = datetime.datetime.strptime(startTime1, "%Y-%m-%d %H:%M:%S")
    endTime2 = datetime.datetime.strptime(endTime1, "%Y-%m-%d %H:%M:%S")
    seconds = (endTime2 - startTime2).seconds
     
    total_seconds = (endTime2 - startTime2).total_seconds()
    if total_seconds < 0:
        total_seconds = -total_seconds
    print(int(total_seconds))
    mins = total_seconds / 60
    return int(mins)
 
if __name__ == "__main__":
    s='2020-07-28 '
    st=input()
    startTime_1 = s+st
    en=input()
    endTime_1 = s+en
    fenNum = minNums(startTime_1, endTime_1)

E. Exclusive OR

题意：
给出(n)个数(a_1,a_2,cdots,a_n)，接下来要输出(n)个数，第(i)个数为从序列中选出(i)个可重复的数，异或的最大值。
(1leq nleq 2cdot 10^5,0leq a_i<2^{18})。

思路：
首先容易发现线性空间的秩为(18)，也就是最多(n=18)时能取到异或的最大值。
并且也很容易发现(ans_igeq ans_{i-2})。
所以小范围考虑暴力，大范围直接通过取等号即可，暴力的话直接通过FWT对值域卷积即可。
正常来想当(igeq 19)时不等式取等号，即(ans_i=ans_{i-2})。
但实际上这里要取到(20)。也就是(ans_{19}>ans_{17})是可能会存在的，并且也可以构造相应的数据出来。这里可以这样想，我们将第(18)个数和第(19)个数两个数的异或值看作一个新的第(18)个数来异或出最大值，这肯定没问题；对于(igeq 20)时，新的第(18)个数是至少三个数异或起来的，这肯定没必要，因为我们只拿一个数，另外偶数个数相互抵消就行，也就是此时只能取等号。
所以异或卷积(19)次把小范围情况解决啦就行。

Code
// Author : heyuhhh
// Created Time : 2020/07/14 14:38:56
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e6 + 5;

void FWT_xor(int *a, int n, int op) {
    for(int i = 1; i < n; i <<= 1)
        for(int p = i << 1, j = 0; j < n; j += p)
            for(int k = 0; k < i; k++) {
                int X = a[j + k], Y = a[i + j + k];
                a[j + k] = (X + Y); a[i + j + k] = (X - Y);
                if(op == -1) a[j + k] = a[j + k] / 2, a[i + j + k] = a[i + j + k] / 2;
            }
}

int n;
int a[N], b[N];
int ans[N];

void run() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        a[x] = b[x] = 1;
        ans[1] = max(ans[1], x);
    }

    int L = (1 << 18);  
    FWT_xor(b, L, 1);  
    for (int k = 2; k <= 19; k++) {
        FWT_xor(a, L, 1);
        for (int i = 0; i < L; i++) {
            a[i] *= b[i];
        }
        FWT_xor(a, L, -1);
        for (int i = 0; i < L; i++) {
            if (a[i] > 0) {
                ans[k] = i;
                a[i] = 1;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i > 19) ans[i] = ans[i - 2];
        cout << ans[i] << " 
"[i == n];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

F. Fake Maxpooling

二维单调队列模板题。

Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5005, M = 5000, T = 1000;
int a, b, n;
int mp[N][N], tmp[N][2];
int q1[N][N], l1[N], r1[N];
int Q1[N];

int Gcd[N][N];

int main() {
    ios::sync_with_stdio(false); cin.tie(0) ;
    cin >> a >> b >> n;
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            if (!Gcd[i][j]) {
                for (int k = 1; k * i <= a && k * j <= b; k++)
                    Gcd[k * i][k * j] = k, mp[k * i][k * j] = i * j * k;
            }
        }
    }

    for(int i = 1; i <= b; i++) l1[i] = 1;
    ll ans = 0;
    for(register int i = 1; i <= a; i++) {
        for(register int j = 1; j <= b; j++) {
            while(l1[j] <= r1[j] && mp[q1[j][r1[j]]][j] <= mp[i][j]) r1[j]--;
            q1[j][++r1[j]] = i ;
            while(l1[j] <= r1[j] && i + 1 - q1[j][l1[j]] > n) l1[j]++;
        }
        for(register int j = 1; j <= b; j++) tmp[j][0] = mp[q1[j][l1[j]]][j];
        int cc1, cc2;
        int L1 = 1, R1 = 0, L2 = 1, R2 = 0;
        for(register int j = 1; j <= b; j++) {
            while(L1 <= R1 && tmp[Q1[R1]][0] <= tmp[j][0]) R1--;
            Q1[++R1] = j ;
            while(L1 <= R1 && j + 1 - Q1[L1] > n) L1++;
            if(i >= n && j >= n) {
                ans += tmp[Q1[L1]][0];
            }
        }
    }
    cout << ans;
    return 0;
}

G. Greater and Greater

维护的是对于每个(b_i)，哪些位置(a_j>=b_i)，然后从(b_1)开始确定出哪些(a)能作为区间的第一个，自然会产生区间第二个位置的备选集合，我们只需要拿(b_2)的bitset与备选集合交一下就能确定哪些(a)能作为第二个...依次往下操作就行了。
细节见代码：

Code
// Author : heyuhhh
// Created Time : 2020/07/14 11:41:23
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 150000 + 5, M = 40000 + 5;

int n, m;
int a[N], b[M];

int p1[N], p2[N];

bitset<N> res, cur;

void run() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    iota(p1 + 1, p1 + n + 1, 1);
    iota(p2 + 1, p2 + m + 1, 1);
    sort(p1 + 1, p1 + n + 1, [&](int i, int j) {
        return a[i] > a[j];
    });
    sort(p2 + 1, p2 + m + 1, [&](int i, int j) {
        return b[i] > b[j];
    });
    res.set();
    for (int i = 1, p = 1; i <= m; i++) {
        while (p <= n && a[p1[p]] >= b[p2[i]]) {
            cur.set(p1[p]);
            ++p;
        }
        res &= (cur >> (p2[i] - 1));
    }
    int ans = res.count();
    cout << ans << '
';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

H. Happy Triangle

看到了一个很巧妙的写法，写起来也不容易错。
因为判断是否能构成三角形主要是要check这个条件：(a+b>c,a<c,b<c)。
假设我们已知(a,b)，未知(x)，直接想的话肯定是按照上述条件来进行check，这样也可以做的，但是比较麻烦。
实际上既然我们已知(a,b,a<b)，那么此时自然会产生一个答案合法区间((b-a,a+b))，如果有(x)落在这个区间范围内说明合法。
那么只需要通过线段树维护区间加减以及单点查询即可。
要离散化一下才行，不过离散化写起来代码麻烦了许多，其实可以直接标记永久化+动态开点，这样写起来也很容易！标记永久化感觉还是挺好用的，尤其是对于区间上面的操作。
细节见代码吧：

Code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int rb = 1e9;

int Add[N * 21], ls[N * 21], rs[N * 21];
int T, rt;
void update(int& o, int l, int r, int L, int R, int v) {
    if (!o) o = ++T;
    if (L <= l && r <= R) {
        Add[o] += v;
        return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid) update(ls[o], l, mid, L, R, v);
    if (R > mid) update(rs[o], mid + 1, r, L, R, v);
}
void update(int l, int r, int v) {
    ++l, --r;
    l = max(l, 1), r = min(r, rb);
    if (l > r) return;
    update(rt, 1, rb, l, r, v);
}
int query(int o, int l, int r, int p) {
    if (!o) return 0;
    if (l == r) return Add[o];
    int mid = (l + r) >> 1;
    if (p <= mid) return query(ls[o], l, mid, p) + Add[o];
    else return query(rs[o], mid + 1, r, p) + Add[o];
}

int main() {
    multiset<int> s;
    int op, x, q;
    auto gao = [&](multiset<int>::iterator l, multiset<int>::iterator r, int v) {
        if (l != s.begin()) {
            --l;
            update(x - *l, x + *l, v);
            if (r != s.end()) update(*r - *l, *r + *l, -v);
        }
        if (r != s.end()) update(*r - x, *r + x, v);
        return 0;
    };
    scanf("%d", &q);
    while (q--) {
        scanf("%d%d", &op, &x);
        if (op == 1) {
            auto r = s.upper_bound(x), l = r;
            gao(l, r, 1);
            s.insert(x);
        } else if (op == 2) {
            auto r = s.upper_bound(x), l = r; --l;
            gao(l, r, -1);
            s.erase(--r);
        } else {
            int t = query(rt, 1, rb, x);
            if (t > 0) cout << "Yes" << '
';
            else cout << "No" << '
';
        }
    }
    return 0;
}

I. Interval

直接将该二维问题转化为在网格图上的问题，那么会发现是一个很简单的最小割，类似于“狼抓兔子”。
这类问题一般是将网格图转化为对偶图，然后跑个最短路就行了。因为直接冲网络流的话很可能会TLE，因为图的规模太大了，如果找到其对偶图的话图的规模没怎么变，但是最短路能把时间复杂度降下来。
跟“狼抓兔子”很像，难度差不多。

Code
// Author : heyuhhh
// Created Time : 2020/07/14 20:52:56
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 500 + 5, M = 252000 + 5;

int n, m;
int grid[N][N];
int T, s, t;

struct Edge{
    int v, w, next;   
}e[M << 1];
ll dis[M];
struct Dijkstra{
    struct node{
        ll d, u;
        bool operator < (const node &A) const {
            return d > A.d;
        }   
    };
    int head[M], tot;
    bool vis[M];
    void init() {
        memset(head, -1, sizeof(head)); tot = 0;   
    }
    void adde(int u, int v, int w) {
        e[tot].v = v; e[tot].w = w; e[tot].next = head[u]; head[u] = tot++;   
    }
    void dij(int s) {
        priority_queue <node> q;
        memset(dis, INF, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        dis[s] = 0;
        q.push(node{0, s});
        while(!q.empty()) {
            node cur = q.top(); q.pop();
            int u = cur.u, d = cur.d;
            if(vis[u]) continue;
            vis[u] = 1;
            for(int i = head[u]; i != -1; i = e[i].next) {
                int v = e[i].v;
                if(dis[v] > dis[u] + e[i].w) {
                    dis[v] = dis[u] + e[i].w;
                    q.push(node{dis[v], v});   
                }
            }   
        }
    }
}solver;

void run() {
    solver.init();
    cin >> n >> m;
    s = ++T, t = ++T;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            grid[i][j] = ++T;
        }
    }
    for (int i = 2; i <= n; i++) {
        grid[0][i] = s;
    }
    for (int i = 1; i < n; i++) {
        grid[i][n + 1] = t;
    }
    while (m--) {
        int l, r, c;
        string dir;
        cin >> l >> r >> dir >> c;
        if (dir == "L") {
            solver.adde(grid[l][r], grid[l][r + 1], c);
            solver.adde(grid[l][r + 1], grid[l][r], c);
        } else {
            solver.adde(grid[l - 1][r], grid[l][r], c);
            solver.adde(grid[l][r], grid[l - 1][r], c);
        }
    }
    solver.dij(s);
    ll ans = dis[t];
    if (ans >= 1000000000000) {
        ans = -1;
    }
    cout << ans << '
';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

J. Just Shuffle

置换类的问题一般考虑为一张有向图上面的问题。
这个题中建出来的图是走了(k)步过后每个点应该去往哪个点，要找到只走一步每个点该走到哪个点，只需要对每一个环走(inv_{k\% len})步即可，因为(kcdot inv_{k}equiv 1(mod len))，因为(k)是一个大质数，所以这是肯定有解的。代码中通过扩展欧几里得算法求解(inv_k)。（不能通过快速幂来求逆元，因为不满足费马小定理的条件，即模数不为质数）。

Code
// Author : heyuhhh
// Created Time : 2020/07/13 14:01:34
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e6 + 5, MOD = 998244353;
 
int n, k;
vector<int> G[N];
bool vis[N];
int p[N];
 
vector<int> v;
 
void dfs(int u) {
    v.push_back(u);
    vis[u] = true;
    for (auto son : G[u])
        if (!vis[son]) {
            dfs(son);
        }
}
 
void exgcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0) {
        x = 1, y = 0;
        return ;
    }
    exgcd(b,a%b,x,y);
    ll z = x ;
    x = y;
    y = z - y * (a / b);
}
ll calc(ll a, ll b, ll c) {
    ll x, y;
    ll g = __gcd(a, b);
    if(c % g != 0) return -1;
    a /= g, b /= g, c /= g;
    exgcd(a, b, x, y);
    x *= c;
    x = (x % b + b) % b;
    return x;
}
 
void gao(vector<int>& v) {
    int len = sz(v);
    int r = k % len;
    int c = calc(r, len, 1);
    // c: steps need to go
    if (c == -1) {
        cout << -1 << '
';
        exit(0);
    }
    vector<int> res(len);
    for (int i = 0; i < len; i++) {
        res[i] = v[(i + c) % len];
    }
    swap(res, v);
}
 
int in[N], out[N];
 
void run() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        ++out[i], ++in[p[i]];
        G[i].push_back(p[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (in[i] != 1 || out[i] != 1) {
            cout << -1 << '
';
            return;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            v.clear();
            dfs(i);
            vector<int> w = v;
            gao(v);
            for (int j = 0; j < sz(w); j++) {
                p[w[j]] = v[j];
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << p[i] << " 
"[i == n];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(20);
    run();
    return 0;
}

K. Keyboard Free

比较简单的方法，直接模拟积分即可，固定(A)为定点（(A)转动起来没啥用，因为求的是平均意义下的，每个(A)所在位置不同答案都是一样的），然后直接枚举(B,C)的位置，然后通过叉积计算面积就行。
当然还有比较硬核的数学计算方法，通过积分求出来三角形的期望高度，然后计算，积分是通过手算的，我感觉还是有点复杂。。

Code
// Author : heyuhhh
// Created Time : 2020/07/15 11:11:44
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
const double pi = acos(-1.0);
vector<double> Sin(500), Cos(500);
void init() {
    for (int i = 0; i < 500; i++) {
        double a = 2.0 * pi * i / 500;
        Sin[i] = sin(a);
        Cos[i] = cos(a);
    }
}
void run() {
    vector<int> r(3);
    for (int i = 0; i < 3; i++) {
        cin >> r[i];
    }
    sort(all(r));
    double ans = 0;
    for (int i = 0; i < 500; i++) {
        double a = 2.0 * pi * i / 500;
        double x2 = r[1] * Cos[i], y2 = r[1] * Sin[i];
        for (int j = 0; j < 500; j++) {
            double b = 2.0 * pi * j / 500;
            double x3 = r[2] * Cos[j], y3 = r[2] * Sin[j];
            ans += fabs((x2 - r[0]) * y3 - (x3 - r[0]) * y2);
        }
    }
    ans = ans / 500 / 500 / 2;
    cout << ans << '
';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(1);
    init();
    int T; cin >> T; while(T--)
    run();
    return 0;
}

相关推荐