本文主要是介绍2014 Multi-University Training Contest 6小记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1003 贪心
对于111...10....000 这样的序列，
a 为1的个数，b为0的个数，易得当
x= a / (a + b) 时 f最小。
讲串分成若干段 1..10..0 , 1..10..0 ,
要满足x非递减 。
对于 xi > xi+1 这样的合并 即可。
const int maxn = 100008 ;struct Node{int one ;int zero ;double f ;Node(){}Node(int o , int z) : one(o) , zero(z){}
};int n ;
int a[maxn] ;
stack<Node> stk ;
vector<Node> lis ;double answer(){int i , l , r ;l = 1 ;while(a[l] == 0 && l <= n) l++ ;r = n ;while(a[r] == 1 && r >= 1) r-- ;if(l > r) return 0.0 ;lis.clear() ;Node nd(0 , 0) ;int c = 1 ;for(i = l ; i <= r ; i++){if(c && a[i] == 1) nd.one++ ;else if(c && a[i] == 0){nd.zero++ ;c = 0 ;}else if(!c && a[i] == 0) nd.zero++ ;else if(!c && a[i] == 1){nd.f = double(nd.one) / double(nd.one + nd.zero) ;lis.push_back(nd) ;nd = Node(1 , 0) ;c = 1 ;}}nd.f = double(nd.one) / double(nd.one + nd.zero) ;lis.push_back(nd) ;
/*for(i = 0 ; i < lis.size() ; i++){nd = lis[i] ;cout<< nd.one <<" " <<nd.zero<<endl ;}
*/while(! stk.empty()) stk.pop() ;for(i = 0 ; i < lis.size() ; i++){nd = lis[i] ;while(! stk.empty() && nd.f < stk.top().f){nd.one += stk.top().one ;nd.zero += stk.top().zero ;nd.f = double(nd.one) / double(nd.one + nd.zero) ;stk.pop() ;}stk.push(nd) ;}double sum = 0.0 ;while(! stk.empty()){nd = stk.top() ; stk.pop() ;sum += (1.0 - nd.f)*(1.0 - nd.f) * nd.one + nd.f * nd.f * nd.zero ;}return sum ;
}int main(){int t , i ;cin>>t ;while(t--){cin>>n ;for(i = 1 ; i <= n ; i++) scanf("%d" , &a[i]) ;printf("%.6lf\n" , answer()) ;}return 0 ;
}1005 奇偶染色， 2种染法，取最大值
const int maxn = 108 ;typedef unsigned long long ULL ;int a[maxn][maxn] ;
int n , m ;int d[4][2] = {{-1 ,0} , {0 ,-1} , {0 , 1} , {1 , 0}} ;int can(int x , int y){return 1 <= x && x <= n && 1 <= y && y <= m ;
}ULL sum(){ULL t = 0ULL ;for(int i = 1 ; i <= n ; i++){for(int j = 1 ; j <= m ; j++){if(a[i][j] == 0) continue ;int c = 0 ;for(int k = 0 ; k < 4 ; k++){int x = i + d[k][0] ;int y = j + d[k][1] ;if(can(x , y) && a[x][y] == 0) c++ ;}t += (ULL) pow(2.0 , double(c)) ;}}return t ;
}int main(){int t , i , j ;cin>>t ;while(t--){cin>>n>>m ;memset(a , 0 , sizeof(a)) ;for(i = 1 ; i <= n ; i++){for(j = 1 ; j <= m ; j++) if((i+j)&1) a[i][j] = 1 ;}ULL ans = sum() ;memset(a , 0 , sizeof(a)) ;for(i = 1 ; i <= n ; i++){for(j = 1 ; j <= m ; j++) if(((i+j)&1) == 0) a[i][j] = 1 ;}ans = max(ans , sum()) ;cout<< ans << endl ;}return 0;
}
1007
多推导几步，找公式，需要用到大数 ，MyEclipse过期了。
#define MAXN 9999
#define MAXSIZE 10
#define DLEN 4class BigNum
{
private:int a[1000]; //可以控制大数的位数int len; //大数长度
public:BigNum(){ len = 1;memset(a,0,sizeof(a)); } //构造函数BigNum(const int); //将一个int类型的变量转化为大数BigNum(const char*); //将一个字符串类型的变量转化为大数BigNum(const BigNum &); //拷贝构造函数BigNum &operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算friend istream& operator>>(istream&, BigNum&); //重载输入运算符friend ostream& operator<<(ostream&, BigNum&); //重载输出运算符BigNum operator+(const BigNum &) const; //重载加法运算符，两个大数之间的相加运算BigNum operator-(const BigNum &) const; //重载减法运算符，两个大数之间的相减运算BigNum operator*(const BigNum &) const; //重载乘法运算符，两个大数之间的相乘运算BigNum operator/(const int &) const; //重载除法运算符，大数对一个整数进行相除运算BigNum operator^(const int &) const; //大数的n次方运算int operator%(const int &) const; //大数对一个int类型的变量进行取模运算bool operator>(const BigNum & T)const; //大数和另一个大数的大小比较bool operator>(const int & t)const; //大数和一个int类型的变量的大小比较void clean(){while(len > 1 && !a[len-1]) len--;}void print(); //输出大数
};
BigNum::BigNum(const int b) //将一个int类型的变量转化为大数
{int c,d = b;len = 0;memset(a,0,sizeof(a));while(d > MAXN){c = d - (d / (MAXN + 1)) * (MAXN + 1);d = d / (MAXN + 1);a[len++] = c;}a[len++] = d;
}
BigNum::BigNum(const char*s) //将一个字符串类型的变量转化为大数
{int t,k,index,l,i;memset(a,0,sizeof(a));l=strlen(s);len=l/DLEN;if(l%DLEN)len++;index=0;for(i=l-1;i>=0;i-=DLEN){t=0;k=i-DLEN+1;if(k<0)k=0;for(int j=k;j<=i;j++)t=t*10+s[j]-'0';a[index++]=t;}
}
BigNum::BigNum(const BigNum & T) : len(T.len) //拷贝构造函数
{int i;memset(a,0,sizeof(a));for(i = 0 ; i < len ; i++)a[i] = T.a[i];
}
BigNum & BigNum::operator=(const BigNum & n) //重载赋值运算符，大数之间进行赋值运算
{int i;len = n.len;memset(a,0,sizeof(a));for(i = 0 ; i < len ; i++)a[i] = n.a[i];return *this;
}
istream& operator>>(istream & in, BigNum & b) //重载输入运算符
{char ch[MAXSIZE*4];int i = -1;in>>ch;int l=strlen(ch);int count=0,sum=0;for(i=l-1;i>=0;){sum = 0;int t=1;for(int j=0;j<4&&i>=0;j++,i--,t*=10){sum+=(ch[i]-'0')*t;}b.a[count]=sum;count++;}b.len =count++;return in;}
ostream& operator<<(ostream& out, BigNum& b) //重载输出运算符
{int i;cout << b.a[b.len - 1];for(i = b.len - 2 ; i >= 0 ; i--){cout.width(DLEN);cout.fill('0');cout << b.a[i];}return out;
}BigNum BigNum::operator+(const BigNum & T) const //两个大数之间的相加运算
{BigNum t(*this);int i,big; //位数big = T.len > len ? T.len : len;for(i = 0 ; i < big ; i++){t.a[i] +=T.a[i];if(t.a[i] > MAXN){t.a[i + 1]++;t.a[i] -=MAXN+1;}}if(t.a[big] != 0)t.len = big + 1;elset.len = big;return t;
}
BigNum BigNum::operator-(const BigNum & T) const //两个大数之间的相减运算
{int i,j,big;bool flag;BigNum t1,t2;if(*this>T){t1=*this;t2=T;flag=0;}else{t1=T;t2=*this;flag=1;}big=t1.len;for(i = 0 ; i < big ; i++){if(t1.a[i] < t2.a[i]){j = i + 1;while(t1.a[j] == 0)j++;t1.a[j--]--;while(j > i)t1.a[j--] += MAXN;t1.a[i] += MAXN + 1 - t2.a[i];//for(int k=0;k<big;k++)// printf("%d %d\n",t1.a[k],t2.a[k]);}elset1.a[i] -= t2.a[i];}t1.len = big;//for(i=0;i<big;i++) cout<<t1.a[i]<<endl;while(t1.a[big - 1] == 0 && t1.len > 1){t1.len--;big--;}return t1;
}BigNum BigNum::operator*(const BigNum & T) const //两个大数之间的相乘运算
{BigNum ret;int i,j,up;int temp,temp1;for(i = 0 ; i < len ; i++){up = 0;for(j = 0 ; j < T.len ; j++){temp = a[i] * T.a[j] + ret.a[i + j] + up;if(temp > MAXN){temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);up = temp / (MAXN + 1);ret.a[i + j] = temp1;}else{up = 0;ret.a[i + j] = temp;}}if(up != 0)ret.a[i + j] = up;}ret.len = i + j;while(ret.a[ret.len - 1] == 0 && ret.len > 1)ret.len--;return ret;
}
BigNum BigNum::operator/(const int & b) const //大数对一个整数进行相除运算
{BigNum ret;int i,down = 0;for(i = len - 1 ; i >= 0 ; i--){ret.a[i] = (a[i] + down * (MAXN + 1)) / b;down = a[i] + down * (MAXN + 1) - ret.a[i] * b;}ret.len = len;while(ret.a[ret.len - 1] == 0 && ret.len > 1)ret.len--;return ret;
}
int BigNum::operator %(const int & b) const //大数对一个int类型的变量进行取模运算
{int i,d=0;for (i = len-1; i>=0; i--){d = ((d * (MAXN+1))% b + a[i])% b;}return d;
}
BigNum BigNum::operator^(const int & n) const //大数的n次方运算
{BigNum t,ret(1);int i;if(n==0)return 1;if(n==1)return *this;int m=n;while(m>1){t=*this;for( i=1;i<<1<=m;i<<=1){t=t*t;}m-=i;ret=ret*t;if(m==1)ret=ret*(*this);}return ret;
}
bool BigNum::operator>(const BigNum & T) const //大数和另一个大数的大小比较
{int ln;if(len > T.len)return true;else if(len == T.len){ln = len - 1;while(a[ln] == T.a[ln] && ln >= 0)ln--;if(ln >= 0 && a[ln] > T.a[ln])return true;elsereturn false;}elsereturn false;
}
bool BigNum::operator >(const int & t) const //大数和一个int类型的变量的大小比较
{BigNum b(t);return *this>b;
}void BigNum::print() //输出大数
{int i;cout << a[len - 1];for(i = len - 2 ; i >= 0 ; i--){cout.width(DLEN);cout.fill('0');cout << a[i];}cout << endl;
}int num[3008] ;int main(){int n , i , m , T ;cin>>T ;while(T--){cin>>n ;for(i = 1 ; i <= n ; i++) scanf("%d" ,&num[i]) ;m = n - 1 ;BigNum sum(0) , t(1) ;BigNum sum2(0) ;sum = sum + BigNum(num[n]) ;for(i = 1 ; i <= m ; i++){t = t * BigNum(m+1-i) ;t = t / i ;BigNum c = t * BigNum(num[n-i]) ;if(i & 1) sum2 = sum2 + c ;else sum = sum + c ;}if(sum2 > sum){sum2 = sum2 - sum ;putchar('-') ;sum2.print() ;}else{sum = sum - sum2 ;sum.print() ;}}return 0;
}
1010
斗地主， 模拟， 没有顺子的情况，挺好写的。
string a , b ;int ok1(){if(a.length() == 1) return 1 ;if(a.length() == 2){if(a[0] == a[1]) return 1 ;if(a[0] == 'X' && a[1] == 'Y') return 1 ;if(a[0] == 'Y' && a[1] == 'X') return 1 ;}if(a.length() == 3){if(a[0] == a[1] && a[0] == a[2]) return 1 ;}if(a.length() == 4){map<char , int> mp ; mp.clear() ;map<char , int> ::iterator it ;for(int i = 0 ; i < 4 ; i++) mp[a[i]]++ ;if(mp.size() == 1) return 1 ;if(mp.size() == 2){it = mp.begin() ;int c1 = it->second ;it++ ;int c2 = it->second ;if(c1 < c2) swap(c1 , c2) ;if(c1 == 3 && c2 == 1) return 1 ;}}if(a.length() == 5){map<char , int> mp ; mp.clear() ;map<char , int> ::iterator it ;for(int i = 0 ; i < 5 ; i++) mp[a[i]]++ ;if(mp.size() == 2){it = mp.begin() ;int c1 = it->second ;it++ ;int c2 = it->second ;if(c1 < c2) swap(c1 , c2) ;if(c1 == 3 && c2 == 2) return 1 ;}}if(a.length() == 6){map<char , int> mp ; mp.clear() ;map<char , int> ::iterator it ;for(int i = 0 ; i < 6 ; i++) mp[a[i]]++ ;for(it = mp.begin() ; it != mp.end() ; it++){if(it->second == 4) return 1 ;}}return 0 ;
}int To(char c){if(c == 'Y') return 1 ;else if(c == 'X') return 2 ;else if(c == '2') return 3 ;else if(c == 'A') return 4 ;else if(c == 'K') return 5 ;else if(c == 'Q') return 6 ;else if(c == 'J') return 7 ;else if(c == 'T') return 8 ;else if(c == '9') return 9 ;else if(c == '8') return 10 ;else if(c == '7') return 11 ;else if(c == '6') return 12 ;else if(c == '5') return 13 ;else if(c == '4') return 14 ;else if(c == '3') return 15 ;
}int cnta[20] , cntb[20] ;int ok2(){int i , j , mxa , mxb ;memset(cnta , 0 , sizeof(cnta)) ;memset(cntb , 0 , sizeof(cntb)) ;for(i = 0 ; i < a.size() ; i++) cnta[To(a[i])]++ ;for(i = 0 ; i < b.size() ; i++) cntb[To(b[i])]++ ;if(cnta[1] && cnta[2]) return 1 ;if(cntb[1] && cntb[2]) return 0 ;mxa = 16 ;for(i = 3 ; i <= 15 ; i++){if(cnta[i] == 4){mxa = i ;break ;}}mxb = 16 ;for(i = 3 ; i <= 15 ; i++){if(cntb[i] == 4){mxb = i ;break ;}}if(mxa != 16 && mxb == 16) return 1 ;if(mxa ==16 && mxb != 16) return 0 ;if(mxa != 16 && mxb != 16 && mxa < mxb) return 1 ;if(mxa != 16 && mxb != 16 && mxa > mxb) return 0 ;mxa = 16 ;for(i = 3 ; i <= 15 ; i++){if(cnta[i] == 3){mxa = i ;break ;}}mxb = 16 ;for(i = 3 ; i <= 15 ; i++){if(cntb[i] == 3){mxb = i ;break ;}}if(mxa != 16 && mxb == 16) return 1 ;if(mxa !=16 && mxb != 16 && mxa < mxb) return 1 ;if(mxa != 16 && mxb != 16 && mxa > mxb){int ca = 0 ;for(i = 3 ; i <= 15 ; i++){if(cnta[i] >= 2 && i != mxa) ca = 1 ;}int cb = 0 ;for(i = 3 ; i <= 15 ; i++){if(cntb[i] >= 2 && i != mxb) cb = 1 ;}if(ca==1 && cb==0) return 1 ;ca = 0 ;for(i = 1 ; i <= 15 ; i++){if(cnta[i] >= 1 && i != mxa) ca = 1 ;}cb = 0 ;for(i = 1 ; i <= 15 ; i++){if(cntb[i] >= 1 && i != mxb) cb = 1 ;}if(ca==1 && cb==0) return 1 ;}mxa = 16 ;for(i = 3 ; i <= 15 ; i++){if(cnta[i] >= 2){mxa = i ;break ;}}mxb = 16 ;for(i = 3 ; i <= 15 ; i++){if(cntb[i] >= 2){mxb = i ;break ;}}if(mxa != 16 && mxb == 16) return 1 ;if(mxa !=16 && mxb != 16 && mxa < mxb) return 1 ;mxa = 16 ;for(i = 1 ; i <= 15 ; i++){if(cnta[i] >= 1){mxa = i ;break ;}}mxb = 16 ;for(i = 1 ; i <= 15 ; i++){if(cntb[i] >= 1){mxb = i ;break ;}}if(mxa != 16 && mxb == 16) return 1 ;if(mxa !=16 && mxb != 16 && mxa < mxb) return 1 ;return 0 ;
}int main(){int t ;cin>>t ;while(t--){cin>>a>>b ;if(ok1()){ puts("Yes") ; continue ;}if(ok2()) puts("Yes") ;else puts("No") ;}return 0 ;
}
这篇关于2014 Multi-University Training Contest 6小记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
