当前位置：首页 > news >正文

镇江网络违法网站全网营销外包

news 2025/7/16 1:21:17

镇江网络违法网站,全网营销外包,北京死亡病例最新消息,网站和app设计区别Edu 151 A. Forbidden Integer 题意： 你有[1, k]内除了 x x x的整数，每个数可以拿多次，问 ∑ n \sum n ∑n是否可行并构造思路： 有1必能构造，否则假如没有1，假如有2, 3必定能构造出大于等于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$ 次的情况下球体排列状况有多少可能性。
思路：

最后的排列中，球体的相对位置不会改变
容易想到一个 $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() {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$ 两个人，相遇的时刻 $\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]$

#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;
}