It feels that you do not do well for CF’s DIV2CD difficulty, so open a pit to practice.
6/20
1.Codeforces 1006D. Two Strings Swaps
Discuss strong classification according to the rules of the question.
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 #include <queue> 7 #include <map> 8 #define ll long long 9 #define out(a) printf("%d",a) 10 #define writeln printf("\n") 11 const int N=1e5+50; 12 using namespace std; 13 int n; 14 char s1[N],s2[N]; 15 int ans; 16 int read() 17 { 18 int s=0,t=1; char c; 19 while (c<'0'||c>'9'){ if (c=='-') t=-1; c=getchar();} 20 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 21 return s*t; 22 } 23 ll readl() 24 { 25 ll s=0,t=1; char c; 26 while (c<'0'||c>'9'){ if (c=='-') t=-1; c=getchar();} 27 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 28 return s*t; 29 } 30 int main() 31 { 32 n=read(); 33 scanf("%s",s1+1); scanf("%s",s2+1); 34 if (n&1){ 35 if (s1[n/2+1]!=s2[n/2+1]) ans++; 36 } 37 for (int i=1;i<=n/2;i++){ 38 if (s1[i]==s1[n-i+1]&&s2[i]==s2[n-i+1]) continue; 39 if (s1[i]==s2[i]&&s1[n-i+1]==s2[n-i+1]) continue; 40 if (s1[i]==s2[n-i+1]&&s2[i]==s1[n-i+1]) continue; 41 if (s1[i]==s1[n-i+1]&&s2[i]!=s2[n-i+1]) { 42 ans+=2; 43 if (s1[i]==s2[i]||s1[n-i+1]==s2[n-i+1]) ans--; continue; 44 } 45 if (s2[i]==s2[n-i+1]&&s1[i]!=s1[n-i+1]) { 46 ans++; continue; 47 } 48 if (s1[i]==s2[i]&&s1[n-i+1]!=s2[n-i+1]) { 49 ans++; continue; 50 } 51 if (s1[i]!=s2[i]&&s1[n-i+1]==s2[n-i+1]) { 52 ans++; continue; 53 } 54 if (s1[i]==s2[n-i+1]&&s2[i]!=s1[n-i+1]) { 55 ans++; continue; 56 } 57 if (s2[i]==s1[n-i+1]&&s1[i]!=s2[n-i+1]) { 58 ans++; continue; 59 } 60 ans+=2; 61 } 62 out(ans); 63 return 0; 64 } 65 66
View Code
2.Codeforces 1005C. Summarize to the Power of Two
n numbers, for a number a [i], if there is no a [j] (i! = J), the power secondary side of A [i]+a [j] is deleted How many numbers.
When you read it, you throw all the numbers into the Map. For a number of power seconds of a number of enumerated 2 and subtract this number to get the NUM, check whether the NUM exists in the map. It should be noted when num == A [a [a [a [a [a [a [a [a [a [a [a [a [a [a When i], it is necessary to determine whether the number of A [i] appears greater than 1.
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 #include <queue> 7 #include <map> 8 #define ll long long 9 #define out(a) printf("%d",a) 10 #define writeln printf("\n") 11 const int N=1e5+20050; 12 using namespace std; 13 map<int,int>cnt; 14 int n; 15 int a[N]; 16 int num,ans; 17 bool flag; 18 int read() 19 { 20 int s=0,t=1; char c; 21 while (c<'0'||c>'9'){ if (c=='-') t=-1; c=getchar();} 22 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 23 return s*t; 24 } 25 ll readl() 26 { 27 ll s=0,t=1; char c; 28 while (c<'0'||c>'9'){ if (c=='-') t=-1; c=getchar();} 29 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 30 return s*t; 31 } 32 int main() 33 { 34 n=read(); 35 for (int i=1;i<=n;i++) 36 a[i]=read(),cnt[a[i]]++; 37 for (int i=1;i<=n;i++){ 38 flag=false; 39 for (int j=30;j>=0;j--){ 40 num=1<<j; 41 if (cnt.count(num-a[i])>0) { 42 flag=true; 43 if ((a[i]<<1)==num) { 44 if (cnt[a[i]]==1) ans++; 45 } 46 break; 47 } 48 } 49 if (flag) continue; 50 ans++; 51 } 52 out(ans); 53 return 0; 54 } 55
View Code
3.Codeforces 1005E1. Median on Segments (Permutations Edition)
Thinking good questions, qaq
Give a 1 to N arrangement and a number K, and how many areas of the medium number of K. (When the size M is the number of mi, the median number is M/2)
Classic routine is to see the equal to K as 0, less than K as -1, greater than K as 1, and then calculate the prefix and.
So you only need to calculate how many intervals and 0 or 1 is 1.
and for 0 are well understood, so why is it calculated for 1?
Prove a wave: Since the number of K must include the number of K, there must be 0 in the interval prefix and the array. When the size of the interval is a odd number, the interval is equal to the number of 0 and 1. When the interval size is even, because it contains one 0, the number of -1 and 1 is not equal, that is, it is not possible to be 0, because the median number is taken downwards, and the number of 1 is more than -1 quantity. 1, that is, 1.
It won’t be here. Essence N2 complexity is explosive.
Then I still read the problem. Essence
Because the interval contains K, we may wish to consider the interval as the form of A+K+B (of course A, B can be an empty set), pre -processed the prefixes and array of the right interval B and K in the Map, and then the beauty Take the number of map queries between the left interval and the number of prefixes and the number of numbers or a 1.
Answer will explode int, so remember to open long long.
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 #include <queue> 7 #include <map> 8 #define ll long long 9 #define out(a) printf("%lld",a) 10 #define writeln printf("\n") 11 const int N=2e5+50; 12 using namespace std; 13 map<int,int>cnt; 14 int n,k; 15 int a[N],b[N],sum[N]; 16 int num; 17 ll ans; 18 int read() 19 { 20 int s=0,t=1; char c; 21 while (c<'0'||c>'9'){ if (c=='-') t=-1; c=getchar();} 22 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 23 return s*t; 24 } 25 ll readl() 26 { 27 ll s=0,t=1; char c; 28 while (c<'0'||c>'9'){ if (c=='-') t=-1; c=getchar();} 29 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 30 return s*t; 31 } 32 int main() 33 { 34 n=read(),k=read(); 35 for (int i=1;i<=n;i++){ 36 a[i]=read(); 37 if (a[i]>k) b[i]=1; 38 else if (a[i]<k) b[i]=-1; 39 if (a[i]==k) num=i; 40 sum[i]=sum[i-1]+b[i]; 41 if (i>=num&&num) cnt[sum[i]]++; 42 } 43 for (int i=0;i<=num-1;i++) 44 ans+=cnt[sum[i]]+cnt[sum[i]+1]; 45 out(ans); 46 return 0; 47 } 48
View Code
4.Codeforces 996D. Suit and Tie
One to n, there are two numbers. Seeking the number of adjacent positions, the number of numbers with the same numbers is adjacent.
Considering that two of the same number adjacent to at least the absolute value of their poor position is reduced. This will not change the order of other numbers if it is directly exchanged, and it will even make the situation of the original number adjacent. The answer directly will not increase or even decrease.
So scan the exchange position statistics and answer.
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 #include <queue> 7 #include <map> 8 #define ll long long 9 #define out(a) printf("%d ",a) 10 #define writeln printf("\n") 11 const int N=1e5+50; 12 using namespace std; 13 int n,num,ans=0; 14 int a[N],cnt[N]; 15 int read() 16 { 17 int s=0,t=1; char c; 18 while (c<'0'||c>'9'){ if (c=='-') t=-1; c=getchar();} 19 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 20 return s*t; 21 } 22 ll readl() 23 { 24 ll s=0,t=1; char c; 25 while (c<'0'||c>'9'){ if (c=='-') t=-1; c=getchar();} 26 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 27 return s*t; 28 } 29 int main() 30 { 31 n=read(); 32 for (int i=1;i<=2*n;i++) 33 a[i]=read(); 34 for (int i=1;i<=2*n;i+=2){ 35 if (a[i]!=a[i+1]){ 36 for (int j=i+1;j<=2*n;j++) 37 if (a[j]==a[i]){ 38 num=j; break; 39 } 40 ans+=num-i-1; 41 for (int j=num;j>i+1;j--) 42 swap(a[j],a[j-1]); 43 } 44 } 45 out(ans); 46 return 0; 47 }
View Code
How many L is consisting of 0.
If two vertical 0 0 appear in the same column, greedy to find to the left and then to the right, the statistical answer.
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 #include <queue> 7 #include <map> 8 #define ll long long 9 #define out(a) printf("%d ",a) 10 #define writeln printf("\n") 11 const int N=1e5+50; 12 using namespace std; 13 int n,len; 14 int ans; 15 char s[2][N]; 16 bool flag; 17 int read() 18 { 19 int s=0,t=1; char c; 20 while (c<'0'||c>'9'){ if (c=='-') t=-1; c=getchar();} 21 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 22 return s*t; 23 } 24 ll readl() 25 { 26 ll s=0,t=1; char c; 27 while (c<'0'||c>'9'){ if (c=='-') t=-1; c=getchar();} 28 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 29 return s*t; 30 } 31 int main() 32 { 33 scanf("%s",s[0]); 34 scanf("%s",s[1]); 35 len=strlen(s[0]); 36 for (int i=0;i<len;i++) 37 if (s[0][i]=='0'&&s[1][i]=='0'){ 38 flag=false; 39 for (int j=0;j<2;j++){ 40 if (s[j][i-1]=='0') { 41 ans++,s[j][i-1]='X',flag=true; 42 break; 43 } 44 } 45 if (flag) s[0][i]=s[1][i]='X'; 46 else { 47 for (int j=0;j<2;j++){ 48 if (s[j][i+1]=='0') { 49 ans++,s[j][i+1]='X',flag=true; 50 break; 51 } 52 } 53 if (flag) s[0][i]=s[1][i]='X'; 54 } 55 } 56 out(ans); 57 return 0; 58 }
View Code
6.Codeforces 1015D. Walking Between Houses
There are 1 ~ N house, and the number of step steps is just a solution for S.
The greedy question with a slightly thinking is probably the first step, and then the rest.
Details are not clear, look at the code ==
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstring> 6 #include <queue> 7 #include <map> 8 #define ll long long 9 #define out(a) printf("%lld ",a) 10 #define writeln printf("\n") 11 const int N=1e5+50; 12 using namespace std; 13 ll n,m,k,x,p,num,now,a,b,c; 14 ll ans=0; 15 ll s; 16 int read() 17 { 18 int s=0,t=1; char c; 19 while (c<'0'||c>'9'){ if (c=='-') t=-1; c=getchar();} 20 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 21 return s*t; 22 } 23 ll readl() 24 { 25 ll s=0,t=1; char c; 26 while (c<'0'||c>'9'){ if (c=='-') t=-1; c=getchar();} 27 while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();} 28 return s*t; 29 } 30 int main() 31 { 32 n=readl(),k=readl(),s=readl(); 33 if (k==s) { 34 puts("YES"); 35 for (int i=1;i<=k;i++) 36 if (i&1) cout<<2<<' '; 37 else cout<<1<<' '; 38 return 0; 39 } 40 if (k>s||(n-1)*k<s){ 41 puts("NO"); return 0; 42 } 43 else { 44 puts("YES"); now=x=1; 45 a=s/(n-1); b=s-a*(n-1); c=k-a;//The remaining C round can be left, and there is step B to go 46 if (b>=c) { 47 for (int i=1;i<=a;i++) 48 if (i&1) out(n),now=n,x=-1; 49 else out(1),now=1,x=1; 50 if (b!=c) { 51 c--; now+=(b-c)*x; out(now); 52 } 53 for (int i=1;i<=c;i++) 54 if (now<n) { 55 if (i&1) out(now+1); 56 else out(now); 57 } 58 else if (now==n){ 59 if (i&1) out(now-1); 60 else out(now); 61 } 62 } 63 else { 64 while (b<c){ 65 a--; b+=n-1; 66 c++; 67 } 68 for (int i=1;i<=a;i++) 69 if (i&1) out(n),now=n,x=-1; 70 else out(1),now=1,x=1; 71 if (b!=c) { 72 c--; now+=(b-c)*x; out(now);} 73 for (int i=1;i<=c;i++) 74 if (now<n) { 75 if (i&1) out(now+1); 76 else out(now); 77 } 78 else if (now==n){ 79 if (i&1) out(now-1); 80 else out(now); 81 } 82 } 83 } 84 return 0; 85 }
View Code
Reprinted: https://www.cnblogs.com/kaleidoscope233/p/9377300.html