首页 > 其他分享 >Codeforces Round 938 (Div. 3)题解（A-E）

Codeforces Round 938 (Div. 3)题解（A-E）

时间：2024-04-09 19:46:32浏览次数：21  
标签：int 题解 ll long -- 938 solve Div include

A. Yogurt Sale
题意：输入一份酸奶a元，两份b元，求买n份酸奶最少要多少钱。

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6+7;

void solve(){
	int n,a,b; cin>>n>>a>>b;
	if(n%2==0){
		if(a*2<=b) cout<<a*n<<'\n';
		else cout<<b*n/2<<'\n';
	}
	else{
		if(a*2<=b) cout<<a*n<<'\n';
		else{
			cout<<a+b*(n-1)/2<<'\n';
		}
	} 
	
	return;
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int T=1;
	cin>>T;
	while(T--){
		solve();
	} 	
	return 0;
}

B. Progressive Square
题意：给n*n个数，问这些数能否排成满足
$ a_{i+1,j} = a_{i,j} + c $
$ a_{i,j+1} = a_{i,j} + d $

思路：
显然\(a_{11}\)最小，
将数组存在哈希表里，让给定数组中最小的数作为\(a_{11}\)，按题意补充矩阵中剩余元素，若对应数不存在输出NO，存在-1

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const ll N = 1e8+7;

void solve(){
	ll n,c,d; cin>>n>>c>>d;
	ll mn=1e11;
	map<int,int> vis;
	
	for(ll i=1;i<=n*n;i++){
		ll num; cin>>num;
		if(mn>num) mn=num;
		vis[num]++;
	}
	
	ll mtx[n+7][n+7];
	mtx[1][1]=mn;
	ll temp;
	for(ll i=2;i<=n;i++){
		temp=mtx[1][i]=mtx[1][i-1]+c;
		if(vis[temp]>0) vis[temp]--;
		else{
			cout<<"NO"<<'\n';
			return;
		}
	}
	for(ll i=2;i<=n;i++){
		temp=mtx[i][1]=mtx[i-1][1]+d;
		if(vis[temp]>0) vis[temp]--;
		else{
			cout<<"NO"<<'\n';
			return;
		}
	}
	for(ll i=2;i<=n;i++){
		for(ll j=2;j<=n;j++){
			temp=mtx[i][j]=mtx[i][j-1]+c;
			if(vis[temp]>0) vis[temp]--;
			else{
				cout<<"NO"<<'\n';
				return;
			}
		}
	}
	
	cout<<"YES"<<'\n';
	return;
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int T=1;
	cin>>T;
	while(T--){
		solve();
	} 	
	return 0;
}

C. Inhabitant of the Deep Sea
题意：有n次射击机会，每次向最左和最右交替射击，每次射击-1生命。能击沉多少船。
思路：完全模拟肯定超时，数据规模是1e15

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;

void solve(){
	ll n,k; cin>>n>>k;
	ll ft=(k+1)/2; int bk=k/2;
	ll ans=0;
	ll ship[n+7];
	ll sum=0;
	for(ll i=1;i<=n;i++){
		cin>>ship[i];
		sum+=ship[i];
	}
	if(sum<=k){
		cout<<n<<'\n';
		return;
	}
      
    ll l=1,r=n;
    while(ft>0){
        if(ft>=ship[l]) ans++;
        ft-=ship[l];
        l+=1;
    }
    while(bk>0){
        if(bk>=ship[r]) ans++;
        bk-=ship[r];
        r-=1;
    }

	cout<<ans<<'\n';
	
	return;
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int T=1;
	cin>>T;
	while(T--){
		solve();
	} 	
	return 0;
}

D. Inaccurate Subsequence Search
题意：有长度为n的数组a和长度为m的数组b，求a长度为m的子段中，有多少个子段是“好的”，即至少k个元素与数组b中的元素匹配。
思路：b存哈希表vis，写一个缓存的哈希表tmp，对a遍历，每次重新对tmp重新初始化
代码实现：

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int MXN=1e6+7;

void solve(){
	int n,m,k; cin>>n>>m>>k;
	int ans=0;
	int a[n+7],b[m+7];
	map<int, int> vis;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++){
		cin>>b[i]; 
		vis[b[i]]++;
	}
	
	for(int i=1;i<=n-m+1;i++){
		int sum=k;
		map<int, int> tmp;
		for(int t=1;t<=m;t++){ 
			tmp[b[t]]=vis[b[t]];
		}
		for(int j=0;j<m;j++){
			if(tmp[a[i+j]]>0){
				sum--;
				tmp[a[i+j]]--;
			}
		}
		if(sum<=0) ans++;
	//	cout<<ans<<' ';
	}
	
	cout<<ans<<'\n';
	
	return;
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int T=1;
	cin>>T;
	while(T--){
		solve();
	} 	
	return 0;
}

上述代码不出所料的在test4超时了,用滑动窗口

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int MXN=1e6+7;

void solve(){
	int n,m,k; cin>>n>>m>>k;
	int a[n+7],b[m+7];
	map<int, int> vis;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++){
		cin>>b[i]; 
		vis[b[i]]++;
	}
	
	ll res=0,ans=0;
	map<int, int> tmp;
    for(int i=1;i<=n;i++){
        if(i>m){
            if(tmp[a[i-m]]<=vis[a[i-m]]) res--;
            tmp[a[i-m]]--;
        }
        if(tmp[a[i]]<vis[a[i]]) res++;
        tmp[a[i]]++;
        if(i>=m && res>=k) ans++;
    }
	
	cout<<ans<<'\n';
	
	return;
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int T=1;
	cin>>T;
	while(T--){
		solve();
	} 	
	return 0;
}

E. Long Inversions
题意：给定以0和1构成的字符串，可以选定一个长度为k的区间对0和1进行翻转，求最大能使字符串都为1的k。
思路：从长度n开始遍历，用check()检查合法。check()使用了差分数组存储是否翻转。

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int N=5010;
string s;
int n;
int d[N];//差分数组 是否操作过 
int a[N];

bool check(int x){
	for(int i=1;i<=n;i++) d[i]=0;
	for(int i=1;i<=n;i++){
		d[i]^=d[i-1]; //<1> 
		if((a[i]^d[i])==0){
			if(i+x-1>n) return 0;
			d[i]^=1;//<2>
			d[i+x]^=1;//<3>
		}
	}
	return 1;
}

// <1>-<3>记录了哪些位置进行了（奇数次）翻转操作 

void solve(){
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		a[i]=s[i-1]-'0';
	}
	
	for(int i=n;i>=1;i--){
		if(check(i)) {
			cout<<i<<'\n';
			return;
		}
	}
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int T=1;
	cin>>T;
	while(T--){
		solve();
	} 	
	return 0;
}

有关差分数组https://zhuanlan.zhihu.com/p/635853214

标签：int,题解,ll,long,--,938,solve,Div,include
From： https://www.cnblogs.com/Zephyr-qwq/p/18124645/cfr938div3

相关文章

  • ARC080F Prime Flip 题解
    传送门题意：给定初始\(a\)数组，每次可以选一个长度为奇质数的区间取反。问全变成\(0\)要多少次操作。和Password、XorReplace的套路相同，做一个差分。令\(b_i=a_i\xora_{i-1}\)，目的就是让\(b\)数组变为全\(0\)。对\(a_i\sima_{i+p-1}\)取反相当于对\(b_i,b_{i+p......
  • Codeforces Round 938 (Div. 3) E
    链接有点意思的题目。首先可以得到的一个结论就是，如果k能够完成，那唯一的操作方法就是从前往后，遇到0就使用，把这个点变成1。那么我们就能够做到O(n)验证了，然后发现O(n^2)可以接受，就过了。但是我因为滥用数据结构，导致我认为验证需要O(nlogn)然后5000又刚刚好跑不过去。所以觉得......
  • 题解：P10234 [yLCPC2024] B. 找机厅
    题意简述给你一个长\(n\)宽\(m\)的\(01\)迷宫，从\((1,1)\)开始要走到\((n,m)\)。如果能走那么输出最短路和路径（路径用\(LRUD\)表示），否则输出\(-1\)。有\(t\)组数据。如果当前格子是\(0\)那么你只能走到\(1\)的格子，反之亦然。思路考虑使用\(BFS\)，每次走......
  • tomcat AJP 任意文件读取/包含漏洞（CVE-2020-1938）
    漏洞描述TomcatAJP协议中存在缺陷，攻击者可以读取或包含Tomcat的webapp目录中的任何文件。漏洞危害:读取webapp配置文件或源代码。如果攻击者读取配置文件得到敏感用户名和下面，tomcatWeb应用开放manager目录具有文件上传功能2.1可以直接上传shell获取控制权，2.2通过Gho......
  • AtCoder Beginner Contest 348 A-F 题解
    A-PenaltyKickQuestion高桥将在一场足球比赛中获得\(N\)个点球。对于第\(i\)个罚球，如果\(i\)是\(3\)的倍数，他将罚球失败，否则罚球成功。请打印他罚球的结果。Solution当\(i\%3==0\)时说明能被\(3\)整除Code#include<bits/stdc++.h>usingnamespacest......
  • SP30785的题解
    （一）树链剖分板子题。支持单点取反，区间查询。在线段树的每一个节点上分别记录全为\(1\)或全为\(0\)。代码挺好理解的。（二）AC代码。#include<bits/stdc++.h>usingnamespacestd;constintmxn=3e5+10;intn,q,head[mxn],cnt,id[mxn],cntt,fa[mxn],cnt1,son[mxn],siz[m......
  • 【蓝桥·算法双周赛 第 9 场 小白入门赛】字符迁移【算法赛】题解（字符串+模运算+差分）
    思路差分数组是一种特殊的数组，它的第iii个数定义为原数组的第ii......
  • 【蓝桥·算法双周赛 第 4 场 小白入门赛】自助餐【算法赛】题解（分支+字符串）
    思路首先定义一个整型变量n和一个长整型变量ans，其中n用于存放输入的字符串个数，ans则用于累计所有字符串对应的价格。在接收到n之后，进入一个循环，在循环中，每次接收一个字符串s，并根据s的首字母判断该字符串对应的餐盘种类，并将其价格累加到ans中。具体来说，如果......
  • newstart 部分题解和pwn相关的学习
    做newstart的pwnpieee题的pie的学习首先：对于pieee这道题很简单的栈溢出，除了NX其他的保护都开了，然后呢在左边也发现了后门函数相对偏移为0x1264（对于这里我们只用关心后三位，因为pie不会随机化地址的低12位，通俗点说就是我们十六进制地址的后三位）而一般而言后三位的地址能够确定我......
  • 【题解】洛谷马的遍历
    马的遍历方法：广度优先搜索源代码如下#include<iostream>#include<queue>#include<cstdio>#include<cstring>usingnamespacestd;structcoord{//结构体定义x,y坐标intx,y;};queue<coord>Q;intans[500][500];//-1代表未访问intwalk[8......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99