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() {IOSint 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() {IOSint 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() {IOSint 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() {IOSint 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$次的情况下球体排列状况有多少可能性。
思路：

• 最后的排列中，球体的相对位置不会改变
• 容易想到一个$dp$, $dp[i][j][k]$表示当前枚举到第$i$个位置，放了$j$个球，移动次数之和为$k$的方案。时间复杂度是$O(n^{2}k)$对于相对位置移动次数之和的统计，套路的转化为位置间隔被经过次数的统计之和。对于i后面的间隔，前面的所有存在的球都会对其有贡献，贡献为$|su{m}_i-su{m}_i^{\prime }|$, $su{m}_i为移动前的\sum a_i$, $su{m}_i^{\prime }$为移动后的。又由于题目要求每个间隔的贡献$\sum |su{m}_i-su{m}_i^{\prime }|\le k$且$su{m}_i^{\prime }-su{m}_{i-1}^{\prime }\le 1$, 考虑前面所有位置对前缀$i$所有的间隔的贡献，最优情况是个等差数列，所以对于每个$i$, $|su{m}_i-su{m}_i^{\prime }|<=sqrt(k)$，改变$dp$定义，$dp[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() {IOSint 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$两个人，相遇的时刻$t=\frac{2kl}{|v_i-v_j|}$或者$t=\frac{2kl}{v_i+v_j}$, 对于$|v_i-v_j|$和$v_i+v_j$是否存在，卷积即可。现在问题变成统计$a=\frac{2kl}{b}$, 化简即统计$a=\frac{k}{b}$, $a属于[0,\frac{t}{2l}]$, 对于$a$的统计是唯一的，考虑枚举所有满足条件的$b$, 对于$gcd(k,b)=1$的答案必定是唯一的, $\sum _{k=1}^{\frac{tb}{2l}}[gcd(k,b)=1]={\sum }_{d|b}mu[b](tb)/(2l)/d$, 那对于不互质的数要如何计算呢，不难发现假如不互质，设$gcd(k,b)$ = d, 其必定在$b$的某个约数$\frac{b}{d}$的时候被完全互质统计到，倒序枚举$b$并枚举约数更新即可。

事实上我们并不需要莫反，其本质只是一种容斥，同样定义$f_i$表示$gcd(k,b)=1$时，$b=i$的合法方案数，$容斥总方案数-gcd(k,b)=2/3/4....$，所以$f_i=(ti)/(2l)-{\sum }_{j|i}{f}_j$, 每个$gcd(k,b)!=1$的答案会被$b$的某个约数d在$gcd(k^{\prime },d)$的时候更新, 所以最后的答案就是$\sum f_j[j|b]$

#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() {IOSinit();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;
}