B
?智乃买瓜
题意：水果摊上贩卖着N个不同的西瓜，第i个西瓜的重量为wi，对于每个瓜都可以选择买一个整瓜或者把瓜劈开买半个瓜或者不买，半个瓜的重量为wi/2。求出购买瓜的重量和为1~m的方案数。
思路：背包问题，dp[i][j]表示考虑前i个瓜的情况下，购买瓜的重量和为j的方案数。
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int maxx = 1e3 + 10;
const int p=1e9+7;
ll n,m;
ll w[maxx][2];
ll dp[maxx][1000010];
bool vis[maxx];
void solve()
{
dp[0][0]=1;
scanf("%lld %lld",&n,&m);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&w[i][0]);
w[i][1]=w[i][0]/2;
//for(ll i=0;i<=n;i++) dp[i][0]=1;
for(ll j=0;j<=m;j++)
{
dp[i][j+w[i][0]]=(dp[i-1][j]+dp[i][j+w[i][0]])%p;
dp[i][j+w[i][1]]=(dp[i-1][j]+dp[i][j+w[i][1]])%p;
dp[i][j]=(dp[i-1][j]+dp[i][j])%p;
}
}
for(ll i=1;i<=m;i++)
{
if(i==m) printf("%lld",dp[n][i]%p);
else printf("%lld ",dp[n][i]%p);
}
}
signed main()
{
int _t=1;
//scanf("%d", &_t);
while (_t--)
{
solve();
}
system("pause");
}
dp[i][j]=dp[i?1][j?wi?]+dp[i?1][j?wi/2??]+dp[i?1][j]?
优化成一维：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e3 + 10;
const int p=1e9+7;
ll n,m,x;
ll dp[maxx];
bool vis[maxx];
void solve()
{
dp[0]=1;
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
for(int j=m;j>=0;j--)
{
if(j>=x/2) dp[j]=(dp[j]+dp[j-x/2])%p;
if(j>=x) dp[j]=(dp[j]+dp[j-x])%p;
}
}
for(int i=1;i<=m;i++)
{
printf("%d%c",dp[i]," \n"[i==m]);
}
}
signed main()
{
int _t=1;
//scanf("%d", &_t);
while (_t--)
{
solve();
}
system("pause");
}
D
智乃的01串打乱
思路：找到第一个0和第一个1交换即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e6 + 10;
const int ma=1e9+10;
int n;
string s;
bool vis[maxx];
char& f(char x)
{
for(int i=0;i<n;i++)
{
if(s[i]==x) return s[i];
}
}
void solve()
{
cin>>n;
cin>>s;
int flag=0;
swap(f('0'),f('1'));
cout<<s<<'\n';
}
int main()
{
int _t=1;
//scanf("%d", &_t);
while (_t--)
{
solve();
}
system("pause");
}
E
智乃的数字积木(easy version)
题意：给定n块积木，每块积木上有颜色和数字，可以将颜色相同且相邻的积木进行无限次交换，给定k次操作，每次操作都选中两种颜色P,Q，然后将所有颜色为P的积木染成颜色Q。输出进行0~k次操作后，积木可以组成的最大数。
思路：按照题目模拟。先按照颜色将数组分段并从大到小排序。
数组切段：
for(int l=1,r=1;l<=n;l=r+1,r=l)
{
while(r<n&&color[r+1]==color[l]) r++;
printf("[%d %d]",l,r);
}
lambda:
sort需要传排序函数的时候，如果cmp函数没有重复利用的必要，可以使用匿名函数在调用sort函数时直接定义。
比如int数组从大到小排序可以这样写：
sort(a + 1, a + 1 + n, [](const int&A, const int&B) {
return A > B;
});
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e5 + 10;
const int p=1e9+7;
int n,m,k;
char s[maxx];
int color[maxx];
void modify(int from, int to)//颜色更新
{
for(int i=1;i<=n;i++)
{
if(color[i]==from) color[i]=to;
}
return ;
}
ll cal()
{
for(int l=1,r=1;l<=n;l=r+1,r=l)//按颜色切断并排序
{
while(r<n&&color[r+1]==color[l]) r++;
sort(s+l,s+r+1,[](const char&A,const char&B){
return A>B;
});
}
ll ret=0;//计算结果
for(int i=1;i<=n;i++)
{
ret=ret*10+(s[i]-'0');
ret%=p;
}
return ret;
}
void solve()
{
scanf("%d %d %d",&n,&m,&k);
scanf("%s",s+1);
for(int i=1;i<=n;i++) scanf("%d",&color[i]);
printf("%lld\n",cal());
while (k--)
{
int u,v;
scanf("%d %d",&u,&v);
modify(u,v);
printf("%lld\n",cal());
}
}
int main()
{
int _t=1;
//scanf("%d", &_t);
while (_t--)
{
solve();
}
system("pause");
}
参考文章
|