Codeforces Round_(Div.2)
29064 ワード
試合ページ:http://codeforces.com/contest/486
公式テーマ:http://codeforces.com/blog/entry/14678
A.Calculating Function
3分目のACは、この手の速さも合わせました.ページは1分以上こすってから磨きましたが.
B.OR in Matrix
m行n列の01マトリクスAについては、同じ規格の01マトリクスBを構成し、i行j列目に対しては、A行列のi行目またはj列目に数字1が存在すると、Bにおいてもその位置は1となり、現在はBがAを求める.
依然として手速問題であり、明らかにBに0があるとAの列は1があり得ないので、最初はAを全部1に設定し、その後Bのi行jの列が0なら、Aのi行目とj列目の要素を全部1に設定する.最後に求めたAに対してもう一度チェックし、合法的であればYESを出力し、不正にNOを出力します.
C.Palindrome Trans formation
小さな文字列を与え、もう一つのポインタを与え、最初はp番目の要素(pへの入力)を指します.そして左右の操作を規定します.それぞれのポインタを左に1つ移動し、右に1つ移動します.最初の要素は左に最後の要素で、最後の要素は右に1つ目の要素です.上下の操作を規定して、それぞれその位置のアルファベットをアルファベットの中の前の方または次の方に変えて、アルファベットを規定するのも循環です.つまりAの前の方がZで、Zの次の方がAです.すみません、少なくともどれぐらいのステップが必要ですか?この小文字を回文列に変えることができますか?
欲張り+分類討論
針の操作手順をシミュレートする必要はありません.pがn/2以下(pは文字列の左半分)であると仮定して、st~edを修正が必要な範囲(つまり、1~st-1とed~n/2はすでに右半分の対応位置と等しい)に設定します.
ポインタpがst~edの範囲内にない場合、まずpからst~edの範囲に移動し、もう一つの修正が必要です.(私達が言っている修正は、pの位置の文字を文字列の右半分の対応する位置の文字に修正することです.これは、ポインタを右半分の修正文字に移動するよりも優れています.)価格=文字の価格を変更します.(タイトルでいう上下の操作回数)＋ed-st＋pをstまたはedに移動する最小の価格です.
もしポインタpがst~edの範囲内にあるならば、私達がst~pの部分を修正したら、必ずp+1~edの部分を振り向けて修正します.明らかに先にpをstまたはedに移動することができます.価格の計算方法は明らかに上と同じで、価格=文字の価格(タイトルの上下操作回数)＋ed-st＋pをstまたはedに移動させる最小の代価です.
D.Valid Sets
まだ更新されていません
E.LIS of Sequence
まだ更新されていません
公式テーマ:http://codeforces.com/blog/entry/14678
A.Calculating Function
3分目のACは、この手の速さも合わせました.ページは1分以上こすってから磨きましたが.
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<stack>
9 #include<vector>
10 #include<queue>
11 #include<string>
12 #include<sstream>
13 #define eps 0.000001
14 #define ALL(x) x.begin(),x.end()
15 #define INS(x) inserter(x,x.begin())
16 using namespace std;
17 typedef long long LL;
18 int i,j,k,n,m,x,y,T,ans,big,cas;
19 bool flag;
20 int main()
21 {
22 LL n,ans;
23 scanf("%I64d",&n);
24 ans=n/2;
25 if (n%2) ans-=n;
26 printf("%I64d
",ans);
27 return 0;
28 }B.OR in Matrix
m行n列の01マトリクスAについては、同じ規格の01マトリクスBを構成し、i行j列目に対しては、A行列のi行目またはj列目に数字1が存在すると、Bにおいてもその位置は1となり、現在はBがAを求める.
依然として手速問題であり、明らかにBに0があるとAの列は1があり得ないので、最初はAを全部1に設定し、その後Bのi行jの列が0なら、Aのi行目とj列目の要素を全部1に設定する.最後に求めたAに対してもう一度チェックし、合法的であればYESを出力し、不正にNOを出力します.
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<stack>
9 #include<vector>
10 #include<queue>
11 #include<string>
12 #include<sstream>
13 #define eps 0.000001
14 #define ALL(x) x.begin(),x.end()
15 #define INS(x) inserter(x,x.begin())
16 using namespace std;
17 typedef long long LL;
18 int i,j,k,n,m,x,y,T,ans,big,cas,b[105][105],a[105][105];
19 bool flag;
20 int main()
21 {
22 scanf("%d%d",&n,&m);
23 memset(b,-1,sizeof(b));// memset ， -1， -1 1
24 for (i=1;i<=n;i++)
25 {
26 for (j=1;j<=m;j++)
27 {
28 scanf("%d",&a[i][j]);
29 if (a[i][j]==0)
30 {
31 for (k=1;k<=n;k++)
32 {
33 b[k][j]=0;
34 }
35 for (k=1;k<=m;k++)
36 {
37 b[i][k]=0;
38 }
39 }
40 }
41 }
42 for (i=1;i<=n;i++)
43 {
44 for (j=1;j<=m;j++)
45 {
46 if (a[i][j])
47 {
48 flag=false;
49 for (k=1;k<=n;k++)
50 {
51 if (b[k][j]!=0)
52 {
53 flag=true;
54 break;
55 }
56 }
57 if (!flag)
58 {
59 for (k=1;k<=m;k++)
60 {
61 if (b[i][k]!=0)
62 {
63 flag=true;
64 break;
65 }
66 }
67 }
68 if (!flag)
69 {
70 printf("NO
");
71 return 0;
72 }
73 }
74 }
75 }
76
77 printf("YES
");
78 for (i=1;i<=n;i++)
79 {
80 for (j=1;j<m;j++)
81 {
82 printf("%d ",-b[i][j]);
83 }
84 printf("%d
",-b[i][m]);
85 }
86 return 0;
87 }C.Palindrome Trans formation
小さな文字列を与え、もう一つのポインタを与え、最初はp番目の要素(pへの入力)を指します.そして左右の操作を規定します.それぞれのポインタを左に1つ移動し、右に1つ移動します.最初の要素は左に最後の要素で、最後の要素は右に1つ目の要素です.上下の操作を規定して、それぞれその位置のアルファベットをアルファベットの中の前の方または次の方に変えて、アルファベットを規定するのも循環です.つまりAの前の方がZで、Zの次の方がAです.すみません、少なくともどれぐらいのステップが必要ですか?この小文字を回文列に変えることができますか?
欲張り+分類討論
針の操作手順をシミュレートする必要はありません.pがn/2以下(pは文字列の左半分)であると仮定して、st~edを修正が必要な範囲(つまり、1~st-1とed~n/2はすでに右半分の対応位置と等しい)に設定します.
ポインタpがst~edの範囲内にない場合、まずpからst~edの範囲に移動し、もう一つの修正が必要です.(私達が言っている修正は、pの位置の文字を文字列の右半分の対応する位置の文字に修正することです.これは、ポインタを右半分の修正文字に移動するよりも優れています.)価格=文字の価格を変更します.(タイトルでいう上下の操作回数)＋ed-st＋pをstまたはedに移動する最小の価格です.
もしポインタpがst~edの範囲内にあるならば、私達がst~pの部分を修正したら、必ずp+1~edの部分を振り向けて修正します.明らかに先にpをstまたはedに移動することができます.価格の計算方法は明らかに上と同じで、価格=文字の価格(タイトルの上下操作回数)＋ed-st＋pをstまたはedに移動させる最小の代価です.
1 /*MADE BY zhyfzy~~~~~~*/
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<iostream>
6 #include<algorithm>
7 #include<set>
8 #include<map>
9 #include<stack>
10 #include<vector>
11 #include<queue>
12 #include<string>
13 #include<sstream>
14 #define eps 0.000001
15 #define ALL(x) x.begin(),x.end()
16 #define INS(x) inserter(x,x.begin())
17 using namespace std;
18 typedef long long LL;
19 int i,j,k,n,m,x,y,T,ans,big,cas,p,st,ed,st2,ed2;
20 bool flag;
21 char s[100005];
22 int main()
23 {
24 scanf("%d%d",&n,&p);
25 scanf("%s",s+1);
26 if (n==1)
27 {
28 printf("0
");
29 return 0;
30 }
31 m=(n+1)/2;
32 ans=0;
33 st=1; ed=m;
34 for (i=1;i<=m;i++)
35 if (s[i]==s[n-i+1]) st++;
36 else break;
37 for (i=m;i>=1;i--)
38 if (s[i]==s[n-i+1]) ed--;
39 else break;
40
41 if (st>m)
42 {
43 printf("0
");
44 return 0;
45 }
46
47 for (i=1;i<=m;i++)
48 {
49 j=n-i+1;
50 ans+=min(abs((int)s[i]-(int)s[j]),26-abs((int)s[i]-(int)s[j]));
51 }
52 //cout<<ans<<endl;
53 st2=n-ed+1;
54 ed2=n-st+1;
55 if (n%2)
56 {
57 ans+=ed-st;
58 if (p>m)
59 {
60 if (p>=st2&&p<=ed2) ans+=min(p-st2,ed2-p);
61 if (p<st2) ans+=st2-p;
62 if (p>ed2) ans+=p-ed2;
63 }
64 else
65 if (p<m)
66 {
67 if (p>=st&&p<=ed) ans+=min(p-st,ed-p);
68 if (p<st) ans+=st-p;
69 if (p>ed) ans+=p-ed;
70 }else
71 if (p==m)
72 {
73 ans+=m-ed2;
74 }
75 printf("%d
",ans);
76 }else
77 {
78 ans+=ed-st;
79 if (p>m)
80 {
81 if (p>=st2&&p<=ed2) ans+=min(p-st2,ed2-p);
82 if (p<st2) ans+=st2-p;
83 if (p>ed2) ans+=p-ed2;
84 }else
85 {
86 if (p>=st&&p<=ed) ans+=min(p-st,ed-p);
87 if (p<st) ans+=st-p;
88 if (p>ed) ans+=p-ed;
89 }
90 printf("%d
",ans);
91 }
92
93 return 0;
94 }D.Valid Sets
まだ更新されていません
E.LIS of Sequence
まだ更新されていません