A.
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; const double EPS = 1.0e-8; const double eps = 1.0e-8; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e6 + 10; const int maxm = 300; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; //next_permutation ll mod = 1e9 + 7; int a[maxn]; int main() { //freopen("out1.txt", "w", stdout); int anser = 0; int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 2; i < n; i++) { if (a[i] > a[i - 1] && a[i] > a[i + 1]) { anser++; } if (a[i] < a[i - 1] && a[i] < a[i + 1]) { anser++; } } cout << anser << endl; }
B.
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; const double EPS = 1.0e-8; const double eps = 1.0e-8; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e6 + 10; const int maxm = 300; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; //next_permutation ll mod = 1e9 + 7; int num[maxn]; map<char, int> mp; int main() { //freopen("out1.txt", "w", stdout); int n; string a; cin >> n >> a; mp['L'] = 1, mp['R'] = 2, mp['U'] = 3, mp['D'] = 4; for (int i = 0; i < a.size(); i++) { num[mp[a[i]]]++; } cout << min(num[1], num[2]) * 2 + min(num[3], num[4]) * 2 << endl; }
C.先把每个字母的dis算出来 然后取里面最小的
dis[a[i] - 'a'] = max(dis[a[i] - 'a'], i - cur[a[i] - 'a']);
ans = min(ans, dis[i]);
#include <bits/stdc++.h> #define PI acos(-1.0) #define mem(a,b) memset((a),b,sizeof(a)) #define TS printf("!!! ") #define pb push_back #define inf 1e9 //std::ios::sync_with_stdio(false); using namespace std; //priority_queue<int,vector<int>,greater<int>> que; const double EPS = 1.0e-8; const double eps = 1.0e-8; typedef pair<int, int> pairint; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e6 + 10; const int maxm = 300; const int turn[4][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}}; //next_permutation ll mod = 1e9 + 7; int cur[maxn]; int dis[maxn]; int main() { //freopen("out1.txt", "w", stdout); int ans = INT_MAX; for (int i = 0; i <= 25; i++) { cur[i] = -1; } string a; cin >> a; int len = a.size(); for (int i = 0; i < len; i++) { dis[a[i] - 'a'] = max(dis[a[i] - 'a'], i - cur[a[i] - 'a']); cur[a[i] - 'a'] = i; } for (int i = 0; i <= 25; i++) { if (dis[i] != 0) { dis[i] = max(dis[i], len - cur[i]); ans = min(ans, dis[i]); //cout << dis[i] << endl; } } cout << ans << endl; }
D.排列组合加错排
#include<bits/stdc++.h> using namespace std; int n,k; long long ans; long long C[1001][1001]; void calc_Cmn()//求组合数 { for(int i=0;i<1001;i++) { C[i][0]=C[i][i]=1; for(int j=1;j<i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j]; } } int main() { calc_Cmn(); cin>>n>>k; for(int i=n-1;i>=n-k;i--) { if(i==n-1) ans+=1; if(i==n-2) ans+=C[n][i]; if(i==n-3) ans+=C[n][i]*2; if(i==n-4) ans+=C[n][i]*9; } cout<<ans<<endl; }
E.折半搜索
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) const int N=50; int a[N]; set<int>s; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n>>m; for(int i=0;i<n;i++)cin>>a[i],a[i]=a[i]%m; sort(a,a+n); int hf=n/2; int _hf=n-hf; for(int i=0;i<(1<<hf);i++) { int t=0; for(int j=0;j<hf;j++)if((1<<j)&i)t=(t+a[j])%m; s.insert(t); } set<int>::iterator it; int ans=0; for(int i=0;i<(1<<_hf);i++) { int t=0; for(int j=0;j<_hf;j++)if((1<<j)&i)t=(t+a[j+hf])%m; it=s.upper_bound(m-1-t); if(it==s.begin()) { ans=max(ans,t); continue; } it--; ans=max(ans,t+*it); } cout<<ans<<endl; return 0; }