• 周日. 11月 27th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

义乌集训7.21 contest 14题解

admin

11月 28, 2021

2021.7.19 Contest 题解

T1:

Description:

​ 小A来到了一个商店,商店内有 (n) 件物品,每件物品有一个售价 (A_i) ,小A是一个奸商,因此他能够把每件物品以 (B_i) 的价格卖出。

​ 而由于小A背包空间有限,他只能买走恰好一件商品。而小A每次购买之后,小B将有可能将小A的物品摧毁,此时小A必须继续购买,并且商店不会返还购买这件物品的钱。小B至多可以摧毁 (m) 件物品。

​ 小A的目标是最大化自己的收益。

​ 小B的目标是最小化小A获得的收益,即卖出的商品所得减去购买所有物品的总花费。

​ 注意到任何时刻小B都可以选择不将小A手中的物品摧毁,这样小A就必须立刻带着这件物品离开商店。

Input:

​ 第一行一个数 (T) ,代表数据组数

​ 每组第一行两个数 (n,m) ,分别表示物品数目和小B可摧毁的物品数量。

​ 之后 (m) 行,每行两个数 (A_i,B_i)

Output:

​ 对于每组数据,输出一个数表示小A最终能获得的收益,由于小A可以直接走出商店(什么都不买),这个收益显然是非负的。

Sample1 Input:

2
3 1
1 3
10 30
10 30
3 0
1 3
10 30
100 130

Sample1 Output:

10
30

Hint:

​ 对于 (100\%) 的数据,(0 leq m <nle10^5,1 leq A_i,B_i leq 10^9,mleq 20,sum{n} leq 3 imes 10^5)

题目分析:

​ 考虑二分一个答案 (mid),也就是说一开始满足 (B_i-A_i geq mid) 的物品小A会去买,小B也会去销毁;到了第二次时,需要满足 (B_j-A_j geq mid+A_i) 小A才会去买,小B也会去销毁……一直到小B无法销毁同时仍有满足要求的 (B_k-A_k)

​ 我们考虑贪心,若 (B_i-A_i geq mid)(B_j-A_j geq mid),肯定会先购买 (B) 较小的,然后再购买 (B) 较大的。证明显然,如果先选 (j),则再选 (i) 需要满足 (B_i-A_i geq mid+A_j) ;而先选 (i),再选 (j) 需要满足 (B_j-A_j geq mid+A_i) ,移项可得,一个是 (B_i geq mid+A_j+A_i),另一个是 (B_j geq mid+A_i+A_j) ,那么显然先拿 (B) 较小的肯定更优。

​ 在确定了选择顺序之后我们就可以DP了,设 (f_{i,j}) 表示枚举到第 (i) 个物品,小B销毁了 (j) 次,此时所需的 (B_i-A_i) 的最小值,然后我们就能在 (O(nmlogV)) 的复杂度内解决这道题。

​ 当然,不用二分直接DP的做法也行,留给读者思考。

代码如下(马蜂很丑,不喜勿喷)——

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define N 100005
#define LL long long
#define inf 2147483647
using namespace std;
int T,n,m,Max,rk[N],a[N],b[N],f[25]; inline bool cmp(int x,int y){if(b[x]^b[y]) return b[x]<b[y];return a[x]<a[y];} inline bool check(int x){
	f[0]=x;for(register int i=1;i<=m;i++) f[i]=inf;for(register int i=1;i<=n;i++) 
	for(register int j=m;j;j--) if(b[rk[i]]-a[rk[i]]>=f[j-1]) f[j]=min(f[j],a[rk[i]]+f[j-1]);return f[m]^inf;
//	int now=x,K=m;for(register int i=1;i<=n;i++) if(b[rk[i]]-a[rk[i]]>=now) if(!K) return 1;else K--,now+=a[rk[i]];return 0;
} 
//inline bool cmp2(int x,int y){if(a[x]^a[y]) return a[x]<a[y];return b[x]<b[y];}
//inline bool cmp3(int x,int y){return a[x]+b[x]<a[y]+b[y];}
struct FastIO{
	static const int S=1048576;
	char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
	FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
	template<typename T>FastIO& operator >> (T&ret){
		ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
	}
	FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
	template<typename T>FastIO& operator << (T x){
		if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
		while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
//	freopen("a.in","r",stdin);freopen("a.ans","w",stdout);
	fin>>T;while(T--){
		fin>>n>>m,m++,Max=0;for(register int i=1;i<=n;i++) fin>>a[i]>>b[i],Max=max(Max,b[i]-a[i]),rk[i]=i;
		sort(rk+1,rk+n+1,cmp);int l=0,r=Max,ans=0;while(l<=r){int mid=l+r>>1;if(check(mid)) ans=max(ans,mid),l=mid+1;else r=mid-1;}fout<<ans<<'
';
//		sort(rk+1,rk+n+1,cmp2);l=ans+1,r=Max;while(l<=r){int mid=l+r>>1;if(check(mid)) ans=max(ans,mid),l=mid+1;else r=mid-1;}
//		sort(rk+1,rk+n+1,cmp3);l=ans+1,r=Max;while(l<=r){int mid=l+r>>1;if(check(mid)) ans=max(ans,mid),l=mid+1;else r=mid-1;}fout<<ans<<'
';
	}
	return 0;
}
//21224751

T2:

Description:

​ 小A有一张无向图 (G(x)),图中每条边的权值可以表达为 (ax+b),现在小A想知道对于在 ([l,r]) 之间的每一个 (x),使得这张图的最小生成树最大的那一个 (x),所对应的最小生成树的权值是多少。

Input:

​ 第一行两个数 (n,m),分别表示点数和边数。

​ 之后 (m) 行,每行四个数 (x,y,a,b),表示一条边的端点和边权 ((ax+b))

​ 最后一行两个整数 (l,r)

Output:

​ 一个实数(保留三位小数),代表最小生成树的最大值。

Sample1 Input:

3 3
1 2 1 10
2 3 10 10
3 1 100 10
-23 23

Sample1 Output:

273.000

Hint:

对于 (100\%) 的数据,(n<mle10^5)(-10^9le lle rle10^9)(|a_i|,|b_i|le 10^5),保证图是联通的。

对于 (20\%) 的数据,(r-lle10)

对于另外 (10\%) 的数据,(a_i=0)

对于另外 (30\%) 的数据,(n,mle10^3)(|a_i|le1)

题目分析:

​ 对于图中的每一棵生成树,它的权值是关于 (x) 的一次函数,那么原问题实际上是求对于每个 (x) 在若干个函数中取最小值从而得到一个新的上凸函数,我们要求这个函数在 ([l,r]) 中的最大值,这个问题显然可以三分,然后这道题就结束了。

​ 具体实现的时候需要注意精度、边界以及常数等一系列问题。

代码如下(马蜂很丑,不喜勿喷)——

#include<bits/stdc++.h>
#define N 100005
#define DB double
#define LL long long
#define eps 1e-7
using namespace std;
int n,m,X[N],Y[N],A[N],B[N],f[N];double ans,l,r;
struct node{int x,y;DB v;}p[N];inline bool cmp(const node x,const node y){return x.v<y.v;} inline int gf(int x){return f[x]==x?x:f[x]=gf(f[x]);} inline DB get(DB xx){
	for(register int i=1;i<=n;i++) f[i]=i;for(register int i=1;i<=m;i++) p[i].x=X[i],p[i].y=Y[i],p[i].v=1.0*A[i]*xx+1.0*B[i];sort(p+1,p+m+1,cmp);
	DB res=0;for(register int i=1;i<=m;i++){int x=p[i].x,y=p[i].y,fx=gf(x),fy=gf(y);if(fx==fy) continue;res+=p[i].v,f[fx]=fy;}return res;
}
struct FastIO{
	static const int S=1048576;
	char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('
');}
	FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='
');return *this;}
	template<typename T>FastIO& operator >> (T&ret){
		ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
	}
	FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='
'){*(s+Len)=ch;Len++;ch=nc();}}
	template<typename T>FastIO& operator << (T x){
		if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
		while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
int main(){
	fin>>n>>m;for(register int i=1;i<=m;i++) fin>>X[i]>>Y[i]>>A[i]>>B[i];fin>>l>>r;ans=-214748364777777777;while(r-l>eps)
	{DB mid1=(2.0*l+r)/3.0,mid2=(l+2.0*r)/3.0;if(get(mid1)<=get(mid2)) l=mid1;else r=mid2;}ans=max(ans,max(get(l),get(r)));printf("%0.3lf
",ans);return 0;
}

T3:

Description:

​ 在计算机编译原理中,我们可以了解到上下文无关文法(CFG)这一概 念,我们可以用几个集合来代表一个文法,如语法 (G = (V,S,P,T))(V) 代表文法词汇表,其中 (S) 代表开始符号的集合,(P) 代表生成式的集合,(T) 代表终止符号的集合。

​ CFG 的工作流程可以这样描述:对于一个由词汇表 (T) 中的词汇构成的句子,可以按照生成式进行展开。如当 (V = {a,b,c,0}),开始符集 (S = {a}),结束符集 (T = {0}),生成式集有如下

(P = {a o bc,b o cc,c o 0,c o b})

​ 当我们输入字符串 (abb)b 时,文法分析检测到开始符,对应生成式可以推导出

(abb o bcbb o ccccccc o 0000000)

​ 此时,通过生成式展开的式子只具有终止符,我们就认定文法分析结束,当然,我们的推导也可以为

(abb o bcbb o ccccccc o bbbbbbb o …)

​ 这样无限推导下去,可以得到任意长度的式子,但是当我们输入 (0a0) 时,发现句首句尾的终止符不会发生变化,不能由终止符推导出其他式子,我们称其为上下文无关文法,也就是说我们定义的生成式 (s_1 o s_2) 中,(s_1
otin T)

​ 我们给出此题的语法 (G = (V,S,P,T)),其中 (V = {A-Z,0,1}),即 (26) 个大写英文字母与 (0, 1) 两个数字;(T={0,1,}),即终止符为 (0, 1) 和空(长度为 (0) 的字符串)三种情况。我们认定,当推导出的式子中只剩 (0, 1) 或什么也没有时,文法分析结束。其开始符 (S={S}) ,即开始符只有 (S) 这个字母;(P) 包含的 (n) 个生成式则由测试数据给出。

​ 现在,Archies只输入了开始符 (large S),他想知道在文法分析结束后,由生成式推导出的式子(字符串)的前 (k) 个字符有多少种不同的可能,特别的,当式子的长度不超过 (k) 时,也视为一种合法的情况,请你解决Archies的疑问,并输出这些长度不超过 (k) 的前缀。

Input:

​ 第一行两个整数 (n,k),其意义见题目描述。

​ 接下来 (n) 行,每行一个生成式,其形式为 (s_1 o s_2) ,保证 (s_1) 不为 (0,1) 或空,保证 (s_2) 的长度不会超过 (10)

Output:

​ 输出第一行一个整数 (c),代表所有合法情况的数量。

​ 之后 (c) 行,每行一个长度不超过 (k) 的字符串,你可以按任意顺序输出这些字符串。你可以输出字符串 eps 代表一个空串。

Sample1 Input:

2 3
S->0S1S
S->

Sample1 Output:

5
eps
01
000
001
010

Hint:

data range:

对于 (100\%) 的数据,(n le 200,k le 7)

题目分析:

​ 考虑每个字符能变成什么,直接模拟这一个过程。。。

标程代码如下(马蜂很丑,不喜勿喷)——

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <string>
#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
typedef long long LL;
using namespace std;
const int N = 26;

inline void judge()
{
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
}

int n , K;
char str[N];
vector<string> trans[N];
vector<int> prefix[N];
bool vis[26][1 << 8];
 
bool isrow(char *s) {
    while (*s) {
        if (!isdigit(*s ++))
            return 0;        
    }
    return 1;
}
 
string itos(int x) {
    string s = "";
    while (x > 1) {
        s += (x & 1) + '0';
        x >>= 1;
    }
    reverse(s.begin() , s.end());
    return s;
}
int Stoi(string s) {
    int x = 1;
    for (int i = 0 ; i < s.size() && i < K ; ++ i)
        x = x << 1 | s[i] - '0';
    return x;
}
 
int cat(int A , int B) {
    int begin = -1;	
    for (int i = K ; i >= 0 ; -- i)
        if (B >> i & 1) {
            begin = i;
            break;
        }
    while (begin > 0) {
        int tmp = A << 1 | (B >> (-- begin) & 1);
        if (tmp >= 1 << K + 1)
            break;
        A = tmp;
    }
    return A;
    string C = itos(A) + itos(B);
    if (C.size() > K)
        C = C.substr(0 , K);
    return Stoi(C);
}
 
int main() {
	judge();
    scanf("%d%d
" , &n , &K);
    //puts("233");
    for (int i = 0 ; i < n ; ++ i) {
        scanf("%s" , str);
        int c = *str - 'A';
        trans[c].push_back(str + 3);
        if (isrow(str + 3)) {
            int num = Stoi(str + 3);
            if (!vis[c][num]) {
                vis[c][num] = 1;
                prefix[c].push_back(num);
            }
        }
    }
    int mask = 1 << K + 1;
    while (1) {
        bool changed = 0;
        for (int i = 0 ; i < 26 ; ++ i) {
            for (auto &t : trans[i]) {
                static bool Hash[2][1 << 8];
                int cur = 0 , nxt = 1;
                memset(Hash[cur] , 0 , sizeof(Hash[cur]));
                Hash[cur][1] = 1;
                for (auto &ch : t) {
                    memset(Hash[nxt] , 0 , sizeof(Hash[nxt]));
                    for (int j = 1 ; j < mask ; ++ j) {
                        if (!Hash[cur][j])
                            continue;
                        if (ch == '0') {
                            Hash[nxt][cat(j , 2)] = 1;
                        } else if (ch == '1') {
                            Hash[nxt][cat(j , 3)] = 1;
                        } else {
                            for (auto &s : prefix[ch - 'A'])
                                Hash[nxt][cat(j , s)] = 1;
                        }
                    }
                    swap(cur , nxt);
                }                
                for (int s = 1 ; s < mask ; ++ s) {
                    //cout << s << endl;
                    if (Hash[cur][s] && !vis[i][s]) {
                        changed = 1;
                        vis[i][s] = 1;
                        prefix[i].push_back(s);
                    }
                }
            }
        }
        if (!changed)
            break;
    }
    cout << prefix['S' - 'A'].size() << endl;
    for (auto &s : prefix['S' - 'A']) {
        if (s == 1)
            cout << "eps" << endl;
        else
            cout << itos(s) << endl;
    }    
    return 0;
}

T4:

Description:

​ Solo生成了一个一条长度为 (n) 的链,链上的点标号 (1)(n),其中 (i) 号点和 (i + 1) 号点之间的边的权值为 (A_i)

​ 现在Solo决定从中删除 (k) 条两两之间没有公共点的子链(长度可以为 (0),即一个单独的节点),使得这 (k) 条链上涵盖的边的边权和最大。

Input:

​ 第一行两个整数 (n,k),其意义见题目描述。

​ 第二行 (n – 1) 个整数,其中第 (i) 个整数代表第 (i) 条边的 (A_i)

Output:

​ 第一行一个整数代表最大值;

​ 接下来 (k) 行每行两个数,表示最大值对应的方案中选出的条链的起点和终点。

Sample1 Input:

9 4
-10 2 1 3 6 -2 17 1

Sample1 Output:

29
1 1
2 6
7 8
9 9

Hint:

对于 (100\%) 的数据,(|Ai| lt 10^5,k le n le 100000)

题目分析:

​ 正解应该是WQS二分,然而博主没写出来,暂时先咕咕了QAQ(也许会永远咕下去

代码如下(马蜂很丑,不喜勿喷)——

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N=100005;
const ll inf=1e12;
ll n,i,j,K,p,l,t,a[N],s[N];
ll f[N][2],L[N][2],R[N][2];
ll tot,ansl[N],ansr[N],ans;
inline void read(ll &x)
{
	x=0; ll ff=1; char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') ff=-1,ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x*=ff;
}
void update(ll x,ll v)
{
	f[x][0]=f[x-1][0];
	f[x][0]=max(f[x][0],f[x-1][0]-v);
	f[x][0]=max(f[x][0],f[x-1][1]+a[x-1]);
	f[x][1]=f[x-1][0]-v;
	f[x][1]=max(f[x][1],f[x-1][1]+a[x-1]);
	L[x][0]=inf; R[x][0]=-1;
	L[x][1]=inf; R[x][1]=-1;
	
	if (f[x][0]==f[x-1][0]) L[x][0]=min(L[x][0],L[x-1][0]),R[x][0]=max(R[x][0],R[x-1][0]);
	if (f[x][0]==f[x-1][1]+a[x-1]) L[x][0]=min(L[x][0],L[x-1][1]),R[x][0]=max(R[x][0],R[x-1][1]);
	if (f[x][0]==f[x-1][0]-v) L[x][0]=min(L[x][0],L[x-1][0]+1),R[x][0]=max(R[x][0],R[x-1][0]+1);
	
	if (f[x][1]==f[x-1][0]-v) L[x][1]=min(L[x][1],L[x-1][0]+1),R[x][1]=max(R[x][1],R[x-1][0]+1);
	if (f[x][1]==f[x-1][1]+a[x-1]) L[x][1]=min(L[x][1],L[x-1][1]),R[x][1]=max(R[x][1],R[x-1][1]);
}
void Dp(ll x)
{
	ll i;
	f[0][0]=0; L[0][0]=0; R[0][0]=0;
	f[0][1]=-inf; L[0][1]=-1; R[0][1]=-1;
	for (i=1;i<=n;i++) update(i,x);
}
ll find0(ll x,ll NK,ll v)
{
	//printf("%lld %lld %lld %lld
",x,f[x][0],f[x-1][0]-v,v);
	if (f[x][0]==f[x-1][0]&&NK>=L[x-1][0]&&NK<=R[x-1][0]) return 1;
	else if (f[x][0]==f[x-1][0]-v&&NK>=L[x-1][0]+1&&NK<=R[x-1][0]+1) return 2;
	else if (f[x][0]==f[x-1][1]+a[x-1]&&NK>=L[x-1][1]&&NK<=R[x-1][1]) return 3;
	return -1;
}
ll find1(ll x,ll NK,ll v)
{
	if (f[x][1]==f[x-1][0]-v&&NK>=L[x-1][0]+1&&NK<=R[x-1][0]+1) return 1;
	else if (f[x][1]==f[x-1][1]+a[x-1]&&NK>=L[x-1][0]&&NK<=R[x-1][0]) return 2;
	return -1;
}
void get(ll K,ll v)
{
	ll i;
	ll NK=K,op=0;
	for (i=n;i>=1;i--)
	{
		ll A=-1;
		if (op==0) 
		{
			A=find0(i,NK,v);
			//printf("%lld %lld %lld
",i,op,A);
			if (A==1) op=0;
			else if (A==2) ansl[++tot]=i,ansr[tot]=i,NK--,op=0;
			else op=1,ansr[++tot]=i;
		}
		else 
		{
			A=find1(i,NK,v);
			//printf("%lld %lld %lld
",i,op,A);
			if (A==1) ansl[tot]=i,NK--,op=0;
			else op=1;
		}
	}
}
int main()
{
	freopen("d.in","r",stdin);
	freopen("d.out","w",stdout);
	read(n); read(K);
	//printf("%lld %lld
",n,K);
	for (i=1;i<=n-1;i++) read(a[i]),s[i+1]=s[i]+a[i];
	//for (i=1;i<=n-1;i++) printf("%lld ",a[i]); printf("
");
	ll l=-1e12,r=1e12;
	while (l<=r)
	{
		ll mi=(l+r)>>1;
		Dp(mi); 
		//printf("%lld
",mi);
		if (K>=L[n][0]&&K<=R[n][0])
		{
			//printf("%lld %lld %lld 
",K,L[n][0],R[n][0]);
			ans=f[n][0]+K*mi;
			get(K,mi);
			break;
		}
		else if (K>R[n][0]) r=mi-1;
		else l=mi+1;
	}
	printf("%lld
",ans);
	for (i=1;i<=tot;i++) printf("%lld %lld
",ansl[i],ansr[i]);
	//printf("%lld %lld
",s[89253]-s[2430],s[100000]-s[1]);
} 

发表回复

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