2022“杭电杯”中国大学生算法设计超级联赛（3）

Cyber Language 

输出每个字符串对应的网络语言。

思路：以空格分段，输出每个空格后的字母大写，注意开头。

AC Code：

#include 
 
int t;
std::string s;
 
int main(){
    std::cin>>t;
    getchar();
    while(t--){
        getline(std::cin,s);
        std::cout<<(char)(s[0]+'A'-'a');
        int len=s.length();
        for(int i=1;i
            if(s[i]==' '&&i+1<=len-1) std::cout<<(char)(s[i+1]+'A'-'a');
        }
        std::cout<<'\n';
    }
    return 0;
}

 os：很好，签到完直接罚坐五小时。

Package Delivery

给出每个快递到达的时间和每个快递滞留的时间，必须在滞留的时间段内去拿快递，问这若干个快递最少需要去拿几次可以拿完。

思路：大佬的思路 统计每个截止日期的物品，对于每个截止日期，若物品个数时k的倍数，那直接无余数的取出；若不是k的倍数，那就找最接近这个日期的物品取走，在此用堆

硬件 设计题目

zip 0星 超过10%的资源 1.37MB

下载

AC Code：

#include 
 
typedef std::pair<int,int>PII;
const int N=5e5+5;
int t,n,k;
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>t;
    while(t--){
        std::cin>>n>>k;
        std::vectorin;
        std::vector<int>out;
        for(int i=1;i<=n;i++){
            int l,r;
            std::cin>>l>>r;
            in.push_back({l,r});
            out.push_back(r);
        }
        std::sort(in.begin(),in.end());
        std::sort(out.begin(),out.end());
        std::priority_queue<int,std::vector<int>,std::greater<int>>pq;
        int cur=0,ans=0;
        for(auto it:out){
            int cnt=0;
            while(curpush(in[cur++].second);
            //in[cur].first<=it,筛选在it这天之前已经存在的物品，push的是过期的时间
            while(!pq.empty()&&pq.top()==it) cnt++,pq.pop();
            //统计截止时间在it当天的物品数
            ans+=cnt/k;
            if(cnt%k==0) continue;
            //当天的物品数量就是k的整数倍
            int extra=k-cnt%k;
            while(!pq.empty()&&extra--) pq.pop();
            //还不到截止时间的物品也在it这天取出，尽量将取出的物品数凑成k的整数倍
            //pq是大顶堆，所以优先pop的是截止时间更小更接近it的物品
            ans++;
        }
        std::cout<'\n';
    }
    return 0;
}

Two Permutations

给出两个序列p，q，和长度为2n的序列s，每次选择p或q最左端的数字插入s序列右端，问这两个数列有多少种构造出s的方案，输出答案模998244353。

思路：考虑DP，即f[i][j]表示到p的第i个数和q的第j个数有多少种构造方案，因为给出的是permutation，则每个数会在构造的序列中出现两次，发现只要记录上次匹配的是哪个序列即可，将两维压成一维，递归求解即可。

AC Code：

#include 
 
const int N=1e6+5;
const int mod=998244353;
int t,n;
int q[N],p[N],s[N];
int f[N][2];
bool vis[N][2];
 
int cal(int x,int y,int u){
	if(x>n&&y>n) return 1;
	if(vis[x+y-1][u]) return f[x+y-1][u];
	int res=0;
	if(p[x]==s[x+y-1]&&x<=n) (res+=cal(x+1,y,0))%=mod;
	if(q[y]==s[x+y-1]&&y<=n) (res+=cal(x,y+1,1))%=mod;
	vis[x+y-1][u]=true;
	return f[x+y-1][u]=res;
}
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n;
		for(int i=0;i<=(n<<1)+2;i++){
			f[i][0]=f[i][1]=0;
			vis[i][0]=vis[i][1]=false;
		}
		for(int i=1;i<=n;i++){
			std::cin>>p[i];
		}
		for(int i=1;i<=n;i++){
			std::cin>>q[i];
		}
		for(int i=1;i<=(n<<1);i++){
			std::cin>>s[i];
		}
		int ans=0;
		if(p[1]==s[1]) (ans+=cal(2,1,0))%=mod;
		if(q[1]==s[1]) (ans+=cal(1,2,1))%=mod;
		std::cout<'\n';
	}
	return 0;
}

在cal函数中，x，y分别代表p和q匹配到的位置，u表示匹配的状态，分情况递归求方案数，记得取模。

太离谱了，补不动啊