- 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[105];
- int main(){
- #ifndef ONLINE_JUDGE
- // freopen("1.txt","r",stdin);
- #endif
- cin>>n>>m;
- int flag=0;
- map<int,int>mp;
- for(int i=0;i<n;i++) cin>>str[i];
- for(int i=1;i<n;i++){
- if(str[i][0]==str[i-1][0]) flag=1;
- }
- if(!flag){
- if(m==1){
- cout<<"YES"<<endl;
- }
- else{
- for(int k=0;k<n;k++){
- for(int i=1;i<m;i++){
- if(str[k][i]!=str[k][i-1]) flag=1;
- }
- }
- if(flag) cout<<"NO"<<endl;
- else cout<<"YES"<<endl;
- }
- }
- else{
- cout<<"NO"<<endl;
- }
- }
- View Code
- 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[25];
- 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=1;i<=m;i++){
- cin>>a[i].num>>a[i].val;
- }
- sort(a+1,a+m+1,cmp);
- ll ans=0;
- for(int i=1;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=0;
- }
- if(!n) break;
- }
- cout<<ans<<endl;
- }
- View Code
- 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==0) 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;
- }
- View Code
- 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-'0')*10+(ch2-'0');
- }
- 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=25,pref=61;
- int ans=0;
- int co=1;
- for(int i=1;i<=n;i++){
- getline(cin,str);
- // cout<<str<<" "<<i<<endl;
- char flag=str[7];
- int shi=Change(str[1],str[2]);
- int fen=Change(str[4],str[5]);
- if(flag=='p') shi+=12;
- if(shi==12&&flag=='a') shi=0;
- if(shi==24&&flag=='p') shi=12;
- // cout<<pres<<""<<pref<<" "<<shi<<" "<<fen<<endl;
- if(shi==pres&&fen==pref) co++;
- else {
- co=1;
- }
- if(co>10) {
- co=1;
- ans++;
- }
- if(shi<pres||(shi==pres&&fen<pref)){
- ans++;
- }
- pres=shi;
- pref=fen;
- }
- cout<<ans<<endl;
- }
- View Code
- 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[25][25];
- double dp[1<<19];
- int main(){
- #ifndef ONLINE_JUDGE
- freopen("1.txt","r",stdin);
- #endif
- std::iOS::sync_with_stdio(false);
- cin>>n;
- for(int i=0;i<n;i++){
- for(int j=0;j<n;j++){
- cin>>a[i][j];
- }
- }
- dp[(1<<n)-1]=1;/// 所有鱼都存在的情况
- for(int i=(1<<n)-1;i;i--){
- int num=0;
- for(int j=0;j<n;j++){
- if(i&(1<<j)) num++;/// 判断存活鱼的个数
- }
- for(int j=0;j<n;j++){
- if(i&(1<<j)){///j 存活
- for(int k=j+1;k<n;k++){
- if(i&(1<<k)){///k 存活
- dp[i-(1<<k)]+=dp[i]*a[j][k]*1.0/(num*(num-1)/2); ///j 吃 k
- dp[i-(1<<j)]+=dp[i]*a[k][j]*1.0/(num*(num-1)/2); ///k 吃 j
- }
- }
- }
- }
- }
- for(int i=0;i<n;i++){
- cout<<dp[1<<i]<<" ";
- }
- cout<<endl;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2946834.html