黑龙江农垦科技职业学院喜迎寒假多校联赛2（快乐ak场）-题解总结

附上链接：
黑龙江农垦科技职业学院喜迎寒假多校联赛2（快乐ak场）

总体：由于考试的时候是按照通过率的节奏来走的，所以像A，B题，一开始都没有打算开题，最后阶段一直死磕D题的二分，直到结束也没找出错误来。。。。。。
最后发现。。。。二分的上界和下届写错了。。。。。。裂开

A数组截取

思路很简单，用两个指针的方式，左指针先不动，右指针往后移，如果不满足条件，左指再往后移，最后找出最长区间。。多么简单啊。。。再也不跟AC率做题了。。。。

据出题人说数据范围很大，建议使用快读。

附上AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 77797;
#define iss ios::sync_with_stdio(false)
inline ll read(){ll s = 0, w = 1; char ch = getchar();while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();return s * w;
}
ll a[20000005];
int main(){ll n = read(),k = read();ll l = 0,sum = 0,ans = -1;for(int i = 0 ; i < n ;++i){a[i] = read();sum += a[i];while(sum > k) sum -= a[l++];if(sum == k) ans = max(ans,i - l + 1);}printf("%lld\n",ans);
}

小结：通过这题，又再一次复习了双指针的用法。l,r真是妙呀。

B排列数字

没啥好说的，直接暴力枚举判断是否满足条件，用dfs或者STL next_permutation(a,a+n)

#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b)  for(int i=(a);i<=(b);i++)
int n,m;
long long a[20];
int ans;
int main()
{  cin>>n>>m;f(i,0,n-1)a[i]=i;do{long long sum=0;f(i,0,n-1){sum=sum*10+a[i];}if(sum%m==0)ans++;}while(next_permutation(a,a+n));if(ans)cout<<ans;elsecout<<-1; }

C查成绩

水题，前缀和，没啥好说的

#include<iostream>
#include<cstdlib>
#include<queue>
#define ll long long
using namespace std;
ll a[1000010];
char ch;
ll read(){while(ch =getchar(), ch < '0' || ch > '9');ll res = ch - 48;while(ch = getchar(), ch >= '0' && ch <= '9')res = res * 10 + ch - 48;return res;
}
int main(){ll n,m,i,x,y;n = read(),m = read();for(i = 1;i <= n;i ++)x = read(),a[i] = a[i-1] + x;while(m--){x = read();y = read();cout<<a[y] - a[x-1]<<endl;}return 0;
}

D学生分组（求区间最大值的最小值）

第一感觉是个典型的DP，于是开始无脑写DP，写着写着，回去看了一下数据范围。。
于是开始写二分，大概15分钟左右，写出二分。。于是这场比赛开始无限卡壳了，

思路：二分答案，判断是否满足条件。

二分的核心代码，check（）函数：

int check(ull mid)
{ull s=1;ull sum=0;for(int i=0;i<m;i++){sum=sum+a[i];if(sum>mid){ sum=a[i];s++;}   if(s>k)return false;}return true;
}

小结：给学生分组的代码，值得反复推敲 。

如果枚举到有答案更大，则不满足，另减去当前a[i]值，上一组分为一组，分组数加1

for(int i=0;i<m;i++){sum=sum+a[i];if(sum>mid){ sum=a[i];s++;}   

如果大于分组数，则不满足条件要求：

if(s>k)return false;

值得思考的是，只要分组数小于等于K，就满足条件。题目条件是求区间和最大值的最小值，如果分组更小的答案都满足条件，那么K组的也一定满足条件。

附上赛后AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
unsigned long long m,k;
ull a[1000020];
ull maxx,minn;
char ch;
ull read(){while(ch =getchar(), ch < '0' || ch > '9');ull res = ch - 48;while(ch = getchar(), ch >= '0' && ch <= '9')res = res * 10 + ch - 48;return res;
}
int check(ull mid)
{ull s=1;ull sum=0;for(int i=0;i<m;i++){sum=sum+a[i];if(sum>mid){ sum=a[i];s++;}   if(s>k)return false;}return true;
}
int main()
{     //freopen("in.txt","r",stdin);scanf("%lld%lld",&m,&k); for(ull i=0;i<m;i++){a[i]=read(); maxx+=a[i];if(minn<a[i])minn=a[i];}while(maxx>minn){ull mid=(maxx+minn)/2; if(check(mid))maxx=mid;elseminn=mid+1;}cout<<maxx;  
} 

原因竟然只是出在这里：

    if(check(mid))maxx=mid;elseminn=mid+1;

一开始我一直写成这样：

    if(check(mid))maxx=mid+1;elseminn=mid;

对二分的理解还是不够。。。。有点背模板的感觉。

二分是上届和下届不清楚的同学，最好是先手动模拟几个样例

E:删数问题

N久以前做过这道题，当时用贪心的方法

于是写了贪心的算法，超时。。。数据范围应该是扩大了

后面交流听大佬说用单调栈，不是很熟练单调栈的用法，后期再补。

F异或运算

结论题：
　　让 n 对应二进制每一位都为 1 即为答案。

#include<iostream>
using namespace std;
int main(){long long n;long sum = 1;int len = 0;scanf("%lld",&n);while(n){n /=2;len++;}while(len--){sum *= 2;}cout<<sum-1;return 0;
}

G%%%Alan

在一个地方,卡了好久！！！！！！！

这里一定要注意，用getchar（）去掉回车

scanf("%d",&n);  
getchar();//scanf()会带来一个回车，用getchar()去掉它,这是为了下面的gets 
gets(s);

附上AC代码：

#include<bits/stdc++.h>
using namespace std;
long long n;
string s;
int  z[2000];
bool g[2000];
int mark=0;
int sum;
int main()
{     int now;//freopen("in.txt","r",stdin);
scanf("%d",&n);getchar();for(int i=1;i<=n;i++){  getline(cin,s);mark=0;int sa=s.size();for(int j=0;j<sa;j++){if(s[j]=='A'){mark++;now=j+1;while(s[now]==' ')now++;if(s[now]=='l'){mark++;now++;while(s[now]==' ')now++;if(s[now]=='a'){  mark++;now++;while(s[now]==' ')now++;if(s[now]=='n') {mark++;now++;}}}}if(mark==4){break;	}}if(mark==4) for(int j=0;j<sa;j++)if(s[j]=='%')sum++;}printf("%d",sum);} 

H&Icg写项目

结构体排序，没啥好说的。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<deque>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
struct node
{string s;string m;string x;string h; long long z;
}a[1000200];
int cmp(node b,node c)
{if(b.s==c.s)return b.z<c.z;if(b.s.size()!=c.s.size())return b.s.size()<c.s.size();else if(b.s!=c.s)return b.s<c.s;else return b.z>c.z;
}
int main()
{//freopen("in.txt","r",stdin);cin>>n;for(int i=1;i<=n;i++){cin>>a[i].s>>a[i].m>>a[i].x>>a[i].h;a[i].z=i;}sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++){cout<<a[i].s<<" "<<a[i].m<<" "<<a[i].x<<" "<<a[i].h<<endl;	} } 

J签到题