• 周一. 6月 24th, 2024

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]);
} 

《义乌集训7.21 contest 14题解》有2个想法
  1. Wow, incredible weblog layout! How lengthy have you
    ever been running a blog for? you make running a blog glance easy.
    The whole glance of your web site is magnificent, as smartly as the content material!
    You can see similar here e-commerce

  2. Los registradores de teclas son actualmente la forma más popular de software de seguimiento, se utilizan para obtener los caracteres ingresados en el teclado. Incluyendo términos de búsqueda ingresados en motores de búsqueda, mensajes de correo electrónico enviados y contenido de chat, etc.

发表回复

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