Codeforces Beta Round #46 (Div. 2)

Codeforces Beta Round #46 (Div. 2)

http://codeforces.com/contest/49

A

 #include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull; int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
map<char,int>mp;
mp['A']++;
mp['E']++;
mp['I']++;
mp['O']++;
mp['U']++;
mp['Y']++;
mp['a']++;
mp['e']++;
mp['i']++;
mp['o']++;
mp['u']++;
mp['y']++;
string str;
getline(cin,str);
char ch;
for(int i=str.length()-;i>=;i--){
if((str[i]>='A'&&str[i]<='Z')||(str[i]>='a'&&str[i]<='z')){
ch=str[i];
break;
}
}
if(mp[ch]) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}

B

模拟进制转换和运算

 #include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull; int getmax(int a){
int Max=;
while(a){
Max=max(a%,Max);
a/=;
}
return Max;
} int Change(int n,int base){
int p=;
int ans=;
while(n){
ans=ans+(n%)*p;
n/=;
p*=base;
}
return ans;
} int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
int a,b;
cin>>a>>b;
int base=max(getmax(a),getmax(b))+;
int sum=Change(a,base)+Change(b,base);
int ans=;
while(sum){
sum/=base;
ans++;
}
cout<<ans<<endl;
}

C

找规律

 #include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull; int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
int n;
cin>>n;
cout<<n<<" ";
for(int i=;i<n;i++) cout<<i<<" ";
}

D

枚举第一个是0还是1,然后不断向后遍历判断,取最小值

 #include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull; int n;
string str; int func(int ch){
int ans=;
if(str[]!=ch+'') ans++;
ch^=;
for(int i=;i<str.length();i++){
if(str[i]!=ch+''){
ans++;
}
ch^=;
}
return ans;
} int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n;
cin>>str;
int ans=0x3f3f3f3f;
ans=min(ans,func());
ans=min(ans,func());
cout<<ans<<endl;
}

E

区间DP

参考博客:https://blog.csdn.net/zhjchengfeng5/article/details/8201105

 #include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 1000005
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; string s[];
int n;
string str[];
int dp[][];
bool book[][][][];
int len[]; void Init(int id){
len[id]=s[id].length();
rep(i,,len[id]){
book[id][i][i][s[id][i]-'a']=;
}
rep(L,,len[id]+){
int st=;
rep(en,st+L-,len[id]){
rep(mid,st,en){
rep(i,,n){
if(book[id][st][mid][str[i][]-'a']&&book[id][mid+][en][str[i][]-'a']){
book[id][st][en][str[i][]-'a']=;
}
}
}
st++;
}
}
} int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>s[]>>s[];
cin>>n;
for(int i=;i<n;i++){
cin>>str[i];
}
Init(),Init();
memset(dp,0x3f,sizeof(dp));
dp[][]=;
rep(mid0,,len[]){
rep(mid1,,len[]){
rep(st0,mid0,len[]){
rep(st1,mid1,len[]){
rep(ch,,){
if(book[][mid0][st0][ch]&&book[][mid1][st1][ch]){
dp[st0+][st1+]=min(dp[st0+][st1+],dp[mid0][mid1]+);
}
}
}
}
}
}
int ans=dp[len[]][len[]];
if(ans==0x3f3f3f3f) cout<<-<<endl;
else cout<<ans<<endl;
}
上一篇:zoj2818 Root of the Problem 简单数学 开方


下一篇:Ruby的基本语法-数组