Codeforces Beta Round #63 (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 eb emplace_back
 8 #define maxn 1000006
 9 #define rep(k,i,j) for(int k=i;k<j;k++)
10 typedef long long ll;
11 typedef unsigned long long ull;
12 
13 int n;
14 struct sair{
15     int x,y,z;
16 }a[105];
17 
18 int main(){
19     #ifndef ONLINE_JUDGE
20      //   freopen("input.txt","r",stdin);
21     #endif
22     std::ios::sync_with_stdio(false);
23     cin>>n;
24     for(int i=1;i<=n;i++){
25         cin>>a[i].x>>a[i].y>>a[i].z;
26     }
27     int aa=0,bb=0,cc=0;
28     for(int i=1;i<=n;i++){
29         aa+=a[i].x;
30         bb+=a[i].y;
31         cc+=a[i].z;
32     }
33     if(aa||bb||cc) cout<<"NO"<<endl;
34     else cout<<"YES"<<endl;
35 }

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 eb emplace_back
 8 #define maxn 1000006
 9 #define rep(k,i,j) for(int k=i;k<j;k++)
10 typedef long long ll;
11 typedef unsigned long long ull;
12 
13 int n,m;
14 int k[105],p[105];
15 
16 int main(){
17     #ifndef ONLINE_JUDGE
18      //   freopen("input.txt","r",stdin);
19     #endif
20     std::ios::sync_with_stdio(false);
21     int l,r,t,c;
22     int ans=0;
23     cin>>n>>m;
24     for(int i=0;i<m;i++){
25         cin>>l>>r>>t>>c;
26         for(int j=l;j<=r;j++){
27             if(t<k[j]||!k[j]){
28                 k[j]=t;
29                 ans-=p[j];
30                 p[j]=c;
31                 ans+=p[j];
32             }
33         }
34     }
35     cout<<ans<<endl;
36 }

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 eb emplace_back
  8 #define maxn 1000006
  9 #define rep(k,i,j) for(int k=i;k<j;k++)
 10 typedef long long ll;
 11 typedef unsigned long long ull;
 12 
 13 char name1[110][110],name2[110][110];
 14 int with[110][110],have[110][110],n;
 15 int g[110][110];
 16 char tname[110];
 17 char s[1000010];
 18 int Find(char *name)
 19 {
 20     for (int i=0;i<n;i++)
 21         if (strcmp(name,name1[i])==0) return i;
 22     return 0;
 23 }
 24 struct sair{
 25     char name[110];
 26     int num;
 27 };
 28 sair p[110];
 29 bool cmp(sair x,sair y)
 30 {
 31     return strcmp(x.name,y.name)<0;
 32 }
 33 
 34 int main(){
 35     #ifndef ONLINE_JUDGE
 36      //   freopen("input.txt","r",stdin);
 37     #endif
 38     std::ios::sync_with_stdio(false);
 39     int k,m,t;
 40     scanf("%d%d%d%d",&k,&n,&m,&t);
 41     for (int i=0;i<n;i++)
 42         scanf("%s",name1[i]);
 43     getchar();
 44     memset(g,0,sizeof(g));
 45     for (int ii=0;ii<m;ii++)
 46     {
 47         gets(s);
 48         int len=strlen(s);
 49         int cnt=0,i=0;
 50         for (i=0;i<len&&s[i]!=':';i++)
 51             name2[ii][cnt++]=s[i];
 52         name2[ii][cnt++]=0;
 53         i+=2;
 54         while (i<len)
 55         {
 56             cnt=0;
 57             for (;s[i]!=' ';i++)
 58                 tname[cnt++]=s[i];
 59             tname[cnt]=0;
 60             int id=Find(tname);
 61             i++;
 62             int num=0;
 63             for (;s[i]!=0&&s[i]!=',';i++)
 64                 num=num*10+s[i]-'0';
 65             g[ii][id]=num;
 66             i+=2;
 67         }
 68     }
 69     memset(have,0,sizeof(have));
 70     memset(with,0,sizeof(with));
 71     for (int i=0;i<t;i++)
 72     {
 73         int tnum;
 74         scanf("%d",&tnum);
 75         scanf("%s",tname);
 76         int id=Find(tname);
 77         have[tnum][id]++;
 78         for (int j=0;j<m;j++)
 79         {
 80             bool tfind=true;
 81             for (int k=0;k<n;k++)
 82                 if (have[tnum][k]<g[j][k]) tfind=false;
 83             if (tfind)
 84             {
 85                 for (int k=0;k<n;k++)
 86                     have[tnum][k]-=g[j][k];
 87                 with[tnum][j]++;
 88             }
 89         }
 90     }
 91     for (int i=1;i<=k;i++)
 92     {
 93         int cnt=0;
 94         for (int j=0;j<n;j++)
 95             if (have[i][j]!=0)
 96             {
 97                 p[cnt].num=have[i][j];
 98                 strcpy(p[cnt++].name,name1[j]);
 99             }
100         for (int j=0;j<m;j++)
101             if (with[i][j]!=0)
102             {
103                 p[cnt].num=with[i][j];
104                 strcpy(p[cnt++].name,name2[j]);
105             }
106         sort(p,p+cnt,cmp);
107         printf("%d
",cnt);
108         for (int j=0;j<cnt;j++)
109             printf("%s %d
",p[j].name,p[j].num);
110     }
111 }

View Code

D

记忆化搜索的博弈，和前天的E题很像

题意：给个初始点，然后两个人轮流移动一段距离，当点和原点的距离大于d时失败。题目中的点可以移动到y=x的对称点这条件没用，因为一个人使用了这个条件，另一个人也可以使用它使点回到刚刚的位置

 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 eb emplace_back
 8 #define maxn 1000006
 9 #define rep(k,i,j) for(int k=i;k<j;k++)
10 typedef long long ll;
11 typedef unsigned long long ull;
12 
13 int d,n;
14 struct sair{
15     int x,y;
16 }a[25];
17 
18 int book[405][405];
19 
20 bool dist(int a,int b){
21     return (a-200)*(a-200)+(b-200)*(b-200) <= d*d;
22 }
23 
24 int dfs(int x,int y){
25     int xx,yy;
26     if(book[x][y]) return book[x][y];
27     for(int i=1;i<=n;i++){
28         xx=x+a[i].x;
29         yy=y+a[i].y;
30         if(dist(xx,yy)){
31             if(2==dfs(xx,yy)){
32                 return book[x][y]=1;
33             }
34         }
35     }
36     return book[x][y]=2;
37 }
38 
39 int main(){
40     #ifndef ONLINE_JUDGE
41      //   freopen("input.txt","r",stdin);
42     #endif
43     std::ios::sync_with_stdio(false);
44     int x,y;
45     cin>>x>>y>>n>>d;
46     for(int i=1;i<=n;i++){
47         cin>>a[i].x>>a[i].y;
48     }
49     if(dfs(x+200,y+200)==1) cout<<"Anton"<<endl;
50     else cout<<"Dasha"<<endl;
51 
52 }

View Code

E

题意:找出在一定区间内只出现过一次的最大的数

思路：建两个map，一个记录数的个数，另一个记录当前个数为1的值即可

 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 eb emplace_back
 8 #define maxn 1000006
 9 #define rep(k,i,j) for(int k=i;k<j;k++)
10 typedef long long ll;
11 typedef unsigned long long ull;
12 
13 int n,k;
14 int a[100005];
15 map<int,int>mp;
16 map<int,int>book;
17 map<int,int>::iterator it;
18 map<int,int>::reverse_iterator rit;
19 
20 int main(){
21     #ifndef ONLINE_JUDGE
22      //   freopen("input.txt","r",stdin);
23     #endif
24     std::ios::sync_with_stdio(false);
25     cin>>n>>k;
26     for(int i=1;i<=n;i++) cin>>a[i];
27     for(int i=1;i<=k;i++){
28         mp[a[i]]++;
29         if(mp[a[i]]==2){
30             book.erase(book.find(a[i]));
31         }
32         else if(mp[a[i]]==1){
33             book[a[i]]=1;
34         }
35     }
36     if(book.size()==0){
37         cout<<"Nothing"<<endl;
38     }
39     else{
40         rit=book.rbegin();
41         cout<<rit->first<<endl;
42     }
43     for(int i=k+1;i<=n;i++){
44         mp[a[i-k]]--;
45         if(mp[a[i-k]]==0) book.erase(book.find(a[i-k]));
46         else if(mp[a[i-k]]==1) book[a[i-k]]=1;
47         mp[a[i]]++;
48         if(mp[a[i]]==1) book[a[i]]=1;
49         else if(mp[a[i]]==2)book.erase(book.find(a[i]));
50         if(book.size()==0){
51             cout<<"Nothing"<<endl;
52         }
53         else{
54             rit=book.rbegin();
55             cout<<rit->first<<endl;
56         }
57     }
58 
59 
60 }

View Code