T1
思路
就是先dfs一遍这棵树，先访问根节点，然后访问右孩子，然后左孩子。最后找出这个序列的最长上升子序列
然后一不小心，把第37行的ans写成了a，瞬间爆零
代码
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
ll read() {
ll x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
ll a[N],ans[N],b[N];
int ls[N],rs[N],num;
void dfs(int u) {
ans[++num] = a[u];
if(rs[u]) dfs(rs[u]);
if(ls[u]) dfs(ls[u]);
}
void solve() {
int js = 0;
b[0] = -1e9;
for(int i = 1;i <= num;++i) {
if(ans[i] > b[js]) b[++js] = ans[i];
else {
int k = upper_bound(b + 1,b + js + 1,ans[i]) - b;
b[k] = ans[i];
}
}
cout<<js;
}
int main() {
freopen("point.in","r",stdin);
freopen("point.out","w",stdout);
int n = read();
for(int i = 1;i <= n;++i) a[i] = read();
for(int i = 1;i <= n;++i) ls[i] = read(),rs[i] = read();
dfs(1);
solve();
return 0;
}
T2
50分思路
直接按照题意交换，然后归并排序或者树状数组找一下逆序对
100分思路
考虑怎样做到\(10^9\)。可以发现，其实数列中有用的数只有交换的那些数，对于中间的这些数只要找出一个元素来代替，并且给他赋个权值，表示在这个区间内有多少个数就可以了。这样就变成了N*3个数，就可以和五十分一样的方法做了
50分代码
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
map<int,int>ma;
ll read() {
ll x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0'&& c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
struct node {
int l,r;
}Q[N];
int n;
namespace BF1 {
int a[N],tmp[N];
ll ans = 0;
void mul_sort(int l,int r) {
if(l >= r) return;
int mid = (l + r) >> 1;
mul_sort(l,mid);mul_sort(mid+1,r);
int L = l,R = mid+1;
int js = l;
while(L <= mid && R <= r) {
if(a[L] <= a[R]) tmp[js++]=a[L++];
else {
ans += mid - L + 1;
tmp[js++] = a[R++];
}
}
while(L <= mid) {
tmp[js++] = a[L++];
}
while(R <= r) {
tmp[js++] = a[R++];
}
for(int i = l;i <= r;++i) a[i] = tmp[i];
}
void Main(int m) {
for(int i = 1;i <= m;++i) a[i] = i;
for(int i = 1;i <= n;++i) swap(a[Q[i].l],a[Q[i].r]);
// for(int i = 1;i <= m;++i) printf("%d ",a[i]);
mul_sort(1,m);
cout<<ans;
}
}
int main() {
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
n = read();
int Max = -1;
for(int i = 1;i <= n;++i) {
Q[i].l = read(),Q[i].r = read();
Max = max(Max,max(Q[i].l,Q[i].r));
}
BF1::Main(Max);
return 0;
}
100分代码
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
map<int,int>ma;
ll read() {
ll x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0'&& c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
struct node {
int l,r;
}Q[N];
int n;
namespace BF2 {
int ls[N * 4],W[N * 4],tot = 0,a[N * 4],tmp[N * 4];
ll ans = 0;
void lisan() {
int num = 0;
for(int i = 1;i <= n;++i) {
ls[++num] = Q[i].l,ls[++num] = Q[i].r;
}
sort(ls + 1,ls + num + 1);
int now = 0;
for(int i = 1;i <= num;++i) {
if(ls[i] == ls[i - 1]) continue;
if(ls[i] - ls[i-1] > 1) {
a[++tot] = tot;
W[tot] = ls[i] - ls[i - 1] - 1;
}
a[++tot] = tot;
ma[ls[i]] = tot;
W[tot] = 1;
}
for(int i = 1;i <= n;++i) {
Q[i].l = ma[Q[i].l];
Q[i].r = ma[Q[i].r];
}
}
void mul_sort(int l,int r) {
if(l >= r) return;
int mid = (l + r) >> 1;
mul_sort(l,mid);
mul_sort(mid + 1,r);
ll WW = 0;
for(int i = l;i <= mid;++i) WW += W[a[i]];
int L = l,R = mid + 1,js = l;
while(L <= mid && R <= r) {
if(a[L] <= a[R]) {
WW -= W[a[L]];
tmp[js++] = a[L++];
}
else {
ans += WW * W[a[R]];
tmp[js++] = a[R++];
}
}
while(L <= mid) {
tmp[js++] = a[L++];
}
while(R <= r) {
tmp[js++] = a[R++];
}
for(int i = l;i <= r;++i) a[i] = tmp[i];
}
void Main() {
lisan();
for(int i = 1;i <= n;++i) swap(a[Q[i].l],a[Q[i].r]);
mul_sort(1,tot);
cout<<ans;
}
}
int main() {
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
n = read();
if(n == 1) {
int x = read(),y = read();
if(x > y) swap(x,y);
cout<< y * 2 - x * 2 - 1;
return 0;
}
int Max = -1;
for(int i = 1;i <= n;++i) {
Q[i].l = read(),Q[i].r = read();
Max = max(Max,max(Q[i].l,Q[i].r));
}
BF2::Main();
return 0;
}
T3
30分思路
每次按照要求将点染色，然后统计联通块个数就可以了。
100分思路
考虑将x染为y时，先将x从树里面拿出来，然后染色，然后重新放回去。在合并的时候，考虑让个数比较小的块加入到个数比较大的块中，舍得复杂度变为\(O(能过)\)
30分代码
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 200000 + 100;
ll read() {
ll x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0'&& c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int col[N],pnt[N],block[N],nbok,a[N];
struct node {
int v,nxt;
} e[N * 2];
int ans;
int head[N],ejs,num[N];
void add(int u,int v) {
e[++ejs].v = v;
e[ejs].nxt = head[u];
head[u] = ejs;
}
queue<int>q1,q2,q;
int vis[N];
int bfs(int U) {
while(!q.empty()) q.pop();
q.push(U);
vis[U] = 1;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if(vis[v]) continue;
if(a[v] == a[u] ) {
q.push(v);
vis[v] = 1;
}
}
}
}
int main() {
freopen("simulator.in","r",stdin);
freopen("simulator.out","w",stdout);
int n = read(),q = read();
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 1; i < n; ++i) {
int u = read(),v = read();
add(u,v);
add(v,u);
}
while(q--) {
int x = read(),y = read();
for(int i = 1; i <= n; ++i) {
if(a[i] == x) a[i] = y;
}
ans = 0;
memset(vis,0,sizeof(vis));
for(int i = 1; i <= n; ++i) {
if(!vis[i]) {
ans++;
bfs(i);
}
}
printf("%d\n",ans);
}
return 0;
}
100分代码
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
const int N = 300000 + 10;
vector<int>son[N];
vector<int>to[N];
ll read() {
ll x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int id[N],cor[N],siz[N];
int ans = 1;
void dfs(int u,int father) {
for(int i = 0;i < son[u].size();++i) {
int v = son[u][i];
if(v == father) continue;
if(cor[v] != cor[u]) ans++;//孩子与父亲颜色不同，证明有新块
dfs(v,u);
}
}
void del(int x) {
for(int i = 0;i < son[x].size();++i) {
int v = son[x][i];
if(cor[v] != cor[x]) ans--;//以前颜色不同，现在颜色相同了，将ans--
}
}
void ins(int x) {
for(int i = 0;i < son[x].size();++i) {
int v = son[x][i];
if(cor[v] != cor[x]) ans++;//重新加入后颜色变得不同了，将ans++
}
}
//cor表示当前点的颜色，id[x]表示x这个颜色的真实颜色。
//to[x]表示所有颜色为x的点。siz[x]表示颜色为x的点的个数
int main() {
freopen("simulator.in","r",stdin);
freopen("simulator.out","w",stdout);
int n = read(),Q = read();
for(int i = 1;i <= n;++i) {
cor[i] = read();id[cor[i]] = cor[i];
to[cor[i]].push_back(i);siz[cor[i]]++;
}
for(int i = 1;i < n;++i) {
int u = read(),v = read();
son[u].push_back(v);son[v].push_back(u);
}
son[1].push_back(0), cor[0] = 0x3e3e3e3e;
dfs(1,0);//处理出一开始有多少联通块
while(Q--) {
int x = read(),y = read();
int y_ = y,x_ = x;
x = id[x],y = id[y];
id[x_] = 0;//x被合并之后消失
if(siz[x] > siz[y]) swap(x,y);//按照包含元素的大小合并
id[y_] = y;//y的颜色将变为块比较大的那个颜色
for(int i = 0;i < to[x].size();++i) {
int v = to[x][i];
del(v);//删除颜色为x的点
to[y].push_back(v);//加入到颜色为y的点中去
siz[y]++;
siz[x]--;
}
for(int i = 0;i < to[x].size();++i)
cor[to[x][i]] = y; //将颜色为x的点重新染色
for(int i = 0;i < to[x].size();++i)
ins(to[x][i]);//将原来颜色为x的点重新加入到树中
to[x].clear();//颜色为x的点消失
printf("%d\n",ans);
}
return 0;
}
总结
期望得分100 + 100 + 30 = 230
实际得分0 + 100 + 30 = 130
再手误就剁手！！！
一言
人的一生会遭遇各种各样的事，其中有令人难以置信的事，也有不讲道理的事，但这就是生活。 ——地狱少女
