|
Problem - A - Codeforces
题目大意：有红r 绿g 蓝b 三把钥匙，还有红R 绿G 蓝B三扇门，先拿钥匙再碰到门就可以开了，三扇门都能开YES，不能NO。
input
4
rgbBRG
RgbrBG
bBrRgG
rgRGBb
output
YES
NO
YES
NO
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<map>
using namespace std;
int main()
{
//cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int a1,a2,a3,b1,b2,b3;
for(int i=0;i<s.size();i++)
{
if(s[i]=='r') a1=i;
else if(s[i]=='R') b1=i;
else if(s[i]=='g') a2=i;
else if(s[i]=='G') b2=i;
else if(s[i]=='b') a3=i;
else b3=i;
}
//cout<<a1<<" "<<a2<<" "<<a3<<" "<<b1<<" "<<b2<<" "<<b3<<endl;
bool flag=true;
if(a1>b1||a2>b2||a3>b3) flag=false;
if(flag==false) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
Problem - B - Codeforces
题目大意：如果条件P[i?2]+P[i?1]≠Pi对所有i(3≤i≤n)成立，我们称长度为n的置换P为反斐波纳契函数。给定一个数字n，让我们求出1~n个数字组成的n个反斐波纳契函数（any）。
input
2
4
3
output
4 1 3 2
1 2 4 3
3 4 1 2
2 4 1 3
3 2 1
1 3 2
3 1 2
一开始用纯暴力做法妥妥的超时了，变换一下思维即可。?
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<map>
using namespace std;
int a[200200];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
a[i]=n-i+1;
for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl;
/*int sum=0;
do
{
bool flag=true;
//cout<<"11111"<<endl;
for(int i=3;i<=n;i++)
{
if(a[i-2]+a[i-1]==a[i])
{
flag=false;
break;
}
}
if(flag==true&&sum!=n)
{
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
sum++;
}
if(sum==n) break;
}while(next_permutation(a+1,a+1+n));*/
int sum=1;
while(sum!=n)
{
for(int i=1;i<=n;i++)
{
if(i==sum) cout<<a[sum+1]<<" "<<a[sum]<<" ",i++;
else cout<<a[i]<<" ";
}
cout<<endl;
sum++;
}
}
return 0;
}
Problem - C - Codeforces
题目大意：给定一个长度为n的数组a，再给定一个数字x。每次在数组中加上k个x，k的范围属于0~n（可非连续加入），然后分别求最大区间和。
input
3
4 2
4 1 3 2
3 5
-2 -7 -1
10 2
-6 -1 -2 4 -6 -1 -4 4 -5 -4
output
10 12 14 16 18
0 4 4 5
4 6 6 7 7 7 7 8 8 8 8
分别求出长度为i的最大和，然后分别加上n个k。
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
using namespace std;
int a[200200],b[200200],f[200200];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
int n,x;
cin>>n>>x;
for(int i=1;i<=n;i++)
cin>>a[i];
memset(b,0,sizeof b);
memset(f,-0x3f3f3f3f,sizeof f);
for(int i=1;i<=n;i++)//前缀和
{
if(i==1) b[1]=a[1];
else b[i]=b[i-1]+a[i];
}
//for(int i=1;i<=n;i++) cout<<b[i]<<" "; cout<<endl;
for(int i=1;i<=n;i++)
{
for(int len=1;len<=n;len++)//长度从1到n依次遍历
{
if(i+len-1<=n) //如果没有越界的话
f[len]=max(f[len],b[i+len-1]-b[i-1]);//更新长度就是i+len-1到i-1的前缀和
}
}
for(int i=0;i<=n;i++)//输出部分，依次进行比较
{
int maxn=-0x3f3f3f3f;
for(int len=1;len<=n;len++)//长度也是从1到n
{
maxn=max(maxn,f[len]+min(i,len)*x);
}
cout<<max(0,maxn)<<" ";//怕会出现负数
}
cout<<endl;
}
return 0;
}
?唔，真就贪心贪麻了
|