常考题目

三分

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<sstream>
using namespace std;
typedef long long
ll;
const int maxn=5e5+10;
int n,m,f[maxn],a,b;
int F(int x){
return f[x]-a*x-b;
}
int solve(int l,int r){
if(r-l<=3) {
int res=max(F(l),F(l+1));
res=max(res,F(l+2));
return max(res,F(r));
}
int s=l*2.0/3+r*1.0/3,t=l*1.0/3+r*2.0/3;
int fs=F(s),ft=F(t);
if(fs>ft) return solve(l,t);
else return solve(s,r);
}
int main(){
while(scanf("%d%d",&n,&m)==2){
for(int i=1;i<=n;++i) scanf("%d",&f[i]);
while(m--){
scanf("%d%d",&a,&b);
printf("%dn",solve(1,n));
}
}
return 0;
}

计算式的计算

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000 + 10;
struct Node {
int data;
char op;
bool is;
};
queue<Node> q;
stack<Node> s;
string op;
map<char, int> mp;
int main() {
ios::sync_with_stdio(false);
mp['+'] = mp['-'] = 1;
mp['*'] = mp['/'] = 2;
cin >> op;
int len = op.length();
Node temp;
for (int i = 0; i < len; i++) {
if (op[i] >= '1'&&op[i] <= '9') {
temp.data = op[i] - '0';
temp.is = true;
q.push(temp);
}
else {
temp.op = op[i];
temp.is = false;
while (!s.empty()&&mp[s.top().op] >= mp[op[i]]) {
Node temp1 = s.top();
s.pop();
q.push(temp1);
}
s.push(temp);
}
}
while (!s.empty()) {
q.push(s.top());
s.pop();
}
while (!q.empty()) {
Node cur = q.front();
q.pop();
if (cur.is) s.push(cur);
else {
Node t2 = s.top();
s.pop();
Node t1 = s.top();
s.pop();
Node ans;
ans.is = true;
if (cur.op == '+') ans.data = t2.data + t1.data;
else if (cur.op == '-') ans.data = t1.data - t2.data;
else if (cur.op == '*') ans.data = t1.data * t2.data;
else if (cur.op == '/') ans.data = t1.data / t2.data;
//cout << ans.data << endl;
s.push(ans);
}
}
cout << s.top().data << endl;
return 0;
}

单调栈计算最大子矩形

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
ll h[maxn];
ll width[maxn];
int n;
ll s[maxn];
int main() {
ios::sync_with_stdio(false);
while (cin >> n && n) {
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
h[n + 1] = 0;
int p = 0;
ll ans = 0;
for (int i = 1; i <= n + 1; i++) {
if (h[i] > s[p]) {
s[++p] = h[i];
width[p] = 1;
}
else {
int d = 0;
while (s[p] > h[i]) {
d += width[p];
ans = max(ans, d*s[p]);
p--;
}
s[++p] = h[i], width[p] = d+1;
}
}
cout << ans << endl;
}
return 0;
}

最大二维矩阵

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000 + 10;
int num[maxn][maxn];
int n;
int ans = 0;
int colsum[maxn];
int get() {
int b = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
if (b+colsum[i] > 0) b += colsum[i];
else b = colsum[i];
ans = max(ans, b);
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
while (cin >> n) {
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> num[i][j];
ans = 0;
for (int i = 1; i <= n; i++) {
cls(colsum, 0);
for (int j = i; j <= n; j++) {
for (int k = 1; k <= n; k++) {
colsum[k] += (num[j][k]);
}
ans = max(ans, get());
}
}
cout << ans << endl;
}
return 0;
}

传纸条

这是走两次的，走三次的类似

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2+10;
int num[maxn][maxn];
int n, m;
int dp[maxn][maxn][maxn];
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>num[i][j];
dp[0][1][1] = num[1][1];
for(int i=1; i<=n+m-2; i++){
for(int x1=1; x1<=n; x1++){
for(int x2=1; x2<=n;x2++){
int y1 = i+2-x1;
if(y1<1||y1>m) continue;
int y2 = i+2-x2;
if(y2<1||y2>m) continue;
if(x1 == x2){
dp[i][x1][x2] = max(dp[i][x1][x2], dp[i-1][x1][x2]+num[x1][y1]);
if(x1-1>=1&&x2-1>=1){
dp[i][x1][x2] = max(dp[i][x1][x2], dp[i-1][x1-1][x2-1]+num[x1][y1]);
}
if(x1-1>=1) dp[i][x1][x2] = max(dp[i][x1][x2], dp[i-1][x1-1][x2]+num[x1][y1]);
if(x2-1>=1) dp[i][x1][x2] = max(dp[i][x1][x2], dp[i-1][x1][x2-1]+num[x1][y1]);
}
else{
dp[i][x1][x2] = max(dp[i][x1][x2], dp[i-1][x1][x2]+num[x1][y1]+num[x2][y2]);
if(x1-1>=1&&x2-1>=1){
dp[i][x1][x2] = max(dp[i][x1][x2], dp[i-1][x1-1][x2-1]+num[x1][y1]+num[x2][y2]);
}
if(x1-1>=1) dp[i][x1][x2] = max(dp[i][x1][x2], dp[i-1][x1-1][x2]+num[x1][y1]+num[x2][y2]);
if(x2-1>=1) dp[i][x1][x2] = max(dp[i][x1][x2], dp[i-1][x1][x2-1]+num[x1][y1]+num[x2][y2]);
}
}
}
}
cout<<dp[n+m-2][n][n]<<endl;
return 0;
}
/*
4 4
1 -1 -1 -1
-1 10 -1 -1
-1 -1 10 -1
-1 -1 -1 10
*/