A题
比较 naive 的快读 + 指针题
首先对原数组做一个前缀和，然后我们枚举每一个左端点，而右端点是只能单调右移的，所以最终的复杂度是O()
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e7 + 50;
long long sum[MAXN],k;
int n;
int R = 1,Ans = -1;
struct ios {
inline char read(){
static const int IN_LEN=1<<18|1;
static char buf[IN_LEN],*s,*t;
return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
}
template <typename _Tp> inline ios & operator >> (_Tp&x){
static char c11,boo;
for(c11=read(),boo=0;!isdigit(c11);c11=read()){
if(c11==-1)return *this;
boo|=c11=='-';
}
for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
boo&&(x=-x);
return *this;
}
} io;
int main() {
io>>n>>k;
long long T;
for(int i = 1 ; i <= n ; i ++) {
io>>T;
sum[i] = sum[i - 1] + T;
}
for(int i = 1 ; i <= n ; i ++) {
while(R < n && sum[R + 1] - sum[i - 1] <= k) R ++;
if(sum[R] - sum[i - 1] == k)
Ans = max(Ans,R - i + 1);
}
printf("%d",Ans);
return 0;
} B题
DFS题，没什么好说的。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k,total = 0;
bool book[15];
void DFS(int x,int now) {
for(int i = 0 ; i < n ; i ++) {
if(book[i] == 0) {
book[i] = 1;
int Q = now;
now = now * 10 + i;
if(x == n) total+= ((now % k) == 0);
else DFS(x + 1,now);
now = Q;
book[i] = 0;
}
}
return ;
}
signed main() {
cin >> n >> k;
DFS(1,0);
if(total) cout << total;
else cout << -1;
return 0;
} C题
一个 naive 的前缀和即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 50;
int n,m;
long long sum[MAXN];
inline long long read() {
long long x = 0;
char ch = getchar();
for( ; ch > '9' || ch < '0' ; ch = getchar());
for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + (ch & 15);
return x;
}
int main() {
n = read() , m = read();
for(int i = 1 ; i <= n ; i ++) sum[i] = sum[i - 1] + read();
while(m --) {
int l,r;
l = read() , r = read();
printf("%lld\n",sum[r] - sum[l - 1]);
}
return 0;
} D题
二分答案即可，答案的初始值赋值为1e18
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6 + 50;
int n,m,sum[MAXN],A[MAXN];
inline long long read() {
long long x = 0;
char ch = getchar();
for( ; ch > '9' || ch < '0' ; ch = getchar());
for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + (ch & 15);
return x;
}
bool check(int x) {
if(x < 0) return 0;
int ls = 0,now = 1,total = 0;
for(int i = 1 ; i <= n ; i ++) {
total += A[i];
if(total > x) total = A[i] , now ++;
}
if(now <= m) return 1;
return 0;
}
signed main() {
n = read() , m = read();
for(int i = 1 ; i <= n ; i ++) sum[i] = sum[i - 1] + (A[i] = read());
if(m == 1) {cout << sum[n] ; return 0;}
int Ans = 1e18;
for(int i = 62 ; i >= 0 ; i --)
if(check(Ans - (1ll << i)) == 1) Ans -= (1ll << i);
cout << Ans;
return 0;
} E题
考察栈结构，没有什么好说的。
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e7 + 50;
char s[MAXN];
int tack[MAXN];
int n,k;
int main() {
scanf("%s",&s);
scanf("%d",&k);
for(int t = 0 ; ; t ++) if(s[t] == '\0') {n = t ; break;}
int C = k;
int ls = -1,top = 0;
for(int i = 0 ; i < n ; i ++) {
while(top > 0 && s[tack[top]] > s[i] && C > 0)C -- , top --;
tack[++top] = i;
}
int flag = 0;
for(int i = 1 ; i <= top - C ; i ++) {
if(s[tack[i]] != '0' || flag != 0)
cout << s[tack[i]];
if(s[tack[i]] != '0') flag = 1;
}
if(!flag) cout << 0;
return 0;
} F题
没有什么好说的，结论题。
#include <bits/stdc++.h>
using namespace std;
long long n,x = 1;
int main() {
cin >> n;
while((x << 1) <= n) x <<= 1;
cout << (x ^ (x - 1));
return 0;
} G题
naive 的字符串模拟题。
#include <bits/stdc++.h>
using namespace std;
char S[10005];
int Ans = 0;
string a;
void Get() {
int tail = 0;
getline(cin,a);
int len = a.length();
for(int i = 0 ; i < len ; i ++)
if(a[i] != ' ' && a[i] != '\n') tail ++ , S[tail] = a[i];
int cnt = 0,flag = 0;
for(int i = 1 ; i <= tail ; i ++) {
if(S[i] == '%') cnt ++;
if(S[i] == 'A' && S[i + 1] == 'l' && S[i + 2] == 'a' && S[i + 3] == 'n') flag = 1;
}
Ans += cnt * flag;
for(int i = 1 ; i <= tail ; i ++) S[i] = '\0';
return ;
}
int main() {
int n;
cin >> n;
n ++;
while(n --) Get();
cout << Ans;
return 0;
} H 题
直接sort即可，可以重载运算符或者写cmp函数
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 50;
struct Node {
string Name,M,X,H;
int len,id;
} T[MAXN];
string A;
bool cmp(Node A, Node B) {
if(A.len != B.len) return A.len < B.len;
if(A.Name != B.Name) return A.Name < B.Name;
return A.id < B.id;
}
int main() {
int n;
cin >> n;
for(int i = 1 ; i <= n ; i ++) {
cin >> T[i].Name >> T[i].M >> T[i].X >> T[i].H;
T[i].len = T[i].Name.length();
T[i].id = i;
}
sort(T + 1 , T + 1 + n , cmp);
for(int i = 1 ; i <= n ; i ++)
cout << T[i].Name << " " << T[i].M << " " << T[i].X << " " << T[i].H << endl;
return 0;
} I 题
同上。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 50;
struct Node {
string Name,M,X,H;
int len,id;
} T[MAXN];
string A;
bool cmp(Node A, Node B) {
if(A.len != B.len) return A.len < B.len;
if(A.Name != B.Name) return A.Name < B.Name;
return A.id < B.id;
}
int main() {
int n;
cin >> n;
for(int i = 1 ; i <= n ; i ++) {
cin >> T[i].Name >> T[i].M >> T[i].X >> T[i].H;
T[i].len = T[i].Name.length();
T[i].id = i;
}
sort(T + 1 , T + 1 + n , cmp);
for(int i = 1 ; i <= n ; i ++)
cout << T[i].Name << " " << T[i].M << " " << T[i].X << " " << T[i].H << endl;
return 0;
} J 题
直接找最小值即可。
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0;
char ch = getchar();
for( ; ch > '9' || ch < '0' ; ch = getchar());
for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + (ch & 15);
return x;
}
int main() {
int M = 100000 , f = 0,n = read(),x;
for(int i = 1 ; i <= n ; i ++) if((x = read()) < M) f = i , M = x;
cout << f;
return 0;
} 
京公网安备 11010502036488号