Codeforces Beta Round #63 (Div. 2)
http://codeforces.com/contest/69
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\n",cnt);
108 for (int j=0;j<cnt;j++)
109 printf("%s %d\n",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