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

做网站的常识网站策划是做什么的

做网站的常识,网站策划是做什么的,专业做网站建设公司怎么样,公司建设网站的手续Problem A. Diverse Game Statement 给定 n m n\times m nm 的矩形 a a a, a a a 中的每一个数均在 1 ∼ n m 1\sim nm 1∼nm 之间且互不相同。求出 n m n\times m nm 的矩形 b b b, b b b 中的每一个数均在 1 ∼ n m 1\sim nm 1∼nm 之间且互…

Problem A. Diverse Game

Statement

给定 n × m n\times m n×m 的矩形 a a a a a a 中的每一个数均在 1 ∼ n m 1\sim nm 1nm 之间且互不相同。求出 n × m n\times m n×m 的矩形 b b b b b b 中的每一个数均在 1 ∼ n m 1\sim nm 1nm 之间且互不相同,同时 a i , j ≠ b i , j a_{i,j}\ne b_{i,j} ai,j=bi,j

Solution

注意到 a a a 如果拉长为一个序列,则是一个长为 n m nm nm 的排列。故,如果直接翻转 a a a,则长度为偶数的时候是可行的;长度为奇数的时候,中间的位置没变,只需将第一个位置与中间的位置交换即可。

Code

void solve() {int n, m, x;cin >> n >> m;std::vector<int> opt;for (int i = 1; i <= n * m; i ++) cin >> x, opt.push_back(x);if (n * m == 1) {cout << -1 << endl;return;}reverse(opt.begin(), opt.end());if (opt.size() & 1) swap(opt[0], opt[opt.size() / 2]);for (int i = 1; i <= n * m; i ++) {cout << opt[i - 1] << " ";if (i % m == 0) cout << endl;}
}

Problem B. Fun Game

Statement

给定一个长为 n n n 的二进制序列,接下来可以进行无限次操作:

  • 选择 l , r l,r l,r,将 s i s_i si 变为 s i − l + 1 ⊕ s i s_{i-l+1}\oplus s_i sil+1si

确定是否能从 s s s 序列变为 t t t 序列。

Solution

考察 s s s 中第一个出现 1 1 1 的位置,那么后面需要翻转的位置一定可以通过这个 1 1 1 来翻转状态。形式化的,若需要变换的位置为 i i i,第一次出现的位置为 j j j,则选择区间 l = i − j + 1 , r = i l=i-j+1,r=i l=ij+1,r=i 即可在不改变其他位置的前提下(因为 j j j 前面全为 0 0 0),翻转 i i i 位置。最后 j j j 位置自己异或自己即可。

但是如果前面存在 i i i,使得 s i = 0 , t i = 1 s_i=0,t_i=1 si=0,ti=1,则必然不存在方案,输出 NO;反之输出 YES

Code

void solve() {int n;string s, t;cin >> n >> s >> t;bool ok = 0;for (int i = 0; i < n; i ++) {if (s[i] == '0' && t[i] == '1') {cout << "NO" << endl;return;}if (s[i] == '1') {cout << "YES" << endl;return;}}cout << "YES" << endl;
}

Problem C. Hungry Games

Statement

给定长为 n n n 的序列 a a a 以及变量 g g g(初始为 0 0 0),选择 l , r l,r l,r,依次遍历 l ∼ r l\sim r lr 中的每一个数, g = g + a i g=g+a_i g=g+ai,若 g > x g>x g>x,则令 g = 0 g=0 g=0。问存在多少个 l , r l,r l,r 使得最终 g g g 的值不为 0 0 0

Solution

考虑枚举每一个 l l l,那么第一个使得 g g g 0 0 0 的位置可以轻松通过二分得出(令其为 k k k),则 l ∼ k − 1 l\sim k-1 lk1 的位置均可以作为右端点。那么 k + 1 ∼ n k+1\sim n k+1n 有哪些位置可以作为右端点呢?注意到 k k k 位置 g g g 0 0 0,即和 l ′ = k l'=k l=k 时初始状态时相同的,也就是 l ′ = k l'=k l=k 的所有可行的右端点, l l l 位置均可以。

故,列出转移方程: f l = f k + ( k − l ) f_l=f_k+(k-l) fl=fk+(kl)。时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn) log ⁡ \log log 来源于找 k k k

Code

void solve() {cin >> n >> x;for (int i = 1; i <= n; i ++)cin >> a[i], a[i] += a[i - 1];for (int i = n; i >= 1; i -- ) {int l = i, r = n, res = -1;while (l <= r) {int mid = l + r >> 1;if (a[mid] - a[i - 1] > x) r = mid - 1, res = mid;else l = mid + 1;}if (res == -1) dp[i] = n - i + 1;else dp[i] = dp[res + 1] + res - i;}int res = 0;for (int i = 1; i <= n; i ++) res += dp[i];cout << res << endl;for (int i = 1; i <= n; i ++) dp[i] = 0;
}

Problem D. Funny Game

Statement

给定 n n n 个点以及序列 a a a,接下来有若干次操作:

  • 选择 u , v u,v u,v,其中 ∣ a u − a v ∣ |a_u-a_v| auav x x x 的倍数,连接 u , v u,v u,v

通过进行 n − 1 n-1 n1 次操作,是否能将 n n n 个点连接成为一棵树,是则输出方案。

Solution

观察 Observation

观察样例发现全部均是 YES,回想抽屉原理的一个应用即为证明存在性。

深入探究 Investigate Deeply

∣ a u − a v ∣ |a_u-a_v| auav x x x 的倍数等价于 a u ≡ a v ( m o d x ) a_u\equiv a_v\pmod x auav(modx),考虑倒序操作,则进行第 x x x 次操作前有 x + 1 x+1 x+1 个连通块,即可选的数有 x + 1 x+1 x+1 个,而对 x x x 取模后可行的数只有 x x x 个,通过抽屉原理,不管前面如何操作,此时必然有至少 1 1 1 a u ≡ a v ( m o d x ) a_u\equiv a_v\pmod x auav(modx),通过并查集找出即可。

综上所述,答案永远都是存在的!

Code

int find(int x) {if (par[x] != x) par[x] = find(par[x]);return par[x];
}
void solve() {cin >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i];for (int i = 1; i <= n; i ++) par[i] = i;for (int i = n - 1; i >= 1; i --) {for (int j = 1; j <= n; j ++) pos[a[j] % i].push_back(j);for (int j = 0; j < n; j ++) {sort(pos[j].begin(), pos[j].end(), [&](int a, int b) { return find(a) < find(b); });if (pos[j].size() <= 1) continue;if (find(pos[j][0]) != find(pos[j].back())) {par[find(pos[j][0])] = find(pos[j].back());res.emplace_back(pos[j][0], pos[j].back());break;}}for (int j = 0; j < n; j ++) pos[j].clear();}reverse(res.begin(), res.end());cout << "YES" << endl;for (auto v : res) cout << v.fi << " " << v.se << endl;res.clear();
}

Problem E. Wooden Game

Statement

给定 k k k 棵树,第 i i i 棵树有 n i n_i ni 个节点,每次可以将任意一棵树的一个子树删除,最终的权值即为删除的子树的大小按位或和

Solution

观察 Observation

简化:如果只有 1 1 1 棵树,则答案必为这棵树的大小。

证明:对于 x 1 + x 2 + ⋯ + x k = n x_1+x_2+\dots +x_k = n x1+x2++xk=n,则 x 1 ∣ x 2 ∣ … ∣ x k ≤ n x_1|x_2|\dots |x_k\le n x1x2xkn。所以这说明对于一棵树,至多只存在一个子树给答案是有贡献的,而一棵树便是特殊情况,必然是这棵树的大小

深入探究 Investigate Deeply

从观察中得出,一棵树只有一个子树给答案是有贡献的,考察这棵子树的大小取值范围,由于可以不断地删除叶子节点取剩余部分,所以大小地取值范围为 [ 1 , n i ] [1,n_i] [1,ni]

问题转化为给定 k k k 个变量 x x x,第 i i i 个变量的取值范围为 [ 1 , n i ] [1,n_i] [1,ni],求 max ⁡ ( x 1 ∣ x 2 ∣ … ∣ x k ) \max(x_1|x_2|\dots |x_k) max(x1x2xk)。故变为了二进制的问题,使用经典方式拆位,对于第 i i i 位:

  • 如果存在大于等于 2 2 2 n j n_j nj 使得第 i i i 位为 1 1 1,则一个 n i n_i ni 将这一位变为 1 1 1,其余的只需这一位取 0 0 0,后面所有位取 1 1 1 即可。

  • 如果存在恰好 1 1 1 n j n_j nj 使得第 i i i 位为 1 1 1,则只需将第 i i i 位变为 1 1 1 即可。

Code

void solve() {cin >> n;for (int i = 1; i <= n; i ++) {cin >> a[i];int x;for (int j = 2; j <= a[i]; j ++) cin >> x;}for (int i = 1; i <= n; i ++)for (int j = 0; j < 30; j ++) cnt[j] += (a[i] >> j & 1);int res = 0;for (int i = 30; i >= 0; i --) {if (cnt[i] >= 2) res |= ((1ll << i) - 1) | (1ll << i);else if (cnt[i] == 1) {res |= (1ll << i);}}cout << res << endl;for (int i = 0; i <= 30; i ++) cnt[i] = 0;
}

Problem F. Stardew Valley

Statement

给定 n n n 个点 m m m 条边的无向图,边权为 1 1 1 的边必须选,边权为 0 0 0 的边可选可不选。求该图上的一条欧拉回路(经过选过的边恰好 1 1 1 次)

Solution

观察 Observation

由于欧拉回路的判定方式为所有点的度数均为偶数,故问题转化为在选择边权为 1 1 1 的边,每个点的度数的奇偶性组成 01 01 01 序列。现在可以加入若干条边,使得两个端点的奇偶性可以异或 1 1 1。给出 1 1 1 种选择方案,将选出的边加入后跑欧拉回路即可解决问题。

深入探究 Investigate Deeply

上述问题与 ABC155F - Perils in Parallel 化为 1 1 1 道题,具体过程此处不再赘述。

聪明的人能看到事物之间的联系,更聪明的人能看到联系之间的联系。

Code

void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u) {st[u] = d[u], vis[u] = true;for (auto v : g[u]) {if (vis[v]) continue;dfs(v);st[u] ^= st[v];if (st[v]) add(u, v), add(v, u);}
}
void Euler_Path(int u) {for (int &i = h[u]; ~i;) {if (has[i]) { i = ne[i]; continue; }int j = e[i];has[i ^ 1] = true, i = ne[i], Euler_Path(j);}res.push(u);
}void solve() {cin >> n >> m;for (int i = 1; i <= n; i ++) h[i] = -1, vis[i] = 0, st[i] = 0, d[i] = 0, g[i].clear();while (m -- ) {int u, v, c;cin >> u >> v >> c;if (!c) g[u].emplace_back(v), g[v].emplace_back(u);else add(u, v), add(v, u), d[u] ^= 1, d[v] ^= 1;}for (int i = 1; i <= n; i ++)if (!vis[i]) {dfs(i);if (st[i]) {cout << "NO" << endl;return;}}Euler_Path(1);cout << "YES" << endl;cout << res.size() - 1 << endl;while (res.size()) cout << res.top() << " ", res.pop();cout << endl;
}

Problem G. Minecraft

Statement

给定目标 01 01 01 s s s n n n 01 01 01 a i a_i ai,求出 01 01 01 x x x 使得 ∑ a i ⊕ x = s \sum a_i\oplus x=s aix=s 01 01 01 串的长度均为 k k k

1 ≤ n , k ≤ 2 × 1 0 6 1\le n,k\le 2\times 10^6 1n,k2×106 1 ≤ n ⋅ k ≤ 2 × 1 0 6 1\le n\cdot k\le 2\times 10^6 1nk2×106

Solution

观察 Observation

二进制问题——拆位,考虑对于每一位与 s s s 匹配的方案,不过注意到存在加法,所以需要同时处理进位问题。对于第 i i i 位,这一位上填的 1 1 1 的个数不会超过 2 n 2n 2n,所以可以直接存储( 1 ≤ n ⋅ k ≤ 2 × 1 0 6 1\le n\cdot k\le 2\times 10^6 1nk2×106

深入探究 Investigate Deeply

f i , j f_{i,j} fi,j 表示前 i i i 位,第 i i i 位填了 j j j 1 1 1 是否可行。考虑转移:
{ f i , ⌊ j 2 ⌋ + c n t i ← f i + 1 , j ⌊ j 2 ⌋ + c n t i m o d 2 = s i f i , ⌊ j 2 ⌋ + n − c n t i ← f i + 1 , j ⌊ j 2 ⌋ + n − c n t i m o d 2 = s i \begin{cases} &f_{i,\lfloor\frac{j}{2}\rfloor+\mathrm{cnt}_i}\leftarrow f_{i+1,j} \qquad \lfloor\frac{j}{2}\rfloor+\mathrm{cnt}_i\bmod 2 = s_i\\ &f_{i,\lfloor\frac{j}{2}\rfloor+n-\mathrm{cnt}_i}\leftarrow f_{i+1,j}\qquad \lfloor\frac{j}{2}\rfloor+n-\mathrm{cnt}_i\bmod 2 = s_i \end{cases} {fi,2j+cntifi+1,j2j+cntimod2=sifi,2j+ncntifi+1,j2j+ncntimod2=si
第一种情况即为当前位 x x x 0 0 0,第二种情况为当前位 x x x 1 1 1。从 i + 1 i+1 i+1 转移过来的原因主要是要从低位向高位做(因为进位是从低位向高位的)。

Code

void solve() {int n, k;cin >> n >> k;char x;std::vector<int> s(k), cnt(k, 0);std::vector<vector<int>> a(n + 1, vector<int>(k)), dp(k, vector<int>(2 * n + 1, 0));std::vector<vector<array<int, 3>>> pre(k, vector<array<int, 3>>(2 * n + 1));for (int i = 0; i < k; i ++) cin >> x, s[i] = x & 1;for (int i = 1; i <= n; i ++) for (int j = 0; j < k; j ++) cin >> x, a[i][j] = x & 1, cnt[j] += a[i][j];if ((cnt[k - 1] & 1) == s[k - 1]) dp[k - 1][cnt[k - 1]] = 1;if ((n - cnt[k - 1] & 1) == s[k - 1]) dp[k - 1][n - cnt[k - 1]] = 1;for (int i = k - 2; i >= 0; i --)for (int j = 0; j <= 2 * n; j ++) {if (!dp[i + 1][j]) continue;int put1 = ((j >> 1) + cnt[i] & 1), put2 = ((j >> 1) + n - cnt[i] & 1);if (put1 == s[i]) dp[i][(j >> 1) + cnt[i]] |= dp[i + 1][j], pre[i][(j >> 1) + cnt[i]] = {i + 1, j, 0};if (put2 == s[i]) dp[i][(j >> 1) + n - cnt[i]] |= dp[i + 1][j], pre[i][(j >> 1) + n - cnt[i]] = {i + 1, j, 1};}if (!dp[0][s[0]]) cout << -1 << endl;else {PII lst = {0, s[0]};std::vector<int> res;while (lst.fi != k - 1) {res.push_back(pre[lst.fi][lst.se][2]);lst = {pre[lst.fi][lst.se][0], pre[lst.fi][lst.se][1]};}if (lst.se == cnt[k - 1]) res.push_back(0);else res.push_back(1);for (auto v : res) cout << v;cout << endl;}
}

视频讲解 Video Tutorial

Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)(A ~ G 题讲解)

http://www.fp688.cn/news/158287.html

相关文章:

  • 服务器做jsp网站教程视频教程国外网站排行
  • 成都网站建设成都app开发互联网营销师报名
  • 做公司网站 国外系统广州seo顾问服务
  • wordpress域名解析橘子seo
  • 南岗哈尔滨网站建设短视频入口seo
  • 网站建设域名怎么收费的不受限制的搜索引擎
  • 做网站主色调选择智能营销系统
  • 唐山房产网站建设福州今日头条新闻
  • 做网站怎么学网站接广告平台
  • 上海品牌网站制作seo sem什么意思
  • 新乡做网站的seo网站优化流程
  • 广州微网站建设哪家好有没有好用的网站推荐
  • 石家庄门户网站制作seo快排
  • 珠海网站制作产品如何推广
  • 北京移动端网站优化推广广告
  • 网站建设网站制作哪个好查权重的软件
  • 如何做做网站新闻头条今日新闻60条
  • wordpress ks主题论坛如何做seo
  • 在常州 做兼职上什么网站海外短视频软件
  • 武汉装饰公司前十名是哪几家seo零基础入门教程
  • 武汉网站seo诊断抖音关键词推广
  • 佛山市南海区水利投资建设有限公司网站中央新闻频道直播今天
  • 东方购物商城seo排名优化培训网站
  • 石家庄网站建站推广优化网站排名
  • 成都网站建设租书网电脑培训学校网站
  • 上海最好的网站设计公司nba体育新闻
  • 网站设计banner尺寸化妆培训
  • 发行商城小程序搜索优化是什么意思
  • 淄博网站建设报价网站营销策划公司
  • 南充网站建设公司软文推广新闻发布