- 括号画家
括号匹配 stack 存下表 直接减就好
#include <iostream>
#include <cstring>
#include <map>
#include <stack>
using namespace std;
const string cd = "*(){}[]";
map<char, int> id;
int main (){
id['('] = 2;
id['{'] = 4;
id['['] = 6;
string s;
cin >> s;
stack<int> stc;
int ans = 0;
for(int i = 0; i< s.size(); i ++ ) {
if(!stc.empty() && cd[id[s[stc.top()]]] == s[i])
stc.pop();
else
stc.push(i);
if(!stc.empty())
ans = max(ans, i - stc.top());
else
ans = max(ans, i + 1);
}
cout << ans << endl;
return 0;
}
- 表达式计算
不知道为什么这题要出现多余括号。。。。orz
#include <iostream>
#include <stack>
using namespace std;
stack<int> nums;
stack<char> ops;
void cal() {
int a = nums.top(); nums.pop();
int b = nums.top(); nums.pop();
char c = ops.top(); ops.pop();
int d;
if (c == '+') d = b + a;
else if (c == '-') d = b - a;
else if (c == '*') d = b * a;
else if (c == '/') d = b / a;
else {
d = 1;
while(a --) {
d *= b;
}
}
nums.push(d);
}
int main() {
string str;
cin >> str;
string left(str.size(), '(');
str = left + str + ')';
for (int i = 0; i < str.size(); i ++ ) {
if (str[i] >= '0' && str[i] <= '9') {
int j = i, t = 0;
while (str[j] >= '0' && str[j] <= '9') {
t = t * 10 + str[j] - '0';
j ++ ;
}
nums.push(t);
i = j - 1;
} else {
char c = str[i];
if (c == '(') ops.push(c);
else if (c == '+' || c == '-') {
if (c == '-' && !(str[i - 1] >= '0' && str[i - 1] <= '9' || str[i - 1] == ')')) {
int j = i + 1, t = 0;
while (str[j] >= '0' && str[j] <= '9') {
t = t * 10 + str[j] - '0';
j ++ ;
}
nums.push(-t);
i = j - 1;
} else {
while (ops.top() != '(') cal();
ops.push(c);
}
} else if (c == '*' || c == '/') {
while (ops.top() == '*' || ops.top() == '/' || ops.top() == '^') cal();
ops.push(c);
} else if (c == '^') {
while (ops.top() == '^') cal();
ops.push(c);
} else if (c == ')') {
while (ops.top() != '(') cal();
ops.pop();
}
}
}
cout << nums.top() << endl;
return 0;
}
城市游戏 这题NOI出过 叫什么 玉蟾宫
单调栈。。。。。 其实还能用悬线法处理
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 5;
int n, m;
int h[maxn][maxn];
int q[maxn], l[maxn], r[maxn];
int sol(int l[], int a[]){
a[0] = -1;
int t = 0;
for(int i = 1; i <= m; i ++ ) {
while(a[q[t]] >= a[i]) t --;
l[i] = q[t] + 1;
q[ ++ t ] = i;
}
}
int work(int a[]){
sol(l, a);
reverse(a + 1, a + 1 + m);
sol(r, a);
reverse(a + 1, a + 1 + m);
int res = 0;
for(int i = 1; i <= m; i ++ ) {
int le = l[i];
int ri = m + 1 - r[m - i + 1];
res = max(res, a[i] * (ri - le + 1));
}
return res;
}
char mp[maxn][maxn];
int main(){
cin >> n >> m;
int ans = 0;
for(int i = 1; i <= n; i ++ ) {
for(int j = 1; j <=m; j ++ ) {
cin >> mp[i][j];
if(mp[i][j] == 'F') h[i][j] = h[i - 1][j] + 1;
else continue;
}
ans = max(ans, work(h[i]));
}
cout << ans * 3 << endl;
return 0;
}
P1169 [ZJOI2007]棋盘制作 2题一样 悬线法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e3+10;
const int INF= 0x3f3f3f3f;
const int mod = 1000000007;
int n,m,k,ans;
int a[maxn];
int l[maxn][maxn],r[maxn][maxn],up[maxn][maxn];
int mp[maxn][maxn];
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin>>mp[i][j];
l[i][j]=r[i][j]=j;
up[i][j]=1;
}
}
for(int i=1; i<=n; i++) for(int j=2; j<=m; j++)
if(mp[i][j-1]^mp[i][j]) l[i][j]=l[i][j-1];
for(int i=1; i<=n; i++) for(int j=m-1; j>=1; j--)
if(mp[i][j]^mp[i][j+1]) r[i][j]=r[i][j+1];
int ans1=0,ans2=0;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if( i>1 && mp[i-1][j]^mp[i][j]) {
l[i][j]=max(l[i-1][j],l[i][j]);
r[i][j]=min(r[i-1][j],r[i][j]);
up[i][j]=up[i-1][j]+1;
}
int len=r[i][j]-l[i][j]+1;
int h=min(up[i][j],len);
ans1=max(h*h,ans1);
ans2=max(len*up[i][j],ans2);
}
}
cout<<ans1<<endl<<ans2<<endl;
return 0;
}
双栈排序 待续
滑动窗口
单调队列 保证有序
#include <iostream>
using namespace std;
const int N = 1E6+5;
int que[N], a[N];
int n, k;
void getmin(){
int h = 1, t = 0;
for(int i = 1; i <= n; i ++) {
if(h <= t && que[h] + k <= i) h ++;
while(h <= t && a[que[t]] >= a[i]) t --;
que[++ t] = i;
if(i >= k) cout << a[que[h]] << " ";
}
cout << endl;
}
void getmax(){
int h = 1, t = 0;
for(int i = 1; i <= n; i ++) {
if(h <= t && que[h] + k <= i) h ++;
while(h <= t && a[que[t]] <= a[i]) t --;
que[++ t] = i;
if(i >= k) cout << a[que[h]] << " ";
}
cout << endl;
}
int main() {
cin >> n >> k;
for(int i = 1; i <= n; i ++ ) cin >> a[i];
getmin();
getmax();
return 0;
}
内存分配 模拟题 待续
矩阵
二维hash
把这矩阵 变成 一维的算hash值 然后 都存起来。。。 算询问hash直接set查
#include <iostream>
#include <unordered_set>
using namespace std;
typedef unsigned long long ULL;
const int maxn = 1005;
ULL h[maxn][maxn], p[maxn * maxn];
int n, m, a, b;
ULL reh(ULL h[], int l, int r){
return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
cin >> n >> m >> a >> b;
string str;
p[0] = 1;
for(int i = 1; i < maxn * maxn; i ++) p[i] = 131*p[i - 1];
for(int i = 1; i <= n; i++ ){
cin >> str;
for(int j = 1; j <= m; j++ ){
h[i][j] = h[i][j - 1] * 131 + str[j - 1] - 48;
}
}
unordered_set<ULL> S;
for(int i = b; i <= m; i++){
ULL s = 0;
int l = i - b + 1, r = i;
for(int j = 1; j <= n; j ++ ){
s = s * p[b] + reh(h[j], l, r);
if(j >= a) {
s -= reh(h[j - a], l, r) * p[a * b];
S.insert(s);
}
}
}
int q;
cin >> q;
while( q -- ){
ULL s = 0;
for (int i = 1; i <= a; i ++ ){
cin >> str;
for(int j = 1; j <= b; j ++ ) {
s = s * 131 + str[j - 1] - 48;
}
}
if(S.count(s)) cout << 1 << endl;
else cout << 0 << endl;
}
return 0;
}
树形地铁系统 树的最小表达
每一次 都补充0 末位补长1 使他们格式对齐
dfs遍历树结构 str
sort 就可以按字典排序 直接找最小表达
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
string dfs(string &s, int &u){
vector<string> vc;
u ++;
while(s[u] == '0')
vc.push_back(dfs(s, u));
u ++;
sort(vc.begin(), vc.end());
string res = "0";
for(int i = 0; i < vc.size(); i ++ ) {
res += vc[i];
}
res += "1";
return res;
}
signed main() {
int n, m;
cin >> n;
while(n --) {
string s1, s2;
cin >> s1 >> s2;
s1 = '0' + s1 + '1';
s2 = '0' + s2 + '1';
int ua = 0, ub = 0;
if(dfs(s1, ua) == dfs(s2, ub))
cout << "same" << endl;
else
cout << "different" << endl;
}
return 0;
}
项链
string最小表达
#include <iostream>
#include <string>
using namespace std;
string str_mins(string s){
int n = s.size();
for(int i = 0; i < n; i ++) s.push_back(s[i]);
int i = 0, j = 1, k;
while( i < n && j < n){
for(k = 0; k < n && s[i + k] == s[j + k]; k ++ );
if(k == n) break;
if(s[i + k] > s[j + k]) {
i = i + k + 1;
if(i == j) i ++;
}else{
j = j + k + 1;
if(i == j) j ++;
}
}
string res;
k = min(i, j);
for(int i = k; i < n + k; i ++) res += s[i];
return res;
}
int main(){
string s1, s2;
cin >> s1 >> s2;
s1 = str_mins(s1);
s2 = str_mins(s2);
if(s1 == s2) {
cout << "Yes" << endl;
cout << s1 << endl;
}
else cout << "No" << endl;
return 0;
}
奶牛矩阵 二维KMP 不会 待续
匹配统计
二分hash 直接查
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int maxn = 2e5 + 5;
char s1[maxn], s2[maxn];
int ans[maxn], p[maxn], h1[maxn], h2[maxn];
bool chk(int mid, int i) {
ULL ss2 = h2[mid];
ULL ss1 = h1[i + mid - 1] - h1[i - 1] * p[mid];
if(ss2 != ss1) return 0;
else return 1;
}
int main() {
int n, m, q;
cin >> n >> m >> q;
cin >> (s1 + 1) >> (s2 + 1) ;
p[0] = 1;
for(int i = 1 ; i <= n; i ++) {
h1[i] = h1[i - 1] * 131 + s1[i];
p[i] = p[i - 1] * 131;
}
for(int i = 1 ; i <= m; i ++) {
h2[i] = h2[i - 1] * 131 + s2[i];
p[i] = p[i - 1] * 131;
}
for(int i = 1; i <= n; i ++) {
int l = 0, r = min(n, m);
while(l < r){
int mid = l + r + 1 >> 1;
if(chk(mid, i)) l = mid;
else r = mid - 1;
}
ans[l] ++ ;
}
while(q--) {
cin >> m;
cout << ans[m] << endl;
}
return 0;
}
电话列表
orz 这题我强行拍了个序。。。。。。
其实不排也行 再ins的时候 判重只需要判断 这个字符串是不是重了其他之前末位 同时它是新建立的 就是重复前醉
bool ins(string &s){
int p = 0;
bool has_new = false;
bool has_found = false;
for (int i = 0; str[i]; i ++ ){
int u = str[i] - '0';
if (!son[p][u]){
trie[p][u] = ++ idx;
has_new = true;
}
p = son[p][u];
if (eds[p]) has_found = true;
}
eds[p] = true;
return has_new && !has_found;
}
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e5 + 5;
int trie[maxn << 1][12], tot = 1;
int eds[maxn << 1];
bool cmp(const string &a, const string &b){
return a.size() < b.size() || ( a.size() == b.size() && a < b );
}
void ins(string s){
int p = 1, len = s.size();
for(int k = 0; k < len; k ++ ) {
int ch = s[k] - '0';
if(trie[p][ch] == 0) trie[p][ch] = ++ tot;
p = trie[p][ch];
}
eds[p]++;
}
int ask(string s){
int p = 1, len = s.size();
for(int k = 0; k < len; k ++ ) {
p = trie[p][s[k] - '0'];
if(eds[p]) return 1;
if(p == 0) return 0;
}
return 0;
}
vector<string> vc;
int main(){
int cas;
cin >> cas;
while(cas -- ) {
int n;
memset(eds, 0, sizeof eds);
memset(trie, 0, sizeof trie);
vc.clear();
tot = 1;
cin >> n;
string s;
while(n -- ){
cin >> s;
vc.push_back(s);
}
int f = 1;
sort(vc.begin(), vc.end(), cmp);
for(auto i : vc){
//cout << "|" << i << endl;
if(ask(i)) {
cout << "NO" << endl;
f = 0;
break;
}
ins(i);
}
if(f) cout << "YES" << endl;
}
return 0;
}
黑盒子
对顶堆 大根堆 放小的 小根堆 放大的
大根堆 > k 往小根堆放 大根堆pop
这样小根堆就是 k + 1 小
#include <bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int> > minheap;
priority_queue<int, vector<int>, less<int> > maxheap;
const int maxn = 3e4 + 5;
int a[maxn];
int vis[maxn];
int k, n, m;
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
}
for(int i = 1, a; i <= m ; i++ ) {
cin >> a;
vis[a]++;
}
for(int i = 1; i <= n; i ++) {
maxheap.push(a[i]);
if(maxheap.size() > k) {
minheap.push(maxheap.top());
maxheap.pop();
}
while(vis[i]) {
cout << minheap.top() << endl;
k ++ ;
maxheap.push(minheap.top());
minheap.pop();
vis[i]--;
}
}
return 0;
}
生日礼物
没有写出 待续
京公网安备 11010502036488号