首页 > 其他分享 >パナソニックグループ プログラミングコンテスト2024（ABC 375）

パナソニックグループ プログラミングコンテスト2024（ABC 375）

时间：2024-10-13 09:32:17浏览次数：1  
标签：ABC int long 2024 ans dis 375 id op

罚时不好吃，一口都没吃

形象理解这一场的 C

A.Seats \(\text{diff }20\)

对给定序列 \(S\) 找出 \(i\) 的个数,使得 \(S_{i}=0,S_{i+1}=1,S_{i+2}=0\)

#define int long long
string x;

signed main(){
	int n;cin>>n;
	cin>>x;
	int ans=0;
	for(int i=0;i<=(int)x.length()-3;++i){
		if(x[i]=='#' and x[i+2]=='#' and x[i+1]=='.'){
			ans++;
		}
	}
	cout<<ans;
}

B.Traveling Takahashi Problem \(\text{diff }65\)

给定平面上 \(N\) 个点，求从原点出发按编号顺序走完 \(N\) 个点并走回原点的直线距离之和

#include<bits/stdc++.h>
using namespace std;
#define int long long
long double dist(int x1,int y1,int x2,int y2){
	return sqrtl((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int n;
int nx=0,ny=0;
long double ans=0;
signed main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		int x,y;
		cin>>x>>y;
		ans+=dist(nx,ny,x,y);
		nx=x;ny=y;
	}
	ans+=dist(nx,ny,0,0);
	printf("%.20Lf",ans);
}

C.Spiral Rotation \(\text{diff }972\)

给定一个 \(N\times N\) 的 \(01\) 矩阵，\(N\) 为偶数，对每个 \(i\in[1,\frac{N}{2}]\) 执行如下操作

  • 选择所有 \(i\le x,y\le N-i+1\)，将 \((y,N-x+1)\) 上的值替换为 \((x,y)\) 上的值

对于每一个 \(i\)，对所有 \((x,y)\) 的替换同时发生，也即在每一个 \(i\) 内不存在覆盖的情况
输出最终的矩阵

\(N\le 10^3\)

通过手摸可以发现，对单独的一个 \(i\) 来说，相当于四个一组发生旋转

点击查看

但是这里有一个 \(i\in[1,\frac{N}{2}]\)，这其实相当于是分层的，先整体转，再转第二层和以内的，再转第三层和以内的，相当于第一层转一圈，第二层转两圈，以此类推

可以发现转四圈不会影响结果，因此第 \(k\) 层转 \(k\mod 4\) 圈就行了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
char mp[3001][3001];
bool vis[3001][3001];
signed main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			cin>>mp[i][j];
		}
	}
	for(int k=1;k<=n/2;++k){
		for(int i=k;i<=n-k+1;++i){
			if(!vis[i][k]){
				if(k%4==1){
					int x1=i,y1=k;
					int x2=y1,y2=n-x1+1;
					int x3=y2,y3=n-x2+1;
					int x4=y3,y4=n-x3+1;
					char tmp=mp[x4][y4];
					mp[x4][y4]=mp[x3][y3];
					mp[x3][y3]=mp[x2][y2];
					mp[x2][y2]=mp[x1][y1];
					mp[x1][y1]=tmp;
					vis[x1][y1]=true;
					vis[x2][y2]=true;
					vis[x3][y3]=true;
					vis[x4][y4]=true;
				}
				else if(k%4==2){
					int x1=i,y1=k;
					int x2=y1,y2=n-x1+1;
					int x3=y2,y3=n-x2+1;
					int x4=y3,y4=n-x3+1;
					char tmp=mp[x4][y4];
					mp[x4][y4]=mp[x3][y3];
					mp[x3][y3]=mp[x2][y2];
					mp[x2][y2]=mp[x1][y1];
					mp[x1][y1]=tmp;
					tmp=mp[x4][y4];
					mp[x4][y4]=mp[x3][y3];
					mp[x3][y3]=mp[x2][y2];
					mp[x2][y2]=mp[x1][y1];
					mp[x1][y1]=tmp;
					vis[x1][y1]=true;
					vis[x2][y2]=true;
					vis[x3][y3]=true;
					vis[x4][y4]=true;
				}
				else if(k%4==3){
					int x1=i,y1=k;
					int x2=y1,y2=n-x1+1;
					int x3=y2,y3=n-x2+1;
					int x4=y3,y4=n-x3+1;
					char tmp=mp[x4][y4];
					mp[x4][y4]=mp[x3][y3];
					mp[x3][y3]=mp[x2][y2];
					mp[x2][y2]=mp[x1][y1];
					mp[x1][y1]=tmp;
					tmp=mp[x4][y4];
					mp[x4][y4]=mp[x3][y3];
					mp[x3][y3]=mp[x2][y2];
					mp[x2][y2]=mp[x1][y1];
					mp[x1][y1]=tmp;
					tmp=mp[x4][y4];
					mp[x4][y4]=mp[x3][y3];
					mp[x3][y3]=mp[x2][y2];
					mp[x2][y2]=mp[x1][y1];
					mp[x1][y1]=tmp;
					vis[x1][y1]=true;
					vis[x2][y2]=true;
					vis[x3][y3]=true;
					vis[x4][y4]=true;
				}
			}
		}
		for(int j=k+1;j<=n-k;++j){
			if(!vis[k][j]){
				if(k%4==1){
					int x1=k,y1=j;
					int x2=y1,y2=n-x1+1;
					int x3=y2,y3=n-x2+1;
					int x4=y3,y4=n-x3+1;
					char tmp=mp[x4][y4];
					mp[x4][y4]=mp[x3][y3];
					mp[x3][y3]=mp[x2][y2];
					mp[x2][y2]=mp[x1][y1];
					mp[x1][y1]=tmp;
					vis[x1][y1]=true;
					vis[x2][y2]=true;
					vis[x3][y3]=true;
					vis[x4][y4]=true;
				}
				else if(k%4==2){
					int x1=k,y1=j;
					int x2=y1,y2=n-x1+1;
					int x3=y2,y3=n-x2+1;
					int x4=y3,y4=n-x3+1;
					char tmp=mp[x4][y4];
					mp[x4][y4]=mp[x3][y3];
					mp[x3][y3]=mp[x2][y2];
					mp[x2][y2]=mp[x1][y1];
					mp[x1][y1]=tmp;
					tmp=mp[x4][y4];
					mp[x4][y4]=mp[x3][y3];
					mp[x3][y3]=mp[x2][y2];
					mp[x2][y2]=mp[x1][y1];
					mp[x1][y1]=tmp;
					vis[x1][y1]=true;
					vis[x2][y2]=true;
					vis[x3][y3]=true;
					vis[x4][y4]=true;
				}
				else if(k%4==3){
					int x1=k,y1=j;
					int x2=y1,y2=n-x1+1;
					int x3=y2,y3=n-x2+1;
					int x4=y3,y4=n-x3+1;
					char tmp=mp[x4][y4];
					mp[x4][y4]=mp[x3][y3];
					mp[x3][y3]=mp[x2][y2];
					mp[x2][y2]=mp[x1][y1];
					mp[x1][y1]=tmp;
					tmp=mp[x4][y4];
					mp[x4][y4]=mp[x3][y3];
					mp[x3][y3]=mp[x2][y2];
					mp[x2][y2]=mp[x1][y1];
					mp[x1][y1]=tmp;
					tmp=mp[x4][y4];
					mp[x4][y4]=mp[x3][y3];
					mp[x3][y3]=mp[x2][y2];
					mp[x2][y2]=mp[x1][y1];
					mp[x1][y1]=tmp;
					vis[x1][y1]=true;
					vis[x2][y2]=true;
					vis[x3][y3]=true;
					vis[x4][y4]=true;
				}
			}
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			cout<<mp[i][j];
		}
		cout<<'\n';
	}
}

D.ABA \(\text{diff }658\)

给定一个字符串 \(S\)，求满足下列条件的 \((i,j,k)\) 对数

  • \(i\lt j\lt k\)
  • \(S_i,S_j,S_k\) 能构成回文

\(|S| \le 2\times 10^5\)

其实也就是找 \(S_i=S_k\) 的对数，然后中间填什么都行

注意到两个相等的数，如果位置分别为 \(i,j\)，那么它们中间夹着的任何一个数都能造成贡献，也即贡献为 \(j-i-1\)

如果枚举到一个数 \(S_i\) 时，有 \(k\) 个数（\(S_{j1},S_{j2}\cdots\)）与其相等，则对答案的贡献应该是 \((S_i-S_{j1}-1)+(S_i-S_{j2}-1)\cdots=k(S_i-1)-\sum S_{j}\)

因此维护前缀和即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int possum[27];
int poscnt[27];
string x;
int ans=0;
signed main(){
	cin>>x;
	for(int i=0;i<=(int)x.length()-1;++i){
		ans+=max(0ll,(i-1)*poscnt[x[i]-'A']-possum[x[i]-'A']);
		poscnt[x[i]-'A']++;
		possum[x[i]-'A']+=i;
	}
	cout<<ans;
}

E.3 Team Division \(\text{diff }1424\)

有三支队伍和 \(N\) 个人，每支队伍初始有一定人数，每个人有权值 \(B_i\)，可以移动任意队伍中的人，问三支队伍的权值和相等所需的最小移动次数

\(N\le 100,\sum B_i\le 1500\)

首先注意到

  • \(\sum B_i \not \equiv 0\pmod 3\) 无解

考虑换种思路做，清空所有队里的人，然后一个一个往里填，如果当前填的人本来就在这个队里，则对移动次数无贡献，否则有 \(1\) 的贡献

然后，注意到最终每个队的总和不超过 \(\frac{\sum B_i}{3}=500\)，因此设计 \(f_{i,j,k}\) 表示放到第 \(i\) 个人，第一队有 \(j\) 的权值和，第二队有 \(k\) 的权值和的最少交换次数（第三队可以用 \(\sum B_i-j-k\) 算出来）

直接枚举每个人填数即可

最后从 \(f_{n,\frac{\sum}{3},\frac{\sum}{3},\frac{\sum}{3}}\) 统计答案

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[101],b[101];
int f[101][501][501];
int sum[5];
int tot;
signed main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i]>>b[i];
		sum[a[i]]+=b[i];
		tot+=b[i];
	}
	if(tot%3!=0){
		cout<<-1;
		return 0;
	}
	memset(f,0x3f,sizeof f);
	f[0][0][0]=0;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=tot/3;++j){
			for(int k=0;k<=tot/3;++k){
				if(j>=b[i]) f[i][j][k]=min(f[i][j][k],f[i-1][j-b[i]][k]+(a[i]!=1));
				if(k>=b[i]) f[i][j][k]=min(f[i][j][k],f[i-1][j][k-b[i]]+(a[i]!=2));
				if(tot-j-k>=b[i]) f[i][j][k]=min(f[i][j][k],f[i-1][j][k]+(a[i]!=3));
			}
		}
	}
	if(f[n][tot/3][tot/3]>=0x3f3f3f3f3f3f3f3f){
		cout<<-1;
		return 0;
	}
	cout<<f[n][tot/3][tot/3]<<endl;
}

F.Road Blocked \(\text{diff }1546\)

无向图中实现如下操作

  • 1 i 删除第 \(i\) 条边
  • 2 x y 查询 \(x,y\) 两点的最短路径长度

\(N\le 300,Q\le 2\times 10^5\)

有删边，应该倒过来处理询问

然后考虑加边怎么处理变化

用 DP 的思路，加了边之后，只有经过这条边两个端点的路径才能有可能改变，因为 \(N\) 比较小，因此考虑将这条新加的边的两个端点当中转点，枚举所有点对的路径来更新

类似弗洛伊德（其实就是弗洛伊德）

#include<bits/stdc++.h>
using namespace std;
#define int long long
int f[301][301];
int n,m,q;
struct edge{
	int l,r,w;
}e[300*300+1];
struct opera{
	int op;
	int id;
	int x,y;
}op[200001];
bool vis[300*300+1];
vector<int>ans;
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>q;
	for(int i=1;i<=m;++i){
		int x,y,z;cin>>x>>y>>z;
		e[i]={x,y,z};
	}
	for(int i=1;i<=q;++i){
		cin>>op[i].op;
		if(op[i].op==1){
			cin>>op[i].id;
			vis[op[i].id]=true;
		}
		else{
			cin>>op[i].x>>op[i].y;
		}
	}
	memset(f,0x3f,sizeof f);
	for(int i=1;i<=m;++i){
		if(!vis[i]){
			f[e[i].l][e[i].r]=min(f[e[i].l][e[i].r],e[i].w);
			f[e[i].r][e[i].l]=min(f[e[i].r][e[i].l],e[i].w);
		}
	}
	for(int k=1;k<=n;++k){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
			}
		}
	}
	for(int t=q;t>=1;--t){
		if(op[t].op==1){
			f[e[op[t].id].l][e[op[t].id].r]=min(f[e[op[t].id].l][e[op[t].id].r],e[op[t].id].w);
			f[e[op[t].id].r][e[op[t].id].l]=min(f[e[op[t].id].r][e[op[t].id].l],e[op[t].id].w);
			// cout<<"add "<<e[op[t].id].l<<" "<<e[op[t].id].r<<endl;
			for(int i=1;i<=n;++i){
				for(int j=1;j<=n;++j){
					f[i][j]=min(f[i][j],f[i][e[op[t].id].l]+f[e[op[t].id].l][j]);
				}
			}
			for(int i=1;i<=n;++i){
				for(int j=1;j<=n;++j){
					f[i][j]=min(f[i][j],f[i][e[op[t].id].r]+f[e[op[t].id].r][j]);
				}
			}
		}
		if(op[t].op==2){
			if(f[op[t].x][op[t].y]>=0x3f3f3f3f3f3f3f3f){
				ans.push_back(-1);
			}
			else ans.push_back(f[op[t].x][op[t].y]);
		}
	}
	std::reverse(ans.begin(),ans.end());
	for(int i:ans){
		cout<<i<<"\n";
	}
}

G.Road Blocked 2 \(\text{diff }2014\)

对给定无向图判断：

  • 对所有 \(i\in[1,m]\)，如果将第 \(i\) 条边删去，\(1\) 至 \(N\) 的最短路径是否发生变化

\(N,M\le 2\times 10^5\)

看的第二篇题解

判断这个其实就是判断一条边是不是会被所有 \(1\) 到 \(N\) 的最短路经过

我们可以根据 \(dis\) 判一下边 \((x,y)\) 是否在最短路上：

\[dis_{1,x}+w_{x,y}+dis_{y,N}=dis_{1,N} \]

或者反着来也行，但是这样我们就能判断其是否在最短路上

然后我们需要判断一条边是否为所有最短路的必经边，判断一条边被几条最短路径经过是不容易的，但是判断 \(1\) 到一个节点有几条最短路径是容易的

因此我们可以这样判断：

  • 如果 \(1\) 到 \(x\) 有 \(c_x\) 条最短路径，到 \(N\) 有 \(c_N\) 条最短路径，\(N\) 到 \(y\) 有 \(c_y\) 条最短路径，则如果 \(c_x\times c_y=c_N\)，那么就说明边 \((x,y)\) 是最短路必经边

这么做有一个好处就是分别拿 \(1,N\) 跑两边最短路就能统计答案

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m; 
const int p=1e9+7;
struct __edge{
	int to,w;
};
vector<__edge>e[200001];
struct ___edge{
	int from,to,w;
};
___edge edge[200001];
int dis[2][200001];
bool vis[2][200001];
int cnt[2][200001];
struct node{
	int id,dis;
	bool operator <(const node &A)const{
		return dis>A.dis;
	}
};
priority_queue<node>q;
void dij(int s,int id){
	memset(dis[id],0x3f,sizeof dis[id]);
	memset(vis[id],0,sizeof vis[id]);
	memset(cnt[id],0,sizeof cnt[id]);
	dis[id][s]=0;
	cnt[id][s]=1;
	q.push({s,dis[id][s]});
	while(!q.empty()){
		node u=q.top();q.pop();
		if(dis[id][u.id]<u.dis) continue;
		if(vis[id][u.id]) continue;
		vis[id][u.id]=true;
		for(__edge i:e[u.id]){
			if(dis[id][i.to]>dis[id][u.id]+i.w){
				dis[id][i.to]=dis[id][u.id]+i.w;
				q.push({i.to,dis[id][i.to]});
				cnt[id][i.to]=cnt[id][u.id];
			}
			else if(dis[id][i.to]==dis[id][u.id]+i.w){
				cnt[id][i.to]=(cnt[id][i.to]+cnt[id][u.id])%p;
			}
		}
	}
}
signed main(){
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
        edge[i]={u,v,w};
    }
	dij(1,0);
	dij(n,1);
	for(int i=1;i<=m;++i){
		int u=edge[i].from,v=edge[i].to,w=edge[i].w;
		if((dis[0][u]+w+dis[1][v]==dis[0][n] and cnt[0][u]*cnt[1][v]%p==cnt[0][n])
		or (dis[0][v]+w+dis[1][u]==dis[0][n] and cnt[0][v]*cnt[1][u]%p==cnt[0][n])){
			cout<<"Yes\n";
		}
		else{
			cout<<"No\n";
		}
	}
}
林妹妹，赢！

哥们图床现在比较富有

标签：ABC,int,long,2024,ans,dis,375,id,op
From： https://www.cnblogs.com/HaneDaCafe/p/18461839

相关文章

  • 多校A层冲刺NOIP2024模拟赛06
    A.小Z的手套（gloves）明现的二分，我们先排序，假定\(a\)数组个数少，我们就对每一个\(a_i\)找一个\(b_i\)使其差不超过二分的值，然后贪心来讲，肯定找相差最大的那组但差不超过二分值的那个数最优，且先找比他小的那组（因为排过序了），然后套个\(multiset\)就过了，虽然\(n{log_n}^2\)......
  • [赛记] 多校A层冲刺NOIP2024模拟赛06
    小Z的手套（gloves）100pts最大值最小，考虑二分答案；首先排序，然后每次找出数量较少的那个数组中的每个数$x$在另一个数组中有没有值在范围$[x-mid,x+mid]$的（其中$mid$为二分的答案），其实只需找$x-mid$就行，最后判断一下所有数是否合法即可；因为已经升序排序，所以......
  • 多校A层冲刺NOIP2024模拟赛06
    多校A层冲刺NOIP2024模拟赛06\(T1\)A.小Z的手套（gloves）\(100pts/100pts\)容易发现将选出的左右手套各升序排序后，同一个位置上的两只手套的尺码差距一定在答案的候选集合里，画个数轴分讨一下就证完了。部分分\(20\%\)：因为\(n=m\)所以不用管谁选谁不选的问题，故\(......
  • 多校 A 层冲刺 NOIP2024 模拟赛 06
    多校A层冲刺NOIP2024模拟赛06T小Z的手套（gloves）签到题答案显然具有单调性，排序后二分答案即可。T小Z的字符串（string）签到题注意到\(n\)较小，可以使用\(O(n^3)\)的算法，直接上大\(DP\)。设计状态\(f_{i,j,k,0/1/2}\)表示从左往右填到\(i\)位，已经填了\(j\)个\(0......
  • 2024-2025-1 20241412《计算机基础与程序设计》第三周学习总结
    2024-2025-120241412《计算机基础与程序设计》第三周学习总结作业信息这个作业属于哪个课程[2024-2025-1-计算机基础与程序设计]https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP这个作业要求在哪里[2024-2025-1计算机基础与程序设计第一周作业]https://edu......
  • Panasonic Programming Contest 2024（AtCoder Beginner Contest 375）
    PanasonicProgrammingContest2024（AtCoderBeginnerContest375）\(A\)Seats\(AC\)基础字符串。点击查看代码intmain(){intn,ans=0,i;strings;cin>>n>>s;for(i=0;i<n;i++){ans+=(s[i]=='#'&&s[i......
  • [赛记] 多校A层冲刺NOIP2024模拟赛05
    这场数数好数（number）100pts找三个数的和，而且允许$\Theta(n^2)$，那么我们可以维护出两个数的和，然后每次顺序遍历找这个数减去前面的某个数在任意两个数的和中有没有出现过，这个也是$\Theta(n^2)$的；所以时间复杂度：$\Theta(n^2)$，如果带$\log$会过不去，要用桶维护；点击......
  • 2024java最新面试题-10张图！彻底搞定Java线程状态转换
    Java线程状态有几个？Java线程状态是如何转换？Java线程状态转换什么情况会进入锁的等待队列？Java线程状态转换什么情况会进入锁的同步队列？一提到Java线程状态，不少读者立马想到线程状态转换图，但细想，印象又不深刻，只记得有那么几个状态。再要你说出Java线程状态是如何转换的，脑子里......
  • Hoverfly 任意文件读取漏洞(CVE-2024-45388)
    漏洞简介Hoverfly是一个为开发人员和测试人员提供的轻量级服务虚拟化/API模拟/API模拟工具。其 /api/v2/simulation​的POST处理程序允许用户从用户指定的文件内容中创建新的模拟视图。然而，这一功能可能被攻击者利用来读取Hoverfly服务器上的任意文件。尽管代码禁止指定绝......
  • 2024.10.12
    根据你提供的MyBatis配置文件，确实有一个小问题需要注意：驼峰命名配置你已将mapUnderscoreToCamelCase设置为注释（<!--<settingname="mapUnderscoreToCamelCase"value="true"/>-->），这意味着驼峰命名转换功能被禁用了。为了启用它，你需要取消注释并确保该设置的值为true。修......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99