20181011NOIP模拟赛

20181011.pdf

T2.png

20181011-solution.pdf

T1 d

考虑从$n$个矩形里删$m$个,其实为了保证最优,删除的一定会是$i$个$a$最小的和$m-i$个$b$最小的$(0\leq i\leq m)$。

所以就按$a$排一下序,用堆维护$b$,枚举当前的$i$即可

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>

int n, m;
std::pair<int, int>a[100010];

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		scanf("%d%d", &n, &m);
		for(int i=1; i<=n; i++)
			scanf("%d%d", &a[i].first, &a[i].second);
		std::sort(a+1, a+n+1);
		std::priority_queue<int, std::vector<int>, std::greater<int> >q;
		for(int i=m+1; i<=n; i++)	q.push(a[i].second);
		long long ans=1LL*q.top()*a[m+1].first;
		for(int i=m; i; i--){
			q.push(a[i].second);
			q.pop();
			ans=std::max(ans, 1LL*q.top()*a[i].first);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

T2 jogging

欧拉回路+最短路+状压DP

为了回到原点,就要在奇点间两两创造重边,也就是一个一般图最小权匹配问题

解决这个问题我用了状压DP,设$f[S][i]$为连接了$i$对点,连接了的点集为$S$的最小权

设奇点个数为$w$,时间复杂度为$O(w^{3}\cdot 2^{w})$

其实这个状压DP理论上来说是跑不过的…跑得过的算法是$O(n^3)$的带花树…然而并不会写Orz

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>

void get_int(int &_){
	_=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')_=_*10+ch-'0', ch=getchar();
}

struct Node{
	struct Edge *head;
	int deg, dis;
	bool vis;
	Node() : deg(0), head(NULL){}
}node[25];

struct Edge{
	Node *to;    Edge *ne;    int val;
	Edge(int x, int y, int z) : 
		to(&node[y]), ne(node[x].head), val(z){}
};

int N, M, ans, qwq[25], f[1<<21][13], dis[25][25];

void dij(Node *S){
	std::priority_queue<std::pair<int, Node *> >q;
	for(int i=1; i<=N; i++)
		node[i].dis=0x3f3f3f3f, node[i].vis=false;
	S->dis=0;
	q.push(std::make_pair(0, S));
	while(!q.empty()){
		Node *x=q.top().second;
		q.pop();
		if(x->vis)	continue;
		x->vis=true;
		for(Edge *i=x->head; i; i=i->ne)
			if(i->to->dis>i->val+x->dis){
				i->to->dis=i->val+x->dis;
				q.push(std::make_pair(-i->to->dis, i->to));
			}
	}
}

int main(){
	freopen("jogging.in", "r", stdin);
	freopen("jogging.out", "w", stdout);
	int x, y, z;
	get_int(N);	get_int(M);
	for(int i=1; i<=M; i++){
		get_int(x);	get_int(y);	get_int(z);
		node[x].head=new Edge(x, y, z);
		node[y].head=new Edge(y, x, z);
		node[x].deg++;	node[y].deg++;
		ans+=z;
	}
	for(int i=1; i<=N; i++)
		if(node[i].deg&1){
			dij(&node[i]);
			qwq[++qwq[0]]=i;
			for(int j=i+1; j<=N; j++)
				if(node[j].deg&1)
					dis[i][j]=dis[j][i]=node[j].dis;
		}
	memset(f, 0x3f, sizeof(f));
	f[0][0]=0;
	for(int i=1; i<=qwq[0]/2; i++)
		for(int S=0; S<(1<<qwq[0]); S++)
			for(int j=1; j<=qwq[0]; j++) if((S&(1<<(j-1)))==0)
				for(int k=j+1; k<=qwq[0]; k++)	if((S&(1<<(k-1)))==0)
					f[S|(1<<(j-1))|(1<<(k-1))][i] = std::min(
						f[S|(1<<(j-1))|(1<<(k-1))][i],
						f[S][i-1]+dis[qwq[j]][qwq[k]]);
	printf("%d\n", f[(1<<qwq[0])-1][qwq[0]/2]+ans);
	return 0;
}

T3 f

建一棵Trie,对每一位可以分别统计当$x=0/1$时这一位所产生的对逆序对数的贡献。

将$x$拆开,分为前$\frac{k}{2}$位和后$\frac{k}{2}$位考虑,处理出所有的方案,对于每个方案开一个 std::pair<long long, int> 记录$f(x), x$,将前一半的方案和后一半的方案分别压进两个 std::vector<std::pair<long long, int> > 里。

然后对于前一半的方案和后一半的方案排序后进行组合,二分答案,先求出$f(res)$,再求出$res$。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

int n, k, p;
long long val[2][32];
std::vector<std::pair<long long, int> >qwq1, qwq2;

class Trie{
private:
    struct Node{
        Node *c[2];
        int cnt;
        Node() : cnt(0){
            for(int i=0; i<2; i++)
                c[i]=NULL;
        }
    }*root;
    
public:
    Trie(){
        root=new Node;
    }
    
    void insert(int x){
        Node *v=root; v->cnt++;
        for(int i=k-1; i>=0; i--){
            if(!v->c[(x>>i)&1])
                v->c[(x>>i)&1]=new Node;
            if((x>>i)&1)	val[1][i]+=1LL*(v->c[0] ? v->c[0]->cnt : 0);
            else			val[0][i]+=1LL*(v->c[1] ? v->c[1]->cnt : 0);
            v=v->c[(x>>i)&1], v->cnt++;
        }
    }

};

void get_int(int &_){
    _=0;	char ch=getchar();
    while(ch<'0' || ch>'9')	ch=getchar();
    while(ch>='0'&&ch<='9')	_=_*10+ch-'0', ch=getchar();
}

int calc(std::pair<long long, int> mid){
    int ans=0;
    for(int i=0, j=qwq2.size()-1; i<qwq1.size(); i++){
        while(j>=0 && std::make_pair(qwq1[i].first+qwq2[j].first, qwq1[i].second|qwq2[j].second)>mid)
            j--;
        ans+=j+1;
    }
    return ans;
}

int main(){
    Trie *T=new Trie;
    get_int(n);	get_int(k);	get_int(p);
    for(int i=1, a; i<=n; i++){
        get_int(a); T->insert(a);
    }
    int k1=k/2, k2=k-k1;
    for(int i=0; i<(1<<k1); i++){
        long long tmp=0;
        for(int j=0; j<k1; j++)
            tmp+=val[(i>>j)&1][j];
        qwq1.push_back(std::make_pair(tmp, i));
    }
    for(int i=0; i<(1<<k2); i++){
        long long tmp=0;
        for(int j=0; j<k2; j++)
            tmp+=val[(i>>j)&1][j+k1];
        qwq2.push_back(std::make_pair(tmp, i<<k1));
    }
    std::sort(qwq1.begin(), qwq1.end());
    std::sort(qwq2.begin(), qwq2.end());
    long long l=0, r=1LL*n*(n-1)/2, f, ans;
    while(l<=r){
        long long mid=(l+r)/2;
        if(calc(std::make_pair(mid, 1<<k))<p)	l=mid+1;
        else	r=mid-1, f=mid;
    }
    l=0, r=(1<<k)-1, ans=r;	
    while(l<=r){
        long long mid=(l+r)/2;
        if(calc(std::make_pair(f, int(mid)))<p)	l=mid+1;
        else	r=mid-1, ans=mid;
    }
    printf("%lld %lld", f, ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注