A 题:
我们发现如果任意两个奇偶性不同都不行, 因为只要奇偶相同, 都能够通过加 2 操作得到
- #include<iostream>
- #include<queue>
- #include<map>
- #include<vector>
- #include<cstdio>
- #include<algorithm>
- #include<stack>
- #include<cstring>
- using namespace std;
- typedef long long ll;
- const int N=1100;
- int main(){
- int t;
- cin>>t;
- while(t--){
- int n;
- cin>>n;
- int i;
- int cnt1=0;
- int cnt2=0;
- for(i=1;i<=n;i++){
- int x;
- cin>>x;
- if(x%2)
- cnt1++;
- else
- cnt2++;
- }
- if(cnt1&&cnt2)
- cout<<"NO"<<endl;
- else
- cout<<"YES"<<endl;
- }
- return 0;
- }
- View Code
B 题
只需要找到两个一样的数并且不能是相邻的就可以, 因为 3 个永远是最少的
- #include<iostream>
- #include<queue>
- #include<map>
- #include<vector>
- #include<cstdio>
- #include<algorithm>
- #include<stack>
- #include<cstring>
- using namespace std;
- typedef long long ll;
- const int N=1e5+10;
- int a[N];
- map<int,int> m1;
- int main(){
- int t;
- cin>>t;
- while(t--){
- m1.clear();
- int n;
- cin>>n;
- int i;
- for(i=1;i<=n;i++){
- scanf("%d",&a[i]);
- }
- int flag=1;
- for(i=1;i<=n;i++){
- if(!m1[a[i]]){
- m1[a[i]]=i;
- }
- else{
- if(i-m1[a[i]]>=2){
- flag=0;
- }
- }
- }
- if(!flag)
- cout<<"YES"<<endl;
- else
- cout<<"NO"<<endl;
- }
- return 0;
- }
- View Code
C 题
显然的二分性质, 我们只需要考虑 r 之间的距离是否满足题意就行, 因为 l 是没用的, 跳到 l 还得跳到 r
- #include<iostream>
- #include<queue>
- #include<map>
- #include<vector>
- #include<cstdio>
- #include<algorithm>
- #include<stack>
- #include<cstring>
- using namespace std;
- typedef long long ll;
- const int N=1e5+10;
- const int inf=0x3f3f3f3f;
- string s;
- bool check(int mid){
- int cnt=0;
- int pos=0;
- for(int i=1;i<=s.size();i++){
- if(s[i]=='R'){
- if(i-pos>mid)
- return false;
- pos=i;
- cnt++;
- }
- }
- int sign=s.size()-1;
- if(sign+1-pos>mid)
- return false;
- if(!cnt){
- if(mid<sign+1)
- return false;
- }
- return true;
- }
- int main(){
- int t;
- cin>>t;
- while(t--){
- cin>>s;
- s=" "+s;
- int i;
- int l=1,r=inf;
- while(l<r){
- int mid=l+r>>1;
- if(check(mid))
- r=mid;
- else
- l=mid+1;
- }
- cout<<l<<endl;
- }
- return 0;
- }
- View Code
D 题
这题可以通过移项变成 a[i]-b[i]>b[j]-a[j] i<j, 这样可以我们可以先做预处理, 通过上下相减的方法得到新的数列, 然后不难发现可以用树状数组来求在他之前比他大的数
但是本题有负数, 所以考虑离散化
- #include<iostream>
- #include<queue>
- #include<map>
- #include<vector>
- #include<cstdio>
- #include<algorithm>
- #include<stack>
- #include<cstring>
- using namespace std;
- typedef long long ll;
- const int N=5e5+10;
- const int inf=0x3f3f3f3f;
- int a[N],b[N];
- int c[N],d[N];
- int tr[N];
- vector<int> num;
- int lowbit(int x){ //lowbit 函数
- return x&-x;
- }
- void add(int x,int c){ // 单点修改函数
- int i;
- for(i=x;i<=num.size();i+=lowbit(i)){
- tr[i]+=c;
- }
- }
- int sum(int x){// 区间查询函数
- int res=0;
- int i;
- for(i=x;i;i-=lowbit(i)){
- res+=tr[i];
- }
- return res;
- }
- int find(int x){
- return lower_bound(num.begin(),num.end(),x)-num.begin()+1;
- }
- int main(){
- int n;
- int i;
- ll res=0;
- cin>>n;
- memset(tr,0,sizeof tr);
- for(i=1;i<=n;i++){
- scanf("%d",&a[i]);
- }
- for(i=1;i<=n;i++){
- scanf("%d",&b[i]);
- }
- for(i=1;i<=n;i++){
- c[i]=a[i]-b[i];
- d[i]=b[i]-a[i];
- }
- for(i=1;i<=n;i++){
- num.push_back(c[i]);
- num.push_back(d[i]);
- }
- sort(num.begin(),num.end());
- num.erase(unique(num.begin(),num.end()),num.end());
- for(i=1;i<=n;i++){
- int pos=find(d[i]);
- int pos2=find(c[i]);
- int tmp=sum(pos);
- int tmp2=sum((int)num.size());
- res+=(tmp2-tmp);
- add(pos2,1);
- }
- cout<<res<<endl;
- return 0;
- }
- View Code
E 题
这题是明显的 dp 题目, 因为睡一天等于还在这个时间点, 所以没变, 只需要考虑醒着的时间的变化, 这降低了思维难度
然后枚举二维表示天数和个数, 注意有两种可能的转移情况
- #include<iostream>
- #include<queue>
- #include<map>
- #include<vector>
- #include<cstdio>
- #include<algorithm>
- #include<stack>
- #include<cstring>
- using namespace std;
- typedef long long ll;
- const int N=5e5+10;
- const int inf=0x3f3f3f3f;
- int f[2100][2100];
- int a[N];
- int main(){
- int n,l,h,r;
- cin>>n>>h>>l>>r;
- int i;
- for(i=1;i<=n;i++){
- cin>>a[i];
- }
- memset(f,-0x3f,sizeof f);
- f[0][0]=0;
- for(i=1;i<=n;i++){
- for(int j=0;j<h;j++){
- f[i][j]=max(f[i-1][(j-a[i]+h)%h],f[i-1][(j-a[i]+1+h)%h])+(l<=j&&j<=r);
- }
- }
- int res=0;
- for(i=0;i<h;i++){
- res=max(res,f[n][i]);
- }
- cout<<res<<endl;
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3460642.html