A：水题，找到不小于n的能够被4整除的最小的数。
假设n不能被4整除，那么n+1,n+2,n+3之中一定存在一个数能够被4整除。所以直接枚举即可。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 bool check(int n){ 6 int sum=0; 7 while(n){ 8 sum+=n%10; 9 n/=10; 10 } 11 if(sum%4==0) return true; 12 return false; 13 } 14 int main() 15 { 16 int n; 17 cin>>n; 18 while(!check(n)){ 19 n++; 20 } 21 cout<<n; 22 return 0; 23 }
B：给定一个双端队列，插入一些数（保证无重复），同时会询问其中某些数到两端的最短距离。
因为无重复，所以我们可以直接用hash表记录值对应的位置，然后在记录左端和右端的位置，即可在O（1）的时间内获得某个数到两端的最短的距离。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <unordered_map> 5 6 using namespace std; 7 const int N=2e5+10; 8 int hh=0,tt=-1; 9 unordered_map<int,int> mp;//值到位置的映射 10 int main() 11 { 12 int t; 13 cin>>t; 14 while(t--){ 15 char c; 16 int x; 17 cin>>c>>x; 18 if(c==‘L‘) 19 mp[x]=--hh; 20 else if(c==‘R‘) 21 mp[x]=++tt; 22 else if(c==‘?‘){ 23 int pos=mp[x]; 24 cout<<min(pos-hh,tt-pos)<<endl; 25 } 26 } 27 return 0; 28 }
C：给定一个只包含1和2的序列，能够选择任意一段连续序列反转，问最长的单调不减序列的长度为多少。
解法1：分析之后可以发现最终的答案一定是由1111122222211111122222这种子序列得来的（其中任何一段均可缺失）
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 const int N = 1e6+10; 5 int q[N]; 6 using namespace std; 7 int main() 8 { 9 int n; 10 cin>>n; 11 for(int i=0;i<n;i++) cin>>q[i]; 12 int s1=0,s2=0,s3=0,s4=0;//s1表示1111的长度,s2表示11111122222的长度,s3表示11111222221111的长度,s4表示1111222211112222的长度。 13 for(int i=0;i<n;i++){ 14 if(q[i]==1){ 15 s1++; 16 s3=max(s2+1,s3+1); 17 }else if(q[i]==2){ 18 s2=max(s1+1,s2+1); 19 s4=max(s3+1,s4+1); 20 } 21 } 22 cout<<max(max(s1,s2),max(s3,s4)); 23 return 0; 24 }
解法2：可以将最终的答案拆成两个单调不减子序列，对于其中的一个点 i ，也就是求0~i和i+1~n-1的最长单调不减子序列。
因为序列中只有1和2，所以最长单调不减子序列可用O（n）的时间求出。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int N = 1e6+10; 6 int n,a[N],res; 7 int pre[N],ne[N]; 8 int cnt[3]; 9 int main() 10 { 11 //求形如11111 222222 1111111 2222222的最长长度 12 cin>>n; 13 for(int i=0;i<n;i++){ 14 cin>>a[i]; 15 } 16 cnt[1]=0,cnt[2]=0; 17 for(int i=0;i<n;i++){//pre为0~i的最长的单调不减子序列 18 if(a[i]==1){ 19 cnt[1]++; 20 pre[i]=cnt[1]; 21 }else if(a[i]==2){ 22 cnt[2]=max(cnt[1],cnt[2])+1; 23 pre[i]=cnt[2]; 24 } 25 } 26 27 cnt[1]=0,cnt[2]=0; 28 for(int i=n-1;i>=0;i--){//ne为i~n-1的最长的单调不减子序列 29 if(a[i]==1){ 30 cnt[1]=max(cnt[1],cnt[2])+1; 31 ne[i]=cnt[1]; 32 }else if(a[i]==2){ 33 cnt[2]++; 34 ne[i]=cnt[2]; 35 } 36 } 37 for(int i=0;i<n;i++) res=max(res,pre[i]+ne[i+1]); 38 cout<<res; 39 return 0; 40 }