【Codeforces_Div2】Solutions
36412 ワード
転載は出典を明記してください.http://www.cnblogs.com/Delostik/archive/2013/02/25/2932004.html
3つの問題を作っても点数が落ちてしまいました.まったく理不尽です.TAT…でも、4つ目の問題は書かれていませんでした.残念です.紫色にならないようです.
【A.Lunch Rush】
http://www.codeforces.com/contest/276/problem/A
タイトル:ans=max｛f[i]-max(0,t[i]-k)｝を求めます.
View Code
【B.Little Girl and Game】
http://www.codeforces.com/contest/276/problem/B
与えられた文字列sは、二人が交互に操作し、その中から文字を一つずつ取っていきます.どちらかの方が持っていく前に文字列を回文列に再編成したら勝ちです.先手必勝かを問う.
回文列を構成する条件は、最大1文字が奇数回で、偶数文字が現れたら両側に対称に置くことです.現在奇数回の文字がある場合は、n個があります.
n=0、1の時に先手必勝状態となります.
n=2で先手必敗.
n=3の時、先手は持っていくことによって、奇数回の字母が現れて、相手に必ず負ける状態が現れさせます.
n=4の時に、まず手で数回の字母を持ってn'=5にしますが、相手もこの字母を持って、先に手をつないでn=4にしてもいいです.しかし、先手が数回の奇文字を持ってn'=3を使えば、相手は必勝状態になります.
つまり、これは水の問題です.
View Code
http://www.codeforces.com/contest/276/problem/C
いくつかの区間との照会がありますが、どうやって配列を再構築したら照会結果の和が最大になりますか?
明らかに検索回数が一番多い点は彼の権利を最大にしてもいいです.
方法1:プレフィックスと、これはブロガーが推奨する方法です.
View Code
View Code
http://www.codeforces.com/contest/276/problem/D
区間[l,r]でans=max｛a^b｝を見つけました.l≦a,b≦r.
先にlとrの最高の違いを探して、a≧bを設けて、それではaはきっと1 XXXXXで、bはきっと0 XXXXXで、区間[l,r]の内で一番良い解はa=100000で、b=01111111です. = =!
View Code
http://www.codeforces.com/contest/276/problem/E
タイトル:ツリーが与えられています.1:ノードvを中心に、vとの距離がdを超えないノードの権利値は＋wとなります.動作2は、あるノードの値を問い合わせる.
問題の中には、各ノードの度が2を超えないという話があります.つまり、ルートノードを取り除いたら、ツリーはいくつかのチェーンになります.各チェーンをそれぞれメンテナンスし、ツリーまたは線分ツリーを使用します.
しかし、多くのチェーンを更新する必要がある場合があり、このように動作するたびに、O(n)に完全に劣化するので、同じ深さのノードの増加値を維持するために追加のツリー配列が必要となる.
wyl 8899の説明に感謝します.また、下のコードはAが落ちていません.たぶん針が遅いから、配列シミュレーションに変えたらAができます.
View Code
3つの問題を作っても点数が落ちてしまいました.まったく理不尽です.TAT…でも、4つ目の問題は書かれていませんでした.残念です.紫色にならないようです.
【A.Lunch Rush】
http://www.codeforces.com/contest/276/problem/A
タイトル:ans=max｛f[i]-max(0,t[i]-k)｝を求めます.
View Code
1 #include <iostream>
2 using namespace std;
3
4 int n,k,ans=-2147483640,a,b;
5
6 int main(){
7 cin>>n>>k;
8 for(int i=1;i<=n;i++){
9 cin>>a>>b;
10 ans=max(ans,a-max(0,(b-k)));
11 }
12 cout<<ans<<endl;
13 return 0;
14 }【B.Little Girl and Game】
http://www.codeforces.com/contest/276/problem/B
与えられた文字列sは、二人が交互に操作し、その中から文字を一つずつ取っていきます.どちらかの方が持っていく前に文字列を回文列に再編成したら勝ちです.先手必勝かを問う.
回文列を構成する条件は、最大1文字が奇数回で、偶数文字が現れたら両側に対称に置くことです.現在奇数回の文字がある場合は、n個があります.
n=0、1の時に先手必勝状態となります.
n=2で先手必敗.
n=3の時、先手は持っていくことによって、奇数回の字母が現れて、相手に必ず負ける状態が現れさせます.
n=4の時に、まず手で数回の字母を持ってn'=5にしますが、相手もこの字母を持って、先に手をつないでn=4にしてもいいです.しかし、先手が数回の奇文字を持ってn'=3を使えば、相手は必勝状態になります.
つまり、これは水の問題です.
View Code
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 string s;
6 int cnt,a[30];
7
8 int main(){
9 cin>>s;
10 int len=s.length();
11 for(int i=0;i<len;i++)
12 a[s[i]-'a']++;
13 for(int i=0;i<26;i++)
14 if(a[i]&1) cnt++;
15 if(!cnt || cnt&1) cout<<"First"<<endl;
16 else cout<<"Second"<<endl;
17 return 0;
18 }http://www.codeforces.com/contest/276/problem/C
いくつかの区間との照会がありますが、どうやって配列を再構築したら照会結果の和が最大になりますか?
明らかに検索回数が一番多い点は彼の権利を最大にしてもいいです.
方法1:プレフィックスと、これはブロガーが推奨する方法です.
View Code
1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4
5 int n,q,l,r;
6 long long a[200010],t[200010],ans;
7
8 int main(){
9 cin>>n>>q;
10 for(int i=0;i<n;i++)
11 cin>>a[i];
12 sort(a,a+n);
13 for(int i=0;i<q;i++){
14 cin>>l>>r;
15 t[l-1]++,t[r]--;
16 }
17 for(int i=1;i<n;i++)
18 t[i]+=t[i-1];
19 sort(t,t+n);
20 for(int i=0;i<n;i++)
21 ans+=a[i]*t[i];
22 cout<<ans;
23 return 0;
24 }View Code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <algorithm>
6 #define lch(x) x<<1
7 #define rch(x) (x<<1)+1
8 using namespace std;
9
10 int n,q,l,r,c,a[200010],b[200010];
11 char sym[2];
12 long long ans;
13
14 struct T_node{
15 int sum,add;
16 int l,r,size;
17 }tree[800010];
18
19 void build(int v,int l,int r){
20 tree[v].l=l,tree[v].r=r;
21 if(l==r) tree[v].size=1;
22 else{
23 build(lch(v),l,(l+r)>>1);
24 build(rch(v),((l+r)>>1)+1,r);
25 tree[v].sum=tree[lch(v)].sum+tree[rch(v)].sum;
26 tree[v].size=tree[lch(v)].size+tree[rch(v)].size;
27 }
28 }
29
30 void pushdown(int v){
31 if(tree[v].l!=tree[v].r){
32 tree[lch(v)].add+=tree[v].add,tree[lch(v)].sum+=tree[v].add*tree[lch(v)].size;
33 tree[rch(v)].add+=tree[v].add,tree[rch(v)].sum+=tree[v].add*tree[rch(v)].size;
34 }
35 tree[v].add=0;
36 }
37
38 void modify(int v,int l,int r){
39 pushdown(v);
40 if(l==tree[v].l && r==tree[v].r) tree[v].add+=1,tree[v].sum+=tree[v].size;
41 else{
42 int mid=(tree[v].l+tree[v].r)>>1;
43 if(r<=mid) modify(lch(v),l,r);
44 else if(l>mid) modify(rch(v),l,r);
45 else{
46 modify(lch(v),l,mid);
47 modify(rch(v),mid+1,r);
48 }
49 tree[v].sum=tree[lch(v)].sum+tree[rch(v)].sum;
50 }
51 }
52
53 int query(int v,int x){
54 pushdown(v);
55 if(x==tree[v].l && x==tree[v].r) return tree[v].sum;
56 int mid=(tree[v].l+tree[v].r)>>1;
57 if(x<=mid) return query(lch(v),x);
58 else if(x>mid) return query(rch(v),x);
59 }
60
61 int main(){
62 cin>>n>>q;
63 for(int i=1;i<=n;i++)
64 cin>>a[i];
65 sort(a+1,a+1+n);
66 build(1,1,n);
67 for(int t=1;t<=q;t++){
68 cin>>l>>r;
69 modify(1,l,r);
70 }
71 for(int i=1;i<=n;i++)
72 b[i]=query(1,i);
73 sort(b+1,b+1+n);
74 for(int i=1;i<=n;i++){
75 ans+=(long long)a[i]*(long long)b[i];
76 }
77 cout<<ans<<endl;
78 return 0;
79 }http://www.codeforces.com/contest/276/problem/D
区間[l,r]でans=max｛a^b｝を見つけました.l≦a,b≦r.
先にlとrの最高の違いを探して、a≧bを設けて、それではaはきっと1 XXXXXで、bはきっと0 XXXXXで、区間[l,r]の内で一番良い解はa=100000で、b=01111111です. = =!
View Code
1 #include <iostream>
2 using namespace std;
3
4 long long l,r,i;
5
6 int main(){
7 cin>>l>>r;
8 for(i=63;i>=0;i--)
9 if((l^r)&(1LL<<i)) break;
10 cout<<(1LL<<(i+1))-1;
11 return 0;
12 }http://www.codeforces.com/contest/276/problem/E
タイトル:ツリーが与えられています.1:ノードvを中心に、vとの距離がdを超えないノードの権利値は＋wとなります.動作2は、あるノードの値を問い合わせる.
問題の中には、各ノードの度が2を超えないという話があります.つまり、ルートノードを取り除いたら、ツリーはいくつかのチェーンになります.各チェーンをそれぞれメンテナンスし、ツリーまたは線分ツリーを使用します.
しかし、多くのチェーンを更新する必要がある場合があり、このように動作するたびに、O(n)に完全に劣化するので、同じ深さのノードの増加値を維持するために追加のツリー配列が必要となる.
wyl 8899の説明に感謝します.また、下のコードはAが落ちていません.たぶん針が遅いから、配列シミュレーションに変えたらAができます.
View Code
1 #include <cstdio>
2 #include <vector>
3 #define mm 200010
4 #define mn 100010
5 #define lowbit(x) ((x)&(-x))
6 using namespace std;
7
8 struct EDGE{
9 int pnt;
10 EDGE *pre;
11 EDGE(){}
12 EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){}
13 }Edge[mm],*SP=Edge,*edge[mn];
14
15 inline void addedge(int a,int b){
16 edge[a]=new(++SP)EDGE(b,edge[a]);
17 }
18
19 int n,q,x,y,v,w,d,tot,opt,root,bng[mn],pos[mn],len[mn],fa[mn],son[mn];
20 vector<int> tree[mn];
21
22 void add(vector<int> &c,int x,int key){
23 for(;x<c.size();x+=lowbit(x)) c[x]+=key;
24 }
25
26 int get(vector<int> c,int x){
27 int res=0;
28 for(;x>0;x-=lowbit(x)) res+=c[x];
29 return res;
30 }
31
32 void dfs(int x,int father){
33 fa[x]=father;
34 for(EDGE *j=edge[x];j;j=j->pre)
35 if(j->pnt!=father){
36 son[x]=j->pnt;
37 dfs(j->pnt,x);
38 }
39 }
40
41 void build_tree(){
42 for(EDGE *j=edge[1];j;j=j->pre,tot++){
43 dfs(j->pnt,1);
44 for(int i=j->pnt;i;i=son[i])
45 bng[i]=tot,pos[i]=++len[tot];
46 tree[tot].resize(len[tot]+1);
47 }
48 tree[tot].resize(n+1);
49 }
50
51 int main(){
52 scanf("%d%d",&n,&q);
53 for(int i=1;i<n;i++){
54 scanf("%d%d",&x,&y);
55 addedge(x,y),addedge(y,x);
56 }
57 build_tree();
58 while(q--){
59 scanf("%d",&opt);
60 if(opt){
61 scanf("%d",&v);
62 if(v==1) printf("%d
",root);
63 else printf("%d
",get(tree[bng[v]],pos[v])+get(tree[tot],pos[v]));
64 }else{
65 scanf("%d%d%d",&v,&w,&d);
66 if(v==1){
67 root+=w;
68 add(tree[tot],1,w);
69 add(tree[tot],d+1,-w);
70 }else{
71 add(tree[bng[v]],max(pos[v]-d,1),w); //
72 add(tree[bng[v]],pos[v]+d+1,-w); //
73 if(d>=pos[v]){
74 root+=w;
75 if(d>pos[v]){
76 add(tree[tot],1,w);add(tree[tot],d-pos[v]+1,-w);
77 add(tree[bng[v]],1,-w);add(tree[bng[v]],d-pos[v]+1,w);
78 }
79 }
80 }
81 }
82 }
83 return 0;
84 }