CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!) 題解
A-Two 0-1 Sequences
題意:有兩個字串\(a和b\),都是\(01\)字串,可以進行一下操作看是否可以將\(a\)變成\(b\),設\(a_1\)和\(a_2\) 表示的是字串\(a\)的第一個字母和字母
- 在滿足可以操作的前提下,將\(a_2\)變成\(max(a_1,a_2)\),并將\(a_1\)刪去
- 在滿足可以操作的前提下,將\(a_2\)變成\(min(a_1,a_2)\),并將\(a_1\)刪去,
思路: 刪去的時候肯定不能讓字串\(a\)的大小<字串\(b\)的大小,并且得知后面的字串一定要相同,否則不能滿足題意,但是字串\(b\)的第一個字母是可以和\(字串a\)與之對應的第一個字母不相同的,因為可以通過操作\(1\)和\(2\)進行變化,將如果缺少\(1\) 那么可以用前面的操作將\(a\)中的\(1\)挪到\(b\)中對應的位置上
code:
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int aa,bb;
cin>>aa>>bb;
string a,b;
cin>>a>>b;
if(aa<bb)//如果大小小的話,直接NO
{
cout<<"NO"<<'\n';
return;
}
if(aa==bb)
{
if(a==b) cout<<"YES"<<'\n';//特殊判斷
else cout<<"NO"<<'\n';
}else
{
for(int i=aa-1,j=bb-1;j>=1;i--,j--)//判斷后面的單詞是否一樣
{
if(a[i]!=b[j])
{
cout<<"NO"<<'\n';
return;
}
}
// debug(a.size()-b.size()+1);
for(int i=0;i<a.size()-b.size()+1;i++)//判斷前面的單詞是否有與之對應的1或者0就可以了
{
if(a[i]==b[0])
{
cout<<"YES"<<'\n';
return;
}
}
cout<<"NO"<<'\n';
}
}
int main()
{
int T=1;
cin>>T;
while(T--) solve();
return 0^0;
}
B-Luke is a Foodie
題意:一串數字,只能挨著吃,當且僅當\(|a_i-x| \le k\) 才可以吃掉,\(x\)當前自己的分數, \(a_i\)是數字,\(k\)是臨界值,開頭可以自己設定任意值,但是之后每一次改變自己的\(x\)都會導致\(ans\)++,問\(ans\)的最小值是多少
題解:考慮貪心:吃的是一個范圍,所以說我們可以找到一個值,使他能夠橫穿而過,這個時候就是最優解,然后再判斷當前是否可以橫穿而過,如果不能,那么就重新寫這個范圍,如果能,賊可以縮小這個范圍 
紅線的就是能走的范圍,如果不能,就只有兩種情況,可以直接哦判斷,然后設定范圍!
code
#include <bits/stdc++.h>
void solve()
{
int n,k;
cin>>n>>k;
int ans=0;
vector<ll> q(n);
for(int i=0;i<n;i++) cin>>q[i];
ll maxn=q[0]+k;//一開始的最大值
ll minn=q[0]-k;//一開始的最小值
for(int i=1;i<n;i++)
{
if(q[i]-k>maxn||q[i]+k<minn)
{
ans++;//如果不在這個范圍內,就重新設定范圍,并且ans++
maxn=q[i]+k;
minn=q[i]-k;
}else
{
maxn=min(maxn,q[i]+k);//縮小范圍
minn=max(minn,q[i]-k);
}
}
cout<<ans<<'\n';
}
int main()
{
int T=1;
cin>>T;
while(T--) solve();
return 0^0;
}
C-Virus
題意:\(n\)個村莊首尾相連,然后有初始化\(k\)個點是一開始感染的,然后每一天就會向外邊感染其他沒有未被感染的村莊(必須是相鄰的),可以在每一天的開始保護一個村莊永遠不會感染,然后可以隔絕其他的村莊感染,然后問你最后感染的最小值
可以考慮貪心.對于一個間隔,我們可以直接保護最左端點和最右端點,然后中間的端點就不會感染,這樣我們能保護的村莊就是最優的.可以先對沒有感染的排序一下,從大到小貪心的做一下
code
#include <bits/stdc++.h>
using namespace std;
bool cmp(int a,int b)
{
return a>b;
}
void solve()
{
int n,k;
cin>>n>>k;
vector<ll> q(k);
for(int i=0;i<k;i++) cin>>q[i];
sort(all(q));
vector<ll> s;
for(int i=1;i<k;i++)
{
if(q[i]-q[i-1]-1>0) s.push_back(q[i]-q[i-1]-1);//如果間隔是大于0的,那么就加入
}
if(n-q[k-1]+q[0]-1>0) s.push_back(n-q[k-1]+q[0]-1);//加入收尾相連的那個
sort(all(s),cmp);
if(s.size()==0)//特判
{
cout<<n<<'\n';
return;
}
ll ans=0;//表示沒有被污染的點
ll day=0;
for(int i=0;i<s.size();i++)
{
s[i]-=day;//減去以前累計的
if(s[i]>0) ans++;
else if(s[i]<=0) break;
s[i]--;
day+=4;//相當于兩天,+4就是這個間隔污染了4個
if(s[i]>=1) ans+=(s[i]-1);//因為上面加了一個了,而且這一天最多污染1個,所以這樣判斷
}
cout<<n-ans<<'\n';
}
int main()
{
IOS;
int T=1;
cin>>T;
while(T--) solve();
return 0^0;
}
D-Magical Array
題意:初始化有\(n\)個陣列,對于其中\(n-1\)個數字進行操作\(1\),對于一個特殊的陣列進行操作\(2\);
操作1:選擇\((i,j)\) 然后可以使得\(a[i-1]+=1,a[i]-=1,a[j]-=1,a[j+1]+=1\).
操作2:選擇\(i,j\),然后使得\(a[i-1]+=1,a[i]-=1,a[j]-=1,a[j+2]+=1\)
然后問你是哪一個特殊的陣列,并且進行了幾次操作?
題解:我們對于這些數字進行前綴和,但是這里是進行兩次前綴和,這樣就能表現出一定的差異,是因為操作\(1\)和操作\(2\)會雖然第一次對于前綴和沒有一定的改變,但是他 操作2會對\(a[i+2]+=1\),這時候相當與對于他的前綴和進行一定的右移,并且可以對于第二次前綴和一定的影響,所以說進行兩次前綴和,然后搞差距,那個差距就是進行操作2的不同數量,然后那個不同的是多少
code
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n,m;
cin>>n>>m;
vector<vector<ll>> s(n+1,vector<ll>(m+1,0));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) cin>>s[i][j];
for(int k=0;k<2;k++)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]+=s[i][j-1];//進行兩次的前綴和
}
vector<int> p(n+1);
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=100;i++)//暴力回圈判斷100便,因為要找到1一個不同,所以隨機判斷前兩個是相同的話,就是對的,這里隨機了,事件復雜度不是很大,感覺近乎O(1)(
{
random_shuffle(p.begin()+1,p.end());
int a=p[1];
int b=p[2];
if(s[a][m]==s[b][m])
{
for(int i=1;i<=n;i++)
{
if(s[i][m]!=s[a][m])
{
cout<<i<<' '<<s[a][m]-s[i][m]<<'\n';
return;
}
}
}
}
}
int main()
{
int T=1;
while(T--) solve();
return 0^0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/500764.html
標籤：其他