第27次CCF-CSP计算机软件能力认证（2022-09-18）

• 一、如此编码
• 二、何以包邮
• 三、防疫大数据
• 四、吉祥物投票

个人感想：算是完成了自己期望的目标300分吧，比之前进步了。第一题花了十五分钟，有十多分钟都是在看题。第二题01背包花了半个小时，太久没看class="superseo">动态规划了模板都忘得差不多。第三题的大模拟依旧有难度，写完的时候离比赛结束还剩一个小时。第四题大概看了一下应该是线段树，但是比线段树难，需要维护的数值有两个，线段树应该只能做一个，然后没去研究，暴力应该能拿点分的但是也做不动了（腰还给扭了QAQ）。

一、如此编码

解题思路：给出a数组求b数组，c数组为a数组前缀和。
可以看出b[i]*c[i-1]=m%c[i]-m%c[i-1]

#include
using namespace std;
int n,m,a[30],b[30],c[30];
int main()
{
	c[0]=1;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)c[i]=c[i-1]*a[i];
	for(int i=1;i<=n;i++)b[i]=(m%c[i]-m%c[i-1])/c[i-1];
	for(int i=1;i<=n;i++)cout<<b[i]<<" ";
	return 0;	
} 

二、何以包邮

解题思路：01背包，从m开始遍历就好了，最高位pre，也就是所有价值相加。

#include
using namespace std;
int n,x,a[50],dp[300050],pre;//dp数组容量1e4*30组 
int main()
{
	dp[0]=1;
	cin>>n>>x;
	for(int i=0;i<n;i++)cin>>a[i],pre+=a[i];//pre最大容量 
	for(int i=0;i<n;i++)
	{
		for(int j=pre;j>=a[i];j--)
		{
			dp[j]=max(dp[j],dp[j-a[i]]+a[i]);//01背包 
		}
	}
	for(int i=x;i<=pre;i++)
	{
		if(dp[i]>=x)
		{
			cout<<i<<endl;
			break;
		}
	}
	return 0;
}

三、防疫大数据

解题思路：关键其实在于存储的方式，set的存储可以自动从小到大排序并且可以去重（题目中有重复数据），听说有另一种解法是存储更新风险地区左右边界的，但是我没去尝试。

#include
using namespace std;
typedef long long ll;
set<ll>sd[1050],su;//sd存储第i天风险地区,su风险人员名单 
struct node{
	ll d,u,r;
}a;
vector<node>v[1050];
ll n,ri,mi,d,u,r,pi;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>ri>>mi;
		for(int j=1;j<=ri;j++)
		{
			cin>>pi;
			for(int j=i;j<i+7;j++)sd[j].insert(pi);//第j天插入风险地区pi 
		}
		for(int j=1;j<=mi;j++)
		{
			cin>>d>>u>>r;
			if(d<0)continue;//天数为负数必不可能高风险 
			if(!sd[d].count(r))continue;//r地区在第d天不是风险地区 
			a.d=d;
			a.u=u;
			a.r=r;
			v[i].push_back(a);//将记录第i天的第j个表格
		}
		for(int j=max(0,i-6);j<=i;j++)//从i-6天前开始遍历mi表，如果是七天前的信息就不需要隔离了(i-6) 
		{//最小从第0天开始 
			for(int k=0;k<v[j].size();k++)//遍历第j天的表 
			{
				a.d=v[j][k].d;
				a.u=v[j][k].u;
				a.r=v[j][k].r;
				if(a.d<=i-7)continue;//表内信息超过七天 
				bool flag=1;
				for(int l=a.d;l<=i;l++)
					flag&=sd[l].count(a.r);//确保一直为风险地区不间断 
				if(flag)//满足条件就隔离 
					su.insert(a.u);
			}
		}
		cout<<i;
		set<ll>::iterator it;
		for(it=su.begin();it!=su.end();it++)cout<<" "<<*it;
		cout<<endl;
		su.clear();
	}
	return 0;
}

四、吉祥物投票

写不动-_-了，第一眼看着像线段树。