Codeforces Beta Round #16 (Div. 2 Only)
http://codeforces.com/contest/16
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 maxn 500005
typedef long long ll;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ int n,m;
string str[]; int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
cin>>n>>m;
int flag=;
map<int,int>mp;
for(int i=;i<n;i++) cin>>str[i];
for(int i=;i<n;i++){
if(str[i][]==str[i-][]) flag=;
}
if(!flag){
if(m==){
cout<<"YES"<<endl;
}
else{
for(int k=;k<n;k++){
for(int i=;i<m;i++){
if(str[k][i]!=str[k][i-]) flag=;
}
}
if(flag) cout<<"NO"<<endl;
else 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 maxn 500005
typedef long long ll;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ struct sair{
ll num,val;
}a[]; bool cmp(sair a,sair b){
return a.val>b.val;
} int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
ll n,m;
cin>>n>>m;
for(int i=;i<=m;i++){
cin>>a[i].num>>a[i].val;
}
sort(a+,a+m+,cmp);
ll ans=;
for(int i=;i<=m;i++){
if(n>=a[i].num){
ans+=a[i].num*a[i].val;
n-=a[i].num;
}
else if(n<a[i].num){
ans+=a[i].val*n;
n=;
}
if(!n) break;
}
cout<<ans<<endl;
}
C
gcd
#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 maxn 500005
typedef long long ll;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ ll gcd(ll a,ll b){
if(b==) return a;
return gcd(b,a%b);
}
int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
ll a,b,c,d;
cin>>a>>b>>c>>d;
ll x=gcd(c,d);
c/=x;
d/=x;
x=min(a/c,b/d);
cout<<c*x<<" "<<d*x<<endl;
}
D
模拟
#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 maxn 500005
typedef long long ll;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */
string str; int Change(char ch1,char ch2){
return (ch1-'')*+(ch2-'');
} int main(){
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif
// std::ios::sync_with_stdio(false);
int n;
scanf("%d%*c",&n);
int pres=,pref=;
int ans=;
int co=;
for(int i=;i<=n;i++){
getline(cin,str);
// cout<<str<<" "<<i<<endl;
char flag=str[];
int shi=Change(str[],str[]);
int fen=Change(str[],str[]);
if(flag=='p') shi+=;
if(shi==&&flag=='a') shi=;
if(shi==&&flag=='p') shi=;
// cout<<pres<<" "<<pref<<" "<<shi<<" "<<fen<<endl;
if(shi==pres&&fen==pref) co++;
else {
co=;
}
if(co>) {
co=;
ans++;
}
if(shi<pres||(shi==pres&&fen<pref)){
ans++;
}
pres=shi;
pref=fen;
}
cout<<ans<<endl;
}
E
状压DP
dp(i吃掉j)=dp(i和j同时存在)∗p(i战胜j)的概率∗prob(i和j相遇)的概率
#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 maxn 500005
typedef long long ll;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ int n;
double a[][]; double dp[<<]; int main(){
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n;
for(int i=;i<n;i++){
for(int j=;j<n;j++){
cin>>a[i][j];
}
}
dp[(<<n)-]=;///所有鱼都存在的情况
for(int i=(<<n)-;i;i--){
int num=;
for(int j=;j<n;j++){
if(i&(<<j)) num++;///判断存活鱼的个数
}
for(int j=;j<n;j++){
if(i&(<<j)){///j存活
for(int k=j+;k<n;k++){
if(i&(<<k)){///k存活
dp[i-(<<k)]+=dp[i]*a[j][k]*1.0/(num*(num-)/); ///j吃k
dp[i-(<<j)]+=dp[i]*a[k][j]*1.0/(num*(num-)/); ///k吃j
}
}
}
}
}
for(int i=;i<n;i++){
cout<<dp[<<i]<<" ";
}
cout<<endl;
}