題目描述1

Problem - A - Codeforces

題目分析

樣例1解釋：

對(duì)于此題，我們采用貪心的想法，從1到n塊數(shù)越少越好，故剛好符合最少的塊數(shù)即可，由于第1塊與第n塊是我們必須要走的路，所以我們可以根據(jù)這兩塊磚的顏色進(jìn)行分類(lèi)判斷。

如果這兩塊磚是一樣的顏色，我們只需要判斷這兩塊磚算上中間的顏色的總塊數(shù)是否>=k即可。

如果這兩塊磚是不一樣的顏色，我們需要分別從兩端觀察前面這部分的磚和后面這部分磚可以走的相同的顏色是否>=k即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
void solve()
{int n, k, c[N];cin >> n >> k;for(int i = 1; i <= n; i ++)cin >> c[i];if(c[1] == c[n]){int cnt = 0;for(int i = 2; i <= n - 1; i ++){if(c[i] == c[1])cnt ++;	}if(cnt >= k - 2)cout << "YES" << '\n';else cout << "NO" << '\n';}else {int l = n, r = 1,kl = 0, kr = 0;for(int i = 1; i <= n && kl < k; i ++){if(c[i] == c[1]){kl ++;l = i;}}for(int i = n; i >= 1 && kr < k; i --){if(c[i] == c[n]){kr ++;r = i;}}if(kl == k && kr == k && l < r)cout << "YES" << '\n';else cout << "NO" << '\n'; }
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while(t --){solve();}return 0;
}

題目描述2

Problem - B - Codeforces

題目樣例示意：

注意：找出的是排列也就是說(shuō)數(shù)字不能重復(fù)，而且所有的數(shù)從小到大排序之后一定為連續(xù)的。

思考：什么是好區(qū)間？

包含1但是不包含2的區(qū)間（2）

包含1，2但是不包含3的區(qū)間（3）

包含1，3但是不包含2的區(qū)間（2）

為了使這樣的區(qū)間盡可能多

我們可以進(jìn)行一個(gè)構(gòu)造，題目要求在所有的區(qū)間中盡量使所有的素?cái)?shù)結(jié)果最多我們可以將2和3放在兩邊，將1放在中間，這樣中間的大部分經(jīng)過(guò)了1，但是未到達(dá)兩邊的2，3區(qū)間都是有貢獻(xiàn)的，或者經(jīng)過(guò)了1，2，但是沒(méi)經(jīng)過(guò)3的也是有貢獻(xiàn)的，或者經(jīng)過(guò)了1，3但是沒(méi)經(jīng)過(guò)2的也有貢獻(xiàn)。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], n;
void solve()
{cin >> n;a[1] = 3, a[n] = 2;int x = (n + 1) / 2;a[x] = 1;int k = 3;for(int i = 2; i < x; i ++){k ++;a[i] = k;	} for(int i = x + 1; i < n; i ++){k ++;a[i] = k;}for(int i = 1; i <= n; i ++)cout << a[i] << ' ';cout << '\n';
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while(t --){solve();}return 0;
}

題目描述3?

Problem - C - Codeforces

題目分析

此題我們需要掌握縮點(diǎn)的思想。

縮點(diǎn)：連續(xù)相同的字符變成一個(gè)字符即可

eg.00011110001011縮點(diǎn)成010101

需要不降序排列故左邊0多好,"?"挨著哪個(gè)數(shù)就縮成哪個(gè)數(shù)，如果左右兩邊的數(shù)不一樣就統(tǒng)一先按左邊來(lái)縮數(shù)

#include<bits/stdc++.h>
using namespace std;
void solve()
{string s ;cin >> s;int n = s.size() ;for(int i = 0; i < n; i ++){if(i != 0 && s[i] == '?'){s[i] = s[i - 1];		}	else if(i == 0 && s[i] == '?')s[i] = '0';}		cout << s << '\n';
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin >> t;while(t --){solve();}return 0;
}

題目描述4

Problem - D - Codeforces

題目分析?

由上圖可知變化一次必然會(huì)進(jìn)行一次顏色的翻轉(zhuǎn)

R表示數(shù)字不同的一列，B表示數(shù)字相同的一列

故要么是全R要么是全B才能到達(dá)一個(gè)全B的終點(diǎn)

一次操作到全R兩次操作就會(huì)回到全B，故我們需要進(jìn)行操作綁定

兩兩配對(duì)操作會(huì)使得除了這兩個(gè)數(shù)之外的所有數(shù)都不發(fā)生變化（操作綁定）

但是如果剩下一個(gè)數(shù)沒(méi)有配對(duì)時(shí)，可以進(jìn)行如圖右下角的方法計(jì)算

將需要改變的1存入vector中，并將其中的不能配對(duì)的奇數(shù)的1單獨(dú)取出計(jì)算，剩下的進(jìn)行配對(duì)即可

注：若取出的數(shù)的位置不在1時(shí)就可以改變(1, x - 1),(1, x)

若取出的數(shù)的位置在1時(shí)就可以改變(x, n)(x + 1, n)

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
typedef pair<int, int> PII; 
void solve()
{char a[N], b[N];int n;vector<PII> ans;vector<int> pos;cin >> n;cin >> a + 1 >> b + 1;bool flag1 = 0, flag2 = 0;for(int i = 1; i <= n; i ++){if(a[i] == b[i])flag1 = 1;else flag2 = 1;}if(flag1 && flag2){cout << "NO" << '\n';return;}if(flag2)//如果全是不相同的字符{ans.push_back({1, n});for(int i = 1; i <= n; i ++){if(a[i] == '0')a[i] = '1';else a[i] = '0';}}for(int i = 1; i <= n; i ++){if(a[i] == '1')pos.push_back(i);}if(pos.size() & 1){int x = pos.back();if(x == 1){ans.push_back({x, n});ans.push_back({x + 1, n});}else{ans.push_back({1, x - 1});ans.push_back({1, x});}pos.pop_back();}for(auto i : pos)ans.push_back({i, i});cout << "YES" << '\n' << ans.size() << '\n';for(auto i : ans){cout << i.first << ' ' << i.second << '\n';	} 
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin >> t;while(t --){solve();}return 0;
}

題目描述5

Problem - E - Codeforces

題目分析

此題相當(dāng)于找規(guī)律，從最大的數(shù)開(kāi)始看起，第一個(gè)大于等于(n - 1)的平方數(shù)就是此處可以組成的平方數(shù)，發(fā)現(xiàn)會(huì)有連續(xù)的一段的平方數(shù)一樣，判斷限制條件，如果條件不滿(mǎn)足就循環(huán)改數(shù)使其滿(mǎn)足條件。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
void solve()
{bitset<N> vis;int n;cin >> n;int y = 0;while(y * y < n - 1)y ++;for(int i = n - 1; i >= 0; i --){while(y * y - i >= n || vis[y * y - i])y --;a[i] = y * y - i;vis[a[i]] = true;}for(int i = 0; i < n; i ++){cout << a[i] << ' ';}cout << '\n';
}
int main()
{int t;cin >> t;while(t --){solve();}return 0;
}