比赛地址
牛客小白月赛101_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ
A . tb的区间问题
每次删掉前面的，后面的，最后剩下连续的n-k个数，答案就是求连续n-k个数的最大和;
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;#define endl '\n'
typedef long long LL;
#define pb push_back
#define eb emplace_back
#define PII pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define int long longconst int N = 2e5 + 10 ;
const int Mod = 1e9 + 7 ;
// int xx[] = { 1,0,-1,0 };
// int yy[] = { 0,1,0,-1 };LL qmi(LL m, LL k){LL res = 1 % Mod, t = m;while (k){if (k&1) res = res * t % Mod;t = t * t % Mod;k >>= 1;}return res;}inline void solve(){int n , k ; cin >> n >> k ;vector<int> a(n) ;for(int& x : a) cin >> x ;int ans = 0 ;int t = n - k ;vector<int> b(n+1,0) ;for(int i=1;i<=n;i++) b[i] = b[i-1] + a[i-1] ;for(int i=t;i<=n;i++) {ans = max(ans,b[i]-b[i-t]) ;}cout << ans << endl ;
}signed main(){IOSint _ = 1;// cin >> _;while(_ --) solve();return 0;
}B . tb的字符串问题
用一个栈维护就好了，类似括号匹配问题 ;
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;#define endl '\n'
typedef long long LL;
#define pb push_back
#define eb emplace_back
#define PII pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define int long longconst int N = 2e5 + 10 ;
const int Mod = 1e9 + 7 ;
// int xx[] = { 1,0,-1,0 };
// int yy[] = { 0,1,0,-1 };LL qmi(LL m, LL k){LL res = 1 % Mod, t = m;while (k){if (k&1) res = res * t % Mod;t = t * t % Mod;k >>= 1;}return res;}inline void solve(){int n ; cin >> n ;string s ; cin >> s ;int ans = 0 ;stack<char> st ;for(int i=0;i<n;i++){if(s[i]=='f'){st.push(s[i]) ;}else if(s[i]=='t'){st.push(s[i]) ;}else if(s[i]=='c'){if(!st.empty()&&st.top()=='f'){ans += 2 ;st.pop() ;}else{st.push(s[i]) ;}}else if(s[i]=='b'){if(!st.empty()&&st.top()=='t'){ans += 2 ;st.pop() ;}else{st.push(s[i]) ;}}else{while(!st.empty()) st.pop() ;}}int res = n - ans ;cout << res << endl ;
}signed main(){IOSint _ = 1;while(_ --) solve();return 0;
}
C . tb的路径问题
数学找规律题，多次打表猜结论就ok ;
对于n>=4 : 都是先走到(2,2),然后再走到离(n,n)最近的2 ;
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;//#define endl '\n'
typedef long long LL;
#define pb push_back
#define eb emplace_back
#define PII pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define int long longconst int N = 1e3 + 10 ;
const int Mod = 1e9 + 7 ;
// int xx[] = { 1,0,-1,0 };
// int yy[] = { 0,1,0,-1 };int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}LL qmi(LL m, LL k){LL res = 1 % Mod, t = m;while (k){if (k&1) res = res * t % Mod;t = t * t % Mod;k >>= 1;}return res;}int a[N][N] ;inline void solve(){int n ; cin >> n ;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// a[i][j] = gcd(i,j) ;
// cout << a[i][j] << " " ;
// }
// cout << endl ;
// }if(n==1){cout << 0 << endl ;}else if(n==2){cout << 2 << endl ;}else if(n==3){cout << 4 << endl ;}else{if(n&1) cout << 6 << endl ;else cout << 4 << endl ;}
}signed main(){IOSint _ = 1;// cin >> _ ;while(_ --) solve();return 0;
}D . tb的平方问题
差分数组 + 前缀和问题
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;#define endl '\n'
typedef long long LL;
#define pb push_back
#define eb emplace_back
#define PII pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define int long longconst int N = 1e3 + 10 ;
const int Mod = 1e9 + 7 ;
// int xx[] = { 1,0,-1,0 };
// int yy[] = { 0,1,0,-1 };LL qmi(LL m, LL k){LL res = 1 % Mod, t = m;while (k){if (k&1) res = res * t % Mod;t = t * t % Mod;k >>= 1;}return res;}bool pd(int x){int t = sqrt(x) ;return t*t==x ;
}inline void solve(){int n , q ; cin >> n >> q ;vector<int> a(n+1) ;for(int i=1;i<=n;i++) cin >> a[i] ;vector<int> b(n+1,0) , c(n+2,0) , d(n+2,0) ; for(int i=1;i<=n;i++) b[i] = b[i-1] + a[i] ;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){if(pd(b[j]-b[i-1])){c[i]++;c[j+1]-- ;}}}for(int i=1;i<=n+1;i++){d[i] = d[i-1] + c[i] ;}while(q--){int x ; cin >> x ;cout << d[x] << endl ;}return ;
}signed main(){IOSint _ = 1;// cin >> _ ;while(_ --) solve();return 0;
}E . tb的数数问题
将没有出现的数，以及它的倍速全删了，最后统计答案即可 ;
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;#define endl '\n'
typedef long long LL;
#define all(x) x.begin(), x.end()bool pd(int x){if(x<2) return false ;for(int i=2;i<=x/2;i++){if(x%i==0) return false ;}return true ;
}const int N = 1e6 + 10 ;int b[N] ;inline void solve(){
// int n ; cin >> n ;
// vector<int> a(n) ;
// for(int& x : a) cin >> x ;
// sort(all(a)) ;
// a.erase(std::unique(all(a)), a.end());
// int res = 0 ;
// n = a.size() ;
// for(int x : a) b[x]++ ;
// if(a[0]!=1){cout << 0 << endl ;return ;}
// for(int j=0;j<n;j++){
// int x = a[j] ;
// bool tag = true ;
// for(int i=1;i<=x/i;i++)
// if(x%i==0){
// if(!b[i]) { tag = false ;break ;}
// if(!b[x/i]) { tag = false ;break ;}
// }
// if(tag) res++ ;
// }
// cout << res << endl ;int n;std::cin >> n ;std::vector<int> vis(1000005, 0), flag(1000005, 0), a(n + 1);bool f = 0;int mx = -1;for (int i = 1; i <= n; i++) {std::cin >> a[i];if (a[i] == 1) {f = 1;}mx = std::max(mx, a[i]);vis[a[i]] = 1;}if (!f) {std::cout << 0;return;}for (int i = 2; i <= mx; i++) {if (!vis[i] && !flag[i]) {for (int j = i * 2; j <= mx; j += i) {vis[j] = 0;flag[j] = 1; }}}int ans = 0;for (int i = 1; i <= mx; i++) {if (vis[i]) {ans++;}}std::cout << ans << '\n';
}signed main(){IOSint _ = 1;while(_ --) solve();return 0;
}
