Codeforces Beta Round #44 (Div. 2)

A

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define maxn 1000005
 8 typedef long long ll;
 9 typedef unsigned long long ull;
10 
11 
12 
13 
14 int main(){
15     #ifndef ONLINE_JUDGE
16       //  freopen("input.txt","r",stdin);
17     #endif
18     std::ios::sync_with_stdio(false);
19     map<int,int>mp;
20     for(int i=1;i<=500;i++){
21         mp[i*(i+1)/2]=1;
22     }
23     int n;
24     cin>>n;
25     if(mp[n]) cout<<"YES"<<endl;
26     else cout<<"NO"<<endl;
27 
28 }

View Code

B

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define maxn 1000005
 8 typedef long long ll;
 9 typedef unsigned long long ull;
10 
11 
12 struct sair{
13     char ch;
14     int v;
15     bool operator<(const sair &b)const{
16         return v>b.v;
17     }
18 }s;
19 
20 int main(){
21     #ifndef ONLINE_JUDGE
22         freopen("input.txt","r",stdin);
23     #endif
24     std::ios::sync_with_stdio(false);
25     int a,b,c;
26     string str;
27     map<char,int>mp;
28     mp['A']++;
29     mp['B']++;
30     mp['C']++;
31     for(int i=1;i<=3;i++){
32         cin>>str;
33         if(str[1]=='>'){
34             mp[str[2]]++;
35         }
36         else{
37             mp[str[0]]++;
38         }
39     }
40     vector<sair>ve;
41     int book[5];
42     memset(book,0,sizeof(book));
43     for(map<char,int>::iterator it=mp.begin();it!=mp.end();it++){
44         s.ch=it->first;
45         s.v=it->second;
46         if(book[s.v]){
47             cout<<"Impossible"<<endl;
48             return 0;
49         }
50         book[s.v]=1;
51         ve.push_back(s);
52     }
53     sort(ve.begin(),ve.end());
54     for(int i=0;i<ve.size();i++){
55         cout<<ve[i].ch;
56     }
57 
58 }

View Code

C

大模拟

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define maxn 1000005
 8 typedef long long ll;
 9 typedef unsigned long long ull;
10 
11 vector<string>ans;
12 string s[6];
13 bool add(char &a,char b){if (a!='.'&&a!=b)return 0;a=b;return 1;}
14 
15 int main(){
16     #ifndef ONLINE_JUDGE
17         freopen("input.txt","r",stdin);
18     #endif
19     std::ios::sync_with_stdio(false);
20     for (int i=0;i<=5;i++)cin>>s[i];
21     sort(s,s+6);
22     do{
23         vector<string>v(s[0].size(),string(s[1].size(),'.'));
24         if (s[0].size()!=s[4].size()+s[3].size()-1) continue;
25         if (s[1].size()!=s[2].size()+s[5].size()-1) continue;
26         bool fl=1;
27         for (int i=0;i<s[0].size();i++)fl&=add(v[i][s[2].size()-1],s[0][i]);
28         for (int i=0;i<s[1].size();i++)fl&=add(v[s[3].size()-1][i],s[1][i]);
29         for (int i=0;i<s[2].size();i++)fl&=add(v[0][i],s[2][i]);
30         for (int i=0;i<s[3].size();i++)fl&=add(v[i][0],s[3][i]);
31         for (int i=0;i<s[4].size();i++)fl&=add(v[s[3].size()-1+i][s[1].size()-1],s[4][i]);
32         for (int i=0;i<s[5].size();i++)fl&=add(v[s[0].size()-1][s[2].size()-1+i],s[5][i]);
33         if (!fl)    continue;
34         if (ans.empty()||v<ans)    ans=v;
35     }while (next_permutation(s,s+6));
36     if (ans.empty())    cout<<"Impossible"<<endl;
37         else for(auto i:ans) cout<<i<<endl;
38 }

View Code

D

暴力搜索

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define maxn 1000005
 8 typedef long long ll;
 9 typedef unsigned long long ull;
10 
11 char s[12][40];
12 int c[12],n,m,ans;
13 void dfs(int t)
14 {
15     int i,j;
16     for(i=0;i<m;i++)
17         if(c[i]<0)return ;
18     if(t>=n)
19     {
20         for(i=0;i<m;i++)
21             if(c[i]>0) return ;
22         ans++;
23         return ;
24     }
25     for(i=0;i<=1;i++)
26     {
27         for(j=0;j<m;j++)
28             if(s[j][t]==(i+'0'))c[j]--;
29         dfs(t+1);
30         for(j=0;j<m;j++)
31             if(s[j][t]==(i+'0'))c[j]++;
32     }
33 }
34 
35 int main(){
36     #ifndef ONLINE_JUDGE
37         freopen("input.txt","r",stdin);
38     #endif
39     std::ios::sync_with_stdio(false);
40     cin>>n>>m;
41     for(int i=0;i<m;i++)cin>>s[i]>>c[i];
42     ans=0;
43     dfs(0);
44     cout<<ans<<endl;
45 }

View Code

E

几何，把子弹按角度从小到大排序，然后模拟

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define maxn 1000005
 8 typedef long long ll;
 9 typedef unsigned long long ull;
10 
11 const double g=9.8;
12 double v,al[10005],ss[10005],cc[10005];
13 int d[10005];
14 pair<double,double> w[100005];
15 double x[10005];
16 
17 double run(double x,double alpha)
18 {
19     return (v*sin(alpha)+v*sin(alpha)-g*x/(v*cos(alpha)))*x/(v*cos(alpha))/2;
20 }
21 bool cmp(const int &a,const int &b)
22 {
23     return al[a]<al[b];
24 }
25 
26 int main(){
27     #ifndef ONLINE_JUDGE
28         freopen("input.txt","r",stdin);
29     #endif
30     std::ios::sync_with_stdio(false);
31     int n,m;
32     scanf("%d%lf",&n,&v);
33     for(int i=1;i<=n;i++)
34         scanf("%lf",&al[d[i]=i]),cc[i]=cos(al[i]),ss[i]=sin(al[i]);
35     sort(d+1,d+1+n,cmp);
36     scanf("%d",&m);
37     for(int i=1;i<=m;i++)
38         scanf("%lf%lf",&w[i].first,&w[i].second);
39     sort(w+1,w+1+m);
40     int j=1;
41     for(int i=1;i<=n;i++)
42     {
43         while(j<=m&&run(w[j].first,al[d[i]])>w[j].second)j++;
44         if(j>m||run(w[j].first,al[d[i]])<0)
45         {
46             x[d[i]]=v*ss[d[i]]/g*2*v*cc[d[i]];
47             continue;
48         }
49         x[d[i]]=w[j].first;
50     }
51     for(int i=1;i<=n;i++)
52         printf("%.9lf %.9lf
",x[i],run(x[i],al[i]));
53 }

View Code