A題:http://codeforces.com/contest/1291/problem/A
題意:給你一個長整數,可以删減裡面的任意數字(也可以不删減),要求本身不能除以2,但是該數的各位和能除以2,輸出任意符合要求的數。
思路:這道題的話,貪心,輸出一個兩位數,每位數字都是奇數即可,即在原來長整數找到兩個奇數(ps:不能改變原來數字順序),否則輸出-1。
AC代碼:
#include <bits/stdc++.h>
typedef long long ll;
const int maxx=110;
const int inf=0x3f3f3f3f;
using namespace std;
string s;
int a[maxx];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
cin>>s;
int k=0;
for(int i=0; i<n; i++)
{
if(k==2)
break;
if((s[i]-'0')%2==1)
{
a[k]=s[i]-'0';
k++;
}
}
if(k==2)
cout<<a[0]<<a[1]<<endl;
else
cout<<"-1"<<endl;
}
return 0;
}
B題:http://codeforces.com/contest/1291/problem/B
題意:給你n個數字組成的序列,你可以對任意位置的進行任意次的減一操作直到這個位置的數字等于0才不能進行。問你是否能構造成題目要求的序列:即嚴格單增或單減,又或者是存在一個k,使得a1<a2<.....<ak,ak>ak+1>.....>an。
思路:這道題的話,我們可以先做兩個最小代價的上升序列即0到n-1和n-1到0。我們假設峰頂為x,那麼如果Yes的話在x之前一定成立ai>=i−1,在x之後一定成立ai>=n−i,我們從前往後找到最後一個ai>=i−1的位置記為ans,從後往前找到最後一個ai>=n−i的位置記為tot,那麼如果ans>=tot那麼也就是說他們可以成功銜接,即答案為Yes。
AC代碼:
#include <bits/stdc++.h>
typedef long long ll;
const int maxx=300010;
const int inf=0x3f3f3f3f;
using namespace std;
int a[maxx],b[maxx],c[maxx];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
b[i]=i-1;
}
int cnt=0;
for(int i=n; i>=1; i--)
c[i]=cnt++;
int ans=0,tot=0;
for(int i=1; i<=n; i++)
{
if (a[i]>=b[i])
ans=i;
else
break;
}
for(int i=n; i>=1; i--)
{
if(a[i]>=c[i])
tot=i;
else
break;
}
if(ans>=tot)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
C題:http://codeforces.com/contest/1291/problem/C
題意:有一個由n個數組成的序列,然後恰有n個人進行排隊,每個人隻能從兩端進行取數。你排在第m位,你可以控制k個人取特定的數字(前或後),你取的時候會取最優的,問你取的數的最小值最大是多少。
思路:這道題的話,如果你排在第m位,很顯然在你之後的人對你沒有絲毫影響。你能控制k個人取什麼,其實有用的k=min(m−1,k),隻有控制你之前的人才會對結果産生影響。對于排在你之前的m−1個人,你能控制k個人,不能控制m−1−k個人,且這m−1−k個人可以任意選取,前m−1個人選取完後,剩下n−m+1個數,你會選擇剩餘序列兩端最大的一個數字。我們雙重循環枚舉你控制的k個人取前端數的人有多少個 和 你不能控制的人裡取前端數的人有多少個,最後在剩下的序列裡兩端取個最大的,由于你不能控制的人選取是任意的,是以我們取的最大值要最小,又由于你能控制k個人選取,是以我們得到最小的最大值要盡可能的大。
AC代碼:
#include <bits/stdc++.h>
typedef long long ll;
const int maxx=10010;
const int inf=0x3f3f3f3f;
using namespace std;
int a[maxx];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m,k;
cin>>n>>m>>k;
for(int i=1; i<=n; i++)
cin>>a[i];
k=min(m-1,k);
ll d=m-k-1;
int M=inf;
int N=-inf;
for(int i=0; i<=k; i++)
{
M=inf;
for(int j=0; j<=d; j++)
{
int q=a[1+i+j];
int p=a[n-(k+d-i-j)];
M=min(M,max(q,p));
}
N=max(M,N);
}
cout<<N<<endl;
}
return 0;
}
D題:http://codeforces.com/contest/1291/problem/D
題意:規定兩個字元串的anagrams:兩個字元串中間字元出現的次數一樣。規定reducible,有一個k≥2,然後有s1,t1,s2,t2,...,sk,tk這幾個子串都是對應的anagrams。規定irreducible,就是不reducible。給定一個字元串,和q次詢問,每次詢問給定一個l,r,問這個子串能否構造出一個irreducible。
思路:這道題的話,我們分類讨論一下:
1:如果長度為1。因為必須要k≥2,是以一定能有irr...
2:子串首尾不相同。那這時候隻需要構造一個字元串,構造的字元串的首尾和原字元串首尾是反的。這樣的話就可以保證從前面開始的子串到一個位置k,有s(1...k),t(1...k)一定不是anagrams。
3:字元串中有三個或三個以上的不同的字元。因為如果有三個不同的字元,那麼一定能構造出左右邊界處連續兩個不同。
AC代碼:
#include <bits/stdc++.h>
typedef long long ll;
const int maxx=200010;
const int inf=0x3f3f3f3f;
using namespace std;
int a[26][maxx];
int l,r;
string s;
void solve()
{
cin>>l>>r;
l--,r--;
if(l==r)
{
cout<<"Yes"<<endl;
return ;
}
if(s[l]!=s[r])
{
cout<<"Yes"<<endl;
return ;
}
int tot=0;
for(int i=0; i<26; i++)
{
int R=a[i][r],L=0;
if(l>0)
L=a[i][l-1];
if(R-L>0)
tot++;
}
if(tot>=3)
{
cout<<"Yes"<<endl;
return ;
}
cout<<"No"<<endl;
}
int main()
{
int t;
cin>>s;
cin>>t;
for(int i=0; i<s.size(); i++)
{
a[s[i]-'a'][i]++;
if(i>0)
{
for(int j=0; j<26; j++)
a[j][i]+=a[j][i-1];
}
}
while(t--)
solve();
return 0;
}