Educational Codeforces Round 151 (Rated for Div. 2)-Toy模板网

这篇具有很好参考价值的文章主要介绍了Educational Codeforces Round 151 (Rated for Div. 2)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Edu 151

A. Forbidden Integer

题意：
你有[1, k]内除了 $x$ 的整数，每个数可以拿多次，问 $\sum = n$ 是否可行并构造
思路：
有1必能构造，否则假如没有1，假如有2, 3必定能构造出大于等于2的所有数，否则只有2的话只能构造出偶数。

#include <bits/stdc++.h>
#define local
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
using db = double;
using PII = pair<int, int>;
using PLI = pair<ll, int>;

template<class T>
ostream &operator<<(ostream &io, vector<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class T>
ostream &operator<<(ostream &io, set<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class K, class V>
ostream &operator<<(ostream &io, map<K, V> a) {
    io << "(";
    for (auto I: a)io << "{" << I.first << ":" << I.second << "}";
    io << ")"; 
    return io;
}

void debug_out() {
    cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H;
    debug_out(T...);
}

#ifdef local
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 1
#endif
#define all(x) x.begin(),x.end()


int main() {
    IOS
    int t;
    cin >> t;
    while (t--) {
        int n, k, x;
        cin >> n >> k >> x;
        if (x == 1) {
            if (k == 1) {
                cout << "NO\n";
            } else if (k == 2) {
                if (n % 2 == 0) {
                    cout << "YES\n";
                    cout << n / 2 << '\n';
                    for (int i = 1; i <= n / 2; ++i) {
                        cout << 2 << " ";
                    }
                    cout << '\n';
                } else {
                    cout << "NO\n";
                }
            } else {
                if (n % 2 == 0) {
                    cout << "YES\n";
                    cout << n / 2 << '\n';
                    for (int i = 1; i <= n / 2; ++i) {
                        cout << 2 << " ";
                    }
                    cout << '\n';
                } else {
                    if (n == 1) {
                        cout << "NO\n";
                    } else {
                        cout << "YES\n";
                        cout << 1 + (n - 3) / 2 << "\n";
                        cout << 3 << " ";
                        for (int i = 1; i <= (n - 3) / 2; ++i) {
                            cout << 2 << " ";
                        }
                        cout << '\n';
                    }
                }
            }
        } else {
            cout << "YES\n";
            cout << n << '\n';
            for (int i = 1; i <= n; ++i) {
                cout << 1 << ' ';
            }
            cout << "\n";
        }
    }
    return 0;
}

B. Come Together

题意：
棋盘上两个点同时从C出发到A, B, 都走最短路径，问最多重叠的格子数
思路：不难发现，x, y轴对答案的贡献是独立的，考虑其中一维，假如在同方向才能有贡献，分类讨论即可。

#include <bits/stdc++.h>
#define local
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
using db = double;
using PII = pair<int, int>;
using PLI = pair<ll, int>;

template<class T>
ostream &operator<<(ostream &io, vector<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class T>
ostream &operator<<(ostream &io, set<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class K, class V>
ostream &operator<<(ostream &io, map<K, V> a) {
    io << "(";
    for (auto I: a)io << "{" << I.first << ":" << I.second << "}";
    io << ")"; 
    return io;
}

void debug_out() {
    cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H;
    debug_out(T...);
}

#ifdef local
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 1
#endif
#define all(x) x.begin(),x.end()


int main() {
    IOS
    int t;
    cin >> t;
    while (t--) {
        int xa, ya, xb, yb, xc, yc;
        cin >> xa >> ya >> xb >> yb >> xc >> yc;
        int x1 = xb - xa, x2 = xc - xa, y1 = yb - ya, y2 = yc - ya;
        int ans = 1;
        if ((ll)x1 * x2 >= 0) {
            if (abs(x1) > abs(x2)) 
                swap(x1, x2);
            ans += abs(x1);
        } 
        if ((ll)y1 * y2 >= 0) {
            if (abs(y1) > abs(y2)) 
                swap(y1, y2);
            ans += abs(y1);
        }
        cout << ans << '\n';
    }
    return 0;
}

C. Strong Password

题意：
给定字符串 $s$ ，问是否存在长度为 $m$ , 每个密码的第 $i$ 位数字在 $l_i, r_i]$ 之间，且不为 $s$ 的子序列的字符串。
思路：
每个密码在 $s$ 中都是独立的，显然我们要让它不为子序列，贪心的考虑在 $i$ 这个位置选择最靠后的字母，建出子序列自动机模拟即可。

#include <bits/stdc++.h>
#define local
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
using db = double;
using PII = pair<int, int>;
using PLI = pair<ll, int>;

template<class T>
ostream &operator<<(ostream &io, vector<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class T>
ostream &operator<<(ostream &io, set<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class K, class V>
ostream &operator<<(ostream &io, map<K, V> a) {
    io << "(";
    for (auto I: a)io << "{" << I.first << ":" << I.second << "}";
    io << ")"; 
    return io;
}

void debug_out() {
    cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H;
    debug_out(T...);
}

#ifdef local
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 1
#endif
#define all(x) x.begin(),x.end()


int main() {
    IOS
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int n = s.length();
        s = ' ' + s;
        int m;
        cin >> m;
        string l, r;
        cin >> l >> r;
        l = ' ' + l;
        r = ' ' + r;
        vector<vector<int>> nxt(n + 1, vector<int>(10, 0));
        for (int i = 0; i < 10; ++i)
            nxt[n][i] = n + 1;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j < 10; ++j) {
                if (s[i + 1] - '0' == j) {
                    nxt[i][j] = i + 1;
                } else {
                    nxt[i][j] = nxt[i + 1][j];
                }
            }
        }
        int ps = 0;
        bool f = 0;
        for (int i = 1; i <= m; ++i) {
            int mx = 0;
            if (f)
            	break;
            for (int j = l[i]; j <= r[i]; ++j) {
                mx = max(mx, nxt[ps][j - '0']);
                if (mx >= n + 1) {
                    f = 1;
                    break;
                }
            }
            ps = mx;
        }
        if (ps >= n + 1)
            f = 1;
        cout << (f ? "YES\n" : "NO\n");
    }
    return 0;
}

D. Rating System

题意：
给出长度为 $n$ 的序列 ${a}$ , 有一个数 $s$ , 第 $i$ 次操作会使 $s$ 加上 $a_i$ , 选择一个值 $k$ , 当 $s >= k$ 的时候， $s$ 不会再小于 $k$ , 求 $n$ 次操作后使得 $s$ 最大的整数 $k$ , 输出任意一种

思路：
原函数图大体上是折线型的，不难想到答案最大的时候， $k$ 一定是 $\sum a_i(下降时候取到的sum)$ 。s的变化分为三个阶段：到达 $k$ , 经过一些操作下降到 $k$ ，再也不会收到 $k$ 的限制。考虑枚举第三阶段的起点 $i$ , 那么答案就是k + sum[n] - sum[i - 1], 维护前缀最大sum更新 $k$ 即可。

#include <bits/stdc++.h>
#define local
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
using db = double;
using PII = pair<int, int>;
using PLI = pair<ll, int>;

template<class T>
ostream &operator<<(ostream &io, vector<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class T>
ostream &operator<<(ostream &io, set<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class K, class V>
ostream &operator<<(ostream &io, map<K, V> a) {
    io << "(";
    for (auto I: a)io << "{" << I.first << ":" << I.second << "}";
    io << ")"; 
    return io;
}

void debug_out() {
    cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H;
    debug_out(T...);
}

#ifdef local
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 1
#endif
#define all(x) x.begin(),x.end()


int main() {
    IOS
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<int> a(n + 1, 0);
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        vector<ll> sum(n + 1, 0);
        sum[1] = a[1];
        for (int i = 2; i <= n; ++i) {
            sum[i] = sum[i - 1] + a[i];
        }
        ll mx = 0, ans = 0, ans2 = 0;
        for (int i = 1; i <= n; ++i) {
            ll now = sum[n] - sum[i - 1] + mx;
            if (now > ans) {
                ans2 = mx;
                ans = now;
            }
            mx = max(mx, sum[i]);
        }
        if (mx > ans) {
            ans2 = mx;
        }
        cout << ans2 << "\n";
    }
    return 0;
}

E. Boxes and Balls

题意：
给定 $n$ 个盒子，其中一些盒子有球，保证不可能全满或者全空。每次可以移动球到相邻的空盒子，问恰好移动 $k$ 次的情况下球体排列状况有多少可能性。
思路：

最后的排列中，球体的相对位置不会改变
容易想到一个 $d p$ , $d p [i] [j] [k]$ 表示当前枚举到第 $i$ 个位置，放了 $j$ 个球，移动次数之和为 $k$ 的方案。时间复杂度是 $O(n^2k)$ 对于相对位置移动次数之和的统计，套路的转化为位置间隔被经过次数的统计之和。对于i后面的间隔，前面的所有存在的球都会对其有贡献，贡献为 $sum_i - sum'_i|$ , $sum_i为移动前的\sum a_i$ , $sum'_i$ 为移动后的。又由于题目要求每个间隔的贡献 $\sum |sum_i - sum'_i| \leq k$ 且 $sum'_i - sum'_{i - 1} \leq 1$ , 考虑前面所有位置对前缀 $i$ 所有的间隔的贡献，最优情况是个等差数列，所以对于每个 $i$ , $sum_i - sum'_i| <= sqrt(k)$ ，改变 $d p$ 定义， $d p [i] [j] [k]$ 表示当前枚举到第 $i$ 个盒子，新排列比原排列多 $j$ 个球，移动次数为 $k$ 的方案数，转移的时候枚举下一位放不放即可。

#include <bits/stdc++.h>
#define local
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
using ll = long long;
using db = double;
using PII = pair<int, int>;
using PLI = pair<ll, int>;

template<class T>
ostream &operator<<(ostream &io, vector<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class T>
ostream &operator<<(ostream &io, set<T> a) {
    io << "{"; 
    for (auto I: a)io << I << " ";
    io << "}";
    return io;
}

template<class K, class V>
ostream &operator<<(ostream &io, map<K, V> a) {
    io << "(";
    for (auto I: a)io << "{" << I.first << ":" << I.second << "}";
    io << ")"; 
    return io;
}

void debug_out() {
    cerr << endl;
}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << ' ' << H;
    debug_out(T...);
}

#ifdef local
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 1
#endif
#define all(x) x.begin(),x.end()

const int maxn = 1505;
const int mod = 1e9 + 7;
int f[2][140][maxn];

void Add(int &x, int y) {
    x += y;
    if (x >= mod)
        x -= mod;
}
int a[maxn];
int main() {
    IOS
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    int del = 57;
    int op = 0;
    f[op][0 + del][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = max(-del, -i); j <= min(i, del); ++j) {
            for (int v = 0; v <= k; ++v) {
                if (!f[op][j + del][v])
                    continue;
                for (auto q : {0, 1}) {
                    int nx1 = j + q - a[i + 1];
                    int nx2 = v + abs(nx1);
                    if (nx2 > k)
                        continue;
                    Add(f[op ^ 1][nx1 + del][nx2], f[op][j + del][v]);
                }
            }
        }
        for (int j = max(-del, -(i + 1)); j <= min(i + 1, del); ++j) {
            for (int v = 0; v <= k; ++v) {
                f[op][j + del][v] = 0;
            }
        }
        op ^= 1;
    }
    int ans = 0;
    for (int i = k; i >= 0; i -= 2) {
        Add(ans, f[op][0 + del][i]);
    }
    cout << ans;
    return 0;
}

F.Swimmers in the Pool

题意：
游泳道 $n$ 个人来回游，速度 $v_i$ , 泳道长 $l$ , 总共游 $t$ 时刻，问有多少个时刻至少有2个人碰到。
思路：
对于 $i$ 和 $j$ 两个人，相遇的时刻 $\frac{2kl}{|v_i - v_j|}$ 或者 $\frac{2kl}{v_i + v_j}$ , 对于 $v_i - v_j|$ 和 $v_i + v_j$ 是否存在，卷积即可。现在问题变成统计 $\frac{2kl}{b}$ , 化简即统计 $\frac{k}{b}$ , $\frac{t}{2l}]$ , 对于 $a$ 的统计是唯一的，考虑枚举所有满足条件的 $b$ , 对于 $g c d (k, b) = 1$ 的答案必定是唯一的, $\sum\limits_{k = 1} ^ {{\frac{tb}{2l}}}[gcd(k, b) = 1] = \sum_{d|b} mu[b] (tb) / (2l) / d$ , 那对于不互质的数要如何计算呢，不难发现假如不互质，设 $g c d (k, b)$ = d, 其必定在 $b$ 的某个约数 $\frac{b}{d}$ 的时候被完全互质统计到，倒序枚举 $b$ 并枚举约数更新即可。

事实上我们并不需要莫反，其本质只是一种容斥，同样定义 $f_i$ 表示 $g c d (k, b) = 1$ 时， $b = i$ 的合法方案数， $容斥总方案数 - g c d (k, b) = 2/3/4....$ ，所以 $f_i = (ti) / (2l) - \sum_{j | i} f_j$ , 每个 $g c d (k, b)! = 1$ 的答案会被 $b$ 的某个约数d在 $g c d (k^{'}, d)$ 的时候更新, 所以最后的答案就是 $\sum f_j [j | b]$ 文章来源地址https://www.toymoban.com/news/detail-531510.html

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
using ull=unsigned long long;
using ll=long long;
const int mod= 998244353,G=3;//??
const int maxn=2e5+5;
template<typename T>
void read(T &f){ 
    f=0;T fu=1;char c=getchar();
    while(c<'0'||c>'9'){ if(c=='-')fu=-1;c=getchar();}
    while(c>='0'&&c<='9'){ f=(f<<3)+(f<<1)+(c&15);c=getchar();}
    f*=fu;
}

template<typename T>
void print(T x){ 
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+48);
    else print(x/10),putchar(x%10+48);
}

template <typename T>
void print(T x, char t) {
    print(x); putchar(t);
}


inline int Add(int x,int y){ 
    x+=y;
    if(x>=mod)x-=mod;
    return x;
}

inline int Sub(int x,int y){ 
    x-=y;
    if(x<0)x+=mod;
    return x;
}

inline ll mul(ll x,ll y){ return 1ll*x*y%mod;}

ll mypow(int a,int b){ 
    int ans=1;
    while(b){ 
        if(b&1)ans=mul(ans,a);
        a=mul(a,a);
        b>>=1;
    }
    return ans;
}

namespace Poly{ 
    typedef vector<ll>poly;
    poly roots,rev;
    void getRevRoot(int base){ 
        int lim=1<<base;
        if((int)roots.size()==lim)return;
        roots.resize(lim);rev.resize(lim);
        for(int i=1;i<lim;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(base-1));
        for(int mid=1;mid<lim;mid<<=1){ 
            int wn=mypow(G,(mod-1)/(mid<<1));
            roots[mid]=1;
            for(int i=1;i<mid;++i)roots[mid+i]=mul(roots[mid+i-1],wn);
        }
    }
    
    void ntt(poly&a,int base){ 
        int lim=1<<base;
        for(int i=0;i<lim;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
        for(int mid=1;mid<lim;mid<<=1){ 
            for(int i=0;i<lim;i+=(mid<<1)){ 
                for(int j=0;j<mid;++j){ 
                    int x=a[i+j],y=mul(a[i+j+mid],roots[j+mid]);
                    a[i+j]=Add(x,y);
                    a[i+j+mid]=Sub(x,y);
                }
            }
        }
    }

    poly operator*(poly a,poly b){ 
        int lim=(int)a.size()+(int)b.size()-1,base=0;
        while((1<<base)<lim)++base;
        a.resize(1<<base);b.resize(1<<base);
        getRevRoot(base);
        ntt(a,base);ntt(b,base);
        for(int i=0;i<(1<<base);++i)a[i]=mul(a[i],b[i]);
        ntt(a,base);
        reverse(a.begin()+1,a.end());
        a.resize(lim);
        int inv=mypow(1<<base,mod-2);
        for(int i=0;i<lim;++i)a[i]=mul(a[i],inv);
        return a;
    }
    poly polyInv(poly f,int base){ 
        int lim=1<<base;
        f.resize(lim);
        if(lim==1){ 
            poly ans(1,mypow(f[0],mod-2));
            return ans;
        }
        poly g(1<<base,0),g0=polyInv(f,base-1),tmp=g0*g0*f;
        for(int i=0;i<(1<<(base-1));++i)g[i]=Add(g0[i],g0[i]);
        for(int i=0;i<(1<<base);++i)g[i]=Sub(g[i],tmp[i]);
        return g;
    }
    poly polyInv(poly f){ 
        int lim=(int)f.size(),base=0;
        while((1<<base)<lim)++base;
        f=polyInv(f,base);f.resize(lim);
        return f;
    }
    
    poly operator+(const poly&a,const poly&b){
        poly c=a;
        c.resize(max(a.size(),b.size()));
        int lim=(int)b.size();
        for(int i=0;i<lim;++i)c[i]=Add(c[i],b[i]);
        return c;
    }

    poly operator-(const poly&a,const poly&b){ 
        poly c=a;
        c.resize(max(a.size(),b.size()));
        int lim=(int)b.size();
        for(int i=0;i<lim;++i)c[i]=Sub(c[i],b[i]);
        return c;
    }

    poly operator*(const int&b,const poly&a){ 
        poly c=a;
        int lim=(int)a.size();
        for(int i=0;i<lim;++i)c[i]=mul(b,c[i]);
        return c;
    }
}

using namespace Poly;
const int del = 2e5;
const int M = 4e5 + 5;
int v[maxn * 2 + 5], mu[maxn * 2 + 5];

bool is[maxn << 1];

vector<int> pr;

ll dp[maxn << 1];

void init() {
    mu[1] = 1;
    for (int i = 2; i < 2 * maxn; ++i) {
        if (!v[i])
            pr.emplace_back(i), mu[i] = -1;
        for (int j = 0; j < pr.size() && i * pr[j] < 2 * maxn; ++j) {
            v[i * pr[j]] = 1;
            if (i % pr[j] == 0) {
                mu[i * pr[j]] = 0;
                break;
            }
            mu[i * pr[j]] = -mu[i];
        }
    }
}

const int P = 1e9 + 7;
vector<int> fac[maxn << 1];

ll mxk[maxn << 1];

int main() {
    IOS
    init();
    int l, t, n;
    cin >> l >> t >> n;
    int mx = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
        mx = max(mx, v[i]);
    }
    poly a(mx + 1, 0), b(del + 1, 0);
    for (int i = 1; i <= n; ++i) {
        a[v[i]]++, b[del - v[i]]++;
    }
    poly A = a * a, B = a * b;
    for (int i = 1; i <= n; ++i) {
        A[2 * v[i]]--;
    }
    for (int i = 1; i <= 2 * mx; ++i) {
        if (A[i]) {
            is[i] = 1;
        }
    }
    for (int i = 1; i <= mx; ++i) {
        if (B[i + del])
            is[i] = 1;
    }
    for (int i = 2 * mx; i >= 1; --i)
        for (int j = i; j <= 2 * mx; j += i)
            is[i] |= is[j];
            // fac[j].emplace_back(i);
    ll ans = 0;
    // for (int i = 2 * mx; i; --i) {
    //     if (is[i]) {
    //         mxk[i] = ((ll) t * i) / (2 * l);
    //     }
    //     for (auto u : fac[i]) {
    //         ans = (ans + mu[u] * (mxk[i] / u) % P) % P;
    //         if (ans >= P)
    //             ans -= P;
    //         if (ans < 0)
    //             ans += P;
    //         mxk[i / u] = max(mxk[i / u], mxk[i] / u);
    //     }
    // }
    for (int i = 1; i <= 2 * mx; ++i) {
        dp[i] = (dp[i] + ((ll) t * i) / (2 * l)) % P;
        if (is[i])
            ans = (ans + dp[i]) % P;
        for (int j = 2 * i; j <= 2 * mx; j += i) {
            dp[j] = (dp[j] - dp[i] + P) % P;
        }
    }
    cout << ans;
    return 0;
}