2022-2023-1ACM集训队每周程序设计竞赛(12)题解-创新互联

问题 A: 富哥买水果

创新互联为企业级客户提高一站式互联网+设计服务,主要包括成都网站设计、网站制作、成都app开发、小程序开发、宣传片制作、LOGO设计等,帮助客户快速提升营销能力和企业形象,创新互联各部门都有经验丰富的经验,可以确保每一个作品的质量和创作周期,同时每年都有很多新员工加入,为我们带来大量新的创意。 

思路:输出yi等于0对应的下标i即可。

#include//#include//#include//#include#define cf int _;cin>>_;while(_--)
#define de cout<<"---"<,greater>q;
#define INF 0x3f3f3f3f
#define endl '\n'
//functiondfs = [&](int u);
//#define x first
//#define y second
using namespace std;
const int mod=998244353;
int n;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	vectora(5,0);
	int res=0;
	for(int i=0;i<5;i++){
		cin>>a[i];
		if(a[i]==0)res=i+1;
	}
	cout<

问题 B: 富哥买宠物

思路:显然y是偶数且大于等于2*x小于等于4*x时有解。

#include//#include//#include//#include#define cf int _;cin>>_;while(_--)
#define de cout<<"---"<,greater>q;
#define INF 0x3f3f3f3f
#define endl '\n'
#define eps 1e-6
//functiondfs = [&](int u);
//#define x first
//#define y second
using namespace std;
const int mod=998244353;
int n;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	int x,y;
	cin>>x>>y;
	if(y>=2*x&&y<=4*x&&y%2==0){
		cout<<"Yes";
	}
	else cout<<"No";
}

问题 C: 禁止出现

思路:由于N和pi都小于100,所以直接从小到大枚举Y到X的距离,然后判断Y是否在p内就行。

#include//#include//#include//#include#define cf int _;cin>>_;while(_--)
#define de cout<<"---"<,greater>q;
#define INF 0x3f3f3f3f
#define endl '\n'
#define eps 1e-6
//functiondfs = [&](int u);
//#define x first
//#define y second
using namespace std;
const int mod=998244353;
int n;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	int x;
	cin>>x>>n;
	sett;
	for(int i=0;i>tt;t.insert(tt);
	}
	for(int i=0;i<=100;i++){
		if(!t.count(x-i)){
			cout<

问题 D: 不能整除

思路:对于每个ai直接枚举所有因子判断是否在数组a内即可(对于ai要特殊判断ai这个因子)。

#include//#include//#include//#include#define cf int _;cin>>_;while(_--)
#define de cout<<"---"<,greater>q;
#define INF 0x3f3f3f3f
#define endl '\n'
//functiondfs = [&](int u);
//#define x first
//#define y second
using namespace std;
const int mod=998244353;
int n;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>n;
	vectora(n);
	vectorcnt(1000001,0);
	for(int i=0;i>a[i];
		cnt[a[i]]++;
	}
	int res=0;
	for(int i=0;i0)f=0;
				else if(j==a[i]&&cnt[j]>1)f=0;
				if(a[i]/j!=a[i]&&cnt[a[i]/j]>0)f=0;
				else if(a[i]/j==a[i]&&cnt[a[i]/j]>1)f=0;
			}
		}
		if(f)res++;
	}
	cout<

问题 E: 幼儿园老大

思路:对于每个班级用一个multiset去维护其中的可爱程度大的值是多少,然后将每个班级可爱程度大的值再放进存储答案的multiset中,去维护其中的最小值。接下来根据题意去模拟过程即可。

#include//#include//#include//#include#define cf int _;cin>>_;while(_--)
#define de cout<<"---"<,greater>q;
#define INF 0x3f3f3f3f
#define endl '\n'
//functiondfs = [&](int u);
//#define x first
//#define y second
using namespace std;
const int mod=998244353,N=2e5+10;
int n,q;
multisett[N];
multisetres;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>n>>q;
	vectora(n+1);
	vectorb(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		t[b[i]].insert(a[i]);
	}
	for(int i=1;i<=200000;i++){
		if(t[i].size()){
			auto j=t[i].rbegin();
			res.insert(*j);
		}
	}
	while(q--){
		int c,d;
		cin>>c>>d;
		res.erase(res.find(*t[b[c]].rbegin()));
		if(t[d].size())res.erase(res.find(*t[d].rbegin()));
		t[b[c]].erase(t[b[c]].find(a[c]));
		if(t[b[c]].size())res.insert(*t[b[c]].rbegin());
		t[d].insert(a[c]);
		res.insert(*t[d].rbegin());
		b[c]=d;
		cout<<*res.begin()<

问题 F: 付哥爱游泳

思路: 我们可以想到这是一个边权都为1的图求单源最短路,所以我们可以用Dijkstra算法,但由于边数可能很多所以我们要考虑如何去优化,对于一个点 i 来说如果经过他走到 j 所花费的代价比目前走到 j 的代价-1还要大的话,那么从 i 接着往下走显然是不优于从 j 开始往下走的所以这时候应该break,停止从 i 继续往后走的操作,这样从 i 走出的边数将大大减小,就可以得到答案了。

#include//#include//#include//#include#define cf int _;cin>>_;while(_--)
#define de cout<<"---"<,greater>q;
#define INF 0x3f3f3f3f
#define endl '\n'
//functiondfs = [&](int u);
//#define x first
//#define y second
using namespace std;
const int mod=998244353,N=1e6+10;
const int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n,m,k;
int x_1,x_2;
int y_1,y_2;
string a[N];
int dis[N];
bool f[N];
int id(int x,int y){
	return (x-1)*m+y;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	cin>>x_1>>y_1>>x_2>>y_2;
	for(int i=1;i<=n*m;i++)dis[i]=1e9;
	priority_queue,greater>q;
	for(int i=1;i<=n;i++){
		string t;
		cin>>t;
		a[i]=" "+t;
	}
	q.push({0,id(x_1,y_1)});
	dis[id(x_1,y_1)]=0;
	while(q.size()){
		auto t=q.top();
		q.pop();
		if(f[t.second])continue;
		f[t.second]=1;
		int x=t.second/m+1;
		int y=t.second%m;
		if(y==0){
			x--;
			y=m;
		}
		int last=id(x,y);
		for(int i=0;i<4;i++){
			int tx=x,ty=y;
			for(int j=1;j<=k;j++){
				tx+=d[i][0];
				ty+=d[i][1];
				int tem=id(tx,ty);
				if(tx<1||tx>n||ty<1||ty>m||a[tx][ty]=='@'||dis[tem]dis[id(x,y)]+1) {
					dis[tem]=dis[id(x,y)]+1;
					q.push({dis[tem],tem});
				}
			}
		}
	}
	if(dis[id(x_2,y_2)]==1e9){
		cout<<"-1";
	}
	else {
		cout<

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


名称栏目:2022-2023-1ACM集训队每周程序设计竞赛(12)题解-创新互联
浏览路径:http://scyanting.com/article/igdgg.html