题目在这里
A.似乎是个并查集+？？？
B.10W的范围，似乎可以暴力来一发二分+sort？
但我猜正解可以O(nlogn)？
C.单调队列入门题目
#include <cstdio>
int n, m, a[], ans1[], ans2[];
struct queue_1 {
int q[];
int l, r;
queue_1(): l(), r() {}
int front() {
return q[l];
}
void push(int i) {
while(l <= r && q[l] + m <= i) l ++;
while(r >= l && a[i] <= a[q[r]]) r --;
q[++ r] = i;
}
}q1;
struct queue_2 {
int q[];
int l, r;
queue_2(): l(), r() {}
int front() {
return q[l];
}
void push(int i) {
while(l <= r && q[l] + m <= i) l ++;
while(r >= l && a[i] >= a[q[r]]) r --;
q[++ r] = i;
}
}q2;
void getint(int &x) {
x = ;
static int c, f;
while(c = getchar(), (c < '' || c > '') && c != '-');
if(c != '-') x = c - '', f = ;
else f = , x = ;
while(c = getchar(), c >= ''&&c <= '') x = x * + c - '';
if(f) x = -x;
}
int main() {
getint(n), getint(m);
for(int i = ;i < m;i ++) getint(a[i]), q1.push(i), q2.push(i);
for(int i = m;i <= n;i ++)
getint(a[i]), q1.push(i), q2.push(i),
ans1[++ ans1[]] = a[q1.front()], ans2[++ ans2[]] = a[q2.front()];
for(int i = ;i <= ans1[];i ++) printf("%d ", ans1[i]);puts("");
for(int i = ;i <= ans2[];i ++) printf("%d ", ans2[i]);
return ;
}我怎么就脑子抽了写了个极丑的封装呢
注意选择C++，G++会超时
D.简单的单点修改+区间查询max
线段树即可，据说这题还能有树状数组的骚操作？
比较懒，写了两个好写一点的
分块
#include <cstdio> int n, m, siz;
int a[], mmax[]; int max(int x, int y){
return x > y ? x : y;
} int main() {
int x, y, z;
char str[];
while(scanf("%d %d", &n, &m) != EOF) {
for(siz = ;siz * siz < n;siz ++);
for(int i = ;i <= n / siz;i ++) mmax[i] = ;
for(int i = ;i < n;i ++)
scanf("%d", &a[i]), mmax[i / siz] = max(mmax[i / siz], a[i]);
while(m --) {
scanf("%s %d %d", str, &x, &y);
if(str[] == 'Q') {
z = , x --, y --;
if(x / siz == y / siz) {
for(int i = x;i <= y;i ++)
z = max(z, a[i]);
}
else {
for(int i = x;i < x / siz * siz + siz;i ++)
z = max(z, a[i]);
for(int i = y / siz * siz;i <= y;i ++)
z = max(z, a[i]);
for(int i = x / siz + ;i < y / siz;i ++)
z = max(z, mmax[i]);
}
printf("%d\n", z);
}
else {
x --, a[x] = y, mmax[x / siz] = ;
for(int i = x / siz * siz;i < x / siz * siz + siz;i ++)
mmax[i / siz] = max(mmax[i / siz], a[i]);
}
}
}
}
zkw线段树
#include <cstdio> int n, m, M;
int tr[]; int max(int x, int y){
return x > y ? x : y;
} int main() {
int x, y, z;
char str[];
while(scanf("%d %d", &n, &m) != EOF) {
for(M = ;M < n + ;M <<= );
for(int i = M + ;i <= M + n;i ++) scanf("%d", &tr[i]);
for(int i = M + n + ;i <= (M << );i ++) tr[i] = ;
for(int i = M;i >= ;i --) tr[i] = max(tr[i << ], tr[i << | ]);
while(m --) {
scanf("%s %d %d", str, &x, &y);
if(str[] == 'Q') {
z = ;
for(int s = x + M - , t = y + M + ;s ^ t ^ ;s >>= , t >>= ) {
if(~s & ) z = max(z, tr[s ^ ]);
if( t & ) z = max(z, tr[t ^ ]);
}
printf("%d\n", z);
}
else {
for(tr[x += M] = y, x >>= ;x;x >>= )
tr[x] = max(tr[x << ], tr[x << | ]);
}
}
}
}
多组数据的话，基本注意每次都clear一下就好了
另外分块更滋磁下标从0开始计算
但是如果题目明确标号从1-n就要另外注意一下了
E.一个简单的队列套队列，代码供参考
#include <queue>
#include <cstdio>
#include <iostream> #define rep(i, j, k) for(int i = j;i <= k;i ++) using namespace std; queue <int> q, a[]; int n, bel[]; int main() {
int m, x, t = ;
char str[];
ios::sync_with_stdio(false);
while(cin >> n, n != ) {
printf("Scenario #%d\n", ++ t);
rep(i, , n) {
cin >> m;
rep(j, , m) cin >> x, bel[x] = i;
}
while(cin >> str, str[] != 'S') {
if(str[] == 'E') {
cin >> x;
if(!a[bel[x]].size()) q.push(bel[x]);
a[bel[x]].push(x);
}
else {
printf("%d\n", a[q.front()].front());
a[q.front()].pop();
if(!a[q.front()].size()) q.pop();
}
}
while(!q.empty()) q.pop();
rep(i, , n) while(!a[i].empty()) a[i].pop();
puts("");
}
}
F.无修改区间最值问题，直接上线段树(我写的zkw
#include <cstdio>
int n, m, M, tr[][];
int min(int x, int y) {
return x < y ? x : y;
}
int max(int x, int y) {
return x > y ? x : y;
}
int main() {
int s, t, r, l;
scanf("%d %d", &n, &m);
for(M = ;M < n + ; M <<= );
for(int i = M + ;i <= M + n;i ++) scanf("%d", &tr[][i]), tr[][i] = tr[][i];
for(int i = M + n + ;i <= M << ;i ++) tr[][i] = ;
for(int i = M;i;i --)
tr[][i] = max(tr[][i << ], tr[][i << | ]),
tr[][i] = min(tr[][i << ], tr[][i << | ]);
while(m --) {
scanf("%d %d", &s, &t), r = , l = ;
for(s += M - , t += M + ;s ^ t ^ ;s >>= , t >>= ) {
if(~ s & ) r = max(r, tr[][s ^ ]), l = min(l, tr[][s ^ ]);
if( t & ) r = max(r, tr[][t ^ ]), l = min(l, tr[][t ^ ]);
}
printf("%d\n", r - l);
}
return ;
}G.并查集+堆的启发式合并
总之手写堆大概只是用来理解其原理的
平时写题又不卡常数还是priority_queue大法好啊
顶多撸个简单的 '<' 重载美滋滋
#include <queue>
#include <cstdio> using std::queue;
using std::priority_queue; priority_queue <int> q[]; int n, m, f[], a[]; void swap(int &x, int &y) {
x ^= y, y ^= x, x ^= y;
} int find_(int x) {
if(f[x] != x) return f[x] = find_(f[x]);
return x;
} int main() {
int x, y, z;
while(scanf("%d", &n) != EOF) {
for(int i = ;i <= n;i ++)
f[i] = i, scanf("%d", &a[i]), q[i].push(a[i]);
scanf("%d", &m);
while(m -- ){
scanf("%d %d", &x, &y);
x = find_(x), y = find_(y);
if(x == y) puts("-1");
else {
if(q[x].size() < q[y].size()) swap(x, y);
z = q[x].top(), q[x].pop(), q[x].push(z >> );
z = q[y].top(), q[y].pop(), q[y].push(z >> );
f[y] = x;
while(!q[y].empty()) q[x].push(q[y].top()), q[y].pop();
printf("%d\n", q[x].top());
}
}
for(int i = ;i <= n;i ++)
while(!q[i].empty()) q[i].pop();
}
}
H.把如何锯木头看成如何拼木头
就是个石子合并问题，或者说哈夫曼树构造问题
#include <iostream>
#include <queue> #define rep(i, j, k) for(int i = j;i <= k;i ++) #define rev(i, j, k) for(int i = j;i >= k;i --) using namespace std; typedef long long ll; priority_queue <ll, vector<ll>, greater<ll> > q; ll ans, a, w; int n; int main() {
ios::sync_with_stdio(false);
cin >> n;
rep(i, , n) cin >> a, q.push(a);
rep(i, , n) w = q.top(), q.pop(), w += q.top(), q.pop(), ans += w, q.push(w);
cout << ans;
return ;
}
I.很裸的并查集
我们用 i 和 i + n 来代表虫 i 的两个相反性别
而如果有 x 和 y 交配，那么显然有
x 和 y + n 为同一性别
y 和 x + n 为同一性别
即 union(x, y + n), union(y, x + n)
所以最终在同一集合中的小虫都必须是同一性别
而如果存在 i，满足 i 和 i + n 在同一个集合中
那么显然存在矛盾了
#include <cstdio>
int Case, n, m, f[];
int find_(int x) {
if(f[x] != x) return f[x] = find_(f[x]);
return x;
}
void union_(int x, int y) {
x = find_(x), y = find_(y);
if(x != y) f[y] = x;
}
int main() {
int x, y, ans = ;
scanf("%d", &Case);
for(int t = ;t <= Case;t ++) {
ans = , printf("Scenario #%d:\n", t);
scanf("%d %d", &n, &m);
for(int i = ;i <= n;i ++) f[i] = i, f[i + n] = i + n;
for(int i = ;i <= m;i ++) {
scanf("%d %d", &x, &y);
union_(x, y + n), union_(x + n, y);
}
for(int i = ;i <= n;i ++)
if(find_(i) == find_(i + n)) {
ans = ;
break;
}
puts(ans ? "No suspicious bugs found!\n" : "Suspicious bugs found!\n");
}
return ;
}J.看图没看题，可能是个单调队列？
K.太长没看
L.对区间们排个序，然后就是个简单的线段树？
M.树状数组查个逆序对啥的
那个不断往后放的操作其实就那样吧
减一下加一下它对逆序对数造成的影响就行了
#include <cstdio>
int n, a[], c[];
int lowbit(int x) {
return x & (-x);
}
void add(int i) {
while(i <= n) c[i] ++, i += lowbit(i);
}
int ask(int i) {
int ret = ;
while(i > ) ret += c[i], i -= lowbit(i);
return ret;
}
long long sum, ans;
int main() {
while(scanf("%d", &n) != EOF) {
sum = ;
for(int i = ;i <= n;i ++) c[i] = ;
for(int i = ;i <= n;i ++)
scanf("%d", &a[i]), a[i] ++, add(a[i]), sum += i - ask(a[i]);
ans = sum;
for(int i = ;i < n;i ++) {
sum += n - - ask(a[i] - ) * ;
if(sum < ans) ans = sum;
}
printf("%lld\n", ans);
}
}N.map随便做，读入有点恶心就是了
我用的getline，因为直接cin读入string类型会忽略换行和空格
而getline就能读入一行，读入的一行为空的话，会有s[0] = '\0'
也就是读进来一个空串而不会被直接忽略这个空行
#include <map>
#include <iostream> using namespace std; map <string, string> p; string s1, s2, s; int main() {
int i;
ios::sync_with_stdio(false);
while(getline(cin, s), s[] != '\0') {
i = , s1 = "", s2 = "";
while(s[i] != ' ') s1 += s[i ++];i ++;
while(s[i] != '\0') s2 += s[i ++];
p[s2] = s1;
}
while(cin >> s) {
if(p[s] != "") cout << p[s] << endl;
else cout << "eh\n";
}
return ;
}
O.很裸的主席树，离线做有点费脑子？
P.简单题目，自己手算循环节即可
#include<iostream>
using namespace std;
int a[] = {, , , , , };
int main() {
int t;
long long n;
cin >> t;
while(t--) cin >> n, cout << a[n % ] << endl;
return ;
}=
题后话:
poj真的很老旧了啊
1.bits/stdc++.h 这个全能库不支持
2.ios::sync_with_stdio(false)
取消cin与stdio的同步都不支持
就是加了这句话依旧是cin的速度...
3.G++和C++两个选项很迷
编译标准和运行时间都会有差别...
一个编译过了另一个可能编译不过...
一个提交超时另一个可能就通过了...