10月vj刷题

梦里梦外; 2022-12-13 04:44 97阅读 0赞

## A - Trading Business ##

**题意**:n个星球，每个星球m个商品，在每个星球最多买k个物品，  
ai成本，bi售价，ci商品数量。从一个星球买，一个星球卖，求最大利润  
**思路**：枚举从哪个星球买，哪个星球卖（可以在同一个星球）

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<string> 
    #include<queue> 
    #include<cmath>
    #include<map>
    #include<vector> 
    using namespace std;
    typedef long long ll;
    const int inf=0x3f3f3f;
    priority_queue<int>ma;
    priority_queue<int,vector<int>,greater<int> >mi;
    int a[15][110],b[15][110],c[15][110];
    int main()
    { 
    	int n,m,k;
    	string str;
    	cin>>n>>m>>k;
    	for(int i=1;i<=n;i++)
    	{ 
    		cin>>str;
    		for(int j=1;j<=m;j++){ 
    			cin>>a[i][j]>>b[i][j]>>c[i][j];
    		}
    	} 
    	int ans=0,flag[120];
    	//枚举两个买卖的星球 
    	for(int i=1;i<=n;i++)
    	{ 
    		for(int j=1;j<=n;j++)
    		{ 
    			memset(flag,0,sizeof(flag));
    			int temp=k,sum=0;
    			//cout<<"xy"<<i<<j<<endl;
    			while(temp>0)
    			{ 
    				int mans=0,wi=0,fl=0;
    				for(int w=1;w<=m;w++)
    				{ 
    					if(flag[w])continue;//标记已经选择过得商品 
    					//算最大利益 
    					if(b[i][w]-a[j][w]>mans)
    					{ 
    					mans=b[i][w]-a[j][w],wi=w,fl=1;	
    					//cout<<mans<<" q "<<wi<<endl;
    					}
    				}
    				//cout<<mans<<" "<<wi<<endl;
    				if(fl==0)break;//最大利润为0 
    				sum=sum+mans*min(temp,c[j][wi]);
    				temp=temp-min(temp,c[j][wi]);
    				flag[wi]=1;//标记已经选择过得商品 
    				//cout<<sum<<endl;
    			}
    			ans=max(ans,sum); 
    		}
    	}
    	cout<<ans<<endl;
    	return 0;
    }

## B - Snowball ##

**题意**：一个重量为w的雪球在高度为h坡上，同时又两个重量为u1，u2的石头在高度d1，d2处，雪球向下滚，高度减少1，重量就会增加，重量增加的数目为当前高度。并且滚到石头同一高度时，雪球重量会减少，重量减少的数目为石头重量  
**思路**：按照题意，直接从h到0暴力，遇到石头就重量减，重量小于0就变成0

int main()
    { 
    	int h,w,u1,d1,u2,d2;
    	cin>>w>>h;
    	cin>>u1>>d1>>u2>>d2;
    	for(int i=h;i>=0;i--)
    	{ 
    		w=w+i;
    		if(i==d1){ 
    			w=w-u1;if(w<0)w=0;
    		}
    		if(i==d2){ 
    			w=w-u2;if(w<0)w=0;
    		}
    	}
    	cout<<w<<endl;
    	return 0;
    }

## C - Delete from the Left ##

**题意**：给两个字符串，通过删除字符串第一个字符，来让这两个字符串相等，问要执行多少次删除操作  
**思路**：从字符串末尾开始往前枚举

int main()
    { 
    	string s1,s2;
    	cin>>s1>>s2;
    	int l1=s1.length(),l2=s2.length();
    	int i,j;
    	for(i=l1-1,j=l2-1;i>=0&&j>=0;i--,j--)
    	{ 
    		if(s1[i]!=s2[j])break;
    	}
    	cout<<i+j+2<<endl;
    	return 0;
    }

## D - Kind Anton ##

**题意**：  
给定两个长度为n的int数组a，b,值只有-1，0，1。问能否通过操作a\[j\]=a\[j\]+a\[i\]（i<=j）让a和b相等  
**思路**：  
从后往前遍历a，数组，比较与b数组的大小，如果比b大，前面有-1就没问题，如果只有1和0就直接输出no

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int a[101000],b[101000];
    int main()
    { 
    	int t,n,x,y;
    	cin>>t;
    	while(t--)
    	{ 
    		cin>>n;
    		x=y=0;
    		for(int i=1;i<=n;i++)
    		{ 
    			scanf("%d",&a[i]);
    			if(a[i]==1)x++;
    			else if(a[i]==-1)y++;
    		}
    		for(int i=1;i<=n;i++)
    		{ 
    			scanf("%d",&b[i]);
    		}
    		bool flag=true;
    		for(int i=n;i>=1;i--)
    		{ 
    			if(a[i]==1)x--;
    			else if(a[i]==-1)y--;
    			if(a[i]>b[i]){ //a大于b，找是否存在-1 
    				if(y<=0){ 
    					flag=false;break;
    				}
    			}
    			else if(a[i]<b[i]){ //a小于b，找是否存在1 
    				if(x<=0){ 
    					flag=false;break;
    				}
    			}	
    		}
    		if(flag)cout<<"YES"<<endl;
    		else  cout<<"NO"<<endl;
    	}
    	return 0;
    }

## G - Coat of Anticubism ##

**题意**：给定n个杆子的长度，你需要把杆子连接起来，最终只剩下两个杆子，然后再从外界增加一个杆子让这三个杆子可以凑成一个三角形，求增加的杆子最小长度  
**思路**：三角形两边之和大于第三遍，之差小于第三边，求出最小差+1

int a[100010];
    int main()
    { 
        int n;cin>>n;
        for(int i=1;i<=n;i++)
    	scanf("%d",&a[i]);
    	long long b=0;
    	sort(a+1,a+1+n);
    	for(int i=1;i<=n-1;i++)b+=a[i];
    	cout<<a[n]-b+1<<endl;
    	return 0;
    }

## J - Block Adventure ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTkzOTgy_size_16_color_FFFFFF_t_70_pic_center]

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int h[10100];
    int main()
    { 
    	int t,n,m,k;cin>>t;
    	while(t--)
    	{ 
    		cin>>n>>m>>k;
    		bool flag=true;
    		for(int i=1;i<=n;i++)
    		{ 
    			cin>>h[i];
    		}
    		for(int i=1;i<n;i++)
    		{ 
    			if(h[i]>=h[i+1]-k){ //相等可以捡起来k个砖块 
    				int temp=h[i]-h[i+1];
    				m=m+min(temp+k,h[i]);
    			} 
    			else{ 
    				int temp=h[i+1]-h[i];
    				m-=temp-k;
    				h[i]=h[i+1]-k;
    			} 
    			if(m<0)flag=false;
    		}
    		if(flag)cout<<"YES"<<endl;
    		else cout<<"NO"<<endl;
    	}
    	return 0;
     }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTkzOTgy_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/1d8ce125d36c4ec2a9f156b7e512a61d.png