Acwing.第137场周赛

比赛地址
寒假回家第一场周赛，明天正式开始加训

A.小写字母数量

思路：

简单的模拟，统计一下小写字母的数量而已

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=12;
char a[N][N];
char b[N][N];

void solve(){
	string s;
	cin>>s;
	int ans=0;
	
	for(int i=0;i<s.size();i++){
		if(s[i]>='a'&&s[i]<='z'){
			ans++;
		}
	}
	cout<<ans<<endl;
	return ;


}
signed main(){

	int t=1;
	while(t--){
		solve();
	}
	return 0;

}

B.最多的布丁

题目

思路：

看题，d是数据范围最小的，所以d就是一个突破口，一开始我以为是二分，事实上根本不需要这么麻烦，我们只需要枚举一下贝茜被分到的次数就可以了

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,m,d;

void solve(){
    // int n,k,m,d;
    cin>>n>>k>>m>>d;
    int x=0;
    int ans=-1;
    
    for(int i=1;i<=d;i++){
        int x=n/(k*i-k+1);
        if(x==0){
            break;
        }
        x=min(x,m);
        ans=max(ans,x*i);
    }
    cout<<ans<<endl;
    return ;
}
signed main(){
    int t=1;
    while(t--){
        solve();

    }
    return 0;

}

C.收集饰品

题目

思路：

动态规划问题

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1010,M=2*N,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;

const long long inf=2e18;
using node=tuple<int,int,int,int>;
int n,m;
int k[N],x[N];
vector<int> b[N];
int c[N]; 
int id[N];
vector<int> g[N];
int d[1<<20];
int f[1<<20];
void solve()
{
    int b;
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++)
    {
        int cnt;
        cin>>x[i]>>k[i]>>cnt;
        id[i]=i;
        for(int j=1;j<=cnt;j++)
        {
            int y;
            cin>>y;
            c[i]|=1<<(y-1);
        }
    }
    sort(id+1,id+1+n,[&](const auto&p,const auto&q){
        return k[p]<k[q]; 
    });

    vector<int> f(1<<m,inf);
    f[0]=0;
    int res=inf;
    for(int i=1;i<=n;i++){
        int p=id[i];
        int tans=k[p]*b;
        for(int j=0;j<1<<m;j++){
            int state=c[p]|j;
            f[state]=min(f[state],f[j]+x[p]);
        }
        if(f[(1<<m)-1]!=inf) res=min(res,f[(1<<m)-1]+tans);
    }
    if(res>=inf) res=-1;
    cout<<res;

}

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
    //init();
    //cin>>t;
    while(t--) solve();
}

#作者：南岸以南南岸哀
#链接：https://www.acwing.com/solution/content/220428/
#来源：AcWing
#著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。