A Split it!

思路：
翻轉(zhuǎn)后看前k個(gè)連續(xù)是否相等，并且滿足$k?2+1<=n$

代碼：

#include<bits/stdc++.h> #include<iostream> #include <stdio.h> using namespace std; const int maxn=200005; const int base=131; typedef long long ll; #define pi acos(-1) #define INF 0x3f3f3f3f #define mod 998244353 const int inf=1<<30; int a[maxn]; int b[maxn]; vector<int> pos; int main() {//freopen("data.in","r",stdin);//freopen("1.out","w",stdout);int t,n,k;cin>>t;string s,s1;while(t--){cin>>n>>k;cin>>s;s1 = s;reverse(s.begin(),s.end());//cout<<s<<endl;int f = 0,cnt = 0;for(int i = 0;i < n ; i++ ){if(s[i] != s1[i] ){if(cnt >= k)f = 1;break;}cnt++;if(cnt >= k){f = 1;break;}}if(k == 0 || ( f && (k*2+1 <= n)))cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return 0; }

B Max and Mex

思路：可以用$\frac{a+b+1}{2}$計(jì)算
如果加入的這個(gè)b已經(jīng)存在于序列中，mex和max不會(huì)變，答案為原序列中不同元素個(gè)數(shù)。

如果b不存在于序列中，并且原序列不是連續(xù)的，則有$mex<max$,那么b最小為$\frac{mex+mex+1+1}{2}$,即$mex+1$,加入后b后$me{x}^{\prime }$和$ma{x}^{\prime }$不變，答案為原序列中不同元素個(gè)數(shù)加一。

如果b不存在于序列中，并且原序列是連續(xù)的則有$mex>max$,，mex一定為$max+1$，那么b為$\frac{max+max+1+1}{2}$,即$max+1$。
加入后b后,$me{x}^{\prime }$變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">$mex+1=max+2$ ，$ma{x}^{\prime }$變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">$max+1$，新的$b^{\prime }=b+1=max+2$,以此類推……答案為原序列中不同元素個(gè)數(shù)加k。

代碼：

#include<bits/stdc++.h> #include<iostream> #include <stdio.h> using namespace std; const int maxn=200005; const int base=131; typedef long long ll; #define pi acos(-1) #define INF 0x3f3f3f3f #define mod 998244353 const int inf=1<<30; ll a[maxn]; set<ll> vis; int main() {//freopen("data.in","r",stdin);//freopen("1.out","w",stdout);ll t,n,k;cin>>t;string s,s1;while(t--){cin>>n>>k;vis.clear();memset(a,0,sizeof(a));for(ll i = 1;i <= n;i++){cin>>a[i];vis.insert(a[i]);}sort(a+1,a+1+n);ll aa,bb;bb = a[n];ll cnt = 0;if(k == 0){cout<<vis.size()<<endl; continue;}ll i ;for( i =1 ;i <= n;i++){if(i == 1 && a[i] != 0){aa = 0;break;}if(a[i+1] != a[i]+1 ){aa = a[i]+1;break;}}ll b = (aa + bb +1) / 2;cnt++;if(vis.find(b) != vis.end() || cnt == k){vis.insert(b);cout<<vis.size()<<endl; }else{ //找不到if(aa > bb)cout<<vis.size() + k<<endl;elsecout<<vis.size() + 1<<endl;}}return 0; }

C Diamond Miner

思路：
將所有的x和y都映射到第一象限上，依次將最小的x點(diǎn)和y點(diǎn)一一對(duì)應(yīng)求距離即可。

代碼：

#include<bits/stdc++.h> #include<iostream> #include <stdio.h> using namespace std; const int maxn=200005; const int base=131; typedef long long ll; #define pi acos(-1) #define INF 0x3f3f3f3f #define mod 998244353 const int inf=1<<30; ll a[maxn],b[maxn]; int main() {//freopen("data.in","r",stdin);//freopen("1.out","w",stdout);ll t,n,k;cin>>t;while(t--){cin>>n;ll x ,y;int cnt1 = 0,cnt2 = 0; for(int i = 1;i <= n *2;i++){cin>>x>>y;if(x == 0){if(y > 0)a[++cnt1] = y;else a[++cnt1] = -y;}if(y == 0){if(x > 0)b[++cnt2] = x;else b[++cnt2] = -x;}}sort(b+1,b+n+1);sort(a+1,a+n+1);double ans = 0.0;for(int i =1;i <= n; i++){ans += sqrt(a[i] * a[i]*1.0 + b[i] *b[i]*1.0);}printf("%.15lf\n",ans);}return 0; }

D Let’s Go Hiking

題意：給定一個(gè)序列，Qingshan只能沿著單調(diào)下降的方向移動(dòng)，Daniel只能沿著單調(diào)上升的方向移動(dòng)，Q先移動(dòng)，D后手，誰(shuí)先不能移動(dòng)誰(shuí)輸。

思路：
首先在這個(gè)n長(zhǎng)的序列中可能有m個(gè)單調(diào)的連續(xù)子序列。Q和D都只能在單調(diào)子序列上移動(dòng)，Q選擇序列中最大的位置，D選擇最小的位置。

為了讓自己的移動(dòng)步數(shù)多，Q和D都會(huì)選擇最長(zhǎng)的單調(diào)序列，因?yàn)槿绻尦鲎铋L(zhǎng)的序列則必輸。如果只有一個(gè)最長(zhǎng)的單調(diào)序列，Q和D相當(dāng)于往對(duì)方移動(dòng)，必會(huì)相遇。由于Q先手，Q必輸。

有多條等長(zhǎng)的間隔開(kāi)的單調(diào)序列，Q和D能移動(dòng)的距離相等，因?yàn)镼先手，Q必輸。

有連接在一起的等長(zhǎng)單調(diào)序列時(shí)，即一個(gè)波形，單調(diào)上升和單調(diào)下降的部分長(zhǎng)度相等為L(zhǎng)。如果長(zhǎng)度L為偶數(shù)，和上面的情況相同，Q必輸。

如果每部分長(zhǎng)度L為奇數(shù)，Q先手，Q可以往往兩個(gè)方向移動(dòng)。長(zhǎng)度為奇數(shù)下Q和D相遇，Q先手D必輸，所以D只能放在第二小的位置將這種相遇轉(zhuǎn)化為長(zhǎng)度為偶數(shù)的相遇；但是Q可以選擇向另一邊移動(dòng)，Q和D同方向移動(dòng)，Q還是可以L次，D放在第二小的位置只能移動(dòng)L-1次,D必輸。

代碼：

#include<bits/stdc++.h> #include<iostream> #include <stdio.h> using namespace std; const int maxn=200005; const int base=131; typedef long long ll; #define pi acos(-1) #define INF 0x3f3f3f3f #define mod 998244353 const int inf=1<<30; int p[maxn]; int l[maxn],r[maxn];int main() {//freopen("data.in","r",stdin);//freopen("1.out","w",stdout);int n;cin>>n;for(int i = 1; i <= n;i++){cin>>p[i];}l[1] = 1;r[n] = 1;for(int i =2 ;i <= n;i++)l[i] = (p[i] > p[i-1])? l[i-1] + 1 : 1;for(int i = n-1 ;i >= 1; i--)r[i] = (p[i] > p[i+1]) ? r[i+1] + 1 : 1;int ma = 0,cnt = 0,vis = 0;for(int i = 1;i <= n;i++){if(l[i] > ma || r[i] > ma){ma = max(l[i],r[i]);cnt = 1;vis = i;}else if(l[i] == ma || r[i] == ma){cnt = 0;}}int ans;int mx = l[vis] > r[vis]? l[vis] : r[vis];int mi = l[vis] > r[vis]? r[vis] : l[vis];if(cnt && mx % 2 &&mx == mi)ans = 1;elseans = 0;cout<<ans<<endl;return 0; }

E Garden of the Sun

題意：
n行m列的農(nóng)田里，種了n*m朵太陽(yáng)花，因陽(yáng)光猛烈太陽(yáng)花死掉了許多，剩下的空格子沒(méi)有共同邊或角。

你需要移除剩下的太陽(yáng)花，使得滿足：一、空格是聯(lián)通的，二、任何兩個(gè)空格間都有一條簡(jiǎn)單路徑，即所有的空格是不成環(huán)的。

思路：
構(gòu)造，構(gòu)的我心態(tài)炸了，就硬構(gòu)。

每三行把其中一行全置空，行是三的倍數(shù)就置空中間的，不是置空第一行，然后聯(lián)通剩下兩行就可以了。

代碼：

#include<bits/stdc++.h> #include<iostream> #include <stdio.h> using namespace std; const int maxn=60005; const int base=131; typedef long long ll; #define pi acos(-1) #define INF 0x3f3f3f3f #define mod 998244353 const int inf=1<<30; string g[maxn]; string ans[maxn];int main() {//freopen("data.in","r",stdin);//freopen("1.out","w",stdout);// ios::sync_with_stdio(false); cin.tie(0);int t,n,m;cin>>t;while(t--){cin>>n>>m;for(int i = 0; i < n; i++){g[i].clear();cin>>g[i];}for(int i = (n%3) == 0; i < n;){for(int j = 0; j < m; j++)g[i][j] = 'X';i += 3;if(i >= n)break;int pos = 1;if(m == 1 || (g[i - 1][1] != 'X' && g[i - 2][1] != 'X' )){pos = 0;}g[i - 1][pos] = 'X';g[i - 2][pos] = 'X';}for(int i = 0; i < n; i++)cout<<g[i]<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的codeforces 706 div2题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。