安丘建设网站,遵义建设厅官方网站 元丰,定制小程序网站开发公司,wordpress直接上传视频网站Edu 151
A. Forbidden Integer
题意#xff1a; 你有[1, k]内除了 x x x的整数#xff0c;每个数可以拿多次#xff0c;问 ∑ n \sum n ∑n是否可行并构造 思路#xff1a; 有1必能构造#xff0c;否则假如没有1#xff0c;假如有2, 3必定能构造出大于等于2的所有数 你有[1, k]内除了 x x x的整数每个数可以拿多次问 ∑ n \sum n ∑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 pairint, int;
using PLI pairll, int;templateclass T
ostream operator(ostream io, vectorT a) {io {; for (auto I: a)io I ;io };return io;
}templateclass T
ostream operator(ostream io, setT a) {io {; for (auto I: a)io I ;io };return io;
}templateclass K, class V
ostream operator(ostream io, mapK, V a) {io (;for (auto I: a)io { I.first : I.second };io ); return io;
}void debug_out() {cerr endl;
}templatetypename 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 pairint, int;
using PLI pairll, int;templateclass T
ostream operator(ostream io, vectorT a) {io {; for (auto I: a)io I ;io };return io;
}templateclass T
ostream operator(ostream io, setT a) {io {; for (auto I: a)io I ;io };return io;
}templateclass K, class V
ostream operator(ostream io, mapK, V a) {io (;for (auto I: a)io { I.first : I.second };io ); return io;
}void debug_out() {cerr endl;
}templatetypename 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 s s问是否存在长度为 m m m, 每个密码的第 i i i位数字在 [ l i , r i ] [l_i, r_i] [li,ri]之间且不为 s s s的子序列的字符串。 思路 每个密码在 s s s中都是独立的显然我们要让它不为子序列贪心的考虑在 i i 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 pairint, int;
using PLI pairll, int;templateclass T
ostream operator(ostream io, vectorT a) {io {; for (auto I: a)io I ;io };return io;
}templateclass T
ostream operator(ostream io, setT a) {io {; for (auto I: a)io I ;io };return io;
}templateclass K, class V
ostream operator(ostream io, mapK, V a) {io (;for (auto I: a)io { I.first : I.second };io ); return io;
}void debug_out() {cerr endl;
}templatetypename 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;vectorvectorint nxt(n 1, vectorint(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 n n的序列 a {a} a, 有一个数 s s s, 第 i i i次操作会使 s s s加上 a i a_i ai, 选择一个值 k k k, 当 s k s k sk的时候 s s s不会再小于 k k k, 求 n n n次操作后使得 s s s最大的整数 k k k, 输出任意一种
思路 原函数图大体上是折线型的不难想到答案最大的时候 k k k一定是 ∑ a i ( 下降时候取到的 s u m ) \sum a_i(下降时候取到的sum) ∑ai(下降时候取到的sum)。s的变化分为三个阶段到达 k k k, 经过一些操作下降到 k k k再也不会收到 k k k的限制。考虑枚举第三阶段的起点 i i i, 那么答案就是k sum[n] - sum[i - 1], 维护前缀最大sum更新 k k 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 pairint, int;
using PLI pairll, int;templateclass T
ostream operator(ostream io, vectorT a) {io {; for (auto I: a)io I ;io };return io;
}templateclass T
ostream operator(ostream io, setT a) {io {; for (auto I: a)io I ;io };return io;
}templateclass K, class V
ostream operator(ostream io, mapK, V a) {io (;for (auto I: a)io { I.first : I.second };io ); return io;
}void debug_out() {cerr endl;
}templatetypename 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;vectorint a(n 1, 0);for (int i 1; i n; i)cin a[i];vectorll 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 n n个盒子其中一些盒子有球保证不可能全满或者全空。每次可以移动球到相邻的空盒子问恰好移动 k k k次的情况下球体排列状况有多少可能性。 思路
最后的排列中球体的相对位置不会改变容易想到一个 d p dp dp, d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示当前枚举到第 i i i个位置放了 j j j个球移动次数之和为 k k k的方案。时间复杂度是 O ( n 2 k ) O(n^2k) O(n2k)对于相对位置移动次数之和的统计套路的转化为位置间隔被经过次数的统计之和。对于i后面的间隔前面的所有存在的球都会对其有贡献贡献为 ∣ s u m i − s u m i ′ ∣ |sum_i - sum_i| ∣sumi−sumi′∣, s u m i 为移动前的 ∑ a i sum_i为移动前的\sum a_i sumi为移动前的∑ai, s u m i ′ sum_i sumi′为移动后的。又由于题目要求每个间隔的贡献 ∑ ∣ s u m i − s u m i ′ ∣ ≤ k \sum |sum_i - sum_i| \leq k ∑∣sumi−sumi′∣≤k且 s u m i ′ − s u m i − 1 ′ ≤ 1 sum_i - sum_{i - 1} \leq 1 sumi′−sumi−1′≤1, 考虑前面所有位置对前缀 i i i所有的间隔的贡献最优情况是个等差数列所以对于每个 i i i, ∣ s u m i − s u m i ′ ∣ s q r t ( k ) |sum_i - sum_i| sqrt(k) ∣sumi−sumi′∣sqrt(k)改变 d p dp dp定义 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示当前枚举到第 i i i个盒子新排列比原排列多 j j j个球移动次数为 k k 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 pairint, int;
using PLI pairll, int;templateclass T
ostream operator(ostream io, vectorT a) {io {; for (auto I: a)io I ;io };return io;
}templateclass T
ostream operator(ostream io, setT a) {io {; for (auto I: a)io I ;io };return io;
}templateclass K, class V
ostream operator(ostream io, mapK, V a) {io (;for (auto I: a)io { I.first : I.second };io ); return io;
}void debug_out() {cerr endl;
}templatetypename 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 n n个人来回游速度 v i v_i vi, 泳道长 l l l, 总共游 t t t时刻问有多少个时刻至少有2个人碰到。 思路 对于 i i i和 j j j两个人相遇的时刻 t 2 k l ∣ v i − v j ∣ t \frac{2kl}{|v_i - v_j|} t∣vi−vj∣2kl或者 t 2 k l v i v j t \frac{2kl}{v_i v_j} tvivj2kl, 对于 ∣ v i − v j ∣ |v_i - v_j| ∣vi−vj∣和 v i v j v_i v_j vivj是否存在卷积即可。现在问题变成统计 a 2 k l b a \frac{2kl}{b} ab2kl, 化简即统计 a k b a \frac{k}{b} abk, a 属于 [ 0 , t 2 l ] a属于[0, \frac{t}{2l}] a属于[0,2lt], 对于 a a a的统计是唯一的考虑枚举所有满足条件的 b b b, 对于 g c d ( k , b ) 1 gcd(k, b) 1 gcd(k,b)1的答案必定是唯一的, ∑ k 1 t b 2 l [ g c d ( k , b ) 1 ] ∑ d ∣ b m u [ b ] ( t b ) / ( 2 l ) / d \sum\limits_{k 1} ^ {{\frac{tb}{2l}}}[gcd(k, b) 1] \sum_{d|b} mu[b] (tb) / (2l) / d k1∑2ltb[gcd(k,b)1]∑d∣bmu[b](tb)/(2l)/d, 那对于不互质的数要如何计算呢不难发现假如不互质设 g c d ( k , b ) gcd(k, b) gcd(k,b) d, 其必定在 b b b的某个约数 b d \frac{b}{d} db的时候被完全互质统计到倒序枚举 b b b并枚举约数更新即可。
事实上我们并不需要莫反其本质只是一种容斥同样定义 f i f_i fi表示 g c d ( k , b ) 1 gcd(k, b) 1 gcd(k,b)1时 b i b i bi的合法方案数 容斥总方案数 − g c d ( k , b ) 2 / 3 / 4.... 容斥总方案数 - gcd(k, b) 2/3/4.... 容斥总方案数−gcd(k,b)2/3/4....所以 f i ( t i ) / ( 2 l ) − ∑ j ∣ i f j f_i (ti) / (2l) - \sum_{j | i} f_j fi(ti)/(2l)−∑j∣ifj, 每个 g c d ( k , b ) ! 1 gcd(k, b) ! 1 gcd(k,b)!1的答案会被 b b b的某个约数d在 g c d ( k ′ , d ) gcd(k, d) gcd(k′,d)的时候更新, 所以最后的答案就是 ∑ f j [ j ∣ b ] \sum f_j [j | b] ∑fj[j∣b]
#includebits/stdc.h
#define IOS ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
using ullunsigned long long;
using lllong long;
const int mod 998244353,G3;//??
const int maxn2e55;
templatetypename T
void read(T f){ f0;T fu1;char cgetchar();while(c0||c9){ if(c-)fu-1;cgetchar();}while(c0c9){ f(f3)(f1)(c15);cgetchar();}f*fu;
}templatetypename T
void print(T x){ if(x0)putchar(-),x-x;if(x10)putchar(x48);else print(x/10),putchar(x%1048);
}template typename T
void print(T x, char t) {print(x); putchar(t);
}inline int Add(int x,int y){ xy;if(xmod)x-mod;return x;
}inline int Sub(int x,int y){ x-y;if(x0)xmod;return x;
}inline ll mul(ll x,ll y){ return 1ll*x*y%mod;}ll mypow(int a,int b){ int ans1;while(b){ if(b1)ansmul(ans,a);amul(a,a);b1;}return ans;
}namespace Poly{ typedef vectorllpoly;poly roots,rev;void getRevRoot(int base){ int lim1base;if((int)roots.size()lim)return;roots.resize(lim);rev.resize(lim);for(int i1;ilim;i)rev[i](rev[i1]1)|((i1)(base-1));for(int mid1;midlim;mid1){ int wnmypow(G,(mod-1)/(mid1));roots[mid]1;for(int i1;imid;i)roots[midi]mul(roots[midi-1],wn);}}void ntt(polya,int base){ int lim1base;for(int i0;ilim;i)if(irev[i])swap(a[i],a[rev[i]]);for(int mid1;midlim;mid1){ for(int i0;ilim;i(mid1)){ for(int j0;jmid;j){ int xa[ij],ymul(a[ijmid],roots[jmid]);a[ij]Add(x,y);a[ijmid]Sub(x,y);}}}}poly operator*(poly a,poly b){ int lim(int)a.size()(int)b.size()-1,base0;while((1base)lim)base;a.resize(1base);b.resize(1base);getRevRoot(base);ntt(a,base);ntt(b,base);for(int i0;i(1base);i)a[i]mul(a[i],b[i]);ntt(a,base);reverse(a.begin()1,a.end());a.resize(lim);int invmypow(1base,mod-2);for(int i0;ilim;i)a[i]mul(a[i],inv);return a;}poly polyInv(poly f,int base){ int lim1base;f.resize(lim);if(lim1){ poly ans(1,mypow(f[0],mod-2));return ans;}poly g(1base,0),g0polyInv(f,base-1),tmpg0*g0*f;for(int i0;i(1(base-1));i)g[i]Add(g0[i],g0[i]);for(int i0;i(1base);i)g[i]Sub(g[i],tmp[i]);return g;}poly polyInv(poly f){ int lim(int)f.size(),base0;while((1base)lim)base;fpolyInv(f,base);f.resize(lim);return f;}poly operator(const polya,const polyb){poly ca;c.resize(max(a.size(),b.size()));int lim(int)b.size();for(int i0;ilim;i)c[i]Add(c[i],b[i]);return c;}poly operator-(const polya,const polyb){ poly ca;c.resize(max(a.size(),b.size()));int lim(int)b.size();for(int i0;ilim;i)c[i]Sub(c[i],b[i]);return c;}poly operator*(const intb,const polya){ poly ca;int lim(int)a.size();for(int i0;ilim;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];vectorint 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;
vectorint 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;
}
