黑龙江农垦科技职业学院喜迎寒假多校联赛2（快乐ak场）
传送门(点击传送 )
A. 数组截取
题意：
从数列中截取和为 k 的序列，越长越好。
思路：
双指针搞一遍，当区间内和小于等于 k 时右指针向右移。之后当区间内和大于 k 时，左指针向右移。建议边处理边读。数据过大注意用快读。
代码：
#include<iostream>
using namespace std;
long long num[20000005];
long long read() {
long long x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x;
}
inline void write(long long x) {
static int sta[35];
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) putchar(sta[--top] + 48);
}
int main()
{
long long n,k,sum=0,ans=-1,i=1,j=1;
n=read();k=read();
while(i<=n){
while(sum<=k && i<=n){
num[i]=read();
sum+=num[i];
if(sum==k){
ans=(i-j+1)>ans?(i-j+1):ans;
}
i++;
}
while(sum>k && i>=j){
sum-=num[j];
j++;
}
if(sum==k){
ans=(i-j)>ans?(i-j):ans;
}
}
if(ans==-1) puts("-1");
else write(ans);
return 0;
} B. 群友们在排列数字
题意：
群友们在玩一个游戏,共 n 个人在玩 每个人要在 0-(n-1) 中选一个数，注意每个数只能选择一次。依次选择后拼成的数字能被 k 整除的个数。
思路：
暴力枚举每一个人选择的数字即可，可用递归。
代码：
#include<bits/stdc++.h>
using namespace std;
bool flag[15];
int n,ans;
long long sum=0,k;
void solve(int now){
if(now>n){
if(sum%k==0) ans++;
return;
}
for(int i=0;i<n;i++){
if(!flag[i]){
sum*=10;
sum+=1ll*i;
flag[i]=true;
solve(now+1);
flag[i]=false;
sum/=10;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>k;
solve(1);
if(ans==0) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
} C. gg查成绩
题意：
已知 n 个同学，m 次询问，每次询问第 x 和第 y 同学之间所有同学的成绩和（包括 x 和 y ）。
思路：
预处理求出前缀和数组，作差即可。
代码：
#include<bits/stdc++.h>
using namespace std;
long long sum[1000005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
long long n,m,get_num;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>get_num;
sum[i]=sum[i-1]+get_num;
}
int a,b;
for(int i=1;i<=m;i++){
cin>>a>>b;
cout<<sum[b]-sum[a-1]<<endl;
}
return 0;
} D. issue与lifehappy给学生分组
题意：
n 个学生，划分成 m 组，让和的最大值最小。
思路：
进行二分处理，对于每一次的值，判断该值是否符合条件。（注意题目中的是选取连续队列），预处理边界 l 为所有数的最大值，r 为所有数之和。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
long long num[1000005];
int n,m;
bool judge(ull x){
int cont=1;
ull sum=0;
for(int i=1;i<=n;i++){
sum+=num[i];
if(sum>x){
sum=num[i];
cont++;
}
if(cont>m) return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ull l=0,r=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>num[i];
r+=num[i];
l=l>num[i]?l:num[i];
}
while(l<r){
ull mid=(l+r)>>1;
if(judge(mid)){
r=mid;
}else{
l=mid+1;
}
}
cout<<l<<endl;
return 0;
} E. 删删删越小越好
题意：
给出一个数，求出删去 k 个字符后的最小值。
思路：
当然是让越靠近左边的数字越小越好（即高位小），所以从左到右依次处理字符，对于第 i 个位置的数字，如果左边的数字（1 ~ i-1）位置有比它大的，则删去第 i 个数字左边的数字，直到无法删除或者第 i 个数字左边的数字都小于等于第 i 个数字。剩下的即为答案。（不知道不用快读行不行）
代码：
#include<bits/stdc++.h>
using namespace std;
inline string read()
{
char ch = getchar();
string st1 = "";
while ((ch >= '0') && (ch <= '9'))
st1 += ch, ch = getchar();
return st1;
}
int read_n() {
int x = 0;
char ch = 0;
while (ch < '0' || ch > '9') {
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x;
}
int main()
{
bool flag=false;
string str=read();
int k=read_n(),cont=0;
deque<char>que;
for(int i=0;i<str.size();i++){
if(cont==k) que.push_back(str[i]);
else if(que.empty()) que.push_back(str[i]);
else{
while((!que.empty())&& cont<k && str[i]<que.back()){
que.pop_back();
cont++;
}
que.push_back(str[i]);
}
}
while(cont<k){
que.pop_back();
cont++;
}
while(!que.empty()){
if(flag){
putchar(que.front());
}else{
if(que.front()!='0'){
putchar(que.front());
flag=true;
}
}
que.pop_front();
}
if(!flag) putchar('0');
return 0;
} F. happy的异或运算
题意：
给出一个整数 n，请求出 1-n 之间选取两个数进行异或最大能得出多大。
思路：
让 n 对应二进制每一位都为 1 即为答案。
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n,ans=0;
cin>>n;
while(n){
ans<<=1;
ans|=1;
n>>=1;
}
cout<<ans<<endl;
return 0;
} G. Alan%%%
题意：
如果一行中除去空格后包括Alan则这一行所有的%为有效%，问一共有多少个有效%。
思路：
每次读一行，暴力对比ALan即可（遇到空格则忽略直接下一个字符）。
代码：
#include<bits/stdc++.h>
using namespace std;
string model="Alan";
int main(void)
{
int n,ans=0,cont,p;
string str;
bool flag;
cin>>n;
getchar();
for(int tc=1;tc<=n;tc++){
p=0;
cont=0;
flag=false;
getline(cin,str);
for(int i=0;i<str.size();i++){
if(str[i]==' ') continue;
if(str[i]=='%') cont++;
if(!flag){
if(str[i]==model[p]){
p++;
if(p==4) flag=true;
}else{
if(str[i]==model[0]) p=1;
else p=0;
}
}
}
if(flag) {
ans+=cont;
}
}
cout<<ans<<endl;
return 0;
} H. cg写项目 & I. cg写项目加强版
题意：
很多用户数据，以用户的用户名为基准进行一下排序,短的在前,同样长度按照字典序小的在前，同用户名先输入的在前面。
思路：
直接 sort 一下加一下排序条件即可。
代码：
#include<bits/stdc++.h>
using namespace std;
struct node{
int loc;
string s,m,x,h;
}que[1000005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>que[i].s>>que[i].m>>que[i].x>>que[i].h;
que[i].loc=i;
}
sort(que+1,que+1+n,[](const node &a,const node &b){
if(a.s.size()==b.s.size()){
if(a.s==b.s){
return a.loc<b.loc;
}else{
return a.s<b.s;
}
}else{
return a.s.size()<b.s.size();
}
});
for(int i=1;i<=n;i++){
cout<<que[i].s<<" "<<que[i].m<<" "<<que[i].x<<" "<<que[i].h<<endl;
}
return 0;
} J. 比赛开始了清楚姐姐喊了一句:签到了签到了
题意：
输出最先做出题目的人的序号。
思路：
签到题怎么写都行。
代码：
#include<bits/stdc++.h>
using namespace std;
struct node{
int loc,num;
}que[10005];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>que[i].num;
que[i].loc=i;
}
sort(que+1,que+1+n,[](const node &a,const node &b){
if(a.num==b.num) return a.loc<b.loc;
else return a.num<b.num;
});
cout<<que[1].loc<<endl;
return 0;
} 
京公网安备 11010502036488号