最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

天天最新：Educational Codeforces Round 14

来源：博客园


(资料图片)

Educational Codeforces Round 14

A Fashion in Berland

做法：模拟代码：

void solve(){    int n;    cin >> n;    int ans = 0;    for (int i = 1;i <= n;i ++) {        int x;        cin >> x;        ans += x;    }      if(n == 1) {        if(ans == 1)        cout << "YES" << endl;        else cout << "NO" << endl;    }else if(n > 1) {        if(ans == n - 1) cout << "YES" << endl;        else cout << "NO" << endl;    }}

B s-palindrome

做法：模拟，前三题都纯模拟 看代码就好了代码：

bool check(char a,char b) {    if(a == b) {        if(a == "A" || a == "H" || a == "W" || a == "T" || a == "Y" || a == "U" || a == "I" || a == "O") return 1;        if(a == "M" || a == "V" || a == "X") return 1;        if(a == "o" || a == "w" || a == "x" || a == "v") return 1;        return 0;    }    else {        if(a == "b" && b == "d") return 1;        if(a == "p" && b == "q") return 1;        if(a == "d" && b == "b") return 1;        if(a == "q" && b == "p") return 1;        return 0;    }    return 0;}bool checklast(char a) {     if(a == "A" || a == "H" || a == "W" || a == "T" || a == "Y" || a == "U" || a == "I" || a == "O") return 1;    if(a == "M" || a == "V" || a == "X") return 1;    if(a == "o" || a == "w" || a == "x" || a == "v") return 1;        return 0;}void solve(){       string s;    cin >> s;    int n = s.size();    s = " " + s;    bool f = 1;    for (int i = 1;i <= n / 2;i ++ ) {        if(check(s[i] , s[n - i + 1]) == 0) f = 0;    }    if(n & 1) {        if(checklast(s[n / 2 + 1]) == 0) f = 0;    }    cout << ((f == 1) ? "TAK": "NIE") << endl;}

C Exponential notation

做法：纯纯的模拟，有点恶心，要分小数点的前后来看代码:

void solve(){       string s;    cin >> s;    int n = s.size();    s = " " + s;    int pos = n + 1;    for (int i = 1;i <= n;i ++) {        if(s[i] == ".") pos = i;    }    if(pos == 0) pos == n + 1;    int stq = -1,sth = -1;     for (int i = 1;i <= n;i ++) {        if(s[i] != "0" && s[i] != ".") {            stq = i;            break;        }    }    for (int i = n;i >= 1;i --) {        if(s[i] != "0" && s[i] != ".") {            sth = i;            break;        }    }    if(stq == -1 && sth == -1) {        cout << 0 << endl;        return;    }    cout << s[stq];    if(stq != sth) cout << ".";    for (int i = stq + 1;i <= sth;i ++) {        if(s[i] == ".") continue;        cout << s[i];    }    if(stq > pos) {        if(stq - pos != 0)        cout << "E-" << stq - pos << endl;    }    else {        if(pos - stq - 1 != 0)        cout << "E" << pos - stq - 1 << endl;    }}

D Swaps in Permutation

做法:这种排列题想到用图去做是一件很显然的思路，所以其实就是用并查集去维护每一个连通块，把每一个连通分块的数放在堆上，按顺序一个个输出就可以了。代码：

priority_queue q[N];int f[N];int find(int x) {    if(x != f[x]) f[x] = find(f[x]);    return f[x];}void solve(){       int n , m;    cin >> n >> m;    vector a(n + 1);    for (int i = 1;i <= n;i ++) cin >> a[i], f[i] = i;    for (int i = 1;i <= m;i ++) {        int x, y;        cin >> x >> y;        x = find(x);        y = find(y);        if(x != y) f[x] = y;    }    for (int i = 1;i <= n;i ++) q[find(i)].emplace(a[i]);    // for (int i = 1;i <= n;i ++) cout << find(i) << " ";    for (int i = 1;i <= n;i ++) {        cout << q[find(i)].top() << " ";        q[find(i)].pop();    }    cout << endl;}

E Xor-sequences

做法：很棒的一道矩阵加速加dp题，这道题我一开始做的时候甚至没有想到暴力的递推去做，其实想想是比较显然的，我们可以这么考虑，当前元素是否能放入，那么只和前面一个元素有关，状态可以这么去考虑，\(dp_{i,j}\)为当前放到第\(i\)个位置，放第\(j\)个元素的方案数，那么递推方程为\(dp_{i, j} = \sum_{k = 1}^{n}dp_{i - 1,k}\ast \left [ popcount(a_{k}\bigoplus a_{j} |3) \right ]\)\(k\)是\(10^{18}\)所以显然这个方程直接去做是超时的，我们可以考虑矩阵加速，因为这个\(popcount\)是可以预处理出来的，做一个矩阵快速幂即可。代码:

int sz;struct mat {int a[115][115];inline mat() { memset(a, 0, sizeof a); } inline mat operator-(const mat& T) const {    mat res;    for (int i = 1; i <= sz; ++i)      for (int j = 1; j <= sz; ++j) {        res.a[i][j] = (a[i][j] - T.a[i][j]) % mod;      }    return res;  } inline mat operator+(const mat& T) const {    mat res;    for (int i = 1; i <= sz; ++i)      for (int j = 1; j <= sz; ++j) {        res.a[i][j] = (a[i][j] + T.a[i][j]) % mod;      }    return res; }   inline mat operator*(const mat& T) const {    mat res;    int r;    for (int i = 1; i <= sz; ++i)      for (int k = 1; k <= sz; ++k) {        r = a[i][k];        for (int j = 1; j <= sz; ++j)          res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= mod;      }    return res;    }  inline mat operator^(int x) const {    mat res, bas;    for (int i = 1; i <= sz; ++i) res.a[i][i] = 1;    for (int i = 1; i <= sz; ++i)      for (int j = 1; j <= sz; ++j) bas.a[i][j] = a[i][j] % mod;    while (x) {      if (x & 1) res = res * bas;      bas = bas * bas;      x >>= 1;             }    return res;    }}; const double eps = 1e-8;// const int M = N * 4;mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());void solve(){       int n ,k ;    cin >> n >> k;    vector a(n + 1);    for (int i = 1;i <= n;i ++) cin >> a[i];    vector f(n + 1);    mat C;    sz = n;    for (int i = 1;i <= n;i ++) {        for (int j = 1;j <= n;j ++) {            int x = a[i] ^ a[j];            int cnt = 0;            while(x) {                if(x & 1) cnt++;                x >>= 1;            }            if(cnt % 3 == 0) C.a[i][j] = 1;        }    }    C = C.operator^(k - 1);    int ans = 0;    mat Ori;    for (int i = 1;i <= n;i ++) Ori.a[1][i] = 1;    for (int i = 1;i <= n;i ++) {        for (int j = 1;j <= n;j ++) {            ans = (ans + Ori.a[1][j] * C.a[j][i] % mod) % mod;        }    }    cout << ans << endl;}

关键词： 就可以了 可以考虑 是一件很